Support Vector Machines

Background

Developed by Vapnik and Cortes in 1995 as a principled margin-maximization classifier
The kernel trick enabled non-linear classification without explicit high-dimensional feature maps
Dominated NLP and computer vision before deep learning (2000s)

The Concept

An SVM finds the hyperplane that maximally separates two classes - the 'widest street' between them. Only the points closest to the boundary (support vectors) determine the decision surface. Kernels allow non-linear boundaries by implicitly mapping data to higher dimensions.

How it Links

Generalizes the perceptron by adding the max-margin criterion
Kernel methods connect to Gaussian processes and kernel PCA
The dual problem and KKT conditions connect to constrained optimization theory

Concrete Example

Classifying emails as spam/ham: the SVM finds the boundary that keeps the most margin between the clearly-spam and clearly-not-spam examples. If a new email falls in the margin, the model is less certain - this uncertainty region has principled theory behind it.

Prerequisites

Math you need: linear algebra and convex optimization, Perceptron, Logistic regression, Bias, variance, over/under-fitting

Learning outcomes

Derive the maximum-margin primal and its hard-margin and soft-margin variants.
Take the Lagrangian, apply the KKT conditions, and obtain the dual quadratic program.
Explain the kernel trick: only inner products appear in the dual, so $K(x_i, x_j)$ replaces $x_i^\top x_j$.
State Mercer's condition and the representer theorem, and recognize why the optimal $w$ lies in the span of the training inputs.
Compare SVMs to perceptron, logistic regression, and kernel ridge regression on loss, output, calibration, and training cost.

TL;DR

A support vector machine (SVM) finds the hyperplane that maximizes the margin between two classes [1]. The primal is a convex quadratic program, and its Lagrangian dual depends on the data only through inner products $x_i^\top x_j$ . Replacing those inner products with a positive semi-definite kernel $K(x_i, x_j)$ implicitly maps to a (possibly infinite-dimensional) feature space at no extra cost - the kernel trick [2][3]. The representer theorem says the optimal classifier lies in the span of the training inputs, so the model is a weighted sum over support vectors. Soft-margin SVMs add slack variables $\xi_i$ and a regularization knob $C$ that trades margin width for slack [2]. The standard fitting algorithm is Sequential Minimal Optimization (SMO), which decomposes the dual into analytically solvable two-variable subproblems [4]. SVMs dominated supervised learning roughly 1995-2010 and remain the right tool for small-to-medium tabular datasets with a clear margin.

Intuition

Two linearly separable clouds of points admit infinitely many separating hyperplanes. The SVM picks the one that sits as far as possible from the closest points of either class. The width of the slab between the boundary and those closest points is the margin, and the points that touch the slab edges are the support vectors. Once you have them, the rest of the training set is irrelevant to the model.

Two facts make this work in practice:

Convex QP. The “max-margin” goal becomes a convex quadratic program with linear constraints, so it has a unique global optimum and well-conditioned solvers [7].
Kernel trick. The dual depends on the data only through $x_i^\top x_j$ . Replace those with $K(x_i, x_j) = \phi(x_i)^\top \phi(x_j)$ for any positive semi-definite kernel and you get a non-linear classifier without ever computing $\phi$ [3].

Why the margin is the right thing to maximize

VC-style generalization bounds for linear classifiers shrink as the margin grows: a fatter slab means a smaller effective hypothesis class and tighter test-error guarantees, independent of input dimension [2]. The geometric intuition is identical: a wider gap leaves more room for test-time noise before a point crosses the boundary. The hinge loss that falls out of the dual is exactly the convex surrogate that targets this margin.

Maximum-margin separator: w^T x + b = 0, slab edges at +-1

w^T x + b = +1w^T x + b = 0w^T x + b = -1support vectorsupport vectormargin = 2 / ||w||

Maximize 2 / ||w|| subject to y_i (w^T x_i + b) at least 1. Equivalent to minimize (1/2) ||w||^2.

Figure 1. The SVM picks the hyperplane that maximizes the slab width between the two classes. Only the support vectors (highlighted) constrain the solution; the others can move freely without changing $w$ or $b$ .

Math

Hard-margin primal: max-margin as a convex QP

Setup

Let $\{(x_i, y_i)\}_{i=1}^{n}$ with $x_i \in \mathbb{R}^{d}$ and $y_i \in \{-1, +1\}$ be linearly separable. A separating hyperplane $\{x : w^\top x + b = 0\}$ classifies $x$ by $\operatorname{sign}(w^\top x + b)$ .

Functional and geometric margin

For a fixed $(w, b)$ , the functional margin of example $i$ is $\hat{\gamma}_i = y_i (w^\top x_i + b)$ , and the geometric margin is $\gamma_i = \hat{\gamma}_i / \lVert w \rVert$ - the signed Euclidean distance from $x_i$ to the hyperplane.

