Skip to content
LumenaryAcademy
Frontier 80 min

Statistical learning theory

Why fitting the past can predict the future — risk and its decomposition, uniform convergence and the VC dimension, double descent demonstrated, and an honest account of what theory does and does not yet explain about deep learning.

Code tested · 5AI-draftedAwaiting review by a statistician

Your guides: Chloe · The Statistician, Margaret · The Simulator, Gideon · The Sceptic

MotivationH

Why should the past predict the future?

A classifier trained on 60,000 handwritten digits labels the next 10,000, which it has never seen, almost perfectly. Nothing in the training algorithm mentions those 10,000 digits. It only ever made its errors on the training set small. Why should that tell us anything about new data?

Two ingredients are needed, and statistical learning theory is the study of how they combine. The first is an assumption: the new data come from the same distribution as the old. Without it, nothing can be promised. The second is a limit on how much the learner chose. A procedure that can fit any labelling of the training data whatsoever learns nothing from fitting yours; a procedure that could only fit a few patterns, and fitted yours, has found something. The theory turns this intuition into inequalities with nn in them.

You have met the practical face of these ideas already. In Lumenary CS's learning from data lesson, validation error traced a U-shape against model complexity, with a caveat at the end: very large networks fit their training data perfectly and still generalise, a phenomenon called double descent. In Likelihood and model selection, AIC and cross-validation estimated how optimistic a training error is; in High-dimensional statistics, regularisation made p>np > n regression possible. This lesson is the theory beneath all three, and its last part is about where that theory, as of 2026, runs out.

DefinitionsH

Risk, empirical risk and the gap

Statistical learning theory works with a deliberately spare model of the world.

Definition— Risk and empirical risk

Pairs (X,Y)(X, Y) are drawn independently from an unknown distribution PP. A loss ℓ(y^,y)≥0\ell(\hat y, y) \ge 0 measures how bad a prediction is: squared error (y^−y)2(\hat y - y)^2 for regression, the 0–1 loss 1[y^≠y]\mathbf 1[\hat y \ne y] for classification. The risk of a prediction rule ff is its expected loss on a new draw,

R(f)=E(X,Y)∼P ℓ(f(X),Y),R(f) = \mathbb{E}_{(X,Y) \sim P}\,\ell(f(X), Y),

and its empirical risk on a sample S={(x1,y1),…,(xn,yn)}S = \{(x_1, y_1), \dots, (x_n, y_n)\} is the average loss on that sample, R^n(f)=1n∑i=1nℓ(f(xi),yi)\hat R_n(f) = \frac1n \sum_{i=1}^n \ell(f(x_i), y_i).

Definition— Empirical risk minimisation and the generalisation gap

A hypothesis class F\mathcal F is the set of rules the learner may choose from: all lines, all trees of depth 5, all networks of a given architecture. Empirical risk minimisation (ERM) picks f^∈F\hat f \in \mathcal F with the smallest empirical risk. The generalisation gap of the chosen rule is R(f^)−R^n(f^)R(\hat f) - \hat R_n(\hat f): how much worse it does on new data than on the data it was chosen to fit.

For one fixed rule, chosen before the data were seen, R^n(f)\hat R_n(f) is an unbiased estimate of R(f)R(f): an average of nn independent losses. For the chosen rule it is biased downwards, because f^\hat f was picked precisely for having a small empirical risk. You met this optimism in Likelihood and model selection: for linear regression with pp coefficients and noise variance σ2\sigma^2, the expected optimism of the training error is 2σ2p/n2\sigma^2 p / n, which is the penalty in AIC and Mallows' CpC_p. Learning theory asks for the same thing for any class and any loss, and preferably with high probability rather than in expectation.

It helps to name the rule we would like to have. Let f∗f^* be the best possible rule of any kind (its risk R∗R^* is the Bayes risk), and fFf_{\mathcal F} the best rule in the class. Then the excess risk of what we learned splits in two:

R(f^)−R∗=R(fF)−R∗⏟approximation error+R(f^)−R(fF)⏟estimation error.R(\hat f) - R^* = \underbrace{R(f_{\mathcal F}) - R^*}_{\text{approximation error}} + \underbrace{R(\hat f) - R(f_{\mathcal F})}_{\text{estimation error}} .

