Bringing Order to Asynchronous SGD: Towards Optimality under Data-Dependent Delays with Momentum
Tehila Dahan ∗, Roie Reshef ∗, Sharon Goldstein, Kfir Y. Levy · 2026
Read Bringing Order to Asynchronous SGD: Towards Optimality under Data-Dependent Delays with Momentum by Tehila Dahan ∗, Roie Reshef ∗, Sharon Goldstein, Kfir Y. Levy (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-02043.txt.
Introduction
Tehila Dahan, Roie Reshef, Sharon Goldstein, and Kfir Levy study asynchronous stochastic gradient descent, where workers send gradients with delays. Stale gradients slow training, and when delay depends on the data, slow samples can be underrepresented and bias the result. The authors introduce ordered momentum as a unified fix.
Their method reaches the best known rates for smooth convex and non-convex goals under both data-linked and data-free delays. They give the first guarantee for smooth convex goals with data-linked delays. Their analysis also gains from parallel work and matches the tight rate for the simpler delay case, with a leading term that does not grow with worker count. Robust learning rates ease tuning across settings.
Catalog record
| CREATOR | Tehila Dahan ∗, Roie Reshef ∗, Sharon Goldstein, Kfir Y. Levy |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 92 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.02043
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Bringing Order to Asynchronous SGD: Towards Optimality under Data-Dependent Delays with Momentum Tehila Dahan ∗, Roie Reshef ∗, Sharon Goldstein, Kfir Y. Levy Abstract Asynchronous stochastic gradient descent (SGD) enables scalable distributed training but suffers from gradient staleness. Existing mitigation strategies, such as delay-adaptive learning rates and staleness-aware filtering, typically attenuate or discard delayed gradients, introducing systematic bias: updates from simpler or faster-to-process samples are overrepresented, while gradients from more complex samples are delayed or suppressed. In contrast, prior approaches to data-dependent delays rely on a Lipschitz assumption that yields suboptimal rates or leave the smooth, convex case unaddressed. We propose a momentum-based asynchronous framework designed to preserve information from delayed gradients while mitigating the effects of staleness. We establish the first optimal convergence rates for data-dependent delays in both convex and non-convex smooth setups, providing a new result for asynchronous optimization under standard assumptions. Additionally, we derive robust learning-rate schedules that simplify hyperparameter tuning in practice. † † footnotetext: ∗ Equal contribution. 1 Introduction The rapid growth of dataset sizes and model complexity has made distributed training indispensable in modern machine learning ( 42 ; 45 ) . Among existing scaling strategies, asynchronous parallelization is particularly appealing, as it reduces synchronization overhead and improves resource utilization ( 28 ) . In this setting, multiple workers independently compute gradients on different mini-batches and update shared model parameters without requiring global synchronization. This design offers several advantages, including reduced communication costs, elimination of idle time caused by stragglers, and efficient utilization of heterogeneous hardware. In contrast to synchronous methods, which require all workers to wait for the slowest one before proceeding to the next update ( 10 ) , asynchronous SGD enables continuous updates, yielding higher throughput in wall-clock time and making it well-suited for scalable learning. These advantages, however, come at a fundamental cost: updates may be delayed and thus stale. Specifically, by the time a worker applies its computed gradient, the global model may have already evolved, resulting in a discrepancy commonly referred to as staleness . Tight analyses of arbitrary delays typically rely on the assumption that staleness is independent of the data ( 6 ; 3 ; 4 ; 28 ; 19 ; 35 ) . In modern training procedures, delays are inherently data-dependent; the computation time of a mini-batch often scales with the input complexity. For instance, in language modeling, to maximize hardware efficiency, sequences are often bucketed by length ( 14 ; 31 ) , causing batches with longer, more complex sequences to experience significantly higher staleness due to the superlinear scaling of self-attention ( 40 ) . An analogous phenomenon arises in video understanding, where longer clips impose heavier computational loads. This coupling between the data distribution and delay biases the optimization process toward easy examples, leading to instability, slower convergence, and degraded generalization. To mitigate this effect, recent data-dependent analyses scale the learning rate with the number of workers M ( 28 ; 19 ; 35 ) . However, these results remain suboptimal for general L -smooth objectives. Specifically, in non-convex settings, they rely on a G -Lipschitz (bounded gradient) assumption that introduces an additional suboptimal term in the convergence rate. Furthermore, in the smooth-convex setting, a result on data-dependent delays is currently absent from the literature. More specifically, in the non-convex setting, existing data-dependent analyses ( 28 ) yield the rate \displaystyle\mathcal{O}\left(\frac{L\Delta M}{T}+\frac{\sigma\sqrt{L\Delta}}{\sqrt{T}}+\left(\frac{GL\Delta M}{T}\right)^{2/3}\right) (1) where \Delta denotes the optimality gap and \sigma denoting the stochastic error. This rate contains an additional \mathcal{O}\left(\left(\frac{GL\Delta M}{T}\right)^{2/3}\right) term that is suboptimal and arises from the bounded-gradient assumption. In the convex case, existing data-dependent analyses ( 28 ) yield the rate \displaystyle\mathcal{O}\left(\frac{GD\sqrt{M}}{\sqrt{T}}\right) (2) where D bounds the distance between two feasible points. This result is limited by its reliance on a G -Lipschitz assumption and does not leverage the objective’s smoothness. Under standard smoothness assumptions, the well-known data- in dependent rate is \mathcal{O}\left(\frac{LD^{2}M}{T}+\frac{\sigma D}{\sqrt{T}}\right) . A critical discrepancy emerges here: in the smooth case, the dominant \mathcal{O}\left(\frac{1}{\sqrt{T}}\right) term is independent of the number of workers M , whereas the existing data-dependent rate incurs a \sqrt{M} penalty. Unfortunately, a result that recovers this M -independent dominant term while accounting for data-dependent delays is currently absent from the literature. From the standpoint of parallelization , these bounds fail to capture the acceleration potential of using many workers. In the non-convex setting, the rate remains disproportionately large relative to the stochastic noise, stifling the attainable speedup (see Remark 4.2 ). The discrepancy is even more severe in the convex case, where the \sqrt{M} factor is on the dominant, slow \mathcal{O}\left(\frac{1}{\sqrt{T}}\right) term. Closing these gaps in a fully data-dependent and smooth setting remains an open challenge that we address in this work. Under data- in dependent assumptions, several existing approaches mitigate the effect of delays by filtering updates based on their staleness. In particular, some methods adjust the learning rate as a function of the observed delay ( 28 ; 19 ; 35 ; 41 ; 5 ; 43 ) , while others employ delay-based filtering thresholds that directly discard excessively stale updates ( 6 ; 3 ; 27 ) . These techniques downweight delayed gradients and thereby reinforce the bias toward samples that are processed quickly. Moreover, these methods introduce additional hyperparameters that may be difficult to tune. For example, 28 ; 19 ; 35 show that for smooth objectives without Lipschitz continuity, the optimal learning rate is \displaystyle\eta_{t}=\min\left\{\Theta\left(\frac{1}{L\tau_{t}}\right),\Theta\left(\frac{1}{LM}\right),\Theta\left(\sqrt{\frac{\Delta}{L\sigma^{2}T}}\right)\right\} (3) which depends on the smoothness constant L , the current delay \tau_{t} , the optimality gap \Delta , and the stochastic error \sigma . Since most of these quantities are generally unknown in practice, it is less practical to evaluate \eta_{t} at each iteration. In contrast to a fixed learning rate, which can be tuned once using simple and standard strategies such as a grid search ( 24 ) , these adaptive schedules require continual approximation, making asynchronous training more delicate and tuning-intensive. Our Contributions In this work, we propose a momentum-based framework that resolves the suboptimality induced by data-dependent delays in asynchronous learning. Our main contributions are: • We provide the first optimal convergence rates for asynchronous learning under data-dependent delays in both convex and non-convex smooth settings: 1. In the smooth non-convex case, prior data-dependent work additionally assumed that the gradients are G -bounded, and the rate is suboptimal by having an additional \mathcal{O}\left(\left(\frac{GL\Delta M}{T}\right)^{2/3}\right) term, implying degraded parallelization compared to the optimal (data-independent) bound. 2. In the convex case, optimal results for the smooth case are non-existent. But under a G -bounded gradient assumption, the rate is \mathcal{O}\left(\frac{G\sqrt{M}}{\sqrt{T}}\right) . Unfortunately, the leading term in this bound degrades as the number of machines M increases, implying degraded performance upon parallelization. Conversely, our new results for the smooth data-dependent case analysis imply that the leading term does not depend on M , a nontrivial benefit of parallelization (as is common in smooth-case analysis). • Our guarantees hold with a fixed learning rate that can be optimized once via standard offline procedures, such as a single grid search. In contrast, existing delay-adaptive methods require per-iteration step sizes of the form \eta_{t}=\min\left\{\Theta\left(\frac{1}{L\tau_{t}}\right),\Theta\left(\frac{1}{LM}\right),\Theta\left(\sqrt{\frac{\Delta}{L\sigma^{2}T}}\right)\right\} . Because this schedule depends on unobservable quantities, it must be re-evaluated at every iteration rather than tuned