Realizable PAC Learnability
An ϵ-net turns a sample into a coverage guarantee for all sufficiently probable sets in a hypothesis class.
The Generalization Problem
A learner observes a labeled sample and must choose a hypothesis from a hypothesis class. The difficult question is whether the selected hypothesis remains accurate beyond the examples in that sample. Realizable PAC learnability answers this question by combining three ideas: a sample that covers every sufficiently probable disagreement region, the VC dimension that controls the relevant class complexity, and empirical risk minimization, or ERM, that selects a hypothesis consistent with the sample.
PAC means probably approximately correct. A hypothesis is approximately correct when its true error is at most ϵ, and probably correct means that this condition holds with probability at least 1 − δ over the random choice of the training sample.
The guarantee is about the random sample, not about every possible sample. With the required sample size, the probability that the selected ERM hypothesis has true error at most ϵ is at least 1 − δ.
From Error to Set Coverage
Suppose c is the target hypothesis and h is another hypothesis in H. Consider the set of instances on which h and c disagree. This is the disagreement set between h and c. Under the distribution D, the probability of this set is exactly the true error of h under the target labeling by c. Therefore, a hypothesis with true error at least ϵ corresponds to a disagreement set with probability at least ϵ.
An ϵ-net for a class of sets under a distribution is a sample that intersects every set in the class whose probability is at least ϵ. Sets with probability below ϵ are not required to be intersected by the sample.
The important conversion is from prediction error to set intersection. If h has true error at least ϵ, its disagreement set with c has probability at least ϵ. If the sample is an ϵ-net for all such disagreement sets, the sample contains an instance where h disagrees with c.
The Disagreement Class H_c
For a target hypothesis c and hypothesis class H, define H_c as the class of disagreement sets between c and the hypotheses in H. In other words, each h in H contributes the set of instances on which h and c give different labels.
The transformation changes the objects being studied: H contains hypotheses, while H_c contains the corresponding disagreement sets. The source argument states that this transformation preserves VC dimension: VCdim(H) equals VCdim(H_c). Consequently, a VC-dimension result that applies to H can also support the ϵ-net argument for H_c.
A Disagreement Set Rules Out a Hypothesis
Suppose the target hypothesis c and a competing hypothesis h disagree on a region with probability 0.4. Let ϵ be 0.2, and suppose the training sample intersects that disagreement region.
Identify the true error: Because h disagrees with c on a region of probability 0.4, h has true error 0.4 under the target labeling.
Compare error with ϵ: The true error 0.4 is at least ϵ = 0.2, so this is a disagreement set that an ϵ-net must intersect.
Use the sampled intersection: The sample contains an instance from the disagreement region, so h makes an error on that labeled training instance.
Apply ERM: If c is consistent with the sample, h cannot be an ERM hypothesis because h has positive empirical error while c has zero empirical error.
The sample rules out h as an ERM choice. The same reasoning applies to every hypothesis whose true error is at least ϵ when the sample is an ϵ-net for H_c.
Why VC Dimension Matters
VC dimension measures the complexity of a hypothesis class. In this argument, H has VC dimension d. The relevant ϵ-net result uses this complexity to control the behavior of the disagreement class. Because VCdim(H) equals VCdim(H_c), the same complexity measure can be carried from the original hypothesis class to the class of sets that must be covered.
VC dimension is not used here to choose a particular hypothesis directly. Its role is to control the complexity of the set family for which the sample must provide coverage.
ERM in the Realizable Setting
ERM chooses a hypothesis with minimum empirical risk from the hypothesis class. In a finite class, the learner examines the available hypotheses and selects one with the smallest training error.
In the realizable setting, c belongs to H and labels the sample. Therefore, c has zero empirical risk on the sample. Any hypothesis that disagrees with c on a sampled instance has positive empirical error and cannot be an ERM hypothesis while a zero-error hypothesis is available.
Now combine the pieces. If an ERM hypothesis h had true error at least ϵ, its disagreement set with c would have probability at least ϵ. An ϵ-net sample would intersect that set, giving h a sampled error. That contradicts h being an ERM hypothesis because c is consistent with the sample. Thus, every ERM hypothesis has true error below the large-error threshold described by the ϵ-net argument.
Reading the PAC Guarantee
| Quantity | Role in the guarantee |
|---|---|
| m | The required number of independent and identically distributed labeled instances, as specified by the relevant sample-size theorem. |
| ϵ | The target upper bound on the true error. |
| δ | The confidence-failure parameter; the guarantee holds with probability at least 1 − δ. |
| ERM | The rule that selects a minimum-empirical-risk hypothesis from the finite class. |
| Realizability | The condition that the class contains at least one zero-risk hypothesis for the target labeling. |
The roles of the parameters and assumptions in the finite-class realizable PAC result.
Theorem 28.4 states the resulting guarantee: with probability at least 1 − δ over the choice of the m independent and identically distributed instances labeled according to c, any ERM hypothesis has true error at most ϵ. The value of m is the one specified by Theorem 28.3. The statement connects the desired error level, the confidence level, and the required sample size without claiming that every individual sample succeeds.
Treating an ϵ-net as a guarantee that every possible set is sampled.
The ϵ-net definition requires intersection only for sets whose probability is at least ϵ.
Fix:
Apply the guarantee to sufficiently probable disagreement sets.Confusing true error with training error.
The sample is used to detect disagreement, while the guarantee is about performance beyond the sample.
Fix:
Track the argument from true error to disagreement-set probability, then use the sample to rule out large-error hypotheses.Thinking that ERM alone guarantees low true error for every sample.
The guarantee holds with probability at least 1 − δ, not with certainty for every possible sample.
Fix:
Include both the sample-size requirement and the confidence probability in the conclusion.Ignoring realizability.
The exclusion argument relies on the target hypothesis c providing a zero-empirical-risk alternative.
Fix:
Check that the target labeling is realizable by the hypothesis class before applying this result.
Apply the Argument
A target hypothesis c belongs to H. A competing hypothesis h disagrees with c on a set whose probability is at least ϵ. The labeled sample is an ϵ-net for H_c, and c is consistent with the sample. Explain why h cannot be selected as an ERM hypothesis.
Hints
- Translate the probability of the disagreement set into the true error of h.
- Use the definition of an ϵ-net.
- Compare the empirical errors of h and c.
Suppose VCdim(H) = d and the source theorem supplies a sample-size requirement m for parameters ϵ and δ. State what the realizable PAC theorem says about any ERM hypothesis after drawing m independent and identically distributed labeled instances.
Hints
- Include the probability over the random sample.
- State the upper bound on true error.
- Mention the role of realizability.
Core Takeaways
- An ϵ-net intersects every set in the relevant class whose probability is at least ϵ.
- For a target c, the disagreement class H_c converts each hypothesis's true error into the probability of a set.
- If a hypothesis has true error at least ϵ, an ϵ-net sample exposes that hypothesis through a sampled disagreement.
- VCdim(H) equals VCdim(H_c), allowing the complexity control for H to support the ϵ-net argument.
- Under realizability, ERM selects a minimum-empirical-risk hypothesis, and with the required sample size any ERM hypothesis has true error at most ϵ with probability at least 1 − δ.
Key Takeaways
- PAC means bounded true error with high probability over the random training sample.
- The disagreement class H_c lets the proof express hypothesis error as set probability.
- An ϵ-net intersects every sufficiently probable disagreement set and therefore rules out hypotheses with true error at least ϵ.
- VC dimension transfers from H to H_c, providing the complexity control needed by the ϵ-net argument.
- In the realizable setting, a sufficiently large sample makes every ERM hypothesis probably approximately correct.