Scaling Up SVM for Large Data Sets

The Problem

The standard SVM solves a quadratic programming (QP) problem whose (dual) size is proportional to the number of training tuples $n$. The final classifier depends only on the support vectors, but finding them costs up to O(n²)–O(n³) in time and O(n²) in memory (the full kernel matrix). For large data sets (millions of tuples) that makes straightforward SVM training impractically slow.

Why can it be made scalable?

SVMs satisfy the KKT (Karush–Kuhn–Tucker) optimality conditions, and the solution is captured entirely by the support vectors; most training points do not matter. If we can isolate the support vectors without solving the full QP, training can be made near-linear. All scalable methods exploit this sparsity.

---

Methods for Scalable SVM

1. Chunking (Vapnik).
Never hold the full set in memory: keep a small working set ("chunk"), solve the QP on it, discard the non-support vectors, and bring in the tuples that most violate the KKT conditions from the remaining data. Repeat until all tuples satisfy KKT. Memory drops from O(n^2) to O(chunk^2).

2. Decomposition methods (Osuna).
At each iteration, optimise only a fixed-size sub-problem (a small subset of the variables) while keeping the others fixed at their previous values. The subset is chosen to contain the variables that most violate KKT, and convergence is guaranteed because the objective strictly decreases. This is the framework underlying SVMlight.

3. Sequential Minimal Optimization (SMO).
A special case of decomposition that optimises exactly two Lagrange multipliers per step using a closed-form analytic update — so no inner QP solver is needed. Memory use is minimal and each step is cheap; implemented in libSVM, it converges very quickly in practice (often near-linear). Working-set heuristics pick the most violating pair.

4. Active sampling / core-set methods.
Since only points near the boundary matter, first sample the likely support vectors (points closest to the current separating surface), train a preliminary SVM, then feed back the misclassified / boundary points. Compact core sets (e.g., core-set SVM, RSVM — Reduced SVM) can be built with a guaranteed O(1/ε²) size for a target accuracy ε.

5. Incremental / online learning.
Add tuples one (or a block) at a time: the KKT conditions indicate exactly which existing support vectors must change, so only a local update is needed. This suits streaming or very large data sets and data that grows over time.

6. Parallel and distributed implementations.

• Cascade SVM — split the data across processors; each trains its own SVM; support-vector sets are merged pairwise and retrained until only one compact set remains.
• MapReduce / Spark approaches — map: train local SVMs on partitions; reduce: combine their support-vector sets; iterate until convergence.
• Kernel approximation — use low-rank approximations (Nyström) or random Fourier feature maps so that a simple linear SVM can be trained on the lifted feature space, dramatically speeding up training.

---

Summary Table

Method	Key idea	Efficiency gain
Chunking	solve QP on small working subset	memory reduced to O(k²)
Decomposition	optimise a small subset, fix rest	avoids solving full QP
SMO	exact 2-variable analytic updates	no QP solver, very fast
Core-set / active sampling	train only on boundary candidates	compact O(1/ε) core set
Incremental	sequential KKT updates	streaming-friendly
Cascade / parallel	pool local support vectors across machines	horizontal scaling

Conclusion: because only the support vectors (boundary points) determine an SVM, scalable algorithms identify them by repeatedly concentrating on the KKT-violating points (chunking, decomposition, SMO) or by data-level strategies (sampling, core sets, incremental, parallel) — avoiding the O(n^3) full-QP solve and making SVM practical for large data sets.