mlsanityData to 7 Oct 2026

Never Go Full Batch (in Stochastic Convex Optimization)

arXiv 2107.00469 ↗First posted 29 Jun 2021math.OC cs.LGcited by 14

Not on the map. Why?

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.

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

Builds on

17 of 34 references.

References · 17

  1. 2016On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minimacited by 1,337
  2. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,140
  3. 2017The Implicit Bias of Gradient Descent on Separable Datacited by 649
  4. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 547
  5. 2017Train longer, generalize better: closing the generalization gap in large batch training of neural networkscited by 278
  6. 2018Implicit Bias of Gradient Descent on Linear Convolutional Networkscited by 251
  7. 2020Stability of Stochastic Gradient Descent on Nonsmooth Convex Lossescited by 172
  8. 2017Lower Bounds for Finding Stationary Points Icited by 125
  9. 2016Tight Complexity Bounds for Optimizing Composite Objectivescited by 47
  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. 2018Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimizationcited by 34
5 more
  1. 2020Acceleration with a Ball Optimization Oraclecited by 31
  2. 2013On Lower Complexity Bounds for Large-Scale Smooth Convex Optimizationcited by 24
  3. 2019Complexity of Highly Parallel Non-Smooth Convex Optimizationcited by 21
  4. 2018Lower Bounds for Parallel and Randomized Convex Optimizationcited by 17
  5. 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: 2021: 1; 2022: 5; 2023: 3; 2024: 3; 2025: 0; 2026: 2.

14 papers.

Sort:

  1. 2021Stochastic Training is Not Necessary for Generalizationcited by 63
  2. 2022Beyond Lipschitz: Sharp Generalization and Excess Risk Bounds for Full-Batch GDcited by 19
  3. 2022Differentially Private Generalized Linear Models Revisitedcited by 17
  4. 2023Information Theoretic Lower Bounds for Information Theoretic Upper Boundscited by 16
  5. 2024Information Complexity of Stochastic Convex Optimization: Applications to Generalization and Memorizationcited by 12
  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. 2023Select without Fear: Almost All Mini-Batch Schedules Generalize Optimallycited by 5
  9. 2024The Dimension Strikes Back with Gradients: Generalization of Gradient Methods in Stochastic Convex Optimizationcited by 5
  10. 2024The Sample Complexity of Gradient Descent in Stochastic Convex Optimizationcited by 5
  11. 2022Black-Box Generalization: Stability of Zeroth-Order Learningcited by 1
  12. 2022Making Progress Based on False Discoveriescited by 0
2 more
  1. 2026All ERMs Can Fail in Stochastic Convex Optimization Lower Bounds in Linear Dimensioncited by 0
  2. 2026Generalization Bounds of Stochastic Gradient Descent in Homogeneous Neural Networkscited by 0