Explainer

Reproducing Kernel Hilbert Spaces

From vectors to the representer theorem, with the math background taught along the way.

Linear regression with more parameters than data points has many perfect fits. A standard way to choose among them is to pick the fit with the smallest weight norm $\norm{w}$ . That choice needs two ingredients. You need a space of candidate models, and you need a way to measure how big each candidate is.

Now suppose you want to fit a nonlinear function directly, with no weight vector in sight. The candidates are functions, and the space of functions has infinitely many dimensions. What does the size of a function even mean? And how could a computer search an infinite-dimensional space?

A reproducing kernel Hilbert space (RKHS) is a space of functions designed to answer both questions. It comes with a norm that measures how complicated a function is. And the best fit in the entire infinite-dimensional space can be found by solving an $n \times n$ linear system, where $n$ is the number of data points. It is also the shared language of kernel methods, Gaussian processes, and the neural tangent kernel theory of wide networks.

Notation

Symbol	Meaning
$\X$	The set of possible inputs. On this page it is usually the real line.
$\cf{f}, \cf{g}$	Functions from $\X$ to $\R$ . Blue everywhere.
$\H$	A Hilbert space whose elements are functions on $\X$ .
$\ip{f}{g}_{\H}$	The inner product of two functions in $\H$ .
$\cn{\norm{f}_{\H}}$	The norm of $f$ , equal to $\sqrt{\ip{f}{f}_{\H}}$ . Magenta everywhere.
$L$	A linear functional, a linear map from a vector space to $\R$ .
$\delta_x$	The evaluation functional at $x$ . It sends $f$ to the number $f(x)$ .
$f_S,\ f_\perp$	The part of $f$ inside a subspace $S$ and the part orthogonal to $S$ .
$\ck{k}(x,x')$	The kernel, a function of two inputs. Green everywhere.
$\ck{k_x}$	The kernel with one slot fixed. It is the function $x' \mapsto k(x', x)$ , a bump centered at $x$ .
$(x_i, \cy{y_i})$	The $n$ training points. Data is orange everywhere.
$K$	The $n \times n$ kernel matrix with entries $K_{ij} = k(x_i, x_j)$ .
$\alpha$	A vector of $n$ coefficients, one per training point.
$\varphi$	A feature map that turns an input $x$ into a vector of features.
$\lambda$	Regularization strength.

Step 1

Functions are vectors

You already think of a vector in $\R^3$ as a list of three numbers. Another way to say the same thing is that a vector assigns a number to each index 1, 2, 3. That is a function on the set $\{1,2,3\}$ .

So a function is a vector with one coordinate per input. A function on the real line has one coordinate for every real number, which is why function spaces are infinite-dimensional.

Let $\X = \{1,2,3\}$ . Take $f$ with $f(1)=2,\ f(2)=0,\ f(3)=-1$ and $g$ with $g(1)=g(2)=g(3)=1$ . As vectors these are $f=(2,0,-1)$ and $g=(1,1,1)$ .

Adding functions pointwise is adding vectors. $(f+g)(x) = f(x)+g(x)$ gives $(3,1,0)$ . Scaling works the same way. $(2f)(x) = 2f(x)$ gives $(4,0,-2)$ .

Vector space of functions

A set $\mathcal{F}$ of functions $\X \to \R$ is a vector space if it is closed under pointwise addition and scalar multiplication. For all $f,g \in \mathcal{F}$ and $c \in \R$ , both $f+g$ and $cf$ are in $\mathcal{F}$ .

Takeaway. A function is a vector whose coordinates are indexed by inputs, so everything you know about vectors is worth trying on functions.

Step 2

Inner products and norms

In $\R^p$ the dot product $w^\top v$ gives you geometry. It gives lengths through $\norm{w} = \sqrt{w^\top w}$ , and it tells you when two vectors are perpendicular. To do geometry with functions we need the same tool.

An inner product is any rule that takes two vectors and returns a number, as long as it behaves like the dot product. For functions on a finite set, the dot product itself works. For functions on an interval, the sum over coordinates becomes an integral.

On $\X=\{1,2,3\}$ with $f=(2,0,-1)$ and $g=(1,1,1)$ we get $\ip{f}{g} = 2+0-1 = 1$ and $\norm{f} = \sqrt{4+0+1} \approx 2.24$ .

On $\X=[0,1]$ with $f(x)=x$ and $g(x)=1$ , the integral version gives

\ip{f}{g}_{L^2} = \int_0^1 x \cdot 1 \, dx = \tfrac12, \qquad \norm{f}_{L^2}^2 = \int_0^1 x^2\,dx = \tfrac13 .

This integral inner product is called the $L^2$ inner product. Remember it, because Step 4 shows it is the wrong choice for learning.

Inner product and norm

An inner product on a vector space $V$ is a map $\ip{\cdot}{\cdot} : V \times V \to \R$ with three properties, for all $f,g,h \in V$ and $a,b\in\R$ .

Symmetry. $\ip{f}{g} = \ip{g}{f}$ .
Linearity. $\ip{af+bg}{h} = a\ip{f}{h} + b\ip{g}{h}$ .
Positivity. $\ip{f}{f} \ge 0$ , and $\ip{f}{f}=0$ only when $f=0$ .

The norm is $\cn{\norm{f}} = \sqrt{\ip{f}{f}}$ .

Orthogonal

Two elements $f$ and $g$ are orthogonal, also called perpendicular, if $\ip{f}{g} = 0$ . An element is orthogonal to a subspace if it is orthogonal to everything in it.

In $\R^2$ the vectors $(1,1)$ and $(1,-1)$ are orthogonal because $1 - 1 = 0$ . On $[0,1]$ with the integral inner product, $f(x) = 1$ and $g(x) = x - \tfrac12$ are orthogonal because $\int_0^1 (x-\tfrac12)\,dx = 0$ .

The one inequality we will use everywhere

Cauchy–Schwarz inequality

For any $f$ and $g$ in an inner product space, the inner product is never bigger than the product of the norms.

