Machine Learning · Lecture 6

Lecture 6
Learning Theory: PAC, VC and Rademacher

Part I · Foundations of supervised learning  |  the generalisation gap, Hoeffding's inequality and test-set bounds, PAC learning, finite classes, no free lunch, shattering and VC dimension, the Sauer–Shelah lemma, Rademacher complexity, margin bounds, double descent, benign overfitting, PAC-Bayes  |  reading: Shalev-Shwartz & Ben-David, Understanding Machine Learning, ch. 2–6 and 26; Mohri, Rostamizadeh & Talwalkar, Foundations of Machine Learning, ch. 2–3 and 5

Cartoon: the practice examA stick figure holds up a practice exam marked 100 percent and says: I memorised every answer! A second stick figure replies: Lovely. The real exam has new questions. 100% I memorised everyanswer! Lovely. The real examhas new questions.
Training error is a practice exam; learning theory asks when the score carries over to the real one
In this lecture
  1. The puzzle: why should training error mean anything?
  2. One classifier: Hoeffding's inequality
  3. PAC learning and finite classes
  4. No free lunch
  5. Infinite classes: shattering and VC dimension
  6. Rademacher complexity: fitting pure noise
  7. Linear classes, margins and Lipschitz losses
  8. Modern puzzles: double descent, benign overfitting, PAC-Bayes
  9. Summary, exercises, projects, reading

Every method so far was trained by making the training error small and then checked on a held-out test set. This lecture asks why the first step should help with the second. The answer is a set of probability inequalities saying that, if the class of models is not too rich compared with the amount of data, the training error of every model in the class is close to its true error, so the one we pick cannot be far off either. The work is in measuring "rich": by counting the models, by counting the labellings they can produce (VC dimension), or by how well they can fit random noise (Rademacher complexity).

These are the tools behind every "generalisation bound" you will meet in papers. They also have limits: a modern neural network can fit random labels perfectly, so bounds based only on the richness of the class say nothing about it, yet it generalises on real labels. We end with what is known about that puzzle.

By the end of this lecture you should be able to bound the error of a fixed classifier from a test set; prove the finite-class bound and use it to compute sample sizes; state what PAC learnability means and why no learner works for every problem; compute VC dimensions of simple classes and prove the Sauer–Shelah lemma; define Rademacher complexity, prove the Rademacher generalisation bound and Massart's lemma, and bound the complexity of norm-bounded linear functions; read a margin bound; and explain double descent, benign overfitting and the PAC-Bayes bound.

1 — The puzzle: why should training error mean anything?

definition 6.1 — risk, empirical risk, generalisation gap

Training data

$$S=\big((x_1,y_1),\dots,(x_n,y_n)\big)$$

are drawn independently from a distribution \(\mathcal D\) on \(\mathcal X\times\mathcal Y\). For a predictor \(h\) and a loss \(\ell\), the risk (true error) and empirical risk (training error) are

$$R(h)=\mathbb E_{(x,y)\sim\mathcal D}\,\ell\big(h(x),y\big),\qquad \hat R_S(h)=\frac1n\sum_{i=1}^n\ell\big(h(x_i),y_i\big).$$

The generalisation gap of \(h\) is \(R(h)-\hat R_S(h)\).

For classification with the 0–1 loss, \(R(h)=P\big(h(X)\ne Y\big)\).

For a predictor fixed in advance, \(\hat R_S(h)\) is an average of \(n\) independent copies of \(\ell(h(X),Y)\), so \(\mathbb E\,\hat R_S(h)=R(h)\) and the law of large numbers applies. The trouble is that we never use a predictor fixed in advance: we choose \(\hat h\) because it has small training error, and then \(\hat R_S(\hat h)\) is biased downward. How far downward depends on how many predictors we chose among, and how flexible they are. Here is the most extreme case.

data — MNIST handwritten digits and CIFAR-10

70,000 grey-scale images of handwritten digits, 28 × 28 pixels, from US Census Bureau employees and high-school students, assembled by LeCun, Cortes and Burges (1998) from NIST data. We use Michael Nielsen's copy (50,000 training, 10,000 validation and 10,000 test images, pixel values scaled to [0, 1]), as in Lecture 4. The second data set is CIFAR-10 (Krizhevsky, 2009), the one Zhang et al. used: 60,000 colour photographs of 32 × 32 pixels in ten classes (aeroplane, car, bird, cat, deer, dog, frog, horse, ship, lorry), 3,072 numbers per image, in the Parquet copy uoft-cs/cifar10 on the Hugging Face Hub.

code — a network fits random labels, on MNIST and CIFAR-10 (after Zhang et al., 2017)
import gzip, pickle, io
import numpy as np, pyarrow.parquet as pq
from PIL import Image
from sklearn.neural_network import MLPClassifier

with gzip.open('data/mnist.pkl.gz', 'rb') as f:
    (X_all, y_all), _, (X_test, y_test) = pickle.load(f, encoding='latin1')
def cifar(split, n):                                 # CIFAR-10 (the data set of Zhang et al., 2017): 32 x 32 colour photos, 10 classes
    t = pq.read_table(f'data/cifar10_{split}.parquet').to_pandas().iloc[:n]
    X = np.stack([np.asarray(Image.open(io.BytesIO(b['bytes'])), np.float32).ravel() / 255 for b in t.img])
    return X, t.label.to_numpy()
data = {'MNIST': (X_all, y_all, X_test[:5000], y_test[:5000]), 'CIFAR-10': (*cifar('train', 50000), *cifar('test', 5000))}
rng = np.random.default_rng(0)
print('data      labels replaced | wrong labels | 100% train acc. at epoch | train acc. | test acc.')
for dname, (Xa_, ya_, X_test_, y_test_) in data.items():
    idx = rng.choice(len(Xa_), 2000, replace=False)
    X, y = Xa_[idx], ya_[idx]                        # 2,000 training images; 5,000 test images with their true labels
    for frac in [0, 0.5, 1.0]:
        y_used = y.copy()
        swap = rng.random(len(y)) < frac             # replace this fraction of labels by random classes
        y_used[swap] = rng.integers(0, 10, swap.sum())
        net = MLPClassifier(hidden_layer_sizes=(512,), alpha=0, random_state=0)
        first_perfect = None
        for epoch in range(1, 401):                  # one pass through the data per call
            net.partial_fit(X, y_used, classes=np.arange(10))
            if first_perfect is None and net.score(X, y_used) == 1:
                first_perfect = epoch
        print(f'{dname:9s} {frac:15.0%} | {np.mean(y_used != y):12.1%} | {first_perfect!s:>24} |'
              f' {net.score(X, y_used):10.3f} | {net.score(X_test_, y_test_):9.3f}')
data      labels replaced | wrong labels | 100% train acc. at epoch | train acc. | test acc.
MNIST                  0% |         0.0% |                       21 |      1.000 |     0.907
MNIST                 50% |        44.4% |                      106 |      1.000 |     0.579
MNIST                100% |        90.2% |                       83 |      1.000 |     0.090
CIFAR-10               0% |         0.0% |                     None |      0.948 |     0.347
CIFAR-10              50% |        44.2% |                     None |      0.729 |     0.197
CIFAR-10             100% |        91.3% |                     None |      0.798 |     0.082

On MNIST the same network, trained the same way, reaches 100% training accuracy every time. With the true labels it gets 90.7% of new images right. With every label replaced by a random digit, it memorises all 2,000 random labels by epoch 83 and is right on 9.0% of test images, no better than guessing. Halfway between, the test accuracy falls in between. Training accuracy alone tells us nothing here: the gap between training and test accuracy ranges from 0.09 to 0.91 for one model class and one algorithm. CIFAR-10 is harder in both directions. With true labels the network reaches 94.8% training accuracy in 400 epochs but only 34.7% on test photographs (chance is 10%); with random labels it has memorised 79.8% of them by epoch 400, while its test accuracy is 8.2%. Photographs of one class vary far more than digits do, so a small fully connected network probably finds little structure that carries over to new images, and spends its capacity on memorising. Zhang et al. (2017) did this at full scale on CIFAR-10 and ImageNet with convolutional networks, which reach 100% on random labels too, and their paper, "Understanding deep learning requires rethinking generalization", is the starting point of Section 8.

Before networks, the simplest version of the problem. Suppose we have \(M\) classifiers that are pure guessers, each wrong with probability exactly ½ on new data, and we pick the one with the lowest training error.

The best of many guessers

\(M\) classifiers, each a coin flip on every example (true error 0.5), are scored on \(n\) training examples. The histogram shows their training errors; the rose bar marks the "learned" classifier with the lowest training error. The dashed lines are how low a training error could be explained by chance for one classifier (moss) and for the best of \(M\) (amber), at 95% confidence.

With \(M=1000\) guessers and \(n=50\) examples, the best one typically gets around 28% training error, and a naive reading would call that a classifier with 72% accuracy. Its true error is 50%. The amber line, from Theorem 6.2 below, says how low the best of \(M\) can fall by luck alone; it moves down only like \(\sqrt{\ln M/n}\), so a thousandfold increase in \(M\) costs about as much as dividing \(n\) by 3. This logarithm is the reason learning from finitely many examples is possible at all.

spot check 6.1

In the widget, why does the lowest training error fall as \(M\) grows, even though every classifier has true error 0.5?

What is the expected training error of one classifier chosen before seeing the data?
For a fixed classifier, \(\mathbb E\,\hat R_S=R=0.5\). The minimum of \(M\) such estimates has expectation below 0.5, and further below as \(M\) grows: selection, not learning.
notation you will see in papers

2 — One classifier: Hoeffding's inequality

Start with the case that works: one classifier, fixed before the data are seen, evaluated on \(m\) fresh examples. Its test error is an average of \(m\) independent indicators with mean \(R(h)\). The central limit theorem says how close it typically is; Hoeffding's inequality gives a guarantee that holds for every \(m\), not just in the limit.

theorem 6.1 — Hoeffding's inequality

Let \(Z_1,\dots,Z_n\) be independent with \(a_i\le Z_i\le b_i\), and \(\bar Z=\frac1n\sum Z_i\). For every \(t>0\),

$$P\big(\bar Z-\mathbb E\bar Z\ge t\big)\le\exp\!\Big(-\frac{2n^2t^2}{\sum_i(b_i-a_i)^2}\Big),$$

and the same bound holds for \(P(\bar Z-\mathbb E\bar Z\le -t)\).

For variables in \([0,1]\):

$$P\big(|\bar Z-\mathbb E\bar Z|\ge t\big)\le 2e^{-2nt^2}.$$

Chernoff's trick. For any \(\lambda>0\), by Markov's inequality applied to \(e^{\lambda\sum(Z_i-\mathbb EZ_i)}\) and independence,

$$P\Big(\sum_i(Z_i-\mathbb EZ_i)\ge nt\Big)\le e^{-\lambda nt}\prod_i\mathbb E\,e^{\lambda(Z_i-\mathbb EZ_i)}.$$

Hoeffding's lemma. If \(Z\in[a,b]\) then

$$\mathbb E\,e^{\lambda(Z-\mathbb EZ)}\le e^{\lambda^2(b-a)^2/8}.$$

Sketch:

$$\psi(\lambda)=\log\mathbb E\,e^{\lambda(Z-\mathbb EZ)}$$

