Formal Learning Theory Kernel: Blueprint v1

3.2.1 Stage 1: Sauer–Shelah (Statement)

The growth function measures the effective richness of \(\mathcal{H}\) on finite samples.

Definition 3.9 Growth Function

For a hypothesis class \(\mathcal{H}\) over \(X\) and integer \(m \geq 1\),

\[ \Pi _\mathcal {H}(m) = \max _{\{ x_1, \ldots , x_m\} \subseteq X} \bigl|\{ (h(x_1), \ldots , h(x_m)) : h \in \mathcal{H}\} \bigr|. \]

The growth function satisfies \(\Pi _\mathcal {H}(m) \leq 2^m\) always, with equality when \(\mathcal{H}\) shatters some set of size \(m\). The Sauer–Shelah lemma says that finite VC dimension forces a polynomial bound.

Lemma 3.10 Sauer–Shelah [

Lean: sauer_shelah

If \(\mathrm{VCdim}(\mathcal{H}) = d\), then for all \(m \geq d\),

\[ \Pi _\mathcal {H}(m) \leq \sum _{i=0}^d \binom {m}{i} \leq \left(\frac{em}{d}\right)^d. \]

The proof of the Sauer–Shelah lemma is combinatorial, proceeding by induction on \(m + d\). It is given in full in the companion textbook’s chapter on Combinatorial Dimensions. 1 For the present chapter, we take it as given and use only the consequence: if \(d = \mathrm{VCdim}(\mathcal{H}) {\lt} \infty \), then \(\Pi _\mathcal {H}(m) = O(m^d)\), polynomial, not exponential.