The geometric margin is invariant to rescaling $(w, b) \to (cw, cb)$ for $c > 0$ , while the functional margin is not. We can therefore fix the scale by requiring the functional margin of the closest point to equal $1$ :

\min_{i} y_i (w^\top x_i + b) = 1.

Under this normalization, the geometric margin is $1 / \lVert w \rVert$ and the slab width (the gap between the two parallel lines $w^\top x + b = \pm 1$ ) is $2 / \lVert w \rVert$ .

The hard-margin primal

Maximizing the slab width is equivalent to minimizing $\lVert w \rVert$ , or equivalently $\tfrac{1}{2}\lVert w \rVert^2$ (which is smooth and convex):

\boxed{\;\min_{w, b}\; \tfrac{1}{2}\,\lVert w \rVert_2^{2} \quad \text{s.t.} \quad y_i(w^\top x_i + b) \ge 1 \;\; \text{for all } i = 1, \dots, n.\;}

This is a convex quadratic program: convex quadratic objective, linear inequality constraints, so it has a unique global minimum if the data is separable [1][7].

Lagrangian, KKT conditions, and the dual

Lagrangian

Introduce dual variables $\alpha_i \ge 0$ for each constraint and form

\mathcal{L}(w, b, \alpha) = \tfrac{1}{2}\,\lVert w \rVert_2^{2} - \sum_{i=1}^{n} \alpha_i\bigl[y_i(w^\top x_i + b) - 1\bigr].

Stationarity (primal optimality)

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

w = \sum_{i=1}^{n} \alpha_i y_i x_i, \qquad \sum_{i=1}^{n} \alpha_i y_i = 0.

The first equation already encodes the representer theorem for the linearly separable SVM: the optimal $w$ is a linear combination of the training inputs, with coefficients $\alpha_i y_i$ .

KKT conditions

For convex QPs with affine constraints, the KKT conditions are necessary and sufficient:

Primal feasibility: $y_i(w^\top x_i + b) \ge 1$ for all $i$ .
Dual feasibility: $\alpha_i \ge 0$ for all $i$ .
Stationarity: $w = \sum_i \alpha_i y_i x_i$ and $\sum_i \alpha_i y_i = 0$ .
Complementary slackness: $\alpha_i \bigl[y_i(w^\top x_i + b) - 1\bigr] = 0$ for all $i$ .

Complementary slackness has a sharp consequence: $\alpha_i > 0$ forces $y_i(w^\top x_i + b) = 1$ , meaning $x_i$ lies exactly on the margin. Those are the support vectors. Every other example has $\alpha_i = 0$ and therefore contributes nothing to $w$ .

The dual

Substituting $w = \sum_i \alpha_i y_i x_i$ back into $\mathcal{L}$ and simplifying yields the dual problem - a quadratic in $\alpha$ alone:

\boxed{\;\max_{\alpha}\; \sum_{i=1}^{n} \alpha_i - \tfrac{1}{2}\sum_{i=1}^{n}\sum_{j=1}^{n} \alpha_i \alpha_j\, y_i y_j\, x_i^\top x_j \quad \text{s.t.} \quad \sum_{i} \alpha_i y_i = 0,\; \alpha_i \ge 0.\;}

Three things are crucial about this form [7][6]:

The dual is again a convex QP (the matrix with entries $y_i y_j x_i^\top x_j$ is positive semi-definite).
Strong duality holds (Slater’s condition), so the dual optimum equals the primal optimum.
The data appears only through the inner products $x_i^\top x_j$ . This is what enables the kernel trick.

Recovering the bias

Pick any support vector $x_s$ (with $0 < \alpha_s$ ). Complementary slackness gives $y_s(w^\top x_s + b) = 1$ , so

b = y_s - w^\top x_s = y_s - \sum_{i=1}^{n} \alpha_i y_i x_i^\top x_s.

In practice we average this over all support vectors for numerical stability.

Soft-margin SVM: slack variables and the role of $C$

Real data is rarely linearly separable. The soft-margin SVM [2] introduces non-negative slack variables $\xi_i \ge 0$ that allow individual examples to violate the margin:

\boxed{\;\min_{w, b, \xi}\; \tfrac{1}{2}\,\lVert w \rVert_2^{2} + C \sum_{i=1}^{n} \xi_i \quad \text{s.t.} \quad y_i(w^\top x_i + b) \ge 1 - \xi_i, \;\; \xi_i \ge 0.\;}