A bigger class can only shrink the approximation error, and the worry is that it inflates the estimation error, because there are more ways to be fooled by noise. When the minimisation is done approximately, by stochastic gradient descent for instance, a third term, the optimisation error, joins them. Much of what follows is about the estimation term, and the surprise at the end of the lesson is that for very large classes it need not grow.

Everything here leans on two words: independent and identically distributed. The training pairs are independent draws, and the future comes from the same PP. Deploy the model on a hospital, a country or a year it was not trained on, and none of the guarantees below says anything at all — which is why Conformal prediction and The statistics of evaluating AI return to distribution shift.

ExplanationH

The bias–variance decomposition

For squared error there is an exact accounting of where the error of a learned rule comes from. Picture the whole training procedure as random: a fresh training set gives a fresh f^\hat f. Fix an input xx and write y=f(x)+εy = f(x) + \varepsilon, where f(x)=E[Y∣X=x]f(x) = \mathbb E[Y \mid X = x] and the noise ε\varepsilon has mean 00 and variance σ2\sigma^2.

Theorem— Bias–variance decomposition

If the new noise ε\varepsilon is independent of the training set, then, averaging over both,

E[(y−f^(x))2]=σ2+(E[f^(x)]−f(x))2+Var⁡[f^(x)].\mathbb E\big[(y - \hat f(x))^2\big] = \sigma^2 + \big(\mathbb E[\hat f(x)] - f(x)\big)^2 + \operatorname{Var}\big[\hat f(x)\big].

The three terms are the noise, the squared bias and the variance of the learned prediction at xx.

Proof

Write fˉ=E[f^(x)]\bar f = \mathbb E[\hat f(x)] and expand y−f^(x)=ε+(f(x)−fˉ)+(fˉ−f^(x))y - \hat f(x) = \varepsilon + (f(x) - \bar f) + (\bar f - \hat f(x)). Squaring gives three squares and three cross terms. The squares have expectations σ2\sigma^2, (f(x)−fˉ)2(f(x) - \bar f)^2 and Var⁡[f^(x)]\operatorname{Var}[\hat f(x)]. The cross terms with ε\varepsilon vanish because ε\varepsilon has mean zero and is independent of f^\hat f; the remaining cross term is 2(f(x)−fˉ) E[fˉ−f^(x)]=02(f(x) - \bar f)\,\mathbb E[\bar f - \hat f(x)] = 0 by the definition of fˉ\bar f. Averaging over xx gives the same identity for the expected test error.

∎

Two things about this identity are often misremembered. It is an identity for squared error, not a law of nature: for the 0–1 loss there is no clean additive version, and several competing definitions exist. And it says nothing about how bias and variance move as a model grows. The familiar "trade-off" — more flexibility, less bias, more variance — is an empirical tendency of classical model families, and the end of this lesson shows a family where it fails.

The identity is easy to check by brute force. Below, kk-nearest-neighbour regression (predict the average label of the kk closest training points) is trained on 400 independent training sets of 100 points each, and each term is measured directly.

python
import numpy as np

rng = np.random.default_rng(7)
f = lambda x: np.sin(3 * x) + 0.5 * x          # the true regression function
sigma = 0.4                                    # noise standard deviation
n, reps = 100, 400                             # training-set size, number of training sets
x_test = np.linspace(0.05, 2.95, 60)           # fixed test inputs

def knn_predict(x_tr, y_tr, x_new, k):
    """k-nearest-neighbour regression in one dimension."""
    d = np.abs(x_new[:, None] - x_tr[None, :])
    idx = np.argpartition(d, k - 1, axis=1)[:, :k]
    return y_tr[idx].mean(axis=1)

print(f"{'k':>4} {'bias^2':>8} {'variance':>9} {'noise':>7} {'sum':>7} {'test MSE':>9}")
for k in [1, 3, 10, 30, 80]:
    preds = np.empty((reps, x_test.size))
    test_err = np.empty(reps)
    for r in range(reps):                      # a fresh training set each time
        x_tr = rng.uniform(0, 3, n)
        y_tr = f(x_tr) + rng.normal(0, sigma, n)
        preds[r] = knn_predict(x_tr, y_tr, x_test, k)
        y_new = f(x_test) + rng.normal(0, sigma, x_test.size)   # fresh labels at the test inputs
        test_err[r] = np.mean((y_new - preds[r]) ** 2)
    bias2 = np.mean((preds.mean(axis=0) - f(x_test)) ** 2)
    var = np.mean(preds.var(axis=0))
    print(f"{k:4d} {bias2:8.4f} {var:9.4f} {sigma**2:7.4f} {bias2 + var + sigma**2:7.4f} {test_err.mean():9.4f}")
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.
DefinitionsH

