Generalisation: VC dimension and double descent

Step 1 Understand it

The problem it solves. 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.

Watch it happen

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.

How it works, step by step

1. Capacity: a family of models "shatters" a set of points if it can separate every possible labelling of them.
2. 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.
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.
4. That predicts a U-shaped test error as models grow, and it holds while models are smaller than the data.
5. 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.
6. 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.

Picture it

xychart-beta
  title "Double descent (illustration): 100 training points"
  x-axis "number of features" [10, 50, 90, 100, 110, 200, 500, 1000]
  y-axis "test error" 0 --> 4.5
  line [1.0, 0.6, 1.5, 4.0, 1.6, 0.8, 0.6, 0.5]

Analogy

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.

Where the analogy breaks

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.

Worked example

A straight line in 2D can separate 3 points (not all in a line) in every possible labelling, but it cannot separate one labelling of 4 points: the XOR pattern. So the VC dimension of a 2D linear classifier is 3.

Must-know 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.

Step 2 Go further (optional)

Optional. The lesson above is written to be enough on its own. If you want a second explanation, start with the one marked Worth it.

• Interactive

  Double Descent

  MLU-Explain (Amazon) · animated, scroll through it

  Worth it: The error curve rises, peaks at the interpolation threshold and falls again, animated alongside the fitted models. It makes a strange result intuitive.

• Read

  Understanding Deep Learning, Ch 8 (double descent) and Ch 20 (why does deep learning work?)

  Simon Prince · free

• Read

  Understanding Machine Learning, Ch 2–6 (PAC learning, VC dimension)

  Shalev-Shwartz and Ben-David · free

• Paper

  Deep Double Descent (2019)

  Nakkiran et al. · arXiv · optional

Step 3 Practise

Try each exercise yourself first: on paper, out loud or in code. Then open the answer and compare it with yours.

1. ExplainSay it in plain words, with no notes.

   Explain double descent in plain words, and why it surprised people.

   Show answer

   The classic picture says: a model that is too simple underfits, a model that is too big overfits, and the best is in between, so test error is a U shape. Double descent says that if you keep making the model bigger, past the point where it can fit every training example perfectly, test error can come down again, often lower than before.

   It surprised people because classical theory said a model that fits every training point, noise and all, must generalise badly. But modern neural networks are exactly that: huge, fitting their training data almost perfectly, and still working well. The explanation is that when there are many ways to fit the data, training tends to find a simple, smooth one, and the worst behaviour happens only at the in-between size where there is just one way to fit.

2. DeriveWrite the maths, or the steps, from memory.

   Show on paper that a line can split 3 points in all 8 labellings, but fails on one labelling of 4 points.

   Show answer

   Three points (not in a line), say at the corners of a triangle. There are 2³ = 8 ways to label them + or −:
   • All the same (2 labellings): put the line off to one side of all three.
   • One point different from the other two (6 labellings): any single corner of a triangle can be cut off from the other two by a straight line.
   So a line can produce all 8 labellings: it "shatters" 3 points.

   Four points, say the corners of a square. Label opposite corners alike: top-left and bottom-right +, top-right and bottom-left − (the XOR pattern). A line would need both + points on one side and both − points on the other. But the segment joining the two + points crosses the segment joining the two − points, and a line can't separate two segments that cross. So at least one labelling of 4 points fails. (In fact no set of 4 points in the plane can be shattered by a line.)

   That makes the VC dimension of a straight-line classifier in 2D equal to 3.