Examples with $\xi_i = 0$ are correctly classified outside the margin; with $0 < \xi_i \le 1$ they sit inside the margin but on the correct side; with $\xi_i > 1$ they are misclassified. The parameter $C > 0$ is a regularization knob trading margin width for slack: large $C$ heavily penalizes slack and produces a narrow, low-bias / high-variance margin; small $C$ tolerates slack and produces a wide, high-bias / low-variance margin.

Soft-margin dual

A near-identical derivation yields the dual

\max_{\alpha}\; \sum_{i=1}^{n} \alpha_i - \tfrac{1}{2}\sum_{i, j} \alpha_i \alpha_j y_i y_j x_i^\top x_j \quad \text{s.t.} \quad \sum_{i} \alpha_i y_i = 0, \;\; 0 \le \alpha_i \le C.

The single change from the hard-margin dual is the box constraint $\alpha_i \le C$ on each dual variable. KKT now classifies points into three groups:

$\alpha_i = 0$ : outside the margin, no influence.
$0 < \alpha_i < C$ : exactly on the margin (a margin support vector); $\xi_i = 0$ .
$\alpha_i = C$ : inside the margin or misclassified; $\xi_i \ge 0$ takes up the slack.

Equivalent hinge-loss form

Eliminating the slacks by choosing $\xi_i = \max(0, 1 - y_i(w^\top x_i + b))$ rewrites the soft-margin problem as

\min_{w, b}\; \frac{1}{2}\lVert w \rVert_2^{2} + C \sum_{i=1}^{n} \max\!\bigl(0,\, 1 - y_i(w^\top x_i + b)\bigr).

That second sum is the hinge loss $\ell_{\mathrm{hinge}}(z) = \max(0, 1 - z)$ . The hinge loss is convex but non-smooth at $z = 1$ , which is why direct primal optimization needs subgradient methods or the dual form [6].

The kernel trick

In the dual, the data appears only through inner products $x_i^\top x_j$ . If we instead apply some feature map $\phi : \mathbb{R}^{d} \to \mathcal{H}$ to a (possibly very high-dimensional) Hilbert space and replace $x_i^\top x_j$ with $\phi(x_i)^\top \phi(x_j)$ , the entire derivation goes through unchanged. Define a kernel function

K(x, x') = \phi(x)^\top \phi(x'),

and the dual becomes

\max_{\alpha}\; \sum_i \alpha_i - \tfrac{1}{2}\sum_{i, j} \alpha_i \alpha_j y_i y_j K(x_i, x_j) \quad \text{s.t.} \quad \sum_i \alpha_i y_i = 0,\; 0 \le \alpha_i \le C.

The classifier at test time is

f(x) = \operatorname{sign}\!\Bigl(\sum_{i=1}^{n} \alpha_i y_i K(x_i, x) + b\Bigr),

so we never need $\phi$ explicitly - only the kernel [3].

The standard kernel zoo

Kernel	K(x, y)	Implicit feature space	When to use
Linear	x^T y	R^d itself	High-dimensional sparse data (text TF-IDF), as a baseline.
Polynomial (degree d, offset c)	(x^T y + c)^d	monomials of degree at most d in the original features	When you suspect feature interactions of bounded degree.
Gaussian / RBF	exp(-gamma * \|\|x - y\|\|^2)	infinite-dimensional Hilbert space (Gaussian basis)	Generic non-linear default; gamma controls smoothness.
Sigmoid (tanh)	tanh(kappa * x^T y + c)	not always PSD; matches a 1-hidden-layer NN	Historical interest; not always Mercer-valid.

Mercer's condition: which functions are valid kernels?

A function $K : \mathcal{X} \times \mathcal{X} \to \mathbb{R}$ is a valid kernel (i.e. corresponds to an inner product in some Hilbert space) if and only if for every finite set $\{x_1, \dots, x_n\}$ the Gram matrix

K_{ij} = K(x_i, x_j)

is symmetric and positive semi-definite (PSD): $z^\top K z \ge 0$ for every $z \in \mathbb{R}^{n}$ .

This is Mercer’s condition (after Mercer’s 1909 theorem on continuous kernels on a compact domain) [3]. It is the bridge between the algebraic (“the dual is PSD”) and analytic (“there exists a feature map $\phi$ ”) views of kernels.

Why we care

Mercer’s condition guarantees:

The dual SVM problem is convex, so a unique global optimum exists.
There is some feature map $\phi$ with $K(x, x') = \phi(x)^\top \phi(x')$ , even if we never construct it.
Closure properties: sums, products, and positive scalar multiples of valid kernels are valid kernels, so we can compose new ones.

The sigmoid kernel $\tanh(\kappa\,x^\top y + c)$ fails Mercer for many parameter values, which is why it sometimes “works” empirically and sometimes makes solvers blow up - the dual stops being convex when $K$ has negative eigenvalues.

