# Asynchronous Distributed Optimization with Stochastic Delays

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Sep 2020.

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

- [Stragglers Are Not Disaster: A Hybrid Federated Learning Algorithm with Delayed Gradients](https://mlsanity.com/paper/2102.06329/) (2021)
- [FedLGA: Towards System-Heterogeneity of Federated Learning via Local Gradient Approximation](https://mlsanity.com/paper/2112.11989/) (2021)

## Abstract (arXiv)

We study asynchronous finite sum minimization in a distributed-data setting with a central parameter server. While asynchrony is well understood in parallel settings where the data is accessible by all machines -- e.g., modifications of variance-reduced gradient algorithms like SAGA work well -- little is known for the distributed-data setting. We develop an algorithm ADSAGA based on SAGA for the distributed-data setting, in which the data is partitioned between many machines. We show that with m machines, under a natural stochastic delay model with an mean delay of m, ADSAGA converges in tildeOleft(left(n + √mkapparight)log(1/ε)right) iterations, where n is the number of component functions, and kappa is a condition number. This complexity sits squarely between the complexity tildeOleft(left(n + kapparight)log(1/ε)right) of SAGA textitwithout delays and the complexity tildeOleft(left(n + mkapparight)log(1/ε)right) of parallel asynchronous algorithms where the delays are textitarbitrary (but bounded by O(m)), and the data is accessible by all. Existing asynchronous algorithms with distributed-data setting and arbitrary delays have only been shown to converge in tildeO(n2kappalog(1/ε)) iterations. We empirically compare on least-squares problems the iteration complexity and wallclock performance of ADSAGA to existing parallel and distributed algorithms, including synchronous minibatch algorithms. Our results demonstrate the wallclock advantage of variance-reduced asynchronous approaches over SGD or synchronous approaches.