Kernels, RKHS and the Representer Theorem

Positive definite kernels, the reproducing property, a complete proof of the representer theorem, and kernel ridge regression.

Classical MLGraduate⏱ 1 day13 min readkernelrkhspositive definiterepresenter theoremkernel ridge

6 problems →

AssumesLinear Algebra for Machine Learning · Linear, Ridge and Lasso Regression

Positive definite kernels

DefinitionPositive definite kernel

$K:\Xcal\times\Xcal\to\R$ is a positive definite kernel if it is symmetric, $K(x,x')=K(x',x)$ , and for every finite $\{x_1,\dots,x_n\}\subseteq\Xcal$ the Gram matrix $\mathbf{K}_{ij}=K(x_i,x_j)$ is positive semidefinite.

TheoremPositive definite iff an inner product of features

$K$ is a positive definite kernel if and only if there is a Hilbert space $\Hcal$ and a map $\phi:\Xcal\to\Hcal$ with

K(x,x') = \ip{\phi(x)}{\phi(x')}_\Hcal \qquad\text{for all } x,x' .

TheoremConstruction of the RKHS (Moore–Aronszajn)

Let $K$ be a positive definite kernel on $\Xcal$ . There is a unique Hilbert space $\Hcal_K$ of real-valued functions on $\Xcal$ such that

$K(x,\cdot)\in\Hcal_K$ for every $x$ ;
$\operatorname{span}\{K(x,\cdot):x\in\Xcal\}$ is dense in $\Hcal_K$ ;
reproducing property: $f(x) = \ip{f}{K(x,\cdot)}_{\Hcal_K}$ for every $f\in\Hcal_K$ and $x\in\Xcal$ .

Key idea

The two halves of the reproducing property are worth separating. It says (a) evaluation at $x$ is a continuous linear functional on $\Hcal_K$ — which is the defining property of an RKHS and is false in, say, $L^2$ , where pointwise values are not even defined; and (b) that functional is represented by $K(x,\cdot)$ . Everything computational about kernels follows from (b), and everything about well-posedness of pointwise learning follows from (a).

The representer theorem

TheoremRepresenter theorem

Let $\Hcal_K$ be the RKHS of $K$ , let $\Omega:[0,\infty)\to\R$ be strictly increasing, and let $c:\R^n\to\R$ be arbitrary. Then any minimiser of

J(f) = c\big(f(x_1),\dots,f(x_n)\big) + \Omega\big(\norm{f}_{\Hcal_K}\big)

over $f\in\Hcal_K$ admits a representation

f^\star = \sum_{i=1}^n\alpha_iK(x_i,\cdot), \qquad \alpha\in\R^n .

Key idea

An infinite-dimensional optimisation problem has been reduced to $n$ real numbers, and the reduction is exact, not an approximation. Note precisely what made it work: the loss depends on $f$ only through its values at the $n$ data points, and the penalty is a strictly increasing function of the norm. Both hypotheses are essential — a penalty like $\norm{f'}_{L^2}$ that is not a function of $\norm{f}_{\Hcal_K}$ , or a loss involving $f$ at unseen points, breaks the conclusion.

Run it: Kernel ridge regressionThe fitted function of kernel ridge regression as bandwidth and regularisation vary.

PropositionKernel ridge regression in closed form

For the squared loss with regularisation $\lambda$ ,

\hat f = \argmin_{f\in\Hcal_K}\left\{\frac1n\sum_{i=1}^n\big(y_i-f(x_i)\big)^2 + \lambda\norm f_{\Hcal_K}^2\right\} = \sum_{i=1}^n\alpha_iK(x_i,\cdot), \qquad \alpha = (\mathbf{K}+n\lambda I)^{-1}y .

Building kernels

PropositionOperations preserving positive definiteness

Let $K_1,K_2$ be positive definite kernels on $\Xcal$ , $c>0$ , $f:\Xcal\to\R$ , and $\psi:\Xcal'\to\Xcal$ . Then the following are positive definite:

cK_1,\quad K_1+K_2,\quad K_1K_2,\quad f(x)f(x'),\quad K_1(\psi(x),\psi(x')),\quad \exp(K_1),\quad \lim_n K_n \text{ (pointwise, if it exists)} .

The Gaussian kernel is positive definite

