mlsanityData to 7 Oct 2026

Towards Understanding the Generalizability of Delayed Stochastic Gradient Descent

arXiv 2308.09430 ↗First posted 18 Aug 2023cs.LGcited by 0

Not on the map. Why?

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.

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

Builds on

44 of 83 references.

References · 44

  1. 2015Deep Residual Learning for Image Recognitioncited by 51,809
  2. 2020Language Models are Few-Shot Learnerscited by 32,199
  3. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  4. 2016Asynchronous Methods for Deep Reinforcement Learningcited by 2,218
  5. 2016Understanding deep learning requires rethinking generalizationcited by 1,657
  6. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,140
  7. 2017Visualizing the Loss Landscape of Neural Netscited by 1,126
  8. 2019Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descentcited by 732
  9. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 655
  10. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 547
  11. 2020Stability of Stochastic Gradient Descent on Nonsmooth Convex Lossescited by 172
  12. 2017The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learningcited by 150
32 more
  1. 2020Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descentcited by 118
  2. 2015Asynchronous Parallel Stochastic Gradient for Nonconvex Optimizationcited by 115
  3. 2017Stability and Generalization of Learning Algorithms that Converge to Global Optimacited by 100
  4. 2016Asynchronous Stochastic Gradient Descent with Delay Compensationcited by 98
  5. 2019High probability generalization bounds for uniformly stable algorithms with nearly optimal ratecited by 97
  6. 2019Sharper bounds for uniformly stable algorithmscited by 91
  7. 2017Data-Dependent Stability of Stochastic Gradient Descentcited by 90
  8. 2017Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpointscited by 82
  9. 2022Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learningcited by 76
  10. 2021Benign Overfitting of Constant-Stepsize SGD for Linear Regressioncited by 71
  11. 2015Perturbed Iterate Analysis for Asynchronous Stochastic Optimizationcited by 67
  12. 2022Asynchronous SGD Beats Minibatch SGD Under Arbitrary Delayscited by 61
  13. 2018Generalization Bounds for Uniformly Stable Algorithmscited by 56
  14. 2018A Tight Convergence Analysis for Stochastic Gradient Descent with Delayed Updatescited by 47
  15. 2015Staleness-aware Async-SGD for Distributed Deep Learningcited by 43
  16. 2020Train simultaneously, generalize better: Stability of gradient-based minimax learnerscited by 43
  17. 2020Advances in Asynchronous Parallel and Distributed Optimizationcited by 40
  18. 2022Topology-aware Generalization of Decentralized SGDcited by 37
  19. 2021Stability and Generalization of Stochastic Gradient Methods for Minimax Problemscited by 35
  20. 2021Stability of SGD: Tightness Analysis and Improved Boundscited by 33
  21. 2021Asynchronous Stochastic Optimization Robust to Arbitrary Delayscited by 32
  22. 2022Stability Analysis and Generalization Bounds of Adversarial Trainingcited by 30
  23. 2021Generalization Bounds for Meta-Learning via PAC-Bayes and Uniform Stabilitycited by 29
  24. 2021Stability & Generalisation of Gradient Descent for Shallow Neural Networks without the Neural Tangent Kernelcited by 25
  25. 2020Multi-Agent Online Optimization with Delays: Asynchronicity, Adaptivity, and Optimismcited by 22
  26. 2022Stability and Generalization Analysis of Gradient Methods for Shallow Neural Networkscited by 21
  27. 2021Simple Stochastic and Online Gradient Descent Algorithms for Pairwise Learningcited by 20
  28. 2022What is a Good Metric to Study Generalization of Minimax Learners?cited by 16
  29. 2017Asynchronous Coordinate Descent under More Realistic Assumptionscited by 14
  30. 2022On the generalization of learning algorithms that do not convergecited by 9
  31. 2022Stability Based Generalization Bounds for Exponential Family Langevin Dynamicscited by 8
  32. 2019Distributed SGD Generalizes Well Under Asynchronycited by 4

Built on by

Not cited yet.