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

arXiv: https://arxiv.org/abs/2202.09357 · HTML: https://mlsanity.com/paper/2202.09357/

## Key facts

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

## Builds on (most cited first, 30 of 37)

- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Federated Learning: Strategies for Improving Communication Efficiency](https://mlsanity.com/paper/1610.05492/) (2016)
- [Local SGD Converges Fast and Communicates Little](https://mlsanity.com/paper/1805.09767/) (2018)
- [Ray: A Distributed Framework for Emerging AI Applications](https://mlsanity.com/paper/1712.05889/) (2017)
- [A Unified Theory of Decentralized SGD with Changing Topology and Local Updates](https://mlsanity.com/paper/2003.10422/) (2020)
- [Tighter Theory for Local SGD on Identical and Heterogeneous Data](https://mlsanity.com/paper/1909.04746/) (2019)
- [Federated Learning of a Mixture of Global and Local Models](https://mlsanity.com/paper/2002.05516/) (2020)
- [SGD: General Analysis and Improved Rates](https://mlsanity.com/paper/1901.09401/) (2019)
- [Don't Use Large Mini-Batches, Use Local SGD](https://mlsanity.com/paper/1808.07217/) (2018)
- [Better Theory for SGD in the Nonconvex World](https://mlsanity.com/paper/2002.03329/) (2020)
- [Is Local SGD Better than Minibatch SGD?](https://mlsanity.com/paper/2002.07839/) (2020)
- [Achieving Geometric Convergence for Distributed Optimization over Time-Varying Graphs](https://mlsanity.com/paper/1607.03218/) (2016)
- [Minibatch vs Local SGD for Heterogeneous Distributed Learning](https://mlsanity.com/paper/2006.04735/) (2020)
- [D2: Decentralized Training over Decentralized Data](https://mlsanity.com/paper/1803.07068/) (2018)
- [Lower Bounds and Optimal Algorithms for Personalized Federated Learning](https://mlsanity.com/paper/2010.02372/) (2020)
- [Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradients](https://mlsanity.com/paper/2102.07053/) (2021)
- [NEXT: In-Network Nonconvex Optimization](https://mlsanity.com/paper/1602.00591/) (2016)
- [Local SGD: Unified Theory and New Efficient Methods](https://mlsanity.com/paper/2011.02828/) (2020)
- [Federated Accelerated Stochastic Gradient Descent](https://mlsanity.com/paper/2006.08950/) (2020)
- [First Analysis of Local GD on Heterogeneous Data](https://mlsanity.com/paper/1909.04715/) (2019)
- [From Local SGD to Local Fixed-Point Methods for Federated Learning](https://mlsanity.com/paper/2004.01442/) (2020)
- [Quasi-Global Momentum: Accelerating Decentralized Deep Learning on Heterogeneous Data](https://mlsanity.com/paper/2102.04761/) (2021)
- [An Improved Analysis of Gradient Tracking for Decentralized Machine Learning](https://mlsanity.com/paper/2202.03836/) (2022)
- [Communication Complexity of Distributed Convex Learning and Optimization](https://mlsanity.com/paper/1506.01900/) (2015)
- [Optimal and Practical Algorithms for Smooth and Strongly Convex Decentralized Optimization](https://mlsanity.com/paper/2006.11773/) (2020)
- [RelaySum for Decentralized Deep Learning on Heterogeneous Data](https://mlsanity.com/paper/2110.04175/) (2021)
- [Stochastic Quasi-Gradient Methods: Variance Reduction via Jacobian Sketching](https://mlsanity.com/paper/1805.02632/) (2018)
- [Parallel SGD: When does averaging help?](https://mlsanity.com/paper/1606.07365/) (2016)
- [The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication](https://mlsanity.com/paper/2102.01583/) (2021)
- [Removing Data Heterogeneity Influence Enhances Network Topology Dependence of Decentralized SGD](https://mlsanity.com/paper/2105.08023/) (2021)

## Built on by (most cited first, 30 of 134)

- [FedExP: Speeding Up Federated Averaging via Extrapolation](https://mlsanity.com/paper/2301.09604/) (2023)
- [SoteriaFL: A Unified Framework for Private Federated Learning with Communication Compression](https://mlsanity.com/paper/2206.09888/) (2022)
- [Variance Reduced ProxSkip: Algorithm, Theory and Application to Federated Learning](https://mlsanity.com/paper/2207.04338/) (2022)
- [Momentum Provably Improves Error Feedback!](https://mlsanity.com/paper/2305.15155/) (2023)
- [Finite-Time Analysis of On-Policy Heterogeneous Federated Reinforcement Learning](https://mlsanity.com/paper/2401.15273/) (2024)
- [PrE-Text: Training Language Models on Private Federated Data in the Age of LLMs](https://mlsanity.com/paper/2406.02958/) (2024)
- [TCT: Convexifying Federated Learning using Bootstrapped Neural Tangent Kernels](https://mlsanity.com/paper/2207.06343/) (2022)
- [GPT-FL: Generative Pre-trained Model-Assisted Federated Learning](https://mlsanity.com/paper/2306.02210/) (2023)
- [Adaptive SGD with Polyak stepsize and Line-search: Robust Convergence and Variance Reduction](https://mlsanity.com/paper/2308.06058/) (2023)
- [Can 5th Generation Local Training Methods Support Client Sampling? Yes!](https://mlsanity.com/paper/2212.14370/) (2022)
- [On the Performance of Gradient Tracking with Local Updates](https://mlsanity.com/paper/2210.04757/) (2022)
- [Communication Acceleration of Local Gradient Methods via an Accelerated Primal-Dual Algorithm with Inexact Prox](https://mlsanity.com/paper/2207.03957/) (2022)
- [Federated Optimization Algorithms with Random Reshuffling and Gradient Compression](https://mlsanity.com/paper/2206.07021/) (2022)
- [Faster federated optimization under second-order similarity](https://mlsanity.com/paper/2209.02257/) (2022)
- [GradSkip: Communication-Accelerated Local Gradient Methods with Better Computational Complexity](https://mlsanity.com/paper/2210.16402/) (2022)
- [Near-Optimal Nonconvex-Strongly-Convex Bilevel Optimization with Fully First-Order Oracles](https://mlsanity.com/paper/2306.14853/) (2023)
- [AsGrad: A Sharp Unified Analysis of Asynchronous-SGD Algorithms](https://mlsanity.com/paper/2310.20452/) (2023)
- [Federated TD Learning over Finite-Rate Erasure Channels: Linear Speedup under Markovian Sampling](https://mlsanity.com/paper/2305.08104/) (2023)
- [Training-Free Model Merging for Multi-target Domain Adaptation](https://mlsanity.com/paper/2407.13771/) (2024)
- [Federated Learning with Regularized Client Participation](https://mlsanity.com/paper/2302.03662/) (2023)
- [Unbiased Compression Saves Communication in Distributed Optimization: When and How Much?](https://mlsanity.com/paper/2305.16297/) (2023)
- [FedP3: Federated Personalized and Privacy-friendly Network Pruning under Model Heterogeneity](https://mlsanity.com/paper/2404.09816/) (2024)
- [Randomized Asymmetric Chain of LoRA: The First Meaningful Theoretical Framework for Low-Rank Adaptation](https://mlsanity.com/paper/2410.08305/) (2024)
- [SGD with Adaptive Preconditioning: Unified Analysis and Momentum Acceleration](https://mlsanity.com/paper/2506.23803/) (2025)
- [Distributed Newton-Type Methods with Communication Compression and Bernoulli Aggregation](https://mlsanity.com/paper/2206.03588/) (2022)
- [CompressedScaffnew: The First Theoretical Double Acceleration of Communication from Local Training and Compression in Distributed Optimization](https://mlsanity.com/paper/2210.13277/) (2022)
- [Stochastic Distributed Optimization under Average Second-order Similarity: Algorithms and Analysis](https://mlsanity.com/paper/2304.07504/) (2023)
- [Lower Bounds and Accelerated Algorithms in Distributed Stochastic Optimization with Communication Compression](https://mlsanity.com/paper/2305.07612/) (2023)
- [LoCoDL: Communication-Efficient Distributed Learning with Local Training and Compression](https://mlsanity.com/paper/2403.04348/) (2024)
- [Alternating Implicit Projected SGD and Its Efficient Variants for Equality-constrained Bilevel Optimization](https://mlsanity.com/paper/2211.07096/) (2022)

## 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.