$K(x,x') = \exp\left(-\frac{\norm{x-x'}_2^2}{2\sigma^2}\right) = \exp\left(-\frac{\norm x^2}{2\sigma^2}\right)\exp\left(\frac{\ip{x}{x'}}{\sigma^2}\right)\exp\left(-\frac{\norm{x'}^2}{2\sigma^2}\right).$
Expand the exponent.
$\ip{x}{x'}/\sigma^2$ is PD (it is an inner product of features, namely $x/\sigma$ ), and $\exp$ of a PD kernel is PD.
The middle factor is the exponential of the linear kernel, hence PD by the closure proposition.
With $f(x)=\exp(-\norm x^2/2\sigma^2)$ , $K = f(x)f(x')\cdot\exp(\ip{x}{x'}/\sigma^2)$ is a product of two PD kernels.
The outer factors form a rank-one kernel f(x)f(x'), which is PD, and the product of PD kernels is PD.

Standard kernels and the feature spaces they correspond to:

Kernel	Formula	Feature space
Linear	$\ip{x}{x'}$	$\R^d$ itself
Polynomial	$(1+\ip{x}{x'})^m$	all monomials of degree $\le m$ , dimension $\binom{d+m}{m}$
Gaussian (RBF)	$\exp(-\norm{x-x'}^2/2\sigma^2)$	infinite-dimensional
Laplace	$\exp(-\norm{x-x'}_1/\sigma)$	infinite-dimensional
Cosine similarity	$\ip{x}{x'}/(\norm x\norm{x'})$	normalised $\R^d$

The cost

PropositionKernel methods cost O(n²) memory and O(n³) time

Forming $\mathbf{K}$ requires $n^2$ kernel evaluations and $n^2$ storage; solving $(\mathbf{K}+n\lambda I)\alpha = y$ by Cholesky costs $\tfrac13n^3$ flops. Prediction at a new point costs $n$ kernel evaluations.

What this does not say

This is the reason kernel methods are not used at the scale deep learning operates at: $n = 10^7$ makes $n^2 = 10^{14}$ entries impossible. The standard remedies are

Nyström approximation: sample $m \ll n$ landmarks and approximate $\mathbf{K}\approx \mathbf{K}_{nm}\mathbf{K}_{mm}^{-1}\mathbf{K}_{mn}$ , reducing cost to $O(nm^2)$ .
Random features (Rahimi–Recht): for a shift-invariant kernel, $K(x,x') = \E_\omega[z_\omega(x)z_\omega(x')]$ by Bochner's theorem, so sampling $m$ frequencies gives an explicit $m$ -dimensional feature map with $O(nm)$ cost.
Structured kernels with fast transforms.

None of these changes the statistical guarantees materially for moderate $m$ , and all of them make the method a finite-dimensional linear model again — which is worth noticing, because the same observation connects kernels to the neural tangent kernel picture on the deep learning theory page.

Problems

The Gaussian kernel is positive definiteProof · Intermediate · 30 min Prove the representer theoremProof · Graduate · 1 hour The reproducing property and its consequencesProof · Advanced · 30 min Kernel ridge regression in closed formProof · Intermediate · 30 min Implement kernel ridge regressionCoding · Intermediate · 1 hour The Schur product theoremProof · Advanced · 30 min

References

BookBernhard Schölkopf and Alexander J. Smola (2002). Learning with Kernels
PaperNachman Aronszajn (1950). Theory of Reproducing Kernels
BookIngo Steinwart and Andreas Christmann (2008). Support Vector MachinesThe most careful modern treatment of RKHS theory for learning.
PaperAli Rahimi and Benjamin Recht (2007). Random Features for Large-Scale Kernel Machines

These works are cited as sources to read, not reproduced. All exposition, examples and problems on this site are written independently; where an argument is standard, the citation points to a canonical treatment.

Results stated on this page

DefinitionPositive definite kernelA symmetric function whose Gram matrices are all PSD.
TheoremA kernel is positive definite iff it is an inner product of featuresproof includedPositive definiteness is exactly the condition for a feature-map representation to exist.
TheoremConstruction of the reproducing kernel Hilbert spaceproof includedEvery positive definite kernel has a unique Hilbert space of functions in which it reproduces evaluation.
TheoremRepresenter theoremproof includedAny regularised empirical risk minimiser over an RKHS lies in the span of the kernel sections at the data points.
PropositionKernel ridge regression in closed formproof includedThe coefficients solve an n-by-n linear system involving only the kernel matrix.
PropositionOperations that preserve positive definitenessproof includedSums, products, scalings, limits and compositions with power series of PD kernels are PD.
PropositionKernel methods cost O(n^2) memory and O(n^3) timeproof includedThe exact solution requires forming and factorising the kernel matrix, which is why approximations exist.

Experiments

Kernel ridge regression
The fitted function of kernel ridge regression as bandwidth and regularisation vary.

Problems (6)

All problems