Support Vector Machines: The Margin, the Dual, and the Kernel Trick

Intuition Beginner

Imagine two crowds standing on a field, one wearing red, one wearing blue, and your job is to paint a single straight line that keeps them apart. If the crowds are well separated, many lines work. Which one should you pick? The support vector machine picks the line that leaves the widest empty street between the two crowds. The street is centred on the line, and its width is the distance from the line to the nearest person on either side.

Why prefer the widest street? Because a wide buffer is forgiving. New people will arrive, and a line jammed right up against the existing crowd will misclassify a newcomer who stands slightly inside the gap. A line with a fat margin of safety tolerates that wobble. Maximizing the margin is choosing the most cautious boundary the data allow.

The people who end up touching the edge of the street do all the work. They are the support vectors. Move someone deep inside the red crowd and the line does not budge; move a support vector and the line shifts. The whole boundary is decided by a handful of borderline cases, not by the comfortable majority.

Real crowds overlap, so a perfectly empty street is often impossible. The soft-margin version lets a few people stand inside the street, or even on the wrong side, and charges a penalty for each one. A single dial trades street width against the total penalty: open the street wide and accept some intruders, or keep it narrow and clean. And by measuring closeness with a kernel instead of plain straight-line distance, the same idea bends the boundary into curves.

Visual Beginner

Object	What it is	What it controls
The line (hyperplane)	The decision boundary	Which side a new point lands on
The street (margin)	The empty band around the line	How much wobble the rule tolerates
Support vectors	The points touching the street edge	The entire position of the line
Slack	How far an intruder sits inside the street	The penalty paid for overlap
The dial $C$	Penalty per unit of slack	Wide-and-forgiving vs narrow-and-strict

The single picture to carry forward: a boundary plus a buffer zone, with the buffer made as wide as the data allow, pinned in place by the few points on its edge. Everything else about the support vector machine is making that picture precise and letting the buffer be measured with curved rather than straight rulers.

Worked example Beginner

Take four points on a line. Two red points sit at positions $-3$ and $-1$, labelled $-1$. Two blue points sit at $+1$ and $+3$, labelled $+1$. We want the threshold that best separates red from blue.

Any threshold between $-1$ and $+1$ separates them. The widest-street choice is the midpoint, $0$: the nearest red point is at $-1$ and the nearest blue point at $+1$, each a distance $1$ from the boundary, so the street runs from $-1$ to $+1$ and has half-width $1$.

Now read off the support vectors. The points at $-1$ and $+1$ touch the edge of the street; they are the support vectors. The points at $-3$ and $+3$ sit comfortably outside and play no role. Slide the point at $-3$ to $-5$ and the boundary stays at $0$. Slide the support vector at $-1$ to $-0.5$ and the street shrinks: the nearest red point is now $0.5$ away, so the midpoint between $-0.5$ and $+1$ moves to $+0.25$ and the half-width drops to $0.75$.

To put numbers on the rule, write the boundary as $wx+b=0$. Centring at $0$ means $b=0$. We scale $w$ so the support vectors satisfy $y(wx+b)=1$: at $x=1$, $y=+1$, we need $w\cdot 1=1$, so $w=1$. Check the red support vector: at $x=-1$, $y=-1$, the value is $(-1)(1\cdot (-1))=1$. Both edges sit at value $1$, as required.

What this tells us: the margin half-width equals $1/w=1$, so making $w$ small makes the street wide. The whole rule rests on the two border points, and the two interior points are spectators.

Check your understanding Beginner

Formal definition Intermediate+

Let the data be $(x_1,y_1),\dots ,(x_n,y_n)$ with $x_i\in {\mathbb{R}}^d$ and labels $y_i\in \{-1,+1\}$. A separating hyperplane is the set $\{x:⟨w,x⟩+b=0\}$ with normal $w\in {\mathbb{R}}^d$ and offset $b\in \mathbb{R}$; the classifier is $x\mapsto \mathrm{sign}(⟨w,x⟩+b)$. The functional margin of point $i$ is $y_i(⟨w,x_i⟩+b)$ and its geometric margin is that quantity divided by $\Vert w\Vert$, the signed Euclidean distance from $x_i$ to the hyperplane. The data are linearly separable if some $(w,b)$ gives every point a positive functional margin.

Definition (hard-margin SVM). When the data are separable, the maximum-margin hyperplane is the minimizer of the convex quadratic program

$$\underset{w,b}{\min }\frac{1}{2}\Vert w{\Vert }^2\text{subject to}{y}_i(⟨w,x_i⟩+b)\ge 1,i=1,\dots ,n.$$

