Support Vector Machines

Table of Contents

1. Learning Objectives
2. Notation
3. Core Intuition
4. Hard-Margin SVM: Maximum Margin Classifier
5. The Lagrangian Dual Problem
6. KKT Conditions and Support Vectors
7. Soft-Margin SVM
8. The Kernel Trick
9. Common Kernels
10. The Representer Theorem
11. Hinge Loss Interpretation
12. Common Pitfalls
13. Research Perspective
14. Summary
15. Exercises

Learning Objectives

1. Derive the maximum-margin hyperplane for linearly separable data.
2. Formulate the dual problem via Lagrange multipliers and interpret it geometrically.
3. State and verify the KKT complementary slackness conditions.
4. Extend to non-separable data via slack variables (soft-margin).
5. Apply the kernel trick to obtain nonlinear decision boundaries without explicit feature maps.
6. Connect hinge loss + L2 regularization to the SVM objective.

Notation

• $(x_i, y_i)_{i=1}^n$ with $y_i \in \{-1, +1\}$ — training data
• $\mathbf{w} \in \mathbb{R}^d$, $b \in \mathbb{R}$ — weight vector and bias
• $\gamma = y_i(\mathbf{w}^T\mathbf{x}_i + b)$ — functional margin
• $\alpha_i \geq 0$ — dual variables (Lagrange multipliers)
• $K(\mathbf{x}, \mathbf{x}') = \langle\phi(\mathbf{x}), \phi(\mathbf{x}')\rangle$ — kernel function
• $\xi_i \geq 0$ — slack variables
• $C > 0$ — misclassification penalty (inverse regularization)

Core Intuition

Among all hyperplanes that correctly classify the training data, the SVM selects the one with maximum margin — the largest distance to the nearest data point. This maximizes robustness to perturbations and, by VC-theory, yields favorable generalization bounds. The solution depends only on a few "support vectors" — the critical data points lying on the margin boundary.

Hard-Margin SVM: Maximum Margin Classifier

For linearly separable data, we seek a hyperplane $\mathbf{w}^T\mathbf{x} + b = 0$ such that:

The geometric margin (distance from hyperplane to nearest point) is $\frac{2}{\lVert\mathbf{w}\rVert}$. Maximizing the margin is equivalent to:

This is a convex quadratic program (QP) with linear constraints.

The Lagrangian Dual Problem

Introduce multipliers $\alpha_i \geq 0$:

Setting $\partial\mathcal{L}/\partial\mathbf{w} = 0$:

Setting $\partial\mathcal{L}/\partial b = 0$:

Substituting back into $\mathcal{L}$ yields the dual problem:

The dual depends on data only through inner products $\mathbf{x}_i^T\mathbf{x}_j$ — this is the entry point for kernelization.

KKT Conditions and Support Vectors

The KKT complementary slackness conditions state:

This means either $\alpha_i = 0$ (point is not a support vector, lies strictly beyond the margin) or $y_i(\mathbf{w}^T\mathbf{x}_i + b) = 1$ (point lies exactly on the margin — a support vector).

The solution $\mathbf{w} = \sum_i \alpha_i y_i \mathbf{x}_i$ is a sparse linear combination of training points, with nonzero $\alpha_i$ only for support vectors.

Soft-Margin SVM

For non-separable data, introduce slack variables $\xi_i \geq 0$:

The dual becomes:

The box constraint $\alpha_i \leq C$ is the only difference from the hard-margin dual.

The Kernel Trick

Replace inner products $\mathbf{x}_i^T\mathbf{x}_j$ with $K(\mathbf{x}_i, \mathbf{x}_j) = \langle\phi(\mathbf{x}_i), \phi(\mathbf{x}_j)\rangle$ where $\phi: \mathcal{X} \to \mathcal{H}$ maps to a (possibly infinite-dimensional) feature space:

The decision function becomes:

We never compute $\phi(\mathbf{x})$ explicitly — only kernel evaluations.

