Kernel Methods for Machine Learning

Contents

• Introduction and overview
• 0. Review: Hilbert spaces, positive matrices and duality
• 1. Positive definite kernels and the kernel trick
• 2. Reproducing kernel Hilbert spaces
• 3. The representer theorem and kernel ridge regression
• 4. Support vector machines
• 5. Unsupervised kernel methods: kernel PCA, kernel k-means, kernel CCA
• 6. Mercer, Bochner and semigroup kernels
• 7. Kernels for strings and graphs, kernels on graphs
• 8. Multiple kernel learning and kernel mean embeddings
• 9. Large-scale learning with kernels
• 10. Deep learning with kernels
• 11. Complements for self-study
• 12. Research directions and open problems
• Exercises
• Projects and assessment
• References

Introduction and overview

Audience: a student with a good M1 in mathematics or computer science who knows linear models and wants learning algorithms that work on sequences, graphs and probability distributions as well as on vectors.

Empirical first: on the scikit-learn “two moons” data set (600 points, noise 0.15, half of them for training), a linear support vector machine reaches 89.7 % test accuracy, while the same algorithm with a Gaussian kernel reaches 99.0 % (code in ch. 4). A protein sequence or a molecule has no natural vector representation at all. One idea fixes both problems: replace every inner product by a positive definite kernel.

This course builds the theory behind that idea and the algorithms that follow from it. It starts from positive definite kernels and their reproducing kernel Hilbert spaces, derives the classical kernel algorithms, then turns to the design of kernels for structured data and to current research on scale and depth.

It shares tools with Introduction to Statistical Learning, Convex Optimization, Graphs in Machine Learning and Bayesian Machine Learning.

What you will be able to do

• Prove that a function is a positive definite kernel, with closure properties, Bochner’s theorem or Schoenberg’s theorem.
• Construct the reproducing kernel Hilbert space (RKHS) of a kernel and compute norms and pointwise bounds in it.
• Apply the representer theorem to turn a learning problem over functions into a problem over n coefficients.
• Derive, implement and tune kernel ridge regression and the support vector machine, including its dual and its optimality conditions.
• Run kernel PCA, kernel k-means, spectral clustering and kernel CCA, and explain the centering and regularization each one needs.
• Design kernels for strings, for whole graphs and for the nodes of a graph, and compute them by dynamic programming or matrix functions.
• Learn a combination of kernels by multiple kernel learning.
• Embed probability distributions in an RKHS and test whether two samples come from the same distribution.
• Scale kernel methods with the Nyström method and random features, and quantify what the approximation costs.
• Relate deep networks to kernels through arc-cosine kernels, convolutional kernel networks and the neural tangent kernel.

Official objectives and syllabus (2026–2027)

The course description on master-mva.com presents an introductory course on kernel methods for machine learning. It starts from an observation: many real-world problems are classical statistical problems, such as pattern recognition, regression or dimension reduction, but the data are often not vectors of numbers.

Its examples are protein sequences and structures in computational biology, text and XML documents in web mining, segmented pictures in image processing, and time series in speech recognition and finance. These objects carry structure that matters for the statistical problem but is hard to encode as a finite-dimensional vector.

According to the description, kernel methods extend statistical methods designed for vectors to virtually any type of data, without an explicit vectorization. The price is the definition of a positive definite kernel between the objects, which is formally equivalent to an implicit vectorization. The description notes that the design of kernels for various objects has advanced considerably and produced state-of-the-art algorithms in many domains.

The stated goal is to present the mathematical foundations of kernel methods and the main approaches to kernel design. The course starts with positive definite kernels and RKHS, which lead to kernel PCA and support vector machines. It then returns to the definition of the kernel, with the main results on Mercer kernels and semigroup kernels and examples of kernels for strings and graphs from computational biology, text processing and image analysis.

Finally it touches on active research topics such as large-scale kernel methods and deep kernel machines. The organisation announced is 9 sessions plus a final written exam, with a numerus clausus of 60 students. The Université Paris-Saclay programme table gives the volume (23 h of lectures); its course detail gives only the assessment type, with no programme of its own.

Every official topic has a section in these notes. The extensions beyond the syllabus are the review of ch. 0, the neural tangent kernel of ch. 10, and two self-study chapters: the complements of ch. 11 (a Rademacher bound, Gaussian processes, SVM solvers, the Fourier view of an RKHS, more sequence kernels, uses of mean embeddings) and the research directions of ch. 12.

Where this course fits in the programme

Official prerequisites: an introductory course on probability and an introductory course on computer programming and data structures. In practice the course also uses linear algebra (symmetric matrices), a little functional analysis (Hilbert spaces) and convex duality; ch. 0 reviews them.

• Refreshers — Probability and Statistics, Linear Algebra, Analysis and Optimization and Scientific Python cover the background of ch. 0 and the code.
• Semester 1 courses that prepare it — Introduction to Statistical Learning (convex risk minimization, complexity measures) and Convex Optimization (duality, used for the SVM). Theoretical Foundations of Deep Learning (risk bounds, Rademacher complexity, double descent) meets ch. 10 and 12. Optimal Transport offers another way to compare distributions than the MMD of ch. 8, and ALTEGRAD uses graph kernels.
• Related courses of semester 2 — Graphs in Machine Learning (Laplacians, spectral clustering), Bayesian Machine Learning (Bayesian nonparametrics; Gaussian processes, the Bayesian reading of KRR in ch. 11, use the same kernels), Large Random Matrices (kernel methods are among its applications), Protein Science (protein sequences and alignments, the data of the string kernels of ch. 7) and Learning Physical Phenomena (kriging metamodels).

Course outline

• 0. Review — positive semidefinite matrices, Hilbert spaces, projection and Riesz, Lagrange duality.
• 1. Positive definite kernels and the kernel trick — the definition, the closure properties, and how inner products become kernels.
• 2. Reproducing kernel Hilbert spaces — the canonical feature space, the Moore–Aronszajn theorem, smoothness.
• 3. Representer theorem and kernel ridge regression — from functions to coefficients, a closed-form estimator and its spectral reading.
• 4. Support vector machines — hinge loss, margin, dual problem, support vectors.
• 5. Unsupervised kernel methods — kernel PCA, kernel k-means and spectral clustering, kernel CCA.
• 6. Mercer, Bochner and semigroup kernels — the spectral theorems that characterize kernels, and kernels on histograms.
• 7. Kernels for strings and graphs, kernels on graphs — dynamic programming, walks, Weisfeiler–Lehman, diffusion.
• 8. Multiple kernel learning and kernel mean embeddings — learning the kernel; embedding distributions and testing two samples.
• 9. Large-scale learning with kernels — random features, Nyström, and how many features are enough.
• 10. Deep learning with kernels — compositional kernels, convolutional kernel networks, the neural tangent kernel.
• 11. Complements for self-study — a generalization bound, Gaussian processes, SVM solvers, the Fourier view of an RKHS, more sequence kernels, uses of mean embeddings.
• 12. Research directions and open problems — a self-study tour of current work.

Session plan

23 h in class = 9 sessions (1 × 3 h + 8 × 2.5 h). The volume of 23 h of lectures comes from the Université Paris-Saclay programme table, and master-mva.com announces 9 sessions plus a final written exam. The split below is a proposal: neither source gives the length of each session, nor says whether the 23 h include the exam.

Level 1 = foundations, 2 = core results and algorithms, 3 = advanced and research-level material. The level never goes down from one session to the next.

Self-study, outside the 23 h (about 6 h in total): ch. 11 Complements for self-study (≈ 2 h) · ch. 12 Research directions and open problems (≈ 4 h).

How to study this module

• Read ch. 0 before session 1 if Hilbert spaces or Lagrange duality feel distant; the rest of the page uses them without warning.
• After each session, do the exercises listed in its row, then run the code of the chapter and change one parameter (bandwidth, regularization, number of features) to see its effect.
• Implement the algorithms yourself at least once (kernel ridge regression, the SVM dual, kernel PCA) before using a library: each one is a few lines of NumPy.
• The code uses NumPy, SciPy, scikit-learn, NetworkX and PyTorch (CPU), with synthetic data or data sets bundled with scikit-learn; every block runs in a few seconds.
• The projects of the last section are sized like the official homework and data challenge; start one after session 4.

0. Review: Hilbert spaces, positive matrices and duality

Kernel methods compute with positive semidefinite matrices, live in Hilbert spaces and are trained by convex optimization. This chapter collects the M1-level facts used later.

The Linear Algebra, Analysis and Optimization refresher covers the same ground at a slower pace.

Positive semidefinite matrices

Hilbert spaces

Finite-dimensional subspaces are closed, so part 1 applies to the span of finitely many vectors, as in the representer theorem of ch. 3.

Lagrange duality

Consider a convex problem \min_x f_0(x) subject to g_i(x) \leq 0 for i = 1, \dots, m, with f_0 and g_i convex.

1. Positive definite kernels and the kernel trick

Many learning algorithms use the data only through inner products \langle x_i, x_j \rangle. Positive definite kernels are the functions that can replace them, turning linear algorithms into non-linear ones on any set of objects.

The name is a historical convention: a p.d. kernel only needs PSD Gram matrices, not positive definite ones.

With \varphi(x) = x this gives the linear kernel K(x, y) = x^\top y. Chapter 2 proves the converse; on a finite set it is already visible.

Building kernels

The kernel trick

The kernel trick is the following recipe. Write an algorithm for vectors so that it uses the data only through inner products x_i^\top x_j; then replace each of them by K(x_i, x_j). The new algorithm runs the old one on the feature vectors \varphi(x_i), without ever computing them.

Distances also kernelize. Expanding the squared norm gives \|\varphi(x) - \varphi(y)\|^2 = K(x, x) + K(y, y) - 2 K(x, y) .

The kernel mean classifier assigns x to the class with the closest feature-space mean; with the linear kernel it is the nearest-centroid rule:

import numpy as np
from sklearn.datasets import make_moons

def gauss(A, B, s):
    d2 = (A**2).sum(1)[:, None] + (B**2).sum(1)[None, :] - 2 * A @ B.T
    return np.exp(-d2 / (2 * s**2))

X, y = make_moons(n_samples=600, noise=0.15, random_state=0)
Xtr, ytr, Xte, yte = X[:300], y[:300], X[300:], y[300:]

def mean_classifier(kern):
    scores = []
    for c in (0, 1):
        C = Xtr[ytr == c]
        # K(x,x) is the same for both classes and cancels; keep the rest
        d = -2 * kern(Xte, C).mean(1) + kern(C, C).mean()
        scores.append(d)
    return np.argmin(np.vstack(scores), axis=0)

lin = lambda A, B: A @ B.T
print("linear  :", (mean_classifier(lin) == yte).mean())
print("gaussian:", (mean_classifier(lambda A, B: gauss(A, B, 0.3)) == yte).mean())

The term K(x, x) is the same for both classes and cancels. On the two moons, the Gaussian kernel raises the test accuracy from 0.84 to 0.98.

Kernels also apply to objects that are not vectors. For finite subsets A, B of a set, K(A, B) = |A \cap B| is the inner product of their indicator vectors, hence p.d.; counting shared words between documents is the bag-of-words kernel.

2. Reproducing kernel Hilbert spaces

The feature space of a kernel is not unique, but one choice is canonical: a Hilbert space of functions in which evaluation is an inner product with the kernel. The estimators of ch. 3–5 live there, and its norm measures their smoothness.

Convergence in an RKHS implies pointwise convergence. L^2([0, 1]) is not an RKHS: evaluation at a point is not defined on its elements.

