Generalization: overfitting, regularization and the surprises of overparameterization

A model is useful only if it performs well on data it was not trained on. Classical statistics gave a clear account of when that happens, and modern deep learning broke much of it. Networks with far more parameters than training examples fit their data perfectly and still generalize well. This lesson covers the classical picture, the evidence against it, and what partly replaces it.

The classical picture

Training minimises the empirical risk, the average loss on the training set. What we care about is the expected risk on fresh data from the same distribution. The difference between the two is the generalization gap.

The classical story is a trade-off between bias and variance. A model class that is too simple cannot represent the true pattern: high bias, or underfitting. One that is too flexible fits the noise in its particular sample as well as the signal: high variance, or overfitting. Fitting ten noisy points with a degree-9 polynomial passes through every point and swings wildly between them. Test error, plotted against model capacity, traces a U-shape, and the advice is to stop at the bottom of the U. Capacity is controlled by choosing a smaller model or by regularization:

• Weight decay / L2 penalty. Add $\tfrac\lambda2\|\theta\|^2$ to the loss. In probabilistic terms this is maximum a posteriori estimation under a Gaussian prior on the weights (see Bayes' rule). With adaptive optimizers it should be applied in decoupled form (AdamW, covered in Stochastic optimization).^[1]
• Dropout. Randomly zero units during training, which prevents units from co-adapting and acts like averaging over many thinned networks.^[2]
• Early stopping. Halt when validation loss stops improving.
• Data augmentation. Enlarge the training set with label-preserving transformations.

All of these are still useful. The theory explaining why deep networks generalize did not survive contact with experiment.

Networks can memorise noise, and still generalize

Zhang, Bengio, Hardt, Recht and Vinyals ran a simple experiment in 2016. They took standard image-classification networks and trained them on CIFAR-10 and ImageNet with the labels randomly shuffled. The networks reached zero training error. Training took only a small constant factor longer than with the true labels. Test accuracy was, of course, at chance. The same networks also fit pure random-noise images, and explicit regularization barely changed any of this.^[3]

The consequence is sharp. The same architecture, optimizer and hyperparameters can either memorise random labels or learn generalizable features from real labels. So no measure of capacity that depends only on the model class can explain why the real-label network generalizes. Something about the interaction between the data, the optimizer and the architecture is doing the work.

Worked example: which of many perfect fits?

When parameters outnumber data points, infinitely many parameter settings fit the training set exactly. The question becomes which one the training procedure picks.

Take linear regression with one example, $x = (1, 1)$ and $y = 2$. Any $w$ with $w_1 + w_2 = 2$ interpolates: $(2,0)$, $(0,2)$, $(1,1)$, $(5,-3)$ and so on. The minimum-norm solution is

compared with $\|(2,0)\| = 2$ and $\|(5,-3)\|\approx5.83$. Gradient descent started from $w=0$ finds exactly $w^\star$. Every gradient of the squared loss is a multiple of $x$, so the iterates never leave the span of the data, and the only interpolating solution in that span is the minimum-norm one. Nobody added a penalty: the optimizer's dynamics supplied the preference. This is called implicit regularization.

Zhang et al. used the same argument and showed that it matters in practice. Fitting MNIST exactly with the minimum-norm kernel solution, with no regularization, gave 1.2% test error. They also cautioned that norm alone does not predict generalization. With wavelet preprocessing, the minimum norm rose from about 220 to about 390 while test error halved.^[3] Implicit bias is part of the story, not all of it.

Double descent

If huge models do not simply overfit, what replaces the U-curve? Belkin, Hsu, Ma and Mandal proposed double descent. Test error follows the classical U as capacity increases, peaks near the interpolation threshold, where the model has just enough capacity to fit the training data exactly, and then falls again as capacity grows further. They observed this across a range of model families and datasets.^[4]

The peak has a clear explanation in the linear case. At the threshold there is essentially one interpolating solution, and it must bend sharply to hit every noisy label, so its norm is huge. Past the threshold, many interpolators exist, and the implicitly selected low-norm one is smoother. Nakkiran et al. found the same shape in modern deep networks. Test error showed double descent as a function of model size and also of training epochs. In some regimes, more training data made test performance worse. They explain this through an "effective model complexity" that shifts where the interpolation threshold falls.^[5]

Flat minima, grokking, and what is still open

Several further observations sharpen the picture without settling it:

• Sharpness. Keskar et al. linked large-batch training to sharp minima and worse generalization.^[6] Dinh et al. showed that reparameterising a network can make a minimum arbitrarily sharp or flat without changing the function it computes, so raw sharpness cannot be the whole explanation.^[7] Whether some reparameterisation-invariant notion of flatness predicts generalization is still debated.
• Grokking. On small algorithmic datasets, such as modular arithmetic tables, Power et al. found networks that memorised the training set early, sat at chance on held-out data for a long time, and then jumped to perfect generalization long after overfitting. Smaller datasets needed more optimization before the jump.^[8] Validation loss at the moment of overfitting is not always a reliable signal to stop.
• Compression. A model that generalizes is one that finds a short description of its data, model cost included. The minimum-description-length view, developed in Prediction is compression, gives one principled account of why low-norm, structured solutions beat memorisation.^[9]

Generalization for large language models

Large language models change which question matters. They are trained on so many tokens that each example is seen only once or a few times, so training and held-out loss on the same distribution stay close. Muennighoff et al. found that repeating data for up to about four epochs changed loss negligibly compared with fresh data, while further repetition gave rapidly diminishing returns.^[10] The practical generalization questions become distribution shift (does capability transfer to new kinds of inputs?), memorisation of specific training sequences, and contamination of benchmarks by training data. These are covered in the Frontier track.

Sequential data raise a different failure: learning a new task can overwrite an earlier one (catastrophic forgetting). This lab's analysis of class-incremental learning finds that, when each task's expert is frozen, the difficulty reduces to choosing which expert to trust, not to generalization within tasks. The lab notes that this decomposition coincides with a theorem proved earlier by Kim et al. (2022).^[11] See Catastrophic forgetting is a verifier-exploitability problem.

Key takeaways

• Classical theory predicts a U-shaped test-error curve and controls capacity with regularization. Weight decay, dropout, early stopping and augmentation remain useful.
• Deep networks can memorise random labels yet generalize on real ones, so capacity of the model class alone cannot explain generalization.
• Among many perfect fits, the optimizer picks one. Gradient descent from zero finds the minimum-norm interpolator in linear models. This implicit bias helps but does not fully predict test error.
• Test error can follow double descent, peaking at the interpolation threshold and falling beyond it, as a function of model size, training time and even dataset size.
• Sharpness, grokking and compression each capture part of the story. A complete theory of deep-network generalization remains open.

Sources