Statistical Learning Theory Primer

Classical learning theory predicts that a model with more parameters than training examples should overfit catastrophically. Modern LLMs have 100x more parameters than tokens-per-sample and generalise spectacularly well. The gap between classical theory and observed practice is one of the most interesting open problems in ML. Knowing where the classical framework still applies and where it has broken down is the difference between explaining model behaviour and being mystified by it.

Bias-variance decomposition

For squared-error loss, the expected error of a learning algorithm on a fresh test point decomposes as:

E[(y - f_hat(x))^2] = (bias(x))^2 + variance(x) + noise(x)

• Bias. How wrong the average prediction is across different training sets drawn from the same distribution. High for under-fit models.
• Variance. How much the prediction wobbles as the training set changes. High for over-fit models.
• Noise. Irreducible. The Bayes-optimal floor.

The classical picture: model complexity trades bias for variance. Too simple, high bias. Too complex, high variance. Optimal complexity sits where the curves cross. Cross-validation finds it.

This picture is real for linear models, shallow trees, kernel methods. It famously breaks for over-parameterised deep nets.

PAC-learning intuition

Probably Approximately Correct (Valiant, 1984). A learning algorithm PAC-learns a concept class if, with probability >= 1 - delta, it returns a hypothesis with error <= epsilon, using a number of samples polynomial in 1/epsilon, 1/delta, and the complexity of the class.

The headline result: sample complexity grows with the capacity of the hypothesis class. Simple classes (linear separators) need few samples; complex classes need many. The framework gives concrete bounds of the form:

sample_complexity = O((capacity + log(1/delta)) / epsilon)

For classical models this matches reality. For deep nets the predicted sample complexity is astronomical compared to what works in practice.

VC dimension

Vapnik-Chervonenkis dimension is the size of the largest set of points the hypothesis class can shatter (label arbitrarily). Higher VC dimension means more capacity, looser generalisation bounds.

A simple bound (Vapnik, 1971):

test_error <= train_error + O(sqrt(VC / n))

where n is the number of training samples. This bound is vacuous for deep nets. A modern transformer has VC dimension on the order of its parameter count - billions. With n in the trillions, the bound sqrt(billions / trillions) is 0.03, not useful. With smaller datasets the bound exceeds 1 (meaningless). And yet models trained on those smaller datasets generalise just fine.

The Zhang et al (2017) paper "Understanding deep learning requires rethinking generalization" hammered this home: a standard CNN can memorise random labels on CIFAR-10 perfectly. So its effective capacity is genuinely massive. But trained on real labels, the same architecture generalises. Capacity-based bounds cannot explain this because they apply uniformly across all label assignments.