VC Dimension, the Growth Function, and the Sauer-Shelah Lemma

Intuition Beginner

A class of rules is dangerous when it can memorise. The clean way to measure that danger is to ask: how many example points can the rules tag in every possible yes/no pattern? If your rules can paint two points in all four ways — both yes, both no, first yes second no, first no second yes — then two points cannot trip them up; whatever the truth turns out to be, some rule already matches it. If they can do this for three points, the rules are richer still. The largest number of points the rules can pattern in every way is the single number that captures the capacity of the whole class.

This number is the VC dimension. It is small for plain rule families and infinite for families rich enough to fit anything. A family of straight cutoffs on a line — "say yes above the cutoff" — can pattern one point in both ways but cannot pattern two points in the order yes-then-no, so its number is one. The lesson is that a low number means the rules cannot memorise much, which is exactly what makes them safe to trust on new data.

The payoff is a sharp split. Count the distinct labelings a class can produce on a sample of $m$ points. If the VC dimension is some finite $d$, that count grows only like a polynomial in $m$ — slow. If the dimension is infinite, the count is the full $2$-to-the-$m$ — every pattern, always. There is no middle ground, and the slow polynomial growth is the whole reason finite-dimension classes can learn while all-powerful ones cannot.

Visual Beginner

Picture two points on a page and a family of straight cutoffs you can slide and flip. Can you realise all four labelings of the two points? For cutoffs on a line you can get three of them but never the pattern where the left point is yes and the right point is no, so a line of cutoffs shatters one point, not two. Now picture a rectangle you may stretch and place freely: it can capture any four points in every in-or-out pattern, but five points defeat it. The largest fully-patternable set is the VC dimension.

 thresholds on a line          axis-aligned rectangles in the plane
   . shatter 1 point             :: shatter 4 points (every in/out pattern)
   .  . cannot do (yes,no)       five points: some pattern is unreachable
   VC dimension = 1              VC dimension = 4

Rule family	Largest set it can pattern every way	VC dimension
thresholds on a line	one point	1
intervals on a line	two points	2
axis-aligned rectangles in the plane	four points	4
every possible rule	any size, forever	infinite

The picture teaches the rule of thumb: a small dimension means the family runs out of patterns quickly, so it cannot fit just anything.

Worked example Beginner

Take the family of intervals on the number line: each rule picks a left end and a right end and says yes inside, no outside. We find its VC dimension by hand.

Step 1. Can it pattern two points? Place points at $1$ and $2$. The pattern no-no comes from an interval that misses both, say $[5,6]$. The pattern yes-yes comes from $[0,3]$. The pattern yes-no comes from $[0.5,1.5]$, catching $1$ but not $2$. The pattern no-yes comes from $[1.5,2.5]$. All four patterns appear, so two points are shattered.

Step 2. Can it pattern three points? Place points at $1$, $2$, $3$ and ask for the pattern yes-no-yes: catch $1$ and $3$ but skip $2$. An interval is one unbroken stretch, so any interval containing both $1$ and $3$ must also contain everything between them, including $2$. The pattern yes-no-yes is impossible.

Step 3. Read off the dimension. Two points can be patterned every way; three points cannot. So the VC dimension of intervals is exactly $2$.

Step 4. Count labelings on a sample. On $m$ points an interval is pinned down by which point it first catches and which it last catches, giving at most about $m^2/2$ distinct labelings — a polynomial of degree $2$, matching the dimension.

What this tells us: the VC dimension is found by pushing the point count up until some pattern becomes unreachable, and that same dimension is the exponent governing how the labeling count grows.

Check your understanding Beginner

Formal definition Intermediate+

The setting is that of 45.07.02: a domain $\mathcal{X}$, a binary label set $\{0,1\}$, and a hypothesis class $\mathcal{H}$ of functions $h:\mathcal{X}\to \{0,1\}$. The combinatorial complexity of $\mathcal{H}$ is measured through how it behaves on finite point sets.

Definition (restriction / trace). For a finite set $C=\{c_1,\dots ,c_m\}\subseteq \mathcal{X}$, the restriction of $\mathcal{H}$ to $C$ is the set of label vectors it induces,

$${\mathcal{H}}_C=\{(h(c_1),\dots ,h(c_m)):h\in \mathcal{H}\}\subseteq \{0,1{\}}^m.$$

Distinct hypotheses agreeing on all of $C$ collapse to one vector, so $|{\mathcal{H}}_C|\le 2^m$ always.

