The Fundamental Theorem of Statistical Learning

Before asking "how well can I learn this," there's a more basic question: "can this even be learned at all, from a finite amount of data, no matter how good my algorithm is?" It sounds like it should require a case-by-case answer for every model class. It doesn't. For binary classification, the fundamental theorem of statistical learning collapses that entire question to checking one number about the class: whether its VC dimension is finite. If it is, the class is learnable, full stop, and a sample-size formula tells you exactly how much data suffices. If it's infinite, no algorithm, however clever, can learn it from any finite sample.

The analogy: can this shape ever be traced from finitely many landmarks

Imagine trying to describe a curve's shape well enough that anyone could redraw it, given only finitely many labeled landmark points on it. If the family of curves you're choosing from is constrained enough — say, "the curve is some polynomial of degree at most 5" — a modest number of landmarks pins the curve down almost exactly, and more landmarks only help. If the family is "any curve whatsoever, no constraint," no finite number of landmarks is ever enough — between any two landmarks, wildly different curves in the unconstrained family agree at the landmarks and diverge everywhere else, so you can never be confident you've found the right one. The fundamental theorem says a hypothesis class is learnable exactly when it's constrained like the first case (a finite VC dimension) and not the boundless second case.

The formal statement

For a hypothesis class $\mathcal{H}$ of binary classifiers, the following are equivalent: (1) $\mathcal{H}$ has finite VC dimension $d$; (2) $\mathcal{H}$ is PAC-learnable (Agnostic PAC Learning); (3) any Empirical Risk Minimization algorithm learns $\mathcal{H}$ successfully. And the sample complexity — how much data is enough — is bounded both above and below by the same quantity $d$:

$$n = \Theta\!\left(\frac{d + \ln(1/\delta)}{\epsilon^2}\right)$$

In words: the number of examples needed to guarantee, with confidence $1-\delta$, error within $\epsilon$ of the best achievable in the class, scales directly with the VC dimension $d$ — not with how many parameters the model has, not with how the algorithm works internally, just with $d$. This is a two-sided result: it is not just an upper bound saying "$d$ this large is enough" (that's the VC bound) — it also proves a lower bound saying no algorithm can do meaningfully better than $\Theta(d/\epsilon^2)$ examples, which is what makes it "fundamental" rather than just "a useful bound."

Worked example 1: a learnable class and its sample size

Linear classifiers in $\mathbb{R}^2$ have VC dimension $d=3$ (they shatter 3 points but not 4, from Shattering and the Growth Function). By the theorem, this class is learnable, and to get $\epsilon = 0.05$ error with $\delta = 0.05$ confidence needs roughly $n = \frac{3 + \ln(20)}{0.0025} = \frac{3+3.0}{0.0025} = 2{,}400$ examples, give or take constants — a concrete, finite, computable number, guaranteed by the theorem to exist before you ever collect a single data point.

Worked example 2: an unlearnable class

Consider the class of "all subsets of the real line" as classifiers (label a point $+1$ if it's in some arbitrary chosen subset, $-1$ otherwise, with no constraint on the subset). This class shatters any finite set of points — for $n$ points, all $2^n$ labelings are trivially achievable by choosing the subset to be exactly the $+1$-labeled points. Its VC dimension is infinite. By the theorem, no finite sample size, however large, can guarantee learning within any fixed $\epsilon$ with confidence — there is always some true labeling consistent with the training data that generalizes arbitrarily badly, no matter how much data you collected, because the class was never constrained enough to rule such labelings out.

Increase the flexibility of the boundary above until it can trace literally any labeling of the points — that unconstrained extreme is the unlearnable class from worked example 2, just made visual.

What this means in practice

The theorem is why practitioners can trust that reasonably constrained model classes — regularized linear models, bounded-depth trees, bounded-width networks — are learnable in principle with realistic data volumes, while it also warns that literally unconstrained function classes are a theoretical non-starter no matter the sample size, which is precisely why every practical learning algorithm restricts to some constrained hypothesis class rather than "all functions."