# Slow and Stale Gradients Can Win the Race: Error-Runtime Trade-offs in Distributed SGD

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

## Key facts

- Cited by 68 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Mar 2018.

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

- [A Field Guide to Federated Optimization](https://mlsanity.com/paper/2107.06917/) (2021)
- [Federated Learning with Buffered Asynchronous Aggregation](https://mlsanity.com/paper/2106.06639/) (2021)
- [Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradients](https://mlsanity.com/paper/2102.07053/) (2021)
- [Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learning](https://mlsanity.com/paper/2206.08307/) (2022)
- [Towards Crowdsourced Training of Large Neural Networks using Decentralized Mixture-of-Experts](https://mlsanity.com/paper/2002.04013/) (2020)
- [Compute-Efficient Deep Learning: Algorithmic Trends and Opportunities](https://mlsanity.com/paper/2210.06640/) (2022)
- [SpreadGNN: Serverless Multi-task Federated Learning for Graph Neural Networks](https://mlsanity.com/paper/2106.02743/) (2021)
- [FLUTE: A Scalable, Extensible Framework for High-Performance Federated Learning Simulations](https://mlsanity.com/paper/2203.13789/) (2022)
- [Trade-offs of Local SGD at Scale: An Empirical Study](https://mlsanity.com/paper/2110.08133/) (2021)
- [AsyncFedED: Asynchronous Federated Learning with Euclidean Distance based Adaptive Weight Aggregation](https://mlsanity.com/paper/2205.13797/) (2022)
- [Gradient Descent with Linearly Correlated Noise: Theory and Applications to Differential Privacy](https://mlsanity.com/paper/2302.01463/) (2023)
- [Ringmaster ASGD: The First Asynchronous SGD with Optimal Time Complexity](https://mlsanity.com/paper/2501.16168/) (2025)
- [CO2: Efficient Distributed Training with Full Communication-Computation Overlap](https://mlsanity.com/paper/2401.16265/) (2024)
- [The Evolution of Distributed Systems for Graph Neural Networks and their Origin in Graph Processing and Deep Learning: A Survey](https://mlsanity.com/paper/2305.13854/) (2023)
- [Asynchronous Decentralized Learning over Unreliable Wireless Networks](https://mlsanity.com/paper/2202.00955/) (2022)
- [Taming Resource Heterogeneity In Distributed ML Training With Dynamic Batching](https://mlsanity.com/paper/2305.12213/) (2023)
- [DIGEST: Fast and Communication Efficient Decentralized Learning with Local Updates](https://mlsanity.com/paper/2307.07652/) (2023)
- [Secure and Efficient Federated Learning Through Layering and Sharding Blockchain](https://mlsanity.com/paper/2104.13130/) (2021)
- [Towards Efficient and Stable K-Asynchronous Federated Learning with Unbounded Stale Gradients on Non-IID Data](https://mlsanity.com/paper/2203.01214/) (2022)
- [Gradient Coding with Dynamic Clustering for Straggler-Tolerant Distributed Learning](https://mlsanity.com/paper/2103.01206/) (2021)
- [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)
- [MindFlayer SGD: Efficient Parallel SGD in the Presence of Heterogeneous and Random Worker Compute Times](https://mlsanity.com/paper/2410.04285/) (2024)
- [The Gradient Convergence Bound of Federated Multi-Agent Reinforcement Learning with Efficient Communication](https://mlsanity.com/paper/2103.13026/) (2021)
- [Freya PAGE: First Optimal Time Complexity for Large-Scale Nonconvex Finite-Sum Optimization with Heterogeneous Asynchronous Computations](https://mlsanity.com/paper/2405.15545/) (2024)
- [Ordered Momentum for Asynchronous SGD](https://mlsanity.com/paper/2407.19234/) (2024)
- [ATA: Adaptive Task Allocation for Efficient Resource Management in Distributed Machine Learning](https://mlsanity.com/paper/2502.00775/) (2025)
- [Ringleader ASGD: The First Asynchronous SGD with Optimal Time Complexity under Data Heterogeneity](https://mlsanity.com/paper/2509.22860/) (2025)
- [Accelerating Neural Network Training with Distributed Asynchronous and Selective Optimization (DASO)](https://mlsanity.com/paper/2104.05588/) (2021)

## Abstract (arXiv)

Distributed Stochastic Gradient Descent (SGD) when run in a synchronous manner, suffers from delays in waiting for the slowest learners (stragglers). Asynchronous methods can alleviate stragglers, but cause gradient staleness that can adversely affect convergence. In this work we present a novel theoretical characterization of the speed-up offered by asynchronous methods by analyzing the trade-off between the error in the trained model and the actual training runtime (wallclock time). The novelty in our work is that our runtime analysis considers random straggler delays, which helps us design and compare distributed SGD algorithms that strike a balance between stragglers and staleness. We also present a new convergence analysis of asynchronous SGD variants without bounded or exponential delay assumptions, and a novel learning rate schedule to compensate for gradient staleness.