3. BuildCode it from scratch in NumPy, with no ML library.

   Reproduce double descent: fit polynomial or random-feature regression with the minimum-norm solution (np.linalg.lstsq) on 100 noisy points, with 10 to 1,000 features. Plot test error against the number of features.

   Show answer

   Use random ReLU features: draw a fixed random projection for each feature, apply ReLU, and fit a linear model on top with np.linalg.lstsq, which returns the minimum-norm solution once there are more features than points. Here the inputs have 10 dimensions and there are 100 noisy training points.

   The test error first falls (best around 25 features), then climbs to a sharp peak at exactly 100 features, the number of training points, where it is about 90 times worse, then falls again and keeps improving all the way to 2,000 features, ending close to the first dip. That second fall is double descent.

   At the peak there is exactly one way to fit every noisy point, and it is a wild one. With many more features there are endless ways to fit the data, and the minimum-norm one is smooth.

   pythonCopy

   import numpy as np
   import matplotlib.pyplot as plt
   
   rng = np.random.default_rng(0)
   d, n = 10, 100
   beta = rng.normal(size=d) / np.sqrt(d)
   truth = lambda X: np.tanh(2 * X @ beta)
   X_tr, X_te = rng.normal(size=(n, d)), rng.normal(size=(2000, d))
   W = rng.normal(size=(d, 2000)) / np.sqrt(d)               # 2,000 random features, fixed
   features = lambda X, p: np.maximum(0, X @ W[:, :p])
   
   ps = [10, 25, 50, 75, 90, 100, 110, 125, 150, 200, 400, 1000, 2000]
   errors = []
   for p in ps:
       errs = []
       for seed in range(5):                                  # median over 5 noise draws
           y = truth(X_tr) + np.random.default_rng(seed).normal(0, 0.2, n)
           w = np.linalg.lstsq(features(X_tr, p), y, rcond=None)[0]   # minimum-norm fit
           errs.append(np.mean((features(X_te, p) @ w - truth(X_te)) ** 2))
       errors.append(np.median(errs))
   print([(p, round(float(e), 3)) for p, e in zip(ps, errors)])
   # [(10, 0.338), (25, 0.164), ... (100, 14.477), ... (2000, 0.222)]
   plt.plot(ps, errors, marker="o"); plt.axvline(n, linestyle=":", color="grey")
   plt.xscale("log"); plt.yscale("log"); plt.xlabel("number of features"); plt.ylabel("test error")
   plt.show()

4. BreakShow when it fails, and why.

   Add more label noise and repeat. What happens to the error peak near 'number of features = number of training points'?

   Show answer

   With more label noise, the peak at "number of features = number of training points" gets much taller: in the run below, about 5 with no noise, 14 with noise 0.2 and 74 with noise 0.5. Far to the right, the error still comes back down.

   Why: at that point the model has just enough freedom to pass exactly through every training point, noise included, and there is only one way to do it. To hit every noisy point it must swing wildly between them, and the more noise there is, the wilder the swings. Below the peak the model can't fit the noise; far above it, the minimum-norm solution spreads the noise thinly across many features.

   Even with no label noise there is still a peak here, because these features can't represent the target exactly, and that mismatch acts like noise. The fix is the usual one: a little regularisation. In this setup, ridge with a small λ (0.01) instead of the exact minimum-norm fit brings the error at 100 features down from tens to about 0.2, flattening the peak.

   pythonCopy

   import numpy as np
   
   rng = np.random.default_rng(0)
   d, n = 10, 100
   beta = rng.normal(size=d) / np.sqrt(d)
   truth = lambda X: np.tanh(2 * X @ beta)
   X_tr, X_te = rng.normal(size=(n, d)), rng.normal(size=(2000, d))
   W = rng.normal(size=(d, 2000)) / np.sqrt(d)
   features = lambda X, p: np.maximum(0, X @ W[:, :p])
   for noise in [0.0, 0.2, 0.5]:
       row = []
       for p in [25, 100, 2000]:
           errs = []
           for seed in range(5):
               y = truth(X_tr) + np.random.default_rng(seed).normal(0, noise, n)
               w = np.linalg.lstsq(features(X_tr, p), y, rcond=None)[0]
               errs.append(np.mean((features(X_te, p) @ w - truth(X_te)) ** 2))
           row.append(round(float(np.median(errs)), 2))
       print(f"noise {noise}: test error at 25 / 100 / 2000 features = {row}")

Step 4 Prove it

Check you understood

Tick each check when you can do it without notes