Representer theorem: the optimal classifier lives in the span of training inputs

Statement (Schölkopf-Smola form)

Let $\mathcal{H}$ be a reproducing-kernel Hilbert space (RKHS) with kernel $K$ and norm $\lVert \cdot \rVert_{\mathcal{H}}$ . Consider a regularized learning problem of the form

\min_{f \in \mathcal{H}}\; \sum_{i=1}^{n} L\bigl(y_i, f(x_i)\bigr) + \Omega\bigl(\lVert f \rVert_{\mathcal{H}}\bigr),

where $L$ is any pointwise loss and $\Omega : [0, \infty) \to \mathbb{R}$ is a strictly increasing function. Then any minimizer $f^\star$ admits a representation

f^\star(x) = \sum_{i=1}^{n} c_i\, K(x_i, x)

for some coefficients $c_i \in \mathbb{R}$ [3].

Proof sketch

Decompose the RKHS as $\mathcal{H} = \mathcal{V} \oplus \mathcal{V}^{\perp}$ , where $\mathcal{V} = \operatorname{span}\{K(x_i, \cdot)\}_{i=1}^{n}$ is the finite-dimensional subspace spanned by the training-input feature maps and $\mathcal{V}^{\perp}$ is its orthogonal complement.

Any $f \in \mathcal{H}$ splits as $f = f_{\parallel} + f_{\perp}$ with $f_{\parallel} \in \mathcal{V}$ and $f_{\perp} \in \mathcal{V}^{\perp}$ . By the reproducing property $f(x_i) = \langle f, K(x_i, \cdot)\rangle_{\mathcal{H}}$ , and orthogonality kills $f_{\perp}$ at every training input:

f(x_i) = \langle f_{\parallel}, K(x_i, \cdot)\rangle + \langle f_{\perp}, K(x_i, \cdot)\rangle = f_{\parallel}(x_i) + 0.

So the loss term depends only on $f_{\parallel}$ . The regularizer $\Omega(\lVert f \rVert_{\mathcal{H}})$ is strictly increasing and Pythagoras gives $\lVert f \rVert_{\mathcal{H}}^{2} = \lVert f_{\parallel} \rVert_{\mathcal{H}}^{2} + \lVert f_{\perp} \rVert_{\mathcal{H}}^{2}$ , so adding any non-zero $f_{\perp}$ strictly increases the regularizer without changing the loss. Therefore the minimizer must have $f_{\perp} = 0$ , i.e. $f^\star \in \mathcal{V}$ . ∎

What it buys

The representer theorem reduces an infinite-dimensional optimization (over all of $\mathcal{H}$ ) to a finite-dimensional one (over the $n$ coefficients $c_i$ ). It is the reason all kernel methods - SVMs, kernel ridge regression, kernel PCA, Gaussian processes - reduce to algebra in $\mathbb{R}^{n}$ rather than functional analysis. The SVM specifically chooses the $c_i$ via the dual, which makes most of them zero (sparse expansion in support vectors).

SMO: how the dual is actually solved

The dual is a convex QP in $n$ variables with $n$ box constraints and one equality constraint. Generic QP solvers scale poorly when $n$ is in the tens of thousands, and constructing the full $n \times n$ kernel matrix is $O(n^2)$ memory. Sequential Minimal Optimization (SMO) decomposes the dual into the smallest possible subproblems and solves them analytically [4].

The key idea: pick a pair $(\alpha_i, \alpha_j)$ to update, fix all the others, and solve the resulting two-variable QP in closed form. Two variables are necessary (not just one) because the equality constraint $\sum_k \alpha_k y_k = 0$ couples them.

Step	Operation
1	Choose two Lagrange multipliers (alpha_i, alpha_j) violating the KKT conditions most strongly (heuristic working-set selection).
2	Hold all other alphas fixed. The equality constraint forces alpha_i + s * alpha_j = const, where s = y_i * y_j.
3	Solve the resulting one-dimensional QP in alpha_j analytically; clip to the box [0, C] using the linear constraint.
4	Recompute the bias b from any margin support vector.
5	Repeat until KKT conditions are satisfied to a tolerance.

SMO never needs the full kernel matrix at once - it computes kernel rows on demand - and its per-iteration cost is constant. The total cost is empirically $O(n^2)$ to $O(n^{2.3})$ for many problems, far better than naive QP solvers. Modern libraries (LIBSVM, sklearn’s SVC) use SMO under the hood with working-set-selection heuristics that improve on Platt’s original choice.

Why SVMs were dominant 1995-2010

Before the ImageNet moment, SVMs were the default supervised classifier across academia and industry. Three reasons:

