# Revisiting Agnostic PAC Learning

arXiv: https://arxiv.org/abs/2407.19777 · HTML: https://mlsanity.com/paper/2407.19777/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 29 references that are in the map.
- First posted on arXiv 29 Jul 2024.

## Builds on (most cited first, 9 of 9)

- [The Optimal Sample Complexity of PAC Learning](https://mlsanity.com/paper/1507.00473/) (2015)
- [Proper Learning, Helly Number, and an Optimal SVM Bound](https://mlsanity.com/paper/2005.11818/) (2020)
- [Bagging is an Optimal PAC Learner](https://mlsanity.com/paper/2212.02264/) (2022)
- [Optimal PAC Bounds Without Uniform Convergence](https://mlsanity.com/paper/2304.09167/) (2023)
- [Refined Error Bounds for Several Learning Algorithms](https://mlsanity.com/paper/1512.07146/) (2015)
- [Exponential Savings in Agnostic Active Learning through Abstention](https://mlsanity.com/paper/2102.00451/) (2021)
- [Majority-of-Three: The Simplest Optimal Learner?](https://mlsanity.com/paper/2403.08831/) (2024)
- [Fast classification rates without standard margin assumptions](https://mlsanity.com/paper/1910.12756/) (2019)
- [Margins are Insufficient for Explaining Gradient Boosting](https://mlsanity.com/paper/2011.04998/) (2020)

## Built on by (most cited first, 11 of 11)

- [Is Limited Participant Diversity Impeding EEG-based Machine Learning?](https://mlsanity.com/paper/2503.13497/) (2025)
- [On Agnostic PAC Learning in the Small Error Regime](https://mlsanity.com/paper/2502.09496/) (2025)
- [On The Statistical Limits of Self-Improving Agents](https://mlsanity.com/paper/2510.04399/) (2025)
- [An Optimal Agnostic PAC Algorithm](https://mlsanity.com/paper/2608.06363/) (2026)
- [Universal rates of ERM for agnostic learning](https://mlsanity.com/paper/2506.14110/) (2025)
- [PAC-Causal Learnability: From Identification to Finite-Sample Guarantees](https://mlsanity.com/paper/2507.18903/) (2025)
- [A Fine-Grained Understanding of Uniform Convergence for Halfspaces](https://mlsanity.com/paper/2605.06004/) (2026)
- [The Interplay Between Interpolation and Aggregation in Regression: Optimal Sample Complexity](https://mlsanity.com/paper/2605.29819/) (2026)
- [Optimal Learning Under Tsybakov Noise](https://mlsanity.com/paper/2608.08416/) (2026)
- [Optimistic Rates for Multiclass PAC Learning](https://mlsanity.com/paper/2608.10869/) (2026)
- [Adversarially Robust PAC Learning with Optimal VC Rates](https://mlsanity.com/paper/2609.24260/) (2026)

## Abstract (arXiv)

PAC learning, dating back to Valiant'84 and Vapnik and Chervonenkis'64,'74, is a classic model for studying supervised learning. In the agnostic setting, we have access to a hypothesis set H and a training set of labeled samples (x1,y1),dots,(xn,yn) ∈ X × -1,1 drawn i.i.d. from an unknown distribution D. The goal is to produce a classifier h : X → -1,1 that is competitive with the hypothesis h^starD ∈ H having the least probability of mispredicting the label y of a new sample (x,y)~ D. Empirical Risk Minimization (ERM) is a natural learning algorithm, where one simply outputs the hypothesis from H making the fewest mistakes on the training data. This simple algorithm is known to have an optimal error in terms of the VC-dimension of H and the number of samples n. In this work, we revisit agnostic PAC learning and first show that ERM is in fact sub-optimal if we treat the performance of the best hypothesis, denoted τ:=PrD[h^starD(x) neq y], as a parameter. Concretely we show that ERM, and any other proper learning algorithm, is sub-optimal by a √ln(1/τ) factor. We then complement this lower bound with the first learning algorithm achieving an optimal error for nearly the full range of τ. Our algorithm introduces several new ideas that we hope may find further applications in learning theory.