# Convergence Analysis of Decentralized ASGD

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 76 references that are in the map.
- First posted on arXiv 7 Sep 2023.

## Builds on (most cited first, 30 of 33)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [High-Resolution Image Synthesis with Latent Diffusion Models](https://mlsanity.com/paper/2112.10752/) (2021)
- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Very Deep Convolutional Networks for Large-Scale Image Recognition](https://mlsanity.com/paper/1409.1556/) (2014)
- [Local SGD Converges Fast and Communicates Little](https://mlsanity.com/paper/1805.09767/) (2018)
- [Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent](https://mlsanity.com/paper/1705.09056/) (2017)
- [Learning under Concept Drift: A Review](https://mlsanity.com/paper/2004.05785/) (2020)
- [Symbolic Discovery of Optimization Algorithms](https://mlsanity.com/paper/2302.06675/) (2023)
- [A Unified Theory of Decentralized SGD with Changing Topology and Local Updates](https://mlsanity.com/paper/2003.10422/) (2020)
- [Asynchronous Federated Optimization](https://mlsanity.com/paper/1903.03934/) (2019)
- [Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication](https://mlsanity.com/paper/1902.00340/) (2019)
- [Online Learning: A Comprehensive Survey](https://mlsanity.com/paper/1802.02871/) (2018)
- [Federated Learning with Buffered Asynchronous Aggregation](https://mlsanity.com/paper/2106.06639/) (2021)
- [Pushing the Limits of Semi-Supervised Learning for Automatic Speech Recognition](https://mlsanity.com/paper/2010.10504/) (2020)
- [Asynchronous Decentralized Parallel Stochastic Gradient Descent](https://mlsanity.com/paper/1710.06952/) (2017)
- [Demystifying Parallel and Distributed Deep Learning: An In-Depth Concurrency Analysis](https://mlsanity.com/paper/1802.09941/) (2018)
- [Stochastic Gradient Push for Distributed Deep Learning](https://mlsanity.com/paper/1811.10792/) (2018)
- [Asynchronous Parallel Stochastic Gradient for Nonconvex Optimization](https://mlsanity.com/paper/1506.08272/) (2015)
- [Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learning](https://mlsanity.com/paper/2206.08307/) (2022)
- [Asynchronous SGD Beats Minibatch SGD Under Arbitrary Delays](https://mlsanity.com/paper/2206.07638/) (2022)
- [A Tight Convergence Analysis for Stochastic Gradient Descent with Delayed Updates](https://mlsanity.com/paper/1806.10188/) (2018)
- [Scalable Deep Learning on Distributed Infrastructures: Challenges, Techniques and Tools](https://mlsanity.com/paper/1903.11314/) (2019)
- [An Asynchronous Mini-Batch Algorithm for Regularized Stochastic Optimization](https://mlsanity.com/paper/1505.04824/) (2015)
- [Asynchronous Stochastic Optimization Robust to Arbitrary Delays](https://mlsanity.com/paper/2106.11879/) (2021)
- [SWIFT: Rapid Decentralized Federated Learning via Wait-Free Model Communication](https://mlsanity.com/paper/2210.14026/) (2022)
- [Asynchronous Gradient-Push](https://mlsanity.com/paper/1803.08950/) (2018)
- [Hopular: Modern Hopfield Networks for Tabular Data](https://mlsanity.com/paper/2206.00664/) (2022)
- [Unbounded Gradients in Federated Learning with Buffered Asynchronous Aggregation](https://mlsanity.com/paper/2210.01161/) (2022)
- [An online learning approach to dynamic pricing and capacity sizing in service systems](https://mlsanity.com/paper/2009.02911/) (2020)
- [Delay-agnostic Asynchronous Distributed Optimization](https://mlsanity.com/paper/2303.18034/) (2023)

## Built on by (most cited first, 2 of 2)

- [Distributed Stochastic Gradient Descent with Staleness: A Stochastic Delay Differential Equation Based Framework](https://mlsanity.com/paper/2406.11159/) (2024)
- [Cooperative SGD with Dynamic Mixing Matrices](https://mlsanity.com/paper/2508.14565/) (2025)

## Abstract (arXiv)

Over the last decades, Stochastic Gradient Descent (SGD) has been intensively studied by the Machine Learning community. Despite its versatility and excellent performance, the optimization of large models via SGD still is a time-consuming task. To reduce training time, it is common to distribute the training process across multiple devices. Recently, it has been shown that the convergence of asynchronous SGD (ASGD) will always be faster than mini-batch SGD. However, despite these improvements in the theoretical bounds, most ASGD convergence-rate proofs still rely on a centralized parameter server, which is prone to become a bottleneck when scaling out the gradient computations across many distributed processes. In this paper, we present a novel convergence-rate analysis for decentralized and asynchronous SGD (DASGD) which does not require partial synchronization among nodes nor restrictive network topologies. Specifically, we provide a bound of O(σε-2) + O(QSavgε-3/2) + O(Savgε-1) for the convergence rate of DASGD, where Savg is the average staleness between models, Q is a constant that bounds the norm of the gradients, and ε is a (small) error that is allowed within the bound. Furthermore, when gradients are not bounded, we prove the convergence rate of DASGD to be O(σε-2) + O(√hatSavghatSmaxε-1), with hatSmax and hatSavg representing a loose version of the average and maximum staleness, respectively. Our convergence proof holds for a fixed stepsize and any non-convex, homogeneous, and L-smooth objective function. We anticipate that our results will be of high relevance for the adoption of DASGD by a broad community of researchers and developers.