From a kernel to its RKHS

The norm measures smoothness

A function of small norm varies little between points that the kernel finds similar: regularizing by \|f\|_{\mathcal{H}_K}^2 is a smoothness prior defined by the kernel.

For f = \sum_i a_i K_{x_i}, the RKHS norm is a quadratic form in the coefficients: \|f\|_{\mathcal{H}_K}^2 = a^\top K a .

The code checks this against the energy \int f'^2 for the min kernel:

import numpy as np

rng = np.random.default_rng(0)
x = np.sort(rng.uniform(0, 1, 5))           # centres x_i
a = rng.normal(size=5)                       # coefficients a_i
K = np.minimum.outer(x, x)                   # Gram matrix of min(x, y)
norm_from_gram = a @ K @ a

t = np.linspace(0, 1, 200001)
fprime = sum(ai * (t <= xi) for ai, xi in zip(a, x))   # f' = sum a_i 1[0, x_i]
energy = np.trapezoid(fprime**2, t) if hasattr(np, "trapezoid") else np.trapz(fprime**2, t)
print(f"a^T K a = {norm_from_gram:.5f},  integral of f'^2 = {energy:.5f}")

3. The representer theorem and kernel ridge regression

Learning in an RKHS minimizes a risk over a usually infinite-dimensional space of functions. The representer theorem reduces it to n unknowns; kernel ridge regression is the simplest instance.

Throughout, the data are pairs (x_1, y_1), \dots, (x_n, y_n) with x_i \in \mathcal{X}, the Gram matrix is K = [K(x_i, x_j)]_{i,j}, and \mathcal{H} = \mathcal{H}_K.

The theorem goes back to Kimeldorf and Wahba (1971); the general form is due to Schölkopf, Herbrich and Smola (2001). It does not assert existence, which holds for convex losses and \Psi coercive in \|f\|.

With f = \sum_i \alpha_i K_{x_i}, both ingredients of J are explicit: \big(f(x_1), \dots, f(x_n)\big) = K\alpha, \qquad \|f\|_{\mathcal{H}}^2 = \alpha^\top K \alpha .

Kernel ridge regression

Kernel ridge regression (KRR) minimizes the regularized empirical squared error, with a regularization parameter \lambda > 0: \min_{f \in \mathcal{H}}\; \frac{1}{n} \sum_{i=1}^n \big(y_i - f(x_i)\big)^2 + \lambda\, \|f\|_{\mathcal{H}}^2 .

Regularization as spectral filtering

Write the eigendecomposition K = \sum_i \mu_i u_i u_i^\top. The fitted values \hat y = K\alpha are a linear smoother of the targets.

For smooth kernels the eigenvalues decay fast and the eigenvectors with small \mu_i oscillate (ch. 6). KRR keeps the smooth components of y and damps the rough ones; \mathrm{df}(\lambda) counts those kept.

The code fits KRR from scratch, checks it against scikit-learn (whose alpha is n\lambda) and prints the effective degrees of freedom:

import numpy as np
from sklearn.kernel_ridge import KernelRidge

rng = np.random.default_rng(0)
n = 80
x = np.sort(rng.uniform(-3, 3, n))
y = np.sin(2 * x) + 0.3 * rng.normal(size=n)
xt = np.linspace(-3, 3, 400)
yt = np.sin(2 * xt)

def gauss(a, b, s=0.5):
    return np.exp(-(a[:, None] - b[None, :]) ** 2 / (2 * s**2))

K = gauss(x, x)
mu = np.linalg.eigvalsh(K)
for lam in [1e-4, 1e-2, 1.0]:
    alpha = np.linalg.solve(K + n * lam * np.eye(n), y)
    pred = gauss(xt, x) @ alpha
    df = np.sum(mu / (mu + n * lam))
    sk = KernelRidge(alpha=n * lam, kernel="rbf", gamma=1 / (2 * 0.5**2)).fit(x[:, None], y)
    gap = np.abs(sk.predict(xt[:, None]) - pred).max()
    print(f"lambda={lam:g}: test MSE={np.mean((pred - yt) ** 2):.4f}, df={df:.1f}, |ours-sklearn|={gap:.1e}")

The middle \lambda is best: the smallest spends 16 effective parameters fitting noise, the largest keeps less than one and oversmooths.

4. Support vector machines

The support vector machine (SVM) is regularized learning in an RKHS with the hinge loss. Its dual involves only the Gram matrix, and its solution depends only on a few training points, the support vectors.

Labels are now y_i \in \{-1, +1\}, and the classifier is the sign of g(x) = f(x) + b, with f \in \mathcal{H} and an unpenalized offset b \in \mathbb{R}.

The dual problem

The code reproduces the introduction’s comparison, then checks Proposition 4.4 on the dual solution:

import numpy as np
from sklearn.datasets import make_moons
from sklearn.svm import SVC

X, y01 = make_moons(n_samples=600, noise=0.15, random_state=0)
y = 2 * y01 - 1                                   # labels in {-1, +1}
Xtr, ytr, Xte, yte = X[:300], y[:300], X[300:], y[300:]

def gauss(A, B, s=0.5):
    d2 = (A**2).sum(1)[:, None] + (B**2).sum(1)[None, :] - 2 * A @ B.T
    return np.exp(-d2 / (2 * s**2))

C = 1.0
for name, ker in [("linear", lambda A, B: A @ B.T), ("gaussian", gauss)]:
    svm = SVC(kernel="precomputed", C=C).fit(ker(Xtr, Xtr), ytr)
    print(f"{name:8s} test accuracy {svm.score(ker(Xte, Xtr), yte):.3f}, "
          f"{len(svm.support_)} support vectors")

# KKT check for the Gaussian SVM: alpha_i * y_i are stored in dual_coef_
alpha = np.abs(svm.dual_coef_.ravel())
idx = svm.support_
g = svm.decision_function(gauss(Xtr, Xtr))
free = (alpha > 1e-6) & (alpha < C - 1e-6)
print("sum alpha_i y_i  =", round(float(alpha @ ytr[idx]), 8))
print("y g(x) on free SVs: min %.3f, max %.3f" % ((ytr[idx] * g[idx])[free].min(),
                                                   (ytr[idx] * g[idx])[free].max()))
nonsv = np.setdiff1d(np.arange(300), idx)
print("min y g(x) off the support:", round(float((ytr[nonsv] * g[nonsv]).min()), 3))

Free support vectors sit at y\, g(x) = 1 up to solver tolerance, and all other points have y\, g(x) \geq 1.

5. Unsupervised kernel methods: kernel PCA, kernel k-means, kernel CCA

PCA, k-means and canonical correlation analysis use the data only through inner products and distances, so the kernel trick applies to each. Two details need care: centering in feature space, and regularization for CCA.

Kernel PCA

Kernel PCA (Schölkopf, Smola and Müller, 1998) runs PCA on the centred features \tilde\varphi(x_i) = \varphi(x_i) - \frac{1}{n} \sum_{j=1}^n \varphi(x_j) . Their Gram matrix is the centred Gram matrix K_c = H K H, \qquad H = I - \frac{1}{n} \mathbf{1}\mathbf{1}^\top .

The directions found are curved in the input space. Mapping a feature-space point back to the input space (the pre-image problem) has no exact solution in general.

Kernel k-means and spectral clustering

Kernel k-means minimizes, over partitions into clusters c_1, \dots, c_k, the within-cluster scatter in feature space: W(c_1, \dots, c_k) = \sum_{l=1}^k \sum_{i \in c_l} \big\| \varphi(x_i) - m_l \big\|^2, \qquad m_l = \frac{1}{|c_l|} \sum_{j \in c_l} \varphi(x_j) .

Applied to a normalized affinity matrix D^{-1/2} W D^{-1/2}, the same relaxation gives the algorithm of Ng, Jordan and Weiss (2002); Dhillon, Guan and Kulis (2004) show that normalized cut is a weighted kernel k-means objective. See also Graphs in Machine Learning.

Kernel CCA

CCA looks for maximally correlated projections of two views (x_i, y_i) of the same objects, such as an image and its caption. Kernel CCA uses functions f \in \mathcal{H}_1 and g \in \mathcal{H}_2.

A correlation of 1 for any data carries no information. The remedy (Bach and Jordan, 2002) penalizes the RKHS norms, replacing each variance \alpha^\top K_1^2 \alpha by \alpha^\top (K_1 + \gamma I)^2 \alpha, which adds 2\gamma \|f\|^2 + \gamma^2 \|\alpha\|^2.

The matrices R_j are the smoother matrices of kernel ridge regression (Proposition 3.4). As \gamma \to 0 they tend to projections and the correlation tends to 1, which is Proposition 5.6 again.

The code runs kernel PCA, spectral clustering and kernel k-means on the circles, then kernel CCA on two non-linearly related views:

import numpy as np
from sklearn.datasets import make_circles
from sklearn.decomposition import KernelPCA
from sklearn.cluster import KMeans
from sklearn.linear_model import LogisticRegression
from sklearn.metrics import adjusted_rand_score as ari

X, y = make_circles(n_samples=400, factor=0.3, noise=0.05, random_state=0)
n, s = len(X), 0.25
K = np.exp(-((X[:, None] - X[None]) ** 2).sum(-1) / (2 * s**2))

# kernel PCA (Proposition 5.1)
H = np.eye(n) - np.ones((n, n)) / n
mu, U = np.linalg.eigh(H @ K @ H)
mu, U = mu[::-1], U[:, ::-1]
pc = U[:, :2] * np.sqrt(mu[:2])
sk = KernelPCA(2, kernel="rbf", gamma=1 / (2 * s**2)).fit_transform(X)
print("same as sklearn up to sign:", np.allclose(np.abs(pc), np.abs(sk), atol=1e-6))
lr = lambda F: LogisticRegression().fit(F, y).score(F, y)
print("linear separability: raw %.2f, first kernel PC %.2f" % (lr(X), lr(pc[:, :1])))

# kernel k-means (Algorithm 5.3) and spectral relaxation (Proposition 5.4)
def kernel_kmeans(K, k, lab):
    while True:
        D = np.stack([np.diag(K) - 2 * K[:, lab == c].mean(1)
                      + K[np.ix_(lab == c, lab == c)].mean() for c in range(k)], 1)
        if np.array_equal(D.argmin(1), lab):
            return lab
        lab = D.argmin(1)

d = K.sum(1)
V = np.linalg.eigh(K / np.sqrt(np.outer(d, d)))[1][:, -2:]          # normalized relaxation
V /= np.linalg.norm(V, axis=1, keepdims=True)
spec = KMeans(2, n_init=10, random_state=0).fit_predict(V)
rand = kernel_kmeans(K, 2, np.random.default_rng(0).integers(0, 2, n))
print("ARI: kernel k-means from random start %.2f, spectral %.2f, kernel k-means from spectral %.2f"
      % (ari(y, rand), ari(y, spec), ari(y, kernel_kmeans(K, 2, spec.copy()))))

import numpy as np

rng = np.random.default_rng(0)
def views(n):
    x = rng.uniform(-1, 1, n)
    return x, x**2 + 0.1 * rng.normal(size=n)       # y depends on x, but not linearly
x, y = views(200)
xt, yt = views(200)                                  # held-out pairs
gram = lambda a, b, s=0.1: np.exp(-(a[:, None] - b[None, :]) ** 2 / (2 * s**2))

def centre(K, Ktr):          # centre K[i, t] = k(train_i, point_t) with training means
    return K - K.mean(0) - Ktr.mean(1)[:, None] + Ktr.mean()