has \(\psi(0)=\psi'(0)=0\), and \(\psi''(\lambda)\) is the variance of \(Z\) under the "tilted" distribution with density proportional to \(e^{\lambda z}\). Any variable in \([a,b]\) has variance at most \((b-a)^2/4\), so Taylor's theorem gives \(\psi(\lambda)\le\lambda^2(b-a)^2/8\).

Together: the probability is at most

$$\exp\big(-\lambda nt+\frac{\lambda^2}8\sum_i(b_i-a_i)^2\big).$$

Minimising over \(\lambda\) (at \(\lambda=4nt/\sum(b_i-a_i)^2\)) gives the bound. The two-sided version adds the bounds for the two tails. \(\square\)

Set \(2e^{-2mt^2}=\delta\) and solve for \(t\): with probability at least \(1-\delta\), the test error of a fixed classifier is within

$$\varepsilon=\sqrt{\frac{\ln(2/\delta)}{2m}}$$

of its true error. Nothing is assumed about the distribution or the classifier. Here it is for Lecture 4's breast-cancer data.

data — Wisconsin diagnostic breast cancer

569 fine-needle aspirates of breast masses, 212 malignant and 357 benign, each described by 30 features of the cell nuclei computed from a digitised image (W. H. Wolberg, W. N. Street, O. L. Mangasarian, University of Wisconsin, 1995; UCI Machine Learning Repository; shipped with scikit-learn). We use Lecture 4's split: 398 training and 171 test patients, stratified, seed 0.

code — how sure are we about a test error?
from scipy.stats import beta
from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.linear_model import LogisticRegression

bc = load_breast_cancer()
Xb, yb = bc.data, 1 - bc.target                      # malignant = 1, as in Lecture 4
Xtr, Xte, ytr, yte = train_test_split(Xb, yb, test_size=0.3, stratify=yb, random_state=0)
sc = StandardScaler().fit(Xtr)
clf = LogisticRegression(max_iter=5000).fit(sc.transform(Xtr), ytr)

m = len(yte); k = int((clf.predict(sc.transform(Xte)) != yte).sum())
delta = 0.05
half = np.sqrt(np.log(2 / delta) / (2 * m))          # Hoeffding, two-sided
lo_cp = beta.ppf(delta / 2, k, m - k + 1)             # exact (Clopper-Pearson) binomial interval
hi_cp = beta.ppf(1 - delta / 2, k + 1, m - k)
print(f'test errors: {k} of {m}  ->  test error {k/m:.4f}')
print(f'Hoeffding 95% interval:       [{max(0, k/m - half):.4f}, {k/m + half:.4f}]   (half-width {half:.4f})')
print(f'Clopper-Pearson 95% interval: [{lo_cp:.4f}, {hi_cp:.4f}]')
for target in [0.05, 0.01]:
    print(f'test points for half-width {target}: {int(np.ceil(np.log(2 / delta) / (2 * target**2)))}')
test errors: 8 of 171  ->  test error 0.0468
Hoeffding 95% interval:       [0.0000, 0.1506]   (half-width 0.1039)
Clopper-Pearson 95% interval: [0.0204, 0.0901]
test points for half-width 0.05: 738
test points for half-width 0.01: 18445

Eight mistakes on 171 patients: 4.7% test error, and Hoeffding guarantees the true error is below 15.1% with 95% confidence. The exact binomial (Clopper–Pearson) interval, [2.0%, 9.0%], is far tighter. Hoeffding uses only the range [0, 1]; when the error rate is small the variance \(p(1-p)\) is small too, and inequalities that use the variance (Bernstein's, or the exact binomial) do better. Hoeffding's advantage is that it extends to the much harder problem of the next section. To pin a true error down to ±1% this way would need 18,445 test points, which is one reason benchmark test sets have tens of thousands of examples.

spot check 6.2

How many test examples does Hoeffding's inequality need to guarantee that a fixed classifier's test error is within 0.1 of its true error with probability 0.95? (Round up.)

Solve \(\sqrt{\ln(2/\delta)/(2m)}\le0.1\) with \(\delta=0.05\).
\(m\ge\ln(40)/(2\times0.01)=3.689/0.02=184.4\), so 185.
history — from Chebyshev to Hoeffding

Chebyshev's inequality (1867) gave the first finite-sample bound, decaying like \(1/(nt^2)\). Exponential bounds came with Sergei Bernstein in the 1920s and Herman Chernoff's 1952 paper on tests based on sums of observations, which introduced the "exponentiate and apply Markov" trick (Chernoff later said the idea was due to Herman Rubin). Wassily Hoeffding, a statistician who had moved from Berlin to the University of North Carolina after the war, published the version for bounded variables in 1963. It became the workhorse of learning theory because it needs nothing but boundedness.

3 — PAC learning and finite classes

A learning algorithm takes a sample and returns a predictor. What should it promise? It cannot promise to be right on every sample: an unlucky sample (every patient in it benign, say) defeats any method. And it cannot promise zero error: there are only finitely many examples. Valiant's answer (1984) is to promise that the result is probably (with probability at least \(1-\delta\) over the sample) approximately (within \(\varepsilon\)) correct.

definition 6.2 — PAC learnability

A hypothesis class \(\mathcal H\) of classifiers is PAC learnable if there is an algorithm \(A\) and a function \(n_{\mathcal H}(\varepsilon,\delta)\) such that for every \(\varepsilon,\delta\in(0,1)\) and every distribution \(\mathcal D\) on \(\mathcal X\), if the labels are given by some \(f\in\mathcal H\) and \(n\ge n_{\mathcal H}(\varepsilon,\delta)\), then with probability at least \(1-\delta\) over \(S\sim\mathcal D^n\),

$$R\big(A(S)\big)\le\varepsilon.$$

\(\mathcal H\) is agnostic PAC learnable if the same holds for every distribution \(\mathcal D\) on \(\mathcal X\times\mathcal Y\), with no assumption about the labels, and the guarantee is

$$R\big(A(S)\big)\le\min_{h\in\mathcal H}R(h)+\varepsilon.$$

The smallest such \(n_{\mathcal H}(\varepsilon,\delta)\) is the sample complexity.

Three features deserve a comment. The guarantee holds for every distribution, so nothing about the data needs to be known. The first version (the "realisable" case) assumes some member of the class is perfect, which is rarely true; the agnostic version only asks to compete with the best member of the class. And Valiant also asked for the algorithm to run in polynomial time; we follow most of the statistics literature in ignoring computation here.

Compare the agnostic guarantee with the decomposition of Lecture 5, Section 7. If \(R^*\) is the Bayes risk,

$$R(\hat h)-R^*=\underbrace{\min_{h\in\mathcal H}R(h)-R^*}_{\text{approximation error}}+\underbrace{R(\hat h)-\min_{h\in\mathcal H}R(h)}_{\text{estimation error}}.$$

PAC learning is a guarantee on the estimation error alone. The approximation error is the price of the class, and no amount of data reduces it.

theorem 6.2 — finite classes: uniform convergence

Let \(\mathcal H\) be finite and the loss take values in \([0,1]\). With probability at least \(1-\delta\) over \(S\sim\mathcal D^n\), simultaneously for every \(h\in\mathcal H\),

$$\big|R(h)-\hat R_S(h)\big|\le\varepsilon_n,\qquad \varepsilon_n=\sqrt{\frac{\ln|\mathcal H|+\ln(2/\delta)}{2n}}.$$

Consequently the empirical risk minimiser \(\hat h\) satisfies

$$R(\hat h)\le\min_{h\in\mathcal H}R(h)+2\varepsilon_n,$$

and \(\mathcal H\) is agnostic PAC learnable with

$$n_{\mathcal H}(\varepsilon,\delta)\le\Big\lceil\frac{2\big(\ln|\mathcal H|+\ln(2/\delta)\big)}{\varepsilon^2}\Big\rceil.$$

For each fixed \(h\), Theorem 6.1 gives

$$P\big(|R(h)-\hat R_S(h)|>\varepsilon\big)\le2e^{-2n\varepsilon^2}.$$

The probability that this happens for at least one \(h\) is at most the sum over \(h\) (the union bound): \(2|\mathcal H|e^{-2n\varepsilon^2}\). Setting this equal to \(\delta\) and solving gives \(\varepsilon_n\).

On the event that all the gaps are at most \(\varepsilon_n\), let \(h^*\) minimise \(R\) over \(\mathcal H\). Then

$$R(\hat h)\le\hat R_S(\hat h)+\varepsilon_n\le\hat R_S(h^*)+\varepsilon_n\le R(h^*)+2\varepsilon_n,$$

using the gap bound for \(\hat h\), the fact that \(\hat h\) minimises training error, and the gap bound for \(h^*\). Requiring \(2\varepsilon_n\le\varepsilon\) gives the sample size. \(\square\)

The proof needs the bound to hold for every \(h\) at once because we do not know in advance which \(h\) the algorithm will pick. That is exactly what defeats the selection effect of the widget above. The price is \(\ln|\mathcal H|\), which has a pleasant reading: if each hypothesis can be written down in \(b\) bits, then \(|\mathcal H|\le2^b\) and \(\ln|\mathcal H|\le b\ln2\). Sample size grows with the description length of the hypotheses, a precise form of Occam's razor (Blumer et al., 1987).

When some hypothesis is perfect, the rate improves from \(1/\sqrt n\) to \(1/n\).

proposition 6.3 — finite classes, realisable case

If \(\mathcal H\) is finite and some \(h\in\mathcal H\) has \(R(h)=0\), then with probability at least \(1-\delta\), every \(h\in\mathcal H\) with zero training error has

$$R(h)\le\frac{\ln|\mathcal H|+\ln(1/\delta)}{n}.$$

Call \(h\) bad if \(R(h)>\varepsilon\). A bad \(h\) gets all \(n\) independent examples right with probability

$$(1-R(h))^n<(1-\varepsilon)^n\le e^{-\varepsilon n}.$$

By the union bound, the probability that some bad \(h\) has zero training error is less than \(|\mathcal H|e^{-\varepsilon n}\). Setting this to \(\delta\) gives

$$\varepsilon=(\ln|\mathcal H|+\ln(1/\delta))/n.\ \square$$

Real data with a class small enough to count: decision stumps ("predict malignant if feature \(f\) exceeds threshold \(t\)") and depth-2 trees on the breast-cancer data. To keep the class fixed before the data are seen, the thresholds come from a grid of 64 values across each feature's range as printed in the dataset's documentation (strictly those ranges were computed from all 569 patients, a mild leak we ignore). There are \(M=30\times64=1920\) candidate splits, so \(2M=3840\) stumps, and \(16M^3\approx1.1\times10^{11}\) depth-2 trees (a root split, a split on each side, a label on each of the four leaves).

code — a finite-class bound that says something
import re

# A threshold grid fixed by the ranges printed in the dataset's documentation (not by the training data)
rng_rows = re.findall(r'^[a-z ]+\((?:mean|standard error|worst)\):\s+([\d.]+)\s+([\d.]+)', bc.DESCR, re.M)
lo, hi = np.array(rng_rows, float).T
G = 64
grid = lo[:, None] + (hi - lo)[:, None] * np.arange(1, G + 1) / (G + 1)     # 30 features x 64 thresholds

def splits(A):            # column f*64+g is the indicator "feature f exceeds threshold g"
    return (A[:, :, None] > grid[None]).reshape(len(A), -1).astype(float)
Btr, Bte = splits(Xtr), splits(Xte)
n, M = Btr.shape

def leaf_errors(pos, cnt):  # a leaf with cnt points, pos of them malignant, labelled by majority
    return np.minimum(pos, cnt - pos)

# Class 1: stumps "predict malignant iff x_f > t" or "iff x_f <= t": |H| = 2M
err_up = Btr.T @ (1 - ytr) + (1 - Btr).T @ ytr
err_all = np.concatenate([err_up, n - err_up])
best = err_all.argmin(); col = best % M
pred = Bte[:, col] if best < M else 1 - Bte[:, col]
stump = (np.log(2 * M), err_all[best] / n, np.mean(pred != yte))

# Class 2: depth-2 trees: a root split, a split on each side, a label on each of 4 leaves: |H| = 16 M^3
P11 = Btr.T @ (Btr * ytr[:, None]); N11 = Btr.T @ Btr        # [root r, child c]: both indicators 1
pos_r, cnt_r = Btr.T @ ytr, Btr.sum(0)
eR = leaf_errors(P11, N11) + leaf_errors(pos_r[:, None] - P11, cnt_r[:, None] - N11)
P01, N01 = pos_r[None, :] - P11, cnt_r[None, :] - N11              # root 0, child 1
P00, N00 = (ytr.sum() - pos_r)[:, None] - P01, (n - cnt_r)[:, None] - N01
eL = leaf_errors(P01, N01) + leaf_errors(P00, N00)
tot = eR.min(1) + eL.min(1); r = tot.argmin(); cR, cL = eR[r].argmin(), eL[r].argmin()
lab = lambda p, c: (p > c - p).astype(int)
right = np.where(Bte[:, cR] == 1, lab(P11[r, cR], N11[r, cR]), lab(pos_r[r] - P11[r, cR], cnt_r[r] - N11[r, cR]))
left = np.where(Bte[:, cL] == 1, lab(P01[r, cL], N01[r, cL]), lab(P00[r, cL], N00[r, cL]))
tree = (np.log(16.0 * M**3), tot[r] / n, np.mean(np.where(Bte[:, r] == 1, right, left) != yte))

print(f'n = {n} training patients, M = {M} candidate splits, delta = 0.05')
print('class          ln|H|   train error   bound on test error   actual test error')
for name, (lnH, tr, te) in [('stumps', stump), ('depth-2 trees', tree)]:
    eps = np.sqrt((lnH + np.log(2 / 0.05)) / (2 * n))
    print(f'{name:13s} {lnH:6.2f}   {tr:11.4f}   {tr + eps:19.4f}   {te:17.4f}')
f = col // G
print(f'best stump: malignant iff {bc.feature_names[f]} {">" if best < M else "<="} {grid.ravel()[col]:.4f}')
n = 398 training patients, M = 1920 candidate splits, delta = 0.05
class          ln|H|   train error   bound on test error   actual test error
stumps          8.25        0.0678                0.1903              0.1345
depth-2 trees  25.45        0.0352                0.2265              0.0585
best stump: malignant iff mean concave points > 0.0495

Both bounds are non-vacuous: they say something a skeptic could check. With 95% confidence, the best stump has true error at most 19.0% (its actual test error is 13.5%) and the best depth-2 tree at most 22.7% (actual 5.8%). The tree class is \(3\times10^7\) times larger than the stump class, but its bound is only 0.07 looser on the gap, because size enters through a logarithm. Notice also what the bound gets wrong: it ranks stumps above trees, while the test set shows trees are much better. A bound is a worst case over all distributions, and this distribution is kinder than the worst.

spot check 6.3

Each hypothesis in a class can be described in 20 bits, and one of them is perfect. How many examples guarantee, with probability 0.99, that every hypothesis with zero training error has true error at most 0.05? (Use Proposition 6.3 and round up.)

\(|\mathcal H|\le2^{20}\), so \(\ln|\mathcal H|\le20\ln2\approx13.863\); \(\ln(1/0.01)\approx4.605\).
\(n\ge(13.863+4.605)/0.05=369.4\), so 370. The agnostic bound of Theorem 6.2 with \(\varepsilon=0.05\) would need \(2(13.863+5.298)/0.0025\approx15{,}329\): the \(1/\varepsilon^2\) of the agnostic case is expensive.

4 — No free lunch

Why restrict to a class at all? Why not let the algorithm consider every possible classifier? Because then the training data say nothing about the points they do not contain.

theorem 6.4 — no free lunch

Let \(A\) be any learning algorithm for binary classification with 0–1 loss on a domain \(\mathcal X\), and let \(n<|\mathcal X|/2\). There is a distribution \(\mathcal D\) on \(\mathcal X\times\{0,1\}\) such that some \(f:\mathcal X\to\{0,1\}\) has \(R(f)=0\), and yet

$$P_{S\sim\mathcal D^n}\Big(R\big(A(S)\big)\ge\tfrac18\Big)\ge\tfrac17.$$

Take a set \(C\subset\mathcal X\) of \(2n\) points and consider all \(T=2^{2n}\) labelling functions \(f_1,\dots,f_T\) of \(C\). Let \(\mathcal D_j\) be uniform on \(C\) with labels from \(f_j\). A sample of size \(n\) contains at most \(n\) distinct points, so at least half of \(C\) is unseen.

Fix an unseen point \(x\). Pair each \(f_j\) with the function that agrees with it everywhere except at \(x\). The two give identical samples whenever \(x\) is not sampled, so \(A\) returns the same classifier for both, and it is wrong at \(x\) for exactly one of them.

Averaging over \(j\), \(A\) errs on each unseen point half the time, so its expected error, averaged over \(j\), is at least

$$\frac12\times\frac12=\frac14.$$

Hence some \(j\) has \(\mathbb E_S\,R(A(S))\ge\tfrac14\).

Finally, a variable \(Z\in[0,1]\) with \(\mathbb EZ\ge\tfrac14\) has \(P(Z\ge\tfrac18)\ge\tfrac17\): otherwise

$$\mathbb EZ<\frac18+\frac17\cdot\frac78=\frac14.$$

See Shalev-Shwartz and Ben-David (2014), Theorem 5.1. \(\square\)

The class of all functions on an infinite domain is therefore not PAC learnable. Every successful learner carries an inductive bias: an assumption, built into the class or the algorithm, about which functions are plausible. Linear models assume a linear boundary, kNN assumes nearby points share labels, convolutional networks (Lecture 11) assume that what matters in an image does not depend on where it is. The theorem does not say learning is hopeless; it says that the assumptions do the work, and that a method good for one kind of problem must be bad for another (Wolpert, 1996).

spot check 6.4

What does the no-free-lunch theorem imply in practice?

The theorem is about a learner that must handle every possible labelling of the unseen points.
The bad distribution in the proof labels points at random: nothing in the sample predicts the rest. Real data have structure, and an inductive bias is a bet on what that structure is.
bayes — the prior is the inductive bias

A Bayesian expresses inductive bias as a prior over functions. The no-free-lunch theorem has a Bayesian reading: averaged over a uniform prior on all labellings, every learner has expected error ½ on unseen points, because under that prior the observed labels carry no information about the others. Learning happens when the prior puts its mass on functions that are simple in some sense (smooth, sparse, linear), so that the observed labels shift belief about the unobserved ones. The hypothesis class of PAC learning is the crudest prior, uniform on \(\mathcal H\) and zero outside it; Section 8's PAC-Bayes bound allows any prior.

5 — Infinite classes: shattering and VC dimension

Linear classifiers form an infinite class, so \(\ln|\mathcal H|=\infty\) and Theorem 6.2 says nothing. But on a sample of \(n\) points, an infinite class produces only finitely many different labellings, and that number is what matters.

definition 6.3 — growth function, shattering, VC dimension

For a class \(\mathcal H\) of functions \(\mathcal X\to\{0,1\}\) and points \(x_1,\dots,x_n\), the restriction

$$\mathcal H_{x_1,\dots,x_n}=\{(h(x_1),\dots,h(x_n)):h\in\mathcal H\}$$

is the set of labellings \(\mathcal H\) produces on them.

To show \(\mathrm{VCdim}(\mathcal H)\ge d\), exhibit one set of \(d\) points and realise all \(2^d\) labellings. To show \(\mathrm{VCdim}(\mathcal H)<d+1\), show that every set of \(d+1\) points has a labelling the class cannot produce. Some examples on the line: thresholds \(x\mapsto\mathbb 1[x>t]\) have VC dimension 1 (two points cannot be labelled 1 then 0); intervals have VC dimension 2 (three points cannot be labelled 1, 0, 1).

The shattering game

Drag the points (or add and remove them). Every possible labelling is listed below; a tick means the chosen class can produce it. Click a labelling to see it on the points, with a separating line or rectangle when one exists. Can you find 4 points that half-planes shatter? 5 points that rectangles shatter?

proposition 6.5 — half-planes have VC dimension 3

The class of half-planes

$$\{x\in\mathbb R^2:w^\top x+b>0\}$$

has VC dimension 3.

More generally, half-spaces in \(\mathbb R^d\) have VC dimension \(d+1\).

Three points are shattered. Take three points not on a line. Labelling all of them the same is easy (put the line far away). Otherwise one point has the minority label, and a line close to that vertex of the triangle cuts it off from the other two.

No four points are shattered. Given four points, either

  • (a) three are collinear: label the middle one differently from its two neighbours; any half-plane containing both ends of a segment contains the middle.
  • Or (b) one point lies inside the triangle formed by the others: label it 0 and the others 1; a half-plane is convex, so if it contains the three vertices it contains the whole triangle, including the inner point.
  • Or (c) the four are in convex position, forming a quadrilateral: label the two ends of one diagonal 1 and of the other diagonal 0; the diagonals cross, so the two classes' segments meet, and a line cannot separate them.

In \(\mathbb R^d\), the \(d+1\) points \(0,e_1,\dots,e_d\) are shattered, and Radon's theorem (any \(d+2\) points split into two groups whose convex hulls meet) shows no \(d+2\) points are. The case analysis above is Radon's theorem in the plane. \(\square\)

Here VC dimension equals the number of parameters (\(w_1,w_2,b\)). That is a coincidence of linear classes: the one-parameter class \(x\mapsto\mathbb 1[\sin(\omega x)>0]\) has infinite VC dimension (Exercise 3), and there are classes with many parameters and small VC dimension.

spot check 6.5

Intervals on the real line have VC dimension ; axis-aligned rectangles in the plane have VC dimension ; half-spaces in \(\mathbb R^3\) have VC dimension .

Proposition 6.5 and the shattering widget.
Intervals shatter any two points but cannot label three points 1, 0, 1. Rectangles shatter the four points of a diamond; among any five points, one is not the extreme in any of the four directions, and labelling it 0 and the rest 1 fails, because the bounding box of the four extremes contains it. Half-spaces in \(\mathbb R^d\): \(d+1\).

The key fact about VC dimension is that it controls the growth function. Below the VC dimension the growth function is \(2^n\); above it, it suddenly becomes a polynomial.

theorem 6.6 — Sauer–Shelah lemma

If \(\mathrm{VCdim}(\mathcal H)=d<\infty\), then for all \(n\),

$$\Pi_{\mathcal H}(n)\le\sum_{j=0}^{d}\binom nj,\qquad\text{and for }n\ge d,\quad \Pi_{\mathcal H}(n)\le\Big(\frac{en}{d}\Big)^d.$$

Fix points \(C=\{c_1,\dots,c_n\}\) and let \(F=\mathcal H_C\), a set of labellings of \(C\). We prove the stronger statement

$$|F|\le\#\{B\subseteq C:\ F\text{ shatters }B\}\qquad(\ast)$$

by induction on \(n\). Since \(F\) shatters no set of more than \(d\) points, the right side is at most \(\sum_{j\le d}\binom nj\).

For \(n=0\), \(F\) has at most one element (the empty labelling), and the empty set is shattered exactly when \(F\) is non-empty.

For the step, write \(C'=C\setminus\{c_1\}\), and let \(F_0\) be the set of restrictions of labellings in \(F\) to \(C'\), and \(F_1\) the set of labellings \(g\) of \(C'\) for which both extensions (\(c_1\mapsto0\) and \(c_1\mapsto1\)) lie in \(F\). Each \(g\in F_0\) comes from one or two members of \(F\), and from two exactly when \(g\in F_1\), so

$$|F|=|F_0|+|F_1|.$$

By induction, \(|F_0|\) is at most the number of subsets of \(C'\) shattered by \(F_0\), each of which is shattered by \(F\) too. And \(|F_1|\) is at most the number of subsets \(B'\subseteq C'\) shattered by \(F_1\); for each such \(B'\), \(F\) shatters \(B'\cup\{c_1\}\), because every pattern on \(B'\) comes with both values at \(c_1\). The first collection of shattered sets does not contain \(c_1\) and the second does, so they are disjoint subsets of the sets shattered by \(F\). Adding gives \((\ast)\).

For the second bound, with \(n\ge d\):

$$\sum_{j\le d}\binom nj\le\sum_{j\le d}\binom nj\big(\frac nd\big)^{d-j}\le\big(\frac nd\big)^d\sum_{j=0}^n\binom nj\big(\frac dn\big)^j=\big(\frac nd\big)^d\big(1+\frac dn\big)^n\le\big(\frac{en}d\big)^d.\ \square$$

Let us count the labellings half-planes actually produce on real data. For points in the plane with no three on a line, the exact count is \(n^2-n+2\) (Cover, 1965); Sauer–Shelah's bound for \(d=3\) is about \(n^3/6\). The code counts the labellings of \(n\) penguins in the (bill length, flipper length) plane by sweeping a line through every direction at which the order of the projections changes.

data — Palmer penguins

Measurements of 344 Adélie, Chinstrap and Gentoo penguins from three islands of the Palmer Archipelago, Antarctica, 2007–2009, collected by Kristen Gorman with the Palmer Station Long Term Ecological Research program; packaged by Horst, Hill and Gorman (2020) as palmerpenguins (CC0). As in Lectures 1 and 3.

code — counting the labellings half-planes can make
import numpy as np
from math import comb
from palmerpenguins import load_penguins

pen = load_penguins().dropna(subset=['bill_length_mm', 'flipper_length_mm'])
P_all = pen[['bill_length_mm', 'flipper_length_mm']].drop_duplicates().to_numpy(float)
P_all = (P_all - P_all.mean(0)) / P_all.std(0)

def halfplane_labellings(P):
    """Every labelling of the points P (n x 2) cut out by a half-plane {x : u.x > t}, as rows of 0/1."""
    n = len(P)
    i, j = np.triu_indices(n, 1)
    d = P[j] - P[i]
    crit = (np.arctan2(d[:, 1], d[:, 0]) + np.pi / 2) % np.pi       # directions u where two projections tie
    crit = np.unique(np.round(np.concatenate([crit, crit + np.pi]), 9))   # merge ties (collinear triples)
    mids = (crit + np.append(crit[1:], crit[0] + 2 * np.pi)) / 2    # one direction between each pair of ties
    order = np.argsort(P @ np.array([np.cos(mids), np.sin(mids)]), axis=0)
    labs = {np.zeros(n, bool).tobytes()}
    for k in range(order.shape[1]):                     # sweep the threshold t down through the points
        lab = np.zeros(n, bool)
        for p in order[::-1, k]:
            lab[p] = True
            labs.add(lab.tobytes())
    return np.array([np.frombuffer(b, bool) for b in labs]).astype(int)

sub = np.random.default_rng(1).permutation(len(P_all))
print('  n   half-plane labellings   n^2-n+2   Sauer bound (d=3)          2^n')
D = {}
for n in [3, 4, 5, 10, 20, 50, 100]:
    D[n] = halfplane_labellings(P_all[sub[:n]])
    sauer = sum(comb(n, j) for j in range(4))
    print(f'{n:3d}   {len(D[n]):21d}   {n*n - n + 2:7d}   {sauer:17d}   {2**n:10.4g}')
  n   half-plane labellings   n^2-n+2   Sauer bound (d=3)          2^n
  3                       8         8                   8            8
  4                      14        14                  15           16
  5                      22        22                  26           32
 10                      90        92                 176         1024
 20                     374       382                1351    1.049e+06
 50                    2414      2452               20876    1.126e+15
100                    9532      9902              166751    1.268e+30

Up to five points the counts match \(n^2-n+2\) exactly; from ten points on they fall slightly short. The measurements are rounded (bills to 0.1 mm, flippers to whole millimetres), so some triples of penguins lie exactly on a line, and a half-plane cannot separate the middle penguin from the two ends. (The count of 90 at \(n=10\) was checked by testing all 1,024 labellings for linear separability with a linear program.) The striking column is the last: with 100 penguins there are \(1.3\times10^{30}\) conceivable labellings, and half-planes make fewer than ten thousand of them. That collapse is what makes learning from 100 examples possible.

spot check 6.6

A class has VC dimension 2. What is the Sauer–Shelah bound on the number of labellings it can produce on 10 points?

\(\binom{10}0+\binom{10}1+\binom{10}2\).
\(1+10+45=56\), compared with \(2^{10}=1024\) possible labellings. Intervals on the line achieve exactly this: \(1+\binom{11}2=56\).

Replacing \(|\mathcal H|\) by the growth function in Theorem 6.2 gives the classical result. The proof needs one more idea (comparing the sample with a second, "ghost" sample), and we give a complete proof of the version below in Section 6.

theorem 6.7 — the VC bound and the fundamental theorem of PAC learning

(a) Let \(\mathcal H\) be a class of classifiers with VC dimension \(d\), with the 0–1 loss, and \(n\ge d\). With probability at least \(1-\delta\), for every \(h\in\mathcal H\),

$$R(h)\le\hat R_S(h)+\sqrt{\frac{2d\ln(en/d)}{n}}+\sqrt{\frac{\ln(1/\delta)}{2n}}.$$

(b) For a class of binary classifiers the following are equivalent:

When \(d\) is finite the sample complexities are, for universal constants \(C_1,C_2\),

$$C_1\frac{d+\ln(1/\delta)}{\varepsilon^2}\le n_{\mathcal H}(\varepsilon,\delta)\le C_2\frac{d+\ln(1/\delta)}{\varepsilon^2}\quad\text{(agnostic)},$$ $$C_1\frac{d+\ln(1/\delta)}{\varepsilon}\le n_{\mathcal H}(\varepsilon,\delta)\le C_2\frac{d\ln(1/\varepsilon)+\ln(1/\delta)}{\varepsilon}\quad\text{(realisable)}.$$

(a) is proved in full after Lemma 6.10.

For (b): finite VC dimension gives uniform convergence by (a); uniform convergence makes ERM succeed exactly as in the proof of Theorem 6.2; a successful agnostic learner is in particular a realisable one. For the converse, if the VC dimension is infinite, then for every \(n\) some set of \(2n\) points is shattered, and the no-free-lunch argument (Theorem 6.4) on that set defeats every learner.

The matching constants in the sample complexities take more work; see Shalev-Shwartz and Ben-David (2014), ch. 6 and 28. \(\square\)

So the dividing line between learnable and unlearnable is sharp, and it is set by one number. For half-planes (\(d=3\)) and \(n=1000\), the gap term \(\sqrt{2d\ln(en/d)/n}\) is about 0.20; for a linear classifier on all 784 MNIST pixels (\(d=785\)), even all 60,000 training images give a gap term of 0.37. The widget turns the bounds into sample sizes.

How many examples do I need?

The curves are the bounds of this section as functions of the sample size \(n\) (log scale): for a finite class, the realisable bound of Proposition 6.3 (moss) and the uniform gap of Theorem 6.2 (sky); for a class of VC dimension \(d\), the gap of Theorem 6.7 (amber). The readout gives the smallest \(n\) at which each falls below your target \(\varepsilon\).

The default \(\ln|\mathcal H|=8.25\) is the stump class above. To guarantee every stump's training error within 0.1 of its true error takes 597 patients; if one stump were perfect, 113 would be enough to guarantee that a stump with zero training error has true error below 0.1. The VC bound for half-planes with the same targets needs 7,197 examples: a valid guarantee, but a conservative one, and typical of the constants in VC theory.

history — Moscow, 1968, and Harvard, 1984

Vladimir Vapnik and Alexey Chervonenkis, working on pattern recognition at the Institute of Control Sciences in Moscow, announced the uniform convergence theorem in a 1968 note in Doklady Akademii Nauk and published the full paper in 1971. The combinatorial lemma was found independently around 1972 by Norbert Sauer, by Saharon Shelah (with Micha Perles), and by Vapnik and Chervonenkis themselves. The work was little known in the West until the 1980s. In 1984 Leslie Valiant at Harvard, approaching learning from computational complexity, defined PAC learning in "A theory of the learnable"; Blumer, Ehrenfeucht, Haussler and Warmuth (1989) showed that the VC dimension characterises it. Valiant received the 2010 Turing Award, whose citation names PAC learning first. Vapnik moved to AT&T Bell Labs in 1990, where with Corinna Cortes he developed the support vector machine of Lecture 7.

6 — Rademacher complexity: fitting pure noise

Counting labellings ignores two things: which labellings are produced on the data we actually have, and losses that are not 0 or 1. Rademacher complexity measures richness in a way that handles both, and it has a vivid meaning. Flip a fair coin for each training point, and ask how well the best function in the class can agree with the coin flips. A class that can match any pattern of noise can also match the noise in real labels, and its training error means little.

definition 6.4 — Rademacher complexity

Let \(\sigma_1,\dots,\sigma_n\) be independent random signs, each \(\pm1\) with probability ½ (Rademacher variables).

For a class \(\mathcal F\) of real-valued functions and a sample \(S=(z_1,\dots,z_n)\), the empirical Rademacher complexity is

$$\widehat{\mathfrak R}_S(\mathcal F)=\mathbb E_\sigma\Big[\sup_{f\in\mathcal F}\frac1n\sum_{i=1}^n\sigma_if(z_i)\Big],$$

and the Rademacher complexity is its average over samples,

$$\mathfrak R_n(\mathcal F)=\mathbb E_{S\sim\mathcal D^n}\,\widehat{\mathfrak R}_S(\mathcal F).$$

For classifiers with values \(\pm1\), \(\frac1n\sum\sigma_ih(x_i)\) is the fraction of points where \(h\) agrees with the signs minus the fraction where it disagrees. A class with one function has complexity 0 (the average of \(\sigma_i\) times a fixed number is 0). A class that shatters the sample can match every sign pattern and has complexity 1.

Chasing random signs

\(n\) points on a line (only their order matters). Each draw gives every point a random sign, moss up for +1 and rose down for −1. The class picks the function (shaded where it predicts +1) that agrees with as many signs as possible, and the readout shows its correlation \(\frac1n\sum\sigma_ih(x_i)\). The average over many draws estimates \(\widehat{\mathfrak R}_S\); compare it with Massart's bound \(\sqrt{2\ln\Pi(n)/n}\) from Lemma 6.10.

With \(n=50\) points, thresholds reach an average correlation of about 0.26, intervals 0.32, unions of five intervals 0.68, and the class of every labelling exactly 1. Increase \(n\) and every class except the last loses its grip on the noise, roughly like \(1/\sqrt n\). That decay is generalisation.

Two tools from probability turn this into a bound. The first extends Hoeffding's inequality from averages to any function of independent variables that no single variable can change much.

lemma 6.8 — McDiarmid's bounded-differences inequality

Let \(Z_1,\dots,Z_n\) be independent and \(g\) a function such that changing the \(i\)-th argument alone changes \(g\) by at most \(c_i\). Then for \(t>0\),

$$P\big(g(Z_1,\dots,Z_n)-\mathbb E\,g\ge t\big)\le\exp\!\Big(-\frac{2t^2}{\sum_ic_i^2}\Big),$$

and the same for the lower tail.

(Hoeffding's inequality is the case \(g=\bar Z\). The proof applies Hoeffding's lemma to the martingale differences

$$\mathbb E[g\mid Z_1,\dots,Z_i]-\mathbb E[g\mid Z_1,\dots,Z_{i-1}];$$

see Boucheron, Lugosi and Massart, 2013, Theorem 6.2.)

theorem 6.9 — the Rademacher generalisation bound

Let \(\mathcal G\) be a class of functions from \(\mathcal Z\) to \([0,1]\) (for us, \(g(x,y)=\ell(h(x),y)\) for \(h\in\mathcal H\)). With probability at least \(1-\delta\) over \(S\sim\mathcal D^n\), for every \(g\in\mathcal G\),

$$\mathbb E\,g(z)\le\frac1n\sum_{i=1}^ng(z_i)+2\,\mathfrak R_n(\mathcal G)+\sqrt{\frac{\ln(1/\delta)}{2n}},$$

and, also with probability at least \(1-\delta\), for every \(g\in\mathcal G\),

$$\mathbb E\,g(z)\le\frac1n\sum_{i=1}^ng(z_i)+2\,\widehat{\mathfrak R}_S(\mathcal G)+3\sqrt{\frac{\ln(2/\delta)}{2n}}.$$

Write \(\hat{\mathbb E}_Sg=\frac1n\sum g(z_i)\) and

$$\Phi(S)=\sup_{g\in\mathcal G}\big(\mathbb Eg-\hat{\mathbb E}_Sg\big),$$

the worst gap.

Step 1: concentration. Changing one \(z_i\) changes each \(\hat{\mathbb E}_Sg\) by at most \(1/n\), so it changes \(\Phi\) by at most \(1/n\). McDiarmid with \(c_i=1/n\) gives, with probability at least \(1-\delta\),

$$\Phi(S)\le\mathbb E\,\Phi+\sqrt{\ln(1/\delta)/(2n)}.$$

Step 2: symmetrisation. Let \(S'=(z_1',\dots,z_n')\) be an independent "ghost" sample. Since \(\mathbb Eg=\mathbb E_{S'}\hat{\mathbb E}_{S'}g\) and a supremum of averages is at most the average of suprema,

$$\mathbb E\,\Phi=\mathbb E_S\sup_g\mathbb E_{S'}\big[\hat{\mathbb E}_{S'}g-\hat{\mathbb E}_Sg\big]\le\mathbb E_{S,S'}\sup_g\frac1n\sum_i\big(g(z_i')-g(z_i)\big).$$

Swapping \(z_i\) with \(z_i'\) does not change the joint distribution, and it flips the sign of the \(i\)-th term. So inserting independent random signs \(\sigma_i\) changes nothing:

$$\mathbb E\,\Phi\le\mathbb E_{\sigma,S,S'}\sup_g\frac1n\sum_i\sigma_i\big(g(z_i')-g(z_i)\big)\le\mathbb E\sup_g\frac1n\sum_i\sigma_ig(z_i')+\mathbb E\sup_g\frac1n\sum_i(-\sigma_i)g(z_i)=2\,\mathfrak R_n(\mathcal G),$$

since \(-\sigma_i\) has the same distribution as \(\sigma_i\). Combining the steps gives the first bound.

Step 3: the data-dependent version. \(\widehat{\mathfrak R}_S(\mathcal G)\) also changes by at most \(1/n\) when one \(z_i\) changes, so with probability at least \(1-\delta/2\),

$$\mathfrak R_n\le\widehat{\mathfrak R}_S+\sqrt{\ln(2/\delta)/(2n)}.$$

Use the first bound with \(\delta/2\) and add: the confidence terms total \(3\sqrt{\ln(2/\delta)/(2n)}\). \(\square\)

The ghost sample is the key idea, and it was Vapnik and Chervonenkis's: the true error is replaced by the error on a second, imaginary sample, and the gap between two samples is a symmetric object that random signs can measure. The second form of the bound uses only the data at hand, so \(\widehat{\mathfrak R}_S\) can be computed or estimated, as the widget does. To connect with Section 5 we need a way to bound it by counting.

lemma 6.10 — Massart's finite-class lemma

Let \(A\subset\mathbb R^n\) be a finite set of vectors with \(\|a\|_2\le r\) for all \(a\in A\). Then

$$\mathbb E_\sigma\Big[\max_{a\in A}\frac1n\sum_{i=1}^n\sigma_ia_i\Big]\le\frac{r\sqrt{2\ln|A|}}{n}.$$

For \(\lambda>0\), by Jensen's inequality, bounding a maximum of positive terms by their sum, and independence,

$$e^{\lambda\,\mathbb E\max_a\sum_i\sigma_ia_i}\le\mathbb E\,e^{\lambda\max_a\sum_i\sigma_ia_i}\le\sum_{a\in A}\prod_i\mathbb E\,e^{\lambda\sigma_ia_i}=\sum_{a\in A}\prod_i\cosh(\lambda a_i).$$

Since \(\cosh u\le e^{u^2/2}\) (compare the Taylor series), each product is at most \(e^{\lambda^2\|a\|^2/2}\le e^{\lambda^2r^2/2}\), so the right side is at most \(|A|e^{\lambda^2r^2/2}\).

Taking logarithms,

$$\mathbb E\max_a\sum_i\sigma_ia_i\le\frac{\ln|A|}\lambda+\frac{\lambda r^2}2.$$

Choosing \(\lambda=\sqrt{2\ln|A|}/r\) gives \(r\sqrt{2\ln|A|}\); divide by \(n\). \(\square\)

For a class \(\mathcal H\) of \(\pm1\)-valued classifiers, the vectors \((h(x_1),\dots,h(x_n))\) have length \(\sqrt n\) and there are \(|\mathcal H_S|\le\Pi_{\mathcal H}(n)\) of them, so Massart's lemma and Sauer–Shelah give

$$\widehat{\mathfrak R}_S(\mathcal H)\le\sqrt{\frac{2\ln\Pi_{\mathcal H}(n)}n}\le\sqrt{\frac{2d\ln(en/d)}n}.$$

Proof of Theorem 6.7(a). With labels \(y\in\{\pm1\}\), the 0–1 loss is \(g(x,y)=\frac{1-yh(x)}2\). The constant \(\tfrac12\) does not affect the supremum's expectation, and \(\sigma_iy_i\) has the same distribution as \(\sigma_i\), so \(\mathfrak R_n(\mathcal G)=\tfrac12\mathfrak R_n(\mathcal H)\). The first bound of Theorem 6.9 then reads \(R(h)\le\hat R_S(h)+\mathfrak R_n(\mathcal H)+\sqrt{\ln(1/\delta)/(2n)}\), and the display above bounds \(\mathfrak R_n(\mathcal H)\). \(\square\)

How tight is Massart's lemma? On penguins, we can compute the exact empirical Rademacher complexity of half-planes by taking the maximum over all the labellings counted in Section 5.

code — how well can half-planes fit noise?
draws = np.random.default_rng(2).choice([-1, 1], size=(2000, 342))      # 2,000 draws of random signs

# Half-planes on two features: the sup is a max over the labellings counted above
print('half-planes:  n    Monte Carlo R_S    Massart bound sqrt(2 ln|labellings| / n)')
for n in [20, 50, 100]:
    H = 2 * D[n] - 1                                                    # labellings as +-1
    sup = (draws[:, :n] @ H.T).max(axis=1) / n
    print(f'{n:16d}    {sup.mean():.4f} ± {sup.std() / np.sqrt(len(sup)):.4f}   {np.sqrt(2 * np.log(len(H)) / n):.4f}')
half-planes:  n    Monte Carlo R_S    Massart bound sqrt(2 ln|labellings| / n)
              20    0.5322 ± 0.0026   0.7697
              50    0.3568 ± 0.0017   0.5582
             100    0.2616 ± 0.0012   0.4281

Half-planes on 100 penguins agree with random signs at a rate of 0.26 above chance on average, and Massart's bound, 0.43, is about 1.6 times too large: the inequality \(\max\le\) sum in the proof is generous when many labellings are nearly the same. Both decay like \(1/\sqrt n\) (up to the logarithm). Bounds in learning theory are usually right about the rate and generous about the constant.

spot check 6.7

The empirical Rademacher complexity of a class containing a single function is , and of the class of all ±1 labellings of \(n\) distinct points it is .

Can the class choose its function after seeing the signs?
A single \(f\) gives \(\mathbb E\frac1n\sum\sigma_if(z_i)=0\). The class of all labellings picks \(h(x_i)=\sigma_i\), so the correlation is exactly 1 for every draw. The network of Section 1 is (nearly) the second case on its 2,000 training images.

7 — Linear classes, margins and Lipschitz losses

Rademacher complexity really earns its keep for real-valued functions, where VC dimension does not apply directly. The most important example: linear functions with bounded weights.

proposition 6.11 — norm-bounded linear functions

Let \(\mathcal F_B=\{x\mapsto w^\top x:\|w\|_2\le B\}\). For any sample \(x_1,\dots,x_n\),

$$\widehat{\mathfrak R}_S(\mathcal F_B)\le\frac Bn\sqrt{\sum_{i=1}^n\|x_i\|_2^2}\ \le\ \frac{BR}{\sqrt n}\qquad\text{if all }\|x_i\|_2\le R.$$

By Cauchy–Schwarz,

$$\sup_{\|w\|\le B}\frac1n w^\top\sum_i\sigma_ix_i=\frac Bn\big\|\sum_i\sigma_ix_i\big\|,$$

with equality at \(w\) parallel to \(\sum\sigma_ix_i\). By Jensen's inequality,

$$\mathbb E\Big\|\sum_i\sigma_ix_i\Big\|\le\sqrt{\mathbb E\Big\|\sum_i\sigma_ix_i\Big\|^2}=\sqrt{\sum_{i,j}\mathbb E[\sigma_i\sigma_j]\,x_i^\top x_j}=\sqrt{\sum_i\|x_i\|^2},$$

because \(\mathbb E[\sigma_i\sigma_j]\) is 1 when \(i=j\) and 0 otherwise. \(\square\)

The dimension of \(x\) does not appear. A linear function on a million features has the same complexity bound as one on three, provided the weights and inputs have the same norms. This is the theoretical reason that weight penalties (ridge, weight decay) control overfitting even when parameters outnumber examples. A check by Monte Carlo, where the supremum has the closed form from the proof:

code — Rademacher complexity of unit-norm linear functions on penguins
# Linear functions w.x with ||w|| <= 1 on four standardised penguin measurements
cols = ['bill_length_mm', 'bill_depth_mm', 'flipper_length_mm', 'body_mass_g']
Z = pen.dropna(subset=cols)[cols].to_numpy(float)
Z = (Z - Z.mean(0)) / Z.std(0)
Z = Z[np.random.default_rng(4).permutation(len(Z))]                 # shuffle so subsets mix species
print('||w|| <= 1:   n    Monte Carlo R_S    bound sqrt(sum ||x||^2) / n')
for n in [10, 30, 100, 342]:
    S = Z[:n]
    sup = np.linalg.norm(draws[:, :n] @ S, axis=1) / n                 # sup_w (1/n) sum s_i w.x_i, exactly
    print(f'{n:15d}    {sup.mean():.4f} ± {sup.std() / np.sqrt(len(sup)):.4f}   {np.sqrt((S**2).sum()) / n:.4f}')
||w|| <= 1:   n    Monte Carlo R_S    bound sqrt(sum ||x||^2) / n
             10    0.5846 ± 0.0062   0.6394
             30    0.3218 ± 0.0032   0.3511
            100    0.1787 ± 0.0019   0.2012
            342    0.0978 ± 0.0011   0.1081

The bound is within 13% at every \(n\) (the only loss is Jensen's inequality), and from 10 to 342 penguins both fall by a factor of about 6, close to \(\sqrt{34.2}\approx5.8\).

To use this for classification we need a loss that connects the real-valued score \(f(x)\) to mistakes. The 0–1 loss is not Lipschitz, but the ramp loss at margin \(\gamma>0\) is:

$$\phi_\gamma(m)=\begin{cases}1,&m\le0,\\1-m/\gamma,&0<m<\gamma,\\0,&m\ge\gamma,\end{cases}\qquad m=yf(x).$$

It charges a full mistake for a wrong sign, nothing for a correct prediction with margin at least \(\gamma\), and something in between for correct but unconfident predictions. Its empirical average \(\hat R_\gamma(f)\) is the empirical margin loss. The next lemma lets us pass the complexity through it.

lemma 6.12 — Talagrand's contraction lemma

If \(\phi:\mathbb R\to\mathbb R\) is \(L\)-Lipschitz, then

$$\widehat{\mathfrak R}_S(\phi\circ\mathcal F)\le L\,\widehat{\mathfrak R}_S(\mathcal F).$$

(Ledoux and Talagrand, 1991; Mohri et al., 2018, Lemma 5.7, prove the version used here.)

theorem 6.13 — the margin bound

Let \(\mathcal F\) be a class of real-valued functions and \(\gamma>0\). With probability at least \(1-\delta\), every \(f\in\mathcal F\) satisfies

$$P\big(Yf(X)\le0\big)\le\hat R_\gamma(f)+\frac2\gamma\,\widehat{\mathfrak R}_S(\mathcal F)+3\sqrt{\frac{\ln(2/\delta)}{2n}}.$$

For \(\mathcal F_B\) of Proposition 6.11, the middle term is at most

$$\frac{2B}{\gamma n}\sqrt{\sum\|x_i\|^2}.$$

Since \(\phi_\gamma(m)\ge\mathbb 1[m\le0]\), the error probability is at most \(\mathbb E\,\phi_\gamma(Yf(X))\). Apply the second bound of Theorem 6.9 to

$$\mathcal G=\{(x,y)\mapsto\phi_\gamma(yf(x)):f\in\mathcal F\},$$

whose values lie in \([0,1]\). The ramp is \((1/\gamma)\)-Lipschitz, so by Lemma 6.12

$$\widehat{\mathfrak R}_S(\mathcal G)\le\frac1\gamma\widehat{\mathfrak R}_S\big(\{(x,y)\mapsto yf(x)\}\big),$$

and multiplying the \(i\)-th term by \(y_i=\pm1\) does not change the distribution of \(\sigma_iy_i\), so this equals \(\frac1\gamma\widehat{\mathfrak R}_S(\mathcal F)\). \(\square\)

The bound trades two things off. A large margin \(\gamma\) makes the complexity term small but the margin loss large (more points are "unconfident"); a small margin does the opposite. And the only thing that matters about the classifier is the margin relative to the size of the weights. Maximising that ratio is exactly what the support vector machine of Lecture 7 does. Here is the bound for a unit-norm linear classifier on the breast-cancer data, at four margins chosen in advance (so \(\delta\) is split four ways).

code — a margin bound for a linear classifier
# Margin bound for a linear classifier on the breast-cancer data (standardised features plus a constant)
Ztr = np.column_stack([sc.transform(Xtr), np.ones(len(Xtr))])
Zte = np.column_stack([sc.transform(Xte), np.ones(len(Xte))])
t_tr, t_te = 2 * ytr - 1, 2 * yte - 1                                  # labels as +-1
w = LogisticRegression(C=0.1, fit_intercept=False, max_iter=5000).fit(Ztr, ytr).coef_[0]
w = w / np.linalg.norm(w)                                             # a unit-norm linear function
n = len(ytr)
Rs = np.sqrt((Ztr**2).sum()) / n                                      # Rademacher bound for ||w|| <= 1
margins = t_tr * (Ztr @ w)
gammas = [0.25, 0.5, 1, 2]
conf = 3 * np.sqrt(np.log(2 * len(gammas) / 0.05) / (2 * n))          # delta split over the four margins
print(f'R_S <= {Rs:.4f};  confidence term {conf:.4f};  test error of the classifier {np.mean(t_te * (Zte @ w) <= 0):.4f}')
print('gamma   ramp loss   2 R_S / gamma   bound on test error')
for g in gammas:
    ramp = np.clip(1 - margins / g, 0, 1).mean()                      # 1 below margin 0, 0 above gamma
    print(f'{g:5.2f}   {ramp:9.4f}   {2 * Rs / g:13.4f}   {ramp + 2 * Rs / g + conf:19.4f}')
R_S <= 0.2791;  confidence term 0.2395;  test error of the classifier 0.0409
gamma   ramp loss   2 R_S / gamma   bound on test error
 0.25      0.0224          2.2327                2.4946
 0.50      0.0349          1.1163                1.3908
 1.00      0.0719          0.5582                0.8696
 2.00      0.1687          0.2791                0.6874

The best of the four bounds guarantees a test error below 0.69; the actual test error is 0.04. This is honest and not useless (a bound above 1 would be), but it is loose, for two reasons visible in the table. The confidence term alone is 0.24 with 398 examples. And the complexity term uses the worst case over all unit-norm linear functions, while logistic regression found one particular, well-behaved one. Margin bounds earn their place less by their numerical value than by what they say: the dimension does not matter, the margin does.

spot check 6.8

In the margin bound for norm-bounded linear classifiers, what happens if we double every feature vector \(x_i\) and keep \(\|w\|\le B\) and \(\gamma\) fixed?

Look at where \(\|x_i\|\) appears in Proposition 6.11.
Rescaling the inputs by 2 is the same as rescaling \(B\) by 2. What the bound really measures is the margin in units of \(B\cdot\max\|x_i\|\), which rescaling cannot change.
causal — every bound here assumes the future looks like the past

Each theorem in this lecture assumes the test point comes from the same distribution \(\mathcal D\) as the training data. When the distribution shifts (a new hospital, a new year, a policy change) the bounds say nothing, and models that exploit spurious correlations fail. Causal reasoning gives one route to guarantees under shift. If the effect of the causes of \(Y\) on \(Y\) is the same in every environment, a predictor using only those causes keeps its accuracy when other parts of the system change. Invariant causal prediction (Peters, Bühlmann and Meinshausen, 2016) tests for such invariance across environments, and invariant risk minimisation (Arjovsky et al., 2019) tries to learn invariant features directly. On the theory side, domain-adaptation bounds (Ben-David et al., 2010) add to the source error a measure of how far apart the source and target distributions are.

8 — Modern puzzles: double descent, benign overfitting, PAC-Bayes

Return to the random-label experiment. The network memorised 2,000 random labels, so on those inputs its class has Rademacher complexity close to the maximum, and every bound that depends only on the class is vacuous for it. Yet the same network, trained on the true labels, generalises. The class cannot be the explanation; the explanation has to involve the data and the algorithm. Three lines of work fill some of the gap.

Double descent

Classical theory predicts the U-shaped test error of Lecture 1: error falls as the model grows, then rises as it starts to fit noise. Belkin, Hsu, Ma and Mandal (2019) observed that if you keep going, past the point where the model can fit the training data exactly, the test error comes back down, often below the bottom of the U. The simplest setting: fix a random first layer of \(p\) ReLU units and fit only the output layer by least squares. When \(p>n\) there are infinitely many exact fits, and we take the one with the smallest norm.

code — double descent with random ReLU features on MNIST
# Double descent: least squares on p random ReLU features of 1,000 MNIST digits
rng = np.random.default_rng(1)
idx = rng.choice(len(X_all), 1000, replace=False)
Xd, Yd = X_all[idx], np.eye(10)[y_all[idx]]                         # one-hot targets
_, _, (Xt_full, yt_full) = pickle.load(gzip.open('data/mnist.pkl.gz', 'rb'), encoding='latin1')
V = rng.standard_normal((784, 20000)) * np.sqrt(2 / 784)            # fixed random first layer
mu = Xd.mean(0)
relu_features = lambda A, p: np.maximum(0, (A - mu) @ V[:, :p])

print('    p    train MSE   test MSE   test error')
for p in [100, 500, 900, 1000, 1100, 2000, 5000, 20000]:
    F = relu_features(Xd, p)
    W = np.linalg.lstsq(F, Yd, rcond=None)[0]        # least squares; minimum-norm solution once p > n
    pred = relu_features(Xt_full, p) @ W
    print(f'{p:5d}   {np.mean(((F @ W - Yd)**2).sum(1)):9.4f}   {np.mean(((pred - np.eye(10)[yt_full])**2).sum(1)):8.3f}'
          f'   {np.mean(pred.argmax(1) != yt_full):10.4f}')
    p    train MSE   test MSE   test error
  100      0.3967      0.490       0.2210
  500      0.1231      0.555       0.1768
  900      0.0152      2.263       0.4251
 1000      0.0000   29099.078       0.8805
 1100      0.0000      2.078       0.4147
 2000      0.0000      0.432       0.1291
 5000      0.0000      0.276       0.0871
20000      0.0000      0.238       0.0810

Double descent

Test error of least squares on \(p\) random ReLU features of 1,000 MNIST digits (10,000 test digits), on a log scale in \(p\). The dashed line is the interpolation threshold \(p=n\). Add a ridge penalty \(\lambda n\|W\|^2\) and watch the peak. The faint curve is \(\lambda=0\) for reference.

With 100 features the test error is 22%. It falls to about 17% around 300–500 features, the bottom of the classical U, then climbs to 88% at \(p=1000=n\), where the model can fit all 1,000 training digits exactly and does so in the most violent way possible: the test mean squared error is 29,099. Beyond the threshold it falls again, to 8.1% at 20,000 features, far better than anything on the classical side. A ridge penalty of \(\lambda=0.001\) removes the peak entirely.

The peak has a simple cause. At \(p=n\) the feature matrix \(F\) is square, and its smallest singular value is nearly zero; the exact fit has to divide by it, so its weights are enormous and amplify every bit of noise in the labels. For \(p>n\), the minimum-norm fit can spread the work across many features, and its norm falls as \(p\) grows. By Proposition 6.11, small norm means small complexity: past the threshold, the minimum-norm solution is regularised implicitly. Gradient descent started from zero on least squares converges to exactly this minimum-norm solution, so the regularisation is a property of the algorithm, not the model class.

Benign overfitting

When can a model that fits noisy labels exactly still have test error close to optimal? For linear regression there is a sharp answer.

theorem 6.14 — benign overfitting in linear regression (informal)

Let \(y=x^\top\theta^*+\varepsilon\) with Gaussian \(x\) of covariance \(\Sigma\) (eigenvalues \(\lambda_1\ge\lambda_2\ge\cdots\)) and noise variance \(\sigma^2\), and let \(\hat\theta\) be the minimum-norm interpolator of \(n\) examples. Define the effective ranks

$$r_k(\Sigma)=\frac{\sum_{i>k}\lambda_i}{\lambda_{k+1}},\qquad R_k(\Sigma)=\frac{\big(\sum_{i>k}\lambda_i\big)^2}{\sum_{i>k}\lambda_i^2},$$

and let \(k^*\) be the smallest \(k\) with \(r_k(\Sigma)\ge bn\) for a suitable constant \(b\). Then, with high probability and up to constants, the excess risk is at most

$$\|\theta^*\|^2\|\Sigma\|\max\Big\{\sqrt{\frac{r_0(\Sigma)}n},\frac{r_0(\Sigma)}n\Big\}\ +\ \sigma^2\Big(\frac{k^*}n+\frac n{R_{k^*}(\Sigma)}\Big),$$

and the noise term \(\sigma^2(k^*/n+n/R_{k^*})\) is also a lower bound.

Overfitting is benign (the excess risk tends to 0) exactly when \(r_0(\Sigma)/n\), \(k^*/n\) and \(n/R_{k^*}(\Sigma)\) all tend to 0.

(Bartlett, Long, Lugosi and Tsigler, 2020.)

The noise term has a clear reading. The \(k^*\) directions of large variance behave like an ordinary regression with \(k^*\) parameters, costing \(k^*/n\). The remaining directions absorb the noise needed to interpolate. That is harmless only if there are many more of them than data points, each with small and similar variance, so that the noise is spread thin, which is what \(n/R_{k^*}\to0\) says. The fitted function is "spiky": a good smooth part plus tiny spikes at the training points that barely affect predictions elsewhere.

PAC-Bayes

The third line of work changes what is being bounded. Instead of one classifier, consider a distribution \(Q\) over classifiers, used by drawing a fresh \(h\sim Q\) for each prediction (the "Gibbs classifier"). Its risk is \(R(Q)=\mathbb E_{h\sim Q}R(h)\), and its training error is \(\hat R_S(Q)=\mathbb E_{h\sim Q}\hat R_S(h)\).

theorem 6.15 — the PAC-Bayes bound

Let \(P\) be a distribution over \(\mathcal H\) chosen before seeing the data (the "prior"), let the loss lie in \([0,1]\), and \(n\ge8\). With probability at least \(1-\delta\) over \(S\), simultaneously for every distribution \(Q\) over \(\mathcal H\),

$$\mathrm{kl}\big(\hat R_S(Q)\,\big\|\,R(Q)\big)\le\frac{\mathrm{KL}(Q\|P)+\ln(2\sqrt n/\delta)}n,$$

where

$$\mathrm{kl}(q\|p)=q\ln\frac qp+(1-q)\ln\frac{1-q}{1-p}$$

is the KL divergence between Bernoulli distributions.

Since \(\mathrm{kl}(q\|p)\ge2(q-p)^2\), this implies McAllester's form

$$R(Q)\le\hat R_S(Q)+\sqrt{\frac{\mathrm{KL}(Q\|P)+\ln(2\sqrt n/\delta)}{2n}}.$$

(McAllester, 1999; Seeger, 2002; Maurer, 2004.)

The complexity term is now \(\mathrm{KL}(Q\|P)\): how far the data moved us from the prior. A class can be huge, as long as the posterior we actually use is not far from a prior fixed in advance. The posterior \(Q\) may depend on the data in any way; only \(P\) must not. With \(\mathcal H\) finite, \(P\) uniform and \(Q\) a point mass, \(\mathrm{KL}(Q\|P)=\ln|\mathcal H|\) and we recover Theorem 6.2 up to a logarithm (Exercise 7). For the breast-cancer data: \(P=\mathcal N(0,s_0^2I)\) on the 31 weights of a linear classifier, with \(s_0\) from a grid of three values fixed in advance, and \(Q=\mathcal N(\hat w,\sigma^2I)\) centred at the logistic-regression weights.

code — a PAC-Bayes certificate for a linear classifier
from scipy.optimize import brentq

def kl_bern(q, p):
    return sum(a * np.log(a / b) for a, b in [(q, p), (1 - q, 1 - p)] if a > 0)
def kl_inverse(q, c):                         # largest p with kl(q || p) <= c
    return brentq(lambda p: kl_bern(q, p) - c, q + 1e-12, 1 - 1e-12) if kl_bern(q, 1 - 1e-12) > c else 1.0

w_hat = LogisticRegression(C=1, fit_intercept=False, max_iter=5000).fit(Ztr, ytr).coef_[0]
d = len(w_hat); rng = np.random.default_rng(3)
priors = [0.3, 1, 3]                          # prior N(0, s0^2 I), chosen before seeing data; delta split 3 ways
rows = []
for s0 in priors:
    for sig in [0.1, 0.2, 0.3, 0.5, 1]:          # posterior N(w_hat, sig^2 I): may depend on the data
        Wq = w_hat + sig * rng.standard_normal((4000, d))
        gibbs_tr = np.mean((Ztr @ Wq.T > 0) != ytr[:, None])
        gibbs_te = np.mean((Zte @ Wq.T > 0) != yte[:, None])
        KL = 0.5 * (w_hat @ w_hat / s0**2 + d * sig**2 / s0**2 - d + d * np.log(s0**2 / sig**2))
        c = (KL + np.log(2 * np.sqrt(n) / (0.05 / len(priors)))) / n
        rows.append((gibbs_tr + np.sqrt(c / 2), kl_inverse(gibbs_tr, c), s0, sig, KL, gibbs_tr, gibbs_te))
rows.sort(key=lambda r: r[1])
print('prior s0   posterior sigma     KL   train Gibbs   McAllester bound   kl bound   test Gibbs')
for b1, b2, s0, sig, KL, gtr, gte in rows[:4]:
    print(f'{s0:8.1f}   {sig:15.1f}   {KL:5.1f}   {gtr:11.4f}   {b1:16.4f}   {b2:8.4f}   {gte:10.4f}')
prior s0   posterior sigma     KL   train Gibbs   McAllester bound   kl bound   test Gibbs
     1.0               0.5    16.6        0.0368             0.2119     0.1416       0.0690
     1.0               0.3    30.0        0.0199             0.2377     0.1455       0.0561
     1.0               0.2    41.8        0.0127             0.2622     0.1573       0.0514
     1.0               0.1    62.8        0.0069             0.3046     0.1881       0.0470

With a posterior of width 0.5 around the fitted weights, the randomised classifier has training error 3.7% and the kl form of the bound certifies a true error below 14.2% with 95% confidence; its actual test error is 6.9%. That is far tighter than the margin bound (0.69) for essentially the same classifier. The posterior width trades off as the margin did: a narrow posterior has lower training error but a larger KL. (The training error of \(Q\) is estimated here from 4,000 draws; a fully rigorous certificate adds a small Monte Carlo correction, as in Langford and Caruana, 2002.) Dziugaite and Roy (2017) optimised exactly this kind of bound for neural networks on a binary version of MNIST and obtained the first non-vacuous bounds for deep networks, around 16–22% for networks with hundreds of thousands of parameters.

spot check 6.9

In the double-descent experiment, why is the test error worst at exactly \(p=n\)?

What happens to the smallest singular value of a random \(n\times p\) matrix as \(p\) passes \(n\)?
The smallest singular value of a random \(n\times p\) matrix is near zero when \(p\approx n\) and grows as \(p\) moves away. The fitted weights involve its reciprocal. Ridge adds \(\lambda\) to the squared singular values and removes the blow-up, as the widget shows.
spot check 6.10

In the PAC-Bayes bound, which of these must be chosen without looking at the training data?

Which quantity plays the role of the fixed hypothesis class?
The prior plays the role of \(\mathcal H\) fixed in advance; the bound then holds uniformly over all posteriors. Choosing among several priors after seeing the data is allowed only with a union bound, which is why the code splits \(\delta\) over three prior widths.
bayes — PAC-Bayes is a frequentist guarantee for Bayesian-style posteriors

The PAC-Bayes bound holds for every data-generating distribution, whether or not the prior is "true"; a bad prior only makes the bound loose. Which posterior minimises it? For the linear form \(\hat R_S(Q)+\mathrm{KL}(Q\|P)/\beta\), the answer (Catoni, 2007) is the Gibbs posterior

$$Q^*(h)\ \propto\ P(h)\,e^{-\beta\hat R_S(h)}.$$

When the loss is the negative log-likelihood and \(\beta=n\), \(e^{-n\hat R_S(h)}\) is the likelihood and \(Q^*\) is exactly the Bayesian posterior. With other losses it is a "generalised Bayesian" posterior, and \(\beta\) acts as a learning rate controlling how far the data may pull us from the prior (Bissiri, Holmes and Walker, 2016). So Bayesian inference is one way to minimise a frequentist generalisation bound.

quantum — quantum examples do not beat the VC dimension

Suppose each training example arrives as a quantum state, the superposition \(\sum_x\sqrt{\mathcal D(x)}\,|x,f(x)\rangle\), rather than as one sampled pair. A quantum learner can measure these states in clever ways, for instance sampling the Fourier spectrum of \(f\). Arunachalam and de Wolf (2018) proved that this does not help with sample size in general: the number of quantum examples needed to PAC learn a class of VC dimension \(d\) is \(\Theta\big((d+\ln(1/\delta))/\varepsilon\big)\) in the realisable case and \(\Theta\big((d+\ln(1/\delta))/\varepsilon^2\big)\) in the agnostic case, the same as Theorem 6.7 up to constants. Quantum advantages appear for special distributions (Bshouty and Jackson, 1999, learned DNF formulas from quantum examples under the uniform distribution) or in computation time rather than samples. In the other direction, Caro et al. (2022) proved generalisation bounds for quantum machine learning models that grow with the number of trainable gates \(T\) roughly as \(\sqrt{T\log T/n}\), the quantum analogue of counting parameters.

big picture — what learning theory does today

Practitioners rarely compute a VC bound. The guarantees they rely on are the simplest ones in this lecture: held-out test sets with Hoeffding or binomial intervals, and their descendant, conformal prediction, which gives distribution-free prediction intervals with exact coverage. The union bound is a live issue there. A benchmark test set reused by thousands of papers is a selection among many classifiers, exactly the widget of Section 1; Recht et al. (2019) rebuilt ImageNet's test set from scratch and found that every model lost 11–14 points of accuracy, although the ranking of models was largely preserved. On the theoretical side, deep learning broke the classical story and the field is rebuilding it: implicit regularisation of gradient descent, norm- and margin-based bounds for networks (Bartlett, Foster and Telgarsky, 2017), neural tangent kernels (Lecture 7), benign overfitting, and PAC-Bayes and compression bounds, which now give non-vacuous guarantees even for large language models (Lotfi et al., 2024). Reading a modern theory paper, you will meet the tools of this lecture on almost every page: a concentration inequality, a union bound or a symmetrisation, a complexity measure, and a trade-off between fit and complexity.

9 — Summary, exercises, projects, reading

summary

Next: Lecture 7 turns the margin into an algorithm, the support vector machine, and uses kernels to make linear methods nonlinear without paying for the dimension.

exercises 6
  1. Show that intervals \([a,b]\) on the real line have VC dimension 2, and that unions of at most \(k\) intervals have VC dimension \(2k\).

    Two points are shattered: an interval can contain neither, either or both. Three points \(x_1<x_2<x_3\) cannot be labelled 1, 0, 1, since an interval containing \(x_1\) and \(x_3\) contains \(x_2\). For \(k\) intervals, \(2k\) points are shattered: any labelling has at most \(k\) runs of 1s among \(2k\) points, each covered by one interval. Among \(2k+1\) points, the labelling 1, 0, 1, 0, …, 1 has \(k+1\) runs of 1s separated by 0s, which need \(k+1\) intervals.

  2. Show that axis-aligned rectangles in the plane have VC dimension 4.

    The four points \((\pm1,0),(0,\pm1)\) are shattered: for any subset, the bounding box of that subset contains no other of the four points. For five points, take a leftmost, a rightmost, a highest and a lowest point (at most four points); some fifth point is none of these. Label it 0 and the rest 1: any rectangle containing the four extreme points contains their bounding box, which contains every point.

  3. Show that the one-parameter class \(\{x\mapsto\mathbb 1[\sin(\omega x)>0]:\omega>0\}\) has infinite VC dimension. (Hint: use the points \(x_i=2^{-i}\), \(i=1,\dots,n\), and for a labelling \(y\in\{0,1\}^n\) take \(\omega=\pi\big(1+\sum_i(1-y_i)2^i\big)\).)

    With this \(\omega\), \(\omega x_j/\pi=2^{-j}+\sum_i(1-y_i)2^{i-j}\). Terms with \(i>j\) are even integers and do not affect the sign of \(\sin\). The term \(i=j\) contributes \(1-y_j\). Terms with \(i<j\), plus \(2^{-j}\), sum to a number in \((0,1)\). So \(\omega x_j/\pi\) lies in \((0,1)\) mod 2 when \(y_j=1\) (sine positive) and in \((1,2)\) mod 2 when \(y_j=0\) (sine negative). Every labelling is realised, for every \(n\). Number of parameters is not complexity.

  4. How many test examples does Hoeffding's inequality need to pin a fixed classifier's error to within ±0.02 with probability 0.99? If the error rate is around 5%, why might far fewer suffice in practice?

    \(m\ge\ln(200)/(2\times0.0004)=5.298/0.0008\approx6{,}623\). Hoeffding ignores the variance; at \(p\approx0.05\) the standard deviation of a single indicator is \(\sqrt{0.05\times0.95}\approx0.22\), not the worst case 0.5, so the normal approximation \(2.58\times0.22/\sqrt m\le0.02\) needs only about 800, and exact binomial intervals behave similarly.

  5. Let \(h\in\{\pm1\}^n\) be fixed. Show that \(\widehat{\mathfrak R}_S(\{h,-h\})=\frac1n\mathbb E\big|\sum_i\sigma_i\big|\), and compute it for \(n=4\).

    \(\max\big(\sum\sigma_ih_i,-\sum\sigma_ih_i\big)=|\sum\sigma_ih_i|\), and \(\sigma_ih_i\) are again independent random signs. For \(n=4\) the sum is \(\pm4\) with probability \(1/16\) each, \(\pm2\) with probability \(4/16\) each, and 0 with probability \(6/16\), so \(\mathbb E|\sum\sigma_i|=(2\cdot4+8\cdot2)/16=1.5\) and the complexity is \(0.375\). For large \(n\) it is about \(\sqrt{2/(\pi n)}\).

  6. Show that for a constant \(c\), a fixed function \(g\) and the convex hull \(\mathrm{conv}\,\mathcal F\): \(\widehat{\mathfrak R}_S(c\mathcal F)=|c|\,\widehat{\mathfrak R}_S(\mathcal F)\), \(\widehat{\mathfrak R}_S(\mathcal F+g)=\widehat{\mathfrak R}_S(\mathcal F)\), and \(\widehat{\mathfrak R}_S(\mathrm{conv}\,\mathcal F)=\widehat{\mathfrak R}_S(\mathcal F)\). Why does the last fact matter for boosting (Lecture 8)?

    Scaling: pull \(c\) out of the supremum, using that \(-\sigma\) has the same law as \(\sigma\) when \(c<0\). Shift: \(\mathbb E\sum\sigma_ig(z_i)=0\). Convex hull: a linear function of \(f\) attains its supremum over a convex combination at one of the combined functions, so \(\sup_{\mathrm{conv}\mathcal F}=\sup_{\mathcal F}\) for every \(\sigma\). Boosting outputs a weighted vote of many weak learners, a point in the convex hull of their class (after normalising the weights), so its complexity is no larger than that of a single weak learner: this is how Schapire et al. (1998) explained why boosting keeps generalising as more rounds are added.

  7. Recover Theorem 6.2 (up to a logarithmic term) from the PAC-Bayes bound by taking \(P\) uniform on a finite \(\mathcal H\) and \(Q\) a point mass at \(h\).

    \(\mathrm{KL}(Q\|P)=\sum_{h'}Q(h')\ln\frac{Q(h')}{P(h')}=1\cdot\ln\frac1{1/|\mathcal H|}=\ln|\mathcal H|\), and the Gibbs classifier is just \(h\). McAllester's form gives \(R(h)\le\hat R_S(h)+\sqrt{(\ln|\mathcal H|+\ln(2\sqrt n/\delta))/(2n)}\) for all \(h\), which is Theorem 6.2's one-sided bound with an extra \(\ln(\sqrt n)\) inside the root.

  8. Show that for \(Q=\mathcal N(\mu,\sigma^2I_d)\) and \(P=\mathcal N(0,s^2I_d)\), $$\mathrm{KL}(Q\|P)=\frac12\Big(\frac{\|\mu\|^2}{s^2}+\frac{d\sigma^2}{s^2}-d+d\ln\frac{s^2}{\sigma^2}\Big).$$

    Both are products over coordinates, so the KL is a sum of \(d\) one-dimensional terms. For one coordinate, \(\mathbb E_Q\big[\ln q(w)-\ln p(w)\big]=\mathbb E_Q\big[-\ln\sigma-\frac{(w-\mu_j)^2}{2\sigma^2}+\ln s+\frac{w^2}{2s^2}\big]=\ln\frac s\sigma-\frac12+\frac{\sigma^2+\mu_j^2}{2s^2}\). Summing over \(j\) gives the formula; this is the KL used in the PAC-Bayes code.

  9. In the double-descent widget with \(\lambda=0\), read off the test error at \(p=900\), 1000 and 1100. Using the singular value decomposition \(F=U\,\mathrm{diag}(s)\,V^\top\), explain why the weights blow up at \(p=n\), and why a ridge penalty prevents it.

    About 0.43, 0.88 and 0.41. The minimum-norm least-squares solution is \(W=V\,\mathrm{diag}(1/s_j)\,U^\top Y\), summing over the nonzero singular values. When \(F\) is square and random, its smallest singular values are close to 0, and \(1/s_j\) multiplies whatever part of \(Y\) lies in those directions, including noise. Ridge replaces \(1/s_j\) by \(s_j/(s_j^2+\lambda n)\), which is at most \(1/(2\sqrt{\lambda n})\) however small \(s_j\) is.

  10. In the no-free-lunch proof, verify the last step: if \(Z\in[0,1]\) and \(\mathbb EZ\ge\tfrac14\), then \(P(Z\ge\tfrac18)\ge\tfrac17\).

    Let \(q=P(Z\ge\tfrac18)\). Then \(\mathbb EZ\le\tfrac18(1-q)+1\cdot q=\tfrac18+\tfrac78q\). If \(q<\tfrac17\) this is less than \(\tfrac18+\tfrac18=\tfrac14\), a contradiction.

  11. Thresholds in either direction on \(n\) distinct points of the line produce \(2n\) labellings. Compute Massart's bound on their empirical Rademacher complexity for \(n=100\), and compare with the widget.

    \(\sqrt{2\ln200/100}=\sqrt{10.597/100}\approx0.326\). The widget's estimate at \(n=100\) is about 0.19, so Massart is roughly 1.7 times too large here: thresholds produce many nearly identical labellings, and the bound counts each as a separate chance to fit the noise.

student projects

Each project uses this lecture's methods and public data, and has a clear result.

1. Does the bound track the gap?

question
Across many real datasets, does estimated Rademacher complexity (or a PAC-Bayes bound) predict which models will have a large generalisation gap?
data
Twenty or so classification datasets from the OpenML-CC18 benchmark suite (Bischl et al., 2021).
method
For several model classes (stumps, depth-limited trees, norm-constrained linear models, small networks), estimate \(\widehat{\mathfrak R}_S\) by Monte Carlo as in this lecture and compute PAC-Bayes bounds; measure the actual gap on held-out data; rank-correlate the two across datasets and models, following the methodology of Jiang et al. (2020), "Fantastic generalization measures and where to find them".
outcome
An answer, on tabular data, to which complexity measures carry real information about generalisation, an open empirical question for most of them.

2. When is double descent visible on small data?

question
On small tabular datasets, when does the double-descent peak appear, how large is it, and what removes it (ridge, early stopping, label noise, feature scaling)?
data
UCI and OpenML regression and classification datasets with a few hundred to a few thousand rows.
method
Random-feature and kernel "ridgeless" regression as in this lecture's code, sweeping \(p/n\); add controlled label noise; record the peak height and the test error at large \(p\) against the best classical model.
outcome
A practical map of when over-parameterised interpolation helps on tabular data, where gradient-boosted trees (Lecture 8) usually win.

3. How much do leaderboards overfit?

question
When thousands of teams evaluate on the same public test set, how much does selection inflate the scores, and does the union-bound picture of Section 1 predict the size of the effect?
data
Public and private leaderboard scores from completed Kaggle competitions (Kaggle Meta Kaggle dataset), extending Roelofs et al. (2019).
method
For each competition, compare public and private scores of the top submissions; model the expected inflation from the number of submissions and the public test-set size using Hoeffding and binomial bounds; test whether the inflation follows the \(\sqrt{\ln M/n}\) scaling.
outcome
A quantitative account of adaptive overfitting in recent competitions, with practical advice on test-set size for benchmark designers.

4. Certified error rates for public-sector models

question
Can simple, transparent models used on public data come with non-vacuous PAC-Bayes or test-set certificates of their error, overall and for subgroups?
data
NYC Open Data (for example, 311 complaint resolution or restaurant inspection grades) or the ProPublica COMPAS data.
method
Fit logistic regression and small trees; compute Hoeffding, Clopper–Pearson and PAC-Bayes bounds overall and by borough, race or age group, with \(\delta\) split across groups by a union bound.
outcome
A worked example of reporting guaranteed error rates by subgroup, and a measurement of how much the union bound over subgroups costs when the groups are small.

Reading and sources

Data. MNIST: Y. LeCun, C. Cortes, C. J. C. Burges, The MNIST database of handwritten digits (1998), in the copy distributed with M. Nielsen, Neural Networks and Deep Learning (github.com/mnielsen/neural-networks-and-deep-learning). CIFAR-10: A. Krizhevsky, Learning Multiple Layers of Features from Tiny Images, technical report, University of Toronto (2009), Parquet copy uoft-cs/cifar10 (Hugging Face Hub). Breast cancer: W. N. Street, W. H. Wolberg, O. L. Mangasarian, "Nuclear feature extraction for breast tumor diagnosis", IS&T/SPIE Symposium on Electronic Imaging 1905, 861–870 (1993); UCI Machine Learning Repository, via scikit-learn. Penguins: A. M. Horst, A. P. Hill, K. B. Gorman, palmerpenguins (2020), CC0; K. B. Gorman, T. D. Williams, W. R. Fraser, "Ecological sexual dimorphism and environmental variability within a community of Antarctic penguins (genus Pygoscelis)", PLoS ONE 9(3), e90081 (2014).

every number in the text and widgets is computed in verify_L06.py; code-box outputs are pasted from actual runs