Agnostic PAC Learning

Core Idea

Agnostic PAC learning generalizes the PAC framework by dropping the assumption that the target function belongs to the hypothesis class. In the realizable PAC setting, there exists a hypothesis with zero error; in the agnostic setting, the best hypothesis in the class may have nonzero error, and the learner must compete with this best-in-class benchmark. The goal becomes finding a hypothesis whose risk is within epsilon of the minimum achievable risk in the class. This is far more realistic — in practice, no model class perfectly captures the true data-generating process — and requires stronger uniform convergence guarantees.

Explainer

The basic PAC framework assumes that the target concept lives inside the hypothesis class — there exists some h in H with zero error. This "realizable" assumption is a convenient starting point but rarely holds in practice. Real data has noise, the true relationship may be more complex than any model in your class, and the hypothesis class is always an approximation. Agnostic PAC learning removes this assumption entirely, asking only that the learner compete with the best hypothesis available in the class.

Formally, in the agnostic setting, the data is generated by some unknown joint distribution P over (x, y) pairs. There is no assumption that a deterministic target function exists or that any hypothesis achieves zero error. The best-in-class risk is R* = min_{h in H} R(h), which may be large. An algorithm is an agnostic PAC learner for H if, given m samples, it outputs a hypothesis h with R(h) <= R* + epsilon with probability at least 1 - delta, where m is polynomial in 1/epsilon, 1/delta, and the class complexity.

The critical technical difference from the realizable case is in the sample complexity. In the realizable setting, a hypothesis that makes zero training errors is known to be close to the target (with high probability, its true error is at most epsilon with O(d/epsilon) samples). This is because errors are binary: either a hypothesis is consistent with all training examples or it is not. In the agnostic setting, the learner must distinguish between hypotheses whose error rates may differ by only epsilon — this requires precisely estimating continuous error rates rather than checking binary consistency. The estimation precision required drives the sample complexity up to O(d/epsilon²), an extra factor of 1/epsilon compared to the realizable case.

This quadratic penalty — the "price of agnosticism" — is tight: no algorithm can do better in the worst case. The agnostic framework is also where the connection to uniform convergence becomes essential. In the realizable case, weaker arguments suffice; in the agnostic case, the learner needs to know that training error uniformly approximates true error for all hypotheses in the class, not just for the correct one. This stronger requirement is what makes agnostic PAC learning the natural foundation for practical generalization theory, since it mirrors the actual conditions under which machine learning systems operate.