mlsanityData to 7 Oct 2026

ProxSkip: Yes! Local Gradient Steps Provably Lead to Communication Acceleration! Finally!

arXiv 2202.09357 ↗First posted 18 Feb 2022cs.LG math.OCcited by 134

Not on the map. Why?

Abstract (arXiv)

We introduce ProxSkip -- a surprisingly simple and provably efficient method for minimizing the sum of a smooth (f) and an expensive nonsmooth proximable (psi) function. The canonical approach to solving such problems is via the proximal gradient descent (ProxGD) algorithm, which is based on the evaluation of the gradient of f and the prox operator of psi in each iteration. In this work we are specifically interested in the regime in which the evaluation of prox is costly relative to the evaluation of the gradient, which is the case in many applications. ProxSkip allows for the expensive prox operator to be skipped in most iterations: while its iteration complexity is Oleft(kappa log frac1varepsilonright), where kappa is the condition number of f, the number of prox evaluations is Oleft(√kappa log frac1varepsilonright) only. Our main motivation comes from federated learning, where evaluation of the gradient operator corresponds to taking a local GD step independently on all devices, and evaluation of prox corresponds to (expensive) communication in the form of gradient averaging. In this context, ProxSkip offers an effective acceleration of communication complexity. Unlike other local gradient-type methods, such as FedAvg, SCAFFOLD, S-Local-GD and FedLin, whose theoretical communication complexity is worse than, or at best matching, that of vanilla GD in the heterogeneous data regime, we obtain a provable and large improvement without any heterogeneity-bounding assumptions.

Key facts. Cited by 134 papers in the map (data through 7 Oct 2026). Builds on 37 of its 60 references that are in the map. First posted on arXiv 18 Feb 2022.

Builds on

37 of 60 references.

References · 37

  1. 2019Advances and Open Problems in Federated Learningcited by 3,021
  2. 2016Federated Learning: Strategies for Improving Communication Efficiencycited by 1,461
  3. 2018Local SGD Converges Fast and Communicates Littlecited by 595
  4. 2017Ray: A Distributed Framework for Emerging AI Applicationscited by 516
  5. 2020A Unified Theory of Decentralized SGD with Changing Topology and Local Updatescited by 361
  6. 2019Tighter Theory for Local SGD on Identical and Heterogeneous Datacited by 266
  7. 2020Federated Learning of a Mixture of Global and Local Modelscited by 208
  8. 2019SGD: General Analysis and Improved Ratescited by 206
  9. 2018Don't Use Large Mini-Batches, Use Local SGDcited by 201
  10. 2020Better Theory for SGD in the Nonconvex Worldcited by 156
  11. 2020Is Local SGD Better than Minibatch SGD?cited by 151
  12. 2016Achieving Geometric Convergence for Distributed Optimization over Time-Varying Graphscited by 149
25 more
  1. 2020Minibatch vs Local SGD for Heterogeneous Distributed Learningcited by 147
  2. 2018D2: Decentralized Training over Decentralized Datacited by 140
  3. 2020Lower Bounds and Optimal Algorithms for Personalized Federated Learningcited by 122
  4. 2021Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradientscited by 122
  5. 2016NEXT: In-Network Nonconvex Optimizationcited by 107
  6. 2020Local SGD: Unified Theory and New Efficient Methodscited by 88
  7. 2020Federated Accelerated Stochastic Gradient Descentcited by 85
  8. 2019First Analysis of Local GD on Heterogeneous Datacited by 80
  9. 2020From Local SGD to Local Fixed-Point Methods for Federated Learningcited by 74
  10. 2021Quasi-Global Momentum: Accelerating Decentralized Deep Learning on Heterogeneous Datacited by 69
  11. 2022An Improved Analysis of Gradient Tracking for Decentralized Machine Learningcited by 68
  12. 2015Communication Complexity of Distributed Convex Learning and Optimizationcited by 59
  13. 2020Optimal and Practical Algorithms for Smooth and Strongly Convex Decentralized Optimizationcited by 43
  14. 2021RelaySum for Decentralized Deep Learning on Heterogeneous Datacited by 39
  15. 2018Stochastic Quasi-Gradient Methods: Variance Reduction via Jacobian Sketchingcited by 34
  16. 2016Parallel SGD: When does averaging help?cited by 30
  17. 2021The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communicationcited by 30
  18. 2021Removing Data Heterogeneity Influence Enhances Network Topology Dependence of Decentralized SGDcited by 28
  19. 2019Generalized monotone operators and their averaged resolventscited by 27
  20. 2021Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networkscited by 19
  21. 2019Proximal Splitting Algorithms for Convex Optimization: A Tour of Recent Advances, with New Twistscited by 15
  22. 2021ADOM: Accelerated Decentralized Optimization Method for Time-Varying Networkscited by 13
  23. 2020Distributed Proximal Splitting Algorithms with Rates and Accelerationcited by 7
  24. 2014A forward-backward view of some primal-dual optimization methods in image recoverycited by 5
  25. 2016Efficient evaluation of scaled proximal operatorscited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 21; 2023: 40; 2024: 41; 2025: 21; 2026: 11.

134 papers.

