Support Vector Machines

Why This Matters

Support vector machines were the dominant classification method from the mid-1990s through the early 2010s, and for good reason: they have a clean mathematical formulation rooted in convex optimization, come with strong generalization guarantees via margin theory, and extend to nonlinear classification through the kernel trick. Even in the deep learning era, SVMs remain the clearest example of how optimization geometry connects to statistical generalization.

Mental Model

You have two classes of points in $\mathbb{R}^d$. You want to find a separating hyperplane that is as far as possible from both classes. The "margin" is the width of the gap between the classes. Maximizing the margin is equivalent to minimizing $\|w\|$ subject to all points being correctly classified. This is a convex quadratic program, and its dual reveals that the solution depends only on dot products between data points — opening the door to kernels.

Hard Margin SVM

Definition

Separating Hyperplane$w^{T}x+b=0$

A hyperplane in $\mathbb{R}^d$ defined by weight vector $w \in \mathbb{R}^d$ and bias $b \in \mathbb{R}$. A point $x_i$ with label $y_i \in \{-1, +1\}$ is correctly classified if and only if $y_i(w^T x_i + b) > 0$.

Definition

Functional Margin$y_i(w^T{x}_i+b)$

The functional margin of a point $(x_i, y_i)$ is $y_i(w^T x_i + b)$. Correct classification means positive functional margin. The geometric margin is the functional margin divided by $\|w\|$, giving the actual Euclidean distance from the point to the hyperplane.

Definition

Hard Margin SVM

For linearly separable data $\{(x_i, y_i)\}_{i=1}^n$, the hard margin SVM solves:

$\min_{w, b} \frac{1}{2}\|w\|^2 \quad \text{s.t.} \quad y_i(w^T x_i + b) \geq 1 \;\; \forall i$

The margin (distance between the two class boundaries) is $\frac{2}{\|w\|}$. Maximizing this margin is equivalent to minimizing $\|w\|^2$.

The Dual Formulation

Theorem

Hard Margin SVM Dual Problem

Statement

The Lagrangian dual of the hard margin SVM is:

$\max_{\alpha} \sum_{i=1}^n \alpha_i - \frac{1}{2}\sum_{i,j} \alpha_i \alpha_j y_i y_j x_i^T x_j$

subject to $\alpha_i \geq 0$ for all $i$ and $\sum_i \alpha_i y_i = 0$.

At optimality, $w^* = \sum_i \alpha_i^* y_i x_i$, and $\alpha_i^* > 0$ only for support vectors: points lying exactly on the margin boundary.

Intuition

The dual says: find weights $\alpha_i$ on training points such that the resulting classifier $w = \sum \alpha_i y_i x_i$ maximizes margin. Most $\alpha_i$ are zero. Only the points closest to the decision boundary (the support vectors) have nonzero weight, so the classifier depends on only a few critical training examples.

Proof Sketch

Form the Lagrangian $L(w, b, \alpha) = \frac{1}{2}\|w\|^2 - \sum_i \alpha_i[y_i(w^T x_i + b) - 1]$. Set $\nabla_w L = 0$ to get $w = \sum_i \alpha_i y_i x_i$. Set $\partial L / \partial b = 0$ to get $\sum_i \alpha_i y_i = 0$. Substitute back into $L$ to eliminate $w$ and $b$, yielding the dual. Strong duality holds because the primal is convex and Slater's condition is satisfied (any strictly feasible point suffices).

Why It Matters

The dual formulation is essential for two reasons: (1) the data appears only through dot products $x_i^T x_j$, enabling the kernel trick, and (2) the dual variables directly identify the support vectors.

Failure Mode

The hard margin SVM has no solution if the data is not linearly separable. Even a single mislabeled point or outlier makes the primal infeasible. This motivates the soft margin formulation.

report a correction →

Lagrange Multipliers and KKT — Quick Recap

