Every practical technique in this track — validation, regularisation, simpler models — rests on an implicit promise: that performance on a sample predicts performance on the population. Statistical learning theory makes this promise precise. It tells us how many examples are needed, how model complexity affects generalisation, and why learning is possible at all. This is the most mathematical lecture of the track; take it slowly.
The PAC framework#
Leslie Valiant (1984) introduced Probably Approximately Correct (PAC) learning. Let $R(h)$ be the true error of hypothesis $h$ and $\hat{R}(h)$ its training error on $n$ i.i.d. examples. A hypothesis class $\mathcal{H}$ is PAC-learnable if there is an algorithm that, for any $\epsilon, \delta \in (0, 1)$ and any data distribution, given
examples, outputs $h$ with
"Approximately correct" = error at most $\epsilon$; "probably" = with confidence $1 - \delta$. The function $n(\epsilon, \delta)$ is the sample complexity.
Finite hypothesis classes#
Realisable case (some $h \in \mathcal{H}$ has zero error). Any consistent hypothesis (zero training error) has true error at most $\epsilon$ with probability $1 - \delta$ if
Proof sketch. A "bad" hypothesis with error $> \epsilon$ survives $n$ independent examples with probability $< (1 - \epsilon)^n \le e^{-\epsilon n}$. By the union bound over at most $|\mathcal{H}|$ bad hypotheses, the probability that any survives is $\le |\mathcal{H}|e^{-\epsilon n}$. Set this $\le \delta$ and solve for $n$. $\blacksquare$
Agnostic case (no perfect hypothesis). Using Hoeffding's inequality and a union bound, with probability $1 - \delta$, for all $h \in \mathcal{H}$ simultaneously:
This is the first generalisation bound: true error ≤ training error + a complexity term that grows with $\ln|\mathcal{H}|$ and shrinks as $1/\sqrt{n}$. It formalises the bias–variance trade-off: a richer class lowers training error but raises the complexity penalty.
Infinite classes: the VC dimension#
Linear classifiers form an infinite class, so $\ln|\mathcal{H}|$ is useless. Vapnik and Chervonenkis measured capacity differently.
A set of points is shattered by $\mathcal{H}$ if, for every possible labelling of those points, some $h \in \mathcal{H}$ realises it. The VC dimension $d_{VC}(\mathcal{H})$ is the size of the largest set that can be shattered.
| Hypothesis class | VC dimension |
|---|---|
| Thresholds on the real line | 1 |
| Intervals on the real line | 2 |
| Linear classifiers (half-planes) in $\mathbb{R}^2$ | 3 |
| Linear classifiers in $\mathbb{R}^d$ | $d + 1$ |
| Axis-aligned rectangles in $\mathbb{R}^2$ | 4 |
| $\sin(\omega x)$ thresholds | $\infty$ (despite one parameter!) |
The last row is a warning: the number of parameters is not the same as capacity.
The VC bound#
With probability $1 - \delta$, for all $h \in \mathcal{H}$:
The fundamental theorem of statistical learning states that a class is PAC-learnable if and only if its VC dimension is finite, with sample complexity $\Theta\left(\frac{d_{VC} + \ln(1/\delta)}{\epsilon^2}\right)$ in the agnostic case. A rough rule of thumb from this theory: you need a number of examples that is a multiple of the VC dimension.
Structural Risk Minimisation#
Vapnik's SRM principle chooses among nested classes $\mathcal{H}_1 \subset \mathcal{H}_2 \subset \dots$ by minimising the bound (training error + complexity term), not the training error alone. Regularisation, SVM margin maximisation (large margins imply lower effective capacity) and model selection by penalised criteria are practical descendants of SRM.
import numpy as np
# How the complexity term shrinks with n for a finite class (|H| = 1e6, delta = 0.05)
H, delta = 1e6, 0.05
for n in [100, 1_000, 10_000, 100_000]:
gap = np.sqrt((np.log(H) + np.log(2 / delta)) / (2 * n))
print(f"n={n:>7}: training error + {gap:.3f} bounds the true error")Other complexity measures#
- Rademacher complexity — how well $\mathcal{H}$ can fit random ±1 labels on the actual data; data-dependent and often tighter.
- Margin bounds — generalisation depends on the margin relative to the data's scale, not dimension (explains SVMs in high dimensions).
- PAC-Bayes bounds — depend on the KL divergence between a posterior over hypotheses and a prior; among the few bounds that give non-vacuous numbers for some deep networks.
- Algorithmic stability — algorithms whose output changes little when one example changes generalise well.
The deep learning puzzle#
Modern networks have far more parameters than training examples and can fit randomly labelled data perfectly (Zhang et al., 2017) — so their capacity by VC or Rademacher standards is enormous, and classical bounds are vacuous (they bound the error by more than 100%). Yet the same networks generalise well on real labels. Explanations under active research include the implicit bias of SGD towards simple solutions, flat minima, norm-based and compression-based bounds, and the structure of natural data. Classical theory is not wrong — its bounds are valid — but they are too loose to explain deep learning's success.