Definition (shattering). A finite set $C$ with $|C|=m$ is shattered by $\mathcal{H}$ if $\mathcal{H}$ realises all of its labelings, ${\mathcal{H}}_C=\{0,1{\}}^m$, equivalently $|{\mathcal{H}}_C|=2^m$.

Definition (VC dimension). The Vapnik-Chervonenkis dimension of $\mathcal{H}$ is

$$\mathrm{VCdim}(\mathcal{H})=\sup \{|C|:C\subseteq \mathcal{X}\text{ finite and shattered by }\mathcal{H}\},$$

with $\mathrm{VCdim}(\mathcal{H})=\infty$ when arbitrarily large sets are shattered. To prove $\mathrm{VCdim}(\mathcal{H})=d$ one exhibits one shattered set of size $d$ and shows no set of size $d+1$ is shattered ^{[Shalev-Shwartz Ben-David 2014]}.

Definition (growth function / shatter coefficient). The growth function is the largest number of labelings $\mathcal{H}$ realises on any $m$-point set,

$${\Pi }_{\mathcal{H}}(m)=\underset{C\subseteq \mathcal{X},|C|=m}{\max }|{\mathcal{H}}_C|.$$

By definition ${\Pi }_{\mathcal{H}}(m)\le 2^m$, with equality for $m\le \mathrm{VCdim}(\mathcal{H})$.

Catalogue of VC dimensions Intermediate+

• Thresholds $\mathcal{H}=\{x\mapsto 1[x\ge a]:a\in \mathbb{R}\}$ on $\mathbb{R}$: $\mathrm{VCdim}=1$. One point is shattered; two points $x_1<x_2$ cannot realise $(1,0)$ since the rule is monotone.
• Intervals $\{x\mapsto 1[x\in [a,b]]\}$: $\mathrm{VCdim}=2$. Two points are shattered; three points $x_1<x_2<x_3$ cannot realise $(1,0,1)$ since an interval is connected.
• Axis-aligned rectangles in ${\mathbb{R}}^2$: $\mathrm{VCdim}=4$. Four extremal points are shattered; among any five points one lies in the bounding box of the others and cannot be excluded while they are included.
• Halfspaces $\{x\mapsto 1[⟨w,x⟩+b\ge 0]:w\in {\mathbb{R}}^d,b\in \mathbb{R}\}$ in ${\mathbb{R}}^d$: $\mathrm{VCdim}=d+1$, proved in the Key theorem.
• Finite classes: $\mathrm{VCdim}(\mathcal{H})\le {\log }_2|\mathcal{H}|$, since shattering $d$ points needs $2^d$ distinct restrictions, hence $2^d\le |\mathcal{H}|$.

Counterexamples to common slips Intermediate+

• "VC dimension counts the parameters of the class." Usually parameters and VC dimension agree (halfspaces: $d+1$ parameters, $d+1$ dimension), but not always. The one-parameter sine family $\{x\mapsto 1[\sin (tx)\ge 0]:t>0\}$ has infinite VC dimension. Parameter count is a heuristic, not the definition.
• "To show $\mathrm{VCdim}\ge d$ I must shatter every $d$-set." Only some $d$-set need be shattered. To show $\mathrm{VCdim}<d+1$, however, no $(d+1)$-set may be shattered — the asymmetry between the existential lower bound and the universal upper bound is where computations go wrong.
• "A small growth function means a small class." The growth function is small (polynomial) exactly when the VC dimension is finite, regardless of cardinality: an infinite class of finite VC dimension has polynomial growth, while a finite class of size $2^{100}$ may shatter up to $100$ points.

Key theorem with proof Intermediate+

The signature result is the Sauer-Shelah lemma: finite VC dimension forces the growth function to be polynomial rather than exponential. The proof is a self-contained combinatorial induction — independently due to Sauer, Shelah and Perles, and Vapnik and Chervonenkis around 1971-1972 — that bounds the number of distinct labelings by counting subsets of bounded size.

Theorem (Sauer-Shelah). Let $\mathcal{H}$ be a hypothesis class with $\mathrm{VCdim}(\mathcal{H})=d<\infty$. Then for every $m$,

$${\Pi }_{\mathcal{H}}(m)\le \sum _{i=0}^d\left(\genfrac{}{}{0ex}{}{m}{i}\right),$$

and for $m\ge d\ge 1$ this is at most $(em/d{)}^d$. ^{[Shalev-Shwartz Ben-David 2014]}

