mlsanityData to 14 Oct 2026

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

arXiv 2207.04338 ↗First posted 9 Jul 2022cs.LG cs.DC math.OCcited by 33

Not on the map. Why?

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.

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

38 of 50 references.

References · 38

  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. 2019Federated Learning: Challenges, Methods, and Future Directionscited by 1,538
  4. 2016Federated Learning: Strategies for Improving Communication Efficiencycited by 1,475
  5. 2016Federated Optimization: Distributed Machine Learning for On-Device Intelligencecited by 564
  6. 2014SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectivescited by 402
  7. 2021A Field Guide to Federated Optimizationcited by 315
  8. 2019Tighter Theory for Local SGD on Identical and Heterogeneous Datacited by 266
  9. 2019SGD: General Analysis and Improved Ratescited by 207
  10. 2020Client Selection in Federated Learning: Convergence Analysis and Power-of-Choice Selection Strategiescited by 198
  11. 2019On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimizationcited by 180
  12. 2019SCAFFOLD: Stochastic Controlled Averaging for Federated Learningcited by 175
26 more
  1. 2020Better Theory for SGD in the Nonconvex Worldcited by 158
  2. 2019On the Convergence of Local Descent Methods in Federated Learningcited by 153
  3. 2020Minibatch vs Local SGD for Heterogeneous Distributed Learningcited by 147
  4. 2022ProxSkip: Yes! Local Gradient Steps Provably Lead to Communication Acceleration! Finally!cited by 134
  5. 2020Optimal Client Sampling for Federated Learningcited by 124
  6. 2021Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradientscited by 123
  7. 2019Natural Compression for Distributed Deep Learningcited by 90
  8. 2020Local SGD: Unified Theory and New Efficient Methodscited by 88
  9. 2019A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descentcited by 84
  10. 2019First Analysis of Local GD on Heterogeneous Datacited by 81
  11. 2020From Local SGD to Local Fixed-Point Methods for Federated Learningcited by 74
  12. 2021On Large-Cohort Training for Federated Learningcited by 74
  13. 2019Don't Jump Through Hoops and Remove Those Loops: SVRG and Katyusha are Better Without the Outer Loopcited by 68
  14. 2019Stochastic Distributed Learning with Gradient Quantization and Variance Reductioncited by 65
  15. 2020Linearly Converging Error Compensated SGDcited by 61
  16. 2018Distributed learning with compressed gradientscited by 55
  17. 2020Bidirectional compression in heterogeneous settings for distributed or federated learning with partial participation: tight convergence guaranteescited by 46
  18. 2019Semi-Cyclic Stochastic Gradient Descentcited by 40
  19. 2015Variance Reduced Stochastic Gradient Descent with Neighborscited by 39
  20. 2021Sharp Bounds for Federated Averaging (Local SGD) and Continuous Perspectivecited by 38
  21. 2016Importance Sampling for Minibatchescited by 36
  22. 2018Nonconvex Variance Reduced Optimization with Arbitrary Samplingcited by 14
  23. 2015SparkNet: Training Deep Networks in Sparkcited by 13
  24. 2013Mini-Batch Primal and Dual Methods for SVMscited by 12
  25. 2014Parallel training of DNNs with Natural Gradient and Parameter Averagingcited by 11
  26. 2022Shifted Compression Framework: Generalizations and Improvementscited by 6

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 4; 2023: 13; 2024: 11; 2025: 2; 2026: 3.

33 papers.

Sort:

  1. 2023GPT-FL: Generative Pre-trained Model-Assisted Federated Learningcited by 24
  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. 2023Federated Learning with Regularized Client Participationcited by 14
  5. 2024FedP3: Federated Personalized and Privacy-friendly Network Pruning under Model Heterogeneitycited by 13
  6. 2024Randomized Asymmetric Chain of LoRA: The First Meaningful Theoretical Framework for Low-Rank Adaptationcited by 13
  7. 2025Detecting Backdoor Attacks in Federated Learning via Direction Alignment Inspectioncited by 13
  8. 2022CompressedScaffnew: The First Theoretical Double Acceleration of Communication from Local Training and Compression in Distributed Optimizationcited by 11
  9. 2024LoCoDL: Communication-Efficient Distributed Learning with Local Training and Compressioncited by 11
  10. 2023Improving Accelerated Federated Learning with Compression and Importance Samplingcited by 8
  11. 2023Similarity, Compression and Local Steps: Three Pillars of Efficient Communications for Distributed Variational Inequalitiescited by 7
  12. 2024SCAFFLSA: Taming Heterogeneity in Federated Linear Stochastic Approximation and TD Learningcited by 7
21 more
  1. 2024Hierarchical Federated Learning with Multi-Timescale Gradient Correctioncited by 7
  2. 2023Towards a Better Theoretical Understanding of Independent Subnetwork Trainingcited by 6
  3. 2023Explicit Personalization and Local Training: Double Communication Acceleration in Federated Learningcited by 5
  4. 2024FedComLoc: Communication-Efficient Distributed Training of Sparse and Quantized Modelscited by 5
  5. 2023TAMUNA: Doubly Accelerated Distributed Optimization under Partial Participationcited by 4
  6. 2023Communication-Efficient Gradient Descent-Accent Methods for Distributed Variational Inequalities: Unified Analysis and Local Updatescited by 4
  7. 2023DualFL: A Duality-based Federated Learning Algorithm with Communication Acceleration in the General Convex Regimecited by 2
  8. 2023Enhanced Federated Optimization: Adaptive Unbiased Client Sampling with Reduced Variancecited by 2
  9. 2023Parallel Trust-Region Approaches in Neural Network Training: Beyond Traditional Methodscited by 2
  10. 2024Streamlining in the Riemannian Realm: Efficient Riemannian Optimization with Loopless Variance Reductioncited by 2
  11. 2024Cohort Squeeze: Beyond a Single Communication Round per Cohort in Cross-Device Federated Learningcited by 2
  12. 2026JacQuant: STE-Free Quantization-Aware Training via Learned Jacobian Surrogatescited by 2
  13. 2023Achieving Linear Speedup with ProxSkip in Distributed Stochastic Optimizationcited by 1
  14. 2023Federated Learning over Hierarchical Wireless Networks: Training Latency Minimization via Submodel Partitioningcited by 1
  15. 2026BiCoLoR: Communication-Efficient Optimization with Bidirectional Compression and Local Trainingcited by 1
  16. 2026LOSCAR-SGD: Local SGD with Communication-Computation Overlap and Delay-Corrected Sparse Model Averagingcited by 1
  17. 2022An Optimal Algorithm for Strongly Convex Min-min Optimizationcited by 0
  18. 2024Near-Optimal Distributed Minimax Optimization under the Second-Order Similaritycited by 0
  19. 2024Convergent Differential Privacy Analysis for General Federated Learningcited by 0
  20. 2024Refined Analysis of Federated Averaging and Federated Richardson-Rombergcited by 0
  21. 2025Extra Clients at No Extra Cost: Overcome Data Heterogeneity in Federated Learning with Filter Decompositioncited by 0