mlsanityData to 14 Oct 2026

Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent

arXiv 1705.09056 ↗First posted 25 May 2017math.OC cs.DC cs.LGcited by 502

Not on the map. Why?

Abstract (arXiv)

Most distributed machine learning systems nowadays, including TensorFlow and CNTK, are built in a centralized fashion. One bottleneck of centralized algorithms lies on high communication cost on the central node. Motivated by this, we ask, can decentralized algorithms be faster than its centralized counterpart? Although decentralized PSGD (D-PSGD) algorithms have been studied by the control community, existing analysis and theory do not show any advantage over centralized PSGD (C-PSGD) algorithms, simply assuming the application scenario where only the decentralized network is available. In this paper, we study a D-PSGD algorithm and provide the first theoretical analysis that indicates a regime in which decentralized algorithms might outperform centralized algorithms for distributed stochastic gradient descent. This is because D-PSGD has comparable total computational complexities to C-PSGD but requires much less communication cost on the busiest node. We further conduct an empirical study to validate our theoretical analysis across multiple frameworks (CNTK and Torch), different network configurations, and computation platforms up to 112 GPUs. On network configurations with low bandwidth or high latency, D-PSGD can be up to one order of magnitude faster than its well-optimized centralized counterparts.

Key facts. Cited by 502 papers in the map (data through 14 Oct 2026). First posted on arXiv 25 May 2017.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2020: 1; 2021: 81; 2022: 92; 2023: 99; 2024: 86; 2025: 70; 2026: 73.

502 papers.

Sort:

By area:

  1. 2021A Field Guide to Federated Optimizationcited by 315
  2. 2021Federated Multi-Task Learning under a Mixture of Distributionscited by 192
  3. 2022Generalized Federated Learning via Sharpness Aware Minimizationcited by 144
  4. 2022Decentralized Federated Learning: Fundamentals, State of the Art, Frameworks, Trends, and Challengescited by 138
  5. 2021EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedbackcited by 133
  6. 2021Decentralized Federated Averagingcited by 114
  7. 2021DENSE: Data-Free One-Shot Federated Learningcited by 100
  8. 2021Edge Artificial Intelligence for 6G: Vision, Enabling Technologies, and Applicationscited by 97
  9. 2022Decentralized Training of Foundation Models in Heterogeneous Environmentscited by 87
  10. 2023Decentralized Federated Learning: A Survey and Perspectivecited by 86
  11. 2022Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learningcited by 79
  12. 2021MARINA: Faster Non-Convex Distributed Learning with Compressioncited by 78
38 more
  1. 20211-bit Adam: Communication Efficient Large-Scale Training with Adam's Convergence Speedcited by 75
  2. 2022DisPFL: Towards Communication-Efficient Personalized Federated Learning via Decentralized Sparse Trainingcited by 74
  3. 2021Quasi-Global Momentum: Accelerating Decentralized Deep Learning on Heterogeneous Datacited by 69
  4. 2022An Improved Analysis of Gradient Tracking for Decentralized Machine Learningcited by 69
  5. 2021From Distributed Machine Learning to Federated Learning: A Surveycited by 66
  6. 2024AdaptSFL: Adaptive Split Federated Learning in Resource-constrained Edge Networkscited by 64
  7. 2022Asynchronous SGD Beats Minibatch SGD Under Arbitrary Delayscited by 63
  8. 2023SWARM Parallelism: Training Large Models Can Be Surprisingly Communication-Efficientcited by 59
  9. 2021Distributed Deep Learning in Open Collaborationscited by 58
  10. 2021Exponential Graph is Provably Efficient for Decentralized Deep Trainingcited by 56
  11. 2021Decentralized Federated Learning: Balancing Communication and Computing Costscited by 55
  12. 2021Deep Federated Learning for Autonomous Drivingcited by 54
  13. 2021Consensus Control for Decentralized Deep Learningcited by 49
  14. 2024Byzantine-Robust Decentralized Federated Learningcited by 48
  15. 2023Improving the Model Consistency of Decentralized Federated Learningcited by 45
  16. 2021Rethinking gradient sparsification as total error minimizationcited by 41
  17. 2022BEER: Fast O(1/T) Rate for Decentralized Nonconvex Optimization with Communication Compressioncited by 41
  18. 2021DecentLaM: Decentralized Momentum SGD for Large-batch Deep Trainingcited by 40
  19. 2021RelaySum for Decentralized Deep Learning on Heterogeneous Datacited by 39
  20. 2022On the Unreasonable Effectiveness of Federated Averaging with Heterogeneous Datacited by 38
  21. 2022Topology-aware Generalization of Decentralized SGDcited by 38
  22. 2024Hierarchical Split Federated Learning: Convergence Analysis and System Optimizationcited by 38
  23. 2021Quantized Federated Learning under Transmission Delay and Outage Constraintscited by 37
  24. 2021Moshpit SGD: Communication-Efficient Decentralized Training on Heterogeneous Unreliable Devicescited by 36
  25. 2021Decentralized Riemannian Gradient Descent on the Stiefel Manifoldcited by 33
  26. 2021Cross-Gradient Aggregation for Decentralized Learning from Non-IID datacited by 33
  27. 2022Lower Bounds and Nearly Optimal Algorithms in Distributed Learning with Communication Compressioncited by 33
  28. 2022Refined Convergence and Topology Learning for Decentralized SGD with Heterogeneous Datacited by 32
  29. 2022Decentralized Gossip-Based Stochastic Bilevel Optimization over Communication Networkscited by 32
  30. 2023Decentralized Gradient Tracking with Local Stepscited by 32
  31. 2021DataLens: Scalable Privacy Preserving Training via Gradient Compression and Aggregationcited by 31
  32. 2022Byzantine-Robust Decentralized Learning via ClippedGossipcited by 31
  33. 2021SpreadGNN: Serverless Multi-task Federated Learning for Graph Neural Networkscited by 30
  34. 2022Fine-tuning Language Models over Slow Networks using Activation Compression with Guaranteescited by 30
  35. 2021Removing Data Heterogeneity Influence Enhances Network Topology Dependence of Decentralized SGDcited by 29
  36. 2023Why Batch Normalization Damage Federated Learning on Non-IID Data?cited by 29
  37. 2022On the Impossible Safety of Large AI Modelscited by 28
  38. 2022Beyond spectral gap: The role of the topology in decentralized learningcited by 27

50 most cited of 502 All 502 (JSON)