One Kernel, Fitted Twice

Kernel methods once had the thing everyone now says they want. A support vector machine came with a margin you could bound, a representer theorem that told you the answer was a weighted sum over your actual data, and attribution that was not a saliency heuristic but the arithmetic of the prediction itself. Then the field walked away from all of it, almost overnight, for one reason. To fit an exact kernel machine you have to solve a linear system over an n by n matrix of pairwise similarities, and past a few thousand examples that solve is a wall. Deep networks never asked you to solve anything: you showed them a batch, took a gradient step, and moved on. The theory lost, and it lost on plumbing.

So here is a stubborn question. Is the solve actually part of the deal, or just the fitting procedure everyone happened to use? This post takes one kernel and fits it both ways: once by the classical exact solve, once by plain gradient descent. If the solve is essential, the two should differ. If it is plumbing, they should agree, and then gradient descent should keep going through every wall the solve dies at. That is a checkable claim, and everything below checks it.

The wall that emptied the field#

Why did one procedure kill an entire research program? Watch what an exact fit costs. A kernel machine’s whole vocabulary is pairwise similarity, so the classical fit starts by building the Gram matrix, the kernel evaluated between every pair of training points, and then solves against it: a linear system for kernel ridge regression, a quadratic program for an SVM. The table is $n^2$ numbers and the solve over it is $O(n^3)$ time, and neither exponent negotiates, because the method is defined over all pairs at once.

Two things break at that wall, and they are the two things deep learning is built on. You cannot minibatch, because the solve wants the whole matrix in memory at once; there is no notion of improving from a hundred examples at a time. And you cannot compose, because a solve is a closed procedure that returns one finished function, not a layer that can sit above an embedding, below a head, and train jointly with both. The escape the field actually took, random features (Rahimi and Recht, 2007), tells you how much the plumbing mattered: it replaces the kernel with a finite random sketch so that the problem becomes an ordinary linear model, which minibatches beautifully and gives up the object, its named centers, and its exactness to do so. Keep the kernel and eat the solve, or keep the gradient step and lose the kernel. That was the trade.

Put the kernel where the neuron was#

The trade is only forced if a kernel machine has to be fit by a solve. It does not. The Yat kernel is a finite, explicit, positive-definite kernel that can sit exactly where a neuron’s activation used to:

Each unit is a similarity to a center $w_u$ that lives in the same space as the data, so the center is a prototype you can read, and Bouhsine (2026) shows the construction is genuinely Mercer and universal: a real kernel with a real RKHS behind it. Stack $K$ of these units, read a scalar off the bank,

and you have a kernel machine whose centers and weights are ordinary trainable parameters. Run adam on them. No Gram matrix is ever built, no system is ever solved, and the object under the gradient steps is still a kernel expansion.

Which raises the question this whole post hangs on. The classical machine and this one carry the same kernel, but they are fitted by procedures that share nothing: one inverts a matrix over the data, the other never even sees two examples at once. Do they land on the same function, or does abandoning the solve abandon the machine?

The same machine, twice#

Below, both fits run in the page. The blue curve is the exact machine: every time the data changes, a real linear system $(\mathbf{K} + \lambda I)\,\alpha = y$ is factorized from scratch, and the timer shows what that fresh solve costs. The orange curve is the same kernel with a handful of prototype units, descending. Drag a data point and hold it: the blue fit snaps, because at eighty points a solve is nothing, and the orange fit flows after it. That asymmetry, re-factorize versus keep flowing, is the entire difference between the two fitting procedures, and the readout tracks how far apart the two functions actually are.

The browser demo is rigged in the solve’s favor, of course: at $n = 80$ a solve costs nothing. So take the same contest somewhere real. California Housing (Pace and Barry, 1997), 4,000 training districts, 8 covariates, from scripts/kernel_solve_wall.py on Kaggle. The exact machine picks its ridge and its bandwidth on validation and posts a test RMSE of 0.491 (in units of one standard deviation of price), from a 4,000-coefficient solve that took 0.7 seconds. The descended machine gets 64 prototypes, 640 parameters total, a learning rate picked on the same validation set, and three seeds. It posts 0.512 ± 0.002.

And here is the number the whole post was built to check: the correlation between the two machines’ predictions on held-out districts is r = 0.95. Not two methods of similar quality, the same function, reached once through a matrix factorization over all four thousand points and once through gradient steps that never saw more than 256 at a time. The ladder below is the capacity dial, with the sketch that replaced kernels for a decade sitting at the bottom as the control:

Sixteen prototypes are already enough to speak for four thousand solved coefficients. And read the last row carefully, because it is the fork in the road the field took: random features match the accuracy at this size, they always did, that is why the escape worked. What they do not match is the object. An RFF model is a linear fit over random noise directions; the descended machine’s sixteen centers are points in the data space, districts you can print and read, with signed weights that decompose every prediction. Same accuracy, and only one of them is still a kernel machine.

The wall, measured#

At four thousand points, then, the solve and the descent agree, and the solve is even fast. So why abandon it? Because of what the next factor of ten does. We timed the exact fit as the cohort grows, on the same box that ran everything else, and the panel below hands you the slider. Small cohorts you can solve right here in the page, and your own timings plot themselves next to the measured ones. Then keep sliding.