Uniform convergence: the price of choosing

One rule, chosen in advance

For a single rule ff fixed before seeing the data, with a loss between 0 and 1, the empirical risk is an average of nn independent bounded terms, and Hoeffding's inequality (Probability theory) controls its deviation:

Pr⁡(∣R^n(f)−R(f)∣>ε)≤2e−2nε2.\Pr\big(|\hat R_n(f) - R(f)| > \varepsilon\big) \le 2 e^{-2 n \varepsilon^2}.

That is the whole justification of a held-out test set: the model was fixed before the test data were seen, so its test error is an honest estimate with error of order 1/n1/\sqrt n.

Many rules, one of them chosen

ERM chooses f^\hat f after seeing the data, so this argument does not apply to it. The way round is to demand more: control the deviation for every rule in the class at once. If sup⁡f∈F∣R^n(f)−R(f)∣≤ε\sup_{f \in \mathcal F} |\hat R_n(f) - R(f)| \le \varepsilon, then whichever rule the data lead us to, its training error is within ε\varepsilon of its risk, and

R(f^)≤R^n(f^)+ε≤R^n(fF)+ε≤R(fF)+2ε,R(\hat f) \le \hat R_n(\hat f) + \varepsilon \le \hat R_n(f_{\mathcal F}) + \varepsilon \le R(f_{\mathcal F}) + 2\varepsilon ,

so the estimation error is at most 2ε2\varepsilon. This is uniform convergence, and for a finite class it costs only a logarithm.

Theorem— Uniform convergence for a finite class

Let F\mathcal F be finite and the loss take values in [0,1][0, 1]. With probability at least 1−δ1 - \delta over the sample, simultaneously for every f∈Ff \in \mathcal F,

∣R^n(f)−R(f)∣≤ln⁡(2∣F∣/δ)2n.|\hat R_n(f) - R(f)| \le \sqrt{\frac{\ln(2|\mathcal F|/\delta)}{2n}} .

Proof

Call ff bad if its deviation exceeds ε\varepsilon. By Hoeffding, each ff is bad with probability at most 2e−2nε22e^{-2n\varepsilon^2}. The probability that some ff is bad is at most the sum of these, 2∣F∣e−2nε22|\mathcal F| e^{-2n\varepsilon^2} (the union bound). Setting this equal to δ\delta and solving for ε\varepsilon gives the stated bound.

∎

The class enters only through ln⁡∣F∣\ln |\mathcal F|: the number of nats needed to name one of its members. At δ=0.05\delta = 0.05, a class of a million rules (2202^{20}) puts ln⁡(221/0.05)≈17.6\ln(2^{21}/0.05) \approx 17.6 in the numerator, against ln⁡40≈3.7\ln 40 \approx 3.7 for a single rule: fewer than five times as many examples buy the same accuracy for a million times as many rules. That is Occam's razor with a price tag: a rule you could have described in 20 bits is worth trusting from far fewer examples than one that needs 20,000.

Infinite classes: the VC dimension

A class of all straight lines is infinite, yet it plainly cannot fit everything. What matters is not how many rules there are but how many different labellings of the data they can produce.

Definition— Shattering and VC dimension

A class F\mathcal F of binary classifiers shatters a set of points x1,…,xmx_1, \dots, x_m if every one of the 2m2^m possible labellings of those points is produced by some f∈Ff \in \mathcal F. The Vapnik–Chervonenkis (VC) dimension of F\mathcal F is the size of the largest set it shatters (infinite if there is no largest).

three points: all 8 labellings by a linefour points: this labelling failsthe two pairs' diagonals cross,so no line can separate them
Half-planes in the plane have VC dimension 3. Left: three points not on a line, and a line producing each of the 2³ = 8 labellings (filled points on one side, hollow on the other). Right: for four points, some labelling always fails; here the 'diagonal' labelling cannot be produced by any line. For four points with one inside the triangle of the others, the failing labelling is the inner point against the outer three.

