Kernel Methods, and Why DL Cares

Step 1

The kernel trick in one line

A linear classifier learns $w$ such that $\mathrm{sign}(w^\top x)$ predicts the label. Replace $x \to \phi(x)$ for some feature map; the model becomes $\sum_i \alpha_i y_i \phi(x_i)^\top \phi(x) = \sum_i \alpha_i y_i k(x_i, x)$. You never need $\phi$ explicitly — only the kernel $k(x, x') = \phi(x)^\top \phi(x')$. That's the kernel trick.

Two consequences. First, the runtime depends on the number of training points $N$, not the (often infinite) feature dimension. Second, you can use kernels whose feature maps have no closed form — the RBF kernel $k(x, x') = \exp(-\|x-x'\|^2 / 2h^2)$ corresponds to an infinite-dimensional Gaussian feature map.

Step 1½

Mercer's theorem & what counts as a valid kernel

Not every symmetric function $k(x, x')$ is a kernel. The requirement: for any finite set of points $\{x_1, \dots, x_N\}$, the Gram matrix $K_{ij} = k(x_i, x_j)$ must be positive semi-definite. Mercer's theorem (1909) says such kernels admit a spectral decomposition

where $\{\lambda_i, \psi_i\}$ are eigenvalues and eigenfunctions of the integral operator $(T_k f)(x) = \int k(x, x') f(x') \, d\mu(x')$. The map $\phi(x) = (\sqrt{\lambda_i}\,\psi_i(x))_i$ is the implicit feature map you never had to compute. Two practical rules follow:

Closure properties. Sums, products, and positive scalar multiples of kernels are kernels. So is $k_1(x, x')\,k_2(z, z')$ on a product space. This is how you build expressive kernels from primitive ones (spectral mixture kernels, additive GPs).
Constructing new kernels. If $\phi$ is any map into a Hilbert space, $k(x, x') = \langle \phi(x), \phi(x')\rangle$ is automatically a valid kernel. Graph kernels, string kernels, and convolutional kernels all follow this template.

Step 1¾

The representer theorem

Why are all kernel-method solutions of the form $f^\star = \sum_i \alpha_i k(x_i, \cdot)$? The representer theorem (Kimeldorf & Wahba, 1971): for any loss $L$ depending only on $\{f(x_i)\}$ and any monotone regulariser $\Omega(\|f\|_\mathcal{H})$, the minimiser of

over the RKHS $\mathcal{H}$ associated with kernel $k$ lies in the finite-dimensional subspace $\mathrm{span}\{k(x_i, \cdot)\}_{i=1}^N$. So the infinite-dimensional variational problem reduces to an $N$-dimensional one in $\alpha$ — that's why kernel methods are tractable.

Step 2

Live: try four kernels

Click anywhere to drop a class-A (left-click) or class-B (right-click / shift-click) point. A kernel-ridge classifier re-fits each click and recolours the decision regions.

kernel bandwidth / scale 0.50 polynomial degree 3

Left-click adds class-A (blue), right-click / shift-click adds class-B (orange). The boundary recomputes live.

Step 2½

Kernel design — pick the right symmetry

Kernel	Formula	Implicit feature map	Use when
Linear	$x^\top x'$	Identity	High-dim sparse data (text BoW)
Polynomial, deg $d$	$(x^\top x' + c)^d$	All monomials of degree $\le d$	You expect feature interactions of bounded order
RBF / Gaussian	$\exp(-\\|x - x'\\|^2 / 2h^2)$	Infinite-dim	Smooth signals, default
Laplacian	$\exp(-\\|x - x'\\| / h)$	Infinite-dim, rougher	Sparse signals, less smooth
Matérn-$\nu$	tunable smoothness	$\nu$-times differentiable functions	You want to control smoothness exactly
Periodic	$\exp(-2\sin^2(\pi\\|x-x'\\|/p)/h^2)$	Fourier basis	Seasonal time series
String / WL graph	histogram of subsequences / subtrees	combinatorial features	Sequences, molecules, graphs

A practical rule of thumb: bandwidth $h$ ≈ median distance between points. The "median heuristic" is a strong default and the starting point for hyperparameter search. For the polynomial kernel, prefer the explicit feature expansion if you actually want feature interactions; for neural-net-like nonlinearities, prefer RBF or Matérn.

Step 2¾

The kernel-GP-SVM trinity

The same kernel gives you three different methods.

Kernel ridge regression. $\hat\alpha = (K + \lambda I)^{-1} y$; prediction $\hat f(x) = \sum_i \hat\alpha_i k(x_i, x)$. Closed form, $O(N^3)$ to fit, $O(N)$ to predict.
Gaussian process regression. Same point estimate as kernel ridge with $\lambda = \sigma^2$ (noise variance), plus a closed-form predictive variance $\sigma_*^2 = k(x_*, x_*) - k_*^\top (K + \sigma^2 I)^{-1} k_*$. That's the "calibrated uncertainty for free" people talk about.
SVM. Same kernel, different loss (hinge instead of squared error). The dual reduces to a QP in $\alpha$; the active constraints pick out the "support vectors" — usually a sparse subset of the training set.

Mental model: kernel ridge = MAP GP. SVM = max-margin variant. Each adds a different ingredient (Bayesian posterior, sparsity) on top of the same kernel.

Step 3

NTK — the kernel inside an infinite-width net

A wide enough randomly-initialised neural net, when trained with vanishing learning rate, behaves as a kernel method (Jacot et al., 2018). Its kernel is the Neural Tangent Kernel:

For a 1-hidden-layer ReLU net the NTK has a known closed form. Below: a finite-width network's predictions alongside the analytic NTK regressor on the same training points. They agree better as you increase width.

hidden width 128

Finite-width-net prediction (solid) vs NTK regressor (dashed). The gap shrinks as width →∞.

Why this matters. The NTK gives a rare-for-DL piece of theory: a closed-form prediction for what an over-parameterised network does. It has limits (real DL learns features; NTK does not), but it explains a lot of double-descent, generalisation, and optimisation behaviour seen in practice.

Step 3½

Scaling kernels past $N \approx 10^4$

The $O(N^3)$ fit and $O(N^2)$ memory of vanilla kernel methods stop being practical above ~10k points. Four standard escapes:

Random Fourier features. Approximate shift-invariant kernels by sampling frequencies from the kernel's Fourier transform: $k(x, x') \approx z(x)^\top z(x')$ with $z(x) \in \mathbb{R}^D$ for small $D$ (Rahimi & Recht, 2007). Reduces to ordinary ridge in $D$ dimensions — $O(NDB)$ to fit.
Nyström approximation. Pick $M \ll N$ landmark points; approximate $K$ by a low-rank factorisation. Used in scikit-learn's Nystroem.
Inducing-point GPs (SVGP). Variational sparse GPs with $M$ inducing locations; $O(NM^2)$ training. Default for GP libraries (GPflow, GPyTorch).
KeOps / structured kernel interpolation. GPU-friendly exact kernel evaluations on millions of points; mature in 2022–2024 for "exact" GPs on large data.

Step 3¾

Deep kernel learning

Why not the best of both worlds — let a neural net learn a feature map $\phi_\theta$ and feed that into a kernel?

Train $\theta$ jointly with the GP marginal likelihood (Wilson et al., 2016). The neural part learns representations; the GP part gives calibrated uncertainty. In 2024–2026 this is the default for tabular and small-data regression tasks where well-calibrated error bars matter — beats deep ensembles in head-to-head benchmarks on most small tabular regression datasets.

Watch out for collapsing $\phi_\theta$. If the feature dimension is very small, $\phi_\theta$ can collapse to a constant; regularise with a fixed-norm output layer or use SVGP-style variational training.
Library: GPyTorch's DKL example.

Step 4

Where kernel methods are still the right tool

Small-data regression with calibrated UQ. A GP with an RBF kernel beats a deep net on $\le 1k$ training points and gives you principled error bars for free. Direct fit for sensor calibration, hardware design, wet-lab.
Deep kernel learning. $k(x, x') = k_{\text{RBF}}(\phi_\theta(x), \phi_\theta(x'))$ where $\phi_\theta$ is a neural feature extractor learned jointly. Best of both worlds; works well on tabular and time-series.
NTK / NNGP regression. When you want the infinite-width limit's prediction (e.g. for theory or as a baseline), the NTK regressor is a line of code in jax via neural-tangents.
Spectral methods on graphs. Graph kernels for molecule property prediction, citation networks, sensor topologies. Often beat GNNs on small graph datasets.

Step 5

Practical gotchas

Standardise the inputs. RBF / Matérn are extremely scale-sensitive. Standardise each feature to unit variance before computing pairwise distances or your bandwidth tuning will be wrong.
Tune the regulariser. $\lambda$ in kernel ridge / $\sigma^2$ in GP / $C$ in SVM matter as much as the kernel choice. Use cross-validation on log-spaced grids.
Nyström samples should be diverse. Uniform-random landmark selection wastes capacity on a cluster. k-means landmarks or leverage-score sampling are better.
Numerical stability. $K + \lambda I$ can be ill-conditioned; jitter with $\varepsilon I$ ($\varepsilon \sim 10^{-6}$) before Cholesky.
When to not use kernels. Large datasets ($\ge 10^5$ raw points), image / audio / language inputs where representation learning matters more than uncertainty calibration — go with deep nets and accept the calibration cost (or post-hoc temperature-scale).

Step 6

Reading list

Schölkopf & Smola, Learning with Kernels — the canonical textbook.
Rasmussen & Williams, Gaussian Processes for Machine Learning — free online; the standard GP reference.
Jacot, Gabriel, Hongler (2018) — Neural Tangent Kernel. The infinite-width-net / kernel correspondence.
Rahimi & Recht (2007) — Random features for large-scale kernel machines. How to scale RBF kernels to millions of points.
Wilson, Hu, Salakhutdinov, Xing (2016) — Deep kernel learning.
Cohen, Sridharan, Daume (2022) — survey of when GPs beat deep nets on tabular regression.