|\ip{f}{g}| \le \cn{\norm{f}}\,\cn{\norm{g}}

Here is the proof, since we lean on this three times later. Assume $g \ne 0$ and pick any number $t$ .

\begin{aligned} 0 &\le \norm{f - tg}^2 && \text{a squared norm is never negative}\\ &= \ip{f-tg}{f-tg} && \text{definition of the norm}\\ &= \norm{f}^2 - 2t\ip{f}{g} + t^2\norm{g}^2 && \text{expand using linearity and symmetry}\\ &= \norm{f}^2 - \frac{\ip{f}{g}^2}{\norm{g}^2} && \text{choose } t = \ip{f}{g}/\norm{g}^2 \end{aligned}

Move the fraction to the left side, multiply by $\norm{g}^2$ , and take square roots. That is the inequality.

Takeaway. An inner product gives a function space lengths and angles, and Cauchy–Schwarz bounds any inner product by the two lengths.

Step 3

Hilbert spaces and projection

In infinite dimensions a new problem appears. A sequence of perfectly nice functions can converge to something that is no longer in your space. It is the same problem the rationals have, where $3,\ 3.1,\ 3.14,\ \dots$ are all rational and the limit $\pi$ is not.

A space with no such holes is called complete. A Hilbert space is an inner product space that is complete. Completeness is what guarantees that minimizers and limits exist, so that when we later ask for the best function, there is one.

A hole in a space

Take continuous functions on $[0,1]$ with the $L^2$ norm. Let $f_m$ be 0 on the left, 1 on the right, with a straight ramp of width $1/m$ in the middle. Each $f_m$ is continuous.

As $m$ grows the ramps get steeper and the functions get closer to each other in norm. The thing they converge to is a step function, which is not continuous. The space of continuous functions with this norm has a hole exactly there.

Hilbert space

