Below the VC dimension a hypothesis class fully shatters — the number of distinct labelings on m points is 2m. Above it, that number collapses to a polynomial. This is the exact combinatorial phase transition that lets a class of infinite cardinality still be learnable. Rendered, not quoted.
source N. Sauer, On the density of families of sets, J. Combin. Theory Ser. A 13 (1972) 145–147 · doi:10.1016/0097-3165(72)90019-2 · independently Shelah (1972) & Vapnik–Chervonenkis (1971).
The Model
Witness class: intervals on the line, h[a,b](x)=1 iff a≤x≤b. A labeling of ordered points x1<…<xm is realizable iff its 1s form one contiguous run (or the empty set).
This class shatters any 2 points ( {}, {x1}, {x2}, {x1,x2} all reachable ) but never 3 — no interval yields {x1,x3} without x2. So VC dim d = 2, fixed by construction.
The engine enumerates all 2m sign patterns and counts the realizable ones. No sampling — exact.The Lineage
Neighbour: the-vc-dimension. VC gives one finite number, d — the largest shatterable set. Sauer is the engine that turns that number into a polynomial cap on the whole class.
A class of infinite cardinality (uncountably many intervals) produces at most O(md) behaviours on any m points. That polynomial is exactly what the union bound needs for uniform convergence to hold — the finite d tames the infinite class.
Sauer → effective hypothesis count → PAC generalization.The Witness · live re-check
Re-runs the tightness test against the current bound and confirms the growth function equals Sauer's sum for the witness class. Flips red the instant window 6 corrupts the upper index.
Checks: growth(m) == Σi=0..d C(m,i), all m in 0..10.
in ↓Data In
A point count m and the class's VC dimension d = 2. Nothing else — the growth function is a pure counting object.
LITThe Panel · the growth function
| m | Π(m) growth | 2m | Sauer bound | tight? |
|---|
Green rows = shattering region (m ≤ d): growth = 2m. Below the line: growth drops to a polynomial while 2m keeps doubling. Growth is computed by exact enumeration of all 2m patterns.
out ↓Data Out
—
The bound is tight for the interval class: growth equals Sauer's sum at every m — yet by m=10 it is — of 2m.
The Adversary
WALL"A finite VC dimension only bounds growth, not error. Your polynomial cap is on the count of labelings — it says nothing about which single hypothesis I'll pick."
True, and that is the whole point: Sauer bounds the effective size of the class; the union bound then converts that finite effective size into a generalization guarantee. Sauer is a lemma, not the theorem — it is the combinatorial half.
The Graveyard
"Growth ≤ 2m is already enough for learning."
→ No. 2m makes the union bound vacuous (m/2m → ∞ per-sample). Only the polynomial md makes it converge.
"Sauer's bound is loose, an over-count."
→ For threshold/interval classes it is exactly tight — equality at every m, verified live in window 0.
"A class with infinitely many members can't be bounded."
→ Cardinality is irrelevant; only d matters. Infinite intervals, growth = 1+m(m+1)/2.
The Tamper · planted void
Disclosed sabotage: sum the binomials up to d+1 instead of d. The bound over-counts, tightness breaks, and the Witness (7) catches it live.
upper index = d (clean)