Strong theory. VC bounds, the kernel trick, and convex duality gave a clean explanation of why the model works, not just that it works [2].
Empirical performance. With an RBF kernel and a tuned $(C, \gamma)$ , SVMs outperformed neural nets on most small-to-medium tabular and text benchmarks until backpropagation was rescued by GPUs and large datasets.
No hyperparameter zoo. Two knobs ( $C$ , $\gamma$ ) and a kernel choice covered most use cases. Compared with the architecture-and-optimizer search of modern deep learning, this was a gift.

Their fall from dominance is also explained by their structure: the $O(n^2)$ -to- $O(n^3)$ training cost and dense-kernel-matrix memory wall do not scale to millions of examples, which is exactly what deep nets started feeding on in 2012.

Model	Loss	Output	Calibrated probabilities?	Kernel support	Training cost
Perceptron	perceptron loss: max(0, -y * (w^T x + b))	sign(w^T x + b)	no	kernel perceptron exists, rarely used	O(n) per pass; converges in finite steps if separable.
Logistic regression	logistic / cross-entropy: log(1 + exp(-y * (w^T x + b)))	sigma(w^T x + b)	yes (trained on log-likelihood)	kernel logistic regression possible but loses sparsity	O(n d) per IRLS iteration; full data each step.
SVM (hinge)	hinge: max(0, 1 - y * (w^T x + b))	sign(w^T x + b)	no (Platt scaling adds them post hoc)	native via the dual; sparse in support vectors	O(n^2) to O(n^3) typical; SMO scales to n in the tens of thousands.
Kernel ridge regression	squared: (y - f(x))^2 + lambda * \|\|f\|\|_H^2	real-valued f(x), then threshold	no (regression to real-valued targets)	native; closed form via (K + lambda I)^(-1) y	O(n^3) for the matrix solve; dense in all training points (no sparsity).

A quick mnemonic: SVM gives you margin + sparsity; logistic regression gives you probabilities; kernel ridge gives you a closed form but no sparsity; the perceptron [8] gives you the cheapest convergence guarantee.

Implementations

Three idiomatic implementations of the soft-margin SVM. The numpy version sketches the dual as a generic QP fed to scipy.optimize.minimize (purely illustrative; production solvers use SMO); the sklearn-svc version is the production default with an RBF kernel; the sklearn-nystroem version approximates the kernel feature map and feeds a LinearSVC for scale.

python

import numpy as np
from scipy.optimize import minimize

def fit_svm_dual(X, y, C=1.0):
  """Sketch: solve the soft-margin dual via a generic QP solver.
  Production code uses SMO (Platt 1998); this shows the math, not the speed.
  y is in {-1, +1}.
  """
  n = X.shape[0]
  K = X @ X.T                                 # linear kernel
  P = (np.outer(y, y)) * K                    # n x n PSD matrix
  q = -np.ones(n)
  bounds = [(0, C)] * n                       # 0 <= alpha_i <= C

  def neg_dual(alpha):                        # minimize -dual
      return 0.5 * alpha @ P @ alpha + q @ alpha
  def neg_dual_grad(alpha):
      return P @ alpha + q

  cons = ({'type': 'eq', 'fun': lambda a: a @ y})
  res = minimize(neg_dual, np.zeros(n), jac=neg_dual_grad,
                 bounds=bounds, constraints=cons, method='SLSQP')
  alpha = res.x

  # Recover w from the representer formula and b from a margin SV.
  w = (alpha * y) @ X
  sv = (alpha > 1e-5) & (alpha < C - 1e-5)    # margin support vectors
  b = np.mean(y[sv] - X[sv] @ w) if sv.any() else 0.0
  return w, b, alpha

# tiny synthetic example
rng = np.random.default_rng(0)
X = np.vstack([rng.normal(loc=[-2, 0], size=(20, 2)),
             rng.normal(loc=[+2, 0], size=(20, 2))])
y = np.array([-1] * 20 + [+1] * 20)
w, b, alpha = fit_svm_dual(X, y, C=1.0)
print("w :", np.round(w, 3))
print("b :", round(float(b), 3))
print("# support vectors:", int((alpha > 1e-5).sum()))

Sketch only. SLSQP is fine for n in the dozens; for production use sklearn or LIBSVM (which run SMO internally).

Run a small sklearn SVC with an RBF kernel on make_moons live in the browser to see the non-linear decision boundary that the kernel trick buys:

Idle (packages: numpy, scikit-learn)

(no output yet)

Real-world uses

