PAC Learning

When Perfect Labels Fail

A traditional learning model often assumes that the features of every input determine one correct label with complete certainty. Under this assumption, there is a target labeling function, and some hypothesis in the class H agrees perfectly with that function. This is the realizability assumption. It makes learning conceptually clean: the learner searches for a hypothesis that makes no errors on the underlying labeling rule. Practical data, however, may not satisfy this assumption. Measured features may fail to capture everything that influences a label, so the same feature description can be associated with different labels. Agnostic PAC learning removes the requirement that one hypothesis represent the data perfectly.

A Joint View of Data and Labels

Agnostic PAC learning describes data generation with a joint data-labels distribution over X × Y. Here, X represents the domain of possible feature descriptions and Y represents the possible labels. A joint distribution assigns likelihood to combinations of a domain point and a label. It therefore describes the two parts together: which point appears and which label accompanies that point.

The diagram does not say that a single observation simultaneously has two labels. It shows that the same domain description can participate in different possible domain-label outcomes under the data-generating distribution. This is precisely what the realizability assumption rules out when it requires one correct label for each input description.

Marginal and Conditional Questions

Suppose the domain point is a papaya feature description. The marginal distribution asks how likely that feature description is to appear at all. It does not, by itself, answer which taste label accompanies the point. The conditional probability asks the second question: once the feature description is fixed, how likely is each label? Keeping these questions separate prevents a common misunderstanding. A point can be common or rare independently of whether its labels are concentrated or varied.

ERM and the Agnostic Goal

In agnostic PAC learning, the learner does not assume that the data can be represented perfectly by a hypothesis in H. The target therefore changes. Instead of requiring zero error, the learner seeks a hypothesis whose performance is close to that of the optimal hypothesis in H. This comparison is important: the learner is judged against the best available member of the chosen hypothesis class, not against a perfect hypothesis that may not exist.

Uniform Risk Control

Theorem 26.5 provides a uniform risk comparison for every hypothesis in the class. Its role is to control the difference between true risk and empirical risk, not merely for the hypothesis eventually selected by ERM, but for all hypotheses in H at once. This uniform statement is what allows the proof to analyze the data-dependent choice made by ERM. Without such a connection, a hypothesis could look best on the observed sample without the analysis establishing that it is close to the best choice under the underlying distribution.

The proof considers the possibility that a hypothesis has a substantial difference between its true risk and empirical risk. Theorem 26.5 supplies the relevant comparison for each hypothesis. The union bound then controls the probability that any of the relevant failure events occurs. The result is a statement that the comparison holds simultaneously across the hypothesis class, with a controlled probability of failure.

• Treating the theorem as a guarantee only for the ERM output.

  The chosen hypothesis depends on the sample. A guarantee stated uniformly for every hypothesis is what allows the proof to cover the data-dependent ERM choice.

  Fix: Understand Theorem 26.5 as a simultaneous comparison across H before focusing on the hypothesis selected by ERM.

• Assuming the union bound makes every individual failure event impossible.

  The union bound controls the probability of the combined event; it does not assert that every component event is impossible.

  Fix: Use it to bound the probability that at least one relevant comparison fails.

• Confusing empirical risk with true risk.

  Empirical risk is based on the sample, while the agnostic objective concerns performance under the data-generating distribution.

  Fix: Use the uniform risk comparison to connect the two quantities.

Why Sample Size Matters

An upper-bound proof for agnostic PAC learnability establishes that there is a sufficient sample complexity for achieving the desired comparison with the optimal hypothesis in H. The sample-size condition is needed because the proof must make the final error small enough, typically below a chosen epsilon. The source material does not provide the literal algebraic expression for that sample complexity. The justified structural conclusion is that the proof first obtains a uniform risk bound, combines the relevant failure events with the union bound, and then imposes the sufficient condition from Lemma A.2 so the final error is below epsilon.

Practice: Trace the Proof

Key Takeaways

1. Realizability requires some hypothesis in H to agree perfectly with a target labeling function, an assumption that may fail when measured features do not completely determine labels.
2. Agnostic PAC learning uses a joint distribution over domain points and labels, allowing the same domain point to be associated with different possible labels.
3. The marginal distribution describes which domain points occur, while the conditional probability describes labels given a particular point.
4. ERM selects a hypothesis with the smallest empirical risk, but Theorem 26.5 is needed to connect empirical risk with true risk uniformly across H.
5. The union bound controls combined failure events, and a sufficient sample-size condition ensures that the final error is below epsilon.