# Asynchronous Decentralized SGD under Non-Convexity: A Block-Coordinate Descent Framework

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 23 of its 29 references that are in the map.
- First posted on arXiv 15 May 2025.

## Builds on (most cited first, 23 of 23)

- [Very Deep Convolutional Networks for Large-Scale Image Recognition](https://mlsanity.com/paper/1409.1556/) (2014)
- [A Unified Theory of Decentralized SGD with Changing Topology and Local Updates](https://mlsanity.com/paper/2003.10422/) (2020)
- [On the Convergence of Decentralized Gradient Descent](https://mlsanity.com/paper/1310.7063/) (2013)
- [Asynchronous Decentralized Parallel Stochastic Gradient Descent](https://mlsanity.com/paper/1710.06952/) (2017)
- [Achieving Geometric Convergence for Distributed Optimization over Time-Varying Graphs](https://mlsanity.com/paper/1607.03218/) (2016)
- [Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learning](https://mlsanity.com/paper/2206.08307/) (2022)
- [Push-Pull Gradient Methods for Distributed Optimization in Networks](https://mlsanity.com/paper/1810.06653/) (2018)
- [On Nonconvex Decentralized Gradient Descent](https://mlsanity.com/paper/1608.05766/) (2016)
- [Asynchronous Stochastic Coordinate Descent: Parallelism and Convergence Properties](https://mlsanity.com/paper/1403.3862/) (2014)
- [ARock: an Algorithmic Framework for Asynchronous Parallel Coordinate Updates](https://mlsanity.com/paper/1506.02396/) (2015)
- [SWIFT: Rapid Decentralized Federated Learning via Wait-Free Model Communication](https://mlsanity.com/paper/2210.14026/) (2022)
- [Robust Asynchronous Stochastic Gradient-Push: Asymptotically Optimal and Network-Independent Performance for Strongly Convex Functions](https://mlsanity.com/paper/1811.03982/) (2018)
- [FusionAI: Decentralized Training and Deploying LLMs with Massive Consumer-Level GPUs](https://mlsanity.com/paper/2309.01172/) (2023)
- [ASAGA: Asynchronous Parallel SAGA](https://mlsanity.com/paper/1606.04809/) (2016)
- [Asynchronous Coordinate Descent under More Realistic Assumptions](https://mlsanity.com/paper/1705.08494/) (2017)
- [Achieving Linear Convergence in Distributed Asynchronous Multi-agent Optimization](https://mlsanity.com/paper/1803.10359/) (2018)
- [Distributed Proximal Gradient Algorithm for Partially Asynchronous Computer Clusters](https://mlsanity.com/paper/1704.03540/) (2017)
- [Decentralized Asynchronous Non-convex Stochastic Optimization on Directed Graphs](https://mlsanity.com/paper/2110.10406/) (2021)
- [Delay-agnostic Asynchronous Distributed Optimization](https://mlsanity.com/paper/2303.18034/) (2023)
- [Asynchronous Optimization over Graphs: Linear Convergence under Error Bound Conditions](https://mlsanity.com/paper/2010.09057/) (2020)
- [Faster Asynchronous Nonconvex Block Coordinate Descent with Locally Chosen Stepsizes](https://mlsanity.com/paper/2203.11307/) (2022)
- [Robust Fully-Asynchronous Methods for Distributed Training over General Architecture](https://mlsanity.com/paper/2307.11617/) (2023)
- [Asynchronous Delay-Aware Accelerated Proximal Coordinate Descent for Nonconvex Nonsmooth Problems](https://mlsanity.com/paper/1902.01856/) (2019)

## Abstract (arXiv)

Decentralized optimization has become vital for leveraging distributed data without central control, enhancing scalability and privacy. However, practical deployments face fundamental challenges due to heterogeneous computation speeds and unpredictable communication delays. This paper introduces a refined model of Asynchronous Decentralized Stochastic Gradient Descent (ADSGD) under practical assumptions of bounded computation and communication times. To understand the convergence of ADSGD, we first analyze Asynchronous Stochastic Block Coordinate Descent (ASBCD) as a tool, and then show that ADSGD converges under computation-delay-independent step sizes. The convergence result is established without assuming bounded data heterogeneity. Empirical experiments reveal that ADSGD outperforms existing methods in wall-clock convergence time across various scenarios. With its simplicity, efficiency in memory and communication, and resilience to communication and computation delays, ADSGD is well-suited for real-world decentralized learning tasks.