# On the Minimal Error of Empirical Risk Minimization

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 36 references that are in the map.
- First posted on arXiv 24 Feb 2021.

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

- [Benign Overfitting in Linear Regression](https://mlsanity.com/paper/1906.11300/) (2019)
- [Just Interpolate: Kernel "Ridgeless" Regression Can Generalize](https://mlsanity.com/paper/1808.00387/) (2018)
- [Benign overfitting in ridge regression](https://mlsanity.com/paper/2009.14286/) (2020)
- [Overfitting or perfect fitting? Risk bounds for classification and regression rules that interpolate](https://mlsanity.com/paper/1806.05161/) (2018)
- [Does data interpolation contradict statistical optimality?](https://mlsanity.com/paper/1806.09471/) (2018)
- [Learning without Concentration](https://mlsanity.com/paper/1401.0304/) (2014)
- [Explaining the Success of AdaBoost and Random Forests as Interpolating Classifiers](https://mlsanity.com/paper/1504.07676/) (2015)
- [Empirical entropy, minimax regret and minimax risk](https://mlsanity.com/paper/1308.1147/) (2013)
- [Recent progress in log-concave density estimation](https://mlsanity.com/paper/1709.03154/) (2017)
- [Max-Affine Regression: Provable, Tractable, and Near-Optimal Statistical Estimation](https://mlsanity.com/paper/1906.09255/) (2019)
- [Optimality of Maximum Likelihood for Log-Concave Density Estimation and Bounded Convex Regression](https://mlsanity.com/paper/1903.05315/) (2019)
- [On Suboptimality of Least Squares with Application to Estimation of Convex Bodies](https://mlsanity.com/paper/2006.04046/) (2020)

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

- [A Moment-Matching Approach to Testable Learning and a New Characterization of Rademacher Complexity](https://mlsanity.com/paper/2211.13312/) (2022)
- [On the Variance, Admissibility, and Stability of Empirical Risk Minimization](https://mlsanity.com/paper/2305.18508/) (2023)
- [An Efficient Minimax Optimal Estimator For Multivariate Convex Regression](https://mlsanity.com/paper/2205.03368/) (2022)

## Abstract (arXiv)

We study the minimal error of the Empirical Risk Minimization (ERM) procedure in the task of regression, both in the random and the fixed design settings. Our sharp lower bounds shed light on the possibility (or impossibility) of adapting to simplicity of the model generating the data. In the fixed design setting, we show that the error is governed by the global complexity of the entire class. In contrast, in random design, ERM may only adapt to simpler models if the local neighborhoods around the regression function are nearly as complex as the class itself, a somewhat counter-intuitive conclusion. We provide sharp lower bounds for performance of ERM for both Donsker and non-Donsker classes. We also discuss our results through the lens of recent studies on interpolation in overparameterized models.