The scale of $(w,b)$ is fixed by the canonical normalization ${\min }_i{y}_i(⟨w,x_i⟩+b)=1$, under which the geometric margin equals $1/\Vert w\Vert$; minimizing $\Vert w{\Vert }^2$ therefore maximizes the margin. A support vector is a point with $y_i(⟨w,x_i⟩+b)=1$, lying exactly on the margin boundary.

Definition (soft-margin SVM). For non-separable data, introduce slack variables ${\xi }_i\ge 0$ measuring margin violation and a penalty parameter $C>0$:

$$\underset{w,b,\xi }{\min }\frac{1}{2}\Vert w{\Vert }^2+C\sum _{i=1}^n{\xi }_i\text{subject to}{y}_i(⟨w,x_i⟩+b)\ge 1-{\xi }_i,{\xi }_i\ge 0.$$

At the optimum ${\xi }_i=[1-y_i(⟨w,x_i⟩+b){]}_{+}$, the hinge loss $[t{]}_{+}=\max (0,t)$ of the margin, so the soft-margin program is the regularized empirical risk

$$\underset{w,b}{\min }\sum _{i=1}^n[1-y_i(⟨w,x_i⟩+b){]}_{+}+\frac{1}{2C}\Vert w{\Vert }^2,$$

with $\lambda =1/(2C)$ playing the regularization role. As $C\to \infty$ the penalty on violations grows without bound and the soft-margin solution returns the hard-margin one whenever the data are separable.

The Lagrange dual (derived below) replaces the inputs by their inner products $⟨x_i,x_j⟩$, which is the opening for the kernel trick: substituting a positive-definite kernel $K(x_i,x_j)=⟨\Phi (x_i),\Phi (x_j)⟩$ for the dot product runs the entire machine in the feature space of $K$ without ever forming $\Phi$. Written as a function-fitting problem with $f(x)=⟨w,\Phi (x)⟩+b$, the soft-margin SVM is

$$\underset{f\in {\mathcal{H}}_K,b}{\min }\sum _{i=1}^n[1-y_{i}f(x_i){]}_{+}+\lambda \Vert f{\Vert }_{{\mathcal{H}}_K}^2,$$

the hinge-loss instance of regularized RKHS risk of 45.08.01, to which the representer theorem applies.

Counterexamples to common slips

• The margin is geometric, not functional. The functional margin $y_i(⟨w,x_i⟩+b)$ scales with $\Vert w\Vert$ and can be inflated by rescaling $(w,b)$; only the geometric margin $1/\Vert w\Vert$ is meaningful, which is why the canonical normalization is imposed.
• Not every point with ${\alpha }_i>0$ sits on the margin. In the soft-margin dual the multipliers obey $0\le {\alpha }_i\le C$; points strictly inside the margin or misclassified hit the upper bound ${\alpha }_i=C$ and lie off the margin boundary, while the bias-recovering "free" support vectors have $0<{\alpha }_i<C$ and sit exactly on it.
• Maximizing the margin is not minimizing training error. On non-separable data a tiny $C$ can prefer a wide margin with many violations to a narrow margin with none; the SVM minimizes regularized hinge risk, not the count of mistakes.
• The hinge loss is not the $0$-$1$ loss. It is a convex upper bound that is exactly $0$ once the margin exceeds $1$ and grows linearly below; this convexity is what makes the program solvable, and the gap to the $0$-$1$ loss is controlled by the calibration theory rather than being zero.

Key theorem with proof Intermediate+

Theorem (the SVM dual and the support-vector characterization). The soft-margin primal

$$\underset{w,b,\xi }{\min }\frac{1}{2}\Vert w{\Vert }^2+C\sum _i{\xi }_i\text{s.t.}{y}_i(⟨w,x_i⟩+b)\ge 1-{\xi }_i,{\xi }_i\ge 0$$

has Lagrange dual

$$\underset{\alpha }{\max }\sum _{i=1}^n{\alpha }_i-\frac{1}{2}\sum _{i,j}{\alpha }_i{\alpha }_j{y}_i{y}_j⟨x_i,x_j⟩\text{s.t.}0\le {\alpha }_i\le C,\sum _i{\alpha }_i{y}_i=0.$$

Strong duality holds, the primal optimum is $w={\sum }_i{\alpha }_i{y}_i{x}_i$, and the KKT complementary-slackness conditions give the trichotomy: ${\alpha }_i=0\Rightarrow y_{i}f(x_i)\ge 1$ (correctly outside the margin); $0<{\alpha }_i<C\Rightarrow y_{i}f(x_i)=1$ (on the margin); ${\alpha }_i=C\Rightarrow y_{i}f(x_i)\le 1$ (inside the margin or misclassified). The support vectors are exactly the points with ${\alpha }_i>0$. The derivation follows Cortes & Vapnik ^{[Cortes 1995]} and Schölkopf & Smola ^{[Schölkopf 2002]} Ch. 7.

