Why Regularization Is a Price List

The representer theorem told us what the optimal weight looks like: a sum of kernel bumps centered on the data, $f(x) = \sum_i \alpha_i\, k(x_i, x)$. The weight lives in the data’s span, right next to the points, built from them. That was the payoff of Where Does a Weight Live? and the engine behind The MLP Block Is a Representer Theorem.

But the theorem left one question unanswered. It says the optimum takes that form; it does not say why that optimum would generalize to new data. A sum over the training points could perfectly memorize them and fail on everything else. Something must be holding the sum back, and whatever it is, it must be the thing that makes a kernel machine more than an interpolation engine.

The worry you should already feel#

Here is the problem in miniature. You have six points, two classes, and a Gaussian kernel. The representer theorem guarantees that the best separator is $\sum_i \alpha_i\, k(x_i, x)$. But there are many such sums. One set of $\alpha_i$ fits the six training points perfectly and wiggles ferociously between them. Another set fits them loosely and draws a smooth boundary. Both are representer-theorem weights. Both live in the data’s span. The theorem does not choose between them.

So what chooses? Whatever it is, it cannot be read off the representer form, because both candidates wear that form perfectly. It has to be something that can look at two sums over the same six points and call one of them expensive.

The bill you pay for a weight#

“Expensive” turns out to be the exact word. What Can a Weight Be? ended on a price list: every kernel splits into modes $\phi_j$ priced by eigenvalues $\lambda_j$, and a weight $f = \sum_j c_j \phi_j$ pays $c_j^2/\lambda_j$ for each mode it uses, so the smooth modes are cheap and the wiggly ones are ruinous. But that list prices a weight one mode at a time, and the representer theorem hands us a weight written one point at a time. Before the price list can judge our two six-point sums, the two currencies have to be exchanged.

Here is the exchange. A kernel bump $k(x_i, \cdot)$ does not walk into the store empty-handed. It arrives already holding a fixed shopping list of modes,

a little of every mode, in proportions pinned down by where $x_i$ sits. Choosing the $\alpha_i$ is choosing how many copies of each point’s list to buy. Buy them in the combination $f = \sum_i \alpha_i\, k(x_i, \cdot)$ and the purchases add up mode by mode, $c_j = \lambda_j \sum_i \alpha_i\, \phi_j(x_i)$, and the total bill collapses into a formula you can evaluate with nothing but the kernel:

That exchange rate, $\alpha$‘s over points on one side, $c$‘s over modes on the other, the same weight priced in both currencies, is the one new idea this post runs on. It answers the miniature immediately: the ferocious fit needs large amounts of the high-frequency modes, the expensive lines on every list, so its bill is enormous; the smooth fit buys mostly cheap modes and stays affordable.

Regularization is the act of capping that bill. Instead of minimizing the training error alone, you minimize

and $\lambda$ is how tight the budget is. A large $\lambda$ says “you can only use the cheap modes,” which forces smoothness. A small $\lambda$ says “spend what you like,” which lets the weight wiggle. The knob is not mysterious. It is literally the spending limit.

Turn the knob and watch#

So can you watch the budget choose between the ferocious fit and the smooth one? Below are the six points from the miniature, one Gaussian kernel, and a slider for $\lambda$. Drag it from left to right and watch three things change simultaneously: the decision boundary smooths, the $\alpha_i$ coefficients shrink toward zero, and the effective number of prototypes drops. The weight is the same sum over the same points at every value of $\lambda$; only the budget changes.

How the eigenvalues decide everything#

The price list is not equally strict in every direction. The eigenvalues of the kernel determine which modes get cut first, and that is where the real structure lives. A Gaussian kernel has eigenvalues that fall off faster than any polynomial, so the high-frequency modes are not merely expensive, they are astronomically expensive. A Sobolev kernel has eigenvalues that fall off like a polynomial, so the high modes are expensive but not impossible. The same regularization strength kills different modes in different kernels.

