# A Tight Convergence Analysis for Stochastic Gradient Descent with Delayed Updates

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

## Key facts

- Cited by 47 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Jun 2018.

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

- [Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learning](https://mlsanity.com/paper/2206.08307/) (2022)
- [Fast Federated Learning in the Presence of Arbitrary Device Unavailability](https://mlsanity.com/paper/2106.04159/) (2021)
- [Asynchronous SGD Beats Minibatch SGD Under Arbitrary Delays](https://mlsanity.com/paper/2206.07638/) (2022)
- [SWARM Parallelism: Training Large Models Can Be Surprisingly Communication-Efficient](https://mlsanity.com/paper/2301.11913/) (2023)
- [Moshpit SGD: Communication-Efficient Decentralized Training on Heterogeneous Unreliable Devices](https://mlsanity.com/paper/2103.03239/) (2021)
- [Asynchronous Stochastic Optimization Robust to Arbitrary Delays](https://mlsanity.com/paper/2106.11879/) (2021)
- [DoCoFL: Downlink Compression for Cross-Device Federated Learning](https://mlsanity.com/paper/2302.00543/) (2023)
- [A New Look and Convergence Rate of Federated Multi-Task Learning with Laplacian Regularization](https://mlsanity.com/paper/2102.07148/) (2021)
- [Personalized Federated Learning with Contextualized Generalization](https://mlsanity.com/paper/2106.13044/) (2021)
- [Ringmaster ASGD: The First Asynchronous SGD with Optimal Time Complexity](https://mlsanity.com/paper/2501.16168/) (2025)
- [Critical Parameters for Scalable Distributed Learning with Large Batches and Asynchronous Updates](https://mlsanity.com/paper/2103.02351/) (2021)
- [Asynchronous Iterations in Optimization: New Sequence Results and Sharper Algorithmic Guarantees](https://mlsanity.com/paper/2109.04522/) (2021)
- [Masked Training of Neural Networks with Partial Gradients](https://mlsanity.com/paper/2106.08895/) (2021)
- [Towards Noise-adaptive, Problem-adaptive (Accelerated) Stochastic Gradient Descent](https://mlsanity.com/paper/2110.11442/) (2021)
- [Characterizing & Finding Good Data Orderings for Fast Convergence of Sequential Gradient Methods](https://mlsanity.com/paper/2202.01838/) (2022)
- [AsGrad: A Sharp Unified Analysis of Asynchronous-SGD Algorithms](https://mlsanity.com/paper/2310.20452/) (2023)
- [A Simple Finite-Time Analysis of TD Learning with Linear Function Approximation](https://mlsanity.com/paper/2403.02476/) (2024)
- [Stragglers Are Not Disaster: A Hybrid Federated Learning Algorithm with Delayed Gradients](https://mlsanity.com/paper/2102.06329/) (2021)
- [FedP3: Federated Personalized and Privacy-friendly Network Pruning under Model Heterogeneity](https://mlsanity.com/paper/2404.09816/) (2024)
- [FedLGA: Towards System-Heterogeneity of Federated Learning via Local Gradient Approximation](https://mlsanity.com/paper/2112.11989/) (2021)
- [PRIOR: Personalized Prior for Reactivating the Information Overlooked in Federated Learning](https://mlsanity.com/paper/2310.09183/) (2023)
- [Learning Under Delayed Feedback: Implicitly Adapting to Gradient Delays](https://mlsanity.com/paper/2106.12261/) (2021)
- [Achieving Linear Speedup in Asynchronous Federated Learning with Heterogeneous Clients](https://mlsanity.com/paper/2402.11198/) (2024)
- [Stochastic Approximation with Delayed Updates: Finite-Time Rates under Markovian Sampling](https://mlsanity.com/paper/2402.11800/) (2024)
- [Towards a Better Theoretical Understanding of Independent Subnetwork Training](https://mlsanity.com/paper/2306.16484/) (2023)
- [ACCO: Accumulate While You Communicate for Communication-Overlapped Sharded LLM Training](https://mlsanity.com/paper/2406.02613/) (2024)
- [MindFlayer SGD: Efficient Parallel SGD in the Presence of Heterogeneous and Random Worker Compute Times](https://mlsanity.com/paper/2410.04285/) (2024)
- [PersA-FL: Personalized Asynchronous Federated Learning](https://mlsanity.com/paper/2210.01176/) (2022)
- [Ordered Momentum for Asynchronous SGD](https://mlsanity.com/paper/2407.19234/) (2024)
- [Ringleader ASGD: The First Asynchronous SGD with Optimal Time Complexity under Data Heterogeneity](https://mlsanity.com/paper/2509.22860/) (2025)

## Abstract (arXiv)

We provide tight finite-time convergence bounds for gradient descent and stochastic gradient descent on quadratic functions, when the gradients are delayed and reflect iterates from τ rounds ago. First, we show that without stochastic noise, delays strongly affect the attainable optimization error: In fact, the error can be as bad as non-delayed gradient descent ran on only 1/τ of the gradients. In sharp contrast, we quantify how stochastic noise makes the effect of delays negligible, improving on previous work which only showed this phenomenon asymptotically or for much smaller delays. Also, in the context of distributed optimization, the results indicate that the performance of gradient descent with delays is competitive with synchronous approaches such as mini-batching. Our results are based on a novel technique for analyzing convergence of optimization algorithms using generating functions.