# AsySPA: An Exact Asynchronous Algorithm for Convex Optimization Over Digraphs

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Aug 2018.

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

- [A Federated Data-Driven Evolutionary Algorithm](https://mlsanity.com/paper/2102.08288/) (2021)
- [Achieving Model Fairness in Vertical Federated Learning](https://mlsanity.com/paper/2109.08344/) (2021)
- [DRACO: Decentralized Asynchronous Federated Learning over Row-Stochastic Wireless Networks](https://mlsanity.com/paper/2406.13533/) (2024)
- [Distributed Online Private Learning of Convex Nondecomposable Objectives](https://mlsanity.com/paper/2206.07944/) (2022)
- [Asynchronous Distributed Optimization with Delay-free Parameters](https://mlsanity.com/paper/2312.06508/) (2023)
- [Asynchronous Parallel Policy Gradient Methods for the Linear Quadratic Regulator](https://mlsanity.com/paper/2407.03233/) (2024)
- [An Asynchronous Decentralized Algorithm for Wasserstein Barycenter Problem](https://mlsanity.com/paper/2304.11653/) (2023)

## Abstract (arXiv)

This paper proposes a novel exact distributed asynchronous subgradient-push algorithm (AsySPA) to solve an additive cost optimization problem over directed graphs where each node only has access to a local convex function and updates asynchronously with an arbitrary rate. Specifically, each node of a strongly connected digraph does not wait for updates from other nodes but simply starts a new update within any bounded time interval by using local information available from its in-neighbors. "Exact" means that every node of the AsySPA can asymptotically converge to the same optimal solution, even under different update rates among nodes and bounded communication delays. To address uneven update rates, we design a simple mechanism to adaptively adjust stepsizes per update in each node, which is substantially different from the existing works. Then, we construct a delay-free augmented system to address asynchrony and delays, and study its convergence by proposing a generalized subgradient algorithm, which clearly has its own significance and helps us to explicitly evaluate the convergence rate of the AsySPA. Finally, we demonstrate advantages of the AsySPA in both theory and simulation.