mlsanityData to 14 Oct 2026

Communication Acceleration of Local Gradient Methods via an Accelerated Primal-Dual Algorithm with Inexact Prox

arXiv 2207.03957 ↗First posted 8 Jul 2022cs.LG cs.DC math.OCcited by 19

Not on the map. Why?

Abstract (arXiv)

Inspired by a recent breakthrough of Mishchenko et al (2022), who for the first time showed that local gradient steps can lead to provable communication acceleration, we propose an alternative algorithm which obtains the same communication acceleration as their method (ProxSkip). Our approach is very different, however: it is based on the celebrated method of Chambolle and Pock (2011), with several nontrivial modifications: i) we allow for an inexact computation of the prox operator of a certain smooth strongly convex function via a suitable gradient-based method (e.g., GD, Fast GD or FSFOM), ii) we perform a careful modification of the dual update step in order to retain linear convergence. Our general results offer the new state-of-the-art rates for the class of strongly convex-concave saddle-point problems with bilinear coupling characterized by the absence of smoothness in the dual function. When applied to federated learning, we obtain a theoretically better alternative to ProxSkip: our method requires fewer local steps (O(kappa1/3) or O(kappa1/4), compared to O(kappa1/2) of ProxSkip), and performs a deterministic number of local steps instead. Like ProxSkip, our method can be applied to optimization over a connected network, and we obtain theoretical improvements here as well.

Key facts. Cited by 19 papers in the map (data through 14 Oct 2026). Builds on 57 of its 78 references that are in the map. First posted on arXiv 8 Jul 2022.

Builds on

57 of 78 references.

References · 57

  1. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,669
  2. 2019Advances and Open Problems in Federated Learningcited by 3,046
  3. 2018Federated Optimization in Heterogeneous Networkscited by 2,987
  4. 2019Federated Learning: Challenges, Methods, and Future Directionscited by 1,538
  5. 2016Federated Learning: Strategies for Improving Communication Efficiencycited by 1,475
  6. 2018Local SGD Converges Fast and Communicates Littlecited by 605
  7. 2016Federated Optimization: Distributed Machine Learning for On-Device Intelligencecited by 564
  8. 2018Sparsified SGD with Memorycited by 376
  9. 2020A Unified Theory of Decentralized SGD with Changing Topology and Local Updatescited by 367
  10. 2021A Field Guide to Federated Optimizationcited by 315
  11. 2019Tighter Theory for Local SGD on Identical and Heterogeneous Datacited by 266
  12. 2019PowerSGD: Practical Low-Rank Gradient Compression for Distributed Optimizationcited by 238
