Sauer–Shelah lemma

Parent: vc-dimension Prereq: learning-theory — H; and vc-dimension — shattering, VCdim.

The lemma that turns "finite VC" into a usable bound: a class of finite VC realizes only polynomially many labelings on n points, not 2ⁿ. This is the engine of the fundamental-theorem.

Definition

h as a set, and the restriction h ∩ S Identify each hypothesis with its + region — the set of inputs it labels +:

$$h \;\equiv\; \{\, x \in X : h(x) = + \,\}.$$

Under this identification h ∩ S is an ordinary set intersection, picking out the + points of S:

$$h \cap S \;=\; \{\, s \in S : h(s) = + \,\} \;\subseteq\; S.$$

Because the labels are binary, this subset already is the labeling: s ∈ h∩S means s is +, s ∉ h∩S means −. So a subset of S and a labeling of S are the same thing, and distinct h ∩ S = distinct labelings.

Growth function

Let S ⊆ X be a set of n points from the input space. Restricting H to S gives $H|_S = \{ h \cap S : h \in H \}$ — the distinct labelings H produces on S (viewing each h as its set of + points). The growth function is the largest such count over all n-point sets:

$$\Pi_H(n) \;=\; \max_{S \subseteq X,\ |S| = n} \bigl| H|_S \bigr|.$$

Always $\Pi_H(n) \le 2^n$, with equality exactly when some n points are shattered.

It counts distinct label-patterns, and has nothing to do with predicting correctly (there is no target here).

Computing

Π_threshold(n) from the definition Recall hₜ ≡ [t, ∞), so hₜ ∩ S = {pᵢ ∈ S : pᵢ ≥ t} — the points to the right of t.

n = 2, S = {p₁, p₂} (p₁<p₂). Sweep t across the line and read off the intersection:

where t sits	hₜ ∩ S	labeling
t ≤ p₁	{p₁, p₂}	(+,+)
p₁ < t ≤ p₂	{p₂}	(−,+)
t > p₂	∅	(−,−)

3 distinct intersections ({p₁}, i.e. (+,−), never occurs) → |H|_S| = 3. Same for any 2 points, so Π(2) = 3.

General n, p₁ < … < pₙ. Since hₜ ∩ S is always the points ≥ t, it is a suffix {pᵢ, …, pₙ}. As t sweeps ℝ it falls into one of n+1 gaps (before p₁, between each consecutive pair, or after pₙ), and the suffix shrinks one point at a time:

$$\{p_1,\dots,p_n\} \to \{p_2,\dots,p_n\} \to \cdots \to \{p_n\} \to \varnothing.$$

That is n+1 distinct intersections, so |H|_S| = n+1. It's the same for every choice of n points, hence the max is

$$\Pi_{\text{threshold}}(n) = \max_{|S|=n} |H|_S| = n+1.$$

Infinitely many thresholds, only n+1 behaviors on n points — linear O(n), matching VC = 1. (Check: Sauer–Shelah gives C(n,0)+C(n,1) = 1 + n.) That collapse of an infinite class to a polynomial count is exactly what the growth function measures.

Sauer–Shelah

If VCdim(H) = d, then for all n

$$\Pi_H(n) \;\le\; \sum_{i=0}^{d} \binom{n}{i} \;\le\; \left(\frac{en}{d}\right)^{d} = O(n^{d}) \quad (n \ge d).$$

So above the VC dimension the growth function switches from exponential 2ⁿ to polynomial nᵈ — that jump is the whole reason finite VC ⟹ learnable.

Proof (induction on n)

Write $\Phi(n,d) = \sum_{i=0}^{d}\binom{n}{i}$; we show $|H|_S| \le \Phi(n,d)$ for every S with |S| = n, where $H|_S = \{\, h \cap S : h \in H \,\}$.

Base. n = 0: one (empty) labeling, and $\Phi(0,d) = 1$. d = 0: H shatters no single point, so all hypotheses agree on every point, giving $|H|_S| = 1 = \Phi(n,0)$.

Step. Fix a point x ∈ S and let $S' = S \setminus \{x\}$. Split $H|_S$ by how each labeling of S' extends over x:

• $H' := H|_{S'}$ — the labelings of S' (two labelings of S that agree on S' collapse to one);
• $H''$ — the labelings of S' that occur in $H|_S$ with both values of x.

Counting extensions gives $|H|_S| = |H'| + |H''|$ (each S'-labeling has one or two extensions; the two-extension ones are exactly $H''$).

• H' is a restriction of H, so VCdim(H') ≤ d, hence $|H'| \le \Phi(n-1,d)$ by induction.
• VCdim(H'') ≤ d − 1: if H'' shatters a set A ⊆ S', then every labeling of A appears with both values of x, so H shatters A ∪ {x}; thus |A| + 1 ≤ d. Hence $|H''| \le \Phi(n-1,d-1)$ by induction.

Adding, $|H|_S| \le \Phi(n-1,d) + \Phi(n-1,d-1) = \Phi(n,d)$ — the last equality is Pascal's identity $\binom{n-1}{i} + \binom{n-1}{i-1} = \binom{n}{i}$. ∎

The bound $\Phi(n,d) \le (en/d)^d$ then follows by a standard binomial estimate.