Finite Classes Are Agnostic PAC Learnable
Uniform convergence is a statement about all hypotheses in H simultaneously.
The Proof Target
The central challenge is not to show that one particular hypothesis has similar empirical and true error. The proof must show this for every hypothesis in the finite class H simultaneously. For a fixed accuracy level ϵ and failure probability δ, it searches for a sample size m such that, for any distribution D, an independently sampled data set S = (z₁, . . . , zₘ) gives the required guarantee with probability at least 1 − δ.
The Two-Pass Strategy
The proof has two distinct probability steps. First, it uses the union bound to gather the possible failure events for the individual hypotheses into one combined event: at least one hypothesis violates the desired accuracy level. Second, it uses a measure concentration inequality to bound the probability of that combined event. The sample size m is chosen so that the resulting probability guarantee is at least 1 − δ.
The order matters conceptually: the union bound identifies the class-wide failure event, while the measure concentration inequality supplies a probability bound for that event.
Gathering Failure Events
For each hypothesis h in H, consider the event that its discrepancy exceeds ϵ. In other words, that hypothesis fails to meet the desired closeness between empirical error L_S(h) and true error L_D(h). Uniform convergence fails if at least one of these hypothesis-specific failure events occurs. The union bound is used first because it relates the probability of this combined event to the probabilities of the individual events.
A Finite Class with Several Possible Failures
Suppose H contains the hypotheses h₁, h₂, and h₃. What event must the proof control to establish uniform convergence?
Identify the individual events: For each hypothesis, identify the event that the discrepancy between its empirical error and true error exceeds ϵ.
Combine the events: Uniform convergence fails when at least one of the three hypothesis-specific failure events occurs.
Apply the first probability tool: Use the union bound to relate the probability of the combined failure event to the probabilities of the three individual events.
Continue to the second step: After the events have been combined, use a measure concentration inequality to bound the probability of the event under consideration.
The proof controls one class-wide failure event rather than treating the hypotheses as if only one selected hypothesis mattered.
Concentrating One Hypothesis
Once the possible failures have been gathered into the event relevant to uniform convergence, the second step uses a measure concentration inequality. Its role is to bound the probability of that event. The proof then chooses m so that this probability is small enough to meet the requested failure probability δ, giving success probability at least 1 − δ.
The Uniform Guarantee
Uniform convergence requires that the inequality |L_S(h) − L_D(h)| ≤ ϵ hold for all h in H at the same time. The sample size m must be chosen so that, for any distribution D and an independently sampled S, this all-hypotheses statement holds with probability at least 1 − δ.
Checking Whether a Statement Is Uniform
Compare these two proof targets: controlling the discrepancy for one selected hypothesis, and controlling it for every h in H.
Inspect the quantifier: A statement about one selected hypothesis does not account for the possibility that another member of H violates the bound.
Use the class-wide requirement: The uniform statement requires |L_S(h) − L_D(h)| ≤ ϵ for all h in H simultaneously.
Attach the probability guarantee: The proof must make this all-hypotheses statement hold with probability at least 1 − δ over the choice of S.
The word uniform refers to the simultaneous requirement over the entire hypothesis class, not merely to the behavior of one chosen hypothesis.
Common Proof Mistakes
Proving the bound for only one hypothesis.
Uniform convergence requires the bound to hold for every h in H at the same time.
Fix:
Treat each hypothesis as contributing a possible failure event and control the combined event.Using the concentration inequality before identifying the combined failure event.
The proof must first gather the individual failure events with a union bound.
Fix:
Use the union bound first, then use a measure concentration inequality to bound the resulting event.Forgetting the role of m.
The proof fixes ϵ and δ and searches for a sample size m that reaches the required probability level.
Fix:
State that m is selected so the all-hypotheses guarantee holds with probability at least 1 − δ.Confusing accuracy with success probability.
ϵ controls the allowed discrepancy between empirical and true error, while δ appears in the required success probability 1 − δ.
Fix:
Keep the two goals distinct: closeness is controlled by ϵ, and the probability of obtaining the class-wide guarantee is controlled by δ.
Practice the Proof Order
Explain the proof outline in the correct order. Your explanation should mention what is fixed first, what event the union bound combines, what the measure concentration inequality does, and what property the selected sample size m must provide.
Hints
- Begin with ϵ and δ.
- Describe one failure event for each h in H.
- Say what it means for at least one of those events to occur.
- End with the probability level required for the all-hypotheses guarantee.
- A strong answer should say: fix ϵ and δ; use the union bound to combine the individual hypothesis failure events; use a measure concentration inequality to bound the combined event; and choose m so that |L_S(h) − L_D(h)| ≤ ϵ holds for every h in H with probability at least 1 − δ.
Key Takeaways
- Uniform convergence is a simultaneous statement about all hypotheses in H.
- The proof fixes ϵ and δ, then searches for a suitable sample size m.
- The union bound is used first to gather the individual failure events into one combined event.
- A measure concentration inequality is used second to bound the probability of that combined event.
- The final guarantee is |L_S(h) − L_D(h)| ≤ ϵ for every h in H with probability at least 1 − δ.
Key Takeaways
- Uniform convergence must control the discrepancy between empirical error and true error for every hypothesis in H simultaneously.
- The proof fixes an accuracy level ϵ and a failure probability δ, then searches for a suitable sample size m.
- The union bound is the first step because it combines the possible failure events for individual hypotheses.
- A measure concentration inequality is the second step because it bounds the probability of the combined event.
- The target guarantee is |L_S(h) − L_D(h)| ≤ ϵ for all h in H with probability at least 1 − δ.