An SVM is only as useful as our ability to solve its optimization problem efficiently. The dual is a quadratic program with \(n\) variables and a dense \(n\times n\) matrix — naively intractable for large data. This chapter explains the algorithms that make SVMs practical: general QP solvers, the elegant SMO decomposition that powers LIBSVM, and the linear-time methods (LIBLINEAR, Pegasos) for massive linear problems.

The optimization landscape

SVM training is a convex problem, so any solver reaches the global optimum — no local minima, no random restarts. The practical question is which solver, and that depends on the regime:

  • Kernel SVM, moderate \(n\): solve the dual QP — decomposition methods (SMO).

  • Linear SVM, large \(n\): solve the primal — coordinate descent (LIBLINEAR) or stochastic subgradient (Pegasos).

Quadratic programming and its limits

The dual is a textbook quadratic program (QP): maximize a concave quadratic in \(\alpha\) subject to one linear equality and box constraints \(0\le\alpha_i\le C\). Off-the-shelf QP solvers work for small problems, but they need the full Gram matrix in memory (\(O(n^2)\)) and run in roughly \(O(n^3)\) time — hopeless beyond a few thousand points. We need a method that never materializes the whole matrix.

Sequential Minimal Optimization (SMO)

SMO (Platt, 1998) is the breakthrough that made kernel SVMs practical. It exploits the equality constraint \(\sum_i\alpha_i y_i=0\): because of it, you cannot change one \(\alpha\) alone, but you can change the smallest meaningful set — a pair \((\alpha_i,\alpha_j)\). For a pair, the subproblem has a closed-form analytic solution (no inner solver needed). SMO repeatedly: (1) picks a pair that most violates the KKT conditions, (2) optimizes it exactly, (3) repeats until all KKT conditions hold within tolerance.

SMO’s genius is that the most expensive step in QP — solving a constrained subproblem — becomes a few lines of arithmetic for a pair. It uses little memory (compute kernel entries on demand, cache hot ones) and scales to tens of thousands of points. LIBSVM, the library behind scikit-learn’s SVC/SVR, is essentially a polished SMO with smart working-set selection and caching.

Large-scale linear SVMs

When the kernel is linear, you can keep \(\vw\) explicitly and avoid the Gram matrix entirely, giving (near) linear-time training:

  • LIBLINEAR uses dual or primal coordinate descent, handling millions of samples/features (ideal for text).

  • Pegasos performs stochastic subgradient descent on the primal, with run time essentially independent of dataset size.

  • SGDClassifier(loss="hinge") in scikit-learn is the mini-batch SGD route, streaming and online-friendly.

Rule of thumb: \(n\gtrsim10^5\) and you want a linear model \(\Rightarrow\) use LIBLINEAR/SGD, not kernel SVC.

Performance traps. (1) Using SVC (kernel) on huge data: training time explodes super-linearly — switch to LinearSVC or SGDClassifier. (2) Ignoring the cache: for kernel SVMs, a too-small kernel cache thrashes; raise cache_size. (3) Loose tolerance vs. speed: tightening tol too far wastes time for no accuracy gain. (4) Not shrinking: LIBSVM’s shrinking heuristic (dropping settled variables) speeds convergence — keep it on. (5) Forgetting that LinearSVC and SVC(kernel="linear") use different solvers and can give slightly different boundaries.

SMO’s decomposition idea — repeatedly solving tiny exactly-solvable subproblems — recurs across optimization in ML, from coordinate descent in Lasso to block updates in large-scale solvers. More importantly, stochastic subgradient descent (Pegasos) for the SVM primal is the same algorithm family that trains every modern neural network: sample a mini-batch, take a noisy gradient step, repeat. Studying Pegasos — with its \(1/t\) step size and convergence guarantees on a convex objective — is the cleanest possible introduction to why SGD works, before the non-convex complications of deep learning.

import numpy as np, time
from sklearn.svm import SVC, LinearSVC
from sklearn.datasets import make_classification
X, y = make_classification(n_samples=40000, n_features=50, random_state=0)
for name, model in [("kernel SVC(linear)", SVC(kernel="linear")),
                    ("LinearSVC", LinearSVC(max_iter=5000))]:
    t = time.time(); model.fit(X, y)
    print(f"{name:>20}: {time.time()-t:5.1f}s  acc={model.score(X, y):.3f}")
# LinearSVC is dramatically faster at this scale

Chapter summary

  • SVM training is convex (global optimum guaranteed); the choice of solver depends on kernel vs. linear and on \(n\).

  • The dual is a QP needing the \(O(n^2)\) Gram matrix — generic solvers don’t scale.

  • SMO optimizes one pair of multipliers at a time in closed form; it powers LIBSVM (scikit-learn’s SVC).

  • For large linear SVMs, use LIBLINEAR (coordinate descent) or Pegasos/SGD (stochastic subgradient).

  • Match solver to scale; Pegasos/SGD on the convex SVM is the cleanest lens on the SGD that trains neural nets.