Some standard values: thresholds on the line, 1[x>t]\mathbf 1[x > t], have VC dimension 1; intervals have 2; half-planes in R2\mathbb R^2 have 3; linear classifiers in Rd\mathbb R^d (with an intercept) have d+1d + 1; axis-aligned rectangles in the plane have 4. But the VC dimension is not a parameter count. The one-parameter class 1[sin⁡(ωx)>0]\mathbf 1[\sin(\omega x) > 0] has infinite VC dimension, because a fast enough sine can weave through any labelling of suitably placed points.

Two results make the VC dimension dd the right measure. The Sauer–Shelah lemma says that a class of VC dimension dd can produce at most ∑i=0d(ni)≤(en/d)d\sum_{i=0}^{d} \binom{n}{i} \le (en/d)^d labellings of nn points — polynomially many, not 2n2^n. Feeding that count into a union-bound argument (with a clever "ghost sample" to handle the infinite class) gives a VC bound: with probability at least 1−δ1 - \delta, for all f∈Ff \in \mathcal F,

∣R^n(f)−R(f)∣≤8n(dln⁡2end+ln⁡4δ).|\hat R_n(f) - R(f)| \le \sqrt{\frac{8}{n}\Big(d \ln\frac{2en}{d} + \ln\frac{4}{\delta}\Big)} .

And the fundamental theorem of statistical learning says that a class of binary classifiers can be learned to any accuracy from finitely many examples, for every distribution PP, if and only if its VC dimension is finite; the number of examples needed then grows like (d+ln⁡(1/δ))/ε2(d + \ln(1/\delta))/\varepsilon^2, and no algorithm can do better in the worst case. Vapnik and Chervonenkis proved the uniform convergence results in the Soviet Union in 1971; Leslie Valiant's 1984 paper "A theory of the learnable" gave computer science the PAC ("probably approximately correct") framing in which they are now usually taught.

A third, more modern measure looks at the data you actually have. The Rademacher complexity of F\mathcal F on a sample asks how well the class can correlate with pure noise: draw random signs σi=±1\sigma_i = \pm 1 and compute Eσsup⁡f∈F1n∑iσif(xi)\mathbb E_\sigma \sup_{f \in \mathcal F} \frac1n \sum_i \sigma_i f(x_i). A class that can match random signs well can fit anything, and the generalisation gap is bounded by about twice this quantity. Hold on to that definition; it is the key to the experiment in the next section.

Here is uniform convergence measured. The class is all thresholds 1[x>t]\mathbf 1[x > t] on [0,1][0, 1]; inputs are uniform, the true boundary is at 0.50.5, and 20% of labels are flipped, so every threshold's risk is known exactly: R(t)=0.2+0.6 ∣t−0.5∣R(t) = 0.2 + 0.6\,|t - 0.5|.

python
import numpy as np

rng = np.random.default_rng(11)
eta = 0.2                                  # label-noise rate
t_grid = np.linspace(0, 1, 2001)           # the class: h_t(x) = 1 if x > t, for every t on a fine grid
true_risk = eta + (1 - 2 * eta) * np.abs(t_grid - 0.5)   # exact risk of each h_t (best: t = 0.5)

def empirical_risks(x, y):
    """Training error of every threshold in t_grid at once, using sorting and cumulative sums."""
    order = np.argsort(x)
    xs, ys = x[order], y[order]
    ones_left = np.concatenate([[0], np.cumsum(ys)])          # points at or below the cut labelled 1
    zeros_right = np.concatenate([[0], np.cumsum((1 - ys)[::-1])])[::-1]   # above the cut, labelled 0
    cut = np.searchsorted(xs, t_grid, side="right")            # how many points have x <= t
    return (ones_left[cut] + zeros_right[cut]) / x.size

def vc_bound(n, d=1, delta=0.05):
    return np.sqrt(8 / n * (d * np.log(2 * np.e * n / d) + np.log(4 / delta)))

