Symptom

You have a classifier with 200 labelled examples and 40 features. It gets 100% on the training set. It gets 61% in production.

You collect 2,000 examples. Training accuracy is still 100%, production is 78%. At 20,000 examples production reaches 89%. Someone asks how many examples you need for 95%, and the honest answer you can give is “more,” which is not a plan and does not fit in a budget.

The instinct is that this is a property of your data — noisy labels, distribution shift, features that do not carry the signal. Some of it is. But the shape of the curve, the fact that there is a curve at all and that it has this form, is not about your data. It is determined by the complexity of the set of models you are choosing between, and it is a theorem.

Statement

Fix an input space $\mathcal{X}$, labels ${0,1}$, and a hypothesis class $\mathcal{H}$ of functions $\mathcal{X} \to {0,1}$. A learner sees $m$ examples drawn i.i.d. from an unknown distribution $\mathcal{D}$ and labelled by an unknown target, and outputs some $h \in \mathcal{H}$.

PAC learnable. $\mathcal{H}$ is probably approximately correct learnable if there is a learner and a function $m_{\mathcal{H}}(\epsilon, \delta)$ such that for every distribution and target, given $m \ge m_{\mathcal{H}}(\epsilon, \delta)$ examples, with probability at least $1 - \delta$ the output has true error at most $\epsilon$. Approximately is $\epsilon$; probably is $\delta$.

Shattering. $\mathcal{H}$ shatters a set $C \subseteq \mathcal{X}$ if $\mathcal{H}$ realises all $2^{|C|}$ labelings of $C$.

VC dimension. $\mathrm{VCdim}(\mathcal{H})$ is the size of the largest shattered set, or $\infty$.

Fundamental theorem of statistical learning (Vapnik–Chervonenkis 1971; Blumer, Ehrenfeucht, Haussler, Warmuth 1989). For binary classification with the 0–1 loss, $\mathcal{H}$ is PAC learnable if and only if $d = \mathrm{VCdim}(\mathcal{H})$ is finite, and then

$$m_{\mathcal{H}}(\epsilon,\delta) = \Theta\!\left(\frac{d + \log(1/\delta)}{\epsilon}\right)$$

in the realisable case, and $\Theta!\left(\frac{d + \log(1/\delta)}{\epsilon^2}\right)$ in the agnostic case.

Read the quantifiers. For every distribution: no assumption about the data is being used. The sample size depends on $d$, on $\epsilon$, on $\delta$ — and on nothing about $\mathcal{X}$, not its dimension, not its size.

Argument

Both directions are long; here is the load-bearing sketch, with the Read next carrying the rest.

Proof sketch.

(Finite $d$ suffices.) The goal is uniform convergence: with high probability, every $h \in \mathcal{H}$ has empirical error within $\epsilon$ of its true error. Then picking the empirical minimiser is safe. For a single $h$, Hoeffding gives failure probability $2e^{-2m\epsilon^2}$. A union bound over $|\mathcal{H}|$ hypotheses gives $m = O((\log|\mathcal{H}| + \log(1/\delta))/\epsilon^2)$ — useless when $\mathcal{H}$ is infinite. The fix is that only the behaviour on the sample matters, so the effective count is the growth function $\Pi_{\mathcal{H}}(m)$, the number of distinct labelings $\mathcal{H}$ realises on $m$ points. Sauer–Shelah: if $\mathrm{VCdim} = d$ then $\Pi_{\mathcal{H}}(m) \le \sum_{i\le d}\binom{m}{i} \le (em/d)^d$ — polynomial in $m$, not exponential, and this collapse is the entire content. A symmetrisation argument (compare the sample to a ghost sample, so the union bound runs over labelings rather than hypotheses) then gives uniform convergence at $m = O((d\log(1/\epsilon) + \log(1/\delta))/\epsilon^2)$; the $\log(1/\epsilon)$ is removable with more care.

(Finite $d$ is necessary.) If $\mathrm{VCdim} = \infty$, then for any $m$ there is a set of $2m$ points shattered by $\mathcal{H}$. Put $\mathcal{D}$ uniform on those $2m$ points and label them at random. The learner sees at most $m$ of them and has no information about the rest; some hypothesis in $\mathcal{H}$ realises every labeling, so its output is a coin flip on the unseen half. Expected error $\ge 1/4$, for every learner and every $m$. This is the No Free Lunch argument, and it is why the theorem is an equivalence.