A sequence $f_1, f_2, \dots$ converges to $f$ if $\norm{f_m - f} \to 0$ as $m \to \infty$ . The sequence is Cauchy if $\norm{f_m - f_{m'}} \to 0$ as $m, m' \to \infty$ . A space is complete if every Cauchy sequence converges to an element of the space. A Hilbert space is a complete inner product space.

$\R^p$ with the dot product is a Hilbert space. Every finite-dimensional inner product space is one too.

Orthogonal projection

The second thing we need from Hilbert spaces is the shadow of a vector on a subspace. Given a subspace $S$ , any vector splits into a part inside $S$ and a part perpendicular to all of $S$ .

In $\R^3$ let $S$ be the floor, spanned by $(1,0,0)$ and $(0,1,0)$ . The vector $f=(3,4,5)$ splits as $f_S=(3,4,0)$ plus $f_\perp=(0,0,5)$ . The squared lengths add up. $50 = 25 + 25$ .

Orthogonal decomposition

Let $S$ be a finite-dimensional subspace of an inner product space. Every $f$ can be written as $f = f_S + f_\perp$ , where $f_S \in S$ and $\ip{f_\perp}{g} = 0$ for every $g \in S$ . The squared norms add.

\norm{f}^2 = \norm{f_S}^2 + \norm{f_\perp}^2

Here is the proof. Finite-dimensional subspaces are the only case we need. Pick perpendicular unit vectors $e_1,\dots,e_m$ that span $S$ . The Gram–Schmidt procedure from linear algebra produces them. Define $f_S = \sum_j \ip{f}{e_j} e_j$ and $f_\perp = f - f_S$ .

\begin{aligned} \ip{f_\perp}{e_i} &= \ip{f}{e_i} - \sum_j \ip{f}{e_j}\ip{e_j}{e_i} && \text{linearity}\\ &= \ip{f}{e_i} - \ip{f}{e_i} = 0 && \ip{e_j}{e_i} \text{ is 1 if } i=j \text{ and 0 otherwise} \end{aligned}

So $f_\perp$ is perpendicular to every $e_i$ , and therefore to everything in $S$ . The lengths then obey Pythagoras.

\begin{aligned} \norm{f}^2 &= \ip{f_S+f_\perp}{f_S+f_\perp}\\ &= \norm{f_S}^2 + 2\ip{f_S}{f_\perp} + \norm{f_\perp}^2 && \text{expand}\\ &= \norm{f_S}^2 + \norm{f_\perp}^2 && \text{the cross term is zero} \end{aligned}

Takeaway. A Hilbert space is an inner product space with no holes, and in it any vector splits into a piece inside a subspace plus a perpendicular piece whose squared lengths add.

Step 4

Why the obvious norm fails

The $L^2$ space from Step 2 is a Hilbert space, so why not use it? Because learning is about function values at points. We observe $f(x_i)$ at training inputs and we want $f(x)$ at test inputs. A useful norm should control those values. The $L^2$ norm does not.

Pause and predictA function is 1 at

x_0 = 0.5

and falls linearly to 0 within a distance

w

on each side. As

w

shrinks toward zero, what happens to its

L^2

norm? What happens to its value at

x_0

The value at $x_0$ stays exactly 1 while the norm goes to zero. Check it with the slider below. In $L^2$ , a function can be almost the zero function and still be far from zero at the one point you care about.

Try this. Shrink the spike width. Watch the norm collapse while the value at

x_0

does not move.

Spike half-width

w

\cf{f}(x_0)

\cn{\norm{f}_{L^2}} = \sqrt{2w/3}

The norm in the readout comes from a direct calculation. The spike is two mirror-image ramps, so

\norm{f}_{L^2}^2 = 2\int_0^w \left(1-\frac{t}{w}\right)^2 dt = 2 \cdot \frac{w}{3} = \frac{2w}{3}.

L^2

cannot see single points

It is even worse than the plot suggests. Changing a function at a single point does not change any integral. So the $L^2$ norm cannot see the value $f(x_0)$ at all. Making $L^2$ fully rigorous requires treating functions that differ on negligible sets as the same object, which needs measure theory. We will not need that, because the spaces we build next avoid the problem.

Takeaway. In $L^2$ , being small in norm tells you nothing about being small at a point, so $L^2$ is the wrong space for learning from point values.

Step 5

The definition of an RKHS

The fix is to demand exactly the property $L^2$ lacks. We want a Hilbert space of functions where a small norm forces small values at every point. That demand is the entire definition of an RKHS.

To state it we need one new term. A linear functional is a machine that eats a vector and returns a single number, and does so linearly.

Linear functional

Let $V$ be a vector space. A linear functional on $V$ is a map $L : V \to \R$ that respects addition and scaling. For all $f, g \in V$ and all numbers $a, b$ ,

L(af + bg) = a\,L(f) + b\,L(g) .

In $\R^p$ the map $L(w) = a^\top w$ for a fixed vector $a$ is a linear functional. For instance $L(w) = 2w_1 - w_3$ on $\R^3$ sends $(1,5,4)$ to $2 - 4 = -2$ . The map $w \mapsto \norm{w}$ is not one, because doubling $w$ doubles the norm but negating $w$ does not negate it.

The functional we care about reads off the value of a function at one fixed input.

Evaluation functional

Let $\H$ be a vector space of functions on $\X$ and fix an input $x \in \X$ . The evaluation functional at $x$ is the map $\delta_x : \H \to \R$ defined by

\delta_x(\cf{f}) = \cf{f}(x) .

It is a linear functional because functions add and scale pointwise. We have $\delta_x(af+bg) = (af+bg)(x) = a f(x) + b g(x) = a\,\delta_x(f) + b\,\delta_x(g)$ .

On $\X=\{1,2,3\}$ with the dot product, take $f=(2,0,-1)$ . Evaluation at the third point gives $\delta_3(f) = -1$ . And $|f(3)| = 1 \le \norm{f} \approx 2.24$ . A coordinate is never bigger than the length of the whole vector, so here evaluation is controlled by the norm with constant 1.

Bounded linear functional

A linear functional $L$ on a Hilbert space is bounded if there is a constant $C$ with $|L(f)| \le C\,\norm{f}$ for every $f$ .

Reproducing kernel Hilbert space

A reproducing kernel Hilbert space on $\X$ is a Hilbert space $\H$ whose elements are functions $\X \to \R$ , such that for every $x \in \X$ the evaluation functional $\delta_x$ is bounded. For each $x$ there is a constant $C_x$ with

|\cf{f}(x)| \le C_x \, \cn{\norm{f}_{\H}} \quad \text{for all } f \in \H .

Norm convergence implies pointwise convergence

In an RKHS, for all $f, g \in \H$ and every $x \in \X$ ,

|f(x) - g(x)| \le C_x\, \norm{f-g}_{\H} .

In particular, if $\norm{f_m - f}_{\H} \to 0$ then $f_m(x) \to f(x)$ at every point $x$ .

The proof is one line. We have $|f(x) - g(x)| = |\delta_x(f-g)| \le C_x \norm{f-g}_{\H}$ , where the equality uses linearity of $\delta_x$ and the inequality is boundedness.

Spikes are therefore impossible. A function with $f(x_0)=1$ must have norm at least $1/C_{x_0}$ .

Notice that no kernel has appeared yet. The name promises a kernel, and the next step shows that boundedness alone forces one to exist.

Takeaway. An RKHS is a Hilbert space of functions in which the value at each point is controlled by the norm.

Step 6

Where the kernel comes from

In $\R^p$ every linear functional is a dot product with some fixed vector. If $L$ is linear then $L(w) = a^\top w$ , where $a$ collects the values of $L$ on the basis vectors. The same fact holds in any Hilbert space for bounded functionals. It is called the Riesz representation theorem.

On $\R^3$ let $L(w) = 2w_1 - w_3$ . Then $L(w) = a^\top w$ with $a = (2, 0, -1)$ . The functional is fully described by one vector living in the same space.

Riesz representation theorem

Let $L$ be a bounded linear functional on a Hilbert space $\H$ . Then there is exactly one element $g \in \H$ such that $L(f) = \ip{f}{g}_{\H}$ for every $f \in \H$ .

Here is the proof in finite dimensions. Take perpendicular unit vectors $e_1,\dots,e_p$ spanning the space, so that $f = \sum_j \ip{f}{e_j}e_j$ .

\begin{aligned} L(f) &= L\Big(\sum_j \ip{f}{e_j}\, e_j\Big) && \text{expand } f \text{ in the basis}\\ &= \sum_j \ip{f}{e_j}\, L(e_j) && L \text{ is linear}\\ &= \Big\langle f,\ \sum_j L(e_j)\, e_j \Big\rangle && \text{inner product is linear, and each } L(e_j) \text{ is just a number} \end{aligned}

So $g = \sum_j L(e_j)e_j$ works. It is also the only choice. If $g$ and $g'$ both work, then $\ip{f}{g-g'} = 0$ for every $f$ . Choosing $f = g-g'$ gives $\norm{g-g'}^2 = 0$ , so $g = g'$ .

In infinite dimensions the same idea works, and boundedness is exactly what makes the infinite sum converge. I am stating the infinite-dimensional theorem without its full proof. This is also the place where completeness from Step 3 is needed.

Apply Riesz to evaluation

In an RKHS each evaluation functional $\delta_x$ is bounded. So the Riesz theorem hands us, for each input $x$ , one special function in $\H$ .

Reproducing kernel

Let $\H$ be an RKHS on $\X$ . For each $x \in \X$ , let $\ck{k_x} \in \H$ be the element that the Riesz theorem gives for $\delta_x$ . It satisfies the reproducing property

\cf{f}(x) = \ip{\cf{f}}{\ck{k_x}}_{\H} \quad \text{for all } f \in \H .

The reproducing kernel of $\H$ is the function of two inputs

\ck{k}(x, x') = \ip{\ck{k_x}}{\ck{k_{x'}}}_{\H} .

