# Asynchronous Distributed Optimization with Delay-free Parameters

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 55 references that are in the map.
- First posted on arXiv 11 Dec 2023.

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

- [On the Convergence of Decentralized Gradient Descent](https://mlsanity.com/paper/1310.7063/) (2013)
- [Achieving Geometric Convergence for Distributed Optimization over Time-Varying Graphs](https://mlsanity.com/paper/1607.03218/) (2016)
- [Papaya: Practical, Private, and Scalable Federated Learning](https://mlsanity.com/paper/2111.04877/) (2021)
- [On Nonconvex Decentralized Gradient Descent](https://mlsanity.com/paper/1608.05766/) (2016)
- [Advances in Asynchronous Parallel and Distributed Optimization](https://mlsanity.com/paper/2006.13838/) (2020)
- [Asynchronous Gradient-Push](https://mlsanity.com/paper/1803.08950/) (2018)
- [Robust Asynchronous Stochastic Gradient-Push: Asymptotically Optimal and Network-Independent Performance for Strongly Convex Functions](https://mlsanity.com/paper/1811.03982/) (2018)
- [Asynchronous Iterations in Optimization: New Sequence Results and Sharper Algorithmic Guarantees](https://mlsanity.com/paper/2109.04522/) (2021)
- [Asynchronous Coordinate Descent under More Realistic Assumptions](https://mlsanity.com/paper/1705.08494/) (2017)
- [Distributed heavy-ball: A generalization and acceleration of first-order methods with gradient tracking](https://mlsanity.com/paper/1808.02942/) (2018)
- [Achieving Linear Convergence in Distributed Asynchronous Multi-agent Optimization](https://mlsanity.com/paper/1803.10359/) (2018)
- [Asynchronous Adaptation and Learning over Networks --- Part I: Modeling and Stability Analysis](https://mlsanity.com/paper/1312.5434/) (2013)
- [AsySPA: An Exact Asynchronous Algorithm for Convex Optimization Over Digraphs](https://mlsanity.com/paper/1808.04118/) (2018)
- [Decentralized Asynchronous Non-convex Stochastic Optimization on Directed Graphs](https://mlsanity.com/paper/2110.10406/) (2021)
- [Decentralized Composite Optimization in Stochastic Networks: A Dual Averaging Approach with Linear Convergence](https://mlsanity.com/paper/2106.14075/) (2021)
- [Delay-agnostic Asynchronous Distributed Optimization](https://mlsanity.com/paper/2303.18034/) (2023)
- [Delay-agnostic Asynchronous Coordinate Update Algorithm](https://mlsanity.com/paper/2305.08535/) (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)
- [Asynchronous Adaptation and Learning over Networks - Part II: Performance Analysis](https://mlsanity.com/paper/1312.5438/) (2013)
- [Totally Asynchronous Large-Scale Quadratic Programming: Regularization, Convergence Rates, and Parameter Selection](https://mlsanity.com/paper/2006.09144/) (2020)
- [Convergence Analysis of Dual Decomposition Algorithm in Distributed Optimization: Asynchrony and Inexactness](https://mlsanity.com/paper/2103.02784/) (2021)
- [The distributed dual ascent algorithm is robust to asynchrony](https://mlsanity.com/paper/2105.01372/) (2021)

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

- [Faster Convergence with Less Communication: Broadcast-Based Subgraph Sampling for Decentralized Learning over Wireless Networks](https://mlsanity.com/paper/2401.13779/) (2024)

## Abstract (arXiv)

Existing asynchronous distributed optimization algorithms often use diminishing step-sizes that cause slow practical convergence, or use fixed step-sizes that depend on and decrease with an upper bound of the delays. Not only are such delay bounds hard to obtain in advance, but they also tend to be large and rarely attained, resulting in unnecessarily slow convergence. This paper develops asynchronous versions of two distributed algorithms, Prox-DGD and DGD-ATC, for solving consensus optimization problems over undirected networks. In contrast to alternatives, our algorithms can converge to the fixed point set of their synchronous counterparts using step-sizes that are independent of the delays. We establish convergence guarantees for convex and strongly convex problems under both partial and total asynchrony. We also show that the convergence speed of the two asynchronous methods adjusts to the actual level of asynchrony rather than being constrained by the worst-case. Numerical experiments demonstrate a strong practical performance of our asynchronous algorithms.