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

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

## Key facts

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

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

- [A Field Guide to Federated Optimization](https://mlsanity.com/paper/2107.06917/) (2021)
- [Federated Multi-Task Learning under a Mixture of Distributions](https://mlsanity.com/paper/2108.10252/) (2021)
- [Generalized Federated Learning via Sharpness Aware Minimization](https://mlsanity.com/paper/2206.02618/) (2022)
- [Decentralized Federated Learning: Fundamentals, State of the Art, Frameworks, Trends, and Challenges](https://mlsanity.com/paper/2211.08413/) (2022)
- [EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedback](https://mlsanity.com/paper/2106.05203/) (2021)
- [Decentralized Federated Averaging](https://mlsanity.com/paper/2104.11375/) (2021)
- [DENSE: Data-Free One-Shot Federated Learning](https://mlsanity.com/paper/2112.12371/) (2021)
- [Edge Artificial Intelligence for 6G: Vision, Enabling Technologies, and Applications](https://mlsanity.com/paper/2111.12444/) (2021)
- [Decentralized Training of Foundation Models in Heterogeneous Environments](https://mlsanity.com/paper/2206.01288/) (2022)
- [Decentralized Federated Learning: A Survey and Perspective](https://mlsanity.com/paper/2306.01603/) (2023)
- [Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learning](https://mlsanity.com/paper/2206.08307/) (2022)
- [MARINA: Faster Non-Convex Distributed Learning with Compression](https://mlsanity.com/paper/2102.07845/) (2021)
- [1-bit Adam: Communication Efficient Large-Scale Training with Adam's Convergence Speed](https://mlsanity.com/paper/2102.02888/) (2021)
- [DisPFL: Towards Communication-Efficient Personalized Federated Learning via Decentralized Sparse Training](https://mlsanity.com/paper/2206.00187/) (2022)
- [Quasi-Global Momentum: Accelerating Decentralized Deep Learning on Heterogeneous Data](https://mlsanity.com/paper/2102.04761/) (2021)
- [An Improved Analysis of Gradient Tracking for Decentralized Machine Learning](https://mlsanity.com/paper/2202.03836/) (2022)
- [From Distributed Machine Learning to Federated Learning: A Survey](https://mlsanity.com/paper/2104.14362/) (2021)
- [AdaptSFL: Adaptive Split Federated Learning in Resource-constrained Edge Networks](https://mlsanity.com/paper/2403.13101/) (2024)
- [Asynchronous SGD Beats Minibatch SGD Under Arbitrary Delays](https://mlsanity.com/paper/2206.07638/) (2022)
- [SWARM Parallelism: Training Large Models Can Be Surprisingly Communication-Efficient](https://mlsanity.com/paper/2301.11913/) (2023)
- [Distributed Deep Learning in Open Collaborations](https://mlsanity.com/paper/2106.10207/) (2021)
- [Exponential Graph is Provably Efficient for Decentralized Deep Training](https://mlsanity.com/paper/2110.13363/) (2021)
- [Decentralized Federated Learning: Balancing Communication and Computing Costs](https://mlsanity.com/paper/2107.12048/) (2021)
- [Deep Federated Learning for Autonomous Driving](https://mlsanity.com/paper/2110.05754/) (2021)
- [Consensus Control for Decentralized Deep Learning](https://mlsanity.com/paper/2102.04828/) (2021)
- [Byzantine-Robust Decentralized Federated Learning](https://mlsanity.com/paper/2406.10416/) (2024)
- [Improving the Model Consistency of Decentralized Federated Learning](https://mlsanity.com/paper/2302.04083/) (2023)
- [Rethinking gradient sparsification as total error minimization](https://mlsanity.com/paper/2108.00951/) (2021)
- [BEER: Fast O(1/T) Rate for Decentralized Nonconvex Optimization with Communication Compression](https://mlsanity.com/paper/2201.13320/) (2022)
- [DecentLaM: Decentralized Momentum SGD for Large-batch Deep Training](https://mlsanity.com/paper/2104.11981/) (2021)

## 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.