Learning theory: Why does it work on data it has never seen?

A student who memorizes last year's exam answers scores full marks on that exam and fails this year's. The same happens with machines: what matters is not the error on the training data but on new data. That ability is called generalization, and it is the property that distinguishes learning from memorizing.

Empirical risk and true risk

Suppose the examples $(x, y)$ come from an unknown distribution $𝒟$ . For a model (or hypothesis) $h$ chosen from a class $ℋ$ and a loss function $ℓ$ , there are two errors:

R (h) = 𝔼_{(x, y) \sim 𝒟} [ℓ (h (x), y)] and {\hat{R}}_{n} (h) = \frac{1}{n} \sum_{i = 1}^{n} ℓ (h (x_{i}), y_{i}) .

The true risk $R$ is what we care about, but we cannot compute it. The empirical risk ${\hat{R}}_{n}$ is what we measure on the data. Training is almost always empirical risk minimization, a principle Vladimir Vapnik placed at the centre of the theory. The question is when a small ${\hat{R}}_{n}$ guarantees a small $R$ .

Fitting a polynomial of degree

d

n

noisy points (the dashed curve is the true function). Right: the error on the training data always goes down as the degree rises, but the error on new data traces a U. With a low degree the model is too rigid (underfitting); with a high degree it chases the noise (overfitting). Press “New data” to see how much the high-degree fit changes with another sample: that is variance.

The figure illustrates the bias–variance decomposition (Geman, Bienenstock and Doursat, 1992). For squared loss, the expected error at a new point splits into three terms:

𝔼 [(y - \hat{h} (x))^{2}] = \underset{{bias}^{2}}{\underset{⏟}{(𝔼 [\hat{h} (x)] - f (x))^{2}}} + \underset{variance}{\underset{⏟}{Var (\hat{h} (x))}} + \underset{noise}{\underset{⏟}{σ^{2}}} .

Simple models have high bias and low variance; complex ones, the reverse. Classical wisdom says to look for the sweet spot in between.

PAC learning

In 1984 Leslie Valiant gave a formal definition of “learning” with a deliberately modest name: probably approximately correct (PAC). We do not demand always being right; it is enough that, with high probability over the sample, the model has small error.

Definition (PAC learning, Valiant 1984)

A class $ℋ$ is learnable if there is an algorithm and a function $n (ε, δ)$ such that, for every distribution $𝒟$ and all $ε, δ \in (0, 1)$ , with $n \geq n (ε, δ)$ examples the algorithm returns $h$ with

P (R (h) \leq min_{h^{'} \in ℋ} R (h^{'}) + ε) \geq 1 - δ .

For a finite class, the answer comes from combining two classic tools.

Theorem (generalization bound for finite classes)

If $ℋ$ is finite and the loss takes values in $[0, 1]$ , then with probability at least $1 - δ$ over the sample, for every $h \in ℋ$ simultaneously,

R (h) \leq {\hat{R}}_{n} (h) + \sqrt{\frac{\ln | ℋ | + \ln (2 / δ)}{2 n}} .

Proof

For a fixed $h$ , ${\hat{R}}_{n} (h)$ is the mean of $n$ independent variables in $[0, 1]$ with expectation $R (h)$ . Hoeffding's inequality (1963) says that $P (| {\hat{R}}_{n} (h) - R (h) | > ε) \leq 2 e^{- 2 n ε^{2}}$ : the law of large numbers with an exponential rate. By the union bound, the probability that some of the $| ℋ |$ hypotheses deviates is at most $2 | ℋ | e^{- 2 n ε^{2}}$ . Setting it equal to $δ$ and solving for $ε$ gives the bound.

The bound captures the intuition of Occam's razor: the price of choosing among many hypotheses grows with $\ln | ℋ |$ , roughly the number of bits needed to describe the chosen hypothesis. More data compensates for it as $1 / \sqrt{n}$ .

The VC dimension

The interesting classes are infinite: there are infinitely many lines in the plane. In 1971 Vladimir Vapnik and Alexey Chervonenkis found the right measure of their capacity. A class is said to shatter a set of points if it can produce every possible labelling of them.

