Uniform Convergence
The growth function measures the maximal effective size of a hypothesis class on finite sets of examples.
Why Effective Size Matters
A hypothesis class can contain many hypotheses, but that total count does not always describe how expressive the class is on a particular set of examples. Uniform convergence studies this effective expressiveness by restricting the class to finite sets of instances and counting the different binary labelings that the hypotheses can produce there.
The central question is not only how many hypotheses exist, but how many distinct labelings they can induce on a finite sample.
Counting Induced Labelings
Take a set of m instances and restrict every hypothesis in the class to those instances. Each restricted hypothesis produces a binary labeling of the set. Some different hypotheses may produce the same labeling, so the relevant count is the number of distinct binary functions induced on that particular set.
The growth function, written as τH(m), is the largest number of distinct binary labelings that the hypothesis class H can induce on any set of m instances.
The word largest is essential. Different sets of m instances may allow different numbers of induced labelings. The growth function chooses the maximum count achievable over all sets of that size.
Shattering Every Pattern
A set of m instances is shattered by a hypothesis class when the class induces every possible binary labeling on that set. Since each of the m instances can receive either of two labels, there are 2^m possible binary labelings. Therefore, a shattered set has all 2^m labelings represented.
A Shattered Three-Instance Set
Suppose a hypothesis class shatters a set containing three instances. How many distinct binary labelings must the class induce on that set?
Count the instances: The set contains m = 3 instances.
Count all binary patterns: Each instance has two possible labels, so the total number of binary labelings is 2^3.
Use the definition of shattering: Because the set is shattered, every one of those binary labelings is induced by some hypothesis in the class.
The class induces all 8 possible binary labelings on the shattered set.
Shattering gives the maximum possible count on a set of m instances: all 2^m binary labelings occur.
The VC Dimension Threshold
The VC dimension of a hypothesis class is the size of its largest shattered set. If the VC dimension is d, then every number of examples m up to d is within the range where all 2^m labelings can be possible on a suitable shattered set.
This creates a threshold. Before the number of examples exceeds d, shattering can support exponential behavior: the growth function can reach 2^m. Once m is greater than d, the class cannot shatter an m-instance set. The growth function is then restricted to fewer than all possible binary labelings, and Sauer's Lemma gives a polynomially bounded upper bound.
Sauer's Polynomial Bound
Sauer's Lemma states that if VCdim(H) is at most d, then the growth function is bounded by the sum of the binomial coefficients from index 0 through d: τH(m) ≤ Σ from i = 0 to d of C(m, i).
The bound is especially useful when m exceeds d. The unrestricted number of binary labelings is 2^m, which grows exponentially with m. Sauer's Lemma replaces that unrestricted upper bound with a sum whose highest index is fixed by the VC dimension. For a fixed d, this sum is polynomially bounded as m increases.
Applying Sauer's Lemma
Assume VCdim(H) is at most 2 and consider m = 3 examples. What upper bound does Sauer's Lemma give?
Substitute the VC dimension: Use d = 2 in the sum of binomial coefficients.
Substitute the sample size: Use m = 3, giving C(3, 0) + C(3, 1) + C(3, 2).
Evaluate the sum: The terms are 1, 3, and 3, so the total is 7.
τH(3) ≤ 7.
From Labelings to Uniform Convergence
Uniform convergence concerns controlling the difference between empirical error and true error for every hypothesis at once. The growth function helps with this analysis because it measures how many distinct behaviors the class can display on a finite sample. A class with fewer effective labelings has fewer distinct sample behaviors to control than its raw number of hypotheses might suggest.
The important chain of ideas is: restrict the class to a finite sample, count the distinct induced labelings, use the VC dimension to identify when full shattering stops, and apply Sauer's Lemma to obtain a polynomially bounded count after that point.
Common Counting Mistakes
Counting hypotheses instead of distinct induced labelings.
Different hypotheses can produce the same binary function on a particular finite set of instances.
Fix:
Restrict the hypotheses to the set and count the distinct labelings they induce.Forgetting that the growth function takes a maximum over sets.
Different sets of m instances may permit different numbers of induced functions.
Fix:
Use the largest count achievable over all sets of m instances.Assuming that a VC dimension of d means the growth function equals 2^m for every m.
A VC dimension of d identifies the largest shattered-set size; after m exceeds d, full shattering is no longer available.
Fix:
Use the exponential possibility up to the VC-dimension threshold and Sauer's Lemma for the larger-sample regime.Treating Sauer's upper bound as an exact count.
Sauer's Lemma gives an upper bound, not a claim that every set realizes that many labelings.
Fix:
Write τH(3) ≤ 7 and interpret 7 as a ceiling.
Check Your Understanding
A hypothesis class has VC dimension at most 2. For a set of 3 instances, answer the following: What is the largest possible number of binary labelings before applying Sauer's Lemma? What upper bound does Sauer's Lemma provide? Why are these two numbers different?
Hints
- There are 2^m possible binary labelings on m instances.
- Use the terms in the Sauer sum from i = 0 through d.
- The VC dimension prevents shattering once m exceeds d.
What do you think happens?
If a hypothesis class has VC dimension at most 2 and you examine 3 instances, which upper bound should you use for the growth function?
Reveal answer
Answer: 7
Sauer's Lemma gives τH(3) ≤ C(3, 0) + C(3, 1) + C(3, 2) = 1 + 3 + 3 = 7. The value 8 is the unrestricted count 2^3, but a class with VC dimension at most 2 cannot shatter a set of 3 instances.
Key Takeaways
- The growth function τH(m) is the maximum number of distinct binary labelings that H can induce on any set of m instances.
- A set is shattered when every one of its 2^m binary labelings is induced by the hypothesis class.
- The VC dimension is the size of the largest shattered set and marks the transition point in the growth function.
- Sauer's Lemma bounds the growth function by a sum of binomial coefficients when VCdim(H) is at most d.
- After the number of examples exceeds the VC dimension, the effective number of labelings is polynomially bounded rather than freely exponential.