# Efficient Optimal PAC Learning

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Feb 2025.

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

- [On Agnostic PAC Learning in the Small Error Regime](https://mlsanity.com/paper/2502.09496/) (2025)
- [The Sample Complexity of Replicable Realizable PAC Learning](https://mlsanity.com/paper/2602.19552/) (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)

## Abstract (arXiv)

Recent advances in the binary classification setting by Hanneke [2016b] and Larsen [2023] have resulted in optimal PAC learners. These learners leverage, respectively, a clever deterministic subsampling scheme and the classic heuristic of bagging Breiman [1996]. Both optimal PAC learners use, as a subroutine, the natural algorithm of empirical risk minimization. Consequently, the computational cost of these optimal PAC learners is tied to that of the empirical risk minimizer algorithm. In this work, we seek to provide an alternative perspective on the computational cost imposed by the link to the empirical risk minimizer algorithm. To this end, we show the existence of an optimal PAC learner, which offers a different tradeoff in terms of the computational cost induced by the empirical risk minimizer.