# DADAO: Decoupled Accelerated Decentralized Asynchronous Optimization

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 56 references that are in the map.
- First posted on arXiv 26 Jul 2022.

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

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [CVXPY: A Python-Embedded Modeling Language for Convex Optimization](https://mlsanity.com/paper/1603.00943/) (2016)
- [A Unified Theory of Decentralized SGD with Changing Topology and Local Updates](https://mlsanity.com/paper/2003.10422/) (2020)
- [EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization](https://mlsanity.com/paper/1404.6264/) (2014)
- [Achieving Geometric Convergence for Distributed Optimization over Time-Varying Graphs](https://mlsanity.com/paper/1607.03218/) (2016)
- [ProxSkip: Yes! Local Gradient Steps Provably Lead to Communication Acceleration! Finally!](https://mlsanity.com/paper/2202.09357/) (2022)
- [Optimal algorithms for smooth and strongly convex distributed optimization in networks](https://mlsanity.com/paper/1702.08704/) (2017)
- [Decoupled Greedy Learning of CNNs](https://mlsanity.com/paper/1901.08164/) (2019)
- [An Improved Analysis of Gradient Tracking for Decentralized Machine Learning](https://mlsanity.com/paper/2202.03836/) (2022)
- [A Universal Catalyst for First-Order Optimization](https://mlsanity.com/paper/1506.02186/) (2015)
- [Tight Complexity Bounds for Optimizing Composite Objectives](https://mlsanity.com/paper/1605.08003/) (2016)
- [Optimal and Practical Algorithms for Smooth and Strongly Convex Decentralized Optimization](https://mlsanity.com/paper/2006.11773/) (2020)
- [Improved asynchronous parallel optimization analysis for stochastic incremental methods](https://mlsanity.com/paper/1801.03749/) (2018)
- [Analysis of Stochastic Gradient Descent in Continuous Time](https://mlsanity.com/paper/2004.07177/) (2020)
- [An Optimal Algorithm for Decentralized Finite Sum Optimization](https://mlsanity.com/paper/2005.10675/) (2020)
- [Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks](https://mlsanity.com/paper/2106.04469/) (2021)
- [Optimal Gradient Tracking for Decentralized Optimization](https://mlsanity.com/paper/2110.05282/) (2021)
- [A principled framework for the design and analysis of token algorithms](https://mlsanity.com/paper/2205.15015/) (2022)
- [Proximal Splitting Algorithms for Convex Optimization: A Tour of Recent Advances, with New Twists](https://mlsanity.com/paper/1912.00137/) (2019)
- [Accelerated Primal-Dual Gradient Method for Smooth and Convex-Concave Saddle-Point Problems with Bilinear Coupling](https://mlsanity.com/paper/2112.15199/) (2021)
- [A Continuized View on Nesterov Acceleration for Stochastic Gradient Descent and Randomized Gossip](https://mlsanity.com/paper/2106.07644/) (2021)
- [ADOM: Accelerated Decentralized Optimization Method for Time-Varying Networks](https://mlsanity.com/paper/2102.09234/) (2021)
- [Dual-Free Stochastic Decentralized Optimization with Variance Reduction](https://mlsanity.com/paper/2006.14384/) (2020)
- [Accelerated Decentralized Optimization with Local Updates for Smooth and Strongly Convex Objectives](https://mlsanity.com/paper/1810.02660/) (2018)
- [Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimization](https://mlsanity.com/paper/2104.02596/) (2021)
- [An Accelerated Decentralized Stochastic Proximal Algorithm for Finite Sums](https://mlsanity.com/paper/1905.11394/) (2019)
- [An Optimal Algorithm for Strongly Convex Minimization under Affine Constraints](https://mlsanity.com/paper/2102.11079/) (2021)
- [Distributed Proximal Splitting Algorithms with Rates and Acceleration](https://mlsanity.com/paper/2010.00952/) (2020)
- [Decoupled Greedy Learning of CNNs for Synchronous and Asynchronous Distributed Learning](https://mlsanity.com/paper/2106.06401/) (2021)
- [Asynchrony and Acceleration in Gossip Algorithms](https://mlsanity.com/paper/2011.02379/) (2020)

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

- [A2CiD2: Accelerating Asynchronous Communication in Decentralized Deep Learning](https://mlsanity.com/paper/2306.08289/) (2023)
- [ACCO: Accumulate While You Communicate for Communication-Overlapped Sharded LLM Training](https://mlsanity.com/paper/2406.02613/) (2024)
- [DRACO: Decentralized Asynchronous Federated Learning over Row-Stochastic Wireless Networks](https://mlsanity.com/paper/2406.13533/) (2024)
- [Distributed Event-Based Learning via ADMM](https://mlsanity.com/paper/2405.10618/) (2024)
- [Model Parallelism With Subnetwork Data Parallelism](https://mlsanity.com/paper/2507.09029/) (2025)
- [Meta-learning Optimizers for Communication-Efficient Learning](https://mlsanity.com/paper/2312.02204/) (2023)
- [Unifying Local Communications and Local Updates for LLM Pretraining](https://mlsanity.com/paper/2606.11081/) (2026)
- [Stochastic convergence of parallel asynchronous adaptive first-order methods](https://mlsanity.com/paper/2606.01787/) (2026)

## Abstract (arXiv)

This work introduces DADAO: the first decentralized, accelerated, asynchronous, primal, first-order algorithm to minimize a sum of L-smooth and μ-strongly convex functions distributed over a given network of size n. Our key insight is based on modeling the local gradient updates and gossip communication procedures with separate independent Poisson Point Processes. This allows us to decouple the computation and communication steps, which can be run in parallel, while making the whole approach completely asynchronous. This leads to communication acceleration compared to synchronous approaches. Our new method employs primal gradients and does not use a multi-consensus inner loop nor other ad-hoc mechanisms such as Error Feedback, Gradient Tracking, or a Proximal operator. By relating the inverse of the smallest positive eigenvalue of the Laplacian matrix chi1 and the maximal resistance chi2≤ chi1 of the graph to a sufficient minimal communication rate between the nodes of the network, we show that our algorithm requires O(n√fracLμlog(frac1ε)) local gradients and only O(n√chi1chi2√fracLμlog(frac1ε)) communications to reach a precision ε, up to logarithmic terms. Thus, we simultaneously obtain an accelerated rate for both computations and communications, leading to an improvement over state-of-the-art works, our simulations further validating the strength of our relatively unconstrained method.