PAC Learning

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.

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.

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.

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.

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.

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.