Domain	System	Why SVMs
Text classification (1995-2010)	Spam filters, news topic classifiers, sentiment analysis with bag-of-words / TF-IDF features	Linear SVM on sparse high-dimensional features dominated until LR caught up; the dual makes the kernel trick optional but the duality view stays useful.
Bioinformatics	Microarray gene-expression classifiers; protein structure prediction	High-d, small-n tabular data; the margin gives sane generalization where logistic regression overfits without strong regularization.
Computer vision (pre-deep-learning)	HOG + linear SVM for pedestrian detection (Dalal-Triggs 2005); SIFT + bag-of-visual-words + RBF SVM	The standard pipeline before CNNs ate the field in 2012.
Anomaly detection	One-class SVM for novelty detection on tabular telemetry	Kernelized boundary in the feature space; handles non-linear "normal regions" without distributional assumptions.
Small tabular Kaggle / business analytics	Default non-tree baseline alongside logistic regression	Strong out-of-the-box accuracy on n in the thousands with low feature dimension.

Pitfalls

Always standardize features before an RBF kernel

The RBF kernel $\exp(-\gamma \lVert x - y \rVert^{2})$ measures distance in the raw feature units. A feature in millimetres and a feature in kilometres have wildly different effective $\gamma$ values, and one will dominate. Wrap the SVC in a StandardScaler (or MinMaxScaler) and treat that as a non-negotiable. The same applies to polynomial kernels with offset.

The default $C$ is rarely right

SVC(C=1.0) is a placeholder, not a recommendation. The optimal $C$ depends on noise level, class balance, and feature scale. A grid search over $C \in \{0.1, 1, 10, 100\}$ paired with $\gamma \in \{\text{scale, auto, } 0.01, 0.1, 1\}$ is the cheapest way to get an honest estimate. Using class_weight='balanced' helps under heavy class imbalance.

SVMs do not output probabilities natively

The decision function $w^\top x + b$ is a signed distance, not a calibrated probability. The probability=True flag in sklearn turns on Platt scaling (fit a logistic regression to the SVM scores on a held-out fold) [5], which adds a $\sim 5\!\times$ training-time cost and is still less calibrated than logistic regression itself. If you need probabilities, prefer logistic regression, or use the SVM only for the hard label and calibrate post hoc with CalibratedClassifierCV.

Training scales like $O(n^{2})$ to $O(n^{3})$

LIBSVM-backed solvers are far slower than $O(n)$ - in the worst case the kernel matrix is dense and every QP iteration touches all of it. Beyond a few hundred thousand examples, prefer Nystroem / RBFSampler + LinearSVC, or move to gradient boosting / a small neural net. SVMs do not scale to “modern” dataset sizes the way logistic regression and trees do.

Linear SVM on sparse high-d data is still elite

For text bags-of-words and TF-IDF features (millions of features, mostly zeros), LinearSVC (with squared hinge loss and dual=False) is one of the fastest, most accurate baselines you can run. Logistic regression with the same features is essentially tied; pick whichever you prefer for the calibration story.

Interview Q&A

Derive the hard-margin SVM primal and dual.research

Primal. Given linearly separable $\{(x_i, y_i)\}$ with $y_i \in \{-1, +1\}$ , fix the scale by $\min_i y_i(w^\top x_i + b) = 1$ . The geometric margin is then $1/\lVert w \rVert$ , so maximizing the slab width $2/\lVert w \rVert$ is equivalent to

\min_{w, b}\; \tfrac{1}{2}\lVert w \rVert^{2} \quad \text{s.t.} \quad y_i(w^\top x_i + b) \ge 1 \;\;\forall i.

This is a convex QP with linear inequality constraints.

Lagrangian. With multipliers $\alpha_i \ge 0$ ,

\mathcal{L}(w, b, \alpha) = \tfrac{1}{2}\lVert w \rVert^{2} - \sum_{i} \alpha_i\bigl[y_i(w^\top x_i + b) - 1\bigr].

Stationarity. $\nabla_w \mathcal{L} = 0$ gives $w = \sum_i \alpha_i y_i x_i$ , and $\partial \mathcal{L}/\partial b = 0$ gives $\sum_i \alpha_i y_i = 0$ .

Dual. Substituting back,

\max_{\alpha}\; \sum_{i} \alpha_i - \tfrac{1}{2} \sum_{i, j} \alpha_i \alpha_j y_i y_j x_i^\top x_j \quad \text{s.t.} \quad \sum_{i} \alpha_i y_i = 0,\;\; \alpha_i \ge 0.

Strong duality holds (Slater’s condition is automatic for affine constraints with non-empty feasible set), so primal and dual optima coincide. KKT complementary slackness $\alpha_i [y_i(w^\top x_i + b) - 1] = 0$ shows that $\alpha_i > 0$ implies $x_i$ lies on the margin: those are the support vectors [1][7].

Sketch the proof of the representer theorem and explain why it matters.research

Setup. Let $\mathcal{H}$ be an RKHS with kernel $K$ , and consider

