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

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.