# On the Variance, Admissibility, and Stability of Empirical Risk Minimization

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 60 references that are in the map.
- First posted on arXiv 29 May 2023.

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

- [Benign Overfitting in Linear Regression](https://mlsanity.com/paper/1906.11300/) (2019)
- [Surprises in High-Dimensional Ridgeless Least Squares Interpolation](https://mlsanity.com/paper/1903.08560/) (2019)
- [Just Interpolate: Kernel "Ridgeless" Regression Can Generalize](https://mlsanity.com/paper/1808.00387/) (2018)
- [A Universal Law of Robustness via Isoperimetry](https://mlsanity.com/paper/2105.12806/) (2021)
- [Does data interpolation contradict statistical optimality?](https://mlsanity.com/paper/1806.09471/) (2018)
- [A modern maximum-likelihood theory for high-dimensional logistic regression](https://mlsanity.com/paper/1803.06964/) (2018)
- [Learning without Concentration](https://mlsanity.com/paper/1401.0304/) (2014)
- [The phase transition for the existence of the maximum likelihood estimate in high-dimensional logistic regression](https://mlsanity.com/paper/1804.09753/) (2018)
- [De-biasing the Lasso: Optimal Sample Size for Gaussian Designs](https://mlsanity.com/paper/1508.02757/) (2015)
- [Empirical entropy, minimax regret and minimax risk](https://mlsanity.com/paper/1308.1147/) (2013)
- [Optimality of Maximum Likelihood for Log-Concave Density Estimation and Bounded Convex Regression](https://mlsanity.com/paper/1903.05315/) (2019)
- [Fitting Tractable Convex Sets to Support Function Evaluations](https://mlsanity.com/paper/1903.04194/) (2019)
- [Convex Regression in Multidimensions: Suboptimality of Least Squares Estimators](https://mlsanity.com/paper/2006.02044/) (2020)
- [On Suboptimality of Least Squares with Application to Estimation of Convex Bodies](https://mlsanity.com/paper/2006.04046/) (2020)
- [Near-Optimal Sample Complexity Bounds for Maximum Likelihood Estimation of Multivariate Log-concave Densities](https://mlsanity.com/paper/1802.10575/) (2018)
- [On the Minimal Error of Empirical Risk Minimization](https://mlsanity.com/paper/2102.12066/) (2021)

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

- [Addressing Label Shift in Distributed Learning via Entropy Regularization](https://mlsanity.com/paper/2502.02544/) (2025)
- [Model Agreement via Anchoring](https://mlsanity.com/paper/2602.23360/) (2026)
- [Risk reversal for least squares estimators under nested convex constraints](https://mlsanity.com/paper/2601.16041/) (2026)

## Abstract (arXiv)

It is well known that Empirical Risk Minimization (ERM) may attain minimax suboptimal rates in terms of the mean squared error (Birg'e and Massart, 1993). In this paper, we prove that, under relatively mild assumptions, the suboptimality of ERM must be due to its large bias. Namely, the variance error term of ERM is bounded by the minimax rate. In the fixed design setting, we provide an elementary proof of this result using the probabilistic method. Then, we extend our proof to the random design setting for various models. In addition, we provide a simple proof of Chatterjee's admissibility theorem (Chatterjee, 2014, Theorem 1.4), which states that in the fixed design setting, ERM cannot be ruled out as an optimal method, and then we extend this result to the random design setting. We also show that our estimates imply the stability of ERM, complementing the main result of Caponnetto and Rakhlin (2006) for non-Donsker classes. Finally, we highlight the somewhat irregular nature of the loss landscape of ERM in the non-Donsker regime, by showing that functions can be close to ERM, in terms of L2 distance, while still being far from almost-minimizers of the empirical loss.