# Towards Understanding the Generalizability of Delayed Stochastic Gradient Descent

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 44 of its 83 references that are in the map.
- First posted on arXiv 18 Aug 2023.

## Builds on (most cited first, 30 of 44)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Asynchronous Methods for Deep Reinforcement Learning](https://mlsanity.com/paper/1602.01783/) (2016)
- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Visualizing the Loss Landscape of Neural Nets](https://mlsanity.com/paper/1712.09913/) (2017)
- [Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descent](https://mlsanity.com/paper/1902.06720/) (2019)
- [Gradient Descent Provably Optimizes Over-parameterized Neural Networks](https://mlsanity.com/paper/1810.02054/) (2018)
- [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015)
- [Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses](https://mlsanity.com/paper/2006.06914/) (2020)
- [The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learning](https://mlsanity.com/paper/1712.06559/) (2017)
- [Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent](https://mlsanity.com/paper/2006.08157/) (2020)
- [Asynchronous Parallel Stochastic Gradient for Nonconvex Optimization](https://mlsanity.com/paper/1506.08272/) (2015)
- [Stability and Generalization of Learning Algorithms that Converge to Global Optima](https://mlsanity.com/paper/1710.08402/) (2017)
- [Asynchronous Stochastic Gradient Descent with Delay Compensation](https://mlsanity.com/paper/1609.08326/) (2016)
- [High probability generalization bounds for uniformly stable algorithms with nearly optimal rate](https://mlsanity.com/paper/1902.10710/) (2019)
- [Sharper bounds for uniformly stable algorithms](https://mlsanity.com/paper/1910.07833/) (2019)
- [Data-Dependent Stability of Stochastic Gradient Descent](https://mlsanity.com/paper/1703.01678/) (2017)
- [Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpoints](https://mlsanity.com/paper/1707.05947/) (2017)
- [Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learning](https://mlsanity.com/paper/2206.08307/) (2022)
- [Benign Overfitting of Constant-Stepsize SGD for Linear Regression](https://mlsanity.com/paper/2103.12692/) (2021)
- [Perturbed Iterate Analysis for Asynchronous Stochastic Optimization](https://mlsanity.com/paper/1507.06970/) (2015)
- [Asynchronous SGD Beats Minibatch SGD Under Arbitrary Delays](https://mlsanity.com/paper/2206.07638/) (2022)
- [Generalization Bounds for Uniformly Stable Algorithms](https://mlsanity.com/paper/1812.09859/) (2018)
- [A Tight Convergence Analysis for Stochastic Gradient Descent with Delayed Updates](https://mlsanity.com/paper/1806.10188/) (2018)
- [Train simultaneously, generalize better: Stability of gradient-based minimax learners](https://mlsanity.com/paper/2010.12561/) (2020)
- [Staleness-aware Async-SGD for Distributed Deep Learning](https://mlsanity.com/paper/1511.05950/) (2015)
- [Advances in Asynchronous Parallel and Distributed Optimization](https://mlsanity.com/paper/2006.13838/) (2020)
- [Topology-aware Generalization of Decentralized SGD](https://mlsanity.com/paper/2206.12680/) (2022)

## Abstract (arXiv)

Stochastic gradient descent (SGD) performed in an asynchronous manner plays a crucial role in training large-scale machine learning models. However, the generalization performance of asynchronous delayed SGD, which is an essential metric for assessing machine learning algorithms, has rarely been explored. Existing generalization error bounds are rather pessimistic and cannot reveal the correlation between asynchronous delays and generalization. In this paper, we investigate sharper generalization error bound for SGD with asynchronous delay τ. Leveraging the generating function analysis tool, we first establish the average stability of the delayed gradient algorithm. Based on this algorithmic stability, we provide upper bounds on the generalization error of tildeO(fracT-τnτ) and tildeO(frac1n) for quadratic convex and strongly convex problems, respectively, where T refers to the iteration number and n is the amount of training data. Our theoretical results indicate that asynchronous delays reduce the generalization error of the delayed SGD algorithm. Analogous analysis can be generalized to the random delay setting, and the experimental results validate our theoretical findings.