print(f"{'n':>5} {'fixed h':>8} {'sup gap':>8} {'x sqrt(n)':>9} {'95th pct':>9} {'VC bound':>9} {'ERM excess':>11}")
for n in [50, 200, 800, 3200]:
    fixed, sup, excess = [], [], []
    for _ in range(300):
        x = rng.uniform(0, 1, n)
        y = ((x > 0.5) ^ (rng.random(n) < eta)).astype(float)  # flip each label with probability eta
        emp = empirical_risks(x, y)
        fixed.append(abs(emp[1000] - true_risk[1000]))         # one h, chosen before seeing the data
        sup.append(np.max(np.abs(emp - true_risk)))             # the worst h in the class
        excess.append(true_risk[np.argmin(emp)] - eta)          # what ERM loses against the best h
    print(f"{n:5d} {np.mean(fixed):8.4f} {np.mean(sup):8.4f} {np.mean(sup) * np.sqrt(n):9.3f} "
          f"{np.quantile(sup, 0.95):9.4f} {vc_bound(n):9.3f} {np.mean(excess):11.4f}")
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

Read the columns from left to right. The deviation of one fixed rule (0.0116 at n=800n = 800) is about a third of the worst deviation over the whole class (0.0326): that factor is the price of choosing. Both shrink like 1/n1/\sqrt n, as the nearly constant fourth column shows. The VC bound, 0.357 at n=800n = 800, is true — it sits above the 95th percentile of the worst-case gap, 0.0479 — but about seven times too large. And the last column falls far faster than 1/n1/\sqrt n: ERM's excess risk drops by roughly a factor of 4 each time nn quadruples.

ExplanationH

When the theory meets a deep network

Apply this machinery to a modern image classifier and it collapses. The VC dimension of a network with WW weights and piecewise-linear activations is at least of the order of WW, and can be larger by a factor of the depth and a logarithm, so a network with ten million weights trained on fifty thousand images gets a VC bound far above 1: true, and useless.

In 2016 Zhang, Bengio, Hardt, Recht and Vinyals made the problem sharp (Zhang et al., 2017). They took standard convolutional networks and standard training recipes, replaced the CIFAR-10 labels with random ones, and trained again. The networks reached zero training error on the random labels, only somewhat more slowly. With the true labels the same networks, trained the same way, generalised well.

Think about what that does to the measures above. The class can fit random signs on this very sample, so its Rademacher complexity on this data is essentially maximal, and any bound that depends only on the class and the sample is vacuous. Whatever makes the networks generalise on real labels must depend on something else: the training algorithm, the structure of real images, or the interaction between them. The classical decomposition still applies — it is an identity — but the classical picture of capacity, in which complexity is a property of the class, has lost its explanatory grip.

So the question changes from "how big is the class?" to "which member of the class does the algorithm pick, and why does that one generalise?" When a model can fit the data in infinitely many ways, the learning algorithm is quietly choosing among them, and that choice is a form of regularisation nobody wrote down.

ComputationC

Double descent, demonstrated

The cleanest place to watch this happen is random-features regression, a two-layer network whose first layer is frozen at random values Rahimi and Recht introduced random features in 2007 to approximate kernel methods; Belkin et al., 2019 used them to exhibit double descent). Each input x∈Rdx \in \mathbb R^{d} is mapped to pp features ϕj(x)=max⁡(0,wj⋅x)\phi_j(x) = \max(0, w_j \cdot x), with the wjw_j drawn at random and never trained, and we fit f(x)=∑jθjϕj(x)f(x) = \sum_j \theta_j \phi_j(x) by least squares. With nn training points:

  • if p<np < n, least squares has a unique solution, and we are in classical territory;
  • if p≥np \ge n, the features can usually fit the training data exactly, in infinitely many ways. We take the one with the smallest Euclidean norm ∥θ∥\|\theta\|, the minimum-norm interpolant, which is what the pseudo-inverse computes. (The code computes it through the small n×nn \times n matrix FF⊤FF^{\top}, using the identity F+=F⊤(FF⊤)+F^{+} = F^{\top}(FF^{\top})^{+}, which is much cheaper than working with FF itself when pp is large.)

The experiment below uses n=100n = 100 training points in d=20d = 20 dimensions, a target that is mostly linear with a sinusoidal wiggle, and noise with standard deviation 0.3, and sweeps pp from 10 to 4000. For comparison it also fits ridge regression with a small penalty λ=0.1\lambda = 0.1. Each row is the median over 20 independent worlds.

python
import numpy as np