38 more
  1. 2018The Convergence of Sparsified Gradient Methodscited by 229
  2. 2016Trained Ternary Quantizationcited by 208
  3. 2017Gradient Sparsification for Communication-Efficient Distributed Optimizationcited by 201
  4. 2019SCAFFOLD: Stochastic Controlled Averaging for Federated Learningcited by 175
  5. 2019On the Convergence of Local Descent Methods in Federated Learningcited by 153
  6. 2020Is Local SGD Better than Minibatch SGD?cited by 151
  7. 2018ATOMO: Communication-efficient Learning via Atomic Sparsificationcited by 136
  8. 2022ProxSkip: Yes! Local Gradient Steps Provably Lead to Communication Acceleration! Finally!cited by 134
  9. 2021EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedbackcited by 133
  10. 2020FedSplit: An algorithmic framework for fast federated optimizationcited by 108
  11. 2019DoubleSqueeze: Parallel Stochastic Gradient Descent with Double-Pass Error-Compensated Compressioncited by 99
  12. 2019Natural Compression for Distributed Deep Learningcited by 90
  13. 2020Acceleration for Compressed Gradient Descent in Distributed and Federated Optimizationcited by 90
  14. 2020Local SGD: Unified Theory and New Efficient Methodscited by 88
  15. 2019A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descentcited by 84
  16. 2017Optimal algorithms for smooth and strongly convex distributed optimization in networkscited by 83
  17. 2019First Analysis of Local GD on Heterogeneous Datacited by 81
  18. 2021MARINA: Faster Non-Convex Distributed Learning with Compressioncited by 78
  19. 2020From Local SGD to Local Fixed-Point Methods for Federated Learningcited by 74
  20. 2019Stochastic Distributed Learning with Gradient Quantization and Variance Reductioncited by 65
  21. 2020Linearly Converging Error Compensated SGDcited by 61
  22. 2021FedNL: Making Newton-Type Methods Applicable to Federated Learningcited by 52
  23. 2020Bidirectional compression in heterogeneous settings for distributed or federated learning with partial participation: tight convergence guaranteescited by 46
  24. 2020Error Compensated Distributed SGD Can Be Acceleratedcited by 45
  25. 2020A Better Alternative to Error Feedback for Communication-Efficient Distributed Learningcited by 43
  26. 2020Optimal and Practical Algorithms for Smooth and Strongly Convex Decentralized Optimizationcited by 43
  27. 2020A Linearly Convergent Algorithm for Decentralized Optimization: Sending Less Bits for Free!cited by 42
  28. 2021Proximal and Federated Random Reshufflingcited by 33
  29. 2021Permutation Compressors for Provably Faster Distributed Nonconvex Optimizationcited by 32
  30. 2021Near-optimal Local Convergence of Alternating Gradient Descent-Ascent for Minimax Optimizationcited by 31
  31. 2018SEGA: Variance Reduction via Gradient Sketchingcited by 29
  32. 20223PC: Three Point Compressors for Communication-Efficient Distributed Training and a Better Theory for Lazy Aggregationcited by 27
  33. 2021Distributed Second Order Methods with Fast Rates and Compressed Communicationcited by 25
  34. 2015Distributed Optimization with Arbitrary Local Solverscited by 23
  35. 2022Server-Side Stepsizes and Sampling Without Replacement Provably Help in Federated Optimizationcited by 23
  36. 2021Smoothness Matrices Beat Smoothness Constants: Better Communication Compression Techniques for Distributed Optimizationcited by 21
  37. 2022FedShuffle: Recipes for Better Use of Local Work in Federated Learningcited by 21
  38. 2022EF-BV: A Unified Theory of Error Feedback and Variance Reduction Mechanisms for Biased and Unbiased Compression in Distributed Optimizationcited by 17

50 most cited of 57 All 57 (JSON)

Built on by

Cited by year

Citing papers per year: 2022: 3; 2023: 5; 2024: 10; 2025: 1.

19 papers.

Sort:

By area:

  1. 2024PrE-Text: Training Language Models on Private Federated Data in the Age of LLMscited by 29
  2. 2022Can 5th Generation Local Training Methods Support Client Sampling? Yes!cited by 22
  3. 2022GradSkip: Communication-Accelerated Local Gradient Methods with Better Computational Complexitycited by 18
  4. 2024Randomized Asymmetric Chain of LoRA: The First Meaningful Theoretical Framework for Low-Rank Adaptationcited by 13
  5. 2024LoCoDL: Communication-Efficient Distributed Learning with Local Training and Compressioncited by 11
  6. 2022Smooth Monotone Stochastic Variational Inequalities and Saddle Point Problems: A Surveycited by 10
  7. 2023Improving Accelerated Federated Learning with Compression and Importance Samplingcited by 8
  8. 2024Stabilized Proximal-Point Methods for Federated Optimizationcited by 7
  9. 2023Towards a Better Theoretical Understanding of Independent Subnetwork Trainingcited by 6
  10. 2023TAMUNA: Doubly Accelerated Distributed Optimization under Partial Participationcited by 4
  11. 2024SPAM: Stochastic Proximal Point Method with Momentum Variance Reduction for Non-convex Cross-Device Federated Learningcited by 3
  12. 2024On the Convergence of FedProx with Extrapolation and Inexact Proxcited by 3
7 more
  1. 2023DualFL: A Duality-based Federated Learning Algorithm with Communication Acceleration in the General Convex Regimecited by 2
  2. 2023Achieving Linear Speedup with ProxSkip in Distributed Stochastic Optimizationcited by 1
  3. 2024Lower Bounds and Optimal Algorithms for Non-Smooth Convex Decentralized Optimization over Time-Varying Networkscited by 1
  4. 2025Certifying the Right to Be Forgotten: Primal-Dual Optimization for Sample and Label Unlearning in Vertical Federated Learningcited by 1
  5. 2024Accelerating Distributed Optimization: A Primal-Dual Perspective on Local Stepscited by 0
  6. 2024Contractivity and linear convergence in bilinear saddle-point problems: An operator-theoretic approachcited by 0
  7. 2024Refined Analysis of Federated Averaging and Federated Richardson-Rombergcited by 0