Uniform Convergence
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.
Try it: Shattering and VC Dimension
What it means for a hypothesis class to shatter a set of points: all labelings are checked exactly, each realizable one with a witness hypothesis drawn, until the first labeling no hypothesis can produce — linked to the VC dimensions of thresholds (1), intervals (2), halfspaces in the plane (3) and axis-aligned rectangles (4).
How it works
- Pick a hypothesis class and place n points.
- Enumerate all labelings of the points with 0 / 1.
- For each labeling decide exactly whether some hypothesis produces it (thresholds: every 1 left of every 0; intervals: no 0 between the outer 1s; rectangles: no 0 in the bounding box of the 1s; halfspaces: strict linear separability).
- Draw a witness hypothesis for every realizable labeling.
- The set is shattered if every labeling is realized; VCdim is the size of the largest shattered set.
Default run (6 steps): 2 points and the class of intervals on a line (VC dimension 2). Check all 2^2 = 4 labelings: is each one produced by some hypothesis? … All 4 labelings are realized: intervals on a line shatter these 2 points, so VCdim >= 2. Theory: VCdim = 2, so no set of 3 points can be shattered.
Simplified: At most 6 points on a 0–10 board. The lab checks one placement at a time: failing to shatter one set of n points does not by itself show VCdim < n — that needs every placement (the lab states the known VC dimension).
Loading the simulation…
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?
- 1Count the instances
The set contains m = 3 instances.
- 2Count all binary patterns
Each instance has two possible labels, so the total number of binary labelings is 23.
- 3Use 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 2m 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 2m, 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?
- 1Substitute the VC dimension
Use d = 2 in the sum of binomial coefficients.
- 2Substitute the sample size
Use m = 3, giving C(3, 0) + C(3, 1) + C(3, 2).
- 3Evaluate 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
Common mistake Counting hypotheses instead of distinct induced labelings.
What it looks likeTreating the full size of H as the growth function.
Why it failsDifferent hypotheses can produce the same binary function on a particular finite set of instances.
Do this insteadRestrict the hypotheses to the set and count the distinct labelings they induce.
Common mistake Forgetting that the growth function takes a maximum over sets.
What it looks likeCounting labelings on one chosen set of m instances and calling that τH(m).
Why it failsDifferent sets of m instances may permit different numbers of induced functions.
Do this insteadUse the largest count achievable over all sets of m instances.
Common mistake Assuming that a VC dimension of d means the growth function equals 2m for every m.
What it looks likeExtending the shattering count beyond m = d.
Why it failsA VC dimension of d identifies the largest shattered-set size; after m exceeds d, full shattering is no longer available.
Do this insteadUse the exponential possibility up to the VC-dimension threshold and Sauer's Lemma for the larger-sample regime.
Common mistake Treating Sauer's upper bound as an exact count.
What it looks likeConcluding that τH(3) equals 7 whenever VCdim(H) is at most 2.
Why it failsSauer's Lemma gives an upper bound, not a claim that every set realizes that many labelings.
Do this insteadWrite τ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 2m 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
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.