def kcca(gamma):             # Proposition 5.7
    n = len(x)
    K1, K2 = gram(x, x), gram(y, y)
    K1c, K2c = centre(K1, K1), centre(K2, K2)
    A1, A2 = K1c + gamma * np.eye(n), K2c + gamma * np.eye(n)
    U, s, Vt = np.linalg.svd(np.linalg.solve(A1, K1c) @ np.linalg.solve(A2, K2c))
    alpha, beta = np.linalg.solve(A1, U[:, 0]), np.linalg.solve(A2, Vt[0])
    f = centre(gram(x, xt), K1).T @ alpha            # f on held-out points
    g = centre(gram(y, yt), K2).T @ beta
    return s[0], abs(np.corrcoef(f, g)[0, 1])

print("linear correlation of (x, y): %.3f" % abs(np.corrcoef(x, y)[0, 1]))
for gamma in [1e-10, 1e-3, 1e-1]:
    train, test = kcca(gamma)
    print(f"gamma={gamma:g}: training correlation {train:.3f}, held-out {test:.3f}")

Kernel k-means from a random start stops at a poor local minimum (adjusted Rand index 0.37); the spectral relaxation finds the circles (1.00), and kernel k-means started there keeps them.

For kernel CCA, the linear correlation of the views is 0.08. With a negligible \gamma = 10^{-10}, the training correlation is 0.98, close to the value 1 of Proposition 5.6, but the held-out one is 0.02. With \gamma = 10^{-3} or 10^{-1}, the held-out correlation stays at 0.94–0.95.

6. Mercer, Bochner and semigroup kernels

Choosing a kernel means choosing an RKHS, that is, a notion of smoothness. Three theorems recognize p.d. kernels and describe their RKHS: Mercer’s on compact domains, Bochner’s for translation-invariant kernels, and Schoenberg’s for kernels built from distances, which leads to kernels on histograms.

Mercer kernels

Let \mathcal{X} be a compact metric space, \mu a finite Borel measure whose support is \mathcal{X}, and K a continuous p.d. kernel. The integral operator of K acts on L^2(\mu): (T_K f)(x) = \int_{\mathcal{X}} K(x, t)\, f(t)\, d\mu(t) . It is compact, self-adjoint, and positive: \langle f, T_K f \rangle_{L^2} \geq 0.

Eigenfunctions with small eigenvalues, typically the oscillating ones, are expensive in RKHS norm. This is the continuous version of Proposition 3.4: the eigenvalues of K / n approximate the \lambda_k when the x_i are drawn from \mu.

Translation-invariant kernels

Bochner’s theorem characterizes the p.d. kernels of the form K(x, y) = \kappa(x - y) on \mathbb{R}^d.

Examples: the Gaussian kernel e^{-\|z\|^2 / 2\sigma^2} corresponds to a Gaussian measure \Lambda with covariance \sigma^{-2} I; the Laplace kernel e^{-|z| / \sigma} on \mathbb{R} corresponds to a Cauchy measure. Sampling \omega \sim \Lambda is the basis of the random features of ch. 9.

Negative definite and semigroup kernels

Schoenberg’s theorem says when exponentiating a distance or a divergence gives a p.d. kernel.

With \psi = \|x - y\|^2 this proves again that the Gaussian kernel is p.d. Moreover \|x - y\|^p is n.d. for 0 < p \leq 2, so e^{-t \|x - y\|^p} is p.d.; it is not for p > 2, and the code exhibits a negative eigenvalue for p = 3.

Data such as histograms and measures form a semigroup (S, +), for instance S = \mathbb{R}_+^d. A semigroup kernel has the form K(x, y) = \phi(x + y), as in Berg, Christensen and Ressel (1984).

Under regularity conditions, every bounded p.d. function on this semigroup has this form (Berg, Christensen and Ressel). For instance 1 / (x + y) = \int_0^\infty e^{-t(x + y)} dt is p.d. on (0, \infty).

These kernels were the standard tool of image classification with bags of visual words, histograms of quantized local descriptors (Zhang, Marszałek, Lazebnik and Schmid, 2007). Cuturi, Fukumizu and Vert (2005) extend the construction to measures.

The code checks Example 6.3 and the positivity claims of this section:

import numpy as np

# Mercer eigenvalues of min(x, y) on [0, 1]: K / m on a grid approximates T_K
m = 2000
t = (np.arange(m) + 0.5) / m
lam = np.linalg.eigvalsh(np.minimum.outer(t, t) / m)[::-1][:4]
print("from the Gram matrix:", np.round(lam, 4))
print("Mercer eigenvalues  :", np.round(1 / ((np.arange(1, 5) - 0.5) ** 2 * np.pi**2), 4))

# kernels on histograms (Proposition 6.8), and exp(-|x-y|^p) for p = 1.5 and 3
rng = np.random.default_rng(0)
Hs = rng.dirichlet(np.ones(10), size=200)          # 200 histograms with 10 bins
chi2 = (((Hs[:, None] - Hs[None]) ** 2) / (Hs[:, None] + Hs[None] + 1e-12)).sum(-1)
inter = np.minimum(Hs[:, None], Hs[None]).sum(-1)
z = np.linspace(0, 3, 40)
dist = np.abs(z[:, None] - z[None])
for name, G in [("exp(-chi2)", np.exp(-chi2)), ("intersection", inter),
                ("exp(-|x-y|^1.5)", np.exp(-dist**1.5)), ("exp(-|x-y|^3)", np.exp(-dist**3))]:
    print(f"{name:16s} smallest eigenvalue {np.linalg.eigvalsh(G).min():+.2e}")

7. Kernels for strings and graphs, kernels on graphs

Sequences and graphs motivated kernel methods in computational biology, text processing and chemistry. This chapter builds kernels for them by counting substructures and by diffusing along a graph, and shows that some natural kernels are intractable.

Kernels for strings

Let \mathcal{A} be a finite alphabet (4 nucleotides, 20 amino acids, or letters) and \mathcal{X} = \mathcal{A}^* the set of finite strings.

Enumerating the occurrences costs \binom{|s|}{p} operations; a dynamic program avoids it. Write sa for the string s followed by the letter a, and t[1{:}j] for the prefix of length j.

Kernels for graphs

A kernel for graphs compares two graphs, for instance two molecules. A feature map that identifies graphs up to isomorphism is out of reach.

Practical graph kernels therefore count simpler substructures: walks, paths or subtrees. Let G and G' have vertex labels (atom types, for instance).

The kernel is fast and strong on molecule benchmarks, but graphs that the 1-dimensional Weisfeiler–Lehman isomorphism test cannot tell apart get the same features. Message-passing graph neural networks share this limit (Xu, Hu, Leskovec and Jegelka, 2019; Morris et al., 2019).

Graph kernels also serve image analysis. A segmented image is a graph whose vertices are regions, labelled by their colour histograms and joined when the regions touch. Harchaoui and Bach (2007) compare such segmentation graphs with walk-based kernels, using a histogram kernel of ch. 6 between the labels of matched regions, and classify the images with an SVM.

Kernels on graphs

A kernel on a graph compares the vertices of one graph, for instance genes in an interaction network; it is an n \times n PSD matrix. Recall that the Laplacian L = D - A is PSD, with quadratic form f^\top L f = \sum_{uv \in E} (f_u - f_v)^2 .

Regression with these kernels spreads labels known on a few vertices to their neighbours; Vert and Kanehisa (2003) used diffusion kernels on gene networks.

The code checks Example 7.2 and Proposition 7.4 against brute force:

import itertools
from functools import lru_cache
from collections import Counter

def spectrum(x, y, k):
    cx = Counter(x[i:i + k] for i in range(len(x) - k + 1))
    cy = Counter(y[i:i + k] for i in range(len(y) - k + 1))
    return sum(c * cy[u] for u, c in cx.items())

print("2-spectrum kernel of Example 7.2:", spectrum("ACGTACG", "TACGT", 2))

def subseq_brute(s, t, p, lam):        # Definition 7.3, by enumeration
    def phi(x):
        f = Counter()
        for idx in itertools.combinations(range(len(x)), p):
            f["".join(x[i] for i in idx)] += lam ** (idx[-1] - idx[0] + 1)
        return f
    fs, ft = phi(s), phi(t)
    return sum(v * ft[u] for u, v in fs.items())

def subseq_dp(s, t, p, lam):           # Proposition 7.4, on prefixes s[:a], t[:b]
    @lru_cache(maxsize=None)
    def Kp(i, a, b):
        if i == 0:
            return 1.0
        if min(a, b) < i:
            return 0.0
        r = lam * Kp(i, a - 1, b)
        for j in range(1, b + 1):
            if t[j - 1] == s[a - 1]:
                r += Kp(i - 1, a - 1, j - 1) * lam ** (b - j + 2)
        return r
    @lru_cache(maxsize=None)
    def K(a, b):
        if min(a, b) < p:
            return 0.0
        r = K(a - 1, b)
        for j in range(1, b + 1):
            if t[j - 1] == s[a - 1]:
                r += Kp(p - 1, a - 1, j - 1) * lam ** 2
        return r
    return K(len(s), len(t))

for s, t in [("cat", "cart"), ("science", "silence"), ("ACGTTGCA", "ACTTGGCA")]:
    print(f"{s:8s} {t:8s} brute {subseq_brute(s, t, 3, 0.7):.10f}  dp {subseq_dp(s, t, 3, 0.7):.10f}")

The second block compares graph kernels on four small graphs, then classifies the vertices of a two-community graph from four labels:

import numpy as np
import networkx as nx
from collections import Counter
from scipy.linalg import expm

def wl_features(G, H=3):               # Algorithm 7.7 (labels kept as strings)
    lab = {v: str(G.degree(v)) for v in G}
    feats = Counter(("0", l) for l in lab.values())
    for h in range(1, H + 1):
        lab = {v: lab[v] + "|" + ",".join(sorted(lab[u] for u in G[v])) for v in G}
        feats.update((str(h), l) for l in lab.values())
    return feats

def wl_kernel(G1, G2):
    f1, f2 = wl_features(G1), wl_features(G2)
    return sum(c * f2[k] for k, c in f1.items())

def walk_kernel(G1, G2, lam=0.1):      # Definition 7.6, unlabelled graphs
    Ax = np.kron(nx.to_numpy_array(G1), nx.to_numpy_array(G2))
    one = np.ones(len(Ax))
    return one @ np.linalg.solve(np.eye(len(Ax)) - lam * Ax, one)

graphs = {"2 triangles": nx.disjoint_union(nx.cycle_graph(3), nx.cycle_graph(3)),
          "hexagon": nx.cycle_graph(6), "path": nx.path_graph(6), "star": nx.star_graph(5)}
names = list(graphs)
for kern in (wl_kernel, walk_kernel):
    M = np.array([[kern(graphs[a], graphs[b]) for b in names] for a in names])
    M = M / np.sqrt(np.outer(np.diag(M), np.diag(M)))   # normalized kernel
    print(kern.__name__, names, "\n", np.round(M, 2))

G = nx.stochastic_block_model([50, 50], [[0.2, 0.02], [0.02, 0.2]], seed=0)
Kd = expm(-0.5 * nx.laplacian_matrix(G).toarray().astype(float))   # Definition 7.8
y = np.r_[np.ones(50), -np.ones(50)]
known = np.array([0, 1, 50, 51])                                      # four labels
alpha = np.linalg.solve(Kd[np.ix_(known, known)] + 0.01 * np.eye(4), y[known])
pred = np.sign(Kd[:, known] @ alpha)
print("diffusion kernel: smallest eigenvalue %.1e, accuracy %.2f"
      % (np.linalg.eigvalsh(Kd).min(), (pred == y).mean()))

