# Asynchronous Stochastic Optimization Robust to Arbitrary Delays

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

## Key facts

- Cited by 32 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 29 references that are in the map.
- First posted on arXiv 22 Jun 2021.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [Error Feedback Fixes SignSGD and other Gradient Compression Schemes](https://mlsanity.com/paper/1901.09847/) (2019)
- [Is Local SGD Better than Minibatch SGD?](https://mlsanity.com/paper/2002.07839/) (2020)
- [Asynchronous Parallel Stochastic Gradient for Nonconvex Optimization](https://mlsanity.com/paper/1506.08272/) (2015)
- [Perturbed Iterate Analysis for Asynchronous Stochastic Optimization](https://mlsanity.com/paper/1507.06970/) (2015)
- [A Tight Convergence Analysis for Stochastic Gradient Descent with Delayed Updates](https://mlsanity.com/paper/1806.10188/) (2018)
- [An Asynchronous Mini-Batch Algorithm for Regularized Stochastic Optimization](https://mlsanity.com/paper/1505.04824/) (2015)
- [Improved asynchronous parallel optimization analysis for stochastic incremental methods](https://mlsanity.com/paper/1801.03749/) (2018)
- [Asynchronous stochastic convex optimization](https://mlsanity.com/paper/1508.00882/) (2015)
- [On Variance Reduction in Stochastic Gradient Descent and its Asynchronous Variants](https://mlsanity.com/paper/1506.06840/) (2015)
- [A Simple Stochastic Variance Reduced Algorithm with Fast Convergence Rates](https://mlsanity.com/paper/1806.11027/) (2018)

## Built on by (most cited first, 30 of 32)

- [Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learning](https://mlsanity.com/paper/2206.08307/) (2022)
- [Asynchronous SGD Beats Minibatch SGD Under Arbitrary Delays](https://mlsanity.com/paper/2206.07638/) (2022)
- [DoCoFL: Downlink Compression for Cross-Device Federated Learning](https://mlsanity.com/paper/2302.00543/) (2023)
- [Near-Optimal Regret for Adversarial MDP with Delayed Bandit Feedback](https://mlsanity.com/paper/2201.13172/) (2022)
- [Ringmaster ASGD: The First Asynchronous SGD with Optimal Time Complexity](https://mlsanity.com/paper/2501.16168/) (2025)
- [Asynchronous Iterations in Optimization: New Sequence Results and Sharper Algorithmic Guarantees](https://mlsanity.com/paper/2109.04522/) (2021)
- [CO2: Efficient Distributed Training with Full Communication-Computation Overlap](https://mlsanity.com/paper/2401.16265/) (2024)
- [AsGrad: A Sharp Unified Analysis of Asynchronous-SGD Algorithms](https://mlsanity.com/paper/2310.20452/) (2023)
- [A Unified Analysis of Nonstochastic Delayed Feedback for Combinatorial Semi-Bandits, Linear Bandits, and MDPs](https://mlsanity.com/paper/2305.08629/) (2023)
- [Distributed Distributionally Robust Optimization with Non-Convex Objectives](https://mlsanity.com/paper/2210.07588/) (2022)
- [Asynchronous Distributed Bilevel Optimization](https://mlsanity.com/paper/2212.10048/) (2022)
- [Communication-Efficient Large-Scale Distributed Deep Learning: A Comprehensive Survey](https://mlsanity.com/paper/2404.06114/) (2024)
- [Stochastic Approximation with Delayed Updates: Finite-Time Rates under Markovian Sampling](https://mlsanity.com/paper/2402.11800/) (2024)
- [Delay-Adapted Policy Optimization and Improved Regret for Adversarial MDP with Delayed Bandit Feedback](https://mlsanity.com/paper/2305.07911/) (2023)
- [MindFlayer SGD: Efficient Parallel SGD in the Presence of Heterogeneous and Random Worker Compute Times](https://mlsanity.com/paper/2410.04285/) (2024)
- [Ringleader ASGD: The First Asynchronous SGD with Optimal Time Complexity under Data Heterogeneity](https://mlsanity.com/paper/2509.22860/) (2025)
- [Convergence Analysis of Decentralized ASGD](https://mlsanity.com/paper/2309.03754/) (2023)
- [DASA: Delay-Adaptive Multi-Agent Stochastic Approximation](https://mlsanity.com/paper/2403.17247/) (2024)
- [Triadic-OCD: Asynchronous Online Change Detection with Provable Robustness, Optimality, and Convergence](https://mlsanity.com/paper/2405.02372/) (2024)
- [Weight for Robustness: A Comprehensive Approach towards Optimal Fault-Tolerant Asynchronous ML](https://mlsanity.com/paper/2501.09621/) (2025)
- [Optimizing Asynchronous Federated Learning: A Delicate Trade-Off Between Model-Parameter Staleness and Update Frequency](https://mlsanity.com/paper/2502.08206/) (2025)
- [Faster Stochastic Optimization with Arbitrary Delays via Asynchronous Mini-Batching](https://mlsanity.com/paper/2408.07503/) (2024)
- [Orthogonal Calibration for Asynchronous Federated Learning](https://mlsanity.com/paper/2502.15940/) (2025)
- [Partial Parameter Updates for Efficient Distributed Training](https://mlsanity.com/paper/2509.22418/) (2025)
- [Asynchronous Policy Gradient Aggregation for Efficient Distributed Reinforcement Learning](https://mlsanity.com/paper/2509.24305/) (2025)
- [A Class of Accelerated Fixed-Point-Based Methods with Delayed Inexact Oracles and Its Applications](https://mlsanity.com/paper/2512.13547/) (2025)
- [Towards Understanding the Generalizability of Delayed Stochastic Gradient Descent](https://mlsanity.com/paper/2308.09430/) (2023)
- [Multi-Timescale Primal Dual Hybrid Gradient with Application to Distributed Optimization](https://mlsanity.com/paper/2506.15387/) (2025)
- [Do We Need Asynchronous SGD? On the Near-Optimality of Synchronous Methods](https://mlsanity.com/paper/2602.03802/) (2026)
- [Bringing Order to Asynchronous SGD: Towards Optimality under Data-Dependent Delays with Momentum](https://mlsanity.com/paper/2605.02043/) (2026)

## Abstract (arXiv)

We consider stochastic optimization with delayed gradients where, at each time step t, the algorithm makes an update using a stale stochastic gradient from step t - dt for some arbitrary delay dt. This setting abstracts asynchronous distributed optimization where a central server receives gradient updates computed by worker machines. These machines can experience computation and communication loads that might vary significantly over time. In the general non-convex smooth optimization setting, we give a simple and efficient algorithm that requires O( σ2/ε4 + τ/ε2 ) steps for finding an ε-stationary point x, where τ is the average delay smashfrac1Tsumt=1T dt and σ2 is the variance of the stochastic gradients. This improves over previous work, which showed that stochastic gradient decent achieves the same rate but with respect to the maximal delay maxt dt, that can be significantly larger than the average delay especially in heterogeneous distributed systems. Our experiments demonstrate the efficacy and robustness of our algorithm in cases where the delay distribution is skewed or heavy-tailed.