One Kernel Family, Fitted Two Ways

Kernel methods came with a geometry, a representer theorem, and optimization problems whose global solutions could often be characterized. Their dense textbook implementation also came with an $n$ by $n$ Gram matrix. That implementation becomes a wall long before the kernel idea does: iterative solvers, Nyström methods, random features, inducing points, and matrix-free products all attack different pieces of it. This post tests one more route, a compact expansion whose centers move under gradient descent.

The comparison needs one distinction before it starts. Kernel ridge fixes one RKHS and solves for coefficients at the training inputs. The compact Yat model uses the same kernel family but learns a smaller set of centers, so it searches a changing, nonconvex finite span. Agreement would show that the compressed model found a similar predictor on this task, not that the two optimization problems are identical. How close do they land, and what does the smaller model buy?

The wall that emptied the field#

Why did the dense textbook procedure become a wall? It builds the Gram matrix and factors it: $O(n^2)$ storage and $O(n^3)$ arithmetic for a fresh dense Cholesky solve. Those are costs of this implementation, not lower bounds for every kernel algorithm. Conjugate gradients can use matrix-vector products, Nyström and inducing-point methods replace the full span with a smaller one, and structured kernels can make products cheaper.

The dense factorization does not minibatch and does not fit naturally inside an ordinary end-to-end training loop. Kernel learning itself can be stochastic or compositional, but then the algorithm is no longer the one-shot dense solve measured here. Random features make that distinction visible: they approximate the kernel with a finite linear model that trains by minibatch. Learned inducing centers make a different approximation, retaining named input-space locations while giving up the fixed training-point span.

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 two models evaluate the same kernel formula but search different spans: all training sections for ridge, a compact learned set for descent. Do those different problems nevertheless land near one another on held-out inputs?

Two machines, one kernel family#

Below, both fits run in the page. The blue curve is kernel ridge: every data point is a fixed center and $(\mathbf K+\lambda I)\alpha=y$ is factorized from scratch. The orange curve uses a smaller bank whose coefficients and centers descend together. Drag a data point and hold it: the blue fit snaps to its unique ridge solution, while the orange nonconvex model follows its optimization path. The readout measures predictor disagreement rather than presuming equality.

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, run 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 their held-out predictions is r = 0.95. That is strong agreement, not equality. The RMSEs differ, the correlation leaves scale and offset errors invisible, and many functions can correlate at 0.95 on one finite test set. The result says a 64-center learned expansion captured most of this ridge predictor’s ordering on this task. The ladder below shows how that approximation changes with capacity:

Sixteen learned centers already recover most of the held-out ordering of the 4,000-center solution, while 64 close much of the RMSE gap. Random features match the compact model’s accuracy at a similar parameter count. The difference is representational: random features expose sampled spectral directions, while the learned expansion exposes input-space centers with signed contributions. Both are finite approximations to kernel computation; neither is the full ridge solution.

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 what happened to this dense Cholesky baseline. From 2,000 to 16,000 rows the data grew 8x and CPU factorization time grew 122x, from 0.16 seconds to 19.6 seconds. The explicit double-precision Gram is already 2 GB at 16,000 rows and clears 16 GB before 50,000. Matrix-free and approximate kernel methods can continue past that point, but they were not the baseline run here. The 64-center model holds one minibatch and one fixed-size bank, so its measured epoch cost grows roughly linearly with the rows it visits.

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 is integration into the training loop. The dense baseline here takes its representation as given. Differentiable solves and deep-kernel methods can learn a representation through a kernel objective, but they pay for repeated approximate solves or implicit differentiation. The learned-center layer takes the ordinary neural-network route: gradients pass through every kernel evaluation and into the trunk. Fashion-MNIST (Xiao et al., 2017), three fits, same kernel family:

Read the middle row first: a frozen random trunk makes this particular solve worse than raw pixels. At matched data the end-to-end learned-center model ties the raw-pixel solve, then reaches 90.1 percent when trained on 55,000 rows. This experiment does not isolate gradient flow from data volume in the final four-point gain, and it does not compare against a scalable deep-kernel solver. It establishes the narrower engineering result that this kernel layer participates in an ordinary minibatch training loop.

What this buys, beyond the scoreboard#

The compact model retains properties that follow directly from its finite expansion: named centers, signed per-center arithmetic, and fixed bank memory. It does not automatically retain every theorem about fixed-kernel ridge, since its centers and hyperparameters were optimized. The survival trial tests the properties that can be checked directly after that optimization: attribution sums, cohort edits, and raw-score abstention.

The dense solve and the learned-center layer are two different bargains. One gives the fixed-KRR optimum while its Gram matrix fits. The other gives up that optimum, learns a compact span, and enters the ordinary minibatch stack. Their 0.95 agreement shows that the compromise can be close on one task; their remaining error and the missing scalable-kernel baselines keep it from being an equivalence theorem.

Behind the tables: JAX and Flax NNX on Kaggle, dense solves in float64 via Cholesky, learned-center models LR-swept on validation and scored at their best validation epoch. The in-page models use the same kernel family as the runs. The runnable companion builds both procedures side by side.

@misc{bouhsine2026youdonthavetosolveakernelmachine,
  author       = {Bouhsine, Taha},
  title        = {One Kernel Family, Fitted Two Ways},
  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}
}