mlsanityData to 14 Oct 2026

Bringing Order to Asynchronous SGD: Towards Optimality under Data-Dependent Delays with Momentum

arXiv 2605.02043 ↗First posted 3 May 2026cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

Asynchronous SGD enables scalable distributed training but suffers from stale gradients. When delays depend on the data, slower samples may be underrepresented, biasing training toward faster samples. We introduce ordered momentum, a unified framework that attains the best-known rates for smooth convex and non-convex objectives under both data-independent and data-dependent delays. Notably, we establish (i) the first convergence guarantee for smooth convex objectives with data-dependent delays and, among analyses of data-dependent delays, the first to (ii) benefit from parallelization and (iii) match the tight data-independent rate, with a leading stochastic term independent of the number of workers. Finally, we derive robust learning rates that simplify hyperparameter tuning across convex and non-convex settings.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 30 of its 44 references that are in the map. First posted on arXiv 3 May 2026.

Builds on

30 of 44 references.

References · 30

  1. 2017Attention Is All You Needcited by 60,361
  2. 2015Deep Residual Learning for Image Recognitioncited by 52,096
  3. 2017Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithmscited by 4,349
  4. 2023A Survey of Large Language Modelscited by 2,576
  5. 2019Momentum-Based Variance Reduction in Non-Convex SGDcited by 306
  6. 2019A Survey on Distributed Machine Learningcited by 188
  7. 2015Asynchronous Parallel Stochastic Gradient for Nonconvex Optimizationcited by 116
  8. 2016Asynchronous Stochastic Gradient Descent with Delay Compensationcited by 99
  9. 2019Grid Search, Random Search, Genetic Algorithm: A Big Comparison for NAScited by 83
  10. 2022Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learningcited by 79
  11. 2015Perturbed Iterate Analysis for Asynchronous Stochastic Optimizationcited by 67
  12. 2022Asynchronous SGD Beats Minibatch SGD Under Arbitrary Delayscited by 63
18 more
  1. 2018A Tight Convergence Analysis for Stochastic Gradient Descent with Delayed Updatescited by 47
  2. 2015An Asynchronous Mini-Batch Algorithm for Regularized Stochastic Optimizationcited by 38
  3. 2021Asynchronous Stochastic Optimization Robust to Arbitrary Delayscited by 32
  4. 2018Improved asynchronous parallel optimization analysis for stochastic incremental methodscited by 30
  5. 2024Dataset Decomposition: Faster LLM Training with Variable Sequence Length Curriculumcited by 26
  6. 2023Optimal Time Complexities of Parallel Stochastic Optimization Methods Under a Fixed Computation Modelcited by 24
  7. 2025Ringmaster ASGD: The First Asynchronous SGD with Optimal Time Complexitycited by 18
  8. 2021Critical Parameters for Scalable Distributed Learning with Large Batches and Asynchronous Updatescited by 17
  9. 2021Asynchronous Iterations in Optimization: New Sequence Results and Sharper Algorithmic Guaranteescited by 17
  10. 2019At Stability's Edge: How to Adjust Hyperparameters to Preserve Minima Selection in Asynchronous Training of Neural Networks?cited by 16
  11. 2019Gap Aware Mitigation of Gradient Stalenesscited by 14
  12. 2022Delay-adaptive step-sizes for asynchronous learningcited by 11
  13. 2019Taming Momentum in a Distributed Asynchronous Environmentcited by 9
  14. 2024Ordered Momentum for Asynchronous SGDcited by 5
  15. 2020Adaptive Braking for Mitigating Gradient Delaycited by 3
  16. 2024Private and Federated Stochastic Convex Optimization: Efficient Strategies for Centralized Systemscited by 3
  17. 2024Faster Stochastic Optimization with Arbitrary Delays via Asynchronous Mini-Batchingcited by 1
  18. 2025Privacy-Preserving Federated Convex Optimization: Balancing Partial-Participation and Efficiency via Noise Cancellationcited by 1

Built on by

Not cited yet.