Cross Validated
2025-11-17 13:36 UTC
Score 12.0
AI-113-20251117-social-media-57579708
It is widely known that if you were to calculate the maximizer of the dual SVM program (denote as $\alpha^*$ ), then the primal minimizer of the hard-margin SVM program, \begin{aligned}&{\underset {{w} ,\;b }{\operatorname {minimize} }}&&\|{w} \|_{2}^{2}\\&{\text{s.t.}}&&y_{i}({w} ^{\top }{x} _{i}-b)\geq 1\quad \forall i\in \{1,\dots ,N\}\end{aligned} can be found through the KKT conditions, in which case, $$w^*= \sum_{i = 1}^N \alpha^*_i y_i x_i$$ In particular, those $x_i$ corresponding to non-zero $\alpha^*_i$ are the famous support vectors. However, a technical detail that people seem to ignore is that this only holds if strong duality also holds. I struggled with verifying strong duality, so I searched widely online. Essentially, online reference argue that Slater's condition guarantees strong duality always hold for hard-margin SVM. Slater condition in this case can be written as either: There exists a pair $(w,b)$ that satisfies $y_{i}({w} ^{\top }{x} _{i}-b)> 1$ for all $i = 1, \ldots, N$ , or There exists a pair $(w,b)$ that satisfies $y_{i}({w} ^{\top }{x} _{i}-b)\geq 1$ , for all $i = 1, \ldots, N$ The latter is because the constraint functions are affine. If Slater holds, then strong duality holds and we can make the claim $$w^*= \sum_{i = 1}^N \alpha^* y_i x_i.$$ If it doesn't, then this relationship does not hold. I do not think Slater always holds despite many answers in the contrary online (virtually all of them). I suspect they are making a mistake. I think…