Proof. Fix an $m$-point set $C=\{c_1,\dots ,c_m\}$; it suffices to bound $|{\mathcal{H}}_C|$, since ${\Pi }_{\mathcal{H}}(m)$ is the maximum of this over $C$. Identify each label vector with the subset of $C$ it marks $1$, so ${\mathcal{H}}_C$ becomes a family $\mathcal{F}\subseteq 2^C$ of subsets of $C$. A set $B\subseteq C$ is shattered by $\mathcal{F}$ if every subset of $B$ arises as $A\cap B$ for some $A\in \mathcal{F}$; because $\mathcal{F}={\mathcal{H}}_C$, a set shattered by $\mathcal{F}$ is shattered by $\mathcal{H}$, so $\mathcal{F}$ shatters no set of size $d+1$.

The claim is the sharper statement that for any family $\mathcal{F}\subseteq 2^C$,

$$|\mathcal{F}|\le |\{B\subseteq C:B\text{ is shattered by }\mathcal{F}\}|.$$

Granting this, since $\mathcal{F}$ shatters no set larger than $d$, the shattered sets all have size $\le d$, so $|\mathcal{F}|\le {\sum }_{i=0}^d\left(\genfrac{}{}{0ex}{}{m}{i}\right)$, the count of subsets of $C$ of size at most $d$.

Prove the claim by induction on $m=|C|$. For $m=0$ the family is $\{\varnothing \}$ or $\varnothing$ and the empty set is the only candidate; both sides agree. For the step, fix an element $x\in C$ and split $\mathcal{F}$ by whether a set contains $x$. Define two families on $C^{\prime }=C\setminus \{x\}$:

$${\mathcal{F}}_0=\{A\in \mathcal{F}:x\notin A\},{\mathcal{F}}_1=\{A\setminus \{x\}:A\in \mathcal{F},x\in A,A\setminus \{x\}\in {\mathcal{F}}_0\}.$$

Here ${\mathcal{F}}_0$ collects the sets avoiding $x$, viewed inside $C^{\prime }$, and ${\mathcal{F}}_1$ collects those $x$-traces whose $x$-free version is also present in ${\mathcal{F}}_0$. Every $A\in \mathcal{F}$ is counted once on the right: a set avoiding $x$ lands in ${\mathcal{F}}_0$; a set $A\ni x$ contributes to ${\mathcal{F}}_1$ exactly when its partner $A\setminus \{x\}$ is in $\mathcal{F}$, and otherwise it is the unique set restricting to $A\setminus \{x\}$ and is counted within ${\mathcal{F}}_0$'s tally of distinct $C^{\prime }$-traces. A direct count gives $|\mathcal{F}|=|{\mathcal{F}}_0|+|{\mathcal{F}}_1|$, where ${\mathcal{F}}_0$ is now read as a family of subsets of $C^{\prime }$.

Apply the inductive hypothesis to each. Any $B\subseteq C^{\prime }$ shattered by ${\mathcal{F}}_0$ is shattered by $\mathcal{F}$ (it avoids $x$, and traces on $C^{\prime }$ within ${\mathcal{F}}_0$ are traces of $\mathcal{F}$), so the shattered sets of ${\mathcal{F}}_0$ are shattered sets of $\mathcal{F}$. For ${\mathcal{F}}_1$: if $B\subseteq C^{\prime }$ is shattered by ${\mathcal{F}}_1$, then $B\cup \{x\}$ is shattered by $\mathcal{F}$. Indeed every subset of $B$ is $A\cap B$ for some $A\in {\mathcal{F}}_1$, which means both $A$ and $A\cup \{x\}$ lie in $\mathcal{F}$; so every subset of $B\cup \{x\}$ — whether or not it contains $x$ — is realised as an intersection with $\mathcal{F}$. Thus each set shattered by ${\mathcal{F}}_1$ yields, by adjoining $x$, a distinct set shattered by $\mathcal{F}$, none of which is counted among the shattered sets of ${\mathcal{F}}_0$ (those omit $x$). Therefore

$$|\mathcal{F}|=|{\mathcal{F}}_0|+|{\mathcal{F}}_1|\le \#\{\text{shattered by }{\mathcal{F}}_0\}+\#\{\text{shattered by }{\mathcal{F}}_1\}\le \#\{\text{shattered by }\mathcal{F}\},$$

completing the induction and the claim.