Both graph kernels give similarity 1.00 between two triangles and a hexagon, two 2-regular graphs with 6 vertices; counting triangles, \mathrm{tr}(A^3)/6, separates them. With the diffusion kernel, 99 % of the vertices are labelled correctly.

8. Multiple kernel learning and kernel mean embeddings

Multiple kernel learning chooses the kernel itself, as a combination of candidate kernels learned with the predictor. Kernel mean embeddings represent probability distributions as points of an RKHS, which gives a distance between distributions, the MMD, and a two-sample test.

Multiple kernel learning

Given kernels K_1, \dots, K_M (one per data source, per feature group, or per bandwidth), consider the combinations K_\eta = \sum_{m=1}^M \eta_m K_m, \qquad \eta \in \Delta_M = \Big\{ \eta \geq 0,\; \sum_m \eta_m = 1 \Big\} . Multiple kernel learning (MKL; Lanckriet et al., 2004; Bach, Lanckriet and Jordan, 2004) minimizes the regularized risk jointly over \eta and f \in \mathcal{H}_{K_\eta}.

The penalty \sum_m \|f_m\| is a block \ell^1 norm, as in the group lasso. At the optimum many blocks vanish, together with their weights \eta_m: MKL selects kernels.

Gradient methods on the simplex therefore solve MKL; SimpleMKL (Rakotomamonjy, Bach, Canu and Grandvalet, 2008) uses an SVM in the inner loop. The code uses exponentiated gradient, with one kernel per input feature; the target ignores feature 3:

import numpy as np

rng = np.random.default_rng(0)
n, lam = 200, 1e-2
X = rng.uniform(-2, 2, size=(n, 3))                 # feature 3 is pure noise
y = np.sin(2 * X[:, 0]) + 0.5 * X[:, 1] ** 2 + 0.1 * rng.normal(size=n)
y = y - y.mean()
gram = lambda a: np.exp(-(a[:, None] - a[None, :]) ** 2 / 2)
Ks = [gram(X[:, m]) for m in range(3)]              # one kernel per feature

def J_and_grad(eta):                                 # Proposition 8.3
    alpha = np.linalg.solve(sum(e * K for e, K in zip(eta, Ks)) + n * lam * np.eye(n), y)
    return lam * y @ alpha, np.array([-lam * alpha @ K @ alpha for K in Ks])

eta = np.ones(3) / 3
for it in range(300):                                # exponentiated gradient on the simplex
    J, g = J_and_grad(eta)
    eta = eta * np.exp(-g / np.abs(g).max())
    eta /= eta.sum()
    if it in (0, 10, 299):
        print(f"iteration {it:3d}: J = {J:.4f}, eta = {np.round(eta, 3)}")

The weights converge to about (0.63, 0.37, 0), the minimum found by a grid search: the noise kernel is switched off.

Kernel mean embeddings

Let K be a measurable kernel with \sup_x K(x, x) = \kappa^2 < \infty.

With the linear kernel, \mathrm{MMD}(P, Q) = \|\mathbb{E} X - \mathbb{E} Y\| compares only the means. A kernel is characteristic when P \mapsto \mu_P is injective, so that \mathrm{MMD}(P, Q) = 0 forces P = Q.

The kernel two-sample test (Gretton, Borgwardt, Rasch, Schölkopf and Smola, 2012) rejects P = Q when the statistic is large. Under the null hypothesis the pooled sample is exchangeable, so permutations give an exact p-value.

import numpy as np
from scipy import stats

rng = np.random.default_rng(0)

def mmd2_u(K, m):                     # Proposition 8.7 from the Gram matrix of [x; y]
    Kxx, Kyy, Kxy = K[:m, :m], K[m:, m:], K[:m, m:]
    n = len(K) - m
    return ((Kxx.sum() - np.trace(Kxx)) / (m * (m - 1))
            + (Kyy.sum() - np.trace(Kyy)) / (n * (n - 1)) - 2 * Kxy.mean())

def mmd_test(x, y, n_perm=500):
    z = np.r_[x, y]
    d2 = (z[:, None] - z[None, :]) ** 2
    K = np.exp(-d2 / (2 * np.median(d2[d2 > 0])))  # Gaussian kernel, median heuristic
    stat = mmd2_u(K, len(x))
    null = [mmd2_u(K[np.ix_(p, p)], len(x))
            for p in (rng.permutation(len(z)) for _ in range(n_perm))]
    return stat, (1 + np.sum(np.array(null) >= stat)) / (1 + n_perm)

m = 200
x = rng.normal(0, 1, m)
for name, y in [("N(0,1) vs N(0,1)", rng.normal(0, 1, m)),
                ("N(0,1) vs Laplace", rng.laplace(0, 1 / np.sqrt(2), m))]:  # same mean and variance
    stat, p = mmd_test(x, y)
    print(f"{name:18s}: MMD^2_u = {stat:+.4f}, permutation p = {p:.3f}, "
          f"t-test p = {stats.ttest_ind(x, y).pvalue:.2f}")

With equal means and variances, a t-test sees nothing (p = 0.64); the MMD test detects the Laplace shape (p = 0.002) and does not reject for two Gaussian samples (p = 0.13).

9. Large-scale learning with kernels

Exact kernel methods need O(n^2) memory and O(n^3) time; with n = 10^5 points the Gram matrix alone takes 80 GB. This chapter replaces it by low-rank approximations, random features or Nyström, and states how small the rank can be without losing accuracy.

Both methods build an explicit feature map z : \mathcal{X} \to \mathbb{R}^D with z(x)^\top z(y) \approx K(x, y). KRR then becomes ridge regression on z, with weights w = (Z^\top Z + n\lambda I_D)^{-1} Z^\top y, where Z \in \mathbb{R}^{n \times D} stacks the z(x_i)^\top. This costs O(nD^2 + D^3) time and O(nD) memory.

Random Fourier features

Let K(x, y) = \kappa(x - y) with \kappa(0) = 1. By Bochner’s theorem (Theorem 6.4), \Lambda is then a probability distribution, and since it is symmetric, \kappa(z) = \mathbb{E}_{\omega \sim \Lambda} \cos(\omega^\top z) .

For the Gaussian kernel, \Lambda = \mathcal{N}(0, \sigma^{-2} I): the features form a one-hidden-layer network with random, fixed first-layer weights.

A union bound over a net extends this to all pairs in a compact set of diameter \ell. A number of features D of order d\, \varepsilon^{-2} \log(\sigma_\Lambda \ell / \varepsilon) gives a uniform error \varepsilon, where \sigma_\Lambda^2 is the second moment of \Lambda (Rahimi and Recht, 2007). The error decreases only like D^{-1/2}, which is why the statistical analysis below matters.

The Nyström method

The Nyström method (Williams and Seeger, 2001) picks m landmarks \tilde x_1, \dots, \tilde x_m, usually a uniform subsample. With K_{nm} the kernel between data and landmarks and K_{mm} among landmarks, it approximates K \approx \tilde K = K_{nm}\, K_{mm}^{+}\, K_{mn} .

FALKON (Rudi, Carratino and Rosasco, 2017) solves this problem by preconditioned conjugate gradient, in about O(n \sqrt{n}) time and O(n) memory.

How many features are enough?

The rank acts as a second regularization parameter.

import time
import numpy as np

rng = np.random.default_rng(0)
d, n, s, lam = 5, 3000, 1.5, 1e-4
f_star = lambda X: np.sin(X[:, 0]) + np.cos(X[:, 1] * X[:, 2]) + 0.5 * X[:, 3]
X, Xt = rng.normal(size=(n, d)), rng.normal(size=(1000, d))
y = f_star(X) + 0.2 * rng.normal(size=n)

def gauss(A, B):
    d2 = (A**2).sum(1)[:, None] + (B**2).sum(1)[None, :] - 2 * A @ B.T
    return np.exp(-d2 / (2 * s**2))

def report(name, pred, t0):
    err = np.mean((pred - f_star(Xt)) ** 2)
    print(f"{name:22s} test MSE {err:.4f}   time {time.time() - t0:.2f} s")

t0 = time.time()                                       # exact KRR: O(n^3)
alpha = np.linalg.solve(gauss(X, X) + n * lam * np.eye(n), y)
report("exact KRR", gauss(Xt, X) @ alpha, t0)

for D in [50, 200, 800]:
    t0 = time.time()                                   # random Fourier features
    W, b = rng.normal(scale=1 / s, size=(d, D)), rng.uniform(0, 2 * np.pi, D)
    z = lambda A: np.sqrt(2 / D) * np.cos(A @ W + b)
    Z = z(X)
    w = np.linalg.solve(Z.T @ Z + n * lam * np.eye(D), Z.T @ y)
    report(f"random features D={D}", z(Xt) @ w, t0)

    t0 = time.time()                                   # Nystrom KRR, Proposition 9.4
    land = X[rng.choice(n, D, replace=False)]
    Knm, Kmm = gauss(X, land), gauss(land, land)
    beta = np.linalg.solve(Knm.T @ Knm + n * lam * Kmm + 1e-8 * np.eye(D), Knm.T @ y)
    report(f"Nystrom m={D}", gauss(Xt, land) @ beta, t0)

With n = 3000, exact KRR is by far the slowest and reaches a test error of 0.024. Nyström with m = 800 nearly matches it (0.025) in a fraction of the time; random features, sampled independently of the data, reach 0.036 at D = 800.

10. Deep learning with kernels

Kernels and neural networks meet in two ways. Multilayer kernels, once approximated, are networks: convolutional kernel networks. Conversely, infinitely wide random networks are kernel machines: the arc-cosine kernel and the neural tangent kernel.

Compositional and arc-cosine kernels

Iterating gives a multilayer kernel K_{l+1} computed from K_l alone. The Gaussian kernel restricted to the unit sphere is of this form, since there e^{-\|u - v\|^2 / 2\sigma^2} = e^{(\langle u, v \rangle - 1)/\sigma^2} .

If the output weights are also Gaussian, the network output is, in the limit of infinite width, a Gaussian process with this covariance (Neal, 1996). The same holds for deep networks with the compositional recursion above (Lee et al., 2018).

Convolutional kernel networks

An image is a map x : \Omega \to \mathbb{R}^p on a grid, whose value at each position is a patch. A convolutional kernel compares all pairs of patches with a dot-product kernel, and its feature map is approximated by projection, as in ch. 9.

By Proposition 9.3, \psi(z)^\top \psi(z') is the Nyström approximation of k(z, z') with landmarks z_j: here K_{mm} = \kappa(Z^\top Z) and k_m(z) = \|z\|\, \kappa(Z^\top \tilde z). The layer is therefore a CNN layer in disguise:

• a convolution with the filters z_j;
• a pointwise non-linearity \kappa;
• a 1 \times 1 linear map \kappa(Z^\top Z)^{-1/2};
• pooling.

The anchors can be learned without labels (k-means on patches) or end-to-end by back-propagation, which gives the supervised CKN of Mairal (2016).

Bietti and Mairal (2019a) show that these representations are stable to small deformations, and that the RKHS norm controls the complexity of CNNs.

The neural tangent kernel

