# On Agnostic PAC Learning in the Small Error Regime

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 21 references that are in the map.
- First posted on arXiv 13 Feb 2025.

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

- [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)
- [Majority-of-Three: The Simplest Optimal Learner?](https://mlsanity.com/paper/2403.08831/) (2024)
- [Revisiting Agnostic PAC Learning](https://mlsanity.com/paper/2407.19777/) (2024)
- [Efficient Optimal PAC Learning](https://mlsanity.com/paper/2502.03620/) (2025)

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

- [An Optimal Agnostic PAC Algorithm](https://mlsanity.com/paper/2608.06363/) (2026)
- [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)
- [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)

Binary classification in the classic PAC model exhibits a curious phenomenon: Empirical Risk Minimization (ERM) learners are suboptimal in the realizable case yet optimal in the agnostic case. Roughly speaking, this owes itself to the fact that non-realizable distributions D are simply more difficult to learn than realizable distributions -- even when one discounts a learner's error by err(h^*D), the error of the best hypothesis in H for D. Thus, optimal agnostic learners are permitted to incur excess error on (easier-to-learn) distributions D for which τ = err(h^*D) is small. Recent work of Hanneke, Larsen, and Zhivotovskiy (FOCS `24) addresses this shortcoming by including τ itself as a parameter in the agnostic error term. In this more fine-grained model, they demonstrate tightness of the error lower bound τ + Omega left(√fracτ (d + log(1 / δ))m + fracd + log(1 / δ)m right) in a regime where τ > d/m, and leave open the question of whether there may be a higher lower bound when τ ≈ d/m, with d denoting VC(H). In this work, we resolve this question by exhibiting a learner which achieves error c · τ + O left(√fracτ (d + log(1 / δ))m + fracd + log(1 / δ)m right) for a constant c ≤ 2.1, thus matching the lower bound when τ ≈ d/m. Further, our learner is computationally efficient and is based upon careful aggregations of ERM classifiers, making progress on two other questions of Hanneke, Larsen, and Zhivotovskiy (FOCS `24). We leave open the interesting question of whether our approach can be refined to lower the constant from 2.1 to 1, which would completely settle the complexity of agnostic learning.