Sort:

  1. 2023FedExP: Speeding Up Federated Averaging via Extrapolationcited by 68
  2. 2022SoteriaFL: A Unified Framework for Private Federated Learning with Communication Compressioncited by 34
  3. 2022Variance Reduced ProxSkip: Algorithm, Theory and Application to Federated Learningcited by 33
  4. 2023Momentum Provably Improves Error Feedback!cited by 31
  5. 2024Finite-Time Analysis of On-Policy Heterogeneous Federated Reinforcement Learningcited by 29
  6. 2024PrE-Text: Training Language Models on Private Federated Data in the Age of LLMscited by 29
  7. 2022TCT: Convexifying Federated Learning using Bootstrapped Neural Tangent Kernelscited by 26
  8. 2023GPT-FL: Generative Pre-trained Model-Assisted Federated Learningcited by 24
  9. 2023Adaptive SGD with Polyak stepsize and Line-search: Robust Convergence and Variance Reductioncited by 23
  10. 2022Can 5th Generation Local Training Methods Support Client Sampling? Yes!cited by 22
  11. 2022On the Performance of Gradient Tracking with Local Updatescited by 21
  12. 2022Communication Acceleration of Local Gradient Methods via an Accelerated Primal-Dual Algorithm with Inexact Proxcited by 19
38 more
  1. 2022Federated Optimization Algorithms with Random Reshuffling and Gradient Compressioncited by 18
  2. 2022Faster federated optimization under second-order similaritycited by 18
  3. 2022GradSkip: Communication-Accelerated Local Gradient Methods with Better Computational Complexitycited by 17
  4. 2023Near-Optimal Nonconvex-Strongly-Convex Bilevel Optimization with Fully First-Order Oraclescited by 16
  5. 2023AsGrad: A Sharp Unified Analysis of Asynchronous-SGD Algorithmscited by 16
  6. 2024Training-Free Model Merging for Multi-target Domain Adaptationcited by 15
  7. 2023Federated TD Learning over Finite-Rate Erasure Channels: Linear Speedup under Markovian Samplingcited by 14
  8. 2023Unbiased Compression Saves Communication in Distributed Optimization: When and How Much?cited by 14
  9. 2023Federated Learning with Regularized Client Participationcited by 13
  10. 2024FedP3: Federated Personalized and Privacy-friendly Network Pruning under Model Heterogeneitycited by 13
  11. 2024Randomized Asymmetric Chain of LoRA: The First Meaningful Theoretical Framework for Low-Rank Adaptationcited by 12
  12. 2025SGD with Adaptive Preconditioning: Unified Analysis and Momentum Accelerationcited by 12
  13. 2022Distributed Newton-Type Methods with Communication Compression and Bernoulli Aggregationcited by 11
  14. 2022CompressedScaffnew: The First Theoretical Double Acceleration of Communication from Local Training and Compression in Distributed Optimizationcited by 11
  15. 2023Stochastic Distributed Optimization under Average Second-order Similarity: Algorithms and Analysiscited by 11
  16. 2023Lower Bounds and Accelerated Algorithms in Distributed Stochastic Optimization with Communication Compressioncited by 11
  17. 2024LoCoDL: Communication-Efficient Distributed Learning with Local Training and Compressioncited by 11
  18. 2022Alternating Implicit Projected SGD and Its Efficient Variants for Equality-constrained Bilevel Optimizationcited by 10
  19. 2024Federated Optimization with Doubly Regularized Drift Correctioncited by 10
  20. 2024Non-convex Stochastic Composite Optimization with Polyak Momentumcited by 9
  21. 2022DADAO: Decoupled Accelerated Decentralized Asynchronous Optimizationcited by 8
  22. 2022On the effectiveness of partial variance reduction in federated learning with heterogeneous datacited by 8
  23. 2023Partially Personalized Federated Learning: Breaking the Curse of Data Heterogeneitycited by 8
  24. 2023Importance of Smoothness Induced by Optimizers in FL4ASR: Towards Understanding Federated Learning for End-to-End ASRcited by 8
  25. 2023Handling Data Heterogeneity via Architectural Design for Federated Visual Recognitioncited by 8
  26. 2023A Communication-Efficient Adaptive Algorithm for Federated Learning under Cumulative Regretcited by 7
  27. 2023Similarity, Compression and Local Steps: Three Pillars of Efficient Communications for Distributed Variational Inequalitiescited by 7
  28. 2023Improving Accelerated Federated Learning with Compression and Importance Samplingcited by 7
  29. 2024The Effectiveness of Local Updates for Decentralized Learning under Data Heterogeneitycited by 7
  30. 2024Hierarchical Federated Learning with Multi-Timescale Gradient Correctioncited by 7
  31. 2023Towards a Better Theoretical Understanding of Independent Subnetwork Trainingcited by 6
  32. 2023Scaff-PD: Communication Efficient Fair and Robust Federated Learningcited by 6
  33. 2023Distributed Personalized Empirical Risk Minimizationcited by 6
  34. 2024SCAFFLSA: Taming Heterogeneity in Federated Linear Stochastic Approximation and TD Learningcited by 6
  35. 2024ACCO: Accumulate While You Communicate for Communication-Overlapped Sharded LLM Trainingcited by 6
  36. 2024Stabilized Proximal-Point Methods for Federated Optimizationcited by 6
  37. 2025Exact and Linear Convergence for Federated Learning under Arbitrary Client Participation is Attainablecited by 6
  38. 2022Federated Learning for Inference at Anytime and Anywherecited by 5

50 most cited of 134 All 134 (JSON)