Sauer's Lemma
The proof has separate lower-bound and upper-bound routes.
Why Counting Labelings Matters
A hypothesis class may contain many hypotheses, but its total number of hypotheses does not by itself tell us how expressive the class is on a particular collection of examples. A more useful question is: when the class is restricted to a finite set of examples, how many different binary labelings can its hypotheses produce? Sauer's Lemma answers this counting question using the VC dimension.
The central transition is from unrestricted counting to effective counting: we count distinct labelings on a finite example set, not merely the hypotheses that exist in the class.
What do you think happens?
Suppose a set of m examples is shattered. How many binary labelings can the hypothesis class induce on that set?
Reveal answer
Answer: All 2^m binary labelings
Shattering means that every binary labeling on the selected set is induced by some hypothesis in the class.
Finite Sets and Induced Labelings
The growth function measures the maximal effective size of a hypothesis class on finite sets of examples. For a set of m instances, it counts the distinct binary functions that the hypotheses can produce on that set, and then takes the largest such count over all sets of m instances. The maximal aspect matters because different sets of m instances may allow different numbers of induced functions.
Shattering connects a finite set of instances with all possible binary labelings on that set. If a set of m instances is shattered, every one of the 2^m binary functions on the set is induced by the hypothesis class. Thus, shattering identifies the situation in which the effective count reaches the full number of possible binary labelings.
A Counting Example
Three Examples with VC Dimension at Most Two
Consider a hypothesis class whose VC dimension is at most 2. What upper bound does Sauer's Lemma give for the growth function on a set of 3 examples?
Identify the sample size: The finite set contains 3 examples, so the growth function is being evaluated at m = 3.
Identify the VC-dimension restriction: The class has VC dimension at most d = 2.
Apply the binomial-count bound: Sauer's Lemma bounds the growth function by the relevant sum of binomial coefficients through degree 2: 1 + 3 + 3.
Interpret the result: The resulting upper bound is 7 induced binary functions on the selected set. This is an upper bound on the growth function, not a claim that every such class realizes exactly 7 functions on every set of 3 examples.
The growth function is bounded above by 7 for this setting.
Before the number of examples exceeds the VC dimension, a shattered set can support all 2^m binary labelings. Once the number of examples is beyond the VC dimension, the class cannot shatter sets of that size. Sauer's Lemma then bounds the growth function by a sum of binomial coefficients, producing polynomially bounded behavior rather than the full exponential count of all binary labelings.
The Lemma's Upper Bound
Sauer's Lemma states that when VCdim(H) is at most d, the growth function is bounded by a sum of binomial coefficients. In the usual notation, the bound counts the terms through degree d: the number of induced binary labelings is no larger than the sum of the binomial coefficients from level 0 through level d.
The significance of the lemma is not simply the numerical sum. It converts a structural restriction, namely a bounded VC dimension, into a limit on effective expressiveness over finite sets. A class may contain many hypotheses, but after the sample size exceeds the VC dimension, its distinct labelings on a set cannot continue to grow like the full collection of 2^m binary labelings. The binomial-coefficient bound gives polynomially bounded growth instead.
When interpreting Sauer's Lemma, always identify three quantities separately: the sample size m, the VC-dimension bound d, and the number of distinct induced binary functions. Confusing the number of hypotheses with the number of induced functions is the main way to lose the meaning of the growth-function bound.
Two Routes in the Multiclass Proof
The proof of the Multiclass Fundamental Theorem, stated as Theorem 29.3 in the source material, divides naturally into two routes. The lower bounds are obtained by reducing the multiclass problem to the Binary Fundamental Theorem. The upper bounds retain the general strategy of the binary-classification proof, but they cannot retain every ingredient unchanged.
- For the lower bounds, reduce the multiclass problem to the Binary Fundamental Theorem.
- For the upper bounds, keep the overall structure of the binary proof.
- Identify Sauer's Lemma as the binary ingredient that does not transfer directly.
- Replace Sauer's Lemma with Natarajan's Lemma.
- Use that multiclass replacement to complete the upper-bound route.
Sauer and Natarajan Compared
| Ingredient | Role | Where it appears |
|---|---|---|
| Sauer's Lemma | Bounds the growth function using a VC-dimension restriction and a sum of binomial coefficients | Binary setting and the binary proof strategy |
| Natarajan's Lemma | Provides the multiclass replacement for Sauer's Lemma | Upper-bound route of the Multiclass Fundamental Theorem |
Sauer's Lemma is the binary counting tool: it turns a VC-dimension restriction into a bound on the growth function, which counts effective binary labelings. Natarajan's Lemma supplies the corresponding multiclass replacement. Its proof has the same general spirit as Sauer's Lemma, but it is the ingredient needed when the upper-bound argument is applied to the multiclass setting.
Common Counting Mistakes
Treating the size of the hypothesis class as the growth function
The growth function counts distinct functions induced on the finite set and then maximizes that count over sets of the given size.
Fix:
Count effective labelings on the examples, not hypotheses in the class.Assuming that a VC dimension of d gives all 2^m labelings for every m
Shattering and the VC-dimension threshold determine when all binary labelings can occur.
Fix:
Separate the regime m ≤ d, where shattering can permit all 2^m labelings, from the regime m > d, where Sauer's Lemma supplies a binomial-sum upper bound.Claiming that the Sauer bound is always attained
Sauer's Lemma gives an upper bound on the growth function.
Fix:
Use language such as at most or bounded above by unless equality has been established separately.Using Sauer's Lemma unchanged in the multiclass upper-bound proof
The source identifies Sauer's Lemma as the binary ingredient that must be changed.
Fix:
Use Natarajan's Lemma as the multiclass replacement.
Check Your Understanding
Explain, in your own words, why a hypothesis class with VC dimension at most d can have exponential behavior in the regime where m does not exceed d, but receives a polynomially bounded growth-function estimate after m exceeds d. Then describe which lemma replaces Sauer's Lemma in the upper-bound route of the Multiclass Fundamental Theorem.
Hints
- Start with what shattering means for a set of m examples.
- Compare the count of all binary labelings with the binomial-coefficient bound.
- For the multiclass proof, distinguish preserving the binary strategy from preserving every binary ingredient.
Proof-Route Recall
Match each task with the correct proof ingredient: obtaining lower bounds, or obtaining upper bounds.
Lower bounds: Use a reduction from the multiclass problem to the Binary Fundamental Theorem.
Upper bounds: Follow the general binary proof strategy, but replace Sauer's Lemma with Natarajan's Lemma.
The lower-bound route is a binary reduction; the upper-bound route is a binary-style argument with a multiclass counting replacement.
Key Takeaways
- The growth function is the maximum number of distinct binary functions induced by a hypothesis class on any finite set of a specified size.
- Shattering means that every one of the 2^m binary labelings on a set of m examples is induced by the class.
- Sauer's Lemma converts a VC-dimension restriction into a binomial-coefficient upper bound on the growth function.
- After the number of examples exceeds the VC dimension, the growth function is polynomially bounded rather than equal to the full exponential count of all binary labelings.
- In the Multiclass Fundamental Theorem, lower bounds come from reducing to the Binary Fundamental Theorem, while upper bounds follow the binary strategy with Natarajan's Lemma replacing Sauer's Lemma.
Key Takeaways
- The growth function measures the maximum number of distinct labelings a hypothesis class can induce on finite example sets.
- Shattering gives all 2^m binary labelings on a set of m examples.
- Sauer's Lemma bounds the growth function by a sum of binomial coefficients when the VC dimension is at most d.
- This changes the effective growth from exponential behavior to polynomially bounded behavior once the sample size exceeds the VC dimension.
- The Multiclass Fundamental Theorem uses a binary reduction for lower bounds and replaces Sauer's Lemma with Natarajan's Lemma for upper bounds.