Representer theorem

1.1 Motivation and historical context

The representer theorem emerged from the study of interpolation and approximation in Hilbert spaces. In the 1970s, Grace Wahba and others working on spline smoothing observed that the minimizer of a regularized least‑squares problem over a certain function space could be expressed as a linear combination of basis functions centered at the data points. This principle was later formalized as the representer theorem for reproducing kernel Hilbert spaces (RKHS) by Kimeldorf and Wahba (1971). The theorem provides a crucial link between infinite‑dimensional function estimation and finite‑dimensional linear algebra, making kernel methods computationally tractable. It has since become a cornerstone of modern machine learning, enabling the practical use of support vector machines, kernel ridge regression, and Gaussian process models.

1.2 Formal definition of the problem setting

1.2.1 Reproducing kernel Hilbert space (RKHS)

A reproducing kernel Hilbert space \(\mathcal{H}\) over a set \(\mathcal{X}\) is a Hilbert space of functions \(f : \mathcal{X} \to \mathbb{R}\) such that the evaluation functional \(\delta_x : f \mapsto f(x)\) is continuous for every \(x \in \mathcal{X}\). By the Riesz representation theorem, there exists a unique kernel function \(k : \mathcal{X} \times \mathcal{X} \to \mathbb{R}\) with the reproducing property: for all \(x \in \mathcal{X}\) and \(f \in \mathcal{H}\), \(f(x) = \langle f, k(x, \cdot) \rangle_{\mathcal{H}}\). The function \(k(x, \cdot)\) is called the representer of evaluation at \(x\). Common kernels include the Gaussian radial basis function kernel and the polynomial kernel.

1.2.2 Regularized empirical risk functional

Given a training set \(\{(x_i, y_i)\}_{i=1}^n\) with \(x_i \in \mathcal{X}\) and \(y_i \in \mathbb{R}\), we consider the regularized empirical risk functional

\[

\]

where \(L\) is a loss function (e.g., squared error or hinge loss), \(\lambda > 0\) is a regularization parameter, and \(\Omega : [0, \infty) \to \mathbb{R}\) is a strictly increasing function. The goal is to minimize \(J(f)\) over \(f \in \mathcal{H}\).

2 Statement of the representer theorem

2.1 Classical version for squared norm regularization

\[ f^*(x) = \sum_{i=1}^n \alpha_i k(x_i, x), \]

for some coefficients \(\alpha_i \in \mathbb{R}\). This finite representation holds even though \(\mathcal{H}\) may be infinite‑dimensional. The coefficients are found by solving a finite‑dimensional optimization problem involving the kernel matrix \(K_{ij} = k(x_i, x_j)\).

2.2 Generalized versions

2.2.1 Non‑smooth regularizers (e.g., L1)

2.2.2 Multiple kernels and vector‑valued functions

The theorem extends to settings with multiple kernels (e.g., multiple kernel learning) and to vector‑valued functions. In the multi‑output case, the solution is expressed as a linear combination of matrix‑valued kernels evaluated at the training points. This generalization is important for multi‑task learning and structured prediction.

3 Proof outline

3.1 Orthogonal decomposition argument

3.2 Optimization over the finite‑dimensional subspace

Because the optimal \(f^*\) lies in \(\mathcal{H}_0\), it can be written as \(f^* = \sum_{i=1}^n \alpha_i k(x_i, \cdot)\). Substituting this into \(J(f)\) yields a finite‑dimensional problem in \(\alpha = (\alpha_1,\dots,\alpha_n)\):

\[ \tilde{J}(\alpha) = \frac{1}{n} \sum_{i=1}^n L\!\left(y_i, \sum_{j=1}^n \alpha_j k(x_j, x_i)\right) + \lambda \Omega\!\left(\sqrt{\alpha^\top K \alpha}\right), \]

where \(K\) is the kernel matrix. This problem can be solved using standard optimization techniques (e.g., convex solvers for SVMs or closed‑form linear algebra for ridge regression).

4 Applications

4.1 Support vector machines (SVM)

In binary classification with the hinge loss, the representer theorem guarantees that the maximum‑margin hyperplane in an RKHS can be written as \(f(x) = \sum_{i=1}^n \alpha_i y_i k(x_i, x) + b\), where many \(\alpha_i\) are zero (support vectors). This sparsity is a direct consequence of the hinge loss and the form of regularization.

4.2 Kernel ridge regression

Using the squared loss and \(\Omega(t)=t^2\), the minimizer is \(f^*(x) = \sum_{i=1}^n \alpha_i k(x_i, x)\) with \(\alpha = (K + n\lambda I)^{-1} y\). This is the kernelized version of ridge regression, also known as least‑squares support vector regression.

4.3 Gaussian process regression (connection)

In Gaussian process (GP) regression, the posterior mean is given by \(m(x) = k(x, X)^\top (K + \sigma^2 I)^{-1} y\), which is exactly the kernel ridge regression solution. The representer theorem provides a frequentist justification: the GP posterior mean minimizes the regularized empirical risk under a squared‑error loss, assuming the GP prior corresponds to the RKHS norm.

4.4 Nonparametric estimation and spline models

Smoothing splines are a special case of kernel methods with a polynomial or thin‑plate spline kernel. The representer theorem explains why the optimal smoothing spline can be expressed as a linear combination of basis functions centered at the data points, leading to efficient computation.

5 Extensions and variants

5.1 Representer theorem for proximal operators

For certain non‑differentiable regularizers, the proximal operator of the RKHS norm can be characterized via the representer theorem. This is used in iterative optimization algorithms (e.g., proximal gradient methods) for kernel‑regularized problems with convex losses.

5.2 Infinite‑dimensional outputs and operator‑valued kernels

When the output space is infinite‑dimensional (e.g., function‑valued regression), the representer theorem generalizes to operator‑valued kernels. The solution takes the form \(f(x) = \sum_{i=1}^n K(x_i, x) \cdot \mathbf{c}_i\), where \(K(x_i, x)\) is an operator acting on vectors \(\mathbf{c}_i\) in the output space.

5.3 Deep kernel learning and neural tangent kernels

In deep kernel learning, the kernel is parameterized by a deep neural network, and the representer theorem continues to hold for the resulting RKHS. The neural tangent kernel (NTK) describes the behavior of infinitely wide neural networks under gradient descent; the NTK’s RKHS admits a representer theorem, linking neural network training to kernel methods.

6 Limitations and considerations

6.1 Dependence on the choice of kernel

The representer theorem does not prescribe how to choose the kernel. The quality of the solution depends critically on whether the RKHS induced by the kernel contains the true underlying function. Poor kernel choice can lead to underfitting or overfitting.

6.2 Computational complexity for large datasets

The solution involves an \(n \times n\) kernel matrix, leading to \(O(n^3)\) time and \(O(n^2)\) memory costs for direct computation. This limits the applicability to datasets with a few tens of thousands of points, although approximations (e.g., Nyström method, random features) mitigate the issue.

6.3 Representer theorem in non‑Hilbert spaces

The theorem relies on the Hilbert space structure (inner product, orthogonality). In Banach spaces or more general metric spaces, the property that the minimizer lies in the span of the data does not generally hold. Extensions exist for certain reproducing kernel Banach spaces, but they lack the simplicity and algorithmic convenience of the Hilbert space case.