Representer theorem

Remarks

Proof idea: let $V$ be the span of $k(\cdot, x_1), \dots, k(\cdot, x_n)$ in the Hilbert space $H$, and write $f = f_V + f_\perp$ with $f_V \in V$ and $f_\perp \perp V$. By the reproducing property $f(x_i) = \langle f, k(\cdot, x_i) \rangle_H = f_V(x_i)$, so the first term only depends on $f_V$. Since $\norm{f}_H^2 = \norm{f_V}_H^2 + \norm{f_\perp}_H^2$ and $g$ is strictly increasing, any $f$ with $f_\perp \ne 0$ is beaten by $f_V$. If $g$ is only nondecreasing, the same argument shows that, if a minimiser exists, some minimiser has this form.

Example: kernel ridge regression minimises $\frac1n \sum_{i=1}^{n} (y_i - f(x_i))^2 + \lambda \norm{f}_H^2$ with $\lambda > 0$. By the theorem $f = \sum_i \alpha_i k(\cdot, x_i)$, and with the Gram matrix $K_{ij} = k(x_i, x_j)$ the problem becomes a quadratic problem in $\alpha \in \R^n$, solved by $\alpha = (K + n \lambda I)^{-1} y$.

Without the penalty $g(\norm{f}_H)$ the conclusion fails: if $H$ is infinite-dimensional, adding to a minimiser any nonzero $f_\perp \perp V$ gives another minimiser of $c(f(x_1), \dots, f(x_n))$ that is not in $V$.

Going deeper

For a student

The theorem is what makes kernel methods computable: support vector machines, kernel ridge regression and smoothing splines all reduce to finite-dimensional problems in $\alpha$ involving only the Gram matrix $K$. It is a form of regularized empirical risk minimization in a reproducing kernel Hilbert space, where the penalty $\norm{f}_H$ controls smoothness. The "kernel trick" follows: the solution can be evaluated at a new point $x$ as $\sum_i \alpha_i k(x, x_i)$ without ever working with elements of $H$ explicitly. Versions of the theorem allow an additional unpenalised finite-dimensional part, such as a constant term.