mlsanityData to 7 Oct 2026

Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond

arXiv 2110.10342 ↗First posted 20 Oct 2021cs.LG math.OC stat.MLcited by 35

Not on the map. Why?

Abstract (arXiv)

In distributed learning, local SGD (also known as federated averaging) and its simple baseline minibatch SGD are widely studied optimization methods. Most existing analyses of these methods assume independent and unbiased gradient estimates obtained via with-replacement sampling. In contrast, we study shuffling-based variants: minibatch and local Random Reshuffling, which draw stochastic gradients without replacement and are thus closer to practice. For smooth functions satisfying the Polyak-Lojasiewicz condition, we obtain convergence bounds (in the large epoch regime) which show that these shuffling-based variants converge faster than their with-replacement counterparts. Moreover, we prove matching lower bounds showing that our convergence analysis is tight. Finally, we propose an algorithmic modification called synchronized shuffling that leads to convergence rates faster than our lower bounds in near-homogeneous settings.

Key facts. Cited by 35 papers in the map (data through 7 Oct 2026). Builds on 18 of its 45 references that are in the map. First posted on arXiv 20 Oct 2021.

Builds on

18 of 45 references.

References · 18

  1. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,592
  2. 2018Federated Optimization in Heterogeneous Networkscited by 2,971
  3. 2016Federated Learning: Strategies for Improving Communication Efficiencycited by 1,461
  4. 2019On the Convergence of FedAvg on Non-IID Datacited by 1,220
  5. 2018Local SGD Converges Fast and Communicates Littlecited by 595
  6. 2019On the Convergence of Local Descent Methods in Federated Learningcited by 150
  7. 2020Random Reshuffling: Simple Analysis with Vast Improvementscited by 112
  8. 2015Why Random Reshuffling Beats Stochastic Gradient Descentcited by 78
  9. 2020A Unified Convergence Analysis for Shuffling-Type Gradient Methodscited by 57
  10. 2021Proximal and Federated Random Reshufflingcited by 33
  11. 2021The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communicationcited by 30
  12. 2017Convergence Analysis of Distributed Stochastic Gradient Descent with Shufflingcited by 23
6 more
  1. 2020SMG: A Shuffling Gradient-Based Method with Momentumcited by 22
  2. 2021Permutation-Based SGD: Is Random Optimal?cited by 16
  3. 2021Random Shuffling Beats SGD Only After Many Epochs on Ill-Conditioned Problemscited by 16
  4. 2020Recht-R'e Noncommutative Arithmetic-Geometric Mean Conjecture is Falsecited by 15
  5. 2020Local SGD With a Communication Overhead Depending Only on the Number of Workerscited by 13
  6. 2020A Unified Linear Speedup Analysis of Federated Averaging and Nesterov FedAvgcited by 4

Built on by

Cited by year

Citing papers per year: 2022: 11; 2023: 13; 2024: 7; 2025: 4.

35 papers.

Sort:

  1. 2023Convergence of AdaGrad for Non-convex Objectives: Simple Proofs and Relaxed Assumptionscited by 55
  2. 2022A Unified Analysis of Federated Learning with Arbitrary Client Participationcited by 45
  3. 2023On the Convergence of Federated Averaging with Cyclic Client Participationcited by 31
  4. 2022Server-Side Stepsizes and Sampling Without Replacement Provably Help in Federated Optimizationcited by 23
  5. 2022Accelerated Federated Learning with Decoupled Adaptive Optimizationcited by 23
  6. 2023Tighter Lower Bounds for Shuffling SGD: Random Permutations and Beyondcited by 21
  7. 2022FedShuffle: Recipes for Better Use of Local Work in Federated Learningcited by 19
  8. 2022Federated Optimization Algorithms with Random Reshuffling and Gradient Compressioncited by 18
  9. 2023Gradient Descent with Linearly Correlated Noise: Theory and Applications to Differential Privacycited by 18
  10. 2022Characterizing & Finding Good Data Orderings for Fast Convergence of Sequential Gradient Methodscited by 15
  11. 2022Correlated quantization for distributed mean estimation and optimizationcited by 14
  12. 2022Anchor Sampling for Federated Learning with Partial Client Participationcited by 14
23 more
  1. 2023Federated Learning with Regularized Client Participationcited by 13
  2. 2024Randomized Asymmetric Chain of LoRA: The First Meaningful Theoretical Framework for Low-Rank Adaptationcited by 12
  3. 2022Sampling without Replacement Leads to Faster Rates in Finite-Sum Minimax Optimizationcited by 10
  4. 2024Last Iterate Convergence of Incremental Methods and Applications in Continual Learningcited by 10
  5. 2024On the Last-Iterate Convergence of Shuffling Gradient Methodscited by 9
  6. 2022SGDA with shuffling: faster convergence for nonconvex-PL minimax optimizationcited by 8
  7. 2023Federated Minimax Optimization with Client Heterogeneitycited by 8
  8. 2023Coordinating Distributed Example Orders for Provably Accelerated Trainingcited by 7
  9. 2023On Convergence of Incremental Gradient for Non-Convex Smooth Functionscited by 7
  10. 2025Understanding Outer Optimizers in Local SGD: Learning Rates, Momentum, and Accelerationcited by 7
  11. 2022Efficiency Ordering of Stochastic Gradient Descentcited by 6
  12. 2023Empirical Risk Minimization with Shuffled SGD: A Primal-Dual Perspective and Improved Boundscited by 6
  13. 2023Minibatch and Local SGD: Algorithmic Stability and Linear Speedup in Generalizationcited by 5
  14. 2023High Probability Guarantees for Random Reshufflingcited by 5
  15. 2023On the Training Instability of Shuffling SGD with Batch Normalizationcited by 3
  16. 2024Asynchronous Federated Learning: A Scalable Approach for Decentralized Machine Learningcited by 3
  17. 2023Distributed Random Reshuffling Methods with Improved Convergencecited by 2
  18. 2024Does Worst-Performing Agent Lead the Pack? Analyzing Agent Dynamics in Unified Distributed SGDcited by 2
  19. 2025Generalization in Federated Learning: A Conditional Mutual Information Frameworkcited by 2
  20. 2024A KL-based Analysis Framework with Applications to Non-Descent Optimization Methodscited by 1
  21. 2025CycleSL: Server-Client Cyclical Update Driven Scalable Split Learningcited by 1
  22. 2024A Statistical Analysis of Deep Federated Learning for Intrinsically Low-dimensional Datacited by 0
  23. 2025Adjusted Shuffling SARAH: Advancing Complexity Analysis via Dynamic Gradient Weightingcited by 0