d, n, n_test, sigma, lam = 20, 100, 1000, 0.3, 0.1   # input dim, training size, test size, noise sd, ridge penalty
widths = [10, 30, 50, 70, 90, 100, 110, 130, 170, 250, 400, 700, 1200, 2000, 4000]

def make_data(rng, m, beta):
    X = rng.normal(size=(m, d))
    y = X @ beta + 0.5 * np.sin(2 * X[:, 0]) + rng.normal(0, sigma, m)   # linear part + a wiggle + noise
    return X, y

results = {p: [] for p in widths}
for seed in range(20):                                     # 20 independent worlds; we report medians
    rng = np.random.default_rng(seed)
    beta = rng.normal(size=d) / np.sqrt(d)
    X, y = make_data(rng, n, beta)
    Xt, yt = make_data(rng, n_test, beta)
    W = rng.normal(size=(d, max(widths)))                  # random first-layer weights, never trained
    A, At = np.maximum(X @ W, 0), np.maximum(Xt @ W, 0)    # ReLU features; the first p columns are a width-p model
    for p in widths:
        F, Ft = A[:, :p] / np.sqrt(p), At[:, :p] / np.sqrt(p)
        evals, U = np.linalg.eigh(F @ F.T)                 # work with the n x n Gram matrix: cheap when p is large
        Uy = U.T @ y
        keep = evals > 1e-10 * evals.max()
        theta = F.T @ (U[:, keep] @ (Uy[keep] / evals[keep]))   # least squares; the minimum-norm interpolant once p >= n
        theta_ridge = F.T @ (U @ (Uy / (evals + lam)))          # ridge regression, from the same decomposition
        results[p].append([np.mean((F @ theta - y) ** 2), np.mean((Ft @ theta - yt) ** 2),
                           np.linalg.norm(theta), np.mean((Ft @ theta_ridge - yt) ** 2)])

print(f"{'p':>5} {'p/n':>5} {'train MSE':>10} {'test MSE':>9} {'|theta|':>8} {'ridge test':>11}   test MSE, log scale")
for p in widths:
    train, test, norm, ridge = np.median(results[p], axis=0)
    bar = "#" * int(round(8 * np.log10(test / 0.2)))
    print(f"{p:5d} {p / n:5.1f} {train:10.4f} {test:9.3f} {norm:8.1f} {ridge:11.3f}   {bar}")
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.
101001000number of random features p (log scale)0.25110100test MSE (log scale)p = n = 100: interpolation thresholdclassical Usecond descentminimum-norm least squaresridge, λ = 0.1
Test error of random-features regression against the number of features p, both on log scales (median of 20 runs from the code above, n = 100 training points). The minimum-norm fit (solid) traces a classical U for p below n, spikes at the interpolation threshold p = n, then descends again to below its classical best. Ridge regression with a small penalty (dashed) removes the spike.

Why does this happen? At p=np = n the feature matrix is square, and a random square matrix almost always has a few tiny singular values. Interpolating the noise then needs enormous coefficients along those directions, and enormous coefficients make wild predictions between the training points: the variance term of the decomposition explodes. Once pp is well beyond nn, there are many ways to interpolate, and the minimum-norm one spreads the fit thinly over many features. The noise still has to be absorbed somewhere, but it is absorbed in many directions, each of which barely affects predictions at new points. In linear models this is now understood precisely: Bartlett, Long, Lugosi and Tsigler characterised when such benign overfitting happens (roughly, when there are many unimportant directions with small but non-negligible variance), and Hastie, Montanari, Rosset and Tibshirani and Mei and Montanari computed the whole curve exactly in the limit where nn, pp and dd grow together. As p→∞p \to \infty, minimum-norm random-features regression becomes interpolation with a kernel, choosing the smoothest interpolant in that kernel's sense.

The ridge column shows the other half of the story. A small explicit penalty caps the coefficients, the spike disappears, and the error decreases almost steadily with pp. Nakkiran, Venkat, Kakade and Ma proved that in some linear settings a well-tuned penalty removes double descent entirely. The peak is a symptom of interpolating noise with no control on the norm, not a law about big models.

But nobody trains a deep network by computing a pseudo-inverse. Where does the "minimum norm" come from? From the optimiser.

Theorem— Gradient descent finds the minimum-norm interpolant