Taking the inner product with $k_x$ reproduces the value of $f$ at $x$ . The function $k_x$ plays the role that the coordinate vector $(0,0,1)$ plays for reading off the third coordinate.

Properties of the reproducing kernel

Let $k$ be the reproducing kernel of an RKHS $\H$ . Then

$k$ is symmetric, so $k(x,x') = k(x',x)$ .
Its slices are the special functions, so $k_{x'} = k(\cdot, x')$ .
$k$ is positive semidefinite. For any points $x_1,\dots,x_n$ and numbers $c_1,\dots,c_n$ we have $\sum_{i,j} c_i c_j\, k(x_i,x_j) \ge 0$ .
Every $f \in \H$ satisfies $|\cf{f}(x)| \le \cn{\norm{f}_{\H}}\sqrt{\ck{k}(x,x)}$ .

The proof takes the four parts in turn.

It is symmetric. $k(x,x') = k(x',x)$ because inner products are symmetric.

Its slices are the special functions. Apply the reproducing property to the function $f = k_{x'}$ at the point $x$ .

k_{x'}(x) = \ip{k_{x'}}{k_x}_{\H} = k(x, x')

So $k_{x'}$ is the function you get from $k$ by fixing the second slot at $x'$ , which is what $k(\cdot, x')$ means.

It is positive semidefinite. Take any points $x_1,\dots,x_n$ and any numbers $c_1,\dots,c_n$ .

\begin{aligned} \sum_{i,j} c_i c_j\, k(x_i,x_j) &= \sum_{i,j} c_i c_j \ip{k_{x_i}}{k_{x_j}} && \text{definition of } k\\ &= \Big\langle \sum_i c_i k_{x_i},\ \sum_j c_j k_{x_j} \Big\rangle && \text{linearity in both slots}\\ &= \Big\lVert \sum_i c_i k_{x_i} \Big\rVert^2 \ \ge\ 0 && \text{a squared norm} \end{aligned}

In matrix language, the kernel matrix $K$ with $K_{ij}=k(x_i,x_j)$ satisfies $c^\top K c \ge 0$ for every $c$ .

It bounds function values. By the reproducing property and Cauchy–Schwarz,

|\cf{f}(x)| = |\ip{f}{k_x}| \le \cn{\norm{f}_{\H}}\,\norm{k_x}_{\H} = \cn{\norm{f}_{\H}}\sqrt{\ck{k}(x,x)} .

This is the best possible constant $C_x$ in the definition of an RKHS.

Linear functions

Let $\H$ be all linear functions on $\R^2$ , written $f_w(x) = w^\top x$ , with inner product $\ip{f_w}{f_v} = w^\top v$ . Which function $k_x$ reproduces evaluation at $x$ ? We need $\ip{f_w}{k_x} = w^\top x$ for all $w$ , so $k_x = f_x$ . The kernel is $k(x,x') = \ip{f_x}{f_{x'}} = x^\top x'$ .

With $w=(2,-1)$ and $x=(1,3)$ we get $f_w(x) = 2 - 3 = -1$ , and $\ip{f_w}{k_x} = w^\top x = -1$ . This is called the linear kernel. Ordinary linear regression already lives in an RKHS.

Takeaway. Bounded evaluation forces the existence of a kernel $k$ , which is symmetric, positive semidefinite, and reads off function values through $f(x) = \langle f, k_x\rangle$ .

Step 7

Building the space from a kernel

Step 6 went from a space to a kernel. In practice people go the other way. They pick a kernel and let it define the space. This works because any symmetric positive semidefinite function is the kernel of exactly one RKHS.

Kernel

A function $k : \X\times\X \to \R$ is a kernel (also called a positive definite kernel) if it is symmetric and for every $n$ , every choice of points $x_1,\dots,x_n$ , and every $c \in \R^n$ ,

\sum_{i=1}^n\sum_{j=1}^n c_i c_j\, \ck{k}(x_i,x_j) \ \ge\ 0 .

Terminology

The literature says "positive definite kernel" for this condition even though the inequality is not strict.

A kernel and a non-kernel

The Gaussian kernel on the real line is $k(x,x') = \exp\!\big(-(x-x')^2/(2\ell^2)\big)$ . The number $\ell$ is called the lengthscale. For $\ell=1$ and the points $0$ and $1$ , the kernel matrix is

K = \begin{pmatrix} 1 & 0.607\\ 0.607 & 1\end{pmatrix}, \qquad c^\top K c = c_1^2 + c_2^2 + 1.213\,c_1c_2 \ \ge 0 .

The last inequality holds because the cross term can never outweigh $c_1^2 + c_2^2$ .

A non-example is distance. Take $k(x,x') = |x-x'|$ with the same two points. Then $K$ has zeros on the diagonal and ones off it. Choosing $c = (1,-1)$ gives $c^\top K c = -2$ . So not every similarity-like function is a kernel.

The construction

Start with the bump functions $k_x = k(\cdot,x)$ , one for each input $x$ . Step 6 says these must be in the space. So take all finite weighted sums of bumps.

\cf{f} = \sum_{i=1}^m \alpha_i\, \ck{k}(\cdot, x_i)

Step 6 also says what the inner product between two bumps must be, namely $\ip{k_x}{k_{x'}} = k(x,x')$ . Extending by linearity leaves no choice for sums. If $g = \sum_j \beta_j k(\cdot, z_j)$ then

\ip{f}{g} = \sum_{i}\sum_{j} \alpha_i \beta_j\, \ck{k}(x_i, z_j), \qquad\text{so}\qquad \cn{\norm{f}^2} = \sum_{i,j}\alpha_i\alpha_j\, k(x_i,x_j) = \alpha^\top K \alpha .

Check that the reproducing property holds with this inner product. Take $g = k(\cdot, x)$ , a single bump with weight 1.

\ip{f}{k(\cdot,x)} = \sum_i \alpha_i\, k(x_i, x) = f(x)

The last equality is just the definition of $f$ evaluated at $x$ . Finally, fill the holes by adding the limits of Cauchy sequences, as in Step 3.

Moore–Aronszajn theorem

For every kernel $k$ on $\X$ there is exactly one RKHS of functions on $\X$ whose reproducing kernel is $k$ . It is the completion of the space of finite sums $\sum_i \alpha_i k(\cdot,x_i)$ under the inner product above.

What the construction skips

The theorem appears in Aronszajn (1950), who credits the idea to E. H. Moore. Three details are skipped here. The inner product does not depend on how $f$ is written as a sum. It is strictly positive for $f \neq 0$ . And the limits added during completion are still genuine functions on $\X$ . All three are proved in the references at the end.

Pause and predictPlace two Gaussian bumps almost on top of each other. Case A gives both weight

+1

. Case B gives them weights

+1

and

-1

. Both have

\sum_i \alpha_i^2 = 2

. Which case has the larger RKHS norm?

Case A. The bumps overlap, so $k(x_1,x_2) \approx 1$ and $\norm{f}^2 = \alpha_1^2+\alpha_2^2+2\alpha_1\alpha_2 k(x_1,x_2)$ . That is about $4$ in case A and about $0$ in case B. This makes sense because in case B the two bumps cancel and $f$ is nearly the zero function. The norm measures the function, not the coefficients. Try both cases below.

Try this. Each handle is one bump. Drag it sideways to move its center and up or down to change its weight

\alpha_i

. Compare the RKHS norm with the plain sum of squared weights.

f = \sum_i \alpha_i k(\cdot,x_i)

individual bumps

\alpha_i k(\cdot,x_i)

handle at (center, weight)

Lengthscale

\ell

\cn{\norm{f}_{\H}^2} = \alpha^\top K\alpha

\sum_i \alpha_i^2

\max_x |\cf{f}(x)|

While you play, check the bound from Step 6. For the Gaussian kernel $k(x,x)=1$ , so $|f(x)| \le \norm{f}_{\H}$ at every point. The maximum of $|f|$ in the readout never exceeds the square root of the norm readout.

Takeaway. Choosing a kernel chooses the space. Its functions are weighted sums of kernel bumps and their limits, and the squared norm of such a sum is $\alpha^\top K \alpha$ .

Step 8

The feature map view

There is a second way to see the same space, and it connects straight back to linear regression. A kernel is a dot product between feature vectors. An RKHS is the set of linear models on those features, and the RKHS norm is the weight norm.

Take the polynomial kernel $k(x,x') = (1+xx')^2$ on the real line. Expand the square.

(1+xx')^2 = 1 + 2xx' + x^2x'^2 = \varphi(x)^\top\varphi(x') \quad\text{with}\quad \varphi(x) = \big(1,\ \sqrt2\,x,\ x^2\big)

Check with $x=1$ and $x'=2$ . The kernel gives $(1+2)^2 = 9$ . The features are $\varphi(1) = (1, \sqrt2, 1)$ and $\varphi(2) = (1, 2\sqrt2, 4)$ , with dot product $1 + 4 + 4 = 9$ .

Try this. Move

x

and

x'

. The kernel value and the feature dot product always agree, even though the kernel never computes the features.

x

x'

\varphi(x)

\varphi(x')

\varphi(x)^\top\varphi(x')

\ck{k}(x,x') = (1+xx')^2

Now consider all linear models on these features, $f_w(x) = w^\top\varphi(x) = w_1 + \sqrt2\,w_2\,x + w_3x^2$ . Give them the inner product $\ip{f_w}{f_v} = w^\top v$ . Is this the RKHS of the polynomial kernel? Check the reproducing property. The bump $k_{x'}$ is the model with weights $\varphi(x')$ , since $k(x,x') = \varphi(x')^\top\varphi(x)$ . Then

\ip{f_w}{k_{x'}} = w^\top \varphi(x') = f_w(x') .

It reproduces. By the uniqueness in Step 7, this space of quadratics with the weight-norm is the RKHS. For instance $f(x)=x^2$ has weights $(0,0,1)$ and norm 1, while $f(x)=x$ has weights $(0,1/\sqrt2,0)$ and norm about $0.71$ .

Feature map characterization

Suppose $k(x,x') = \ip{\varphi(x)}{\varphi(x')}_{\mathcal{W}}$ for some map $\varphi$ from $\X$ into a Hilbert space $\mathcal{W}$ of feature vectors. Then the RKHS of $k$ is the set of functions $f_w(x) = \ip{w}{\varphi(x)}_{\mathcal W}$ , and

\cn{\norm{f}_{\H}} = \min\{\, \norm{w}_{\mathcal W} \ :\ f_w = f \,\}.

Feature maps are not unique

The minimum matters when several weight vectors give the same function. The RKHS norm is the norm of the smallest one. Every kernel has at least one feature map, namely $\varphi(x) = k(\cdot, x)$ with $\mathcal W = \H$ . Feature maps are not unique, but they all give the same RKHS.

The Gaussian kernel needs infinitely many features. For $\ell = 1$ , split the exponent and use the Taylor series of $e^{xx'}$ .

\begin{aligned} e^{-(x-x')^2/2} &= e^{-x^2/2}\, e^{-x'^2/2}\, e^{xx'} && \text{expand the square in the exponent}\\ &= e^{-x^2/2}\, e^{-x'^2/2} \sum_{j=0}^\infty \frac{(xx')^j}{j!} && \text{Taylor series of the exponential}\\ &= \sum_{j=0}^\infty \varphi_j(x)\,\varphi_j(x') \quad\text{with}\quad \varphi_j(x) = e^{-x^2/2}\frac{x^j}{\sqrt{j!}} && \text{split each term evenly} \end{aligned}

So Gaussian-kernel regression is linear regression on infinitely many features. No computer could store $\varphi(x)$ , yet $k(x,x')$ is one line of code. Using $k$ to get feature dot products without computing features is called the kernel trick.

This is the link to overparameterized linear regression. The minimum-norm interpolator there picks the smallest $\norm{w}$ among weights that fit the data. In an RKHS, picking the smallest $\norm{f}_{\H}$ is the same act, carried out in a feature space that may be infinite-dimensional.

Takeaway. An RKHS is the set of linear models on some feature map, and the RKHS norm is the smallest weight norm that produces the function.

Step 9

What the norm measures

The RKHS norm is a complexity measure. A function with small norm cannot be large and cannot change quickly. How quickly it may change is set by the kernel.

Smoothness bound

Let $\H$ be an RKHS with kernel $k$ . For every $f \in \H$ and all inputs $x, x'$ ,

|f(x) - f(x')| \le \cn{\norm{f}_{\H}}\ \sqrt{k(x,x) + k(x',x') - 2k(x,x')} .

The size bound was part 4 of the lemma in Step 6. To prove the bound on change, compare the values at two points using the reproducing property.

\begin{aligned} |f(x) - f(x')| &= |\ip{f}{k_x} - \ip{f}{k_{x'}}| && \text{reproducing property, twice}\\ &= |\ip{f}{k_x - k_{x'}}| && \text{linearity}\\ &\le \cn{\norm{f}_{\H}}\ \norm{k_x - k_{x'}}_{\H} && \text{Cauchy–Schwarz}\\ &= \cn{\norm{f}_{\H}}\ \sqrt{k(x,x) + k(x',x') - 2k(x,x')} && \text{expand } \norm{k_x-k_{x'}}^2 \text{ with } \ip{k_x}{k_{x'}}=k(x,x') \end{aligned}

Gaussian kernel with $\ell = 1$ and two points a distance $0.1$ apart. The square root is $\sqrt{2 - 2e^{-0.005}} \approx 0.0999$ . So any $f$ in this RKHS satisfies $|f(x)-f(x')| \le 0.0999\,\norm{f}_{\H}$ . To jump by 1 over that short distance, a function needs norm at least 10.

An explicit norm

For some kernels the norm has an explicit formula. For the Laplace kernel $k(x,x') = e^{-|x-x'|}$ on the real line it is

\cn{\norm{f}_{\H}^2} = \frac12\int_{-\infty}^{\infty} \big( f(x)^2 + f'(x)^2 \big)\, dx .

That formula penalizes both size and slope. For the Gaussian kernel the penalty involves derivatives of every order, which is why its functions are extremely smooth. The Laplace formula is quoted here as a standard result without a derivation.

Takeaway. A small RKHS norm means the function is small and changes slowly, with the kernel deciding what slowly means.

Step 10

The representer theorem

We can now pose the learning problem. Among all functions in $\H$ , find the one that fits the data well and has small norm.

\min_{f \in \H}\ \ \sum_{i=1}^n \big(\cf{f}(x_i) - \cy{y_i}\big)^2 \ +\ \lambda\, \cn{\norm{f}_{\H}^2}

The first term is the fit to the data. The second is the complexity penalty, with $\lambda > 0$ setting the trade-off.

Pause and predictFor the Gaussian kernel,

\H

is infinite-dimensional. How many numbers do you expect it takes to write down the exact minimizer for

n

data points?

Exactly $n$ . The minimizer is a weighted sum of the $n$ bumps centered at the training inputs. Every other direction in the infinite-dimensional space is useless, for a reason the proof below makes precise.

Representer theorem

Any minimizer of the problem above has the form

\cf{f} = \sum_{i=1}^n \alpha_i\, \ck{k}(\cdot, x_i) \quad\text{for some } \alpha \in \R^n .

Generality and credit

The same holds if the squared error is replaced by any loss that depends on $f$ only through $f(x_1),\dots,f(x_n)$ , and if $\lambda\norm{f}^2$ is replaced by any strictly increasing function of $\norm{f}$ . The squared-error case goes back to Kimeldorf and Wahba around 1970. The general version is due to Schölkopf, Herbrich and Smola (2001).

Proof

Let $S$ be the subspace spanned by the $n$ bumps $k_{x_1},\dots,k_{x_n}$ . It is finite-dimensional, so by Step 3 any $f\in\H$ splits as $f = f_S + f_\perp$ with $f_\perp$ perpendicular to every bump.

The fit term cannot see $f_\perp$ . At each training point,

\begin{aligned} f(x_i) &= \ip{f}{k_{x_i}} && \text{reproducing property}\\ &= \ip{f_S}{k_{x_i}} + \ip{f_\perp}{k_{x_i}} && \text{split } f\\ &= \ip{f_S}{k_{x_i}} + 0 = f_S(x_i) && f_\perp \text{ is perpendicular to every bump.} \end{aligned}

So $f$ and $f_S$ agree on all the training data and have the same fit term.

The penalty can only grow with $f_\perp$ . By Pythagoras from Step 3, $\norm{f}^2 = \norm{f_S}^2 + \norm{f_\perp}^2$ .

Putting these together, if $f_\perp \ne 0$ then dropping it keeps the fit identical and strictly lowers the penalty. So a minimizer must have $f_\perp = 0$ . It lies in $S$ , which means it is a weighted sum of the $n$ bumps.

Try this. The slider adds

t

times a unit-norm function

\hat g

that is perpendicular to all the bumps. Watch the curve change everywhere except at the data. The fit term stays frozen while the penalty grows by exactly

t^2

f = f_S + t\,\hat g

f_S

alonedata

Amount

t

Location of the extra wiggle

fit term

\sum_i(\cf{f}(x_i)-\cy{y_i})^2

\cn{\norm{f}_{\H}^2} = \norm{f_S}^2 + t^2

Real computation.

\hat g

is a bump at the wiggle location with its projection onto the five training bumps subtracted, then scaled to unit norm. Gaussian kernel,

\ell = 0.7

Takeaway. Anything perpendicular to the training bumps is invisible to the data and costs norm, so the best function is always a sum of $n$ bumps at the training inputs.

Step 11

Kernel ridge regression

The representer theorem turns a search over functions into a search over $n$ numbers. All that is left is to plug $f = \sum_j \alpha_j k(\cdot,x_j)$ into the objective and solve for $\alpha$ .

Kernel ridge regression

The minimizer of the problem in Step 10 is

\cf{f}(x) = \sum_{i=1}^n \alpha_i\, \ck{k}(x, x_i) \qquad\text{with}\qquad \alpha = (K + \lambda I)^{-1}\, \cy{y} .

Here is the derivation. Both terms become matrix expressions. The prediction at a training point is $f(x_i) = \sum_j \alpha_j k(x_i,x_j) = (K\alpha)_i$ . The squared norm is $\alpha^\top K\alpha$ from Step 7. So the objective is

J(\alpha) = \norm{K\alpha - \cy{y}}^2 + \lambda\, \alpha^\top K \alpha .

Set the gradient to zero.

\begin{aligned} \nabla J(\alpha) &= 2K(K\alpha - y) + 2\lambda K\alpha && \text{gradient of each term, using } K^\top = K\\ &= 2K\big[(K + \lambda I)\alpha - y\big] && \text{factor out } 2K \end{aligned}

The bracket is zero when

\alpha = (K + \lambda I)^{-1}\, \cy{y}, \qquad\text{giving the prediction}\qquad \cf{f}(x) = \sum_{i=1}^n \alpha_i\, \ck{k}(x, x_i).

The matrix $K+\lambda I$ is always invertible, because $K$ is positive semidefinite and $\lambda>0$ . Since $J$ is convex, this stationary point is a minimizer.

When

K

is not invertible

If two training inputs coincide, $K$ is singular and other vectors $\alpha$ also make the gradient zero. They differ from ours by some $v$ with $Kv = 0$ . The function $\sum_i v_i k(\cdot,x_i)$ has squared norm $v^\top K v = 0$ , so it is the zero function. Every solution therefore gives the same $f$ .

Two data points, $(x_1,y_1) = (0,1)$ and $(x_2,y_2)=(1,0)$ . Gaussian kernel with $\ell=1$ and $\lambda = 0.1$ .

K + \lambda I = \begin{pmatrix}1.1 & 0.607\\ 0.607 & 1.1\end{pmatrix},\qquad \alpha = (K+\lambda I)^{-1}\begin{pmatrix}1\\0\end{pmatrix} \approx \begin{pmatrix}1.306\\ -0.720\end{pmatrix}

The fitted values are $f(0) \approx 0.869$ and $f(1) \approx 0.072$ , pulled slightly away from the targets $1$ and $0$ . The squared norm is $\alpha^\top K\alpha \approx 1.084$ .

It contains ordinary ridge regression

The linear kernel gives ridge regression

With the linear kernel $k(x,x') = x^\top x'$ , the kernel ridge prediction is $f(x) = x^\top w^*$ , where $w^* = (X^\top X + \lambda I_p)^{-1}X^\top y$ is the ordinary ridge regression solution.

To see this, use the linear kernel. Then $K = XX^\top$ , where the rows of $X$ are the training inputs. The prediction at a new $x$ is

\begin{aligned} f(x) &= \sum_i \alpha_i\, x_i^\top x = x^\top X^\top \alpha && \text{definition of the linear kernel}\\ &= x^\top X^\top (XX^\top + \lambda I_n)^{-1} y && \text{plug in } \alpha\\ &= x^\top (X^\top X + \lambda I_p)^{-1} X^\top y && \text{swap identity, explained below} \end{aligned}

The last line is $x^\top w^*$ . The swap is valid because $(X^\top X + \lambda I_p)X^\top = X^\top(XX^\top + \lambda I_n)$ . Both sides equal $X^\top X X^\top + \lambda X^\top$ . Multiply by the two inverses on either side and you get the swap.

Notice what changed. The familiar ridge formula inverts a $p\times p$ matrix, one row per parameter. The kernel formula inverts an $n \times n$ matrix, one row per data point. When features are infinite, only the second is possible.

The limit of no regularization

As $\lambda \to 0$ the fit passes through every training point when $K$ is invertible, with $\alpha = K^{-1}y$ . Among all functions in $\H$ that interpolate the data, this one has the smallest norm. It is the function-space twin of the minimum-norm interpolator of overparameterized linear regression.

Pause and predictIn the playground below, you will push

\lambda

toward zero. The curve must then pass through every noisy point. What do you expect to happen to

\norm{f}_{\H}^2

, and does a larger lengthscale make that better or worse?

The norm grows, and a larger lengthscale makes it much worse. Wide bumps are nearly identical to their neighbors, so matching noisy targets needs huge weights of alternating sign that almost cancel. The norm readout can jump by many orders of magnitude. With a short lengthscale each bump handles its own point and the norm stays modest.

Try this. Click empty space to add a point. Drag points to move them. Double-click a point to remove it. Then sweep

\lambda

and

\ell

and watch the trade between fit error and the norm. Switch to the Laplace kernel to see how the kernel sets the shape of the fit.

fit

f

bumps

\alpha_i k(\cdot,x_i)

data

\lambda

\ell

Kernel Show bumps

fit error

\sum_i(\cf{f}(x_i)-\cy{y_i})^2

\cn{\norm{f}_{\H}^2} = \alpha^\top K\alpha

= largest

|\alpha_i|

Real computation. Each redraw solves

(K+\lambda I)\alpha = y

in your browser.

Takeaway. Kernel ridge regression is $\alpha = (K+\lambda I)^{-1}y$ . It is ridge regression in feature space, computed with an $n\times n$ solve no matter how many features there are.

Wrap-up

The whole chain in one place

Functions are vectors, so a set of functions can be a vector space.
An inner product gives that space a norm and Cauchy–Schwarz.
Completeness makes it a Hilbert space, where projections and Pythagoras work.
The $L^2$ norm does not control values at points, so it is a poor fit for learning.
An RKHS is a Hilbert space of functions where each point evaluation is bounded by the norm.
By Riesz, bounded evaluation produces $k_x$ with $f(x) = \ip{f}{k_x}$ , and $k(x,x') = \ip{k_x}{k_{x'}}$ is symmetric and positive semidefinite.
Conversely every such $k$ defines one RKHS, made of sums of bumps with $\norm{f}^2 = \alpha^\top K\alpha$ .
Equivalently it is linear models on a feature map, with the RKHS norm equal to the smallest weight norm.
The norm bounds how large $f$ is and how fast it changes.
Regularized fitting over the whole space always lands on a sum of $n$ training bumps.
For squared loss the coefficients are $\alpha = (K+\lambda I)^{-1}y$ .

Common misconceptions

"The Gaussian RKHS contains every reasonable function." It does not. On an interval it contains no nonzero constant function and no nonzero polynomial (Steinwart, Hush and Scovel 2006, Minh 2010). What is true is that its functions can approximate any continuous function on a bounded closed interval as closely as you like (Steinwart 2001). The approximating functions pay with an exploding norm.

"The RKHS norm is some version of the $L^2$ norm." They are different. A function can have a tiny $L^2$ norm and a huge RKHS norm, as the playground shows when the fit wiggles through noise.

" $\norm{f}^2$ is the sum of squared coefficients." It is $\alpha^\top K\alpha$ . Overlapping bumps interact, as in the Step 7 prediction.

"Any similarity function is a kernel." It must be symmetric and positive semidefinite. Distance is a non-example.

"The feature map is part of the definition." Many different feature maps give the same kernel, and they all give the same RKHS. The kernel is the canonical object.

"Kernel methods are a different thing from linear models." They are linear models, in a feature space chosen through $k$ . All the nonlinearity is in the fixed map $\varphi$ . Nothing about $\varphi$ is learned from data.

Blind spots worth knowing about

The spectral view (Mercer's theorem). Under mild conditions a kernel can be expanded as $k(x,x') = \sum_j \mu_j\, e_j(x) e_j(x')$ with eigenvalues $\mu_j \ge 0$ and orthonormal eigenfunctions $e_j$ , the function analog of diagonalizing a symmetric matrix. Then $\norm{f}_{\H}^2 = \sum_j c_j^2/\mu_j$ , where $c_j$ is the component of $f$ along $e_j$ . Directions with small eigenvalues are expensive, and those are typically the high-frequency ones. This is the tool behind most precise generalization analyses of kernel regression, and it is how the analysis of double descent in linear regression (Hastie et al., listed below) extends beyond plain linear features.

Gaussian processes. A Gaussian process uses the same $k$ as a covariance function for a random function. Its posterior mean with noise variance $\lambda$ is exactly the kernel ridge solution above. A subtle point is that random draws from the process are typically rougher than anything in the RKHS and almost surely lie outside it when the RKHS is infinite-dimensional. Kanagawa et al. (2018) is the reference for these connections.

The neural tangent kernel. Jacot, Gabriel and Hongler (2018) showed that an infinitely wide network, under a particular scaling of the initialization, trains like kernel regression with a fixed kernel determined by the architecture. This is the main reason deep learning theory talks about RKHSs. It is also a limitation. A fixed kernel means the features never change. Other scalings of the network, such as the maximal update parameterization (µP), are designed so that features keep moving at infinite width. That is the regime this theory does not describe.

Beyond RKHS norms. The RKHS norm is an $\ell_2$ norm on a fixed set of features. Networks that learn features behave more like an $\ell_1$ -type norm over an infinite pool of possible neurons, which can adapt to structure such as dependence on a few input directions. Bach (2017) contrasts the two function spaces. If you ever see "Barron space" or "variation norm", this is that story.

Random features. Rahimi and Recht (2007) approximate a kernel with a finite number $p$ of random features and then run plain ridge regression. This gives a bridge between kernel regression ( $p = \infty$ ) and the parameter-count axis in double descent plots.

Interpolation without regularization. The $\lambda\to 0$ limit, sometimes called ridgeless kernel regression, fits noise exactly and can still generalize in high dimensions. Belkin, Ma and Mandal (2018) argued that this puzzle already appears in kernel methods, not only in deep networks.

Cost. The $n \times n$ solve takes time proportional to $n^3$ and memory proportional to $n^2$ . That scaling is the practical reason kernel methods lost ground to networks on large datasets.

Sources and further reading

T. Hastie, A. Montanari, S. Rosset and R. Tibshirani (2019). Surprises in high-dimensional ridgeless least squares interpolation. For minimum-norm interpolation and double descent in linear regression.
N. Aronszajn (1950). Theory of reproducing kernels. Transactions of the American Mathematical Society 68. The original source for Steps 5 to 7.
G. Kimeldorf and G. Wahba (1970). A correspondence between Bayesian estimation on stochastic processes and smoothing by splines. Annals of Mathematical Statistics 41. Also their 1971 paper, Some results on Tchebycheffian spline functions.
B. Schölkopf, R. Herbrich and A. Smola (2001). A generalized representer theorem. COLT 2001. The proof in Step 10 follows theirs.
M. Kanagawa, P. Hennig, D. Sejdinovic and B. Sriperumbudur (2018). Gaussian processes and kernel methods, a review on connections and equivalences. A readable modern reference for most of this page.
I. Steinwart, D. Hush and C. Scovel (2006). An explicit description of the reproducing kernel Hilbert spaces of Gaussian RBF kernels. IEEE Transactions on Information Theory 52. And H. Q. Minh (2010), Some properties of Gaussian reproducing kernel Hilbert spaces, Constructive Approximation 32.
A. Jacot, F. Gabriel and C. Hongler (2018). Neural tangent kernel, convergence and generalization in neural networks.
F. Bach (2017). Breaking the curse of dimensionality with convex neural networks. JMLR 18.
M. Belkin, S. Ma and S. Mandal (2018). To understand deep learning we need to understand kernel learning.
A. Rahimi and B. Recht (2007). Random features for large-scale kernel machines. NeurIPS 2007.
Textbooks. Schölkopf and Smola, Learning with Kernels (2002). Steinwart and Christmann, Support Vector Machines (2008), for full proofs of everything stated without proof here.