How many modes actually survive a given budget? On the left below is the eigenvalue spectrum: bars whose height is $\lambda_k$, the price of each mode. On the right is a gauge showing the effective dimension, $d_{\text{eff}} = \sum_k \lambda_k / (\lambda_k + \lambda)$, the number of modes that survive the budget. As you drag $\lambda$, the gauge moves: tight budget, low effective dimension; loose budget, high effective dimension.

If the budget is one number, why do some points survive it?#

But a puzzle hides in that gauge. The budget is a single cap on the whole bill, one number, and yet when you solve for the $\alpha_i$ under it, the six points come out wildly unequal: a few carry large coefficients and hold the boundary in place, the rest end up contributing almost nothing. Press play below and watch the solved boundary reassemble one prototype at a time, largest coefficient first. The first few bumps carve the boundary; the last ones barely shift it.

The shopping lists explain the inequality. Every bump carries the full catalog of modes, but in proportions fixed by where its point sits. A point deep in a crowd of same-class neighbors holds nearly the same list they do, so the cheapest way to buy the boundary is one generous copy of the shared list and token amounts of the duplicates. A point that alone covers a stretch of the boundary holds the only affordable route to the modes needed there, and the solver has no choice but to buy its list in bulk. Large $\alpha_i$ marks a list that cannot be substituted; small $\alpha_i$ marks a redundant one. The budget is one number, but it is spent through six different lists, and the spending concentrates where the lists are irreplaceable.

One note before the last panel, because the phrase “support vector” usually belongs to a different machine. The solver behind every panel here is kernel ridge: it solves $(K + \lambda I)\,\alpha = y$, and unlike a hinge-loss SVM it never sets a coefficient exactly to zero. Tightening $\lambda$ shrinks every $\alpha_i$ smoothly, just at very different rates, so what emerges is not a hard roster of survivors but a graded hierarchy in which a few coefficients dominate and the rest fade toward irrelevance. The dashed threshold in the bar chart below is a reading aid, not a mechanism: a bar above it still carries the boundary, a bar below it has shrunk until deleting its point barely moves the surface. Drag $\lambda$ from loose to tight and the bars all sink together, but not at the same rate: the redundant points slip under the line first, one by one, until only the few bumps the boundary cannot do without still show above it.

But why would smooth generalize?#

The phrase “regularization makes things smooth” is true but shallow. The real story is about capacity. The effective dimension $d_{\text{eff}} = \sum_k \lambda_k / (\lambda_k + \lambda)$ counts how many independent directions the weight is allowed to use. A weight with small $d_{\text{eff}}$ lives in a low-dimensional subspace of the full RKHS, and a low-dimensional subspace has less room to overfit. The bound is not hand-waving: Bartlett and Mendelson (2002) show that the Rademacher complexity of an RKHS ball of radius $R$ is $R \sqrt{d_{\text{eff}} / n}$, so the generalization gap shrinks as $d_{\text{eff}}$ drops.

That is why the knob works. Tightening $\lambda$ does not just smooth the boundary. It lowers the effective dimension, which lowers the complexity of the function class, which shrinks the gap between training and test error. The price list is not a metaphor for generalization. It is the mechanism.

And the Yat kernel, the one this series builds on, sits in a particular spot on that spectrum. Its eigenvalues decay exponentially, faster than Sobolev but slower than the Gaussian, so its effective dimension drops fast but not instantaneously. It is universal (can approximate any continuous target) and local (the kernel bump stays in input space), which means the modes it keeps are the ones that correspond to real, picture-able prototypes. The price list is steep enough to regularize, but the modes it lets through are the ones you can point at.

That is the whole answer to why a representer-theorem weight generalizes. It is not a free combination of the data. It is a combination the price list can afford, and regularization is how you set the budget. The eigenvalues decide which modes survive, the budget decides how many, and the effective dimension counts what is left. The weight is the data, recombined, and the price list is the reason that recombination works.

The representer theorem is Schölkopf, Herbrich and Smola (2001); the eigenvalue-price-list framing is the standard RKHS theory in Steinwart and Christmann (2008); the Rademacher complexity bound is from Bartlett and Mendelson (2002). The interactive panels run the real kernel-ridge solve in your browser. The conceptual predecessors are Where Does a Weight Live? and What Can a Weight Be?.