mlsanityData to 7 Oct 2026

Thinking Outside the Ball: Optimal Learning with Gradient Descent for Generalized Linear Stochastic Convex Optimization

arXiv 2202.13328 ↗First posted 27 Feb 2022cs.LG math.OCcited by 7

Not on the map. Why?

Abstract (arXiv)

We consider linear prediction with a convex Lipschitz loss, or more generally, stochastic convex optimization problems of generalized linear form, i.e.~where each instantaneous loss is a scalar convex function of a linear function. We show that in this setting, early stopped Gradient Descent (GD), without any explicit regularization or projection, ensures excess error at most ε (compared to the best possible with unit Euclidean norm) with an optimal, up to logarithmic factors, sample complexity of tildeO(1/ε2) and only tildeO(1/ε2) iterations. This contrasts with general stochastic convex optimization, where Omega(1/ε4) iterations are needed Amir et al. [2021b]. The lower iteration complexity is ensured by leveraging uniform convergence rather than stability. But instead of uniform convergence in a norm ball, which we show can guarantee suboptimal learning using Theta(1/ε4) samples, we rely on uniform convergence in a distribution-dependent ball.

Key facts. Cited by 7 papers in the map (data through 7 Oct 2026). Builds on 29 of its 46 references that are in the map. First posted on arXiv 27 Feb 2022.

Builds on

29 of 46 references.

References · 29

  1. 2019Introduction to Online Convex Optimizationcited by 793
  2. 2017The Implicit Bias of Gradient Descent on Separable Datacited by 649
  3. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 547
  4. 2019Implicit Regularization in Deep Matrix Factorizationcited by 402
  5. 2014In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learningcited by 339
  6. 2017Implicit Regularization in Matrix Factorizationcited by 318
  7. 2019Gradient Descent Maximizes the Margin of Homogeneous Neural Networkscited by 308
  8. 2020Kernel and Rich Regimes in Overparametrized Modelscited by 302
  9. 2020Implicit Bias of Gradient Descent for Wide Two-layer Neural Networks Trained with the Logistic Losscited by 267
  10. 2018Characterizing Implicit Bias in Terms of Optimization Geometrycited by 259
  11. 2018Implicit Bias of Gradient Descent on Linear Convolutional Networkscited by 251
  12. 2019Uniform convergence may be unable to explain generalization in deep learningcited by 223
17 more
  1. 2020Stability of Stochastic Gradient Descent on Nonsmooth Convex Lossescited by 172
  2. 2019Implicit regularization for deep neural networks driven by an Ornstein-Uhlenbeck like processcited by 123
  3. 2021Implicit Bias of SGD for Diagonal Linear Networks: a Provable Benefit of Stochasticitycited by 107
  4. 2020Shape Matters: Understanding the Implicit Bias of the Noise Covariancecited by 88
  5. 2020Implicit Bias in Deep Linear Classification: Initialization Scale vs Training Accuracycited by 70
  6. 2020Gradient descent follows the regularization path for general lossescited by 57
  7. 2019Lexicographic and Depth-Sensitive Margins in Homogeneous and Non-Homogeneous Deep Modelscited by 53
  8. 2021Implicit Regularization in Tensor Factorizationcited by 43
  9. 2018Uniform Convergence of Gradients for Non-Convex Learning and Optimizationcited by 38
  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. 2013Margins, Shrinkage, and Boostingcited by 35
  13. 2020Gradient Methods Never Overfit On Separable Datacited by 29
  14. 2021SGD: The Role of Implicit Regularization, Batch-size and Multiple-epochscited by 22
  15. 2020The Statistical Complexity of Early-Stopped Mirror Descentcited by 19
  16. 2020Can Implicit Bias Explain Generalization? Stochastic Convex Optimization as a Case Studycited by 16
  17. 2021Never Go Full Batch (in Stochastic Convex Optimization)cited by 14

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 1; 2023: 1; 2024: 3; 2025: 1; 2026: 1.

7 papers.

  1. 2024Uniform Generalization Bounds on Data-Dependent Hypothesis Sets via PAC-Bayesian Theory on Random Setscited by 9
  2. 2022Generalization Bounds of Nonconvex-(Strongly)-Concave Stochastic Minimax Optimizationcited by 6
  3. 2023Select without Fear: Almost All Mini-Batch Schedules Generalize Optimallycited by 5
  4. 2024The Sample Complexity of Gradient Descent in Stochastic Convex Optimizationcited by 5
  5. 2024Loss Gradient Gaussian Width based Generalization and Optimization Guaranteescited by 0
  6. 2025Generalization Bound of Gradient Flow through Training Trajectory and Data-dependent Kernelcited by 0
  7. 2026All ERMs Can Fail in Stochastic Convex Optimization Lower Bounds in Linear Dimensioncited by 0