# Distributed stochastic optimization with large delays

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 62 references that are in the map.
- First posted on arXiv 6 Jul 2021.

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

- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [How to Escape Saddle Points Efficiently](https://mlsanity.com/paper/1703.00887/) (2017)
- [Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition](https://mlsanity.com/paper/1503.02101/) (2015)
- [Coordinate Descent Algorithms](https://mlsanity.com/paper/1502.04759/) (2015)
- [Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile](https://mlsanity.com/paper/1807.02629/) (2018)
- [Asynchronous Parallel Stochastic Gradient for Nonconvex Optimization](https://mlsanity.com/paper/1506.08272/) (2015)
- [Deep learning with Elastic Averaging SGD](https://mlsanity.com/paper/1412.6651/) (2014)
- [Learning in games with continuous action sets and unknown payoff functions](https://mlsanity.com/paper/1608.07310/) (2016)
- [Perturbed Iterate Analysis for Asynchronous Stochastic Optimization](https://mlsanity.com/paper/1507.06970/) (2015)
- [A Comprehensive Linear Speedup Analysis for Asynchronous Stochastic Parallel Optimization from Zeroth-Order to First-Order](https://mlsanity.com/paper/1606.00498/) (2016)
- [An Asynchronous Mini-Batch Algorithm for Regularized Stochastic Optimization](https://mlsanity.com/paper/1505.04824/) (2015)
- [Accelerated, Parallel and Proximal Coordinate Descent](https://mlsanity.com/paper/1312.5799/) (2013)
- [Gradient Descent Converges to Minimizers](https://mlsanity.com/paper/1602.04915/) (2016)
- [Multi-Agent Online Optimization with Delays: Asynchronicity, Adaptivity, and Optimism](https://mlsanity.com/paper/2012.11579/) (2020)
- [Asynchronous Stochastic Coordinate Descent: Parallelism and Convergence Properties](https://mlsanity.com/paper/1403.3862/) (2014)
- [Asynchronous stochastic convex optimization](https://mlsanity.com/paper/1508.00882/) (2015)
- [GPU Asynchronous Stochastic Gradient Descent to Speed Up Neural Network Training](https://mlsanity.com/paper/1312.6186/) (2013)
- [An Asynchronous Parallel Randomized Kaczmarz Algorithm](https://mlsanity.com/paper/1401.4780/) (2014)
- [Distributed Block Coordinate Descent for Minimizing Partially Separable Functions](https://mlsanity.com/paper/1406.0238/) (2014)
- [Parallel and Distributed Block-Coordinate Frank-Wolfe Algorithms](https://mlsanity.com/paper/1409.6086/) (2014)
- [Revisiting Asynchronous Linear Solvers: Provable Convergence Rate Through Randomization](https://mlsanity.com/paper/1304.6475/) (2013)
- [Analysis of Sparse Cutting-planes for Sparse MILPs with Applications to Stochastic MILPs](https://mlsanity.com/paper/1601.00198/) (2016)

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

- [Non-stationary Delayed Online Convex Optimization: From Full-information to Bandit Setting](https://mlsanity.com/paper/2305.12131/) (2023)
- [Unbiased least squares regression via averaged stochastic gradient descent](https://mlsanity.com/paper/2406.18623/) (2024)
- [Stability and Convergence of Distributed Stochastic Approximations with large Unbounded Stochastic Information Delays](https://mlsanity.com/paper/2305.07091/) (2023)

## Abstract (arXiv)

One of the most widely used methods for solving large-scale stochastic optimization problems is distributed asynchronous stochastic gradient descent (DASGD), a family of algorithms that result from parallelizing stochastic gradient descent on distributed computing architectures (possibly) asychronously. However, a key obstacle in the efficient implementation of DASGD is the issue of delays: when a computing node contributes a gradient update, the global model parameter may have already been updated by other nodes several times over, thereby rendering this gradient information stale. These delays can quickly add up if the computational throughput of a node is saturated, so the convergence of DASGD may be compromised in the presence of large delays. Our first contribution is that, by carefully tuning the algorithm's step-size, convergence to the critical set is still achieved in mean square, even if the delays grow unbounded at a polynomial rate. We also establish finer results in a broad class of structured optimization problems (called variationally coherent), where we show that DASGD converges to a global optimum with probability 1 under the same delay assumptions. Together, these results contribute to the broad landscape of large-scale non-convex stochastic optimization by offering state-of-the-art theoretical guarantees and providing insights for algorithm design.