Your kernel SVM has trained for hours on 50,000 rows — why, and what would you change?

## Where the hours go Training a kernel SVM means solving a convex quadratic program in the dual, which has **one variable per training row** and a quadratic term built from the kernel matrix `K`, where `K[i][j]` is the kernel value between rows `i` and `j`. That matrix is `n` by `n`. At `n = 50,000` that is 2,500,000,000 entries — around 20 GB in double precision. No solver materialises it. Real implementations use decomposition: they optimise a small working set of variables at a time (Sequential Minimal Optimization takes this to the extreme with two at a time), holding a bounded cache of recently used kernel columns and recomputing the rest on demand. The consequence is that the observed cost has two components: - **Algorithmic**: the number of solver iterations grows with `n`, and each iteration touches `O(n)` kernel entries, giving empirical scaling between `n^2` and `n^3` depending on the problem, the kernel and how much regularisation is applied. - **Cache behaviour**: once the working set stops fitting the kernel cache, columns are recomputed over and over. This is why the wall-clock curve often bends upward much more sharply than the theoretical one at a specific dataset size — you crossed the cache. So the honest sanity check is arithmetic, not intuition. If 10,000 rows took four minutes and cost grows quadratically, 50,000 rows is 25 times that — nearly two hours; if it is closer to cubic, it is a day. Nothing is broken. The algorithm simply does not scale in rows. ## The second bill: prediction A kernel SVM's prediction is a weighted sum of kernel evaluations against its **support vectors**, which are stored training rows. On noisy problems the number of support vectors tends to grow roughly linearly with the training set size, so a bigger training set gives you a slower model to serve as well as a slower one to train. Heavier regularisation (a smaller `C`) admits more margin violations and therefore generally *more* support vectors, making inference slower; a very large `C` tends to make the quadratic program harder to converge, making training slower. Neither direction is free. And if the model is one arm of a multiclass decomposition, every one of those pairwise models carries its own support-vector set. ## What to change, cheapest first **1. Loosen the solver, enlarge the cache.** Tightening convergence beyond what the decision boundary needs buys nothing. A looser stopping tolerance and a kernel cache sized to the machine's memory are configuration changes that often halve the time with no measurable accuracy cost. **2. Use fewer rows on purpose.** Because cost is superlinear, halving the data cuts training time four- to eight-fold. Train on a stratified sample at several sizes — 5,000, 10,000, 20,000 — and look at whether held-out accuracy has flattened. Very often it has, and the remaining rows are buying nothing but hours. Deduplicating near-identical rows has the same effect for free. **3. Give up the kernel.** If the features are high-dimensional or sparse — text, one-hot encodings — a linear max-margin model is frequently as accurate as an RBF kernel, and specialised primal solvers for the linear case scale roughly linearly in the number of non-zero feature values. This is usually the single largest win available. **4. Approximate the kernel explicitly.** If the non-linearity is genuinely needed, map the data into an explicit finite-dimensional feature space whose inner products approximate the kernel, then fit the fast linear model there. The Nyström method builds such a map from a sampled subset of rows; random Fourier features build one by sampling frequencies to approximate a shift-invariant kernel such as the RBF. Both convert an `n`-by-`n` problem into an `n`-by-`d` one with `d` chosen by you, restoring linear-in-rows behaviour at some accuracy cost. **5. Reduce the number of hyperparameter fits.** A grid search multiplies every one of these costs. Search on a subsample and refit only the winner on the full data, rather than searching at full size. ## The thing not to say "Add more cores." The dual optimisation is sequential in nature and does not parallelise cleanly across the working set — the parallelism you can get is mostly inside the kernel evaluations. Throwing hardware at a superlinear algorithm buys a constant factor while the data keeps growing; the fixes above change the exponent. ## The senior framing The useful answer is not a trick but a decision: measure the accuracy curve against training-set size first. If accuracy plateaued at 10,000 rows, the whole problem was self-inflicted. If it has not plateaued, then the model class that needs 500,000 rows to be right is not the model class whose training cost is quadratic in rows, and you should say so.