\min_{f \in \mathcal{H}}\; \sum_{i=1}^{n} L\bigl(y_i, f(x_i)\bigr) + \Omega\bigl(\lVert f \rVert_{\mathcal{H}}\bigr),

with $\Omega$ strictly increasing.

Decomposition. Let $\mathcal{V} = \operatorname{span}\{K(x_i, \cdot)\}_{i=1}^{n}$ and $\mathcal{V}^\perp$ its orthogonal complement. Any $f \in \mathcal{H}$ writes uniquely as $f = f_\parallel + f_\perp$ with $f_\parallel \in \mathcal{V}$ , $f_\perp \in \mathcal{V}^\perp$ .

Loss term. By the reproducing property $f(x_i) = \langle f, K(x_i, \cdot)\rangle$ , and orthogonality kills $f_\perp$ at training inputs: $f(x_i) = f_\parallel(x_i)$ . So the loss depends only on $f_\parallel$ .

Regularizer. Pythagoras gives $\lVert f \rVert_\mathcal{H}^{2} = \lVert f_\parallel \rVert^{2} + \lVert f_\perp \rVert^{2}$ . Since $\Omega$ is strictly increasing, any non-zero $f_\perp$ strictly increases the regularizer without changing the loss. So the minimizer has $f_\perp = 0$ , i.e. $f^\star \in \mathcal{V}$ , which means

f^\star(x) = \sum_{i=1}^{n} c_i\, K(x_i, x).

Why it matters. The theorem reduces an infinite-dimensional optimization problem to an $n$ -dimensional one. It is the reason every kernel method - SVMs, kernel ridge, kernel PCA, Gaussian processes - reduces to algebra in $\mathbb{R}^{n}$ [3]. For SVMs specifically, the dual makes most $c_i$ zero, giving the sparse expansion in support vectors.

State the kernel trick formally. Why don't we ever need $\phi(x)$?onsite

The dual SVM objective and the test-time decision function depend on the data only through inner products $x_i^\top x_j$ . Replacing those with $K(x_i, x_j) = \phi(x_i)^\top \phi(x_j)$ for any map $\phi : \mathcal{X} \to \mathcal{H}$ to a Hilbert space gives the kernelized version

f(x) = \operatorname{sign}\!\Bigl(\sum_{i=1}^{n} \alpha_i y_i K(x_i, x) + b\Bigr).

We never compute $\phi(x)$ directly. Mercer’s condition (PSD Gram matrix on every finite subset) guarantees that some such $\phi$ exists, even though we may not be able to write it down in closed form. For the RBF kernel $K(x, y) = \exp(-\gamma \lVert x - y \rVert^{2})$ , $\phi$ lives in an infinite-dimensional space, yet $K$ is computable in $O(d)$ [3]. The kernel trick decouples expressive feature space from compute cost, and that decoupling is what enabled non-linear SVMs to dominate from 1995 to 2010.

In the soft-margin SVM, why does $C$ trade margin width for slack?onsite

The soft-margin objective

\min_{w, b, \xi}\; \tfrac{1}{2}\lVert w \rVert^{2} + C \sum_{i} \xi_i \quad \text{s.t.}\quad y_i(w^\top x_i + b) \ge 1 - \xi_i,\; \xi_i \ge 0

balances two terms:

$\tfrac{1}{2}\lVert w \rVert^{2}$ rewards small $w$ , which means a wide margin (slab width $= 2/\lVert w \rVert$ ).
$C \sum_i \xi_i$ penalizes margin violations, with larger $C$ making each unit of slack more expensive.

Large $C$ : slack is very expensive, so the optimizer drives $\xi_i \to 0$ even at the cost of a large $\lVert w \rVert$ - a narrow margin that is intolerant of noise (low bias, high variance). In the limit $C \to \infty$ this is the hard-margin SVM, which only exists for linearly separable data.

Small $C$ : slack is cheap, so the optimizer prefers a wide margin even if many points violate it (high bias, low variance). Many examples land at $\alpha_i = C$ in the dual (bound support vectors).

The dual makes this concrete: the box constraint $0 \le \alpha_i \le C$ caps how much any single example can pull on $w$ . Smaller $C$ caps the influence sooner, which limits overfitting to outliers. In practice, $C$ is the regularization knob and is selected by cross-validation [2][6].

State Mercer's theorem. Why is it the right characterization of a valid kernel?research

Statement (finite version). A symmetric function $K : \mathcal{X} \times \mathcal{X} \to \mathbb{R}$ is a valid (Mercer) kernel if and only if for every finite set $\{x_1, \dots, x_n\} \subseteq \mathcal{X}$ , the Gram matrix $K_{ij} = K(x_i, x_j)$ is symmetric and positive semi-definite.

