mlsanityData to 7 Oct 2026

Revisiting Optimal Convergence Rate for Smooth and Non-convex Stochastic Decentralized Optimization

arXiv 2210.07863 ↗First posted 14 Oct 2022cs.LG math.OCcited by 22

Not on the map. Why?

Abstract (arXiv)

Decentralized optimization is effective to save communication in large-scale machine learning. Although numerous algorithms have been proposed with theoretical guarantees and empirical successes, the performance limits in decentralized optimization, especially the influence of network topology and its associated weight matrix on the optimal convergence rate, have not been fully understood. While (Lu and Sa, 2021) have recently provided an optimal rate for non-convex stochastic decentralized optimization with weight matrices defined over linear graphs, the optimal rate with general weight matrices remains unclear. This paper revisits non-convex stochastic decentralized optimization and establishes an optimal convergence rate with general weight matrices. In addition, we also establish the optimal rate when non-convex loss functions further satisfy the Polyak-Lojasiewicz (PL) condition. Following existing lines of analysis in literature cannot achieve these results. Instead, we leverage the Ring-Lattice graph to admit general weight matrices while maintaining the optimal relation between the graph diameter and weight matrix connectivity. Lastly, we develop a new decentralized algorithm to nearly attain the above two optimal rates under additional mild conditions.

Key facts. Cited by 22 papers in the map (data through 7 Oct 2026). Builds on 53 of its 93 references that are in the map. First posted on arXiv 14 Oct 2022.

Builds on

53 of 93 references.

References · 53

  1. 2015Deep Residual Learning for Image Recognitioncited by 51,809
  2. 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,160
  3. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,592
  4. 2019On the Convergence of FedAvg on Non-IID Datacited by 1,220
  5. 2018Local SGD Converges Fast and Communicates Littlecited by 595
  6. 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 526
  7. 2017Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descentcited by 496
  8. 2019Bayesian Nonparametric Federated Learning of Neural Networkscited by 385
  9. 2020A Unified Theory of Decentralized SGD with Changing Topology and Local Updatescited by 361
  10. 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 303
  11. 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 283
  12. 2019On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimizationcited by 178
38 more
  1. 2014EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimizationcited by 160
  2. 2017Asynchronous Decentralized Parallel Stochastic Gradient Descentcited by 159
  3. 2013On the Convergence of Decentralized Gradient Descentcited by 158
  4. 2018Stochastic Gradient Push for Distributed Deep Learningcited by 152
  5. 2016Achieving Geometric Convergence for Distributed Optimization over Time-Varying Graphscited by 149
  6. 2018D2: Decentralized Training over Decentralized Datacited by 140
  7. 2017Lower Bounds for Finding Stationary Points Icited by 125
  8. 2017Network Topology and Communication-Computation Tradeoffs in Decentralized Optimizationcited by 119
  9. 2016NEXT: In-Network Nonconvex Optimizationcited by 107
  10. 2019DoubleSqueeze: Parallel Stochastic Gradient Descent with Double-Pass Error-Compensated Compressioncited by 98
  11. 2017Optimal algorithms for smooth and strongly convex distributed optimization in networkscited by 81
  12. 2013Distributed optimization over time-varying directed graphscited by 77
  13. 2021Quasi-Global Momentum: Accelerating Decentralized Deep Learning on Heterogeneous Datacited by 69
  14. 2022An Improved Analysis of Gradient Tracking for Decentralized Machine Learningcited by 68
  15. 2019MATCHA: Speeding Up Decentralized SGD via Matching Decomposition Samplingcited by 67
  16. 2019Stochastic Distributed Learning with Gradient Quantization and Variance Reductioncited by 64
  17. 2020Optimal Complexity in Decentralized Trainingcited by 59
  18. 2013On the Linear Convergence of the ADMM in Decentralized Consensus Optimizationcited by 57
  19. 2017Lower Bounds for Finding Stationary Points II: First-Order Methodscited by 55
  20. 2018How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGDcited by 55
  21. 2021Exponential Graph is Provably Efficient for Decentralized Deep Trainingcited by 55
  22. 2020An improved convergence analysis for decentralized online stochastic non-convex optimizationcited by 53
  23. 2017A decentralized proximal-gradient method with network independent step-sizes and separated convergence ratescited by 51
  24. 2017Exact Diffusion for Distributed Optimization and Learning --- Part I: Algorithm Developmentcited by 50
  25. 2020Optimal and Practical Algorithms for Smooth and Strongly Convex Decentralized Optimizationcited by 43
  26. 2021A Unified and Refined Convergence Analysis for Non-Convex Decentralized Learningcited by 43
  27. 2018Optimal Algorithms for Non-Smooth Distributed Optimization in Networkscited by 41
  28. 2021DecentLaM: Decentralized Momentum SGD for Large-batch Deep Trainingcited by 40
  29. 2022Lower Bounds and Nearly Optimal Algorithms in Distributed Learning with Communication Compressioncited by 33
  30. 2015An optimal randomized incremental gradient methodcited by 32
  31. 2019DADAM: A Consensus-based Distributed Adaptive Gradient Method for Online Optimizationcited by 30
  32. 2021Removing Data Heterogeneity Influence Enhances Network Topology Dependence of Decentralized SGDcited by 28
  33. 2018A Dual Approach for Optimal Algorithms in Distributed Optimization over Networkscited by 27
  34. 2021Accelerating Gossip SGD with Periodic Global Averagingcited by 25
  35. 2021Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networkscited by 19
  36. 2018Lower Bounds for Parallel and Randomized Convex Optimizationcited by 17
  37. 2020Towards accelerated rates for distributed optimization over time-varying networkscited by 10
  38. 2018Distributed Non-Convex First-Order Optimization and Information Processing: Lower Complexity Bounds and Rate Optimal Algorithmscited by 6

