The Sauer-Shelah Lemma

Suppose you have a family of classifiers — say, all possible single vertical cutoffs on a number line — and $n$ labelled points. How many genuinely different ways can that family label those $n$ points as positive or negative? Naively, there are $2^n$ possible labelings, but most classifier families can't produce anywhere near all of them: a single cutoff can only ever split the points into "everything left is negative, everything right is positive," which is just $n+1$ distinct labelings, not $2^n$. The Sauer-Shelah lemma pins down exactly how slowly the number of achievable labelings can grow as $n$ increases, in terms of a single number describing the family's complexity.

That single number is the family's VC dimension, $d$: the size of the largest set of points the family can label in every possible way. The lemma says that once $n$ exceeds $d$, the number of distinct labelings the family can produce on any $n$ points is at most $\sum_{i=0}^{d} \binom{n}{i}$, which for large $n$ grows only polynomially, like $n^d$, rather than exponentially like $2^n$. In plain terms: a family that can only "shatter" small sets of points close together is stuck growing slowly forever after, no matter how large the dataset gets.

For the single-cutoff example, $d = 1$ (one point can always be labeled either way, but no two points can be split all four possible ways with a single cutoff). Plugging in, the bound gives at most $n + 1$ labelings for $n$ points — which matches the exact count.

This gap between $2^n$ and a polynomial in $n$ is the mathematical reason learning theory can bound how much a model can overfit: a hypothesis family with bounded VC dimension can't fit an ever-larger fraction of all possible label patterns as data grows, so agreement with the training labels starts to mean something about the underlying pattern rather than sheer flexibility.