Equivalently (Mercer’s original 1909 statement on a compact domain): if $K$ is a continuous symmetric kernel on $\mathcal{X} \times \mathcal{X}$ for compact $\mathcal{X}$ , and the integral operator $T_K f(x) = \int_\mathcal{X} K(x, y) f(y)\, dy$ is positive semi-definite, then $K$ admits an eigen-expansion

K(x, y) = \sum_{k=1}^{\infty} \lambda_k\, \phi_k(x)\, \phi_k(y), \qquad \lambda_k \ge 0,

with $\{\phi_k\}$ an orthonormal basis of eigenfunctions. Setting $\Phi(x) = (\sqrt{\lambda_k}\,\phi_k(x))_k$ gives an explicit feature map satisfying $K(x, y) = \Phi(x)^\top \Phi(y)$ .

Why it is the right condition.

Existence of $\phi$ . PSD-ness is exactly what is needed for $K$ to be the inner product of some feature map in a Hilbert space.
Convexity of the dual. The dual SVM objective has Hessian $\operatorname{diag}(y) K \operatorname{diag}(y)$ , which is PSD if and only if $K$ is - so Mercer’s condition is what makes the dual a convex QP with a unique global optimum.
Closure properties. Sums, products, scalar multiples (by non-negative scalars), and tensor products of valid kernels are valid kernels, so Mercer’s condition is preserved by all the natural ways to compose kernels [3].

The sigmoid kernel $\tanh(\kappa\,x^\top y + c)$ is the textbook example of a “kernel” that fails Mercer for many parameter values, which is why it sometimes gives non-convex training and unreliable test-time behaviour.

Check yourself

Score: 0 / 5(0 answered)

1. In the hard-margin SVM dual, what is the role of the constraint sum_i alpha_i * y_i = 0?
2. What does the representer theorem say about the optimal classifier in an RKHS?
3. Which of the following is NOT a valid Mercer kernel for all parameter settings?
4. In the soft-margin dual, what does alpha_i = C imply about example i?
5. Why do SVMs not output calibrated probabilities natively?

Build it yourself

A short evening project to internalize SVMs:

Implement the soft-margin dual on a 2-D synthetic dataset using scipy.optimize.minimize with SLSQP, exactly as in the numpy CodeCompare block above. Plot the decision boundary, the two margin lines, and circle the support vectors.
Swap the linear kernel for an RBF kernel by replacing $X X^\top$ with the Gaussian Gram matrix. Confirm the boundary curves around make_moons.
Implement a tiny SMO loop: pick the two most KKT-violating $(\alpha_i, \alpha_j)$ , solve the analytic 2-var QP, clip to the box, and repeat. Compare iterations to the SLSQP path on the same problem.
Stretch: add Platt scaling on top of the SVM scores using a held-out fold, and compare the resulting calibration to logistic regression with the same features (use a reliability diagram).

Interactive Demo

SVM Margin Demo

C = 1.00

Margin width: 2.000

Support vectors: 0

Points inside margin: 0

Class +1 (blue)

Class -1 (red)

Margin lines

Support vector

What to try: Move the C slider: low C = wide margin with possible misclassifications; high C = narrow margin that tries to classify everything correctly.

References

Boser, B. E., Guyon, I. M., and Vapnik, V. N. (1992). A training algorithm for optimal margin classifiers. Proceedings of the Fifth Annual Workshop on Computational Learning Theory (COLT) 144-152. doi:10.1145/130385.130401
Cortes, C. and Vapnik, V. (1995). Support-vector networks. Machine Learning 20(3), 273-297. doi:10.1007/BF00994018
Schölkopf, B. and Smola, A. J. (2002). Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond. MIT Press. ISBN 978-0-262-19475-4
Platt, J. C. (1998). Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines. Microsoft Research Technical Report MSR-TR-98-14. https://www.microsoft.com/en-us/research/publication/sequential-minimal-optimization-a-fast-algorithm-for-training-support-vector-machines/
Platt, J. C. (1999). Probabilistic outputs for support vector machines and comparisons to regularized likelihood methods. Advances in Large Margin Classifiers, MIT Press, 61-74. ISBN 978-0-262-19448-8
Hastie, T., Tibshirani, R., and Friedman, J. (2009). The Elements of Statistical Learning, 2nd ed.. Springer. https://hastie.su.domains/ElemStatLearn/
Bishop, C. M. (2006). Pattern Recognition and Machine Learning. Springer. ISBN 978-0-387-31073-2
Rosenblatt, F. (1958). The Perceptron: A Probabilistic Model for Information Storage and Organization in the Brain. Psychological Review 65(6), 386-408. doi:10.1037/h0042519

Gradient Boosting Naive Bayes