Generalisation and the Union Bound

Every model you fit reports a score on the data it was fitted to. That number is not what you want to know. What you want is how the model will do on data it has never seen, and the gap between the two is not a detail - it is the whole subject of this path.

Two errors, only one of which you can see

Fix a hypothesis $h$: some rule that takes an input and predicts a label.

Its true error is how often it is wrong across the whole population the data comes from. This is the quantity you care about, and you can never compute it.

Its training error is how often it is wrong on your sample. This you can compute, and it is the only thing you ever observe.

For a single, fixed hypothesis those two are close, and the reason is ordinary: each sample point is an independent trial, so the training error is an average of independent draws, and averages concentrate. Hoeffding's inequality makes that precise, bounding the probability that an average of $n$ bounded independent terms sits far from its expectation.

So far there is no problem. The problem arrives with the word fixed.

Choosing is not free

A learner does not pick a hypothesis in advance. It looks at the data and chooses the one that scores best. That choice is itself a function of the sample, and it breaks the guarantee entirely.

Here is the effect, measured on data designed so that there is nothing to learn. Every hypothesis is pure noise with a true error of exactly $0.5$; none is better than any other. Draw a sample of 200, score them all, and report the best:

With one candidate there is nothing to choose, and the training error lands within $0.0002$ of the truth. With a thousand, the reported error is $0.1149$ below the truth - a model that looks meaningfully better than chance while being exactly chance.

Nothing in that table is about the quality of the hypotheses. They are identical. What differs is luck, and taking the minimum is taking the luckiest. This is the mechanism behind every leaderboard that fails to replicate, every feature selected on the same data it is evaluated on, and every "we tried a few architectures and this one worked".

Paying for the search

The repair is to stop asking about the chosen hypothesis and ask about all of them at once.

If the guarantee holds simultaneously for every hypothesis in the class, then it holds in particular for whichever one the learner picked - no matter how that pick was made. The tool is the union bound, which is almost embarrassingly simple: the chance that at least one of several events happens is at most the sum of their individual chances.

Apply Hoeffding to each hypothesis, add up the failure probabilities, and solve for the sample size:

$$n \;\ge\; \frac{\ln|H| + \ln(2/\delta)}{2\varepsilon^2}$$

Read it as a price list. You choose $\varepsilon$, the tolerance you will accept, and $\delta$, how often you are willing for the guarantee to fail. The class size $|H|$ is what your search costs.

The logarithm is the whole story

Put numbers in it. For $\varepsilon = 0.1$ and $\delta = 0.05$:

Going from two hypotheses to over a million - half a million times as many - costs 658 extra samples. Not 658 times more; 658 more.

That is what $\log|H|$ buys you, and it is the reason machine learning is possible at all. If the requirement grew with $|H|$ rather than its logarithm, no interesting model class would ever be learnable. Instead, doubling the class adds a constant, so the requirement grows with the number of digits in the class size.

Both tables are in the figure below, and neither is simulated. The best of m identical hypotheses is the minimum of m binomial draws, so the flattery is a finite sum rather than an average over 200 trials - which fixes one entry: with a single candidate the expected gap is exactly 0, and the 0.0002 above is the simulation's own noise. Switch to the second panel and push the class size to a billion to watch the budget refuse to follow.

Why it must be uniform

One detail is worth stating separately, because skipping it is the commonest misunderstanding.

The bound holds for every hypothesis in the class at once. Not for the best one; not for a typical one. For all of them simultaneously.

That is exactly what is needed, and nothing weaker would do. The learner's output depends on the sample, so it is not fixed in advance, and a guarantee about a pre-specified hypothesis says nothing about it. Only a statement covering the whole class is guaranteed to cover whatever the data happened to select.

This also explains why the bound is two-sided and why it is pessimistic. It must survive an adversary who looks at your sample and picks the worst case, and that is a strong requirement. Real performance is usually far better than the bound promises, which is fine: the bound's job is to tell you which quantity controls generalisation, not to predict your test error.

What this leaves open

The argument counts hypotheses, which works when there are finitely many. Most real classes are infinite - every threshold on a line, every hyperplane in a space - and $\log|H|$ is then $\log\infty$, which is no bound at all.

Yet those classes plainly do generalise. So counting members must be the wrong measure of capacity, and the next lesson replaces it with the right one: not how many hypotheses a class contains, but how many genuinely different things it can do on the data you actually hold.