Growth Functions
A class with small effective size enjoys the uniform convergence property.
Why Class Size Matters
Suppose a learning argument must control the behavior of every member of a class H at once. The central question is whether H is small enough in effective size for a uniform guarantee to hold. The key result is that a class with small effective size enjoys the uniform convergence property.
Reading the Theorem Symbols
Theorem 6.11 organizes five quantities. H is the class under consideration. The growth function τ_H is the class-level quantity used in the theorem and serves as the effective-size description of H. D is a distribution over which the theorem quantifies. δ is chosen in the interval from 0 to 1 and represents the probability allowance in the guarantee. S is the random sample, selected according to S ∼ D^m.
Following the Probability Guarantee
- Begin with a class H and its growth function τ_H.
- Choose any distribution D and any δ in the interval from 0 to 1.
- Select the random sample S according to S ∼ D^m.
- Apply the displayed condition from Theorem 6.11 to these quantities.
- The theorem states that the displayed condition holds with probability at least 1 − δ over the choice of S.
The probability is over the random choice of S, not over a single fixed hypothesis selected in isolation. This matters because the result concerns the behavior of every member of H at once. The theorem turns the sample-dependent displayed condition into a high-probability statement useful for uniform convergence.
A Symbolic Walkthrough
Organizing an Application of Theorem 6.11
You are given a class H, its growth function τ_H, a distribution D, a value δ in (0, 1), and a sample S drawn according to S ∼ D^m. What can be concluded without inventing the missing displayed condition?
Identify the class: Treat H as the class whose members must be controlled simultaneously.
Identify effective size: Use τ_H as the class-level quantity describing the effective size relevant to the theorem.
Identify randomness: Treat S as the random object, with its selection governed by S ∼ D^m.
Apply the theorem's condition: Read the exact displayed condition supplied by Theorem 6.11 and verify or establish it using the quantities in the theorem.
State the guarantee: Once the theorem is applied, the displayed condition holds with probability at least 1 − δ over the choice of S.
The theorem supplies a probability guarantee about the sample S. It does not justify replacing the displayed condition with an unspecified formula.
Common Reading Errors
Treating τ_H as a second hypothesis class instead of the growth function associated with H.
The source identifies τ_H as the class-level quantity used to describe the effective size of H.
Fix:
Read τ_H as the growth function connected to the class H.Forgetting that the randomness is in S.
The theorem's guarantee is made over samples S selected according to S ∼ D^m.
Fix:
State that the condition holds with probability at least 1 − δ over the choice of S.Treating δ as the probability that the theorem succeeds.
The theorem gives a probability of at least 1 − δ, so δ is the allowance complementary to that guarantee.
Fix:
Report the guarantee as at least 1 − δ.Replacing the displayed condition with a remembered or invented formula.
The exact condition is part of the theorem's displayed statement and cannot be recovered from the symbol roles alone.
Fix:
Use the literal displayed condition when applying Theorem 6.11.
Check Your Understanding
Explain Theorem 6.11 in one paragraph using all five symbols H, τ_H, D, δ, and S. Your explanation must state what is random, identify the sampling rule, and give the probability guarantee. Do not write an explicit displayed condition unless it has been supplied separately.
Hints
- Begin with H and τ_H.
- Mention that D and δ are quantified over, with δ in (0, 1).
- State that S is selected according to S ∼ D^m.
- Finish with the phrase probability at least 1 − δ over the choice of S.
Key Takeaways
- A class H with small effective size enjoys the uniform convergence property.
- The growth function τ_H is the class-level quantity used in Theorem 6.11 to describe effective size.
- The theorem quantifies over every distribution D and every δ in (0, 1), while the sample S is selected according to S ∼ D^m.
- With probability at least 1 − δ over the choice of S, the displayed condition in Theorem 6.11 holds.
- The theorem's probability claim and its displayed condition are related but distinct: the condition provides the exact details, while the theorem supplies the high-probability guarantee.
Key Takeaways
- Small effective size of H, represented through τ_H, supports uniform convergence.
- H is the class, τ_H is its growth function, D is the distribution, δ is in (0, 1), and S is sampled according to S ∼ D^m.
- Theorem 6.11 guarantees that its displayed condition holds with probability at least 1 − δ over S.
- The exact displayed condition must be supplied from the theorem; it should not be reconstructed from the symbol roles alone.