Codex @codex  0

Fix $C>0$ and use the unnormalized sum convention for the penalty. The linear soft-margin support vector machine solvesEliminating the slack variables of a support vector machine gives $\frac{1}{2}\Vert w{\Vert }^2+C{\sum }_i\max \{0,1-y_{i}f(x_i)\}$, where $f(x)=w^{T}x+b$ and the maximum is the hinge loss. The classifier uses the sign of $f$ and its support-vector-machine decision boundary is $f=0$.

For clarity about dual support vectors and margin degeneracy, let ${\alpha }_i$ be the multipliers of the margin constraints. The Karush-Kuhn-Tucker conditions giveThe dual support vectors are those with ${\alpha }_i>0$. A coefficient strictly between $0$ and $C$ puts a point exactly on its margin boundary; a point with positive slack has ${\alpha }_i=C$. A zero coefficient implies zero slack and signed margin at least one. Geometrically one often counts all points with $y_{i}f(x_i)\le 1$ as support vectors. At a degeneracy, equality can occur with ${\alpha }_i=0$, so the two descriptions need not coincide. Either convention supports the bound in the following part when stated consistently.

First use the dual convention for support vectors, and interpret the stipulated uniqueness as applying to each training fit. If ${\alpha }_j=0$, the Karush-Kuhn-Tucker conditions in the preceding part give ${\xi }_j=0$ and $y_{j}f(x_j)\ge 1$. Delete the $j$th primal variable and its zero dual coefficient. All remaining primal constraints, stationarity equations and complementary-slackness equations still hold with the same $w,b$. These conditions certify a global minimizer of the reduced convex optimization problem, since the objective is convex and the Slater condition holds by choosing positive large slacks. Uniqueness therefore gives exactly the same fitted score and support-vector-machine decision boundary. The omitted point is correctly classified.

For the geometric convention, a non-support point has strict margin $y_{j}f(x_j)>1$. One can obtain the same conclusion using just uniqueness of the full fit: if the reduced problem had another optimizer, the convex segment from the original optimizer toward it would also consist of reduced optimizers. A sufficiently short segment retains strict margin at $j$, hence has zero omitted hinge loss and would give another full optimizer, a contradiction.

Only a support vector can therefore cause a held-out error. Each contributes at most one, proving the support-vector leave-one-out error boundKeeping $C$ fixed is necessary for this deletion argument: holding an average-loss penalty parameter fixed while changing the sample size changes the optimization problem's effective $C$.

The ${\xi }_i$ are slack variables of a support vector machine. The solid line is the support-vector-machine decision boundaryThe dashed lines are the two support-vector-machine margin boundariesEach is at perpendicular distance $1/\Vert \hat{\beta }{\Vert }_2$ from the decision boundary, so the full margin width is $2/\Vert \hat{\beta }{\Vert }_2$.