Let FF be an n×pn \times p matrix of rank nn, with p>np > n. Gradient descent on 12∥Fθ−y∥2\tfrac12\|F\theta - y\|^2, started at θ0=0\theta_0 = 0 with a small enough constant step size, converges to the minimum-norm solution θ†=F⊤(FF⊤)−1y\theta^\dagger = F^{\top}(FF^{\top})^{-1}y.

Proof

Every gradient F⊤(Fθ−y)F^{\top}(F\theta - y) lies in the row space of FF (the span of its rows). Starting from zero, every iterate is a sum of such vectors, so it stays in the row space. With a step size below 2/σmax⁡(F)22/\sigma_{\max}(F)^2, the iterates converge to some minimiser, and since the minimum is zero, to an interpolant. The interpolants form the set θ†+ker⁡F\theta^\dagger + \ker F, and the row space is the orthogonal complement of ker⁡F\ker F, so the only interpolant in the row space is θ†\theta^\dagger, which by Pythagoras is the shortest one.

∎

This is implicit regularisation: nobody asked for a small norm, but the algorithm delivered one. Analogous results hold beyond least squares — gradient descent on logistic regression with separable data converges in direction to the maximum-margin classifier (Soudry et al.) — and in deep networks the implicit bias of stochastic gradient descent, weight decay, early stopping and the architecture together play the role that an explicit penalty plays in ridge regression. Nakkiran et al. showed double descent in real deep networks too, against width and even against the number of training epochs, most visibly when labels are noisy. A Python exercise below lets you watch gradient descent arrive at the minimum-norm solution.

ExplanationH

What theory explains, and what it does not (2026)

Here is a working statistician's map of the territory as of late 2026: what is established, what is partly understood, and what remains open. It changes every year, and the boundaries are argued over.

Established. The bias–variance identity; uniform convergence, VC and Rademacher theory for classical model classes, with matching lower bounds; minimax rates for nonparametric estimation. Double descent and benign overfitting in linear, kernel and random-features models, with exact asymptotic formulas. The implicit bias of gradient descent in linear models and in some simple networks. Algorithmic stability: an algorithm whose output changes little when one training point changes generalises, and stochastic gradient descent run for few enough steps is stable in this sense (Hardt, Recht and Singer) — a bound that depends on the algorithm, not just the class.

Partly understood. In a particular infinite-width limit, a network trained by gradient descent behaves like a kernel method with a fixed kernel, the neural tangent kernel (Jacot, Gabriel and Hongler). The theory is clean, but in that regime the network does not learn features: its internal representation barely moves. Real networks move far from their initialisation, and that feature learning is much of their power. Other limits keep feature learning — mean-field analyses and the "maximal update" parameterisation of Yang and Hu, which practitioners use to transfer learning-rate settings from small models to large ones — but a general theory of what features are learned, and why they generalise, does not exist. Generalisation bounds that are non-vacuous for trained networks do exist, via PAC-Bayes and compression arguments (Dziugaite and Roy, 2017; for language models, Lotfi et al., 2023). They are a real achievement, and they are still far looser than a held-out test set.

Open, or contested. Nagarajan and Kolter built settings where gradient descent generalises yet any two-sided uniform convergence bound is provably vacuous, suggesting that the uniform-convergence route itself may not be the right one for deep learning. Scaling laws — test loss falling as a smooth power law in model size, data and compute (Hoffmann et al., 2022, and the earlier work it revised) — are empirical regularities with several partial theoretical explanations and no consensus one. Phenomena such as grokking, where test accuracy jumps long after training accuracy saturates, and the "emergence" of abilities at scale (which some argue is partly an artefact of the metrics chosen) are actively studied. And for large language models trained for roughly one pass over enormous corpora, training and held-out loss on the same distribution are nearly equal; the classical generalisation gap is not where the mystery lives. The live questions are about out-of-distribution behaviour, in-context learning, and what exactly a model has learned — questions the iid framework does not even pose.

In practice, then, theory shapes intuitions and some recipes (regularisation, the value of data, hyperparameter transfer), while models are chosen and trusted on the basis of held-out evaluation. That makes evaluation itself a statistical problem, with its own sampling error, clustering and overfitting; it is the subject of The statistics of evaluating AI.