Proof. Introduce multipliers ${\alpha }_i\ge 0$ for the margin constraints $1-{\xi }_i-y_i(⟨w,x_i⟩+b)\le 0$ and ${\mu }_i\ge 0$ for $-{\xi }_i\le 0$. The Lagrangian is

$$L=\frac{1}{2}\Vert w{\Vert }^2+C\sum _i{\xi }_i+\sum _i{\alpha }_i(1-{\xi }_i-y_i(⟨w,x_i⟩+b))-\sum _i{\mu }_i{\xi }_i.$$

The problem is convex with affine constraints, so Slater's condition holds and strong duality with KKT optimality follows from 44.02.01 and 44.02.02. Stationarity in the primal variables:

$${\nabla }_{w}L=w-\sum _i{\alpha }_i{y}_i{x}_i=0\Rightarrow w=\sum _i{\alpha }_i{y}_i{x}_i,\frac{\partial L}{\partial b}=-\sum _i{\alpha }_i{y}_i=0,$$ $$\frac{\partial L}{\partial {\xi }_i}=C-{\alpha }_i-{\mu }_i=0\Rightarrow {\mu }_i=C-{\alpha }_i.$$

Substituting $w={\sum }_i{\alpha }_i{y}_i{x}_i$ back into $L$ and using ${\sum }_i{\alpha }_i{y}_i=0$ to kill the $b$-term and ${\mu }_i=C-{\alpha }_i\ge 0$ to convert the $\xi$-terms, the $\xi$ contributions cancel ($C{\xi }_i-{\alpha }_i{\xi }_i-{\mu }_i{\xi }_i=0$), leaving the dual objective

$$g(\alpha )=\sum _i{\alpha }_i-\frac{1}{2}\sum _{i,j}{\alpha }_i{\alpha }_j{y}_i{y}_j⟨x_i,x_j⟩,$$

because $\frac{1}{2}\Vert w{\Vert }^2=\frac{1}{2}{\sum }_{i,j}{\alpha }_i{\alpha }_j{y}_i{y}_j⟨x_i,x_j⟩$ and the linear cross-term doubles it with the opposite sign. The constraint ${\mu }_i\ge 0$ becomes ${\alpha }_i\le C$, giving the box $0\le {\alpha }_i\le C$ together with ${\sum }_i{\alpha }_i{y}_i=0$.

For the trichotomy, complementary slackness 44.02.02 reads ${\alpha }_i(1-{\xi }_i-y_{i}f(x_i))=0$ and ${\mu }_i{\xi }_i=(C-{\alpha }_i){\xi }_i=0$, with $f(x)=⟨w,x⟩+b$. If ${\alpha }_i=0$ then ${\mu }_i=C>0$ forces ${\xi }_i=0$, and the margin constraint gives $y_{i}f(x_i)\ge 1$. If $0<{\alpha }_i<C$ then ${\mu }_i>0$ forces ${\xi }_i=0$, and ${\alpha }_i>0$ forces $y_{i}f(x_i)=1-{\xi }_i=1$: the point lies on the margin. If ${\alpha }_i=C$ then ${\mu }_i=0$ permits ${\xi }_i\ge 0$, and ${\alpha }_i>0$ forces $y_{i}f(x_i)=1-{\xi }_i\le 1$: inside the margin or misclassified. Points with ${\alpha }_i=0$ drop out of $w$, so the expansion $w={\sum }_{i:{\alpha }_i>0}{\alpha }_i{y}_i{x}_i$ runs only over support vectors. $\square$

Bridge. This dual is the foundational reason the kernel trick works: every input enters only through the inner product $⟨x_i,x_j⟩$, so replacing it by $K(x_i,x_j)$ nonlinearizes the classifier without touching the optimization, and this is exactly the 45.08.01 picture with the hinge loss in place of squared error. The result builds toward the kernel SVM and the support-vector regression of the Advanced results, and appears again in every margin-based generalization bound, where the sparse support set controls capacity. The dual is dual to the primal margin program in the precise sense of 44.02.01: the primal unknown is the feature-space normal $w$, the dual unknown is the data-space coefficient vector $\alpha$, and the stationarity identity $w={\sum }_i{\alpha }_i{y}_i{x}_i$ is the same data-space-versus-weight-space correspondence that the representer theorem of 45.08.01 guarantees in general. Putting these together, complementary slackness of 44.02.02 is the central insight that produces sparsity: the box constraint $0\le {\alpha }_i\le C$ and the slackness equations sort the data into spectators, margin vectors, and bound vectors, and this generalises the hard-margin case as the limit $C\to \infty$.

Exercises Intermediate+