Definition (Vapnik–Chervonenkis dimension)

The VC dimension of $ℋ$ is the largest $d$ such that some set of $d$ points is shattered by $ℋ$ . If sets of every size can be shattered, it is infinite.

Can lines shatter these points? Each thumbnail is one of the

2^{n}

possible labellings, with the line that separates it (if one exists). Drag the points. With 3 points in general position you get all 8, but with 4 you never get all 16: there is always an XOR-like labelling that is impossible. The VC dimension of lines in the plane is 3 (and that of hyperplanes in

ℝ^{k}

k + 1

Theorem (fundamental theorem of PAC learning)

For binary classification, $ℋ$ is PAC-learnable if and only if its VC dimension $d$ is finite. In that case the number of examples needed is

n (ε, δ) = Θ (\frac{d + \ln (1 / δ)}{ε^{2}}),

and empirical risk minimization is an algorithm that achieves it.

This result, built by Vapnik and Chervonenkis (1971) and Blumer, Ehrenfeucht, Haussler and Warmuth (1989), is one of the peaks of the theory: it reduces the question “can this be learned?” to a combinatorial number. In the 1990s it inspired support vector machines (Boser, Guyon and Vapnik, 1992; Cortes and Vapnik, 1995), which maximize the margin to control capacity and were the star method before deep learning.

No free lunch

Theorem (no free lunch; Wolpert, 1996)

Averaged over all possible target functions, every learning algorithm has the same mean error outside the training sample. No method beats another on every problem.

Generalizing requires assuming something about the world, an inductive bias. Convolutions assume that what matters in an image does not depend on its position. Attention assumes that any word can depend on any other, with a weight computed from the content. Choosing the architecture is, to a large extent, choosing the right assumptions.

The mystery of deep networks

In 2017 Chiyuan Zhang and his colleagues ran a devastating experiment: they trained standard vision networks on images whose labels had been randomly shuffled. The networks memorized them perfectly. Their capacity is therefore enough to fit anything, so VC-based bounds are useless for them: they predict errors above 100%. And yet, with the true labels, those same networks generalize beautifully.

Belkin and his colleagues (2019) also documented double descent: if model size is increased beyond the point where it fits the data perfectly, the test error, which had got worse following the classic U-shaped curve, goes down again. LLMs live far to the right of that curve.

Open question

There is still no complete theory of why overparameterized networks generalize. The candidate explanations are the implicit regularization of stochastic gradient descent (which tends towards “simple” or small-norm solutions), a preference for flat minima, PAC-Bayes bounds (which do give non-trivial guarantees in some cases) and the structure of real-world data itself.

With the right data, architecture and optimization algorithm, generalization arrives. For language, the architecture that changed everything appeared in 2017.

References

V. N. Vapnik and A. Y. Chervonenkis (1971). “On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities”. Theory of Probability and Its Applications, 16(2).
W. Hoeffding (1963). “Probability Inequalities for Sums of Bounded Random Variables”. JASA, 58(301).
L. G. Valiant (1984). “A Theory of the Learnable”. Communications of the ACM, 27(11).
A. Blumer, A. Ehrenfeucht, D. Haussler and M. K. Warmuth (1989). “Learnability and the Vapnik-Chervonenkis Dimension”. Journal of the ACM, 36(4).
S. Geman, E. Bienenstock and R. Doursat (1992). “Neural Networks and the Bias/Variance Dilemma”. Neural Computation, 4(1).
D. H. Wolpert (1996). “The Lack of A Priori Distinctions Between Learning Algorithms”. Neural Computation, 8(7).
C. Zhang, S. Bengio, M. Hardt, B. Recht and O. Vinyals (2017). “Understanding Deep Learning Requires Rethinking Generalization”. ICLR.
M. Belkin, D. Hsu, S. Ma and S. Mandal (2019). “Reconciling modern machine-learning practice and the classical bias-variance trade-off”. PNAS, 116(32).
S. Shalev-Shwartz and S. Ben-David (2014). Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press.

§Empirical risk and true risk

§PAC learning

§The VC dimension

§No free lunch

§The mystery of deep networks