# Universal Rates of Empirical Risk Minimization

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 38 references that are in the map.
- First posted on arXiv 3 Dec 2024.

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

- [The Optimal Sample Complexity of PAC Learning](https://mlsanity.com/paper/1507.00473/) (2015)
- [Minimax Analysis of Active Learning](https://mlsanity.com/paper/1410.0996/) (2014)
- [A Theory of Universal Learning](https://mlsanity.com/paper/2011.04483/) (2020)
- [Refined Error Bounds for Several Learning Algorithms](https://mlsanity.com/paper/1512.07146/) (2015)
- [Understanding the Eluder Dimension](https://mlsanity.com/paper/2104.06970/) (2021)
- [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)
- [A Compression Technique for Analyzing Disagreement-Based Active Learning](https://mlsanity.com/paper/1404.1504/) (2014)
- [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)

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

- [Universal rates of ERM for agnostic learning](https://mlsanity.com/paper/2506.14110/) (2025)
- [Universal Multiclass Transductive Online Learning](https://mlsanity.com/paper/2605.30479/) (2026)
- [On the Learning Curves of Revenue Maximization](https://mlsanity.com/paper/2604.26922/) (2026)

## Abstract (arXiv)

The well-known empirical risk minimization (ERM) principle is the basis of many widely used machine learning algorithms, and plays an essential role in the classical PAC theory. A common description of a learning algorithm's performance is its so-called "learning curve", that is, the decay of the expected error as a function of the input sample size. As the PAC model fails to explain the behavior of learning curves, recent research has explored an alternative universal learning model and has ultimately revealed a distinction between optimal universal and uniform learning rates (Bousquet et al., 2021). However, a basic understanding of such differences with a particular focus on the ERM principle has yet to be developed. In this paper, we consider the problem of universal learning by ERM in the realizable case and study the possible universal rates. Our main result is a fundamental tetrachotomy: there are only four possible universal learning rates by ERM, namely, the learning curves of any concept class learnable by ERM decay either at e-n, 1/n, log(n)/n, or arbitrarily slow rates. Moreover, we provide a complete characterization of which concept classes fall into each of these categories, via new complexity structures. We also develop new combinatorial dimensions which supply sharp asymptotically-valid constant factors for these rates, whenever possible.