Lean formalization Intermediate+

Mathlib does not host the constrained-optimization apparatus the SVM requires (lean_status: none), so no module is wired in. The intended shape of the primal program, the dual, and the support-vector characterization, once a KKT predicate and the RKHS API exist, would read roughly as follows.

-- Intended shape; not part of the current Babel Bible Lean build.
-- Requires: a formalized convex QP, a KKT theorem with complementary slackness,
-- and an inner-product / kernel API.
variable {d n : ℕ}
variable (x : Fin n → EuclideanSpace ℝ (Fin d)) (y : Fin n → ℝ)  -- y i ∈ {-1, +1}
variable (C : ℝ) (hC : 0 < C)

-- Soft-margin primal objective in (w, b, ξ).
noncomputable def svmPrimal (w : EuclideanSpace ℝ (Fin d)) (b : ℝ) (ξ : Fin n → ℝ) : ℝ :=
  (1 / 2) * ‖w‖ ^ 2 + C * ∑ i, ξ i

-- Dual objective in α over the box 0 ≤ αᵢ ≤ C with ∑ αᵢ yᵢ = 0.
noncomputable def svmDual (K : Fin n → Fin n → ℝ) (α : Fin n → ℝ) : ℝ :=
  (∑ i, α i) - (1 / 2) * ∑ i, ∑ j, α i * α j * y i * y j * K i j

-- Support-vector characterization: at the KKT optimum, αᵢ > 0 ↔ the margin
-- constraint is active (yᵢ f(xᵢ) ≤ 1), via complementary slackness.
theorem support_vector_iff
    (K : Fin n → Fin n → ℝ) (α : Fin n → ℝ) (b : ℝ)
    (hkkt : IsKKTOptimal C x y K α b) (i : Fin n) :
    0 < α i ↔ y i * (∑ j, α j * y j * K j i + b) ≤ 1 := by
  sorry

