# Achieving Linear Convergence in Distributed Asynchronous Multi-agent Optimization

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Mar 2018.

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

- [Hierarchical Federated Learning with Multi-Timescale Gradient Correction](https://mlsanity.com/paper/2409.18448/) (2024)
- [Distributed Online Private Learning of Convex Nondecomposable Objectives](https://mlsanity.com/paper/2206.07944/) (2022)
- [A survey on secure decentralized optimization and learning](https://mlsanity.com/paper/2408.08628/) (2024)
- [Distributed Conformal Prediction via Message Passing](https://mlsanity.com/paper/2501.14544/) (2025)
- [Asynchronous speedup in decentralized optimization](https://mlsanity.com/paper/2106.03585/) (2021)
- [Robust Fully-Asynchronous Methods for Distributed Training over General Architecture](https://mlsanity.com/paper/2307.11617/) (2023)
- [Robust Online Learning over Networks](https://mlsanity.com/paper/2309.00520/) (2023)
- [Provably Accelerated Decentralized Gradient Method Over Unbalanced Directed Graphs](https://mlsanity.com/paper/2107.12065/) (2021)
- [Asynchronous Distributed Optimization with Delay-free Parameters](https://mlsanity.com/paper/2312.06508/) (2023)
- [Distributed Learning over Arbitrary Topology: Linear Speed-Up with Polynomial Transient Time](https://mlsanity.com/paper/2503.16123/) (2025)
- [Asynchronous Decentralized SGD under Non-Convexity: A Block-Coordinate Descent Framework](https://mlsanity.com/paper/2505.10322/) (2025)

## Abstract (arXiv)

This papers studies multi-agent (convex and nonconvex) optimization over static digraphs. We propose a general distributed asynchronous algorithmic framework whereby i) agents can update their local variables as well as communicate with their neighbors at any time, without any form of coordination; and ii) they can perform their local computations using (possibly) delayed, out-of-sync information from the other agents. Delays need not be known to the agent or obey any specific profile, and can also be time-varying (but bounded). The algorithm builds on a tracking mechanism that is robust against asynchrony (in the above sense), whose goal is to estimate locally the average of agents' gradients. When applied to strongly convex functions, we prove that it converges at an R-linear (geometric) rate as long as the step-size is sufficiently small. A sublinear convergence rate is proved, when nonconvex problems and/or diminishing, it uncoordinated step-sizes are considered. To the best of our knowledge, this is the first distributed algorithm with provable geometric convergence rate in such a general asynchronous setting. Preliminary numerical results demonstrate the efficacy of the proposed algorithm and validate our theoretical findings.