Generalisation: VC dimension and double descent
Generalisation is doing well on unseen data. The VC dimension measures how much a family of models is able to fit. Double descent is the surprise that test error can fall again once models grow big enough to fit the training data exactly.
Why it matters
Classical theory says bigger models need more data or they overfit. Yet today's best models have far more parameters than training examples and still generalise well. To reason about model size and data size — and to read modern research — you need both the classical picture and the newer one.
The idea
Generalisation means doing well on data you have never seen. Classical theory says bigger models need more data. The VC dimension measures how many points a family of models can fit in every possible way. But deep networks break the simple story: as models grow past the point where they fit the training data perfectly, test error can go down again. This is called double descent.
A student who can memorise any answer sheet has high capacity. Classical theory says: give them more exercises than they can memorise, so they are forced to learn the ideas.
The student picture predicts that huge models must overfit. In practice, very large networks trained with SGD often generalise well. The theory is still catching up with that.
How it works
- Capacity: a family of models "shatters" a set of points if it can separate every possible labelling of them.
- Lines in 2-D can shatter 3 points in general position (all 8 labellings), but no set of 4: the XOR pattern always defeats them. So their VC dimension is 3.
- Classical bound: the gap between training and test error grows with capacity and shrinks with the amount of data. More capacity needs more data.
- That predicts a U-shaped test error as models grow, and it holds while models are smaller than the data.
- At the "interpolation threshold", where the number of parameters roughly equals the number of training points, the model can just about fit every point, and test error spikes.
- Past that point, among all the many perfect fits, training methods tend to find smooth, small-norm ones, and test error falls again: double descent.
Key points
- Generalisation gap = test error − training error.
- VC dimension = the largest number of points the model family can shatter.
- Classical regime: more parameters → more overfitting risk.
- Modern regime: very over-parameterised models trained with (S)GD often generalise well.
- The error peak sits where parameters ≈ training points, and label noise makes it worse.
- Practical lesson: when overfitting, "bigger model plus more data plus regularisation" can beat "smaller model".
Common mistakes
- Assuming more parameters always means worse generalisation.
- Assuming bigger is always better: near the interpolation threshold it can be worse.
- Treating VC bounds as accurate predictions. They are loose worst-case guarantees.
Not true: Adding parameters always makes a model generalise worse.
In fact: Past the point where a model can fit its training data exactly, test error often falls again as the model grows: double descent.
Not true: Model size: test error falls steadily as parameters are added, with no peak on the way.
In fact: Near the interpolation threshold, where the model can only just fit the training data, test error peaks. Bigger helps again only past that point.
Go deeper: Where a generalisation bound comes from
- Fix one model, chosen before seeing the data. Its training error is an average of n independent 0-or-1 mistakes, so it lands close to its true error (its error on new data). Hoeffding's inequality says how close: P(|true error − training error| > ε) ≤ 2·e^(−2nε²).
- But training picks the best of many models after seeing the data, and the best-looking one may just be lucky. Suppose the family has M models. The chance that at least one of them is off by more than ε is at most the sum of the separate chances: 2M·e^(−2nε²).
- Call that chance δ and solve for ε: ε = √(ln(2M/δ) / (2n)).
- So with probability at least 1 − δ, every model in the family, including the one training picks, satisfies: true error ≤ training error + √(ln(2M/δ) / (2n)).
- Read the formula. The gap grows with ln M, the capacity of the family, and shrinks like 1/√n. With M = 1,000 models, n = 10,000 examples and δ = 0.05, the gap is at most about 2.3 percentage points.
- Real model families are infinite, so ln M is replaced by a measure such as the VC dimension. For networks with millions of weights these bounds come out above 100% and say nothing, which is exactly the puzzle that double descent points at.
With probability 1 − δ: true error ≤ training error + √(ln(2M/δ) / (2n)). More capacity loosens the bound; more data tightens it like 1/√n.
Part of Unit 2: Classical ML, built by you in the free ML Foundations course.