How Much Data Is Enough?

Chapter 11 said the only thing that counts is doing well on data you have never seen. Chapter 12 said every model must bring an assumption to the table. Neither answered the practical question, which is the one people actually have: how many examples do I need? A model that fits ten points perfectly might still be wrong everywhere else.

There is a real theory for that question. It is one of the most useful things in this guide and it is nearly always skipped, because it is not how modern systems are built.

Making the question countable

Two names do the work. PAC learning — probably approximately correct, from Leslie Valiant’s 1984 model — reframes learning as a promise: with probability at least 1 − δ, the rule you learned is within ε of the best possible. Instead of asking whether a model is right, it asks how close to right it is, and how often.

Once the promise is written that way, you can ask the obvious follow-up: how many examples does it take to keep it? That number is the sample complexity. The surprising result — worked out by Blumer, Ehrenfeucht, Haussler and Warmuth in 1989 — is that it does not depend on the number of parameters, or on how clever the learning algorithm is. It depends on one combinatorial property of the set of rules you allowed.

Capacity is the currency

That property is the Vapnik–Chervonenkis dimension. Roughly: the largest number of points your model can label in every possible way. A straight line in a plane can shatter three points but not four, so its VC dimension is three. A model that can fit anything has a VC dimension as large as you like.

The paper’s central result is stated plainly: “the essential condition for distribution-free learnability is finiteness of the Vapnik–Chervonenkis dimension.” Finite capacity means learnable. And the standard error bound has the shape you would now expect —

test error  ≤  training error  +  O( √( VC dimension / n ) )

— where n is the number of examples. The bound says the extra error from learning rather than memorising shrinks like one over the square root of your data, and grows with the square root of your capacity. To double your accuracy you need four times the data; to keep the same accuracy with a much richer model, you need proportionally more examples. Steve Hanneke later proved the tight version of the bound in 2016, closing a problem open for decades.

This is the real content of the old warning against overfitting, with the numbers filled in. And it explains something the scaling chapters will make concrete: a bigger model does not just need more compute, it needs more data to be worth its capacity.

Where this picture broke

Then it stopped being true, or at least stopped being the explanation.

In 2017, Zhang, Bengio, Hardt, Recht and Vinyals ran the experiment that should have been run years earlier. They took ordinary deep networks and randomised the labels — gave every image a meaningless category — and trained. The networks fit the random labels perfectly. A model that can memorise pure noise has capacity to spare, far more than it has data. Classical theory says such a model should generalise terribly. Yet the same architectures, trained on real labels, generalise well.

So the bound is sound but not explanatory: it is a worst case over all models of that capacity, and real training does not find the worst one. Something else is doing the work — and the honest position is that the classical theory tells you the price of capacity without telling you why the purchase is so often a good one.

If capacity does not explain why big models work, something else must. The oldest candidate is a principle most people already believe: the best explanation of the data is the shortest one that still fits.