Learn · Intermediate

Sample complexity: how many examples does learning actually take?

Sample complexity is the number of training examples a learning method needs in order to reliably learn a given pattern. It is a property of the method and the problem together -- not of the dataset -- which is what makes it powerful: it lets you say that one approach needs a thousand examples where another needs a million for the same result, and prove it rather than measure it. It is the formal version of the question everyone asks about modern AI, which is why a child learns a new word from three exposures while a language model reads most of the internet.

The question it makes precise

"How much data do you need?" is not answerable as stated. Sample complexity makes it answerable by pinning down three things: how accurate you need the result to be, how confident you need to be that you got there, and what class of pattern you are trying to learn. Given those, the sample complexity is the number of examples required.

What makes the concept useful is that the answer depends heavily on how you set up the learning, not just on how hard the problem is. Two methods pointed at identical data can have wildly different sample complexities. That gap is where most real progress in machine learning has come from -- and it is invisible if you only ever measure final accuracy on the data you happen to have.

Why the scaling is what matters

The important part of a sample-complexity result is rarely the constant. It is how the requirement grows as the problem gets harder.

Suppose a problem has a hidden structure of depth L -- letters compose into words, words into phrases, phrases into meaning. A method whose sample complexity grows exponentially in L is unusable past small depths: each extra layer multiplies the data you need, and you run out of internet. A method whose requirement grows linearly, or stays constant, keeps working. Same problem, same data, entirely different outcome, decided by the shape of the curve rather than its starting point.

This was demonstrated crisply in 2026 by Daniel Korchinski, Alessandro Favero and Matthieu Wyart. Using a grammar that generates tokens by recursively applying rules down a hidden tree, they proved that token-level learning -- predicting the next word, the standard objective for language models -- needs a number of samples exponential in the depth of that tree. Predicting your own internal representations instead, as JEPA and data2vec do, needs a number constant in the depth. Not a better constant. A different growth curve. We reported the result in predicting your own latents cuts the sample cost from exponential to flat.

The analogy is learning a language by memorising complete sentences versus learning the grammar. Memorising scales terribly, because there are exponentially many sentences. Learning the rules does not, because there are not many rules. Both approaches "work" on small examples; only one survives contact with a real language.

How it relates to scaling laws

Scaling laws and sample complexity answer neighbouring questions and are easy to confuse.

A scaling law is empirical. You train models at many sizes on many data volumes, plot loss against compute, and fit a curve -- the approach Joel Hestness and colleagues formalised in 2017 and Jared Kaplan's team made famous for language models in 2020. It tells you what happens if you keep doing what you are doing, and it has been extraordinarily useful for planning training runs.

Sample complexity is theoretical. It tells you what a method requires in principle, which lets it make comparisons a fitted curve cannot: not "this run will cost more" but "this entire family of methods is exponentially worse here." Scaling laws describe the road you are on. Sample complexity tells you whether a different road exists.

Why it matters in practice

The instinct that data is abundant is a text-specific illusion. There is a great deal of text on the internet and remarkably little of almost everything else: robot manipulation trajectories, medical imaging for rare conditions, failure footage from a specific factory line, labelled examples of anything a domain expert has to produce by hand. In those settings, the number of examples a method needs is the binding constraint on whether the project is possible at all.

This is why so much recent work is really sample-complexity work under other names. Fine-tuning and LoRA exist because adapting a pretrained model needs vastly fewer examples than training from scratch. In-context learning is the extreme case -- learning a pattern from a handful of demonstrations at inference time with no weight updates at all. Synthetic data is an attempt to buy your way out of a sample-complexity problem when real examples are unavailable. Distillation transfers what an expensive model learned so a cheap one does not have to pay the same price.

The honest limits

Theoretical bounds are frequently loose. A proof that a method needs at most some number of examples can be far above what it needs in practice, because worst-case analysis assumes an adversary chooses your data and reality usually does not. Bounds are also proved on tractable idealisations -- the Korchinski, Favero and Wyart result uses a synthetic grammar with a fixed tree shape and no context-dependent rules, and the authors say plainly that extending it toward real language is future work.

So treat sample complexity as a compass rather than a map. It will rarely tell you exactly how many examples to gather. It will reliably tell you which of two approaches gets worse faster as the problem grows, and that is the more valuable thing to know before you start.

Ground Truth. (2026, August 11). Sample complexity: how many examples does learning actually take?. Ground Truth. https://groundtruth.day/learn/sample-complexity.html

@misc{groundtruth:sample-complexity,
  title  = {Sample complexity: how many examples does learning actually take?},
  author = {{Ground Truth}},
  year   = {2026},
  month  = {aug},
  url    = {https://groundtruth.day/learn/sample-complexity.html}
}

Topics: learning-theory · sample-efficiency · scaling-laws · fundamentals · data