Mercer's Theorem. $K$ is a valid kernel if and only if it is symmetric and positive semi-definite: $\sum_{i,j}c_ic_jK(\mathbf{x}_i,\mathbf{x}_j) \geq 0$ for all $\{c_i\}$ and $\{\mathbf{x}_i\}$.

Common Kernels

• Linear: $K(\mathbf{x}, \mathbf{x}') = \mathbf{x}^T\mathbf{x}'$
• Polynomial: $K(\mathbf{x}, \mathbf{x}') = (\mathbf{x}^T\mathbf{x}' + c)^p$
• RBF (Gaussian): $K(\mathbf{x}, \mathbf{x}') = \exp(-\gamma\lVert\mathbf{x} - \mathbf{x}'\rVert^2)$
  • Corresponds to infinite-dimensional feature space.
  • $\gamma$ controls the "locality" of influence.

The Representer Theorem

Theorem. For any regularized empirical risk minimization problem of the form:

the minimizer admits the representation $f^*(\mathbf{x}) = \sum_{i=1}^n c_i K(\mathbf{x}_i, \mathbf{x})$.

This justifies the kernel SVM: even though $\mathcal{H}$ may be infinite-dimensional, the optimal solution lies in the $n$-dimensional subspace spanned by $K(\mathbf{x}_i, \cdot)$.

Hinge Loss Interpretation

The soft-margin SVM is equivalent to minimizing:

This is hinge loss + L2 regularization, connecting SVMs to the general framework of regularized loss minimization. The hinge loss is a convex upper bound on the 0-1 classification loss.

Common Pitfalls

Pitfall 1. Forgetting to scale features. SVMs use distances/inner products; features on different scales distort the geometry.

Pitfall 2. Using RBF kernel with incorrect $\gamma$. Too large $\gamma$ → each point only influences itself (overfitting). Too small $\gamma$ → all points look similar (underfitting).

Pitfall 3. Expecting SVMs to scale to very large datasets. The dual has $n$ variables; solving the QP is $O(n^2)$–$O(n^3)$ in practice. Use SGD on the primal hinge loss for large $n$.

Research Perspective

SVMs were the dominant classification method from the mid-1990s to early 2010s (Vapnik, 1995; Cortes & Vapnik, 1995). Their theoretical appeal lies in the margin-based generalization bounds and the elegant kernel framework. The kernel trick has since been reinterpreted through the Neural Tangent Kernel lens, connecting SVMs to infinite-width neural networks. Modern large-scale kernel methods use random Fourier features (Rahimi & Recht, 2007) to approximate RBF kernels in linear time.

Summary

• Hard-margin SVM finds the maximum-margin separating hyperplane via a convex QP.
• The dual depends only on inner products → enables kernelization.
• Support vectors are the only data points that determine the solution.
• Soft-margin handles non-separable data via slack variables and penalty $C$.
• Kernel trick implicitly maps to high-dimensional spaces without computing the map.
• SVM $\Leftrightarrow$ hinge loss + L2 regularization.

Exercises

Exercise 1. Show that the distance from a point $\mathbf{x}_0$ to the hyperplane $\mathbf{w}^T\mathbf{x} + b = 0$ is $\frac{|\mathbf{w}^T\mathbf{x}_0 + b|}{\lVert\mathbf{w}\rVert}$.

Exercise 2. Derive the dual problem (equation 6) from the Lagrangian by eliminating $\mathbf{w}$ and $b$.

Exercise 3. Verify the KKT conditions for a simple 2D example with 3 points.

Exercise 4. Show that the polynomial kernel $K(\mathbf{x}, \mathbf{x}') = (\mathbf{x}^T\mathbf{x}' + 1)^2$ corresponds to a specific finite-dimensional feature map (write it explicitly for $d=2$).

Exercise 5. Prove that the RBF kernel $K(\mathbf{x}, \mathbf{x}') = e^{-\gamma\lVert\mathbf{x}-\mathbf{x}'\rVert^2}$ is positive semi-definite by expanding as an infinite series.