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.

Why deep nets break classical generalisation bounds

Several effects, none individually sufficient:

• Implicit regularisation of SGD. Even with no explicit regulariser, SGD finds solutions in a specific subset of all loss-zero solutions - typically the "minimum-norm" or "flattest" interpolator. The choice of optimiser matters as much as the choice of architecture for generalisation.
• Architectural inductive bias. A CNN's translation equivariance, a transformer's attention pattern - these constrain the function class without showing up in parameter count.
• Data structure. Real data lies on low-dimensional manifolds inside high-dimensional input space. Effective dimension is far smaller than nominal dimension.
• Over-parameterisation as regularisation. Counterintuitively, more parameters often help generalisation past a threshold. The double descent phenomenon makes this concrete.

Double descent

Nakkiran et al (2019). Plot test error against model size (or training time, or dataset size). Classical theory predicts a U-shape: error drops then rises with capacity. What you actually see in deep nets:

test error
   |
   |   classical
   |     /\
   |    /  \
   |   /    \____            new descent
   |  /         \___________/
   |_/_____________________________ model size
                interpolation
                threshold

Up to the interpolation threshold (where the model can exactly fit the training set), classical U-shape holds. Past that point, error often decreases again with model size. The interpolation threshold itself is the worst place to be.

Implications:

• "More parameters than data points" is not automatically bad. Often it is the right side of the second descent.
• Tuning by validation often picks models past the classical optimum.
• The behaviour is robust across vision and language; it is not an artefact of any one dataset.

The implicit regularisation framing

Even without explicit regularisation, SGD does not converge to an arbitrary zero-loss solution. Several lines of work characterise the bias:

• Linear case. SGD on under-determined linear regression with squared loss converges to the minimum-L2-norm solution. This is implicit ridge regression.
• Logistic loss. Gradient descent on separable data converges (in direction) to the max-margin classifier. Same direction as a hard-margin SVM.
• Deep networks. Less clean theory, but SGD with small batch / large LR systematically prefers "flatter" minima, which empirically generalise better.

The practical takeaway: SGD's noise is doing real work. Replacing it with full-batch optimisation, especially in pretraining, often hurts.

What scaling laws are saying about generalisation

The Kaplan et al (2020) and Hoffmann et al (2022, "Chinchilla") scaling laws show that test loss follows clean power laws in model size N, dataset size D, and compute C:

L(N, D) ~ A / N^alpha + B / D^beta + L_inf

with alpha and beta empirically near 0.34 and 0.28 for language modelling. Several things stand out:

1. Generalisation gap is tiny at scale. For frontier LLMs trained on web-scale data, train and validation loss are within fractions of a percent. The classical "overfit by memorising training data" failure mode is absent because data is effectively unbounded.
2. Compute-optimal allocation. Chinchilla showed that for a fixed compute budget, you should scale N and D together. GPT-3 was massively undertrained. The math falls directly out of the scaling-law form.
3. No saturation in sight. Power-law extrapolation keeps predicting improvement out to compute budgets we have not yet spent. Whether this holds indefinitely is unknown, but every model release of the last six years has stayed on the curve.

The scaling-laws picture has largely displaced classical learning theory as the working framework practitioners use to plan training runs. It is empirical and unsatisfying as theory, but it predicts.

When the intuition fails

• Effective capacity is not parameter count. A 70B model trained with weight decay and dropout may have effective capacity orders of magnitude lower than a 70B model trained without.
• In-distribution generalisation is well-behaved; OOD is not. Scaling laws say nothing about distribution shift. Models that match perfectly on the IID test set can fall apart on data drawn from a different source.
• Memorisation can be intentional. LLMs memorise rare facts (capital cities, code APIs). The question is not "does it memorise" but "does memorising hurt generalisation on other tasks." Empirically: it does not seem to, much.

Further reading

• Understanding deep learning requires rethinking generalization - Zhang, Bengio, Hardt, Recht, Vinyals; the random-label memorisation paper.
• Deep Double Descent - Nakkiran et al, the double-descent phenomenon documented across architectures.
• Scaling Laws for Neural Language Models - Kaplan et al 2020, the original scaling laws.
• Generalization in Deep Learning - Kawaguchi, Kaelbling, Bengio; a careful survey of where classical bounds fail.