The Sauer–Shelah Lemma and Its Proof

Why Count Sample Labelings?

A class of binary-valued rules may be infinite, yet on a fixed finite sample it can produce only finitely many different labelings. The number of those labelings measures how flexibly the class can fit the sample. VC dimension constrains this number: even when a class is infinite, a finite VC dimension prevents its sample labelings from growing as fast as all possible binary patterns.

The Sauer–Shelah lemma makes that statement precise. Its proof is a combinatorial argument: separate labelings according to their value at one coordinate, then track how much shattering capacity remains when both values are possible there.

Traces and the Growth Function

Let \(\mathcal H\) be a nonempty class of functions \(h:\mathcal X\to\{0,1\}\). Given points \(x_1,\ldots,x_m\), a labeling produced by \(\mathcal H\) is the vector \((h(x_1),\ldots,h(x_m))\) for some \(h\in\mathcal H\). The points need not be distinct. We count distinct vectors, not the number of functions that produce them.

Definition: A finite set \(S\subseteq\mathcal X\) is shattered by \(\mathcal H\) if every function from \(S\) to \(\{0,1\}\) is the restriction to \(S\) of some member of \(\mathcal H\). The VC dimension of \(\mathcal H\), denoted \(V\), is the largest cardinality of a set shattered by \(\mathcal H\), or infinity if sets of arbitrarily large finite cardinality are shattered. The growth function is \[ \Pi_{\mathcal H}(m)=\sup_{x_1,\ldots,x_m\in\mathcal X} \left|\{(h(x_1),\ldots,h(x_m)):h\in\mathcal H\}\right|. \]

For a fixed sample, each labeling can also be represented by the subset of coordinate indices labeled 1. Thus the labelings form a family of subsets of \(\{1,\ldots,m\}\). This representation lets us prove a finite combinatorial statement and then apply it to every sample.

Worked Example: A Class of Singletons

Let \(\mathcal X=\{a,b,c,d\}\), and let \(\mathcal H\) consist of the indicator functions of the four singleton sets \(\{a\},\{b\},\{c\},\{d\}\). On the four-point sample \((a,b,c,d)\), the possible sets of coordinates labeled 1 are exactly \(\{1\},\{2\},\{3\},\{4\}\), so there are four distinct labelings.

The VC dimension is 1. Any one point is shattered: the singleton set containing that point labels it 1, and the singleton set containing a different point labels it 0. No pair is shattered, because no member of the class labels both points 1. Therefore the Sauer–Shelah sum is \(\binom{4}{0}+\binom{4}{1}=1+4=5\), which bounds the actual count of 4.

The Sauer–Shelah Lemma

Theorem (Sauer–Shelah lemma): If a class \(\mathcal H\) has finite VC dimension \(V\), then for every integer \(m\geq 0\), \[ \Pi_{\mathcal H}(m)\leq \sum_{j=0}^{V}\binom{m}{j}, \] where \(\binom{m}{j}=0\) when \(j>m\). In particular, if \(V\geq m\), the right-hand side is \(2^m\), the number of all possible binary labelings.

We prove the bound for a family \(\mathcal A\) of subsets of \(\{1,\ldots,m\}\) whose VC dimension is at most \(V\). Here shattering means that all subsets of a coordinate set occur as intersections with members of \(\mathcal A\). Any sample from \(\mathcal H\) gives such a family with VC dimension at most \(V\): a shattered set of coordinate indices cannot contain two indices referring to the same sample point, since inconsistent labels on those indices cannot occur. The remaining indices correspond to distinct points, which would be shattered by \(\mathcal H\).

Proof: We use induction on \(m\). When \(m=0\), there is at most one subset of the empty coordinate set, so the claimed bound is 1. For any \(m\), if \(V=0\), the family has at most one member: two distinct members would differ at some coordinate, and their restrictions would realize both labels there, shattering a singleton. The claimed sum is then \(\binom{m}{0}=1\). If \(V\geq m\), the family has at most \(2^m=\sum_{j=0}^{V}\binom{m}{j}\) members.

It remains to consider \(1\leq V<m\). For each \(B\subseteq\{1,\ldots,m-1\}\), define \[ \mathcal A_0=\{B:B\in\mathcal A\},\qquad \mathcal A_1=\{B:B\cup\{m\}\in\mathcal A\}. \] These are families on the first \(m-1\) coordinates. Each member of \(\mathcal A\) either omits \(m\), contributing to \(\mathcal A_0\), or includes \(m\), contributing to \(\mathcal A_1\); a subset \(B\) belongs to both families exactly when both corresponding members of \(\mathcal A\) occur. Hence \[ |\mathcal A|=|\mathcal A_0\cup\mathcal A_1|+|\mathcal A_0\cap\mathcal A_1|. \] The union \(\mathcal A_0\cup\mathcal A_1\) has VC dimension at most \(V\), since any coordinate set it shatters is also shattered by \(\mathcal A\). The intersection \(\mathcal A_0\cap\mathcal A_1\) has VC dimension at most \(V-1\): if it shattered a set \(I\) of \(V\) coordinates, then for every labeling on \(I\), a member of the intersection would provide that labeling both with coordinate \(m\) absent and with it present. Thus \(\mathcal A\) would shatter \(I\cup\{m\}\), contradicting its VC dimension being at most \(V\).

