mlsanityData to 7 Oct 2026

All ERMs Can Fail in Stochastic Convex Optimization Lower Bounds in Linear Dimension

arXiv 2602.08350 ↗First posted 9 Feb 2026cs.LG stat.MLcited by 0

Not on the map. Why?

Abstract (arXiv)

We study the sample complexity of the best-case Empirical Risk Minimizer in the setting of stochastic convex optimization. We show that there exists an instance in which the sample size is linear in the dimension, learning is possible, but the Empirical Risk Minimizer is likely to be unique and to overfit. This resolves an open question by Feldman. We also extend this to approximate ERMs. Building on our construction we also show that (constrained) Gradient Descent potentially overfits when horizon and learning rate grow w.r.t sample size. Specifically we provide a novel generalization lower bound of Omegaleft(√η T/m1.5right) for Gradient Descent, where η is the learning rate, T is the horizon and m is the sample size. This narrows down, exponentially, the gap between the best known upper bound of O(η T/m) and existing lower bounds from previous constructions.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 24 of its 40 references that are in the map. First posted on arXiv 9 Feb 2026.

Builds on

24 of 40 references.

References · 24

  1. 2019Introduction to Online Convex Optimizationcited by 793
  2. 2014Convex Optimization: Algorithms and Complexitycited by 569
  3. 2019Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networkscited by 562
  4. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 547
  5. 2014In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learningcited by 339
  6. 2018Deep learning generalizes because the parameter-function map is biased towards simple functionscited by 180
  7. 2020Stability of Stochastic Gradient Descent on Nonsmooth Convex Lossescited by 172
  8. 2020The Neural Tangent Kernel in High Dimensions: Triple Descent and a Multi-Scale Theory of Generalizationcited by 101
  9. 2020Is SGD a Bayesian sampler? Well, almostcited by 50
  10. 2021SGD Generalizes Better Than GD (And Regularization Doesn't Help)cited by 38
  11. 2016Generalization of ERM in Stochastic Convex Optimization: The Dimension Strikes Backcited by 37
  12. 2021SGD: The Role of Implicit Regularization, Batch-size and Multiple-epochscited by 22
12 more
  1. 2022Benign Underfitting of Stochastic Gradient Descentcited by 18
  2. 2020Can Implicit Bias Explain Generalization? Stochastic Convex Optimization as a Case Studycited by 16
  3. 2023Information Theoretic Lower Bounds for Information Theoretic Upper Boundscited by 16
  4. 2021Never Go Full Batch (in Stochastic Convex Optimization)cited by 14
  5. 2024Information Complexity of Stochastic Convex Optimization: Applications to Generalization and Memorizationcited by 12
  6. 2023The Sample Complexity Of ERMs In Stochastic Convex Optimizationcited by 8
  7. 2022Thinking Outside the Ball: Optimal Learning with Gradient Descent for Generalized Linear Stochastic Convex Optimizationcited by 7
  8. 2023Lower Generalization Bounds for GD and SGD in Smooth Stochastic Convex Optimizationcited by 6
  9. 2024The Dimension Strikes Back with Gradients: Generalization of Gradient Methods in Stochastic Convex Optimizationcited by 5
  10. 2024The Sample Complexity of Gradient Descent in Stochastic Convex Optimizationcited by 5
  11. 2024Provable Tempered Overfitting of Minimal Nets and Typical Netscited by 5
  12. 2022A Framework for Overparameterized Learningcited by 2

Built on by

Not cited yet.