# Variance Reduced ProxSkip: Algorithm, Theory and Application to Federated Learning

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

## Key facts

- Cited by 33 papers in the map (data through 14 Oct 2026).
- Builds on 38 of its 50 references that are in the map.
- First posted on arXiv 9 Jul 2022.

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

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Federated Learning: Challenges, Methods, and Future Directions](https://mlsanity.com/paper/1908.07873/) (2019)
- [Federated Learning: Strategies for Improving Communication Efficiency](https://mlsanity.com/paper/1610.05492/) (2016)
- [Federated Optimization: Distributed Machine Learning for On-Device Intelligence](https://mlsanity.com/paper/1610.02527/) (2016)
- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [A Field Guide to Federated Optimization](https://mlsanity.com/paper/2107.06917/) (2021)
- [Tighter Theory for Local SGD on Identical and Heterogeneous Data](https://mlsanity.com/paper/1909.04746/) (2019)
- [SGD: General Analysis and Improved Rates](https://mlsanity.com/paper/1901.09401/) (2019)
- [Client Selection in Federated Learning: Convergence Analysis and Power-of-Choice Selection Strategies](https://mlsanity.com/paper/2010.01243/) (2020)
- [On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimization](https://mlsanity.com/paper/1905.03817/) (2019)
- [SCAFFOLD: Stochastic Controlled Averaging for Federated Learning](https://mlsanity.com/paper/1910.06378/) (2019)
- [Better Theory for SGD in the Nonconvex World](https://mlsanity.com/paper/2002.03329/) (2020)
- [On the Convergence of Local Descent Methods in Federated Learning](https://mlsanity.com/paper/1910.14425/) (2019)
- [Minibatch vs Local SGD for Heterogeneous Distributed Learning](https://mlsanity.com/paper/2006.04735/) (2020)
- [ProxSkip: Yes! Local Gradient Steps Provably Lead to Communication Acceleration! Finally!](https://mlsanity.com/paper/2202.09357/) (2022)
- [Optimal Client Sampling for Federated Learning](https://mlsanity.com/paper/2010.13723/) (2020)
- [Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradients](https://mlsanity.com/paper/2102.07053/) (2021)
- [Natural Compression for Distributed Deep Learning](https://mlsanity.com/paper/1905.10988/) (2019)
- [Local SGD: Unified Theory and New Efficient Methods](https://mlsanity.com/paper/2011.02828/) (2020)
- [A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descent](https://mlsanity.com/paper/1905.11261/) (2019)
- [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)
- [On Large-Cohort Training for Federated Learning](https://mlsanity.com/paper/2106.07820/) (2021)
- [Don't Jump Through Hoops and Remove Those Loops: SVRG and Katyusha are Better Without the Outer Loop](https://mlsanity.com/paper/1901.08689/) (2019)
- [Stochastic Distributed Learning with Gradient Quantization and Variance Reduction](https://mlsanity.com/paper/1904.05115/) (2019)
- [Linearly Converging Error Compensated SGD](https://mlsanity.com/paper/2010.12292/) (2020)
- [Distributed learning with compressed gradients](https://mlsanity.com/paper/1806.06573/) (2018)
- [Bidirectional compression in heterogeneous settings for distributed or federated learning with partial participation: tight convergence guarantees](https://mlsanity.com/paper/2006.14591/) (2020)
- [Semi-Cyclic Stochastic Gradient Descent](https://mlsanity.com/paper/1904.10120/) (2019)

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

- [GPT-FL: Generative Pre-trained Model-Assisted Federated Learning](https://mlsanity.com/paper/2306.02210/) (2023)
- [Can 5th Generation Local Training Methods Support Client Sampling? Yes!](https://mlsanity.com/paper/2212.14370/) (2022)
- [GradSkip: Communication-Accelerated Local Gradient Methods with Better Computational Complexity](https://mlsanity.com/paper/2210.16402/) (2022)
- [Federated Learning with Regularized Client Participation](https://mlsanity.com/paper/2302.03662/) (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)
- [Detecting Backdoor Attacks in Federated Learning via Direction Alignment Inspection](https://mlsanity.com/paper/2503.07978/) (2025)
- [CompressedScaffnew: The First Theoretical Double Acceleration of Communication from Local Training and Compression in Distributed Optimization](https://mlsanity.com/paper/2210.13277/) (2022)
- [LoCoDL: Communication-Efficient Distributed Learning with Local Training and Compression](https://mlsanity.com/paper/2403.04348/) (2024)
- [Improving Accelerated Federated Learning with Compression and Importance Sampling](https://mlsanity.com/paper/2306.03240/) (2023)
- [Similarity, Compression and Local Steps: Three Pillars of Efficient Communications for Distributed Variational Inequalities](https://mlsanity.com/paper/2302.07615/) (2023)
- [SCAFFLSA: Taming Heterogeneity in Federated Linear Stochastic Approximation and TD Learning](https://mlsanity.com/paper/2402.04114/) (2024)
- [Hierarchical Federated Learning with Multi-Timescale Gradient Correction](https://mlsanity.com/paper/2409.18448/) (2024)
- [Towards a Better Theoretical Understanding of Independent Subnetwork Training](https://mlsanity.com/paper/2306.16484/) (2023)
- [Explicit Personalization and Local Training: Double Communication Acceleration in Federated Learning](https://mlsanity.com/paper/2305.13170/) (2023)
- [FedComLoc: Communication-Efficient Distributed Training of Sparse and Quantized Models](https://mlsanity.com/paper/2403.09904/) (2024)
- [TAMUNA: Doubly Accelerated Distributed Optimization under Partial Participation](https://mlsanity.com/paper/2302.09832/) (2023)
- [Communication-Efficient Gradient Descent-Accent Methods for Distributed Variational Inequalities: Unified Analysis and Local Updates](https://mlsanity.com/paper/2306.05100/) (2023)
- [DualFL: A Duality-based Federated Learning Algorithm with Communication Acceleration in the General Convex Regime](https://mlsanity.com/paper/2305.10294/) (2023)
- [Enhanced Federated Optimization: Adaptive Unbiased Client Sampling with Reduced Variance](https://mlsanity.com/paper/2310.02698/) (2023)
- [Parallel Trust-Region Approaches in Neural Network Training: Beyond Traditional Methods](https://mlsanity.com/paper/2312.13677/) (2023)
- [Streamlining in the Riemannian Realm: Efficient Riemannian Optimization with Loopless Variance Reduction](https://mlsanity.com/paper/2403.06677/) (2024)
- [Cohort Squeeze: Beyond a Single Communication Round per Cohort in Cross-Device Federated Learning](https://mlsanity.com/paper/2406.01115/) (2024)
- [JacQuant: STE-Free Quantization-Aware Training via Learned Jacobian Surrogates](https://mlsanity.com/paper/2605.25469/) (2026)
- [Achieving Linear Speedup with ProxSkip in Distributed Stochastic Optimization](https://mlsanity.com/paper/2310.07983/) (2023)
- [Federated Learning over Hierarchical Wireless Networks: Training Latency Minimization via Submodel Partitioning](https://mlsanity.com/paper/2310.17890/) (2023)
- [BiCoLoR: Communication-Efficient Optimization with Bidirectional Compression and Local Training](https://mlsanity.com/paper/2601.12400/) (2026)
- [LOSCAR-SGD: Local SGD with Communication-Computation Overlap and Delay-Corrected Sparse Model Averaging](https://mlsanity.com/paper/2605.20866/) (2026)
- [An Optimal Algorithm for Strongly Convex Min-min Optimization](https://mlsanity.com/paper/2212.14439/) (2022)
- [Near-Optimal Distributed Minimax Optimization under the Second-Order Similarity](https://mlsanity.com/paper/2405.16126/) (2024)

## Abstract (arXiv)

We study distributed optimization methods based on the em local training (LT) paradigm: achieving communication efficiency by performing richer local gradient-based training on the clients before parameter averaging. Looking back at the progress of the field, we em identify 5 generations of LT methods: 1) heuristic, 2) homogeneous, 3) sublinear, 4) linear, and 5) accelerated. The 5rm th generation, initiated by the ProxSkip method of Mishchenko, Malinovsky, Stich and Richt'arik (2022) and its analysis, is characterized by the first theoretical confirmation that LT is a communication acceleration mechanism. Inspired by this recent progress, we contribute to the 5rm th generation of LT methods by showing that it is possible to enhance them further using em variance reduction. While all previous theoretical results for LT methods ignore the cost of local work altogether, and are framed purely in terms of the number of communication rounds, we show that our methods can be substantially faster in terms of the em total training cost than the state-of-the-art method ProxSkip in theory and practice in the regime when local computation is sufficiently expensive. We characterize this threshold theoretically, and confirm our theoretical predictions with empirical results.