# Critical Parameters for Scalable Distributed Learning with Large Batches and Asynchronous Updates

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

## Key facts

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

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

- [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)
- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour](https://mlsanity.com/paper/1706.02677/) (2017)
- [On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima](https://mlsanity.com/paper/1609.04836/) (2016)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [The Convergence of Sparsified Gradient Methods](https://mlsanity.com/paper/1809.10505/) (2018)
- [Measuring the Effects of Data Parallelism on Neural Network Training](https://mlsanity.com/paper/1811.03600/) (2018)
- [The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learning](https://mlsanity.com/paper/1712.06559/) (2017)
- [QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding](https://mlsanity.com/paper/1610.02132/) (2016)
- [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)
- [The Impact of Neural Network Overparameterization on Gradient Confusion and Stochastic Gradient Descent](https://mlsanity.com/paper/1904.06963/) (2019)
- [Taming the Wild: A Unified Analysis of Hogwild!-Style Algorithms](https://mlsanity.com/paper/1506.06438/) (2015)
- [Improved asynchronous parallel optimization analysis for stochastic incremental methods](https://mlsanity.com/paper/1801.03749/) (2018)
- [New Convergence Aspects of Stochastic Gradient Algorithms](https://mlsanity.com/paper/1811.12403/) (2018)
- [Asynchronous stochastic convex optimization](https://mlsanity.com/paper/1508.00882/) (2015)
- [On Unbounded Delays in Asynchronous Parallel Fixed-Point Algorithms](https://mlsanity.com/paper/1609.04746/) (2016)
- [On the linear convergence of the stochastic gradient method with constant step-size](https://mlsanity.com/paper/1712.01906/) (2017)
- [The Effect of Network Width on the Performance of Large-batch Training](https://mlsanity.com/paper/1806.03791/) (2018)
- [Sparsification as a Remedy for Staleness in Distributed Asynchronous SGD](https://mlsanity.com/paper/1910.09466/) (2019)
- [Understanding the Effects of Data Parallelism and Sparsity on Neural Network Training](https://mlsanity.com/paper/2003.11316/) (2020)

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

- [Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learning](https://mlsanity.com/paper/2206.08307/) (2022)
- [Analyzing & Reducing the Need for Learning Rate Warmup in GPT Training](https://mlsanity.com/paper/2410.23922/) (2024)
- [A General Theory for Federated Optimization with Asynchronous and Heterogeneous Clients Updates](https://mlsanity.com/paper/2206.10189/) (2022)
- [Masked Training of Neural Networks with Partial Gradients](https://mlsanity.com/paper/2106.08895/) (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)
- [Asynchronous Federated Learning with Bidirectional Quantized Communications and Buffered Aggregation](https://mlsanity.com/paper/2308.00263/) (2023)
- [FADAS: Towards Federated Adaptive Asynchronous Optimization](https://mlsanity.com/paper/2407.18365/) (2024)
- [Layered gradient accumulation and modular pipeline parallelism: fast and efficient training of large language models](https://mlsanity.com/paper/2106.02679/) (2021)
- [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)
- [Asynchronous Heterogeneous Linear Quadratic Regulator Design](https://mlsanity.com/paper/2404.09061/) (2024)
- [Asynchronous Federated Stochastic Optimization for Heterogeneous Objectives Under Arbitrary Delays](https://mlsanity.com/paper/2405.10123/) (2024)
- [Client Selection in Federated Learning with Data Heterogeneity and Network Latencies](https://mlsanity.com/paper/2504.01921/) (2025)
- [Accelerating Perturbed Stochastic Iterates in Asynchronous Lock-Free Optimization](https://mlsanity.com/paper/2109.15292/) (2021)
- [Stragglers Can Contribute More: Uncertainty-Aware Distillation for Asynchronous Federated Learning](https://mlsanity.com/paper/2511.19966/) (2025)
- [Bringing Order to Asynchronous SGD: Towards Optimality under Data-Dependent Delays with Momentum](https://mlsanity.com/paper/2605.02043/) (2026)

## Abstract (arXiv)

It has been experimentally observed that the efficiency of distributed training with stochastic gradient (SGD) depends decisively on the batch size and -- in asynchronous implementations -- on the gradient staleness. Especially, it has been observed that the speedup saturates beyond a certain batch size and/or when the delays grow too large. We identify a data-dependent parameter that explains the speedup saturation in both these settings. Our comprehensive theoretical analysis, for strongly convex, convex and non-convex settings, unifies and generalized prior work directions that often focused on only one of these two aspects. In particular, our approach allows us to derive improved speedup results under frequently considered sparsity assumptions. Our insights give rise to theoretically based guidelines on how the learning rates can be adjusted in practice. We show that our results are tight and illustrate key findings in numerical experiments.