Much of the open territory is about assumptions rather than algebra. Every result in this lesson assumes iid data from a fixed distribution; deployed models meet shifted distributions, adversarial inputs and feedback loops in which their own outputs become tomorrow's training data. A bound is a statement about its assumptions, and only as useful as they are true.

Common misconceptionsH

Common misconceptions

Misconception

"Double descent proves the bias–variance decomposition wrong." The decomposition is an identity and always holds. What fails is the assumption that variance rises monotonically with the number of parameters. In random-features regression the variance peaks at p=np = n and falls after it, because the minimum-norm interpolant becomes more stable as features are added.

Misconception

"More parameters always means more overfitting." Capacity is not a parameter count. A one-parameter sine classifier has infinite VC dimension; a network with millions of parameters, trained by gradient descent with weight decay, may select a simple function. What matters is the effective complexity of the function the whole procedure selects.

Misconception

"Zero training error on noisy data means the model will generalise badly." Sometimes it does (at p=np = n above, catastrophically), and sometimes the damage is mild or negligible. Whether interpolation is benign, tempered or catastrophic depends on the geometry of the features and the algorithm, and is now well understood in linear and kernel models.

Misconception

"VC bounds are useless, so learning theory is irrelevant to practice." The constants are loose, but the theory explains why held-out sets work, why ln⁡∣F∣\ln |\mathcal F| rather than ∣F∣|\mathcal F| is the price of choosing, why sample sizes scale like 1/ε21/\varepsilon^2, and — through the lower bounds — what no algorithm can achieve without assumptions on the distribution.

Misconception

"Double descent means regularisation is unnecessary." In the experiment above a small ridge penalty beat the unregularised interpolant at every width. Implicit regularisation is still regularisation; turning off explicit regularisation and hoping for the second descent is rarely the best plan.

Exercises

Exercises

1. Statistical learning theory

Warm-upHuman

A classifier on the real line predicts 1 for points inside a closed interval [a,b][a, b] and 0 outside, where a≤ba \le b may be chosen freely. What is the VC dimension of this class?

2. Statistical learning theory

CoreHuman

A team chooses among ∣F∣=220|\mathcal F| = 2^{20} candidate classification rules by minimising training error (0–1 loss). Using the finite-class bound ln⁡(2∣F∣/δ)/(2n)\sqrt{\ln(2|\mathcal F|/\delta)/(2n)}, what is the smallest whole number of training examples nn that guarantees, with probability at least 95% (δ=0.05\delta = 0.05), that every rule's training error is within ε=0.02\varepsilon = 0.02 of its true error?

3. Statistical learning theory

CoreHuman

In the random-features experiment, the minimum-norm least-squares fit has test error 0.670 with p=30p = 30 features, 69.5 with p=n=100p = n = 100, and 0.364 with p=4000p = 4000. What is the main reason for the spike at p=np = n?

Choose one

4. Statistical learning theory

CoreHuman

Zhang et al. (2017) trained standard image classifiers on CIFAR-10 with the labels replaced by random ones, and the networks reached zero training error. Which conclusions follow? Select all that apply.

Choose all that apply

5. Statistical learning theory

CoreComputational

You have retrained a model on many independent training sets and stored its predictions in an array preds of shape (reps, m): row r holds the predictions of the r-th trained model at m fixed test inputs. The true regression function at those inputs is truth, shape (m,).

Write bias_variance(preds, truth) returning a pair (bias2, variance): the squared bias and the variance of the predictions, each averaged over the m test inputs. Use the population variance (divide by reps, NumPy's default).

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

6. Statistical learning theory

StretchComputational

Implicit regularisation in action. Write gd_from_zero(F, y, lr, steps) that runs plain gradient descent on 12∥Fθ−y∥2\tfrac12\|F\theta - y\|^2, starting from θ=0\theta = 0, for steps iterations with constant step size lr, and returns θ\theta.

The tests use a wide matrix (p>np > n), for which infinitely many θ\theta interpolate the data, and check that your answer is the minimum-norm interpolant, np.linalg.pinv(F) @ y.

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

7. Statistical learning theory

Warm-upHuman

As the number of parameters grows past the number of training points, test error can first spike and then fall again, sometimes below its best value in the classical regime. What is this phenomenon called (two words)?

Further reading and resources