\(\newcommand{\ci}{\perp\!\!\!\perp}\) \(\newcommand{\cA}{\mathcal{A}}\) \(\newcommand{\cB}{\mathcal{B}}\) \(\newcommand{\cC}{\mathcal{C}}\) \(\newcommand{\cD}{\mathcal{D}}\) \(\newcommand{\cE}{\mathcal{E}}\) \(\newcommand{\cF}{\mathcal{F}}\) \(\newcommand{\cG}{\mathcal{G}}\) \(\newcommand{\cH}{\mathcal{H}}\) \(\newcommand{\cI}{\mathcal{I}}\) \(\newcommand{\cJ}{\mathcal{J}}\) \(\newcommand{\cK}{\mathcal{K}}\) \(\newcommand{\cL}{\mathcal{L}}\) \(\newcommand{\cM}{\mathcal{M}}\) \(\newcommand{\cN}{\mathcal{N}}\) \(\newcommand{\cO}{\mathcal{O}}\) \(\newcommand{\cP}{\mathcal{P}}\) \(\newcommand{\cQ}{\mathcal{Q}}\) \(\newcommand{\cR}{\mathcal{R}}\) \(\newcommand{\cS}{\mathcal{S}}\) \(\newcommand{\cT}{\mathcal{T}}\) \(\newcommand{\cU}{\mathcal{U}}\) \(\newcommand{\cV}{\mathcal{V}}\) \(\newcommand{\cW}{\mathcal{W}}\) \(\newcommand{\cX}{\mathcal{X}}\) \(\newcommand{\cY}{\mathcal{Y}}\) \(\newcommand{\cZ}{\mathcal{Z}}\) \(\newcommand{\bA}{\mathbf{A}}\) \(\newcommand{\bB}{\mathbf{B}}\) \(\newcommand{\bC}{\mathbf{C}}\) \(\newcommand{\bD}{\mathbf{D}}\) \(\newcommand{\bE}{\mathbf{E}}\) \(\newcommand{\bF}{\mathbf{F}}\) \(\newcommand{\bG}{\mathbf{G}}\) \(\newcommand{\bH}{\mathbf{H}}\) \(\newcommand{\bI}{\mathbf{I}}\) \(\newcommand{\bJ}{\mathbf{J}}\) \(\newcommand{\bK}{\mathbf{K}}\) \(\newcommand{\bL}{\mathbf{L}}\) \(\newcommand{\bM}{\mathbf{M}}\) \(\newcommand{\bN}{\mathbf{N}}\) \(\newcommand{\bO}{\mathbf{O}}\) \(\newcommand{\bP}{\mathbf{P}}\) \(\newcommand{\bQ}{\mathbf{Q}}\) \(\newcommand{\bR}{\mathbf{R}}\) \(\newcommand{\bS}{\mathbf{S}}\) \(\newcommand{\bT}{\mathbf{T}}\) \(\newcommand{\bU}{\mathbf{U}}\) \(\newcommand{\bV}{\mathbf{V}}\) \(\newcommand{\bW}{\mathbf{W}}\) \(\newcommand{\bX}{\mathbf{X}}\) \(\newcommand{\bY}{\mathbf{Y}}\) \(\newcommand{\bZ}{\mathbf{Z}}\) \(\newcommand{\ba}{\mathbf{a}}\) \(\newcommand{\bb}{\mathbf{b}}\) \(\newcommand{\bc}{\mathbf{c}}\) \(\newcommand{\bd}{\mathbf{d}}\) \(\newcommand{\be}{\mathbf{e}}\) \(\newcommand{\bg}{\mathbf{g}}\) \(\newcommand{\bh}{\mathbf{h}}\) \(\newcommand{\bi}{\mathbf{i}}\) \(\newcommand{\bj}{\mathbf{j}}\) \(\newcommand{\bk}{\mathbf{k}}\) \(\newcommand{\bl}{\mathbf{l}}\) \(\newcommand{\bm}{\mathbf{m}}\) \(\newcommand{\bn}{\mathbf{n}}\) \(\newcommand{\bo}{\mathbf{o}}\) \(\newcommand{\bp}{\mathbf{p}}\) \(\newcommand{\bq}{\mathbf{q}}\) \(\newcommand{\br}{\mathbf{r}}\) \(\newcommand{\bs}{\mathbf{s}}\) \(\newcommand{\bt}{\mathbf{t}}\) \(\newcommand{\bu}{\mathbf{u}}\) \(\newcommand{\bv}{\mathbf{v}}\) \(\newcommand{\bw}{\mathbf{w}}\) \(\newcommand{\bx}{\mathbf{x}}\) \(\newcommand{\by}{\mathbf{y}}\) \(\newcommand{\bz}{\mathbf{z}}\) \(\newcommand{\RR}{\mathbb{R}}\) \(\newcommand{\NN}{\mathbb{N}}\) \(\newcommand{\balpha}{\boldsymbol{\alpha}}\) \(\newcommand{\bbeta}{\boldsymbol{\beta}}\) \(\newcommand{\btheta}{\boldsymbol{\theta}}\) \(\newcommand{\hpi}{\widehat{\pi}}\) \(\newcommand{\bpi}{\boldsymbol{\pi}}\) \(\newcommand{\hbpi}{\widehat{\boldsymbol{\pi}}}\) \(\newcommand{\bxi}{\boldsymbol{\xi}}\) \(\newcommand{\bmu}{\boldsymbol{\mu}}\) \(\newcommand{\bepsilon}{\boldsymbol{\epsilon}}\) \(\newcommand{\bzero}{\mathbf{0}}\) \(\newcommand{\T}{\text{T}}\) \(\newcommand{\Trace}{\text{Trace}}\) \(\newcommand{\Cov}{\text{Cov}}\) \(\newcommand{\Var}{\text{Var}}\) \(\newcommand{\E}{\mathbb{E}}\) \(\newcommand{\Pr}{\text{Pr}}\) \(\newcommand{\pr}{\text{pr}}\) \(\newcommand{\pdf}{\text{pdf}}\) \(\newcommand{\P}{\text{P}}\) \(\newcommand{\p}{\text{p}}\) \(\newcommand{\One}{\mathbf{1}}\) \(\newcommand{\argmin}{\operatorname*{arg\,min}}\) \(\newcommand{\argmax}{\operatorname*{arg\,max}}\) \(\newcommand{\dtheta}{\frac{\partial}{\partial\theta} }\) \(\newcommand{\ptheta}{\nabla_\theta}\) \(\newcommand{\alert}[1]{\color{darkorange}{#1}}\) \(\newcommand{\alertr}[1]{\color{red}{#1}}\) \(\newcommand{\alertb}[1]{\color{blue}{#1}}\)

1 The Motivation

The Module 1 notes establish several important properties of an RKHS:

  • The Moore-Aronszajn theorem (Aronszajn 1950) established the one-to-one correspondence between positive-definite kernels and RKHSs. We also know how to construct the RKHS given a kernel function.
  • The kernel trick allows us to compute inner products in an RKHS without explicitly mapping data points to the high-dimensional feature space.
  • Mercer’s theorem, mentioned in Kernel Mean Embedding and Applications, provides an eigenfunction and eigenvalue expansion of a kernel under a specified reference measure and suitable regularity conditions. It does not apply to every positive-definite kernel without additional assumptions (Mercer 1909).

The connections among these ideas can be illustrated using the following figure:

With this understanding, we want to further discuss how to computationally use the RKHS structure in statistical learning problems. This is the goal of the Representer Theorem (Kimeldorf and Wahba 1970; Schölkopf et al. 2001), which states that the solution to a large class of optimization problems in an RKHS can be represented as a finite linear combination of kernel functions evaluated at the training data points. The smoothing-spline proof uses the same orthogonal-decomposition mechanism. Its roughness penalty is a seminorm with the unpenalized null space \(\operatorname{span}\{1,x\}\), so its exact representation also contains an unpenalized linear term. It is therefore a closely related generalized case rather than a literal special case of the theorem stated below. Kernel ridge regression is a direct special case. This result allows us to reduce infinite-dimensional optimization problems to finite-dimensional ones, making them computationally feasible.

2 The Representer Theorem

\(\cH\) is a very large space of functions. If we want to find \(f\) in \(\cH\) for an optimization problem, it is not clear how to complete that task computationally. Think about the second-order Sobolev space example in smoothing splines. It is impossible to exhaust all such functions. Luckily, we do not need to. This is ensured by the Representer Theorem, which states that only a finite-sample representation is needed.

The Representer Theorem

Let \(\cH\) be an RKHS with kernel \(K\), and consider \[ J(f) = \cL\big(\{(y_i,f(x_i))\}_{i=1}^n\big) + p\big(\|f\|_{\cH}^2\big), \qquad f\in\cH, \] where the loss depends on \(f\) only through its evaluations at the observed inputs. Assume that \(J\) attains its minimum.

If \(p:[0,\infty)\to\RR\) is nondecreasing, then at least one minimizer has the form \[ \widehat f(\cdot)=\sum_{i=1}^n\alpha_iK(\cdot,x_i). \] If \(p\) is strictly increasing, then every minimizer has this form.

The theorem is conditional on existence and does not guarantee that the minimizer is unique. Even when the minimizing function is unique, its coefficient vector may be nonunique if the kernel sections are linearly dependent.

The proof is quite simple. The logic is the same as the smoothing-spline proof. Let

\[ \cS=\operatorname{span}\{K(\cdot,x_1),\ldots,K(\cdot,x_n)\}. \]

Remember that these functions defined on the observed data form a finite-dimensional subspace \(\cS\) of \(\cH\). Since \(\cS\) is finite-dimensional, it is closed. The Hilbert-space projection theorem therefore gives the unique decomposition1

\[ f=s+h, \qquad s\in\cS,\quad h\in\cS^\perp, \]

where

\[ s(\cdot)=\sum_{i=1}^n\alpha_iK(\cdot,x_i). \]

Here the orthogonal complement of \(\cS\) is defined as

\[ \cS^\perp = \{h\in\cH:\langle h,g\rangle_{\cH}=0,\ \forall g\in\cS\}. \]

Now we can investigate what happens to the loss function and the penalty term in the optimization problem. For the loss function, we only care about the values of \(f\) at the observed inputs. Because \(h\) is orthogonal to every function in \(\cS\), the reproducing property gives

\[ h(x_j) = \langle h,K(\cdot,x_j)\rangle_{\cH} = 0 \]

for all \(j\). More explicitly,

\[\begin{align} f(x_j) &=\langle f,K(\cdot,x_j)\rangle_{\cH} \nonumber\\ &=\left\langle \sum_{i=1}^n\alpha_iK(\cdot,x_i)+h,\ K(\cdot,x_j)\right\rangle_{\cH} \nonumber\\ &=\sum_{i=1}^n\alpha_iK(x_i,x_j)+h(x_j) \nonumber\\ &=\sum_{i=1}^n\alpha_iK(x_i,x_j). \end{align}\]

This means that the finite-sample representation already captures all the information about \(f\) used by the loss. Hence, the loss is the same if we use \(s\) without \(h\).

For the penalty term,

\[\begin{align} \|f\|_{\cH}^2 &=\left\|\sum_{i=1}^n\alpha_iK(\cdot,x_i)+h\right\|_{\cH}^2 \nonumber\\ &=\left\|\sum_{i=1}^n\alpha_iK(\cdot,x_i)\right\|_{\cH}^2 +\|h\|_{\cH}^2 +2\sum_{i=1}^n\alpha_i\langle K(\cdot,x_i),h\rangle_{\cH} \nonumber\\ &=\left\|\sum_{i=1}^n\alpha_iK(\cdot,x_i)\right\|_{\cH}^2+\|h\|_{\cH}^2 \nonumber\\ &\geq\left\|\sum_{i=1}^n\alpha_iK(\cdot,x_i)\right\|_{\cH}^2. \end{align}\]

Since \(f(x_i)=s(x_i)\) for every \(i\), the two functions have the same loss. Since \(p\) is nondecreasing,

\[ J(s)\leq J(f). \]

Therefore, projecting any minimizer onto \(\cS\) produces a minimizer in \(\cS\). If \(p\) is strictly increasing and \(h\neq0\), then \(J(s)<J(f)\), contradicting the optimality of \(f\). Thus every minimizer lies in \(\cS\) under strict monotonicity.

3 Notes on Application

The main computational implication of the Representer Theorem is that optimization problems covered by the theorem can be reduced to finite-dimensional problems involving the kernel matrix. For the common choice

\[ p(t)=\lambda t,\qquad \lambda>0, \]

define

\[ \balpha=(\alpha_1,\ldots,\alpha_n)^\T, \qquad \bK=\big(K(x_i,x_j)\big)_{i,j=1}^n. \]

The finite-dimensional problem is

\[ \widehat{\balpha} \in \underset{\balpha\in\RR^n}{\arg\min} \left\{ \cL\left( \left\{ \left(y_i,\sum_{j=1}^n\alpha_jK(x_i,x_j)\right) \right\}_{i=1}^n \right) + \lambda\balpha^\T\bK\balpha \right\}. \]

Here,

\[ \left\| \sum_{i=1}^n\alpha_iK(\cdot,x_i) \right\|_{\cH}^2 = \balpha^\T\bK\balpha. \]

Typically, these coefficients can be obtained using standard optimization techniques. Penalizing the RKHS norm controls complexity in the kernel-induced geometry described previously. Smoothness in the original input coordinates requires corresponding regularity of the kernel.

The next lecture combines this finite representation with the \(\epsilon\)-insensitive loss. Unlike kernel ridge regression, support vector regression does not have the same closed-form solution, but the optimization problem remains finite-dimensional and convex.

Aronszajn, Nachman. 1950. “Theory of Reproducing Kernels.” Transactions of the American Mathematical Society 68 (3): 337–404.
Kimeldorf, George S, and Grace Wahba. 1970. “A Correspondence Between Bayesian Estimation on Stochastic Processes and Smoothing by Splines.” The Annals of Mathematical Statistics 41 (2): 495–502.
Mercer, James. 1909. “Xvi. Functions of Positive and Negative Type, and Their Connection the Theory of Integral Equations.” Philosophical Transactions of the Royal Society of London. Series A, Containing Papers of a Mathematical or Physical Character 209 (441-458): 415–46.
Schölkopf, Bernhard, Ralf Herbrich, and Alex J. Smola. 2001. “A Generalized Representer Theorem.” Computational Learning Theory, 416–26. https://doi.org/10.1007/3-540-44581-1_27.

  1. The projection \(s\) is unique, although its coefficient vector may not be unique when the kernel matrix is singular. No full-rank assumption is needed. For the linear kernel, \(\bK=\bX\bX^\T\) and \[ \operatorname{rank}(\bK) = \operatorname{rank}(\bX) \leq \min(n,p). \] For distinct observed inputs, the Gaussian kernel matrix is strictly positive-definite.↩︎