Sauer's Lemma

The significance of the lemma is not simply the numerical sum.

Programming

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.

Key point

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?

At most m labelings
Exactly d labelings
All 2^{^m} binary labelings
Only one labeling

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

Definition

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.

How do hypotheses on a finite set of examples induce different binary labelings, and how does shattering determine the number of labelings that can occur?

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

Worked 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?

1
Identify the sample size
The finite set contains 3 examples, so the growth function is being evaluated at m = 3.
2
Identify the VC-dimension restriction
The class has VC dimension at most d = 2.
3
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.
4
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.

Result

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.

What changes in the growth function when the number of examples passes the VC dimension, and how does the bound shift from all possible labelings to polynomially many labelings?

The Lemma's Upper Bound

Definition

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.

Best practice

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

What are the major steps in the lower-bound and upper-bound arguments for the Multiclass Fundamental Theorem, and where do the two routes diverge?

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.

1
For the lower bounds, reduce the multiclass problem to the Binary Fundamental Theorem.
2
For the upper bounds, keep the overall structure of the binary proof.
3
Identify Sauer's Lemma as the binary ingredient that does not transfer directly.
4
Replace Sauer's Lemma with Natarajan's Lemma.
5
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

The two lemmas have different roles in the proof architecture, even though Natarajan's Lemma has the same general proof spirit as Sauer's Lemma.

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

Common mistake
Treating the size of the hypothesis class as the growth function
What it looks like
A class may contain many hypotheses, but several hypotheses can induce the same binary function on a selected finite set.
Why it fails
The growth function counts distinct functions induced on the finite set and then maximizes that count over sets of the given size.
Do this instead
Count effective labelings on the examples, not hypotheses in the class.
Common mistake
Assuming that a VC dimension of d gives all 2^{^m} labelings for every m
What it looks like
The full 2^m count is guaranteed when the selected set is shattered; a VC-dimension restriction prevents shattering once the sample size exceeds d.
Why it fails
Shattering and the VC-dimension threshold determine when all binary labelings can occur.
Do this instead
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.
Common mistake
Claiming that the Sauer bound is always attained
What it looks like
The upper bound of 7 for VC dimension at most 2 and 3 examples does not assert that every such class realizes exactly 7 functions.
Why it fails
Sauer's Lemma gives an upper bound on the growth function.
Do this instead
Use language such as at most or bounded above by unless equality has been established separately.
Common mistake
Using Sauer's Lemma unchanged in the multiclass upper-bound proof
What it looks like
The multiclass proof follows the binary strategy but replaces Sauer's Lemma.
Why it fails
The source identifies Sauer's Lemma as the binary ingredient that must be changed.
Do this instead
Use Natarajan's Lemma as the multiclass replacement.

Check Your Understanding

MEDIUM

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.

Your attempt (not saved)

Worked example

Proof-Route Recall

Match each task with the correct proof ingredient: obtaining lower bounds, or obtaining upper bounds.

1
Lower bounds
Use a reduction from the multiclass problem to the Binary Fundamental Theorem.
2
Upper bounds
Follow the general binary proof strategy, but replace Sauer's Lemma with Natarajan's Lemma.

Result

The lower-bound route is a binary reduction; the upper-bound route is a binary-style argument with a multiclass counting replacement.

Key Takeaways

1
The growth function is the maximum number of distinct binary functions induced by a hypothesis class on any finite set of a specified size.
2
Shattering means that every one of the 2^m binary labelings on a set of m examples is induced by the class.
3
Sauer's Lemma converts a VC-dimension restriction into a binomial-coefficient upper bound on the growth function.
4
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.
5
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.

At a glance

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.

Related concepts

More concepts starting with S