The measured points say it plainly. From 2,000 to 16,000 rows the data grew 8x and the CPU solve time grew 122x, 0.16 seconds to 19.6 seconds, the cubic doing exactly what a cubic does. The GPU hides the time for a while behind parallelism, a second flat up to 16,000, but it cannot hide the memory: the Gram is already 2 GB at 16,000 rows in double precision, and it clears 16 GB before 50,000. There is no clever scheduling around that, because the solve is defined over the whole table. Meanwhile one epoch of gradient descent over the same 16,000 rows costs 90 milliseconds, and its cost line through the whole plot is the boring straight one, because it holds 64 prototypes and one minibatch at a time, and nothing it holds ever scales with $n^2$.

Past the wall#

Everything so far was played on the solve’s home turf, cohorts small enough that it could show up. Covertype (Blackard and Dean, 1999) is 511,012 training rows of forest terrain, 54 covariates, and the question of whether a patch is lodgepole pine. The solve cannot enter this dataset whole: at 64,000 rows its Gram would be 33 GB. It gets subsamples, the biggest that fit, and it makes them count: 76.0% accuracy from 2,000 rows, 82.4% from 8,000, 85.5% from 16,000, at each size the stronger same-size fit, which it should be, holding every row as a center while the descended net compresses the same rows into 64 prototypes. At 16,000 rows the solve posts its best number. Then it hits the wall, and its column of the scoreboard goes silent, not worse, silent.

The descended machine does not stop. Same kernel, same bandwidth, minibatches of 512: at 16,000 rows it posts 79.5% with 64 prototypes, six points behind the same-size solve and paying that gap for a 250x smaller model. Then it does the thing the solve constitutionally cannot: it keeps eating data, 64,000 rows, 256,000, all 511,012. And because nothing in it scales with $n^2$, capacity is a free dial too, so the prototypes scale with the data: 256 of them reach 83.0% on the full set, and 1,024 reach 85.9% ± 0.1, past the best number the solve ever produced, from a model that summarizes half a million rows in a thousand readable centers. At matched size the solve is the stronger fit, and it does not matter, because sizes stopped being matched at 16,000: past the wall there is exactly one kernel machine still on the field, and it finishes above every score the other one left behind.

The third wall is the one that built deep learning#

Time and memory are the walls everyone names. The third one matters more. A solve takes the representation as given: hand it pixels and it compares pixels, forever, because the fit is a closed formula over the inputs it was handed. A network trains the representation under the head. If the kernel machine can be descended, it can sit on top of a trunk and shape the features it compares. If it must be solved, it cannot. Fashion-MNIST (Xiao et al., 2017), three fits, same kernel head:

Read the middle row first, because it kills the cheap version of composition: bolting a random trunk under the solve makes things worse than raw pixels. Features do not help because they exist; they help because they are trained, and training them requires gradients flowing through the head, which requires the head to be descendable. At matched data the end-to-end machine ties the raw-pixel solve. Then it scales to the rows the solve cannot hold, 55,000 of them, a 24 GB Gram if anyone tried to solve it, and takes four more points. The panel below shows what it bought with them: pick a garment and compare the representation the solve was stuck with against the features the trunk built for its kernel head.

What this buys, beyond the scoreboard#

The reason to want the kernel back was never accuracy, it was everything a kernel carries around it: attribution that is the arithmetic of the prediction, centers you can read and edit, capacity you can dial, a bounded response to strangers. None of that was used up in this post, and none of it was lost by descending instead of solving, because the object under the gradient steps really is a kernel expansion. The whole inheritance is demonstrated on a live clinical problem in the survival trial, where the same construction names the patients behind each risk score, deletes a cohort in closed form, and abstains on strangers, all after being trained like any network.

Start again from the wall, then. The field abandoned kernel machines because fitting one meant a cubic-time solve over a quadratic-memory table that could not minibatch and could not compose, and the escape it took gave up the object to get the plumbing. The experiments here say the dilemma was never real. One kernel, fitted both ways: the machines agree where both exist, and only one of them stops existing at 16,000 rows. You do not have to solve a kernel machine to have one. And once you stop solving it, the kernel is an ordinary layer, trained like everything else, still carrying every theorem it was worth keeping.

Every number in this post comes from scripts/kernel_solve_wall.py (JAX + Flax NNX, exact solves in float64 via Cholesky, gradient models LR-swept on validation with best-epoch selection, run on Kaggle), reshaped for the panels by scripts/export_solve_wall_viz.py. The in-page solver and descender run the same kernel live in your browser. The runnable companion builds both fitting procedures side by side.

@misc{bouhsine2026youdonthavetosolveakernelmachine,
  author       = {Bouhsine, Taha},
  title        = {One Kernel, Fitted Twice},
  year         = {2026},
  month        = {jul},
  howpublished = {\url{https://tahabouhsine.com/blog/you-dont-have-to-solve-a-kernel-machine/}},
  note         = {Blog post, Records of the !mmortal Data Scientist}
}