# Never Go Full Batch (in Stochastic Convex Optimization)

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 34 references that are in the map.
- First posted on arXiv 29 Jun 2021.

## Builds on (most cited first, 17 of 17)

- [On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima](https://mlsanity.com/paper/1609.04836/) (2016)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [The Implicit Bias of Gradient Descent on Separable Data](https://mlsanity.com/paper/1710.10345/) (2017)
- [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015)
- [Train longer, generalize better: closing the generalization gap in large batch training of neural networks](https://mlsanity.com/paper/1705.08741/) (2017)
- [Implicit Bias of Gradient Descent on Linear Convolutional Networks](https://mlsanity.com/paper/1806.00468/) (2018)
- [Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses](https://mlsanity.com/paper/2006.06914/) (2020)
- [Lower Bounds for Finding Stationary Points I](https://mlsanity.com/paper/1710.11606/) (2017)
- [Tight Complexity Bounds for Optimizing Composite Objectives](https://mlsanity.com/paper/1605.08003/) (2016)
- [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)
- [Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimization](https://mlsanity.com/paper/1805.10222/) (2018)
- [Acceleration with a Ball Optimization Oracle](https://mlsanity.com/paper/2003.08078/) (2020)
- [On Lower Complexity Bounds for Large-Scale Smooth Convex Optimization](https://mlsanity.com/paper/1307.5001/) (2013)
- [Complexity of Highly Parallel Non-Smooth Convex Optimization](https://mlsanity.com/paper/1906.10655/) (2019)
- [Lower Bounds for Parallel and Randomized Convex Optimization](https://mlsanity.com/paper/1811.01903/) (2018)
- [Can Implicit Bias Explain Generalization? Stochastic Convex Optimization as a Case Study](https://mlsanity.com/paper/2003.06152/) (2020)

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

- [Stochastic Training is Not Necessary for Generalization](https://mlsanity.com/paper/2109.14119/) (2021)
- [Beyond Lipschitz: Sharp Generalization and Excess Risk Bounds for Full-Batch GD](https://mlsanity.com/paper/2204.12446/) (2022)
- [Differentially Private Generalized Linear Models Revisited](https://mlsanity.com/paper/2205.03014/) (2022)
- [Information Theoretic Lower Bounds for Information Theoretic Upper Bounds](https://mlsanity.com/paper/2302.04925/) (2023)
- [Information Complexity of Stochastic Convex Optimization: Applications to Generalization and Memorization](https://mlsanity.com/paper/2402.09327/) (2024)
- [The Sample Complexity Of ERMs In Stochastic Convex Optimization](https://mlsanity.com/paper/2311.05398/) (2023)
- [Thinking Outside the Ball: Optimal Learning with Gradient Descent for Generalized Linear Stochastic Convex Optimization](https://mlsanity.com/paper/2202.13328/) (2022)
- [The Dimension Strikes Back with Gradients: Generalization of Gradient Methods in Stochastic Convex Optimization](https://mlsanity.com/paper/2401.12058/) (2024)
- [The Sample Complexity of Gradient Descent in Stochastic Convex Optimization](https://mlsanity.com/paper/2404.04931/) (2024)
- [Select without Fear: Almost All Mini-Batch Schedules Generalize Optimally](https://mlsanity.com/paper/2305.02247/) (2023)
- [Black-Box Generalization: Stability of Zeroth-Order Learning](https://mlsanity.com/paper/2202.06880/) (2022)
- [Making Progress Based on False Discoveries](https://mlsanity.com/paper/2204.08809/) (2022)
- [All ERMs Can Fail in Stochastic Convex Optimization Lower Bounds in Linear Dimension](https://mlsanity.com/paper/2602.08350/) (2026)
- [Generalization Bounds of Stochastic Gradient Descent in Homogeneous Neural Networks](https://mlsanity.com/paper/2602.22936/) (2026)

## Abstract (arXiv)

We study the generalization performance of full-batch optimization algorithms for stochastic convex optimization: these are first-order methods that only access the exact gradient of the empirical risk (rather than gradients with respect to individual data points), that include a wide range of algorithms such as gradient descent, mirror descent, and their regularized and/or accelerated variants. We provide a new separation result showing that, while algorithms such as stochastic gradient descent can generalize and optimize the population risk to within ε after O(1/ε2) iterations, full-batch methods either need at least Omega(1/ε4) iterations or exhibit a dimension-dependent sample complexity.