Let f(x; \theta) be a network with parameters \theta \in \mathbb{R}^p, initialized at \theta_0. Its neural tangent kernel (NTK) is the kernel of the feature map \nabla_\theta f(x; \theta_0), p.d. by Proposition 1.2: \Theta(x, x') = \big\langle \nabla_\theta f(x; \theta_0),\; \nabla_\theta f(x'; \theta_0) \big\rangle .

Jacot, Gabriel and Hongler (2018) show that, as the width grows with a suitable scaling, the NTK becomes deterministic and constant during training: the trained network is the kernel regressor above.

Chizat, Oyallon and Bach (2019) show that this lazy regime, in which the features barely move, is an effect of the scaling of the model. Networks that leave it and learn features can outperform any fixed kernel (ch. 12).

The code checks Theorem 10.2 by Monte Carlo, and Example 10.5 with PyTorch on a network of width 20,000:

import numpy as np
import torch

torch.manual_seed(0)
d, m = 3, 20000
X = torch.randn(5, d, dtype=torch.float64)

def arccos_terms(X):                       # the two formulas of Theorem 10.2
    nrm = X.norm(dim=1)
    cos = (X @ X.T / torch.outer(nrm, nrm)).clamp(-1, 1)
    th = torch.arccos(cos)
    k1 = torch.outer(nrm, nrm) * (torch.sin(th) + (np.pi - th) * cos) / (2 * np.pi)
    return k1, (np.pi - th) / (2 * np.pi)

k1, k0 = arccos_terms(X)
F = torch.relu(X @ torch.randn(d, 200000, dtype=torch.float64))
print("arc-cosine kernel: max |Monte Carlo - formula| = %.4f" % (F @ F.T / 200000 - k1).abs().max())

W = torch.randn(m, d, dtype=torch.float64, requires_grad=True)
a = torch.randn(m, dtype=torch.float64, requires_grad=True)
net = lambda x: a @ torch.relu(W @ x) / np.sqrt(m)
G = torch.stack([torch.cat([g.ravel() for g in torch.autograd.grad(net(x), (W, a))]) for x in X])
ntk_emp, ntk_inf = G @ G.T, k1 + (X @ X.T) * k0     # Example 10.5
print("NTK: relative error, width %d vs infinite width = %.4f"
      % (m, (ntk_emp - ntk_inf).norm() / ntk_inf.norm()))

The Monte Carlo error is below 0.01, and the finite-width NTK is within 1 % of its limit; its fluctuations are of order m^{-1/2}.

11. Complements for self-study

This chapter collects results that extend chapters 3, 4, 6, 7 and 8 beyond what the sessions can cover: a generalization bound, links with Gaussian processes, SVM consistency and solvers, the Fourier description of an RKHS, more sequence kernels, and applications of mean embeddings. It is read after the corresponding chapter; nothing in chapters 0–10 depends on it.

Why the RKHS norm controls overfitting (complement to ch. 3)

The ball \mathcal{F}_B of radius B in \mathcal{H} is infinite-dimensional, yet its complexity on a sample is small. The empirical Rademacher complexity, with i.i.d. random signs \varepsilon_i, is \hat{\mathfrak{R}}_n(\mathcal{F}_B) = \mathbb{E}_\varepsilon \sup_{f \in \mathcal{F}_B} \frac{1}{n} \sum_{i=1}^n \varepsilon_i\, f(x_i) .

The bound does not depend on the dimension of the feature space. Combined with the standard Rademacher generalization bound for Lipschitz losses (Bartlett and Mendelson, 2002), it shows that the gap between empirical and true risk over \mathcal{F}_B is of order B\kappa / \sqrt{n}. The regularization \lambda \|f\|^2 is the Lagrangian form of the constraint \|f\| \leq B.

Gaussian processes and other losses (complement to ch. 3)

Consistency and solvers for the SVM (complement to ch. 4)

The hinge loss is a convex upper bound of the 0–1 loss \mathbb{1}[y\, g(x) \leq 0]. With a universal kernel such as the Gaussian kernel, the SVM is consistent: its risk converges to the Bayes risk for a suitable C = C_n (Steinwart, 2001).

The RKHS of a translation-invariant kernel (complement to ch. 6)

Bochner’s theorem (Theorem 6.4) also describes the RKHS of \kappa(x - y): its norm is a weighted energy in the frequency domain.

The penalty 1 / \hat\kappa(\omega) is a frequency weighting. For the Gaussian kernel it grows like e^{\sigma^2 \|\omega\|^2 / 2}: functions of its RKHS are extremely smooth. For the Laplace kernel on \mathbb{R}, \hat\kappa(\omega) = 2\sigma / (1 + \sigma^2 \omega^2), and Plancherel’s identity turns the norm into a Sobolev norm: \|f\|_{\mathcal{H}_K}^2 = \frac{1}{2\sigma} \int f^2 + \frac{\sigma}{2} \int f'^2 .

More kernels for sequences (complement to ch. 7)

Uses of mean embeddings (complement to ch. 8)

12. Research directions and open problems

This chapter is for self-study. It surveys active research questions that build on chapters 3–10, with pointers to papers whose authors and year are given in the references. It is a map, not a review: each item says what the question is and where to start reading.

Kernel methods at the scale of modern data

• Preconditioned solvers made exact-accuracy kernel regression practical on millions of points: FALKON (Rudi, Carratino and Rosasco, 2017) and its multi-GPU implementation for billions of points (Meanti, Carratino, Rosasco and Rudi, 2020). EigenPro (Ma and Belkin, 2017) follows a related route with preconditioned stochastic gradient.
• Open questions include the choice of landmarks beyond uniform sampling (leverage scores, Bach, 2013; El Alaoui and Mahoney, 2015), kernel learning at this scale, and the trade-off between precision, memory and communication on distributed hardware.

Interpolation and generalization

• Belkin, Ma and Mandal (2018) observed that kernel machines that interpolate noisy training data can still generalize, as deep networks do. Liang and Rakhlin (2020) analysed minimum-norm interpolation with kernels in high dimension.
• A precise picture of when interpolation is benign, as a function of dimension, sample size and kernel spectrum, is still being worked out; random matrix theory is one of the tools (see Large Random Matrices).

Beyond the lazy regime

• The NTK explains some aspects of wide networks but not feature learning. Chizat, Oyallon and Bach (2019) characterized lazy training; Ghorbani, Mei, Misiakiewicz and Montanari (2021) quantified the gap between linearized and trained two-layer networks in high dimension.
• Bietti and Mairal (2019b) studied the inductive bias of the NTK (smoothness, stability to deformations). How much of the success of deep networks a well-designed kernel can recover remains open.

Kernels for distributions, sampling and generation

• The MMD has become a training criterion and a geometry on distributions. Arbel, Korba, Salim and Gretton (2019) studied the MMD gradient flow and its convergence; Bińkowski, Sutherland, Arbel and Gretton (2018) analysed MMD GANs.
• Kernel Stein discrepancies (Chwialkowski, Strathmann and Gretton, 2016; Liu, Lee and Jordan, 2016) test goodness of fit without normalizing constants, and Stein variational gradient descent (Liu and Wang, 2016) turns them into a particle sampler. Langevin sampling, studied in Stochastic Calculus in Machine Learning, and the gradient flows of Optimal Transport are the natural points of comparison.

Kernels as models of non-negative functions and for optimization

• Marteau-Ferey, Bach and Rudi (2020) represent non-negative functions as quadratic forms in feature space, f(x) = \varphi(x)^\top A\, \varphi(x) with A \succeq 0, which keeps a representer theorem and convexity. Densities and global optimization are natural applications (Rudi, Marteau-Ferey and Bach, 2020).

Structured data and attention

• Convolutional kernel networks have been extended to sequences (Chen, Jacob and Mairal, 2019) and graphs (Chen, Jacob and Mairal, 2020). Graph kernels and graph neural networks share the Weisfeiler–Lehman limit (Morris et al., 2019; Xu et al., 2019).
• Attention in transformers can be read as a kernel smoother (Tsai et al., 2019), and random features give linear-time approximations of softmax attention (Choromanski et al., 2021).

Questions to explore

1. Can the kernel itself be learned from data with guarantees comparable to those of fixed kernels, beyond the convex combinations of ch. 8?
2. What is the best rank–accuracy trade-off for kernel approximation when the data lie near a low-dimensional manifold?
3. How should a kernel encode known invariances (rotations, permutations, deformations) while keeping a tractable RKHS norm?
4. When is the MMD the right discrepancy for generative modelling, and how should its bandwidth adapt during training?

Exercises

Levels: ★ apply the course, ★★ combine results or prove a short statement, ★★★ open-ended or research-flavoured. Exercises 3, 13, 14, 15 and 16 are computational.

1. ★ Gram matrices of the min kernel. For the points 0.2, 0.5, 0.9 and the kernel \min(x, y) on [0, 1], write the Gram matrix, show that it is positive definite with a Cholesky factorization, and compute the RKHS norm of f = K_{0.5} - K_{0.2} in two ways.

   Solution: the Gram matrix has rows (0.2, 0.2, 0.2), (0.2, 0.5, 0.5) and (0.2, 0.5, 0.9). Its Cholesky factor has diagonal \sqrt{0.2}, \sqrt{0.3}, \sqrt{0.4}, all positive, so it is positive definite (eigenvalues 0.092, 0.2 and 1.308).

   With a = (-1, 1, 0), a^\top K a = 0.2 + 0.5 - 2 \times 0.2 = 0.3. Directly, f' = \mathbb{1}_{[0.2, 0.5]}, and \int f'^2 = 0.3 (Example 2.8).

2. ★ An explicit polynomial feature map. Find a feature map \varphi : \mathbb{R}^2 \to \mathbb{R}^6 for K(x, y) = (x^\top y + 1)^2, and check it on x = (1, 2), y = (3, 1). What is the dimension for (x^\top y + 1)^d on \mathbb{R}^p?

   Solution: expanding the square, \varphi(x) = \big( x_1^2,\; x_2^2,\; \sqrt{2}\, x_1 x_2,\; \sqrt{2}\, x_1,\; \sqrt{2}\, x_2,\; 1 \big) . Here \varphi(x) = (1, 4, 2\sqrt{2}, \sqrt{2}, 2\sqrt{2}, 1) and \varphi(y) = (9, 1, 3\sqrt{2}, 3\sqrt{2}, \sqrt{2}, 1). Their inner product is 9 + 4 + 12 + 6 + 4 + 1 = 36 = (5 + 1)^2.

   The monomials of degree at most d in p variables number \binom{p + d}{d}, here \binom{4}{2} = 6.

3. ★ The kernel mean classifier, in Python. Run the code of ch. 1 with Gaussian bandwidths \sigma \in \{0.02, 0.05, 0.1, 0.3, 1, 3, 10\}. Explain the two extremes.

   Hints and expected result: test accuracies are about 0.74, 0.98, 0.99, 0.98, 0.87, 0.85 and 0.84.

   For large \sigma, K(x, y) \approx 1 - \|x - y\|^2 / 2\sigma^2, so the rule compares mean squared distances to the classes, which is the nearest-centroid rule: the linear kernel’s 0.84.

   For very small \sigma, K(x, x_j) is almost 0 unless x is very close to a training point. The decision then rests on a few neighbours and on the constant term of Proposition 1.7, and it degrades.

