# Ordered Momentum for Asynchronous SGD

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 52 references that are in the map.
- First posted on arXiv 27 Jul 2024.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour](https://mlsanity.com/paper/1706.02677/) (2017)
- [TensorFlow: Large-Scale Machine Learning on Heterogeneous Distributed Systems](https://mlsanity.com/paper/1603.04467/) (2016)
- [Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Training](https://mlsanity.com/paper/1712.01887/) (2017)
- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [PowerSGD: Practical Low-Rank Gradient Compression for Distributed Optimization](https://mlsanity.com/paper/1905.13727/) (2019)
- [A Survey on Distributed Machine Learning](https://mlsanity.com/paper/1912.09789/) (2019)
- [On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimization](https://mlsanity.com/paper/1905.03817/) (2019)
- [Asynchronous Decentralized Parallel Stochastic Gradient Descent](https://mlsanity.com/paper/1710.06952/) (2017)
- [SlowMo: Improving Communication-Efficient Distributed SGD with Slow Momentum](https://mlsanity.com/paper/1910.00643/) (2019)
- [Asynchronous Parallel Stochastic Gradient for Nonconvex Optimization](https://mlsanity.com/paper/1506.08272/) (2015)
- [Asynchronous Stochastic Gradient Descent with Delay Compensation](https://mlsanity.com/paper/1609.08326/) (2016)
- [Communication Compression for Decentralized Training](https://mlsanity.com/paper/1803.06443/) (2018)
- [Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learning](https://mlsanity.com/paper/2206.08307/) (2022)
- [Accelerating Federated Learning via Momentum Gradient Descent](https://mlsanity.com/paper/1910.03197/) (2019)
- [1-bit Adam: Communication Efficient Large-Scale Training with Adam's Convergence Speed](https://mlsanity.com/paper/2102.02888/) (2021)
- [Quasi-Global Momentum: Accelerating Decentralized Deep Learning on Heterogeneous Data](https://mlsanity.com/paper/2102.04761/) (2021)
- [Slow and Stale Gradients Can Win the Race: Error-Runtime Trade-offs in Distributed SGD](https://mlsanity.com/paper/1803.01113/) (2018)
- [Asynchronous SGD Beats Minibatch SGD Under Arbitrary Delays](https://mlsanity.com/paper/2206.07638/) (2022)
- [A Tight Convergence Analysis for Stochastic Gradient Descent with Delayed Updates](https://mlsanity.com/paper/1806.10188/) (2018)
- [Staleness-aware Async-SGD for Distributed Deep Learning](https://mlsanity.com/paper/1511.05950/) (2015)
- [DecentLaM: Decentralized Momentum SGD for Large-batch Deep Training](https://mlsanity.com/paper/2104.11981/) (2021)
- [An Asynchronous Mini-Batch Algorithm for Regularized Stochastic Optimization](https://mlsanity.com/paper/1505.04824/) (2015)
- [CSER: Communication-efficient SGD with Error Reset](https://mlsanity.com/paper/2007.13221/) (2020)
- [Critical Parameters for Scalable Distributed Learning with Large Batches and Asynchronous Updates](https://mlsanity.com/paper/2103.02351/) (2021)
- [Distributed Learning Systems with First-order Methods](https://mlsanity.com/paper/2104.05245/) (2021)
- [At Stability's Edge: How to Adjust Hyperparameters to Preserve Minima Selection in Asynchronous Training of Neural Networks?](https://mlsanity.com/paper/1909.12340/) (2019)
- [On the Role of Server Momentum in Federated Learning](https://mlsanity.com/paper/2312.12670/) (2023)
- [Detached Error Feedback for Distributed SGD with Random Sparsification](https://mlsanity.com/paper/2004.05298/) (2020)

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

- [Delayed Momentum Aggregation: Communication-efficient Byzantine-robust Federated Learning with Partial Participation](https://mlsanity.com/paper/2509.02970/) (2025)
- [Optimal Asynchronous Stochastic Nonconvex Optimization under Heavy-Tailed Noise](https://mlsanity.com/paper/2601.19379/) (2026)
- [Aggregation on Learnable Manifolds for Asynchronous Federated Optimization](https://mlsanity.com/paper/2503.14396/) (2025)
- [Bringing Order to Asynchronous SGD: Towards Optimality under Data-Dependent Delays with Momentum](https://mlsanity.com/paper/2605.02043/) (2026)
- [Robustifying Asynchronous SGD via Soft Throttling](https://mlsanity.com/paper/2609.39357/) (2026)

## Abstract (arXiv)

Distributed learning is essential for training large-scale deep models. Asynchronous SGD (ASGD) and its variants are commonly used distributed learning methods, particularly in scenarios where the computing capabilities of workers in the cluster are heterogeneous. Momentum has been acknowledged for its benefits in both optimization and generalization in deep model training. However, existing works have found that naively incorporating momentum into ASGD can impede the convergence. In this paper, we propose a novel method called ordered momentum (OrMo) for ASGD. In OrMo, momentum is incorporated into ASGD by organizing the gradients in order based on their iteration indexes. We theoretically prove the convergence of OrMo with both constant and delay-adaptive learning rates for non-convex problems. To the best of our knowledge, this is the first work to establish the convergence analysis of ASGD with momentum without dependence on the maximum delay. Empirical results demonstrate that OrMo can achieve better convergence performance compared with ASGD and other asynchronous methods with momentum.