mlsanityData to 14 Oct 2026

Federated Optimization Algorithms with Random Reshuffling and Gradient Compression

arXiv 2206.07021 ↗First posted 14 Jun 2022cs.LG math.OCcited by 18

Not on the map. Why?

Abstract (arXiv)

Gradient compression is a popular technique for improving communication complexity of stochastic first-order methods in distributed training of machine learning models. However, the existing works consider only with-replacement sampling of stochastic gradients. In contrast, it is well-known in practice and recently confirmed in theory that stochastic methods based on without-replacement sampling, e.g., Random Reshuffling (RR) method, perform better than ones that sample the gradients with-replacement. In this work, we close this gap in the literature and provide the first analysis of methods with gradient compression and without-replacement sampling. We first develop a na"ive combination of random reshuffling with gradient compression (Q-RR). Perhaps surprisingly, but the theoretical analysis of Q-RR does not show any benefits of using RR. Our extensive numerical experiments confirm this phenomenon. This happens due to the additional compression variance. To reveal the true advantages of RR in the distributed learning with compression, we propose a new method called DIANA-RR that reduces the compression variance and has provably better convergence rates than existing counterparts with with-replacement sampling of stochastic gradients. Next, to have a better fit to Federated Learning applications, we incorporate local computation, i.e., we propose and analyze the variants of Q-RR and DIANA-RR -- Q-NASTYA and DIANA-NASTYA that use local gradient steps and different local and global stepsizes. Finally, we conducted several numerical experiments to illustrate our theoretical results.

Key facts. Cited by 18 papers in the map (data through 14 Oct 2026). Builds on 44 of its 54 references that are in the map. First posted on arXiv 14 Jun 2022.

Builds on

44 of 54 references.

References · 44

  1. 2015Deep Residual Learning for Image Recognitioncited by 52,096
  2. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,669
  3. 2015Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shiftcited by 7,005
  4. 2015Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classificationcited by 3,611
  5. 2019Advances and Open Problems in Federated Learningcited by 3,046
  6. 2016Federated Learning: Strategies for Improving Communication Efficiencycited by 1,475
  7. 2018Sparsified SGD with Memorycited by 376
  8. 2019FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantizationcited by 356
  9. 2021A Field Guide to Federated Optimizationcited by 315
  10. 2019Tighter Theory for Local SGD on Identical and Heterogeneous Datacited by 266
  11. 2019Qsparse-local-SGD: Distributed SGD with Quantization, Sparsification, and Local Computationscited by 181
  12. 2020Federated Learning with Compression: Unified Analysis and Sharp Guaranteescited by 160
32 more
  1. 2020Is Local SGD Better than Minibatch SGD?cited by 151
  2. 2016QSGD: Communication-Efficient SGD via Gradient Quantization and Encodingcited by 147
  3. 2020Minibatch vs Local SGD for Heterogeneous Distributed Learningcited by 147
  4. 2020On Biased Compression for Distributed Learningcited by 140
  5. 2022ProxSkip: Yes! Local Gradient Steps Provably Lead to Communication Acceleration! Finally!cited by 134
  6. 2021Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradientscited by 123
  7. 2020Random Reshuffling: Simple Analysis with Vast Improvementscited by 115
  8. 2019Distributed Learning with Compressed Gradient Differencescited by 112
  9. 2020Local SGD: Unified Theory and New Efficient Methodscited by 88
  10. 2019A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descentcited by 84
  11. 2019Unified Optimal Analysis of the (Stochastic) Gradient Methodcited by 82
  12. 2020From Local SGD to Local Fixed-Point Methods for Federated Learningcited by 74
  13. 2019Stochastic Distributed Learning with Gradient Quantization and Variance Reductioncited by 65
  14. 2020SGD with shuffling: optimal rates without component convexity and large epoch requirementscited by 58
  15. 2020Closing the convergence gap of SGD without replacementcited by 57
  16. 2018Distributed learning with compressed gradientscited by 55
  17. 2021Federated Learning Meets Natural Language Processing: A Surveycited by 43
  18. 2021Sharp Bounds for Federated Averaging (Local SGD) and Continuous Perspectivecited by 38
  19. 2021Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyondcited by 36
  20. 2021Proximal and Federated Random Reshufflingcited by 33
  21. 2021The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communicationcited by 31
  22. 2021Bias-Variance Reduced Local SGD for Less Heterogeneous Federated Learningcited by 31
  23. 2022Server-Side Stepsizes and Sampling Without Replacement Provably Help in Federated Optimizationcited by 23
  24. 2021Smoothness Matrices Beat Smoothness Constants: Better Communication Compression Techniques for Distributed Optimizationcited by 21
  25. 2022FedShuffle: Recipes for Better Use of Local Work in Federated Learningcited by 21
  26. 2021Trade-offs of Local SGD at Scale: An Empirical Studycited by 20
  27. 2020On Communication Compression for Distributed Optimization on Heterogeneous Datacited by 19
  28. 2021Random Reshuffling with Variance Reduction: New Analysis and Better Ratescited by 19
  29. 2021Random Shuffling Beats SGD Only After Many Epochs on Ill-Conditioned Problemscited by 17
  30. 2022Federated Random Reshuffling with Compression and Variance Reductioncited by 12
  31. 2022FL_PyTorch: optimization research simulator for federated learningcited by 10
  32. 2021Distributed Random Reshuffling over Networkscited by 7

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 2; 2023: 8; 2024: 6; 2025: 1; 2026: 1.

18 papers.

Sort:

  1. 2023AsGrad: A Sharp Unified Analysis of Asynchronous-SGD Algorithmscited by 16
  2. 2023Federated Learning with Regularized Client Participationcited by 14
  3. 2024Randomized Asymmetric Chain of LoRA: The First Meaningful Theoretical Framework for Low-Rank Adaptationcited by 13
  4. 2023Communication Compression for Byzantine Robust Learning: New Efficient Algorithms and Improved Ratescited by 12
  5. 2024LoCoDL: Communication-Efficient Distributed Learning with Local Training and Compressioncited by 11
  6. 2024On the Last-Iterate Convergence of Shuffling Gradient Methodscited by 11
  7. 2023Improving Accelerated Federated Learning with Compression and Importance Samplingcited 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. 2022Privacy-Aware Compression for Federated Learning Through Numerical Mechanism Designcited by 6
  11. 2023Towards a Better Theoretical Understanding of Independent Subnetwork Trainingcited by 6
  12. 2023Byzantine Robustness and Partial Participation Can Be Achieved at Once: Just Clip Gradient Differencescited by 5
6 more
  1. 2024On the Convergence of FedProx with Extrapolation and Inexact Proxcited by 3
  2. 2024Streamlining in the Riemannian Realm: Efficient Riemannian Optimization with Loopless Variance Reductioncited by 2
  3. 2024MARINA-P: Superior Performance in Non-smooth Federated Optimization with Adaptive Stepsizescited by 1
  4. 2025First Provable Guarantees for Practical Private FL: Beyond Restrictive Assumptionscited by 1
  5. 2026BiCoLoR: Communication-Efficient Optimization with Bidirectional Compression and Local Trainingcited by 1
  6. 2022Convergence of ease-controlled Random Reshuffling gradient Algorithms under Lipschitz smoothnesscited by 0