The Sauer–Shelah collapse deserves a number. Take $\mathcal{H}$ = thresholds on a line, $h_a(x) = \mathbb{1}[x > a]$. It is an infinite class. On $m$ sorted points it realises exactly $m+1$ labelings, not $2^m$. It shatters any single point but no pair — you cannot label the left point 1 and the right point 0 — so $d = 1$. Plugging in: about $O((1 + \log(1/\delta))/\epsilon)$ examples, so a few hundred gets you $\epsilon = 0.01$ at $\delta = 0.05$. An infinite class, learnable from a few hundred examples, because infinity was never the relevant measure.

VC dimensions worth memorising. Intervals on a line: 2. Axis-aligned rectangles in the plane: 4. Half-spaces in $\mathbb{R}^n$: $n+1$. Any finite class: $\le \log_2|\mathcal{H}|$. Linear classifiers with a margin $\gamma$ on data of radius $R$: $O(R^2/\gamma^2)$, independent of dimension — which is the whole theoretical case for SVMs and kernels, since it says you may map into a million dimensions and pay only for the margin.

Back to the 40-feature classifier. If it is a linear model, $d = 41$, and the agnostic bound at $\epsilon = 0.05$, $\delta = 0.05$ wants roughly $(41 + 3)/0.0025 \approx 17{,}600$ examples. Your 200 examples were two orders of magnitude short, your 20,000 landed in the right region, and the observed curve matches. The theory did not tell you the accuracy; it told you the budget, before you spent it.

Why this depends on MDL. The framing in T025 — prefer the hypothesis with the shortest description — gets a quantitative form here. $\log_2 |\mathcal{H}|$ is a description length in bits, and for finite classes it upper bounds $d$. VC dimension is the right generalisation of “description length” to infinite classes: not how many models there are, but how many distinctions they can draw on finite data.

Forbids

Distribution-free learning of an infinite-VC class. Not hard, not sample-inefficient: impossible. Some distribution defeats every learner.

Zero training error as evidence of generalisation. The bound relates empirical to true error only through $d$. Without a complexity constraint, perfect training error carries no information — the class that memorises anything achieves it always.

Sample complexity that ignores hypothesis-class complexity. “How much data do I need” has no answer without $\mathcal{H}$. It is not a property of the problem alone.

Beating $\Omega(d/\epsilon^2)$ in the agnostic setting. The lower bound is matching. A clever algorithm does not escape it, only a smaller class or a distributional assumption does.

Does not forbid

It does not say high VC dimension means you cannot learn, which is the misreading that makes people fear large models. The bound is a sufficient sample size for a worst-case distribution. Real distributions are not adversarial, and a class with enormous $d$ can generalise beautifully on the data you actually have. The bound is one-directional.

It does not say the bound is tight for your problem. It is tight for the worst distribution over the whole class. Both quantifiers are worst-case, and the gap between that and a specific dataset is often several orders of magnitude. This gap is not a small technicality, and it becomes its own post shortly.

It does not require the target function to be in $\mathcal{H}$. That is the realisable case. The agnostic version compares you to the best hypothesis in the class, so the guarantee survives model misspecification, paying $\epsilon^2$ instead of $\epsilon$ in the rate.

It does not measure the number of parameters. VC dimension often tracks parameter count, and then people assume it always does. It does not: the one-parameter class ${\mathbb{1}[\sin(\theta x) > 0]}$ has infinite VC dimension. Margin-based classes go the other way, with unbounded parameters and finite effective complexity.

It does not cover regression, multiclass, or structured output directly. Those need fat-shattering dimension, Natarajan dimension, or Rademacher complexity. The pattern — a combinatorial capacity measure controlling uniform convergence — is the same; the specific numbers are not.

Boundary

  • i.i.d. is a real assumption. Time series, user sessions, and any data with feedback from your own model violate it, and the bounds say nothing there.
  • Worst-case over distributions is the source of nearly all the looseness. Distribution-dependent measures such as Rademacher complexity, computed on your actual sample, are much tighter and are what to use if you want a number to act on.
  • Computational cost is ignored entirely. PAC learnability is about sample size. Finding the empirical risk minimiser can be NP-hard, and for many natural classes it is.
  • The class must be fixed before seeing data. Choosing $\mathcal{H}$ by looking at the data invalidates the bound, and this is what hyperparameter search on a test set actually does.
  • The bounds are famously vacuous for deep networks, sometimes predicting error above 1. That is not a failure of the theorem, whose hypotheses are all satisfied. It is a failure of the worst-case framing to describe what is happening, and it is the most honest open problem in the field.

The reframing to keep: generalisation is not about how much data you have, it is about the ratio of data to the number of distinctions your model class can draw. Everything else in learning theory is an attempt to measure that second quantity more sharply.