mlsanityData to 14 Oct 2026

Achieving Linear Speedup with ProxSkip in Distributed Stochastic Optimization

arXiv 2310.07983 ↗First posted 12 Oct 2023cs.LG math.OC stat.MLcited by 1

Not on the map. Why?

Abstract (arXiv)

The ProxSkip algorithm for distributed optimization is gaining increasing attention due to its effectiveness in reducing communication. However, existing analyses of ProxSkip are limited to the strongly convex setting and fail to achieve linear speedup with respect to the number of nodes. Key questions regarding its behavior in the non-convex setting and the achievability of linear speedup remain open. In this paper, we revisit decentralized ProxSkip and answer these questions affirmatively. We provide a unified convergence analysis for stochastic non-convex, convex, and strongly convex problems, revealing how gradient noise, local updates, network connectivity, and data heterogeneity jointly determine the convergence behavior. To the best of our knowledge, this is the first analysis showing that decentralized ProxSkip achieves linear speedup in the number of nodes under stochastic gradients. Moreover, our results demonstrate that local updates can effectively reduce communication frequency and improve communication efficiency.

Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 39 of its 54 references that are in the map. First posted on arXiv 12 Oct 2023.

Builds on

39 of 54 references.

References · 39

  1. 2018Local SGD Converges Fast and Communicates Littlecited by 605
  2. 2021Federated Learning Based on Dynamic Regularizationcited by 562
  3. 2017Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descentcited by 502
  4. 2020A Unified Theory of Decentralized SGD with Changing Topology and Local Updatescited by 367
  5. 2019Tighter Theory for Local SGD on Identical and Heterogeneous Datacited by 266
  6. 2018Don't Use Large Mini-Batches, Use Local SGDcited by 202
  7. 2021Achieving Linear Speedup with Partial Worker Participation in Non-IID Federated Learningcited by 193
  8. 2020Federated Learning with Compression: Unified Analysis and Sharp Guaranteescited by 160
  9. 2020Is Local SGD Better than Minibatch SGD?cited by 151
  10. 2016Achieving Geometric Convergence for Distributed Optimization over Time-Varying Graphscited by 150
  11. 2020FedPD: A Federated Learning Framework with Optimal Rates and Adaptivity to Non-IID Datacited by 144
  12. 2018D2: Decentralized Training over Decentralized Datacited by 140
27 more
  1. 2022ProxSkip: Yes! Local Gradient Steps Provably Lead to Communication Acceleration! Finally!cited by 134
  2. 2021Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradientscited by 123
  3. 2018Distributed Stochastic Gradient Tracking Methodscited by 106
  4. 2023Stochastic Controlled Averaging for Federated Learning with Communication Compressioncited by 101
  5. 2017Optimal algorithms for smooth and strongly convex distributed optimization in networkscited by 83
  6. 2019Variance Reduced Local SGD with Lower Communication Complexitycited by 80
  7. 2022An Improved Analysis of Gradient Tracking for Decentralized Machine Learningcited by 69
  8. 2017A decentralized proximal-gradient method with network independent step-sizes and separated convergence ratescited by 51
  9. 2017Exact Diffusion for Distributed Optimization and Learning --- Part I: Algorithm Developmentcited by 50
  10. 2021A Unified and Refined Convergence Analysis for Non-Convex Decentralized Learningcited by 44
  11. 2020Optimal and Practical Algorithms for Smooth and Strongly Convex Decentralized Optimizationcited by 43
  12. 2023Momentum Benefits Non-IID Federated Learning Simply and Provablycited by 38
  13. 2022Variance Reduced ProxSkip: Algorithm, Theory and Application to Federated Learningcited by 33
  14. 2023Decentralized Gradient Tracking with Local Stepscited by 32
  15. 2023Momentum Provably Improves Error Feedback!cited by 31
  16. 2022RandProx: Primal-Dual Optimization Algorithms with Randomized Proximal Updatescited by 28
  17. 2022On the Performance of Gradient Tracking with Local Updatescited by 21
  18. 2020An Optimal Algorithm for Decentralized Finite Sum Optimizationcited by 19
  19. 2022Communication Acceleration of Local Gradient Methods via an Accelerated Primal-Dual Algorithm with Inexact Proxcited by 19
  20. 2021Optimal Gradient Tracking for Decentralized Optimizationcited by 18
  21. 2020Variance Reduced EXTRA and DIGing and Their Optimal Acceleration for Strongly Convex Decentralized Optimizationcited by 13
  22. 2023CEDAS: A Compressed Decentralized Stochastic Gradient Method with Improved Convergencecited by 9
  23. 2022DISA: A Dual Inexact Splitting Algorithm for Distributed Convex Composite Optimizationcited by 5
  24. 2023Accelerated AB/Push-Pull Methods for Distributed Optimization over Time-Varying Directed Networkscited by 5
  25. 2023Decentralized Inexact Proximal Gradient Method With Network-Independent Stepsizes for Convex Composite Optimizationcited by 5
  26. 2021Communication-efficient Distributed Cooperative Learning with Compressed Beliefscited by 4
  27. 2023On the Computation-Communication Trade-Off with A Flexible Gradient Tracking Approachcited by 4

Built on by

Cited by year

Citing papers per year: 2024: 1.

1 paper.

  1. 2024Towards Faster Decentralized Stochastic Optimization with Communication Compressioncited by 5