Finite Classes Are Agnostic PAC Learnable

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.

Programming

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 − δ.

How can one guarantee that empirical error is close to true error for every hypothesis in H simultaneously?

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 − δ.

What happens first and second when proving that a finite hypothesis class is agnostic PAC learnable?

Key point

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.

How do failure events for individual hypotheses combine into one probability bound for the entire class H?

Worked example

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?

1
Identify the individual events
For each hypothesis, identify the event that the discrepancy between its empirical error and true error exceeds ϵ.
2
Combine the events
Uniform convergence fails when at least one of the three hypothesis-specific failure events occurs.
3
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.
4
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.

Result

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 − δ.

How does a concentration inequality connect a hypothesis's empirical and true errors to a high-probability guarantee?

The Uniform Guarantee

Definition

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 − δ.

What exact relationship must hold for every h in H, and how do empirical error, true error, ϵ, and δ fit into the guarantee?

Worked example

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.

1
Inspect the quantifier
A statement about one selected hypothesis does not account for the possibility that another member of H violates the bound.
2
Use the class-wide requirement
The uniform statement requires |L_S(h) − L_D(h)| ≤ ϵ for all h in H simultaneously.
3
Attach the probability guarantee
The proof must make this all-hypotheses statement hold with probability at least 1 − δ over the choice of S.

Result

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

Common mistake
Proving the bound for only one hypothesis.
What it looks like
Showing that |L_S(h) − L_D(h)| ≤ ϵ for a selected h and stopping there.
Why it fails
Uniform convergence requires the bound to hold for every h in H at the same time.
Do this instead
Treat each hypothesis as contributing a possible failure event and control the combined event.
Common mistake
Using the concentration inequality before identifying the combined failure event.
What it looks like
Applying a probability bound without first accounting for the possibility that any hypothesis violates the accuracy requirement.
Why it fails
The proof must first gather the individual failure events with a union bound.
Do this instead
Use the union bound first, then use a measure concentration inequality to bound the resulting event.
Common mistake
Forgetting the role of m.
What it looks like
Describing the probability tools without explaining what the proof must choose.
Why it fails
The proof fixes ϵ and δ and searches for a sample size m that reaches the required probability level.
Do this instead
State that m is selected so the all-hypotheses guarantee holds with probability at least 1 − δ.
Common mistake
Confusing accuracy with success probability.
What it looks like
Treating ϵ and δ as if they represented the same requirement.
Why it fails
ϵ controls the allowed discrepancy between empirical and true error, while δ appears in the required success probability 1 − δ.
Do this instead
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

MEDIUM

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.

Your attempt (not saved)

1
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 − δ.

At a glance

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 − δ.

Related concepts

More concepts starting with F