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
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.
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.
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.
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.
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.
In the widget, why does the lowest training error fall as \(M\) grows, even though every classifier has true error 0.5?
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.
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.
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.
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.
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.)
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.
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.
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.
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\).
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).
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.
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.)
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.
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).
What does the no-free-lunch theorem imply in practice?
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.
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.
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 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
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.
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 .
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.
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.
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.
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.
A class has VC dimension 2. What is the Sauer–Shelah bound on the number of labellings it can produce on 10 points?
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.
(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.
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.
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.
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.
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.
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.
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.)
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.
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.
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.
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 .
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.
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:
# 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.
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.)
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).
# 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.
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?
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.
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.
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.
# 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
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.
When can a model that fits noisy labels exactly still have test error close to optimal? For linear regression there is a sharp answer.
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.
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)\).
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.
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.
In the double-descent experiment, why is the test error worst at exactly \(p=n\)?
In the PAC-Bayes bound, which of these must be chosen without looking at the training data?
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.
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.
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.
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.
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.
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.
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.
\(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.
\(\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)}\).
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.
\(\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.
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.
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.
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.
\(\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.
Each project uses this lecture's methods and public data, and has a clear result.
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