The Representer Theorem

A kernel method like kernel ridge regression is, technically, searching for the best function in an entire infinite-dimensional space of possible functions — every conceivable smooth curve is a candidate. That should be an intractable search: how do you optimize over infinitely many functions with a computer that only has finite memory? The representer theorem is the result that rescues this: it proves the optimal function, whatever infinite space it was theoretically drawn from, always turns out to be expressible using only a finite number of terms — one per training point. The search space collapses from infinite to exactly $n$ dimensions, where $n$ is the number of training examples, and that collapse is what makes every kernel method in practical use computationally solvable.

The analogy: mixing paint from only the colors on your palette

Imagine you're told to find the "best" color to paint a wall, searching over every conceivable color in existence — an infinite space. That sounds impossible to search directly. But suppose you're also told: whatever the optimal color turns out to be, it can always be produced as some mixture of exactly the pigments already sitting on your palette, nothing else. Suddenly the infinite search collapses to "how much of each pigment on my palette do I use" — a small, finite, entirely tractable optimization. The representer theorem is exactly this guarantee for kernel methods: whatever function class you're theoretically searching (infinite), the optimal answer is always a mixture of only the kernel functions centered at your $n$ training points — your "palette."

The statement

For a broad class of problems — minimize a loss on the training data plus a penalty on the function's complexity, measured by its norm $\|f\|_{\mathcal H}^2$ in the kernel's associated function space (its reproducing kernel Hilbert space) —

$$\hat f = \arg\min_{f \in \mathcal H} \sum_{i=1}^n L(y_i, f(x_i)) + \lambda \|f\|_{\mathcal H}^2$$

the representer theorem guarantees the minimizer always has the exact finite form

$$\hat f(x) = \sum_{i=1}^n \alpha_i \, k(x, x_i)$$

Plain English: no matter how rich or infinite-dimensional the space $\mathcal H$ theoretically is, the optimal fitted function is always just a weighted sum of "kernel similarity to each training point," with one weight $\alpha_i$ per training example — turning an infinite optimization problem into an $n$-dimensional one, solvable with ordinary linear algebra.

Worked example 1: kernel ridge regression's closed form

For kernel ridge regression specifically, the representer theorem means the fit reduces to solving one linear system for the $n$ coefficients $\alpha = (\alpha_1,\dots,\alpha_n)$:

$$\alpha = (K + \lambda I)^{-1} y$$

where $K$ is the $n\times n$ Gram matrix from Mercer's condition and $y$ is the vector of targets. With $n=3$ training points, $K=\begin{pmatrix}2&1&0\\1&3&1\\0&1&2\end{pmatrix}$, $\lambda=1$, $y=(4,6,2)^T$: solving $(K+I)\alpha = y$ (a $3\times3$ system, well within reach of ordinary matrix inversion) gives a specific $\alpha$ vector directly — never an infinite-dimensional object, exactly as the theorem promises, regardless of how complex the underlying kernel's implicit feature space is.

Worked example 2: prediction on a new point

Having solved for $\alpha = (1.1, 0.8, -0.3)$ from three training points $x_1,x_2,x_3$ using an RBF kernel with $\gamma=0.5$, predicting at a new point $x^*$ requires only evaluating the kernel between $x^*$ and each of the three training points and combining: $\hat f(x^*) = 1.1\,k(x^*,x_1) + 0.8\,k(x^*,x_2) - 0.3\,k(x^*,x_3)$. If $k(x^*,x_1)=0.9$, $k(x^*,x_2)=0.2$, $k(x^*,x_3)=0.05$: $\hat f(x^*) = 1.1(0.9)+0.8(0.2)-0.3(0.05) = 0.99+0.16-0.015 = 1.135$. Three multiplications and a sum — no matter how exotic the kernel's implicit feature space, prediction always costs exactly $n$ kernel evaluations, a direct consequence of the theorem's finite-sum form.

Every point in an infinite-dimensional space still has to be reached through finitely many building blocks once you fix a basis — the representer theorem is the statement that, for kernel methods, the training points themselves are always sufficient building blocks, however the underlying space is structured.

What this means in practice

The representer theorem is why the kernel trick and finite computation are compatible at all — without it, "optimize over an infinite-dimensional function space" would be a purely theoretical exercise, and kernel SVMs, kernel ridge regression, and Gaussian processes would not exist as practical algorithms. It's also the reason kernel methods scale with the number of training points rather than the number of features: the $\alpha$ vector has exactly $n$ entries and the Gram matrix is $n\times n$, regardless of whether the feature space the kernel implicitly represents is 10-dimensional or infinite-dimensional.