The induction hypothesis now gives \[ |\mathcal A| \leq \sum_{j=0}^{V}\binom{m-1}{j} +\sum_{j=0}^{V-1}\binom{m-1}{j} =\sum_{j=0}^{V}\binom{m}{j}, \] where the last equality follows from Pascal’s identity \(\binom{m}{j}=\binom{m-1}{j}+\binom{m-1}{j-1}\). This proves the bound for every such family and therefore for every sample from \(\mathcal H\). Taking the supremum over samples proves the theorem. \(\square\)

Worked Example: A Class Attaining the Binomial Sum

On a domain with five points, let \(\mathcal H\) contain the indicator functions of all subsets having at most two elements. Its VC dimension is exactly 2. Every pair is shattered: the empty set gives the pattern \(00\), either singleton gives one of the patterns \(10\) or \(01\), and the pair itself gives \(11\). No three-point set is shattered, because the labeling with all three points equal to 1 would require a subset of size three.

On the five-point domain, the class has \(\binom{5}{0}+\binom{5}{1}+\binom{5}{2}=1+5+10=16\) members, and each produces a different labeling. The Sauer–Shelah bound is also 16, so equality holds in this example.

The Exponential Simplification

The binomial sum is often simplified to a single expression. The following bound is useful when the sample size is at least the VC dimension and the dimension is positive.

Corollary: If \(1\leq V\leq m\), then \[ \sum_{j=0}^{V}\binom{m}{j}\leq\left(\frac{em}{V}\right)^V. \] Consequently, a class with VC dimension \(V\geq1\) satisfies \(\Pi_{\mathcal H}(m)\leq (em/V)^V\) for \(m\geq V\).

Derivation. Set \(x=V/m\), so \(0<x\leq1\). For every \(j\leq V\), \(x^j\geq x^V\). Therefore

\sum_{j=0}^{V}\binom{m}{j} \leq x^{-V}\sum_{j=0}^{V}\binom{m}{j}x^j \leq x^{-V}(1+x)^m.

Since \(1+x\leq e^x\), the last expression is at most \(x^{-V}e^{mx}\). Substituting \(x=V/m\) gives \(x^{-V}=(m/V)^V\) and \(e^{mx}=e^V\). Multiplying these factors yields \((em/V)^V\), as claimed.

Worked Example: Checking the Exponential Bound

Use the class of all subsets of a six-point domain having at most two elements. As in the previous example, its VC dimension is \(V=2\). The number of labelings on all six points is \(\binom{6}{0}+\binom{6}{1}+\binom{6}{2}=1+6+15=22\).

Here \(m=6\) and \(V=2\), so the exponential bound is \[ \left(\frac{em}{V}\right)^V =\left(\frac{6e}{2}\right)^2 =(3e)^2 =9e^2 \approx 66.50. \] Thus \(22\leq66.50\), as required. The exponential bound is valid but substantially looser than the exact binomial-sum bound of 22 in this case.

Edge Cases and a Common Pitfall

The condition \(V\geq1\) matters in the exponential form: when \(V=0\), division by \(V\) is undefined. A nonempty class of VC dimension zero produces at most one labeling on any sample, so the appropriate bound is \(\Pi_{\mathcal H}(m)\leq1\). When \(m<V\), the binomial-sum bound is simply \(2^m\); the stated exponential corollary is intended for \(m\geq V\).

Common mistake: It is tempting to replace the binomial sum by \((em/V)^V\) for every value of \(V\), including zero, or to apply it when \(m<V\) without checking its hypotheses. That substitution is not justified: the expression is undefined for \(V=0\), and the derivation uses \(x=V/m\) with \(0<x\leq1\). Handle dimension zero separately, and verify \(1\leq V\leq m\) before using the exponential bound.

The lemma matters because it turns a dimension statement into a count of possible sample labelings. The bound is uniform over the choice of sample points, and it applies even if the hypothesis class itself is infinite. In particular, for fixed finite \(V\), the binomial sum grows polynomially in \(m\), rather than as \(2^m\). This count is a key input when relating combinatorial complexity to statistical generalization.

Key takeaway: A class of VC dimension \(V\) produces at most \(\sum_{j=0}^{V}\binom{m}{j}\) distinct labelings on \(m\) points. For \(1\leq V\leq m\), this is at most \((em/V)^V\); for \(V=0\), the correct bound is 1.

Check Your Understanding

Answer each question using the definitions and bounds above.

Why does a family of subsets with VC dimension zero have at most one member?
In the proof, why does shattering a \(V\)-coordinate set in \(\mathcal A_0\cap\mathcal A_1\) imply that \(\mathcal A\) shatters a set of size \(V+1\)?
For \(m=5\) and \(V=2\), calculate the Sauer–Shelah binomial-sum bound.
State the conditions needed to use the exponential bound \((em/V)^V\), and explain why \(V=0\) requires separate treatment.
What is the number of distinct labelings produced by all subsets of a six-point domain of size at most two?