Representer theorem

Theorem

• Let $\mathcal{X}$ be a nonempty set, $\mathcal{K}$ a positive-definite real-valued kernel on $\mathcal{X}\times \mathcal{X}$ with corresponding reproducing kernel Hilbert space $H_k$, and let $R:H_k\to \mathbb{R}$ be a differentiable regularization function. Then given a training sample $(x_1,y_1),\dots ,(x_n,y_n)\in \mathcal{X}\times \mathbb{R}$ and an arbitrary error function $E:(\mathcal{X}\times {\mathbb{R}}^2{)}^m\to \mathbb{R}\cup \{\infty \}$, a minimizer $f^{\ast }=\underset{f\in H_k}{\mathrm{argmin}}\left\{E\left((x_1,y_1,f(x_1)),\dots ,(x_n,y_n,f(x_n))\right)+R(f)\right\}$ of the regularized empirical risk admits a representation of the form $f^{\ast }(\cdot )={\sum }_{i=1}^n{\alpha }_{i}k(\cdot ,x_i),$ Why it’s cool
• Representer theorems are useful from a practical standpoint because they dramatically simplify the regularized ERM problem.
  • In most interesting applications, the search domain $H_k$ for the minimization will be an infinite-dimensional subspace of $L_2(X)$ and therefore the search (as written) does not admit implementation on finite-memory and finite-precision computers.
  • In contrast, the representation of $f^{\ast }(\cdot )$ afforded by a representer theorem reduces the original (infinite-dimensional) minimization problem to a search for the optimal $n$-dimensional vector of coefficients $\alpha$; it can then be obtained by applying any standard function minimization algorithm.