For the closed form, assume $1\le d\le m$ and use ${\sum }_{i=0}^d\left(\genfrac{}{}{0ex}{}{m}{i}\right)\le {\sum }_{i=0}^d\left(\genfrac{}{}{0ex}{}{m}{i}\right)(m/d{)}^{d-i}\le (m/d{)}^d{\sum }_{i=0}^m\left(\genfrac{}{}{0ex}{}{m}{i}\right)(d/m{)}^i=(m/d{)}^d(1+d/m{)}^m\le (m/d{)}^d{e}^d=(em/d{)}^d$, where the first inequality uses $(m/d{)}^{d-i}\ge 1$ and the last uses $(1+t{)}^m\le e^{tm}$ with $t=d/m$. $\square$

Bridge. The Sauer-Shelah lemma is the foundational reason an infinite class can still learn: it converts the abstract finiteness of the VC dimension into the concrete polynomial bound ${\Pi }_{\mathcal{H}}(m)=O(m^d)$ that the growth-function uniform-convergence estimate of 45.07.02 demands, since $\log {\Pi }_{\mathcal{H}}(m)=O(d\log m)$ is sublinear precisely when $d<\infty$. This is exactly the replacement of the union-bound factor $|\mathcal{H}|$ by an effective, sample-dependent count, and the bridge is the lemma's degree-$d$ polynomial standing in for the cardinality. It builds toward the fundamental theorem of statistical learning in 45.07.04, where finite VC dimension, the uniform-convergence property, and agnostic-PAC learnability are shown equivalent, the central insight being that the entire learnability question reduces to whether this growth count is polynomial or exponential. The same bound appears again in the empirical-process route to the VC-Donsker theorem, where Sauer-Shelah controls the metric entropy of a VC class; putting these together, the combinatorics proved here generalises the finite-class union bound into the master complexity measure of the subject.

Exercises Intermediate+

Advanced results Master

The Sauer-Shelah bound is the hinge between three developments: the sharper trace-counting form that proves the lemma, the polynomial-versus-exponential dichotomy that the lemma forces on every class, and the passage from this combinatorics into the uniform-convergence machinery that closes the subject.

Theorem 1 (Pajor / sharp trace form). For any family $\mathcal{F}\subseteq 2^{[m]}$,

$$|\mathcal{F}|\le |\{B\subseteq [m]:B\text{ is shattered by }\mathcal{F}\}|,$$

where $B$ is shattered by $\mathcal{F}$ if $\{A\cap B:A\in \mathcal{F}\}=2^B$. The Sauer-Shelah lemma is the corollary obtained by capping the size of shattered sets at $d=\mathrm{VCdim}$: the right side is then at most ${\sum }_{i=0}^d\left(\genfrac{}{}{0ex}{}{m}{i}\right)$ ^{[Bollobás 1986]}. This trace form is strictly stronger than the cardinality statement, since it bounds $|\mathcal{F}|$ by the actual count of shattered subsets rather than by the worst-case maximum, and it is the version the down-shifting proof establishes directly.

Theorem 2 (down-shifting / compression proof). For $x\in [m]$ define the operator $S_x$ on a family $\mathcal{F}\subseteq 2^{[m]}$ by

