# Universal rates of ERM for agnostic learning

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 49 references that are in the map.
- First posted on arXiv 17 Jun 2025.

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

- [The Optimal Sample Complexity of PAC Learning](https://mlsanity.com/paper/1507.00473/) (2015)
- [A Theory of Universal Learning](https://mlsanity.com/paper/2011.04483/) (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)
- [Learning Whenever Learning is Possible: Universal Learning under General Stochastic Processes](https://mlsanity.com/paper/1706.01418/) (2017)
- [Majority-of-Three: The Simplest Optimal Learner?](https://mlsanity.com/paper/2403.08831/) (2024)
- [Multiclass Learnability Beyond the PAC Framework: Universal Rates and Partial Concept Classes](https://mlsanity.com/paper/2210.02297/) (2022)
- [Exponential convergence of testing error for stochastic gradient methods](https://mlsanity.com/paper/1712.04755/) (2017)
- [Revisiting Agnostic PAC Learning](https://mlsanity.com/paper/2407.19777/) (2024)
- [Fine-Grained Distribution-Dependent Learning Curves](https://mlsanity.com/paper/2208.14615/) (2022)
- [Universal Rates for Multiclass Learning](https://mlsanity.com/paper/2307.02066/) (2023)
- [Universal Rates of Empirical Risk Minimization](https://mlsanity.com/paper/2412.02810/) (2024)

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

- [Optimal Learning Under Tsybakov Noise](https://mlsanity.com/paper/2608.08416/) (2026)

## Abstract (arXiv)

The universal learning framework has been developed to obtain guarantees on the learning rates that hold for any fixed distribution, which can be much faster than the ones uniformly hold over all the distributions. Given that the Empirical Risk Minimization (ERM) principle being fundamental in the PAC theory and ubiquitous in practical machine learning, the recent work of arXiv:2412.02810 studied the universal rates of ERM for binary classification under the realizable setting. However, the assumption of realizability is too restrictive to hold in practice. Indeed, the majority of the literature on universal learning has focused on the realizable case, leaving the non-realizable case barely explored. In this paper, we consider the problem of universal learning by ERM for binary classification under the agnostic setting, where the ''learning curve" reflects the decay of the excess risk as the sample size increases. We explore the possibilities of agnostic universal rates and reveal a compact trichotomy: there are three possible agnostic universal rates of ERM, being either e-n, o(n-1/2), or arbitrarily slow. We provide a complete characterization of which concept classes fall into each of these categories. Moreover, we also establish complete characterizations for the target-dependent universal rates as well as the Bayes-dependent universal rates.