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

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

## 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 (most cited first, 30 of 36)

- [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015)
- [Information-theoretic analysis of generalization capability of learning algorithms](https://mlsanity.com/paper/1705.07809/) (2017)
- [Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses](https://mlsanity.com/paper/2006.06914/) (2020)
- [Information-Theoretic Generalization Bounds for SGLD via Data-Dependent Estimates](https://mlsanity.com/paper/1911.02151/) (2019)
- [Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent](https://mlsanity.com/paper/2006.08157/) (2020)
- [Stability and Generalization of Learning Algorithms that Converge to Global Optima](https://mlsanity.com/paper/1710.08402/) (2017)
- [High probability generalization bounds for uniformly stable algorithms with nearly optimal rate](https://mlsanity.com/paper/1902.10710/) (2019)
- [Sharper bounds for uniformly stable algorithms](https://mlsanity.com/paper/1910.07833/) (2019)
- [Data-Dependent Stability of Stochastic Gradient Descent](https://mlsanity.com/paper/1703.01678/) (2017)
- [Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpoints](https://mlsanity.com/paper/1707.05947/) (2017)
- [Generalization Error Bounds for Noisy, Iterative Algorithms](https://mlsanity.com/paper/1801.04295/) (2018)
- [Stochastic Gradient Descent on Separable Data: Exact Convergence with a Fixed Learning Rate](https://mlsanity.com/paper/1806.01796/) (2018)
- [How Good is SGD with Random Shuffling?](https://mlsanity.com/paper/1908.00045/) (2019)
- [Stochastic Training is Not Necessary for Generalization](https://mlsanity.com/paper/2109.14119/) (2021)
- [On Generalization Error Bounds of Noisy Gradient Methods for Non-Convex Learning](https://mlsanity.com/paper/1902.00621/) (2019)
- [Generalization Bounds for Uniformly Stable Algorithms](https://mlsanity.com/paper/1812.09859/) (2018)
- [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)
- [Generalization of ERM in Stochastic Convex Optimization: The Dimension Strikes Back](https://mlsanity.com/paper/1608.04414/) (2016)
- [Stability of SGD: Tightness Analysis and Improved Bounds](https://mlsanity.com/paper/2102.05274/) (2021)
- [Stability vs Implicit Bias of Gradient Methods on Separable Data and Beyond](https://mlsanity.com/paper/2202.13441/) (2022)
- [Time-independent Generalization Bounds for SGLD in Non-convex Settings](https://mlsanity.com/paper/2111.12876/) (2021)
- [Stability and Generalization Analysis of Gradient Methods for Shallow Neural Networks](https://mlsanity.com/paper/2209.09298/) (2022)
- [Generalization and Stability of Interpolating Neural Networks with Minimal Width](https://mlsanity.com/paper/2302.09235/) (2023)
- [On the Generalization of Stochastic Gradient Descent with Momentum](https://mlsanity.com/paper/1809.04564/) (2018)
- [Beyond Lipschitz: Sharp Generalization and Excess Risk Bounds for Full-Batch GD](https://mlsanity.com/paper/2204.12446/) (2022)
- [Limitations of Information-Theoretic Generalization Bounds for Gradient Descent Methods in Stochastic Convex Optimization](https://mlsanity.com/paper/2212.13556/) (2022)
- [Information Theoretic Lower Bounds for Information Theoretic Upper Bounds](https://mlsanity.com/paper/2302.04925/) (2023)
- [Characterizing & Finding Good Data Orderings for Fast Convergence of Sequential Gradient Methods](https://mlsanity.com/paper/2202.01838/) (2022)
- [Black-box tests for algorithmic stability](https://mlsanity.com/paper/2111.15546/) (2021)

## Built on by (most cited first, 5 of 5)

- [Repeated Random Sampling for Minimizing the Time-to-Accuracy of Learning](https://mlsanity.com/paper/2305.18424/) (2023)
- [Continual Learning with Neuromorphic Computing: Foundations, Methods, and Emerging Applications](https://mlsanity.com/paper/2410.09218/) (2024)
- [Rapid Overfitting of Multi-Pass Stochastic Gradient Descent in Stochastic Convex Optimization](https://mlsanity.com/paper/2505.08306/) (2025)
- [Understanding Generalization of Federated Learning: the Trade-off between Model Stability and Optimization](https://mlsanity.com/paper/2411.16303/) (2024)
- [Stability-based Generalization Analysis of Randomized Coordinate Descent for Pairwise Learning](https://mlsanity.com/paper/2503.01530/) (2025)

## 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.