# Generalization of ERM in Stochastic Convex Optimization: The Dimension Strikes Back

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

## Key facts

- Cited by 37 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Aug 2016.

## Built on by (most cited first, 30 of 37)

- [Remember What You Want to Forget: Algorithms for Machine Unlearning](https://mlsanity.com/paper/2103.03279/) (2021)
- [Private Stochastic Convex Optimization: Optimal Rates in ℓ1 Geometry](https://mlsanity.com/paper/2103.01516/) (2021)
- [Private Convex Optimization via Exponential Mechanism](https://mlsanity.com/paper/2203.00263/) (2022)
- [Stability and Deviation Optimal Risk Bounds with Convergence Rate O(1/n)](https://mlsanity.com/paper/2103.12024/) (2021)
- [SGD Generalizes Better Than GD (And Regularization Doesn't Help)](https://mlsanity.com/paper/2102.01117/) (2021)
- [SGD: The Role of Implicit Regularization, Batch-size and Multiple-epochs](https://mlsanity.com/paper/2107.05074/) (2021)
- [Private Non-smooth Empirical Risk Minimization and Stochastic Convex Optimization in Subquadratic Steps](https://mlsanity.com/paper/2103.15352/) (2021)
- [Benign Underfitting of Stochastic Gradient Descent](https://mlsanity.com/paper/2202.13361/) (2022)
- [Beyond Lipschitz: Sharp Generalization and Excess Risk Bounds for Full-Batch GD](https://mlsanity.com/paper/2204.12446/) (2022)
- [Information Theoretic Lower Bounds for Information Theoretic Upper Bounds](https://mlsanity.com/paper/2302.04925/) (2023)
- [Algorithmic Instabilities of Accelerated Gradient Descent](https://mlsanity.com/paper/2102.02167/) (2021)
- [Never Go Full Batch (in Stochastic Convex Optimization)](https://mlsanity.com/paper/2107.00469/) (2021)
- [Information Complexity of Stochastic Convex Optimization: Applications to Generalization and Memorization](https://mlsanity.com/paper/2402.09327/) (2024)
- [Generalization Bounds for Stochastic Gradient Descent via Localized varepsilon-Covers](https://mlsanity.com/paper/2209.08951/) (2022)
- [Complementary Composite Minimization, Small Gradients in General Norms, and Applications](https://mlsanity.com/paper/2101.11041/) (2021)
- [Sample Complexity of Agnostic Multiclass Classification: Natarajan Dimension Strikes Back](https://mlsanity.com/paper/2511.12659/) (2025)
- [Uniform Stability for First-Order Empirical Risk Minimization](https://mlsanity.com/paper/2207.08257/) (2022)
- [The Sample Complexity Of ERMs In Stochastic Convex Optimization](https://mlsanity.com/paper/2311.05398/) (2023)
- [Thinking Outside the Ball: Optimal Learning with Gradient Descent for Generalized Linear Stochastic Convex Optimization](https://mlsanity.com/paper/2202.13328/) (2022)
- [Lower Generalization Bounds for GD and SGD in Smooth Stochastic Convex Optimization](https://mlsanity.com/paper/2303.10758/) (2023)
- [The Dimension Strikes Back with Gradients: Generalization of Gradient Methods in Stochastic Convex Optimization](https://mlsanity.com/paper/2401.12058/) (2024)
- [The Sample Complexity of Gradient Descent in Stochastic Convex Optimization](https://mlsanity.com/paper/2404.04931/) (2024)
- [Select without Fear: Almost All Mini-Batch Schedules Generalize Optimally](https://mlsanity.com/paper/2305.02247/) (2023)
- [Initialization-Dependent Sample Complexity of Linear Predictors and Neural Networks](https://mlsanity.com/paper/2305.16475/) (2023)
- [Flat Minima and Generalization: Insights from Stochastic Convex Optimization](https://mlsanity.com/paper/2511.03548/) (2025)
- [Soft ascent-descent as a stable and flexible alternative to flooding](https://mlsanity.com/paper/2310.10006/) (2023)
- [Rapid Overfitting of Multi-Pass Stochastic Gradient Descent in Stochastic Convex Optimization](https://mlsanity.com/paper/2505.08306/) (2025)
- [Towards Better Generalization: Weight Decay Induces Low-rank Bias for Neural Networks](https://mlsanity.com/paper/2410.02176/) (2024)
- [Black-Box Generalization: Stability of Zeroth-Order Learning](https://mlsanity.com/paper/2202.06880/) (2022)
- [Characterizing the Accuracy-Communication-Privacy Trade-off in Distributed Stochastic Convex Optimization](https://mlsanity.com/paper/2501.03222/) (2025)

## Abstract (arXiv)

In stochastic convex optimization the goal is to minimize a convex function F(x) doteq mathbf E_mathbf f~ D[mathbf f(x)] over a convex set cal K subset mathbb Rd where D is some unknown distribution and each f(·) in the support of D is convex over cal K. The optimization is commonly based on i.i.d.~samples f1,f2,ldots,fn from D. A standard approach to such problems is empirical risk minimization (ERM) that optimizes FS(x) doteq frac1nsumi≤ n fi(x). Here we consider the question of how many samples are necessary for ERM to succeed and the closely related question of uniform convergence of FS to F over cal K. We demonstrate that in the standard ℓp/ℓq setting of Lipschitz-bounded functions over a cal K of bounded radius, ERM requires sample size that scales linearly with the dimension d. This nearly matches standard upper bounds and improves on Omega(log d) dependence proved for ℓ2/ℓ2 setting by Shalev-Shwartz et al. (2009). In stark contrast, these problems can be solved using dimension-independent number of samples for ℓ2/ℓ2 setting and log d dependence for ℓ1/ℓ_∞ setting using other approaches. We further show that our lower bound applies even if the functions in the support of D are smooth and efficiently computable and even if an ℓ1 regularization term is added. Finally, we demonstrate that for a more general class of bounded-range (but not Lipschitz-bounded) stochastic convex programs an infinite gap appears already in dimension 2.