4. ★ Kernel ridge regression by hand. Redo Example 3.3 with targets y = (1, 1). Compute \alpha, \hat f(0), \hat f(0.5), the degrees of freedom, and the limit \lambda \to 0.

   Solution: by symmetry \alpha = (a, a) with a\,(1 + 0.6065 + 0.1) = 1, so a = 0.586.

   Then \hat f(0) = a\,(1 + 0.6065) = 0.941 and \hat f(0.5) = 2a\, e^{-1/8} = 1.034: between the two points the fit overshoots slightly.

   The eigenvalues of K are 1.6065 and 0.3935, so \mathrm{df} = \frac{1.6065}{1.7065} + \frac{0.3935}{0.4935} = 1.74 . As \lambda \to 0, a \to 1/1.6065 = 0.622, and \hat f interpolates.

5. ★ A support vector machine on three points. Points x = (0, 1, 3) on the line, labels (-1, +1, +1), linear kernel, hard margin. Find w, b, the support vectors, the multipliers and the margin; check that there is no duality gap.

   Solution: the support vectors are the points 0 and 1. The margin conditions g(0) = -1 and g(1) = 1 give w = 2 and b = -1. The point 3 has y\, g(3) = 5 > 1, so \alpha_3 = 0.

   The constraint \sum_i \alpha_i y_i = 0 forces \alpha_1 = \alpha_2 = a, and w = \sum_i \alpha_i y_i x_i = a = 2.

   Dual value: 4 - \frac{1}{2} \cdot 4 = 2; primal value: \frac{1}{2} w^2 = 2. The margin is 1/w = 0.5. The soft-margin SVM gives the same solution when C \geq 2.

6. ★ A spectrum kernel by hand. Compute the 2-spectrum kernel between GATTACA and TACATA, and the normalized kernel K(x, y) / \sqrt{K(x, x)\, K(y, y)}.

   Solution: GATTACA has the 2-mers GA, AT, TT, TA, AC, CA, once each, so K(x, x) = 6. TACATA has TA twice and AC, CA, AT once, so K(y, y) = 4 + 1 + 1 + 1 = 7.

   The shared 2-mers give K(x, y) = 1 \cdot 2 + 1 + 1 + 1 = 5, and the normalized kernel is 5 / \sqrt{42} = 0.772.

7. ★★ Minimum-norm interpolation with the min kernel. Let 0 < x_1 < \dots < x_n \leq 1 and values y_i. Show that the function of minimal norm in the RKHS of Example 2.8 with f(x_i) = y_i is piecewise linear. Compute its norm, then evaluate it for the data (0.5, 1) and (1, 0).

   Solution: apply Theorem 3.1 with \Psi equal to \|f\| on the interpolation constraints and +\infty elsewhere; its proof works unchanged for this extended-valued \Psi. The minimizer is \sum_i \alpha_i \min(x_i, \cdot).

   This function is piecewise linear with kinks at the x_i, zero at 0 and constant after x_n. It is fixed by its values at the x_i, so it is the piecewise-linear interpolant through (0, 0) and the data.

   With x_0 = y_0 = 0, its norm is the sum of squared slopes times lengths: \|f\|^2 = \sum_{i=1}^n \frac{(y_i - y_{i-1})^2}{x_i - x_{i-1}} . For the data given, 1/0.5 + 1/0.5 = 4.

8. ★★ Centering in feature space. (a) Show that the Gram matrix of the centred features is HKH. (b) Deduce that the kernel principal components of the training points have zero mean. (c) Write the centred kernel between a training point x_i and a new point x.

   Solution: (a) with the mean feature \bar\varphi = \frac{1}{n} \sum_l \varphi_l, expanding gives \langle \varphi_i - \bar\varphi, \varphi_j - \bar\varphi \rangle = K_{ij} - \frac{1}{n} \sum_l K_{il} - \frac{1}{n} \sum_l K_{lj} + \frac{1}{n^2} \sum_{l, k} K_{lk} = (HKH)_{ij} .

   2. H\mathbf{1} = 0 gives \mathbf{1}^\top K_c = 0, and the scores are K_c \alpha_k, so they sum to 0.

   3. Replace \varphi_j by \varphi(x) in (a): \tilde K(x_i, x) = K(x_i, x) - \frac{1}{n} \sum_l K(x_l, x) - \frac{1}{n} \sum_l K(x_i, x_l) + \frac{1}{n^2} \sum_{l, k} K_{lk} .

9. ★★ Regularized kernel CCA. (a) Show that the regularized canonical correlation of Proposition 5.7 is strictly less than 1 when \gamma > 0. (b) Show that, as \gamma \to \infty, the canonical directions tend to those of the singular value problem for K_1 K_2, and interpret.

   Solution: (a) R_j has eigenvalues \mu / (\mu + \gamma) < 1, so \|R_1 R_2\| \leq \|R_1\|\, \|R_2\| < 1.

   2. \gamma R_j = K_j (I + K_j / \gamma)^{-1} \to K_j. So \gamma^2 R_1 R_2 \to K_1 K_2, and the singular vectors of R_1 R_2 tend to those of K_1 K_2.

   The criterion becomes the covariance \alpha^\top K_1 K_2 \beta under \|\alpha\| = \|\beta\| = 1: strong regularization turns kernel CCA into a kernel partial least squares, which maximizes covariance instead of correlation.

10. ★★ The Laplace kernel through Schoenberg. For x \in \mathbb{R}, let g_x = \mathbb{1}_{[0, x)} if x \geq 0 and g_x = -\mathbb{1}_{[x, 0)} if x < 0. Show that |x - y| = \|g_x - g_y\|_{L^2}^2.

    Deduce that e^{-t |x - y|} and e^{-t \|x - y\|_1} are p.d. on \mathbb{R} and \mathbb{R}^d.

    Solution: whatever the signs of the two points, g_x - g_y equals \pm 1 between x and y and 0 elsewhere. Its squared norm is therefore |x - y|.

    A squared distance between feature vectors is negative definite (Definition 6.5), so Theorem 6.6 gives e^{-t|x - y|} p.d. On \mathbb{R}^d, \|x - y\|_1 = \sum_k |x_k - y_k| is a sum of negative definite kernels, hence negative definite, and Theorem 6.6 applies again.