50 most cited of 53 All 53 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 7; 2024: 3; 2025: 6; 2026: 6.

22 papers.

Sort:

  1. 2023Unbiased Compression Saves Communication in Distributed Optimization: When and How Much?cited by 14
  2. 2023Convergence of Adam for Non-convex Objectives: Relaxed Hyperparameters and Non-ergodic Casecited by 13
  3. 2023Lower Bounds and Accelerated Algorithms in Distributed Stochastic Optimization with Communication Compressioncited by 11
  4. 2023CEDAS: A Compressed Decentralized Stochastic Gradient Method with Improved Convergencecited by 9
  5. 2023Optimal Multitask Linear Regression and Contextual Bandits under Sparse Heterogeneitycited by 7
  6. 2023On the Computation-Communication Trade-Off with A Flexible Gradient Tracking Approachcited by 4
  7. 2025DES-LOC: Desynced Low Communication Adaptive Optimizers for Training Foundation Modelscited by 3
  8. 2024On the Complexity of Finite-Sum Smooth Optimization under the Polyak-Lojasiewicz Conditioncited by 2
  9. 2024Quantization Avoids Saddle Points in Distributed Optimizationcited by 2
  10. 2025MT-DAO: Multi-Timescale Distributed Adaptive Optimizers with Local Updatescited by 2
  11. 2023Structured Cooperative Learning with Graphical Model Priorscited by 1
  12. 2024OledFL: Unleashing the Potential of Decentralized Federated Learning via Opposite Lookahead Enhancementcited by 1
10 more
  1. 2025Exploiting Similarity for Computation and Communication-Efficient Decentralized Optimizationcited by 1
  2. 2025Unveiling the Power of Multiple Gossip Steps: A Stability-Based Generalization Analysis in Decentralized Trainingcited by 1
  3. 2026Near-Optimal Decentralized Stochastic Nonconvex Optimization with Heavy-Tailed Noisecited by 1
  4. 2026Accelerated Decentralized Stochastic Gradient Descent for Strongly Convex Optimizationcited by 1
  5. 2025Decentralized Stochastic Nonconvex Optimization under the (L0,L1)-Smoothnesscited by 0
  6. 2025Pareto-optimal Trade-offs Between Communication and Computation with Flexible Gradient Trackingcited by 0
  7. 2026Topology-Independent Robustness of the Weighted Mean under Label Poisoning Attacks in Heterogeneous Decentralized Learningcited by 0
  8. 2026Provably Convergent Decentralized Optimization over Directed Graphs under Generalized Smoothnesscited by 0
  9. 2026Decentralized Non-convex Stochastic Optimization with Heterogeneous Variancecited by 0
  10. 2026Improved Convergence Analysis of Topology Dependence in Decentralized SGDcited by 0