# Accelerating Asynchronous Algorithms for Convex Optimization by Momentum Compensation

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Feb 2018.

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

- [Accelerating Perturbed Stochastic Iterates in Asynchronous Lock-Free Optimization](https://mlsanity.com/paper/2109.15292/) (2021)
- [An Asynchronous Decentralized Algorithm for Wasserstein Barycenter Problem](https://mlsanity.com/paper/2304.11653/) (2023)

## Abstract (arXiv)

Asynchronous algorithms have attracted much attention recently due to the crucial demands on solving large-scale optimization problems. However, the accelerated versions of asynchronous algorithms are rarely studied. In this paper, we propose the "momentum compensation" technique to accelerate asynchronous algorithms for convex problems. Specifically, we first accelerate the plain Asynchronous Gradient Descent, which achieves a faster O(1/√ε) (v.s. O(1/ε)) convergence rate for non-strongly convex functions, and O(√kappalog(1/ε)) (v.s. O(kappa log(1/ε))) for strongly convex functions to reach an ε- approximate minimizer with the condition number kappa. We further apply the technique to accelerate modern stochastic asynchronous algorithms such as Asynchronous Stochastic Coordinate Descent and Asynchronous Stochastic Gradient Descent. Both of the resultant practical algorithms are faster than existing ones by order. To the best of our knowledge, we are the first to consider accelerated algorithms that allow updating by delayed gradients and are the first to propose truly accelerated asynchronous algorithms. Finally, the experimental results on a shared memory system show that acceleration can lead to significant performance gains on ill-conditioned problems.