11. ★★ Unlabelled walk kernels are weak. Without labels, show that \mathbf{1}^\top (A \otimes A')^k \mathbf{1} is the product w_k(G)\, w_k(G'), where w_k(G) = \mathbf{1}^\top A^k \mathbf{1} counts the walks of length k in G.

    Deduce that all d-regular graphs on n vertices have the same random-walk features, and explain the normalized values close to 0.99 printed in ch. 7.

    Solution: the mixed-product rule gives (A \otimes A')^k = A^k \otimes A'^k, and \mathbf{1} = \mathbf{1}_n \otimes \mathbf{1}_{n'}. Conclude with the identity (u \otimes v)^\top (M \otimes N)(u \otimes v) = (u^\top M u)(v^\top N v) .

    For a d-regular graph, A\mathbf{1} = d\mathbf{1}, so w_k = n d^k for every such graph.

    The kernel is \sum_k \lambda^k w_k(G) w_k(G'), an inner product of walk-count sequences. These sequences grow geometrically and are nearly parallel for graphs of similar size, hence normalized values close to 1.

12. ★★ The MKL objective and its optimality conditions. Starting from Proposition 8.3, write the optimality conditions of \min_{\eta \in \Delta_M} J(\eta) and interpret them.

    Solution: J is convex and differentiable on the simplex. So \eta is optimal iff, for some t, every active kernel (\eta_m > 0) has \partial J / \partial \eta_m = -t and every inactive one has \partial J / \partial \eta_m \geq -t.

    With the gradient of Proposition 8.3, all active kernels reach the same maximal value of \alpha^\top K_m \alpha, and inactive kernels have a value no larger.

    In words, \alpha^\top K_m \alpha = \|f_m\|^2 / \eta_m^2 measures how much kernel m correlates with the dual residual \alpha = (y - \hat y)/(n\lambda). Only the kernels that explain the residual best are switched on.

13. ★★ Random features: variance, in Python. (a) Show that a single term 2\cos(\omega^\top x + b)\cos(\omega^\top y + b) has variance 1 + \kappa(2\delta)/2 - \kappa(\delta)^2, where \delta = x - y.

    2. For the Gaussian kernel with \sigma = 1 and \|\delta\| = 1, compare the predicted standard deviation of z(x)^\top z(y) with a simulation over 2000 draws, for D \in \{10, 100, 1000\}.

    Solution: (a) write the term as \cos(\omega^\top \delta) + \cos(u + v + 2b) with u = \omega^\top x, v = \omega^\top y. The two parts are uncorrelated, with second moments (1 + \kappa(2\delta))/2 and 1/2. Subtract the squared mean \kappa(\delta)^2.

    2. Here \kappa(\delta) = e^{-1/2} and \kappa(2\delta) = e^{-2}, so the variance of one term is 0.700. The predicted standard deviations are 0.265, 0.084 and 0.026. A simulation over 2000 draws matches them up to its own Monte Carlo error of a few percent (one run gave 0.266, 0.084 and 0.026). The error decreases like D^{-1/2}.

14. ★★★ The neural tangent kernel of a two-layer network. (a) Derive the formula of Example 10.5 from Theorem 10.2. (b) With the code of ch. 10, measure the relative error between the empirical and the limiting NTK for widths m \in \{10^2, 10^3, 10^4, 10^5\} and estimate the rate. (c) Train the network by gradient descent with a small step on 20 points of a one-dimensional regression problem, and compare its predictions with Proposition 10.4 as m grows.

    Hints and expected result: (a) sum the contributions of a and of W, using independence of a_j and w_j and \mathbb{E} a_j^2 = 1. (b) The error decreases roughly like m^{-1/2}, about a factor 3 per decade of width.

    3. For large widths, the trained network and the NTK predictor agree closely and the weights barely move (lazy regime). For small widths they separate. Report the relative change \|W_t - W_0\| / \|W_0\| as a function of m.

15. ★★★ Kernels on a graph for semi-supervised classification. On two-block stochastic block models with within-block probability 0.2 and between-block probability q \in \{0.02, 0.05, 0.1\}, compare the diffusion kernel and the regularized Laplacian kernel for kernel ridge regression from 2 labels per class. Study the accuracy as a function of \beta and explain the limits \beta \to 0 and \beta \to \infty.

    Hints and expected result: as \beta \to 0, both kernels tend to the identity, so nothing propagates and unlabelled vertices get the prediction 0. As \beta \to \infty on a connected graph, e^{-\beta L} \to \frac{1}{n} \mathbf{1}\mathbf{1}^\top, and every vertex gets the same prediction. The accuracy is therefore maximal at an intermediate \beta, comparable to the inverse spectral gap of the graph.

    It degrades as q grows and the communities blur. Report curves averaged over 20 random graphs.

16. ★★★ Choosing the bandwidth of an MMD test. For the Gaussian-versus-Laplace problem of ch. 8, estimate the power of the permutation test at level 0.05 as a function of the bandwidth \sigma \in \{0.1, 0.3, 1, 3\} and of the sample size m \in \{50, 100, 200\}. Compare with the median heuristic, then implement a selection of \sigma on half of the data and testing on the other half.

    Hints and expected result: the two distributions differ in the tails and in the peak, so small and medium bandwidths are more powerful than very large ones.

    With a very large \sigma, expand the kernel in powers of 1/\sigma^2. The first term of the squared MMD is \frac{(\mathbb{E}X - \mathbb{E}Y)^2}{\sigma^2} .

    More generally, when the moments of order below r agree, the first non-zero term is proportional to the squared difference of the moments of order r, at order \sigma^{-2r}.

    Here the means, variances and third moments agree, so the signal is of order \sigma^{-8} (about 1.6\, \sigma^{-8}), far below the estimation noise, and the power falls towards the level.

    Selecting \sigma on held-out data and testing on the rest keeps the level exact. It may beat the median heuristic despite halving the sample, which is the idea of Gretton et al. (2012b) and of later work learning deep kernels for testing (Liu et al., 2020).

Projects and assessment

The official assessment, per master-mva.com, combines one final exam (40%), a data challenge (40%) and 3 homework assignments submitted online (20%); the Université Paris-Saclay course detail classifies it as “Evaluation Continue non Intégrale” (partial continuous assessment). The solo subjects below are sized like a homework assignment extended into a short study. The group subjects rehearse the data challenge. The written exam proposal shows the kind of questions a 40% final exam can ask; none of these proposals is official material.

Solo projects

1. [Solo · ≈ 20 h] Random features versus Nyström: a paper study. Reproduce the main experiments of Rahimi and Recht (2007) and the comparison of Rudi, Camoriano and Rosasco (2015).
   • Implement: kernel ridge regression with random Fourier features and with Nyström landmarks, from NumPy.
   • Data: a public regression set such as California housing (scikit-learn) or YearPredictionMSD (UCI), subsampled to fit a laptop.
   • Success criterion: plots of test error and time against D and m, showing where each method reaches exact-KRR accuracy, and checking the \sqrt{n} scaling of Theorem 9.5 on 3 values of n.
   • Deliverables: code, a 4–6 page report, a 10-minute talk. Chapters 3, 6, 9.
2. [Solo · ≈ 20 h] Kernel two-sample tests: a paper study. Study and reimplement the MMD test of Gretton, Borgwardt, Rasch, Schölkopf and Smola (2012).
   • Implement: the unbiased statistic, the permutation test, and the linear-time statistic of the same paper.
   • Data: synthetic problems (Gaussian against Laplace, mixtures with a shifted component, the “blobs” problem in two dimensions).
   • Success criterion: empirical level within 0.05 \pm 0.02 under the null, and power curves against m and against the bandwidth that reproduce the qualitative findings of the paper.
   • Deliverables: code, report, talk. Chapters 6, 8.
3. [Solo · ≈ 15 h] Subsequence string kernels for text. Implement the gap-weighted subsequence kernel of Lodhi et al. (2002) with the O(p\, |s|\, |t|) recursion, and test it against brute force.
   • Task: classify two topics of the 20 Newsgroups corpus (scikit-learn) with an SVM on a precomputed kernel. Use at most 400 documents cut to their first 250 characters, and vectorize the recursion in NumPy (or compile it with Numba) so that the Gram matrix takes minutes, not hours.
   • Success criterion: an accuracy comparison with the bag-of-words and spectrum kernels, with timings and the effect of p and \lambda.
   • Deliverables: code, report, talk. Chapters 4, 7.

Group projects

1. [Group of 2–3 · ≈ 30 h each] Data-challenge rehearsal: classifying DNA sequences with hand-made kernel methods. The rule is that every learning algorithm is implemented by the group, without a machine-learning library.
   • Data: the public UCI “Molecular Biology (Splice-junction Gene Sequences)” data set (3190 sequences of 60 nucleotides), or synthetic sequences with planted motifs.
   • Work split: one member writes the kernels (spectrum, mismatch, gap-weighted subsequence); one writes the solvers (KRR, kernel logistic regression by Newton’s method, an SVM dual solver); one runs model selection, kernel combination (ch. 8) and the final submission.
   • Success criterion: a held-out accuracy above a k-mer logistic-regression baseline, with cross-validated hyperparameters.
   • Deliverables: code, a 6-page report, a leaderboard-style submission, a 15-minute talk. Chapters 3, 4, 7, 8.
2. [Group of 2–3 · ≈ 30 h each] Graph kernels for molecules: a paper study. Reproduce part of the experimental table of Shervashidze et al. (2011).
   • Data: MUTAG and ENZYMES, two of the data sets of that table, from the public TU Dortmund graph benchmark collection.
   • Work split: one kernel per member (Weisfeiler–Lehman subtree, shortest-path, random-walk with labels), plus a shared nested cross-validation harness and SVM.
   • Success criterion: accuracies within 2 points of the published ones for the WL kernel, and a timing comparison that reproduces the paper’s ranking of the kernels.
   • Deliverables: code, report, talk. Chapters 4, 7.
3. [Group of 2–3 · ≈ 30 h each] Convolutional kernel networks on small images. Study Mairal et al. (2014) and Mairal (2016), and build a one- and two-layer CKN as in Definition 10.3.
   • Data: the 8×8 digits of scikit-learn, then Fashion-MNIST (public) on a laptop CPU.
   • Work split: patch extraction and Nyström layer with k-means anchors; pooling and the second layer; comparison with a Gaussian-kernel SVM on raw pixels, random features, and a small CNN of similar size.
   • Success criterion: a table of test accuracy against the number of anchors, showing where the two-layer CKN beats the one-layer one.
   • Deliverables: code, report, talk. Chapters 4, 9, 10.

Written exam (proposal)

Format: 3 hours, one handwritten A4 sheet allowed, no electronic device; four exercises, independent of each other.

1. Course question (4 points). Define a positive definite kernel and a reproducing kernel Hilbert space. State and prove the representer theorem.

   Expected: Definitions 1.1 and 2.1; Theorem 3.1 with the orthogonal decomposition onto the span of the K_{x_i}, the invariance of the data term, and the strict increase of the norm term.

2. Computation (6 points). Kernel ridge regression with the kernel K(x, y) = \min(x, y) + 1 on [0, 2], the points x = (0, 1, 2), the targets y = (0, 1, 0) and n\lambda = 1.

   1. Show that the kernel is p.d. (b) Compute \alpha and \hat f(1). (c) Compute the degrees of freedom.

   Expected: (a) on [0, 2], \min(x, y) is the L^2 inner product of the indicators of [0, x] and [0, y], hence p.d. (Proposition 1.2); the constant 1 is p.d., and so is the sum (Proposition 1.4).

   2. The Gram matrix has rows (1, 1, 1), (1, 2, 2) and (1, 2, 3); solving (K + I)\alpha = y gives \alpha = \tfrac{1}{13}(-2, 7, -3), \qquad \hat f(1) = \tfrac{6}{13} \approx 0.46 .
   3. From the eigenvalues of K, or from the trace of (K + I)^{-1}: \mathrm{df} = \mathrm{tr}\, K (K + I)^{-1} = 3 - \mathrm{tr}\,(K + I)^{-1} = \tfrac{19}{13} \approx 1.46 .

3. Short proof (5 points). Show that if \psi is negative definite, then e^{-t\psi} is p.d. for all t > 0. Deduce that e^{-t \chi^2(x, y)} is p.d. on histograms.

   Expected: the auxiliary kernel \tilde K of Theorem 6.6 with its positivity proof, the factorization of e^{-t\psi}, and Proposition 6.8.

4. Problem (5 points). Let \hat\mu_P and \hat\mu_Q be the empirical mean embeddings of two samples of size m, from P and Q, for a kernel bounded by \kappa^2.

   1. Show that \mathbb{E} \|\hat\mu_P - \mu_P\|^2 \leq \kappa^2 / m. (b) Deduce a bound on the expected error of the plug-in estimate of the MMD: \mathbb{E}\, \Big| \|\hat\mu_P - \hat\mu_Q\| - \mathrm{MMD}(P, Q) \Big| .
   2. Explain why a permutation test has the exact level.

   Expected: (a) Proposition 8.7. (b) The triangle inequality and Jensen give 2\kappa / \sqrt{m}. (c) Under the null hypothesis the pooled sample is exchangeable, so the observed statistic is uniformly ranked among the permuted ones.

Grading rubric (proposal)

References

Official references (master-mva.com)

• N. Aronszajn. Theory of reproducing kernels. Transactions of the American Mathematical Society, 68:337–404, 1950.
• C. Berg, J. P. R. Christensen and P. Ressel. Harmonic Analysis on Semigroups. Springer, 1994 (year as listed on the course page; the book appeared in 1984 as Graduate Texts in Mathematics 100, Harmonic Analysis on Semigroups: Theory of Positive Definite and Related Functions).
• N. Cristianini and J. Shawe-Taylor. Kernel Methods for Pattern Analysis. Cambridge University Press, 2004 (as listed on the course page; the book gives the authors in the order J. Shawe-Taylor and N. Cristianini).
• Course website linked from the official description: https://mva-kernel-methods.github.io/course-2023-2024/.

Textbooks

• A. Berlinet and C. Thomas-Agnan. Reproducing Kernel Hilbert Spaces in Probability and Statistics. Kluwer Academic Publishers, 2004.
• S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
• C. E. Rasmussen and C. K. I. Williams. Gaussian Processes for Machine Learning. MIT Press, 2006.
• W. Rudin. Fourier Analysis on Groups. Interscience Publishers, 1962.
• B. Schölkopf and A. J. Smola. Learning with Kernels. MIT Press, 2002.
• B. Schölkopf, K. Tsuda and J.-P. Vert (eds.). Kernel Methods in Computational Biology. MIT Press, 2004.
• I. Steinwart and A. Christmann. Support Vector Machines. Springer, 2008.
• G. Wahba. Spline Models for Observational Data. SIAM, 1990.

Foundations, kernel ridge regression and SVMs (ch. 1–4)

• P. L. Bartlett and S. Mendelson. Rademacher and Gaussian complexities: risk bounds and structural results. Journal of Machine Learning Research, 3:463–482, 2002.
• B. E. Boser, I. M. Guyon and V. N. Vapnik. A training algorithm for optimal margin classifiers. Proceedings of COLT, 1992.
• C.-C. Chang and C.-J. Lin. LIBSVM: a library for support vector machines. ACM Transactions on Intelligent Systems and Technology, 2(3):27, 2011.
• C. Cortes and V. Vapnik. Support-vector networks. Machine Learning, 20(3):273–297, 1995.
• T. Hofmann, B. Schölkopf and A. J. Smola. Kernel methods in machine learning. Annals of Statistics, 36(3):1171–1220, 2008.
• G. Kimeldorf and G. Wahba. Some results on Tchebycheffian spline functions. Journal of Mathematical Analysis and Applications, 33(1):82–95, 1971.
• J. C. Platt. Fast training of support vector machines using sequential minimal optimization. In Advances in Kernel Methods — Support Vector Learning, MIT Press, 1999.
• B. Schölkopf, R. Herbrich and A. J. Smola. A generalized representer theorem. Proceedings of COLT, 2001.
• I. Steinwart. On the influence of the kernel on the consistency of support vector machines. Journal of Machine Learning Research, 2:67–93, 2001.

Unsupervised kernel methods (ch. 5)

• F. R. Bach and M. I. Jordan. Kernel independent component analysis. Journal of Machine Learning Research, 3:1–48, 2002.
• I. S. Dhillon, Y. Guan and B. Kulis. Kernel k-means, spectral clustering and normalized cuts. Proceedings of KDD, 2004.
• A. Y. Ng, M. I. Jordan and Y. Weiss. On spectral clustering: analysis and an algorithm. Advances in Neural Information Processing Systems 14, 2002.
• B. Schölkopf, A. Smola and K.-R. Müller. Nonlinear component analysis as a kernel eigenvalue problem. Neural Computation, 10(5):1299–1319, 1998.
• U. von Luxburg. A tutorial on spectral clustering. Statistics and Computing, 17(4):395–416, 2007.

Kernel design (ch. 6–7)

• M. Cuturi, K. Fukumizu and J.-P. Vert. Semigroup kernels on measures. Journal of Machine Learning Research, 6:1169–1198, 2005.
• T. Gärtner, P. Flach and S. Wrobel. On graph kernels: hardness results and efficient alternatives. Proceedings of COLT, 2003.
• Z. Harchaoui and F. Bach. Image classification with segmentation graph kernels. Proceedings of CVPR, 2007.
• D. Haussler. Convolution kernels on discrete structures. Technical report UCSC-CRL-99-10, University of California at Santa Cruz, 1999.
• M. Hein and O. Bousquet. Hilbertian metrics and positive definite kernels on probability measures. Proceedings of AISTATS, 2005.
• T. Jaakkola and D. Haussler. Exploiting generative models in discriminative classifiers. Advances in Neural Information Processing Systems 11, 1999.
• H. Kashima, K. Tsuda and A. Inokuchi. Marginalized kernels between labeled graphs. Proceedings of ICML, 2003.
• R. I. Kondor and J. Lafferty. Diffusion kernels on graphs and other discrete input spaces. Proceedings of ICML, 2002.
• C. Leslie, E. Eskin and W. S. Noble. The spectrum kernel: a string kernel for SVM protein classification. Pacific Symposium on Biocomputing, 2002.
• C. Leslie, E. Eskin, A. Cohen, J. Weston and W. S. Noble. Mismatch string kernels for discriminative protein classification. Bioinformatics, 20(4):467–476, 2004.
• H. Lodhi, C. Saunders, J. Shawe-Taylor, N. Cristianini and C. Watkins. Text classification using string kernels. Journal of Machine Learning Research, 2:419–444, 2002.
• J. Mercer. Functions of positive and negative type, and their connection with the theory of integral equations. Philosophical Transactions of the Royal Society A, 209:415–446, 1909.
• C. Morris, M. Ritzert, M. Fey, W. L. Hamilton, J. E. Lenssen, G. Rattan and M. Grohe. Weisfeiler and Leman go neural: higher-order graph neural networks. Proceedings of AAAI, 2019.
• H. Saigo, J.-P. Vert, N. Ueda and T. Akutsu. Protein homology detection using string alignment kernels. Bioinformatics, 20(11):1682–1689, 2004.
• I. J. Schoenberg. Metric spaces and positive definite functions. Transactions of the American Mathematical Society, 44(3):522–536, 1938.
• N. Shervashidze, P. Schweitzer, E. J. van Leeuwen, K. Mehlhorn and K. M. Borgwardt. Weisfeiler-Lehman graph kernels. Journal of Machine Learning Research, 12:2539–2561, 2011.
• A. J. Smola and R. Kondor. Kernels and regularization on graphs. Proceedings of COLT, 2003.
• J.-P. Vert and M. Kanehisa. Graph-driven feature extraction from microarray data using diffusion kernels and kernel CCA. Advances in Neural Information Processing Systems 15, 2003.
• S. V. N. Vishwanathan, N. N. Schraudolph, R. Kondor and K. M. Borgwardt. Graph kernels. Journal of Machine Learning Research, 11:1201–1242, 2010.
• K. Xu, W. Hu, J. Leskovec and S. Jegelka. How powerful are graph neural networks? Proceedings of ICLR, 2019.
• J. Zhang, M. Marszałek, S. Lazebnik and C. Schmid. Local features and kernels for classification of texture and object categories: a comprehensive study. International Journal of Computer Vision, 73(2):213–238, 2007.

Multiple kernel learning and mean embeddings (ch. 8)

• F. R. Bach, G. R. G. Lanckriet and M. I. Jordan. Multiple kernel learning, conic duality, and the SMO algorithm. Proceedings of ICML, 2004.
• G. K. Dziugaite, D. M. Roy and Z. Ghahramani. Training generative neural networks via maximum mean discrepancy optimization. Proceedings of UAI, 2015.
• K. Fukumizu, L. Song and A. Gretton. Kernel Bayes’ rule: Bayesian inference with positive definite kernels. Journal of Machine Learning Research, 14:3753–3783, 2013.
• M. Gönen and E. Alpaydın. Multiple kernel learning algorithms. Journal of Machine Learning Research, 12:2211–2268, 2011.
• A. Gretton, O. Bousquet, A. Smola and B. Schölkopf. Measuring statistical dependence with Hilbert-Schmidt norms. Proceedings of ALT, 2005.
• A. Gretton, K. M. Borgwardt, M. J. Rasch, B. Schölkopf and A. Smola. A kernel two-sample test. Journal of Machine Learning Research, 13:723–773, 2012.
• A. Gretton, B. Sriperumbudur, D. Sejdinovic, H. Strathmann, S. Balakrishnan, M. Pontil and K. Fukumizu. Optimal kernel choice for large-scale two-sample tests. Advances in Neural Information Processing Systems 25, 2012 (cited as 2012b).
• G. R. G. Lanckriet, N. Cristianini, P. Bartlett, L. El Ghaoui and M. I. Jordan. Learning the kernel matrix with semidefinite programming. Journal of Machine Learning Research, 5:27–72, 2004.
• Y. Li, K. Swersky and R. Zemel. Generative moment matching networks. Proceedings of ICML, 2015.
• F. Liu, W. Xu, J. Lu, G. Zhang, A. Gretton and D. J. Sutherland. Learning deep kernels for non-parametric two-sample tests. Proceedings of ICML, 2020.
• K. Muandet, K. Fukumizu, B. Sriperumbudur and B. Schölkopf. Kernel mean embedding of distributions: a review and beyond. Foundations and Trends in Machine Learning, 10(1–2):1–141, 2017.
• A. Rakotomamonjy, F. R. Bach, S. Canu and Y. Grandvalet. SimpleMKL. Journal of Machine Learning Research, 9:2491–2521, 2008.
• A. Smola, A. Gretton, L. Song and B. Schölkopf. A Hilbert space embedding for distributions. Proceedings of ALT, 2007.
• L. Song, J. Huang, A. Smola and K. Fukumizu. Hilbert space embeddings of conditional distributions with applications to dynamical systems. Proceedings of ICML, 2009.
• B. K. Sriperumbudur, A. Gretton, K. Fukumizu, B. Schölkopf and G. R. G. Lanckriet. Hilbert space embeddings and metrics on probability measures. Journal of Machine Learning Research, 11:1517–1561, 2010.

Large-scale kernel methods (ch. 9)

• F. Bach. Sharp analysis of low-rank kernel matrix approximations. Proceedings of COLT, 2013.
• A. Caponnetto and E. De Vito. Optimal rates for the regularized least-squares algorithm. Foundations of Computational Mathematics, 7(3):331–368, 2007.
• A. El Alaoui and M. W. Mahoney. Fast randomized kernel ridge regression with statistical guarantees. Advances in Neural Information Processing Systems 28, 2015.
• S. Ma and M. Belkin. Diving into the shallows: a computational perspective on large-scale shallow learning. Advances in Neural Information Processing Systems 30, 2017.
• G. Meanti, L. Carratino, L. Rosasco and A. Rudi. Kernel methods through the roof: handling billions of points efficiently. Advances in Neural Information Processing Systems 33, 2020.
• A. Rahimi and B. Recht. Random features for large-scale kernel machines. Advances in Neural Information Processing Systems 20, 2007.
• A. Rudi, R. Camoriano and L. Rosasco. Less is more: Nyström computational regularization. Advances in Neural Information Processing Systems 28, 2015.
• A. Rudi, L. Carratino and L. Rosasco. FALKON: an optimal large scale kernel method. Advances in Neural Information Processing Systems 30, 2017.
• A. Rudi and L. Rosasco. Generalization properties of learning with random features. Advances in Neural Information Processing Systems 30, 2017.
• C. K. I. Williams and M. Seeger. Using the Nyström method to speed up kernel machines. Advances in Neural Information Processing Systems 13, 2001.

Kernels and deep learning (ch. 10)

• A. Bietti and J. Mairal. Group invariance, stability to deformations, and complexity of deep convolutional representations. Journal of Machine Learning Research, 20(25):1–49, 2019 (cited as 2019a).
• A. Bietti and J. Mairal. On the inductive bias of neural tangent kernels. Advances in Neural Information Processing Systems 32, 2019 (cited as 2019b).
• D. Chen, L. Jacob and J. Mairal. Biological sequence modeling with convolutional kernel networks. Bioinformatics, 35(18):3294–3302, 2019.
• D. Chen, L. Jacob and J. Mairal. Convolutional kernel networks for graph-structured data. Proceedings of ICML, 2020.
• L. Chizat, E. Oyallon and F. Bach. On lazy training in differentiable programming. Advances in Neural Information Processing Systems 32, 2019.
• Y. Cho and L. K. Saul. Kernel methods for deep learning. Advances in Neural Information Processing Systems 22, 2009.
• A. Jacot, F. Gabriel and C. Hongler. Neural tangent kernel: convergence and generalization in neural networks. Advances in Neural Information Processing Systems 31, 2018.
• J. Lee, Y. Bahri, R. Novak, S. S. Schoenholz, J. Pennington and J. Sohl-Dickstein. Deep neural networks as Gaussian processes. Proceedings of ICLR, 2018.
• J. Mairal, P. Koniusz, Z. Harchaoui and C. Schmid. Convolutional kernel networks. Advances in Neural Information Processing Systems 27, 2014.
• J. Mairal. End-to-end kernel learning with supervised convolutional kernel networks. Advances in Neural Information Processing Systems 29, 2016.
• R. M. Neal. Bayesian Learning for Neural Networks. Springer, 1996.

Research directions (ch. 12)

• M. Arbel, A. Korba, A. Salim and A. Gretton. Maximum mean discrepancy gradient flow. Advances in Neural Information Processing Systems 32, 2019.
• M. Belkin, S. Ma and S. Mandal. To understand deep learning we need to understand kernel learning. Proceedings of ICML, 2018.
• M. Bińkowski, D. J. Sutherland, M. Arbel and A. Gretton. Demystifying MMD GANs. Proceedings of ICLR, 2018.
• K. Choromanski, V. Likhosherstov, D. Dohan et al. Rethinking attention with Performers. Proceedings of ICLR, 2021.
• K. Chwialkowski, H. Strathmann and A. Gretton. A kernel test of goodness of fit. Proceedings of ICML, 2016.
• B. Ghorbani, S. Mei, T. Misiakiewicz and A. Montanari. Linearized two-layers neural networks in high dimension. Annals of Statistics, 49(2):1029–1054, 2021.
• T. Liang and A. Rakhlin. Just interpolate: kernel “ridgeless” regression can generalize. Annals of Statistics, 48(3):1329–1347, 2020.
• Q. Liu, J. D. Lee and M. I. Jordan. A kernelized Stein discrepancy for goodness-of-fit tests. Proceedings of ICML, 2016.
• Q. Liu and D. Wang. Stein variational gradient descent: a general purpose Bayesian inference algorithm. Advances in Neural Information Processing Systems 29, 2016.
• U. Marteau-Ferey, F. Bach and A. Rudi. Non-parametric models for non-negative functions. Advances in Neural Information Processing Systems 33, 2020.
• A. Rudi, U. Marteau-Ferey and F. Bach. Finding global minima via kernel approximations. arXiv preprint, 2020.
• Y.-H. H. Tsai, S. Bai, M. Yamada, L.-P. Morency and R. Salakhutdinov. Transformer dissection: a unified understanding of transformer’s attention via the lens of kernel. Proceedings of EMNLP-IJCNLP, 2019.