The primal view trains SVMs by gradient descent, but it hides two treasures: why support vectors appear, and how the kernel trick becomes possible. Both emerge when we rewrite the SVM through Lagrangian duality. This is the most mathematical chapter of the book; take it slowly, because the dual form is the gateway to everything nonlinear.

Constrained optimization and the Lagrangian

For the hard-margin problem \(\min \tfrac12\|\vw\|^2\) s.t. \(y_i(\vw^\top\vxi+b)\ge1\), introduce a Lagrange multiplier \(\alpha_i\ge0\) for each constraint and form the Lagrangian \[\mathcal{L}(\vw,b,\alpha) = \tfrac12\|\vw\|^2 - \sum_{i=1}^n \alpha_i\big[y_i(\vw^\top\vxi+b)-1\big].\]

A Lagrange multiplier is the “price” of a constraint. Each \(\alpha_i\) measures how hard constraint \(i\) is pushing on the solution. The art of duality: minimize \(\mathcal{L}\) over the primal variables \((\vw,b)\) and maximize over the prices \(\alpha\). Under convexity (which the SVM enjoys), this min–max can be swapped (strong duality), and solving the resulting “dual” problem in \(\alpha\) recovers the exact primal solution.

Deriving the dual

Setting \(\partial\mathcal{L}/\partial\vw=0\) and \(\partial\mathcal{L}/\partial b=0\) gives the stationarity conditions \[\vw = \sum_{i=1}^n \alpha_i y_i \vxi, \qquad \sum_{i=1}^n \alpha_i y_i = 0.\] The first is profound: the optimal weight vector is a linear combination of the training points, weighted by \(\alpha_i y_i\). Substituting back eliminates \(\vw,b\) and yields the dual problem: \[\max_{\alpha\ge0}\ \sum_{i} \alpha_i - \tfrac12\sum_{i,j}\alpha_i\alpha_j\,y_i y_j\,\vxi^\top\vx_j \quad\text{s.t.}\quad \sum_i \alpha_i y_i = 0,\ \ (0\le\alpha_i\le C).\] The box constraint \(\alpha_i\le C\) appears in the soft-margin case.

Stare at the dual objective: the data enters only through inner products \(\vxi^\top\vx_j\). The features themselves have vanished — we never need the coordinates of \(\vxi\), only their pairwise similarities. This is the doorway to the kernel trick (Chapter [ch:kerneltrick]): replace \(\vxi^\top\vx_j\) with any valid kernel \(k(\vxi,\vx_j)\) and you are solving an SVM in a high-dimensional feature space, at no extra cost. Duality is not just elegant; it is what makes nonlinear SVMs computable.

KKT conditions and the birth of support vectors

At the optimum, the Karush–Kuhn–Tucker (KKT) conditions hold; the decisive one is complementary slackness: \[\alpha_i\big[y_i(\vw^\top\vxi+b)-1+\xi_i\big] = 0.\] This forces an either/or for every point:

  • \(\alpha_i = 0\): the point is strictly beyond the margin — not a support vector, no influence.

  • \(0<\alpha_i<C\): the point sits exactly on the margin — a free support vector.

  • \(\alpha_i = C\): the point violates its margin (\(\xi_i>0\)) — a bounded support vector.

So the support vectors are exactly the points with \(\alpha_i>0\), and the prediction \(\hat y=\sgn(\sum_i \alpha_i y_i\,\vxi^\top\vx + b)\) sums over them alone.

Why the dual matters

Three payoffs. (1) Kernels: the dual depends only on inner products, enabling nonlinear SVMs. (2) Sparsity: most \(\alpha_i=0\), so prediction is cheap — only support vectors are stored. (3) Insight: the multipliers \(\alpha_i\) rank how “critical” each example is. The cost: the dual is an \(n\times n\) quadratic program (the Gram matrix of all pairwise kernels), so it scales poorly with the number of samples — which is why huge linear problems are often solved in the primal instead (Chapter [ch:optimization]).

Primal or dual? Use the dual when you need kernels or when \(p\) (features) \(\gg n\) (samples). Use the primal (subgradient/Pegasos, LIBLINEAR) for linear SVMs when \(n\) is large, since the dual’s \(n\times n\) Gram matrix becomes intractable past \(\sim 10^5\) points. A common mistake is reaching for a kernel SVM on a million rows — it will crawl; either subsample, use a linear SVM, or use an explicit feature approximation (random Fourier features, Chapter [ch:kernels]).

Lagrangian duality and KKT are not SVM-specific — they are the backbone of constrained optimization across AI: they underlie support-vector sparsity, the dual formulations used in reinforcement learning (constrained policy optimization), optimal transport, and adversarial robustness (min–max games). The interpretation of multipliers as sample importance recurs in modern theory: in the SVM–neural-network correspondence, the Lagrange multipliers of the equivalent SVM measure which training points most shape an infinitely wide network (Chapter [ch:svmmlai]). Mastering duality here pays dividends far beyond SVMs.

import numpy as np
from sklearn.svm import SVC
from sklearn.datasets import make_blobs
X, y = make_blobs(n_samples=40, centers=2, random_state=6)
clf = SVC(kernel="linear", C=1.0).fit(X, y)
print("dual coefs (alpha*y) for SVs:", clf.dual_coef_.round(2))
print("# support vectors:", len(clf.support_), "of", len(X))
# reconstruct w from the dual: w = sum_i alpha_i y_i x_i  (over support vectors)
w = (clf.dual_coef_ @ clf.support_vectors_).ravel()
print("w from dual:", w.round(2), " vs clf.coef_:", clf.coef_.ravel().round(2))

Chapter summary

  • The Lagrangian attaches multipliers \(\alpha_i\ge0\) to the margin constraints; convexity gives strong duality.

  • Stationarity yields \(\vw=\sum_i\alpha_i y_i\vxi\) and \(\sum_i\alpha_i y_i=0\) — the weight vector is a combination of training points.

  • The dual depends on data only through inner products \(\vxi^\top\vx_j\) — the doorway to the kernel trick.

  • KKT complementary slackness makes \(\alpha_i>0\) only for support vectors; free (\(0<\alpha<C\)) vs bounded (\(\alpha=C\)).

  • Dual for kernels / \(p\gg n\); primal for large \(n\) (the dual’s \(n\times n\) Gram matrix limits scale).