mlsanityData to 14 Oct 2026

Minibatch and Local SGD: Algorithmic Stability and Linear Speedup in Generalization

arXiv 2310.01139 ↗First posted 2 Oct 2023cs.LG cs.AIcited by 5

Not on the map. Why?

Abstract (arXiv)

The increasing scale of data propels the popularity of leveraging parallelism to speed up the optimization. Minibatch stochastic gradient descent (minibatch SGD) and local SGD are two popular methods for parallel optimization. The existing theoretical studies show a linear speedup of these methods with respect to the number of machines, which, however, is measured by optimization errors in a multi-pass setting. As a comparison, the stability and generalization of these methods are much less studied. In this paper, we study the stability and generalization analysis of minibatch and local SGD to understand their learnability by introducing an expectation-variance decomposition. We incorporate training errors into the stability analysis, which shows how small training errors help generalization for overparameterized models. We show minibatch and local SGD achieve a linear speedup to attain the optimal risk bounds.

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

Builds on

38 of 53 references.

References · 38

  1. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,669
  2. 2016Federated Learning: Strategies for Improving Communication Efficiencycited by 1,475
  3. 2016On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minimacited by 1,352
  4. 2018Local SGD Converges Fast and Communicates Littlecited by 605
  5. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 552
  6. 2019Agnostic Federated Learningcited by 456
  7. 2018Parallel Restarted SGD with Faster Convergence and Less Communication: Demystifying Why Model Averaging Works for Deep Learningcited by 278
  8. 2019Tighter Theory for Local SGD on Identical and Heterogeneous Datacited by 266
  9. 2018Don't Use Large Mini-Batches, Use Local SGDcited by 202
  10. 2019Private Stochastic Convex Optimization with Optimal Ratescited by 186
  11. 2020Stability of Stochastic Gradient Descent on Nonsmooth Convex Lossescited by 173
  12. 2020Is Local SGD Better than Minibatch SGD?cited by 151
26 more
  1. 2020Minibatch vs Local SGD for Heterogeneous Distributed Learningcited by 147
  2. 2013Mini-batch Stochastic Approximation Methods for Nonconvex Stochastic Composite Optimizationcited by 143
  3. 2020Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descentcited by 119
  4. 2017Stability and Generalization of Learning Algorithms that Converge to Global Optimacited by 100
  5. 2019High probability generalization bounds for uniformly stable algorithms with nearly optimal ratecited by 98
  6. 2019Sharper bounds for uniformly stable algorithmscited by 93
  7. 2017Data-Dependent Stability of Stochastic Gradient Descentcited by 92
  8. 2017Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpointscited by 82
  9. 2020SGD for Structured Nonconvex Functions: Learning Rates, Minibatching and Interpolationcited by 67
  10. 2018Optimal Rates for Spectral Algorithms with Least-Squares Regression over Hilbert Spacescited by 59
  11. 2018Stability and Convergence Trade-off of Iterative Optimization Algorithmscited by 53
  12. 2016Distributed learning with regularized least squarescited by 42
  13. 2021Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyondcited by 36
  14. 2018Learning with SGD and Random Featurescited by 33
  15. 2021Stability of SGD: Tightness Analysis and Improved Boundscited by 33
  16. 2022Stability vs Implicit Bias of Gradient Methods on Separable Data and Beyondcited by 29
  17. 2023Understanding Generalization of Federated Learning via Stability: Heterogeneity Matterscited by 27
  18. 2021Differentially Private SGD with Non-Smooth Lossescited by 22
  19. 2019Beating SGD Saturation with Tail-Averaging and Minibatchingcited by 21
  20. 2021Communication-efficient SGD: From Local SGD to One-Shot Averagingcited by 19
  21. 2022Benign Underfitting of Stochastic Gradient Descentcited by 19
  22. 2021DESTRESS: Computation-Optimal and Communication-Efficient Decentralized Nonconvex Finite-Sum Optimizationcited by 16
  23. 2021Minimax Estimation for Personalized Federated Learning: An Alternative between FedAvg and Local Training?cited by 15
  24. 2015Unregularized Online Learning Algorithms with General Loss Functionscited by 11
  25. 2022Capacity dependent analysis for functional online learning algorithmscited by 10
  26. 2017Total stability of kernel methodscited by 5

Built on by

Cited by year

Citing papers per year: 2024: 3; 2025: 2.

5 papers.

  1. 2024Bootstrap SGD: Algorithmic Stability and Robustnesscited by 0
  2. 2024Stability and Generalization for Distributed SGDAcited by 0
  3. 2024How Does the Smoothness Approximation Method Facilitate Generalization for Federated Adversarial Learning?cited by 0
  4. 2025Stability-based Generalization Analysis of Randomized Coordinate Descent for Pairwise Learningcited by 0
  5. 2025Generalization and Optimization of SGD with Lookaheadcited by 0