mlsanityData to 14 Oct 2026

Select without Fear: Almost All Mini-Batch Schedules Generalize Optimally

arXiv 2305.02247 ↗First posted 3 May 2023cs.LG stat.MLcited by 5

Not on the map. Why?

Abstract (arXiv)

We establish matching upper and lower generalization error bounds for mini-batch Gradient Descent (GD) training with either deterministic or stochastic, data-independent, but otherwise arbitrary batch selection rules. We consider smooth Lipschitz-convex/nonconvex/strongly-convex loss functions, and show that classical upper bounds for Stochastic GD (SGD) also hold verbatim for such arbitrary nonadaptive batch schedules, including all deterministic ones. Further, for convex and strongly-convex losses we prove matching lower bounds directly on the generalization error uniform over the aforementioned class of batch schedules, showing that all such batch schedules generalize optimally. Lastly, for smooth (non-Lipschitz) nonconvex losses, we show that full-batch (deterministic) GD is essentially optimal, among all possible batch schedules within the considered class, including all stochastic ones.

Key facts. Cited by 5 papers in the map (data through 14 Oct 2026). Builds on 36 of its 49 references that are in the map. First posted on arXiv 3 May 2023.

Builds on

36 of 49 references.

References · 36

  1. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 552
  2. 2017Information-theoretic analysis of generalization capability of learning algorithmscited by 303
  3. 2020Stability of Stochastic Gradient Descent on Nonsmooth Convex Lossescited by 173
  4. 2019Information-Theoretic Generalization Bounds for SGLD via Data-Dependent Estimatescited by 119
  5. 2020Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descentcited by 119
  6. 2017Stability and Generalization of Learning Algorithms that Converge to Global Optimacited by 100
  7. 2019High probability generalization bounds for uniformly stable algorithms with nearly optimal ratecited by 98
  8. 2019Sharper bounds for uniformly stable algorithmscited by 93
  9. 2017Data-Dependent Stability of Stochastic Gradient Descentcited by 92
  10. 2017Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpointscited by 82
  11. 2018Generalization Error Bounds for Noisy, Iterative Algorithmscited by 82
  12. 2018Stochastic Gradient Descent on Separable Data: Exact Convergence with a Fixed Learning Ratecited by 64
24 more
  1. 2019How Good is SGD with Random Shuffling?cited by 64
  2. 2021Stochastic Training is Not Necessary for Generalizationcited by 63
  3. 2019On Generalization Error Bounds of Noisy Gradient Methods for Non-Convex Learningcited by 57
  4. 2018Generalization Bounds for Uniformly Stable Algorithmscited by 56
  5. 2021Stability and Deviation Optimal Risk Bounds with Convergence Rate O(1/n)cited by 42
  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. 2021Stability of SGD: Tightness Analysis and Improved Boundscited by 33
  9. 2022Stability vs Implicit Bias of Gradient Methods on Separable Data and Beyondcited by 29
  10. 2021Time-independent Generalization Bounds for SGLD in Non-convex Settingscited by 27
  11. 2022Stability and Generalization Analysis of Gradient Methods for Shallow Neural Networkscited by 21
  12. 2023Generalization and Stability of Interpolating Neural Networks with Minimal Widthcited by 21
  13. 2018On the Generalization of Stochastic Gradient Descent with Momentumcited by 20
  14. 2022Beyond Lipschitz: Sharp Generalization and Excess Risk Bounds for Full-Batch GDcited by 19
  15. 2022Limitations of Information-Theoretic Generalization Bounds for Gradient Descent Methods in Stochastic Convex Optimizationcited by 19
  16. 2023Information Theoretic Lower Bounds for Information Theoretic Upper Boundscited by 17
  17. 2022Characterizing & Finding Good Data Orderings for Fast Convergence of Sequential Gradient Methodscited by 16
  18. 2021Black-box tests for algorithmic stabilitycited by 15
  19. 2021Never Go Full Batch (in Stochastic Convex Optimization)cited by 14
  20. 2022On Generalization of Decentralized Learning with Separable Datacited by 8
  21. 2017Stochastic Nonconvex Optimization with Large Minibatchescited by 7
  22. 2022Thinking Outside the Ball: Optimal Learning with Gradient Descent for Generalized Linear Stochastic Convex Optimizationcited by 7
  23. 2023Lower Generalization Bounds for GD and SGD in Smooth Stochastic Convex Optimizationcited by 6
  24. 2021Stability and Generalization for Randomized Coordinate Descentcited by 4

Built on by

Cited by year

Citing papers per year: 2023: 1; 2024: 2; 2025: 2.

5 papers.

  1. 2023Repeated Random Sampling for Minimizing the Time-to-Accuracy of Learningcited by 26
  2. 2024Continual Learning with Neuromorphic Computing: Foundations, Methods, and Emerging Applicationscited by 8
  3. 2025Rapid Overfitting of Multi-Pass Stochastic Gradient Descent in Stochastic Convex Optimizationcited by 3
  4. 2024Understanding Generalization of Federated Learning: the Trade-off between Model Stability and Optimizationcited by 0
  5. 2025Stability-based Generalization Analysis of Randomized Coordinate Descent for Pairwise Learningcited by 0