Research map / Optimization / Distributed and compressed
Ordered Momentum for Asynchronous SGD
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes ordered momentum (OrMo), which adds momentum to asynchronous SGD by ordering gradients by iteration index, with convergence proofs independent of maximum delay for constant and delay-adaptive learning rates.
Problem
Momentum naively added to asynchronous SGD (ASGD) can slow convergence or diverge under gradient delays, and prior momentum-ASGD variants lack convergence guarantees; existing ASGD analyses also depend on maximum delay.
Approach
Reformulates synchronous SGD with momentum to show its momentum is a weighted sum of gradient groups ordered by iteration index, then mimics this in ASGD by adding each arriving gradient to the momentum with a weight determined by its iteration group and compensating the parameter update coefficient.
Key results
- On CIFAR10 with 64 homogeneous workers, OrMo reaches 88.03% test accuracy vs 83.14% for ASGD and 86.82% for SMEGA^2 (ResNet20).
- Under heterogeneous setting with 16 workers, naive ASGDm has unstable results (73.23 ± 31.61% test accuracy on CIFAR10) while OrMo achieves 91.01%.
- OrMo can be about 8 times faster than SSGDm in wall-clock time under heterogeneous setting.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use ordered momentum instead of ASGD | ASGD · CIFAR10 and CIFAR100, homogeneous and heterogeneous worker settings | test accuracy | Helped |
| Use ordered momentum instead of SMEGA^2 | Asynchronous training · CIFAR10 and CIFAR100, homogeneous and heterogeneous worker settings | test accuracy | Helped |
| Use naive momentum in ASGD instead of ASGD | ASGD · CIFAR10, heterogeneous worker settings | test accuracy | Hurt |
| Add OrMo's compensated parameter update rule rather than using a vanilla SGD step (ablation) | OrMo · CIFAR10, 16 workers (hom.) | test accuracy: 90.32 ± 0.45 -> 90.95 ± 0.27 | Helped |
| Add OrMo's compensated parameter update rule rather than using a vanilla SGD step (ablation) | OrMo · CIFAR10, 64 workers (hom.) | test accuracy: 86.08 ± 1.33 -> 88.03 ± 0.28 | Helped |
| Add OrMo's compensated parameter update rule rather than using a vanilla SGD step (ablation) | OrMo · CIFAR10, 16 workers (het.) | test accuracy: 90.23 ± 0.32 -> 91.01 ± 0.10 | Helped |
| Add OrMo's compensated parameter update rule rather than using a vanilla SGD step (ablation) | OrMo · CIFAR10, 64 workers (het.) | test accuracy: 86.10 ± 1.71 -> 87.76 ± 0.57 | Helped |
| Use delay-adaptive learning rates in place of a constant learning rate | OrMo · CIFAR10 and CIFAR100 | test accuracy | Mixed |
Surprising findings
- Naive ASGDm with momentum 0.9 frequently fails to converge under heterogeneous workers, while tuning momentum to 0.1-0.6 gives results comparable to ASGD.
Limitations
- Analysis restricted to i.i.d. data across workers; non-i.i.d. setting left to future work.
- Experiments limited to small ResNet models on CIFAR10/CIFAR100 with simulated heterogeneity via 10x slow workers.
Experimental setup
Datasets: CIFAR10 CIFAR100
Benchmarks: CIFAR10 CIFAR100
Metrics: test accuracy training loss wall-clock training time
Baselines: ASGD naive ASGDm shifted momentum SMEGA^2 SSGDm
Builds on: SGD with momentum asynchronous SGD SMEGA^2 shifted momentum delay-adaptive ASGD
Closest papers by meaning
- Ringmaster ASGD: The First Asynchronous SGD with Optimal Time Complexity (ICML 2025 · similarity 0.88)
- Rescaled Asynchronous SGD: Optimal Distributed Optimization under Data and System Heterogeneity (NeurIPS 2026 · similarity 0.88)
- Stability and Generalization of Asynchronous SGD: Sharper Bounds Beyond Lipschitz and Smoothness (NeurIPS 2024 · similarity 0.87)
- Gradient correlation is a key ingredient to accelerate SGD with momentum (ICLR 2025 · similarity 0.87)
- Perfect Parallelization in Mini-Batch SGD with Classical Momentum Acceleration (NeurIPS 2026 · similarity 0.87)
- The Marginal Value of Momentum for Small Learning Rate SGD (ICLR 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.