mlsanityData to 7 Oct 2026

SGD: The Role of Implicit Regularization, Batch-size and Multiple-epochs

arXiv 2107.05074 ↗First posted 11 Jul 2021cs.LG cs.AIcited by 22

Not on the map. Why?

Abstract (arXiv)

Multi-epoch, small-batch, Stochastic Gradient Descent (SGD) has been the method of choice for learning with large over-parameterized models. A popular theory for explaining why SGD works well in practice is that the algorithm has an implicit regularization that biases its output towards a good solution. Perhaps the theoretically most well understood learning setting for SGD is that of Stochastic Convex Optimization (SCO), where it is well known that SGD learns at a rate of O(1/√n), where n is the number of samples. In this paper, we consider the problem of SCO and explore the role of implicit regularization, batch size and multiple epochs for SGD. Our main contributions are threefold: (a) We show that for any regularizer, there is an SCO problem for which Regularized Empirical Risk Minimzation fails to learn. This automatically rules out any implicit regularization based explanation for the success of SGD. (b) We provide a separation between SGD and learning via Gradient Descent on empirical loss (GD) in terms of sample complexity. We show that there is an SCO problem such that GD with any step size and number of iterations can only learn at a suboptimal rate: at least widetildeOmega(1/n5/12). (c) We present a multi-epoch variant of SGD commonly used in practice. We prove that this algorithm is at least as good as single pass SGD in the worst case. However, for certain SCO problems, taking multiple passes over the dataset can significantly outperform single pass SGD. We extend our results to the general learning setting by showing a problem which is learnable for any data distribution, and for this problem, SGD is strictly better than RERM for any regularization function. We conclude by discussing the implications of our results for deep learning, and show a separation between SGD and ERM for two layer diagonal neural networks.

Key facts. Cited by 22 papers in the map (data through 7 Oct 2026). Builds on 21 of its 35 references that are in the map. First posted on arXiv 11 Jul 2021.

Builds on

21 of 35 references.

References · 21

  1. 2016Understanding deep learning requires rethinking generalizationcited by 1,657
  2. 2016On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minimacited by 1,337
  3. 2017The Implicit Bias of Gradient Descent on Separable Datacited by 649
  4. 2019Implicit Regularization in Deep Matrix Factorizationcited by 402
  5. 2018Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layerscited by 340
  6. 2017Implicit Regularization in Matrix Factorizationcited by 318
  7. 2018On the Optimization of Deep Networks: Implicit Acceleration by Overparameterizationcited by 280
  8. 2018Characterizing Implicit Bias in Terms of Optimization Geometrycited by 259
  9. 2018Implicit Bias of Gradient Descent on Linear Convolutional Networkscited by 251
  10. 2020Stability of Stochastic Gradient Descent on Nonsmooth Convex Lossescited by 172
  11. 2017The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learningcited by 150
  12. 2020Implicit Regularization in Deep Learning May Not Be Explainable by Normscited by 118
9 more
  1. 2018An Alternative View: When Does SGD Escape Local Minima?cited by 115
  2. 2018On the Convergence Rate of Training Recurrent Neural Networkscited by 82
  3. 2018Risk and parameter convergence of logistic regressioncited by 81
  4. 2021Benign Overfitting of Constant-Stepsize SGD for Linear Regressioncited by 71
  5. 2019SGD Converges to Global Minimum in Deep Learning via Star-convex Pathcited by 39
  6. 2021SGD Generalizes Better Than GD (And Regularization Doesn't Help)cited by 38
  7. 2016Generalization of ERM in Stochastic Convex Optimization: The Dimension Strikes Backcited by 37
  8. 2019Can SGD Learn Recurrent Neural Networks with Provable Generalization?cited by 17
  9. 2020Can Implicit Bias Explain Generalization? Stochastic Convex Optimization as a Case Studycited by 16

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 7; 2023: 4; 2024: 6; 2025: 2; 2026: 3.

22 papers.

Sort:

  1. 2023Momentum Provably Improves Error Feedback!cited by 31
  2. 2022Benign Underfitting of Stochastic Gradient Descentcited by 18
  3. 2022Limitations of Information-Theoretic Generalization Bounds for Gradient Descent Methods in Stochastic Convex Optimizationcited by 18
  4. 2022On the Overlooked Structure of Stochastic Gradientscited by 13
  5. 2024Non-convex Stochastic Composite Optimization with Polyak Momentumcited by 9
  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. 2022Benign Overfitting in Classification: Provably Counter Label Noise with Larger Modelscited by 5
  10. 2022From Gradient Flow on Population Loss to Learning with Stochastic Gradient Descentcited by 5
  11. 2023Deep ReLU Networks Have Surprisingly Simple Polytopescited by 5
  12. 2024The Dimension Strikes Back with Gradients: Generalization of Gradient Methods in Stochastic Convex Optimizationcited by 5
10 more
  1. 2024The Sample Complexity of Gradient Descent in Stochastic Convex Optimizationcited by 5
  2. 2024Towards Faster Decentralized Stochastic Optimization with Communication Compressioncited by 4
  3. 2022Losing momentum in continuous-time stochastic optimisationcited by 2
  4. 2024Improving Implicit Regularization of SGD with Preconditioning for Least Square Problemscited by 2
  5. 2025Rapid Overfitting of Multi-Pass Stochastic Gradient Descent in Stochastic Convex Optimizationcited by 2
  6. 2025Stochastic Difference-of-Convex Optimization with Momentumcited by 2
  7. 2024Improving the Convergence Rates of Forward Gradient Descent with Repeated Samplingcited by 1
  8. 2026All ERMs Can Fail in Stochastic Convex Optimization Lower Bounds in Linear Dimensioncited by 0
  9. 2026Generalization Bounds of Stochastic Gradient Descent in Homogeneous Neural Networkscited by 0
  10. 2026Less Data, Faster Training: repeating smaller datasets speeds up learning via sampling biasescited by 0