The Generalization Gap

A researcher shows you a strategy with a backtested Sharpe of 2.5 over eight years. It goes live and does 0.4. Nobody lied, no code was wrong, the data was clean. The number simply did not survive contact with data it had not already seen.

That distance has a name. Every model has a score on the data used to build it and a score on everything else, and the second is the one that pays you. The difference between them is the generalization gap, and the entire field of learning theory is an attempt to say something reliable about how big it can be before you find out the expensive way.

The interesting part is that the gap has two completely different sources, and they call for completely different remedies. One is ordinary sampling noise, which shrinks predictably as you gather more data. The other is a bias you create yourself, by choosing the model after looking at the data — and that one can be enormous, does not shrink with more data if you also search harder, and is invisible in the training numbers.

The analogy: revising from a paper you have already memorised

You practise for an exam using last year's paper. After four run-throughs you are scoring 95%. That 95% measures two things mixed together: how much maths you know, and how much of that specific paper you have absorbed. The real exam separates them, usually unkindly.

Now imagine you had done this with fifty past papers and reported only your best score. Even if your ability never changed, your best-of-fifty number is high — some paper happened to suit you. Report it and you have not lied about a single figure, yet the number is systematically optimistic. Backtesting a hundred variants and reporting the winner is the same procedure.

Writing it down

Write $h$ for a model — a specific rule that maps an input to a prediction. Write $\ell(h, z)$ for the loss it incurs on one example $z$: 1 if it misclassifies, 0 otherwise, say.

The true risk is the average loss over the whole world, not just the data you hold:

$$R(h) = \mathbb{E}_{z \sim \mathcal{D}}\big[\ell(h, z)\big]$$

In words: if examples keep arriving forever from the same source $\mathcal{D}$, $R(h)$ is the long-run average loss. It is the number you actually care about and can never observe.

The empirical risk is the same average over the $n$ examples in your sample $S$:

$$\hat{R}_S(h) = \frac{1}{n}\sum_{i=1}^{n} \ell(h, z_i)$$

In words: the score on the data in front of you. Observable, and the only thing you ever compute.

The gap is the difference, $R(h) - \hat{R}_S(h)$: how much your measured score flatters the truth.

Here is the fact everything hangs on. If $h$ was fixed before you drew the sample, then $\hat{R}_S(h)$ is an average of $n$ independent draws whose mean is $R(h)$, so it is an unbiased estimate and the gap is pure noise that shrinks like $1/\sqrt{n}$. If $h$ was chosen using the sample — which is what fitting a model means — that argument collapses, because $h$ and $S$ are no longer independent.

Worked example 1: the gap for a model you did not tune

A classifier was built last year, frozen, and shipped. You evaluate it on $n = 500$ fresh examples and it errs on 118 of them, so $\hat{R}_S(h) = 0.236$. What is the true error?

Hoeffding's inequality says that for an average of $n$ independent quantities bounded in $[0,1]$,

$$\Pr\big(|\hat{R}_S(h) - R(h)| > \varepsilon\big) \le 2e^{-2n\varepsilon^2}$$

Set the right side to $\delta = 0.05$ and solve for $\varepsilon$:

$$\varepsilon = \sqrt{\frac{\ln(2/\delta)}{2n}} = \sqrt{\frac{\ln 40}{1000}} = \sqrt{\frac{3.6889}{1000}} = \sqrt{0.0036889} = 0.0607$$

So with 95% confidence the true error sits within 6.1 percentage points of 0.236 — somewhere in $[0.175, 0.297]$. That is the honest width of a 500-example evaluation, and it is wider than most people assume.

Now watch how slowly it improves. To halve the gap to 3.0 points you need $\varepsilon^2$ to quarter, so $n$ must quadruple to 2,000: $\sqrt{3.6889/4000} = 0.0304$. To reach 1 point you need $n = 18{,}445$. Statistical noise costs data quadratically, which is why evaluation sets are always smaller than you would like.

The explorer below shows this shape directly: a running average settling on the truth with an envelope that narrows like $1/\sqrt{n}$. That envelope is the gap for one fixed model.

Worked example 2: the gap you create by choosing

Now the dangerous half. You test $m = 1000$ strategy variants on the same $n = 500$ observations. Suppose — pessimistically but instructively — that every single one is worthless, with true error exactly $R = 0.5$.

Step 1 — how noisy is each measurement? Each $\hat{R}_S$ is a proportion from 500 coin flips, so its standard deviation is

$$\sqrt{\frac{0.5 \times 0.5}{500}} = \sqrt{0.0005} = 0.02236$$

Step 2 — how good does the best of 1000 look? The minimum of 1000 roughly normal draws sits about 3.24 standard deviations below their mean. So the winner's measured error is about

$$0.5 - 3.24 \times 0.02236 = 0.5 - 0.0725 = 0.4275$$

Step 3 — read the result. The winner shows 42.8% error. Its true error is 50%. You will report a 7.2-point edge that does not exist, and nothing in your training numbers reveals this, because the search itself is what created it. Note also that more data alone does not save you if you also expand the search: doubling $n$ shrinks each standard deviation by only $\sqrt{2}$, while going from 1,000 to 100,000 variants pushes the multiplier from 3.24 to about 4.42.

Step 4 — the bound that does account for it. Applying Hoeffding once per candidate and adding the failure probabilities gives a guarantee that covers all $m$ at once:

$$\varepsilon = \sqrt{\frac{\ln(2m/\delta)}{2n}} = \sqrt{\frac{\ln 40{,}000}{1000}} = \sqrt{\frac{10.5966}{1000}} = 0.1029$$

Ten-and-a-third points, not six. The wider bound comfortably covers the 7.2-point illusion you produced — that is what the extra width is for. Notice that $m$ enters inside a logarithm, so searching a hundred times harder widens the bound by only about 50%. Search is not forbidden; it is priced.

The explorer below shows the gap as model flexibility increases. Watch the training curve fall monotonically while the test curve turns up — the vertical distance between them at any point is the generalization gap.

What this means in practice

A held-out set is only clean until you use it to decide. The first time you look at test error and change something, that set has joined your training data in every way that matters. Keep a third split you touch once.

Count your search, and say the number. "We tried three configurations" and "we tried eleven thousand" deserve very different discounts on the same reported Sharpe. In quant research this is the entire logic behind the The Deflated Sharpe Ratio and behind purged, combinatorial cross-validation.

Prefer fewer, better-motivated candidates. Because $m$ sits inside a logarithm, the fix is rarely "collect more data" — it is "stop generating hypotheses you have no reason to believe".

The gap is not a bug to eliminate. A model with a zero gap and 45% error is worse than one with a 5-point gap and 20% error. What you minimise is true risk, and the gap is only one of its two ingredients.

Practise it

1. You evaluate a frozen model on 2,000 examples and see 15% error. Give a 95% interval for true error. (Answer: $\varepsilon = \sqrt{\ln 40/4000} = 0.0304$, so $[0.120, 0.180]$.)
2. How many examples for a 95% interval of width $\pm 2$ points? (Answer: $n = \ln 40 / (2 \times 0.02^2) = 4611$.)
3. You search 250 variants on 1,000 observations, all truly worthless with error 0.5. Roughly how good will the winner look? (Answer: sd $= 0.0158$; best of 250 is about 2.81 sd out, so $0.5 - 0.044 = 0.456$.)
4. Rework question 3 with 10,000 observations instead. Does the illusion vanish? (Answer: sd $= 0.005$, illusion $\approx 1.4$ points — it shrinks like $1/\sqrt{n}$ but never reaches zero.)