# An Optimal Agnostic PAC Algorithm

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 26 references that are in the map.
- First posted on arXiv 6 Aug 2026.

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

- [The Optimal Sample Complexity of PAC Learning](https://mlsanity.com/paper/1507.00473/) (2015)
- [Adversarial Laws of Large Numbers and Optimal Regret in Online Classification](https://mlsanity.com/paper/2101.09054/) (2021)
- [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)
- [Optimal Prediction Using Expert Advice and Randomized Littlestone Dimension](https://mlsanity.com/paper/2302.13849/) (2023)
- [Regularization and Optimal Multiclass Learning](https://mlsanity.com/paper/2309.13692/) (2023)
- [The One-Inclusion Graph Algorithm is not Always Optimal](https://mlsanity.com/paper/2212.09270/) (2022)
- [Revisiting Agnostic PAC Learning](https://mlsanity.com/paper/2407.19777/) (2024)
- [On Agnostic PAC Learning in the Small Error Regime](https://mlsanity.com/paper/2502.09496/) (2025)
- [Is Transductive Learning Equivalent to PAC Learning?](https://mlsanity.com/paper/2405.05190/) (2024)

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

- [Adversarially Robust PAC Learning with Optimal VC Rates](https://mlsanity.com/paper/2609.24260/) (2026)
- [Agnostic Smoothed Online Regression with Adversarial Responses](https://mlsanity.com/paper/2609.32478/) (2026)

## Abstract (arXiv)

Let Hsubseteq-1,+1X be a class of finite VC dimension d≥1. Writing L for the binary risk and L^*=minh∈ HL(h), we construct a learner achieving the statistically optimal risk bound: from an i.i.d. sample of size n, for every 0<δ≤ 1/2, with probability at least 1-δ, [ L(widehat h) ≤ L^*+ 7·108left( √fracL^*(d+log(1/δ))n +fracd+log(1/δ)n right). ] This settles the sample complexity of agnostic PAC learning up to universal constants at every fixed L^*, matching the lower bounds of Devroye, Gy"orfi, and Lugosi [A Probabilistic Theory of Pattern Recognition, Springer, 1996].