SVM is the canonical setting for seeing Lagrange multipliers and the KKT conditions in action. A short self-contained refresher, since these concepts do not have standalone topic pages yet.

A constrained convex problem $\min_x f(x) \text{ s.t. } g_i(x) \le 0$ has Lagrangian $L(x, \alpha) = f(x) + \sum_i \alpha_i g_i(x)$ with $\alpha_i \ge 0$. The dual function $g(\alpha) = \min_x L(x, \alpha)$ is concave; its supremum equals $f^*$ at the primal optimum under regularity (Slater's condition: a strictly feasible point exists). The four KKT conditions characterize that joint optimum:

1. Stationarity (gradient of Lagrangian vanishes): $\nabla_x f(x^*) + \sum_i \alpha_i^* \nabla g_i(x^*) = 0$
2. Primal feasibility: $g_i(x^*) \le 0$ for every $i$
3. Dual feasibility: $\alpha_i^* \ge 0$ for every $i$
4. Complementary slackness: $\alpha_i^* g_i(x^*) = 0$ for every $i$ — each constraint is either tight ($g_i(x^*) = 0$) or its multiplier is zero ($\alpha_i^* = 0$).

For the hard-margin SVM with constraints $g_i(w, b) = 1 - y_i(w^\top x_i + b) \le 0$, the KKT conditions specialize to:

1. Stationarity: $w^* = \sum_i \alpha_i^* y_i x_i$ (and $\sum_i \alpha_i^* y_i = 0$ from $\partial L / \partial b$).
2. Primal feasibility: $y_i(w^{*\top} x_i + b^*) \ge 1$ for every training point.
3. Dual feasibility: $\alpha_i^* \ge 0$.
4. Complementary slackness: $\alpha_i^*[y_i(w^{*\top} x_i + b^*) - 1] = 0$ — either $\alpha_i^* = 0$ (the point is not a support vector) or $y_i(w^{*\top} x_i + b^*) = 1$ (the point sits exactly on the margin gutter). No middle ground.

The dual-variable interpretation is what makes SVM both interpretable and sparse: only the support vectors contribute to $w^*$. The complementary-slackness identity is the operational rule that picks them out.

Soft Margin SVM and Hinge Loss

Definition

Soft Margin SVM${\xi }_i$

When data is not linearly separable, introduce slack variables $\xi_i \geq 0$:

$\min_{w, b, \xi} \frac{1}{2}\|w\|^2 + C\sum_{i=1}^n \xi_i \quad \text{s.t.} \quad y_i(w^T x_i + b) \geq 1 - \xi_i, \;\; \xi_i \geq 0$

The parameter $C > 0$ trades off margin width against margin violations. Large $C$ penalizes violations heavily (close to hard margin); small $C$ allows more violations for a wider margin.

Definition

Hinge Loss$\max (0,1-y\cdot f(x))$

The soft margin SVM is equivalent to minimizing the hinge loss:

$\min_w \frac{\lambda}{2}\|w\|^2 + \frac{1}{n}\sum_{i=1}^n \max(0, 1 - y_i(w^T x_i + b))$

where $\lambda = 1/(nC)$. The hinge loss is convex, non-differentiable at $y \cdot f(x) = 1$, and zero for correctly classified points with margin $\geq 1$. This is a regularized ERM problem with hinge loss.

The Kernel Trick

Since the dual depends on data only through dot products $x_i^T x_j$, we can replace these with a kernel function $k(x_i, x_j) = \phi(x_i)^T \phi(x_j)$ where $\phi$ maps to a (potentially infinite-dimensional) feature space. The classifier becomes:

$f(x) = \sum_{i=1}^n \alpha_i y_i k(x_i, x) + b$

We never compute $\phi(x)$ explicitly. We only evaluate the kernel. Four canonical kernels cover the bulk of practice:

The RBF kernel maps to an infinite-dimensional feature space yet computes in $O(d)$ per pair, which is what made the kernel trick a practical revolution. The kernels and RKHS page gives the full Mercer / reproducing-kernel theory underneath.

Sensitivity to $C$ and $\sigma$

SVM performance is famously parameter-sensitive. Two knobs dominate, and miscalibrating either can flip the model from underfit to overfit:

• $C$ (soft-margin penalty). Large $C$ heavily penalizes margin violations; the model approaches the hard-margin SVM, narrowing the margin and overfitting outliers. Small $C$ tolerates violations, widening the margin and behaving like a heavily regularized classifier (potentially underfitting). The mapping $\lambda = 1 / (n C)$ ties $C$ to the regularization strength of the equivalent hinge-loss-plus-$\ell_2$ ERM.
• $\sigma$ (RBF bandwidth). Large $\sigma$ makes $k(x, z)$ vary slowly with distance, producing smooth, low-capacity decision functions (underfit). Small $\sigma$ makes $k(x, z)$ near-zero for any pair of distinct points, producing a near-nearest-neighbor classifier with high capacity (overfit; the algorithmic stability bound becomes loose).

The standard discipline is grid search over $\log C$ and $\log \sigma$ with cross-validation, evaluated on a hold-out set. The classical sweet spot for RBF SVMs on a normalized dataset is $C \in [10^{-1}, 10^{2}]$ and $\sigma \approx \text{median pairwise distance}$ ("median heuristic"). When the median heuristic disagrees sharply with the cross-validated optimum, the data has multi-scale structure that single-bandwidth RBF cannot capture; that is when polynomial or composite kernels earn their place.

Bousquet and Elisseeff (2002, Theorem 22) gave SVM an explicit stability bound $\beta = L^2 / (2\mu n)$, where $\mu$ is the strong-convexity constant of the regularizer (here $2/C$) and $L$ is the Lipschitz constant of the loss. This is one of the cleanest examples of a stability-based generalization bound in the canonical-algorithm setting, and the rate $1/(\mu n)$ scales linearly with $C$.

Theorem

Representer Theorem for SVMs

Statement

For any regularized risk minimization problem of the form $\min_{f \in \mathcal{H}_k} \frac{\lambda}{2}\|f\|_{\mathcal{H}_k}^2 + \frac{1}{n}\sum_i \ell(y_i, f(x_i))$, the minimizer has the representation $f^*(x) = \sum_{i=1}^n \alpha_i k(x_i, x)$.

Intuition

You never need to search over the full (infinite-dimensional) RKHS. The optimal function is always a finite linear combination of kernel evaluations at the training points. This is why the kernel trick is computationally feasible.

Proof Sketch

Decompose $f = f_\parallel + f_\perp$ where $f_\parallel$ lies in $\text{span}\{k(x_i, \cdot)\}$ and $f_\perp$ is orthogonal. Then $f(x_i) = f_\parallel(x_i)$ for all training points (by reproducing property), but $\|f\|^2 = \|f_\parallel\|^2 + \|f_\perp\|^2 \geq \|f_\parallel\|^2$. So $f_\perp$ only increases the regularizer without affecting the loss.

Why It Matters

The representer theorem reduces an infinite-dimensional optimization to a finite-dimensional one (finding $n$ coefficients $\alpha_i$), making kernel methods computationally tractable.

Failure Mode

The kernel matrix $K_{ij} = k(x_i, x_j)$ is $n \times n$. For large $n$, storing and inverting this matrix becomes prohibitive ($O(n^2)$ memory, $O(n^3)$ solve time). This is why SVMs do not scale as well as SGD-based methods to very large datasets.

report a correction →

Connection to Regularization

The soft margin SVM is equivalent to regularized ERM with hinge loss:

$\min_w \frac{\lambda}{2}\|w\|^2 + \frac{1}{n}\sum_{i=1}^n \ell_{\text{hinge}}(y_i, w^T x_i)$

This is the same framework as ridge regression (squared loss + L2 regularization) or regularized logistic regression (logistic loss + L2). The only difference is the loss function. The hinge loss is special because it creates sparsity in the dual: most $\alpha_i = 0$, giving the "support vector" property.

Canonical Examples

Example

Hard margin in 2D

Consider two classes: $\{(1,1), (2,2)\}$ with label $+1$ and $\{(-1,-1), (-2,-2)\}$ with label $-1$. The optimal separating hyperplane passes through the origin with $w \propto (1,1)$. The margin is $\frac{2}{\|w\|}$ and the support vectors are $(1,1)$ and $(-1,-1)$, the closest points to the boundary from each class.

Common Confusions

Watch Out

SVMs do not maximize accuracy. THEY maximize margin

An SVM does not directly maximize classification accuracy on the training set. Many hyperplanes may achieve 100% training accuracy on separable data. The SVM picks the one with the largest margin. The theoretical justification is that large margin implies small generalization error (via VC dimension bounds on the margin classifier class).

Watch Out

The kernel trick is not specific to SVMs

Any algorithm whose computation depends only on dot products between data points can be kernelized. This includes kernel PCA, kernel ridge regression, and kernel k-means. SVMs popularized the kernel trick, but it is a general principle.

Why SVMs Were Dominant Pre-Deep-Learning

From roughly 1995 to 2012, SVMs were the go-to method for classification:

• Convex optimization: a single global optimum, no local minima
• Strong theory: margin-based generalization bounds
• Kernels: nonlinear classification without manual feature engineering
• Sparsity: the solution depends on few support vectors

Deep learning overtook SVMs because neural networks scale better to massive datasets (SGD is $O(n)$ per epoch vs $O(n^2)$-$O(n^3)$ for kernel SVMs) and learn hierarchical features automatically.

Summary

• Hard margin SVM: minimize $\|w\|^2$ subject to $y_i(w^T x_i + b) \geq 1$
• Margin = $2/\|w\|$; maximizing margin = minimizing $\|w\|$
• Dual depends on data only through dot products $\to$ kernel trick
• Support vectors: points with $\alpha_i > 0$, lying on the margin
• Soft margin: slack variables $\xi_i$, parameter $C$ controls tradeoff
• Hinge loss $\max(0, 1 - yf(x))$: convex surrogate for 0-1 loss

Exercises

ExerciseCore

Problem

Derive the dual of the hard margin SVM. Start from the primal $\min_{w,b} \frac{1}{2}\|w\|^2$ subject to $y_i(w^T x_i + b) \geq 1$, introduce Lagrange multipliers $\alpha_i \geq 0$, and eliminate $w$ and $b$.

Hint

Reveal Solution

ExerciseAdvanced

Problem

Show that for the soft margin SVM, the dual variables satisfy $0 \leq \alpha_i \leq C$. What does $\alpha_i = C$ mean geometrically?

Hint

Reveal Solution

Related Comparisons

• SVM vs. Logistic Regression

References

Canonical:

• Vapnik, The Nature of Statistical Learning Theory (1995), Chapters 5 and 10
• Cristianini & Shawe-Taylor, An Introduction to Support Vector Machines (2000)
• Cortes & Vapnik, "Support-Vector Networks" (Machine Learning, 1995)
• Boser, Guyon, Vapnik, "A Training Algorithm for Optimal Margin Classifiers" (COLT, 1992)
• Schoelkopf & Smola, Learning with Kernels (2002), Chapters 2 and 7

Current:

• Shalev-Shwartz & Ben-David, Understanding Machine Learning (2014), Chapters 15-16
• Boyd & Vandenberghe, Convex Optimization (2004), Chapter 5
• Hastie, Tibshirani, Friedman, The Elements of Statistical Learning (2009), Chapter 12
• Steinwart & Christmann, Support Vector Machines (2008), Chapters 1 and 2

Next Topics

The natural next step from SVMs:

• Kernels and RKHS: the full theory of reproducing kernel Hilbert spaces