$$S_x(A)=\{\begin{array}{ll}A\setminus \{x\}& \text{if }x\in A\text{ and }A\setminus \{x\}\notin \mathcal{F},\\ A& \text{otherwise,}\end{array}$$

and $S_x(\mathcal{F})=\{S_x(A):A\in \mathcal{F}\}$. Then $|S_x(\mathcal{F})|=|\mathcal{F}|$ (the map is injective on $\mathcal{F}$), and the family of sets shattered by $S_x(\mathcal{F})$ is contained in that shattered by $\mathcal{F}$. Iterating over all $x$ produces a family ${\mathcal{F}}^{\downarrow }$ that is a down-set (closed under taking subsets) with the same cardinality and no larger shattered-set family. For a down-set, the shattered sets are exactly its own members, so $|{\mathcal{F}}^{\downarrow }|$ equals the number of sets it shatters, and the trace bound is immediate ^{[Bollobás 1986]}. The compression argument is the cleanest route to the lemma and the one closest to a Lean formalisation, since each step is a finite cardinality-preserving rewrite.

Theorem 3 (the polynomial-exponential dichotomy). For any class $\mathcal{H}$, the growth function satisfies exactly one of:

$${\Pi }_{\mathcal{H}}(m)=2^m\text{ for all }m\text{(if }\mathrm{VCdim}(\mathcal{H})=\infty \text{)},{\Pi }_{\mathcal{H}}(m)\le (em/d{)}^d=O(m^d)\text{ for }m\ge d\text{(if }\mathrm{VCdim}(\mathcal{H})=d<\infty \text{)}.$$

There is no intermediate growth rate: a growth function is either identically exponential or eventually polynomial, with the polynomial degree equal to the VC dimension. The dichotomy is a structural consequence of Sauer-Shelah — finiteness of $d$ caps the degree, while infinite VC dimension means every $m$-set is shattered, so ${\Pi }_{\mathcal{H}}(m)=2^m$ identically ^{[Shalev-Shwartz Ben-David 2014]}. This is the combinatorial reason learnability is a zero-one phenomenon rather than a matter of degree.

Theorem 4 (from Sauer-Shelah to uniform convergence). Substituting the polynomial growth bound into the symmetrised tail estimate of 45.07.02, for $0$–$1$ loss and a class of VC dimension $d$,

$$\underset{S\sim {\mathcal{D}}^m}{\mathrm{Pr}}[\underset{h\in \mathcal{H}}{\sup }|L_S(h)-L_{\mathcal{D}}(h)|>\epsilon ]\le 4{\Pi }_{\mathcal{H}}(2m)e^{-m{\epsilon }^2/8}\le 4(2em/d{)}^d{e}^{-m{\epsilon }^2/8},$$

whose right side vanishes as $m\to \infty$ for every fixed $\epsilon$ precisely because $d\log m$ is sublinear. Hence finite VC dimension implies the uniform-convergence property, and the sample complexity is $m_{\mathcal{H}}^{\mathrm{UC}}(\epsilon ,\delta )=O((d\log (d/\epsilon )+\log (1/\delta ))/{\epsilon }^2)$ ^{[Mohri Rostamizadeh Talwalkar 2018]}. This is the implication that lets the entire learnability theory of 45.07.02 apply verbatim to infinite classes, with ${\Pi }_{\mathcal{H}}(2m)$ in the role the cardinality $|\mathcal{H}|$ played for finite classes.

Synthesis. The foundational reason an infinite class can learn is the single combinatorial fact that finite VC dimension forces polynomial growth, and every result here is a reading of that fact through a different lens. This is exactly the trace-counting bound $|\mathcal{F}|\le \#\{\text{shattered sets}\}$, which the down-shifting compression proves directly and which generalises the crude ${\sum }_{i\le d}\left(\genfrac{}{}{0ex}{}{m}{i}\right)$ count by replacing the worst case with the actual shattered family. The polynomial-exponential dichotomy is dual to the No-Free-Lunch picture of 45.07.02: infinite VC dimension means every $m$-set is shattered, so the class realises all labelings and the averaging adversary defeats every learner, while finite VC dimension caps the labeling count and revives uniform convergence — putting these together, learnability is a zero-one property governed by one integer. The central insight is that the cardinality $|\mathcal{H}|$ of the finite-class union bound is the wrong complexity measure and must be replaced by the growth function, whose logarithm Sauer-Shelah pins at $O(d\log m)$; the bridge upward at every level is the same substitution, and it is what makes the fundamental theorem of statistical learning in 45.07.04 possible — uniform convergence, agnostic learnability, and finite VC dimension all coincide because the growth function mediates between the analytic concentration and the combinatorial count.

Full proof set Master

Proposition 1 (shattering and the growth function). For every class $\mathcal{H}$ and every $m$, ${\Pi }_{\mathcal{H}}(m)=2^m$ if and only if some $m$-point set is shattered; consequently $\mathrm{VCdim}(\mathcal{H})=\max \{m:{\Pi }_{\mathcal{H}}(m)=2^m\}$ (with the convention $\max \varnothing =0$, and $\infty$ if the set is unbounded).

Proof. If some $m$-set $C$ is shattered then $|{\mathcal{H}}_C|=2^m$, so the maximum ${\Pi }_{\mathcal{H}}(m)\ge 2^m$; combined with the universal bound ${\Pi }_{\mathcal{H}}(m)\le 2^m$ this gives equality. Conversely if ${\Pi }_{\mathcal{H}}(m)=2^m$ then the maximising $m$-set $C$ has $|{\mathcal{H}}_C|=2^m=|\{0,1{\}}^m|$, and since ${\mathcal{H}}_C\subseteq \{0,1{\}}^m$ this forces ${\mathcal{H}}_C=\{0,1{\}}^m$, i.e. $C$ is shattered. The VC dimension, the largest size of a shattered set, is therefore the largest $m$ with ${\Pi }_{\mathcal{H}}(m)=2^m$. $\square$

Proposition 2 (Sauer-Shelah, trace form). For any finite ground set $C$ with $|C|=m$ and any $\mathcal{F}\subseteq 2^C$, $|\mathcal{F}|\le \#\{B\subseteq C:B\text{ shattered by }\mathcal{F}\}$.

Proof. Induct on $m$. For $m=0$, $\mathcal{F}\subseteq \{\varnothing \}$; if $\mathcal{F}=\{\varnothing \}$ then $\varnothing$ is shattered (its only subset $\varnothing$ equals $\varnothing \cap \varnothing$) and both sides are $1$, and if $\mathcal{F}=\varnothing$ both sides are $0$. For the step pick $x\in C$, $C^{\prime }=C\setminus \{x\}$, and set ${\mathcal{F}}_0=\{A\in \mathcal{F}:x\notin A\}$ and ${\mathcal{F}}_1=\{A\setminus \{x\}:A\in \mathcal{F},x\in A,A\setminus \{x\}\in {\mathcal{F}}_0\}$, both viewed in $2^{C^{\prime }}$. The trace map $A\mapsto A\setminus \{x\}$ sends $\mathcal{F}$ onto the $C^{\prime }$-traces; a $C^{\prime }$-trace $A^{\prime }$ has either one preimage (only $A^{\prime }$, or only $A^{\prime }\cup \{x\}$, lies in $\mathcal{F}$) contributing $1$ to $|{\mathcal{F}}_0|$, or two preimages ($A^{\prime }$ and $A^{\prime }\cup \{x\}$ both in $\mathcal{F}$) contributing $1$ to $|{\mathcal{F}}_0|$ and $1$ to $|{\mathcal{F}}_1|$. Hence $|\mathcal{F}|=|{\mathcal{F}}_0|+|{\mathcal{F}}_1|$. By induction $|{\mathcal{F}}_0|\le \#\{B\subseteq C^{\prime }:B\text{ shattered by }{\mathcal{F}}_0\}$ and $|{\mathcal{F}}_1|\le \#\{B\subseteq C^{\prime }:B\text{ shattered by }{\mathcal{F}}_1\}$. Each $B$ shattered by ${\mathcal{F}}_0$ is shattered by $\mathcal{F}$ and omits $x$. Each $B$ shattered by ${\mathcal{F}}_1$ gives $B\cup \{x\}$ shattered by $\mathcal{F}$: a subset $T\subseteq B$ is $A^{\prime }\cap B$ for some $A^{\prime }\in {\mathcal{F}}_1$ with $A^{\prime },A^{\prime }\cup \{x\}\in \mathcal{F}$, so $T=(A^{\prime }\cap (B\cup \{x\}))$ and $T\cup \{x\}=(A^{\prime }\cup \{x\})\cap (B\cup \{x\})$ both arise. The two families of shattered sets — those omitting $x$ from ${\mathcal{F}}_0$, those containing $x$ from ${\mathcal{F}}_1$ — are disjoint and both consist of sets shattered by $\mathcal{F}$, so their counts add to at most $\#\{B\subseteq C:B\text{ shattered by }\mathcal{F}\}$. $\square$

Proposition 3 (Sauer-Shelah, cardinality form and closed form). If $\mathrm{VCdim}(\mathcal{H})=d<\infty$ then ${\Pi }_{\mathcal{H}}(m)\le {\sum }_{i=0}^d\left(\genfrac{}{}{0ex}{}{m}{i}\right)$ for all $m$, and ${\Pi }_{\mathcal{H}}(m)\le (em/d{)}^d$ for $m\ge d\ge 1$.

Proof. Fix an $m$-set $C$ and let $\mathcal{F}={\mathcal{H}}_C\subseteq 2^C$. A set shattered by $\mathcal{F}$ is shattered by $\mathcal{H}$, hence has size $\le d$. By Proposition 2, $|{\mathcal{H}}_C|=|\mathcal{F}|\le \#\{\text{shattered }B\}\le \#\{B\subseteq C:|B|\le d\}={\sum }_{i=0}^d\left(\genfrac{}{}{0ex}{}{m}{i}\right)$. Maximising over $C$ gives the growth-function bound. For the closed form with $1\le d\le m$, multiply termwise by $(m/d{)}^{d-i}\ge 1$:

$$\sum _{i=0}^d\left(\genfrac{}{}{0ex}{}{m}{i}\right)\le \sum _{i=0}^d\left(\genfrac{}{}{0ex}{}{m}{i}\right)(\frac{m}{d}{)}^{d-i}\le (\frac{m}{d}{)}^d\sum _{i=0}^m\left(\genfrac{}{}{0ex}{}{m}{i}\right)(\frac{d}{m}{)}^i=(\frac{m}{d}{)}^d(1+\frac{d}{m}{)}^m\le (\frac{m}{d}{)}^d{e}^d=(\frac{em}{d}{)}^d,$$

where the binomial theorem evaluates the sum and $(1+d/m{)}^m\le e^d$ uses $1+t\le e^t$. $\square$

Proposition 4 (VC dimension of halfspaces is $d+1$). The class of halfspaces $\{x\mapsto 1[⟨w,x⟩+b\ge 0]:w\in {\mathbb{R}}^d,b\in \mathbb{R}\}$ on ${\mathbb{R}}^d$ has VC dimension exactly $d+1$.

Proof. Lower bound: the points $0,e_1,\dots ,e_d$ are shattered. For a target $(y_0,\dots ,y_d)$ put $s_j=2y_j-1$, $b=s_0/2$, $w_j=s_j-b$; then $⟨w,0⟩+b=s_0/2$ has the sign of $s_0$, and $⟨w,e_j⟩+b=w_j+b=s_j$ has the sign of $s_j$, realising the labeling. Upper bound: take any $d+2$ points in ${\mathbb{R}}^d$. By Radon's theorem they split into disjoint sets $X_1,X_2$ whose convex hulls intersect at a point $p={\sum }_{x\in X_1}{\alpha }_{x}x={\sum }_{x\in X_2}{\beta }_{x}x$ with $\alpha ,\beta \ge 0$ summing to $1$. The labeling assigning $1$ to $X_1$ and $0$ to $X_2$ is unrealisable: a halfspace containing $X_1$ contains the convex combination $p$, and a complementary halfspace excluding $X_2$ excludes $p$, contradiction. So no $(d+2)$-set is shattered and $\mathrm{VCdim}=d+1$. $\square$

Proposition 5 (finite VC dimension implies sublinear log-growth). If $\mathrm{VCdim}(\mathcal{H})=d<\infty$ then ${\log }_2{\Pi }_{\mathcal{H}}(m)=O(d\log m)$, and consequently ${\log }_2{\Pi }_{\mathcal{H}}(m)/m\to 0$.

Proof. By Proposition 3, for $m\ge d\ge 1$, ${\Pi }_{\mathcal{H}}(m)\le (em/d{)}^d$, so ${\log }_2{\Pi }_{\mathcal{H}}(m)\le d{\log }_2(em/d)=d({\log }_{2}e+{\log }_{2}m-{\log }_{2}d)=O(d\log m)$. Dividing by $m$, ${\log }_2{\Pi }_{\mathcal{H}}(m)/m\le d{\log }_2(em/d)/m\to 0$ as $m\to \infty$ since $\log m/m\to 0$. The case $d=0$ gives ${\Pi }_{\mathcal{H}}(m)=1$, for which the bound is immediate. $\square$

Connections Master

This unit completes the infinite-class program opened in 45.07.02: there the growth function ${\Pi }_{\mathcal{H}}(m)$ and the VC dimension are introduced as the quantities that replace the cardinality $|\mathcal{H}|$ in the union bound, and the Sauer-Shelah lemma proved here supplies the missing combinatorial fact — that finite VC dimension forces ${\Pi }_{\mathcal{H}}(m)=O(m^d)$ — which makes the symmetrised uniform-convergence estimate vanish. The bias-complexity and No-Free-Lunch results of that unit are the analytic and adversarial faces of the dichotomy proved here.

The destination is the fundamental theorem of statistical learning in 45.07.04: the polynomial growth bound is exactly the input that closes the equivalence of finite VC dimension, the uniform-convergence property, agnostic-PAC learnability, and ERM-learnability for binary classification. This unit is the combinatorial half of that theorem; the No-Free-Lunch lower bound of 45.07.02 supplies the converse, that infinite VC dimension defeats every learner.

The same VC-dimension and growth-function machinery powers the empirical-process theory of 45.05.03: a VC class of functions with square-integrable envelope is $P$-Donsker for every $P$, because Sauer-Shelah controls the uniform metric entropy ${\sup }_{Q}N(\epsilon ,\mathcal{F},L^2(Q))$ by a power of $1/\epsilon$, whose square-rooted logarithm integrates near zero. The Glivenko-Cantelli unit [45.07.02 prerequisite chain] already proves the set-system form of Sauer-Shelah as a tool for distribution-free uniform laws of large numbers; this unit develops the hypothesis-class form and its consequences as a first-class object.

The proof technique is the probabilistic-method and counting toolkit of 40.07.01: shattering is a statement about the trace of a set system, the down-shifting operator is a compression argument of the kind that pervades extremal set theory, and the closed-form bound $(em/d{)}^d$ is the standard binomial-tail estimate. The lemma is one of the rare results that is simultaneously a cornerstone of learning theory and a clean theorem of finite combinatorics, rediscovered independently from both directions.

Historical & philosophical context Master

The capacity measure now called VC dimension was introduced by Vladimir Vapnik and Alexey Chervonenkis in their 1971 paper on the uniform convergence of relative frequencies, where the growth function (which they called the index or entropy of a system of events) and its polynomial bound appear as the engine of the first distribution-free generalization guarantee ^{[Vapnik Chervonenkis 1971]}. Their motivation was statistical: to determine when empirical frequencies converge to probabilities uniformly over an infinite family of events, the cardinality of the family being the wrong measure.

The combinatorial lemma at the centre of this unit was proved independently and almost simultaneously around 1972 by Norbert Sauer and by Saharon Shelah (the latter attributing the result also to Micha Perles), and is implicit in the 1971 Vapnik-Chervonenkis bound; it is for this reason often called the Sauer-Shelah-Perles lemma or the Vapnik-Chervonenkis-Sauer-Shelah lemma ^{[Bollobás 1986]}. Shelah's interest came from model theory, where the same dichotomy underlies the notion of a stable or NIP (non-independence-property) theory; Sauer's was purely combinatorial. The down-shifting proof given in the Full proof set is the form developed in the extremal-set-theory tradition and recorded by Bollobás. The textbook synthesis with PAC learning, organizing the lemma around shattering and the growth function as the route to the fundamental theorem, is due to Shalev-Shwartz and Ben-David (2014) and Mohri, Rostamizadeh and Talwalkar (2018).

Bibliography Master

@article{vapnikchervonenkis1971,
  author  = {Vapnik, Vladimir N. and Chervonenkis, Alexey Ya.},
  title   = {On the uniform convergence of relative frequencies of events to their probabilities},
  journal = {Theory of Probability and Its Applications},
  volume  = {16},
  number  = {2},
  pages   = {264--280},
  year    = {1971}
}

@article{sauer1972,
  author  = {Sauer, Norbert},
  title   = {On the density of families of sets},
  journal = {Journal of Combinatorial Theory, Series A},
  volume  = {13},
  number  = {1},
  pages   = {145--147},
  year    = {1972}
}

@article{shelah1972,
  author  = {Shelah, Saharon},
  title   = {A combinatorial problem; stability and order for models and theories in infinitary languages},
  journal = {Pacific Journal of Mathematics},
  volume  = {41},
  number  = {1},
  pages   = {247--261},
  year    = {1972}
}

@book{shalevshwartzbendavid2014,
  author    = {Shalev-Shwartz, Shai and Ben-David, Shai},
  title     = {Understanding Machine Learning: From Theory to Algorithms},
  publisher = {Cambridge University Press},
  year      = {2014}
}

@book{mohri2018,
  author    = {Mohri, Mehryar and Rostamizadeh, Afshin and Talwalkar, Ameet},
  title     = {Foundations of Machine Learning},
  edition   = {2},
  publisher = {MIT Press},
  year      = {2018}
}

@book{bollobas1986,
  author    = {Bollob\'{a}s, B\'{e}la},
  title     = {Combinatorics: Set Systems, Hypergraphs, Families of Vectors and Combinatorial Probability},
  publisher = {Cambridge University Press},
  year      = {1986}
}

@book{vapnik1998,
  author    = {Vapnik, Vladimir N.},
  title     = {Statistical Learning Theory},
  publisher = {Wiley-Interscience},
  year      = {1998}
}