the Mathlib gap analysis records the missing pieces: a formalized convex quadratic program with a KKT theorem and complementary slackness (the same gap noted for the optimization spine's KKT unit 44.02.02), the Wolfe-dual derivation, and the surrogate-risk calibration theory behind hinge-loss consistency. The support-vector trichotomy rides on IsKKTOptimal and its slackness conditions once those objects exist.

Advanced results Master

The SVM is the hinge-loss member of the regularized-RKHS-risk family of 45.08.01. Writing $f(x)=⟨w,\Phi (x)⟩+b$ with $\Phi$ the feature map of $K$, the soft-margin program is ${\min }_{f,b}{\sum }_i[1-y_{i}f(x_i){]}_{+}+\lambda \Vert f{\Vert }_{{\mathcal{H}}_K}^2$ with $\lambda =1/(2C)$, and the representer theorem forces $f={\sum }_i{\beta }_i{K}_{x_i}$ with ${\beta }_i={\alpha }_i{y}_i$ ^{[Steinwart 2008]}. Squared error gives kernel ridge regression with dense coefficients; the hinge loss gives the SVM with sparse coefficients, the sparsity being the analytic signature of the loss's flat region $[1-m{]}_{+}=0$ for $m\ge 1$, which sends the complementary-slackness multiplier to zero for every comfortably-classified point. The two methods share the projection-onto-the-data-span engine and differ only in $L$, exactly the unification the Bridge of 45.08.01 advertises.

The hinge loss is a classification-calibrated (Fisher-consistent) surrogate, which is the precise statement that minimizing hinge risk drives the $0$-$1$ risk to its Bayes optimum ^{[Steinwart 2008]}. For a margin loss $\varphi$, define the conditional $\varphi$-risk $C_{\eta }(m)=\eta \varphi (m)+(1-\eta )\varphi (-m)$ at posterior $\eta =\mathbb{P}(y=+1\mid x)$; $\varphi$ is calibrated when, for every $\eta \ne 1/2$, the minimizer of $C_{\eta }$ has the sign of $2\eta -1$, the Bayes decision. The hinge $\varphi (m)=[1-m{]}_{+}$ satisfies this: its conditional minimizer is $\mathrm{sign}(2\eta -1)$ for $\eta \ne 1/2$, so the population SVM recovers the Bayes classifier, and the self-calibration inequality $R_{0\text{-}1}(f)-R_{0\text{-}1}^{\star }\le R_{\varphi }(f)-R_{\varphi }^{\star }$ bounds the excess $0$-$1$ risk by the excess hinge risk without a multiplicative loss. Unlike logistic loss, the hinge minimizer does not estimate $\eta$ itself, only its thresholded sign — the price the SVM pays for sparsity is the loss of calibrated probabilities.

Margin theory supplies the generalization guarantee that motivates margin maximization as structural risk minimization. Vapnik's gap-tolerant bound shows that separating hyperplanes of geometric margin $\Delta$ inside a ball of radius $R$ have VC dimension at most $\min (R^2/{\Delta }^2,d)+1$, independent of the (possibly infinite) feature dimension $d$ when $R^2/{\Delta }^2$ is the binding term ^{[Vapnik 1998]}. The Rademacher route is sharper and dimension-free: the empirical Rademacher complexity of the kernel ball $\{f\in {\mathcal{H}}_K:\Vert f\Vert \le B\}$ is ${\hat{\mathfrak{R}}}_n\le B\sqrt{\mathrm{tr}\mathbf{K}}/n=B\sqrt{{\sum }_{i}K(x_i,x_i)}/n$, and composing with the $1$-Lipschitz hinge loss via Talagrand's contraction lemma gives, with probability $1-\delta$, a bound of the form $R_{0\text{-}1}(f)\le {\hat{R}}_{\text{hinge}}(f)+2{\hat{\mathfrak{R}}}_n+3\sqrt{\log (2/\delta )/2n}$. The margin enters through $B\sim 1/\Delta$, so a large margin means small complexity means a tight bound — the generalization counterpart of the foundational regularization control developed in the high-dimensional and learning-theory units.

Support vector regression replaces classification by the $\epsilon$-insensitive loss $|y-f(x){|}_{\epsilon }=\max (0,|y-f(x)|-\epsilon )$, flat inside a tube of half-width $\epsilon$ and linear outside ^{[Schölkopf 2002]}. The primal $\min \frac{1}{2}\Vert w{\Vert }^2+C{\sum }_i({\xi }_i+{\xi }_i^{\ast })$ subject to $y_i-f(x_i)\le \epsilon +{\xi }_i$, $f(x_i)-y_i\le \epsilon +{\xi }_i^{\ast }$, ${\xi }_i,{\xi }_i^{\ast }\ge 0$ has the dual $\max -\frac{1}{2}{\sum }_{ij}({\alpha }_i-{\alpha }_i^{\ast })({\alpha }_j-{\alpha }_j^{\ast })K(x_i,x_j)-\epsilon {\sum }_i({\alpha }_i+{\alpha }_i^{\ast })+{\sum }_i{y}_i({\alpha }_i-{\alpha }_i^{\ast })$ over the box $0\le {\alpha }_i,{\alpha }_i^{\ast }\le C$ with ${\sum }_i({\alpha }_i-{\alpha }_i^{\ast })=0$, and $f(x)={\sum }_i({\alpha }_i-{\alpha }_i^{\ast })K(x_i,x)+b$. The $\epsilon$-tube is the regression analogue of the margin: points inside it are spectators (${\alpha }_i={\alpha }_i^{\ast }=0$), and only the tube-violating points become support vectors, so sparsity persists. Solving these box-constrained QPs at scale is the role of decomposition methods; sequential minimal optimization optimizes the smallest admissible working set of two multipliers at a time, each step solving a one-dimensional problem analytically along the line cut out by the equality constraint ${\sum }_i{\alpha }_i{y}_i=0$, with working sets chosen by maximal KKT violation ^{[Platt 1999]}, the optimization story continued in 44.02.02.

Synthesis. The foundational reason the support vector machine, the kernel trick, and convex duality cohere into one method is that the maximum-margin primal is a convex quadratic program whose Lagrangian dual of 44.02.01 expresses every input through inner products alone, so the kernel substitution $⟨x_i,x_j⟩\mapsto K(x_i,x_j)$ nonlinearizes the classifier while the optimization stays convex — this is exactly the 45.08.01 regularized-RKHS-risk picture with the hinge loss in place of squared error. The central insight is that complementary slackness of 44.02.02 sorts the data into the support-vector trichotomy and forces sparsity, which is dual to the dense kernel-ridge solution and generalises the hard-margin classifier as the $C\to \infty$ limit. Putting these together, the representer theorem of 45.08.01 guarantees the finite expansion $f={\sum }_i{\alpha }_i{y}_i{K}_{x_i}$, the dual produces its coefficients as box-constrained multipliers, and the KKT conditions identify which coefficients survive; the bridge is the kernel Gram matrix $\mathbf{K}$, whose positive-semidefiniteness makes the dual a concave maximization, whose entries are the only data the solver ever sees, and whose trace bounds the Rademacher complexity that, together with the margin, certifies generalization. This is exactly the structural-risk-minimization programme — wide margin as low capacity, sparse support set as compressed evidence, convex surrogate as tractable computation — assembled from the duality, KKT, and RKHS layers built in the prerequisite units.

Full proof set Master

The dual derivation, the support-vector trichotomy, the bias recovery, and the representer-theorem instance are established in the Formal definition, Key theorem, and Exercises. The remaining Master claims are recorded here.

Proposition 1 (hard-margin is the $C\to \infty$ limit of soft-margin on separable data). If the data are linearly separable, then for all $C$ large enough the soft-margin solution coincides with the hard-margin solution, with all ${\xi }_i=0$.

Proof. Separability gives a feasible $(w_0,b_0)$ with $y_i(⟨w_0,x_i⟩+b_0)\ge 1$ for all $i$, hence the hard-margin program has a finite optimal value $\frac{1}{2}\Vert w^{\star }{\Vert }^2=:P^{\star }$. For any $C$, the soft-margin optimum is bounded above by the hard-margin feasible point $(w^{\star },b^{\star },0)$ with value $P^{\star }$, so the soft optimum value is $\le P^{\star }$. Suppose the soft optimum had some ${\xi }_i>0$; its objective would be $\frac{1}{2}\Vert w{\Vert }^2+C{\sum }_i{\xi }_i\ge C{\xi }_i$, which exceeds $P^{\star }$ once $C>P^{\star }/{\xi }_{\min }$ for the smallest positive slack achievable — more carefully, the optimal total slack ${\sum }_i{\xi }_i$ is a non-increasing function of $C$ that must vanish for $C$ large, since otherwise the $C{\sum }_i{\xi }_i$ term would force the objective above the fixed bound $P^{\star }$. With all ${\xi }_i=0$ the soft program reduces to the hard program, so the minimizers coincide. $\square$

Proposition 2 (the SVM solution depends only on the kernel Gram matrix). The dual optimizer $\alpha$, the support set, and the decision function $f(\cdot )$ evaluated at any point depend on the training data only through the Gram matrix ${\mathbf{K}}_{ij}=K(x_i,x_j)$, the labels $y$, and the test-point kernel vector $k(x{)}_i=K(x_i,x)$.

Proof. The dual objective ${\sum }_i{\alpha }_i-\frac{1}{2}{\alpha }^{\top }(D\mathbf{K}D)\alpha$ with $D=\mathrm{diag}(y)$ and its feasible set $\{0\le \alpha \le C,y^{\top }\alpha =0\}$ reference the inputs only through $\mathbf{K}$ and $y$; hence the optimizer $\alpha$ and the support set $\{i:{\alpha }_i>0\}$ do too. The decision function $f(x)={\sum }_i{\alpha }_i{y}_{i}K(x_i,x)+b={\alpha }^{\top }Dk(x)+b$ with $b=y_k-{\alpha }^{\top }D{\mathbf{K}}_{\cdot k}$ for a free support vector $k$ references inputs only through $\mathbf{K}$ and $k(x)$. So no explicit feature representation is ever needed; the feature map $\Phi$ may be infinite-dimensional. $\square$

Proposition 3 (the SVM is a regularized empirical-risk minimizer with the hinge loss). The soft-margin primal is equivalent to ${\min }_{w,b}{\sum }_i[1-y_i(⟨w,x_i⟩+b){]}_{+}+\frac{1}{2C}\Vert w{\Vert }^2$, and any minimizer of the latter yields, with ${\xi }_i=[1-y_i(⟨w,x_i⟩+b){]}_{+}$, a minimizer of the former.

Proof. Fix $(w,b)$. The soft-margin program minimizes ${\sum }_i{\xi }_i$ over ${\xi }_i\ge 0$, ${\xi }_i\ge 1-y_i(⟨w,x_i⟩+b)$ for each $i$ separately; the minimum of ${\xi }_i$ over $\{{\xi }_i\ge 0,{\xi }_i\ge t_i\}$ is $\max (0,t_i)=[t_i{]}_{+}$ with $t_i=1-y_i(⟨w,x_i⟩+b)$. Substituting the optimal slacks turns $\frac{1}{2}\Vert w{\Vert }^2+C{\sum }_i{\xi }_i$ into $\frac{1}{2}\Vert w{\Vert }^2+C{\sum }_i[1-y_i(⟨w,x_i⟩+b){]}_{+}$; dividing by $C$ and writing $\lambda =1/(2C)$ gives the hinge-plus-ridge form up to the positive scale $C$, which does not move the argmin. Conversely a minimizer of the hinge form with ${\xi }_i$ set to the hinge values is feasible for the soft-margin program and attains the same objective, hence optimal. $\square$

Proposition 4 (hinge-loss classification calibration). Let $\eta =\mathbb{P}(y=+1\mid x)$. The conditional hinge risk $C_{\eta }(m)=\eta [1-m{]}_{+}+(1-\eta )[1+m{]}_{+}$ is minimized over $m\in \mathbb{R}$ at $m^{\star }=\mathrm{sign}(2\eta -1)$ for $\eta \ne 1/2$. Consequently the population hinge minimizer has the Bayes sign, and the hinge loss is classification-calibrated.

Proof. $C_{\eta }$ is convex and piecewise linear in $m$ with breakpoints at $m=\pm 1$. On $m\le -1$, $C_{\eta }=\eta (1-m)$ with slope $-\eta \le 0$. On $-1\le m\le 1$, $C_{\eta }=\eta (1-m)+(1-\eta )(1+m)=1+(1-2\eta )m$ with slope $1-2\eta$. On $m\ge 1$, $C_{\eta }=(1-\eta )(1+m)$ with slope $1-\eta \ge 0$. For $\eta >1/2$ the middle slope $1-2\eta <0$, so $C_{\eta }$ decreases up to $m=1$ then increases, with minimum at $m^{\star }=1=\mathrm{sign}(2\eta -1)$; for $\eta <1/2$ the middle slope is positive, the minimum is at $m^{\star }=-1=\mathrm{sign}(2\eta -1)$. In both cases $\mathrm{sign}(m^{\star })=\mathrm{sign}(2\eta -1)$, the Bayes decision; calibration follows because the minimizing sign matches the Bayes rule whenever $\eta \ne 1/2$. $\square$

Proposition 5 (Rademacher bound for the kernel ball). For the class ${\mathcal{F}}_B=\{x\mapsto ⟨w,\Phi (x)⟩:\Vert w\Vert \le B\}$ with kernel $K$, the empirical Rademacher complexity satisfies ${\hat{\mathfrak{R}}}_n({\mathcal{F}}_B)\le \frac{B}{n}\sqrt{{\sum }_{i=1}^{n}K(x_i,x_i)}$.

Proof. With Rademacher signs ${\sigma }_i$ independent and uniform on $\{\pm 1\}$,

$${\hat{\mathfrak{R}}}_n({\mathcal{F}}_B)=\frac{1}{n}{\mathbb{E}}_{\sigma }\underset{\Vert w\Vert \le B}{\sup }⟨w,\sum _i{\sigma }_i\Phi (x_i)⟩=\frac{B}{n}{\mathbb{E}}_{\sigma }\Vert \sum _i{\sigma }_i\Phi (x_i)\Vert ,$$

the supremum attained by aligning $w$ with ${\sum }_i{\sigma }_i\Phi (x_i)$. By Jensen, ${\mathbb{E}}_{\sigma }\Vert {\sum }_i{\sigma }_i\Phi (x_i)\Vert \le ({\mathbb{E}}_{\sigma }\Vert {\sum }_i{\sigma }_i\Phi (x_i){\Vert }^2{)}^{1/2}$, and ${\mathbb{E}}_{\sigma }\Vert {\sum }_i{\sigma }_i\Phi (x_i){\Vert }^2={\sum }_{i,j}\mathbb{E}[{\sigma }_i{\sigma }_j]⟨\Phi (x_i),\Phi (x_j)⟩={\sum }_i\Vert \Phi (x_i){\Vert }^2={\sum }_{i}K(x_i,x_i)$ using $\mathbb{E}[{\sigma }_i{\sigma }_j]={\delta }_{ij}$. Hence ${\hat{\mathfrak{R}}}_n({\mathcal{F}}_B)\le \frac{B}{n}\sqrt{{\sum }_{i}K(x_i,x_i)}$. Composing with the $1$-Lipschitz hinge loss via Talagrand's contraction inequality leaves this complexity unchanged up to the standard constant, yielding the margin-based generalization bound. $\square$

Connections Master

Kernels, RKHS, and the representer theorem 45.08.01 are the direct parent: the SVM is the hinge-loss instance of regularized RKHS risk, and the representer theorem proved there is exactly what reduces the infinite-dimensional fit to the finite support-vector expansion $f={\sum }_i{\alpha }_i{y}_i{K}_{x_i}$. Kernel ridge regression is the squared-error sibling with dense coefficients; the SVM differs only in the loss $L$, and the contrast between dense and sparse solutions is the hinge loss's flat-region signature.

Lagrangian duality 44.02.01 supplies the engine: the Wolfe dual of the margin program is its Lagrange dual, strong duality (via Slater on the convex QP) is what licenses passing from primal to dual, and the dual unknown $\alpha$ is the data-space coefficient vector conjugate to the feature-space normal $w$. The push from primal to dual is precisely what exposes the inner products that the kernel trick then replaces.

The Karush-Kuhn-Tucker conditions 44.02.02 characterize the support vectors: complementary slackness on the margin constraints produces the trichotomy ${\alpha }_i=0$, $0<{\alpha }_i<C$, ${\alpha }_i=C$, sorting the data into spectators, free margin vectors, and bound vectors, and the box constraints $0\le {\alpha }_i\le C$ are the slackness conditions on the slack-variable multipliers. The same KKT-violation criterion drives the SMO working-set selection.

Empirical process theory and margin-based generalization bounds (forward, 45.07.05) certify why margin maximization controls overfitting: the Rademacher complexity of the kernel ball scales with the RKHS-norm budget $B\sim 1/\Delta$, so a large geometric margin means small complexity and a tight excess-risk bound; the hinge loss's classification calibration links that excess hinge risk back to the excess $0$-$1$ risk, completing the structural-risk-minimization argument.

Convex optimization solvers (forward) implement the SVM at scale: the dual is a box-constrained convex QP with a single linear equality, and decomposition methods such as SMO and its working-set generalizations exploit the KKT structure of 44.02.02, the optimization continuation of this unit's duality content.

Historical & philosophical context Master

The maximum-margin idea entered learning theory through Vladimir Vapnik and Alexey Chervonenkis's work on the optimal separating hyperplane in the 1960s and 1970s, where margin maximization was justified by the capacity-control programme that became structural risk minimization. The modern support vector machine took shape at AT&T Bell Labs: Bernhard Boser, Isabelle Guyon, and Vapnik introduced the kernel trick for the optimal-margin classifier in 1992, and Corinna Cortes and Vapnik published the soft-margin support-vector network for non-separable data in 1995 in Machine Learning ^{[Cortes 1995]}, adding the slack variables and the box-constrained dual that made the method practical on real, overlapping data. Vapnik's 1998 Statistical Learning Theory ^{[Vapnik 1998]} set the margin-based generalization bounds and the gap-tolerant VC-dimension argument that motivate margin maximization on capacity grounds.

The kernel viewpoint was consolidated by Bernhard Schölkopf, Alexander Smola, and collaborators, whose 2002 Learning with Kernels ^{[Schölkopf 2002]} unified the SVM, support vector regression, and the broader kernel-methods family under the RKHS regularization framework, and Hastie, Tibshirani, and Friedman placed the SVM as a penalized hinge-loss method alongside the rest of statistical learning. The computational bottleneck of the dense dual QP was broken by John Platt's 1999 sequential minimal optimization ^{[Platt 1999]}, which reduced training to a sequence of analytically solvable two-variable subproblems. The consistency theory — that the hinge loss is a classification-calibrated surrogate, so the SVM is Bayes-consistent — was settled by Ingo Steinwart and Andreas Christmann and collaborators in the 2000s ^{[Steinwart 2008]}, placing the convex-surrogate heuristic on a rigorous statistical footing.

Bibliography Master

@article{cortes1995support,
  author  = {Cortes, Corinna and Vapnik, Vladimir},
  title   = {Support-Vector Networks},
  journal = {Machine Learning},
  volume  = {20},
  number  = {3},
  pages   = {273--297},
  year    = {1995}
}

@inproceedings{boser1992training,
  author    = {Boser, Bernhard E. and Guyon, Isabelle M. and Vapnik, Vladimir N.},
  title     = {A Training Algorithm for Optimal Margin Classifiers},
  booktitle = {Proceedings of the Fifth Annual Workshop on Computational Learning Theory (COLT)},
  pages     = {144--152},
  year      = {1992}
}

@book{vapnik1998statistical,
  author    = {Vapnik, Vladimir N.},
  title     = {Statistical Learning Theory},
  publisher = {Wiley},
  year      = {1998}
}

@book{scholkopf2002learning,
  author    = {Sch\"olkopf, Bernhard and Smola, Alexander J.},
  title     = {Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond},
  publisher = {MIT Press},
  year      = {2002}
}

@incollection{platt1999fast,
  author    = {Platt, John C.},
  title     = {Fast Training of Support Vector Machines using Sequential Minimal Optimization},
  booktitle = {Advances in Kernel Methods --- Support Vector Learning},
  editor    = {Sch\"olkopf, Bernhard and Burges, Christopher J. C. and Smola, Alexander J.},
  publisher = {MIT Press},
  pages     = {185--208},
  year      = {1999}
}

@book{steinwart2008support,
  author    = {Steinwart, Ingo and Christmann, Andreas},
  title     = {Support Vector Machines},
  series    = {Information Science and Statistics},
  publisher = {Springer},
  year      = {2008}
}

@book{hastie2009elements,
  author    = {Hastie, Trevor and Tibshirani, Robert and Friedman, Jerome},
  title     = {The Elements of Statistical Learning: Data Mining, Inference, and Prediction},
  edition   = {2},
  publisher = {Springer},
  year      = {2009},
  note      = {Chapter 12 (support vector machines and flexible discriminants)}
}