acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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.

Primary area:
optimization
Keywords:
asynchronous stochastic gradient descent, stochastic optimization, distributed learning

Reviews

Among:
Shape:
1234this paper, Top 32%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.50 over 4 reviews, above 68% of the others.
Reviewer_PioXOpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies asynchronous SGD, an variation of SGD in which stochastic gradients have delay. The authors focus on a setting where delays may be sample/data-dependent, making the analysis and convergence harder. Vanilla Asynchronous SGD is modified using first momentum and yielding a perturbed iterate analysis, while a second momentum is then added to obtain better rates.

Critical strengths
  • The setup is very interesting: delays should indeed depend on samples. There are harder and easier ones, for instance if samples are generated using simulations (in RL applications for instance): easy ones will be always faster. It is also a difficult problem.
  • The paper is very easy to follow: assumptions and theorems are clearly marked and assessing the contributions is facilitated.
  • Although the analysis was not checked by the reviewer, it seems that the analysis extends the perturbed iterates analysis of Mishchenko et al. 2022 to momentum: the difference between the virtual sequence (without delays) and the one with delay can be written similarly. Momentum enables to not have to use delay-dependent online stepsizes.
  • The double-momentum algorithm obtains better rates than all previous works in the data-dependent delays setting.
Critical weaknesses

There are no major weaknesses, since the setup is clearly motivated and formalized. However, my main concern is that it seems that delay-dependency is only handled by assuming bounded gradients. This assumption is strong, and in the results it means that dependence is made worst-case. One would wonder if there could be an in-between, since here the result is robust to adversarial dependence. Since the dependence is not adversarial (in most settings), different assumptions than bounded gradients (Markovian dependency ? etc) could be used and their impact could be quantified.

Questions for authors

Could the authors comment on the above comment on the bounded gradient assumption?

2 comments

Thank you for the thoughtful review. Your RL example captures the motivation for our work well, and we're glad to read that you appreciated both the fixed-step momentum results and the improved rates from double momentum.

Regarding intermediate forms of data-delay dependence, we thank the reviewer for raising this great question. We believe that sharper guarantees are achievable under suitable assumptions on the interaction between samples and delays. Exploring this requires characterizing how the interaction between samples and delays affects the pending-gradient contributions, then incorporating that structure into our analysis of the discrepancy btb_t from ideal momentum (Lemmas B.5 and C.6). An interesting point is that our framework already handles both endpoints: it achieves tight data-independent rates and the best-known data-dependent guarantees under their respective assumptions. This suggests that the same approach may also yield refined guarantees for intermediate regimes. Establishing how the rates improve under more favorable dependence, and whether these rates are optimal, is indeed an interesting direction for future work.

I thank the authors for their answers, and maintain my score.

Reviewer_TM17OpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes ordered momentum for asynchronous SGD, weighting gradients according to when their computation started so that their coefficients match those in an ideal momentum sum without delays. The only missing terms correspond to gradients that have not yet arrived, and their number is bounded by the number of workers MM. The paper gives convergence guarantees for both data-independent and data-dependent delays.

Critical strengths

The ordered-momentum construction is intuitive. It recovers the best-known nonconvex rates with a constant stepsize for both data-independent and data-dependent delays, under the assumptions stated for each case. In the data-independent setting, it offers an alternative to methods that use delay-adaptive stepsizes or filter overly stale gradients.

Critical weaknesses

1. The claims about handling data-dependent delays need stronger qualification.

The data-dependent guarantees require uniformly bounded stochastic gradients, whereas the corresponding independent-delay guarantees assume only bounded variance. This is a substantial restriction and is used directly to control the contribution of pending gradients. Although the method uses a common algorithmic framework, removing delay independence comes with a considerably stronger assumption. Given the emphasis on data-dependent delays in the title and framing, the paper should explain more clearly what the momentum construction adds beyond what the bounded-gradient assumption already enables.

Ordinary ASGD already handles data-dependent delays with a constant stepsize under bounded stochastic gradients (Mishchenko et al., 2022, Theorem 2). Compared with that result, Theorem 3.2 replaces LΔM/TL\Delta M/T with LΔ/TL\Delta/T, but leaves the stochastic and delay-dependent terms unchanged. This is an improvement, but it does not improve the dominant rate under the bounded-gradient assumption.

The convex result also requires bounded stochastic gradients and additionally assumes that every sample loss is smooth. The cited general convex baseline already assumes bounded gradients but does not require samplewise smoothness (Mishchenko et al., 2022, Theorem 1). The improved guarantee is therefore obtained under stronger conditions, and the comparison does not isolate how much of the improvement comes specifically from ordering.

Remark 4.5 also claims optimal time complexity under general data-dependent delays, but the paper does not derive an explicit time-complexity bound or show that it matches an applicable lower bound. The claimed connection to the framework of Tyurin and Richtárik (2023) needs to be justified; an iteration-complexity guarantee alone does not establish optimal time complexity.

2. The practical motivation for the assumed data-dependent delays is not convincing.

The paper motivates data-dependent delays through variable-length text and video, but it is unclear why independently sampling examples with different computation costs is the right training setup.

In the cited work of Pouransari et al. (2024), sequences are grouped into buckets by length. At each optimization step, one bucket is selected, and all GPUs draw their respective batches from that same bucket, adjusting batch size to maintain a fixed token budget. On comparable devices, this gives similar computation times across GPUs within each step. Long-sequence steps may take longer than short-sequence steps, but this does not create the competition between different sequence lengths that motivates the present paper.

Videos could similarly be grouped by duration and resolution. It is therefore unclear why each GPU should independently select examples with different computation costs instead of coordinating bucket selection. I would expect the coordinated approach to reduce workload imbalance. The authors should compare these two approaches while preserving the intended data mixture and measuring the time needed to reach a given accuracy.

When devices also differ in speed, another option is to assign buckets to workers or worker groups according to their computation costs. Each worker would repeatedly sample from a relatively uniform workload, while different workers would have different local data distributions and different computation times. This makes asynchronous methods for heterogeneous data, such as FedBuff (Nguyen et al., AISTATS 2022) and Ringleader ASGD (Maranjyan and Richtárik, ICLR 2026), relevant alternatives to investigate.

The current toy experiments with artificially assigned delays do not establish when the proposed setup offers an advantage over these alternatives on a real workload.

Questions for authors

see Weaknesses.

2 comments

Thank you for your valuable feedback. We wish to address some points raised to provide further clarification and insight into our work:

  • Regarding the gradient assumptions. We thank the reviewer for raising this important question. A bounded-variance assumption applies under fresh sampling, whereas data-dependent delays can change the distribution of gradients that remain pending. For example, rare samples with large gradients may have longer computation times and become overrepresented among pending gradients, even when the original variance is bounded. Our analysis uses Assumption 2.4 to control every pending gradient, regardless of how its delay depends on the sample. Ordered momentum makes the discrepancy from ideal momentum consist of at most M−1M-1 pending contributions; the uniform bound then controls their size (Lemma B.5, Equations (6-8)). Furthermore, our Theorem 3.2 matches the best-known nonconvex rate under the same assumptions as Mishchenko et al. [1, Theorem 2]. For smooth convex objectives, ordered double momentum further exploits smoothness to obtain an MM-independent leading stochastic term (Theorem 4.2), improving on the previous O(DGM/T)O(DG\sqrt{M/T}) guarantee under bounded gradients [1]. This improvement demonstrates what the construction adds beyond controlling gradient magnitudes.

  • Regarding the comparison with ordinary ASGD. We agree that Theorem 3.2 improves the faster-decaying deterministic term from O(LΔM/T)O(L\Delta M/T) to O(LΔ/T)O(L\Delta/T), while leaving the stochastic and delay-dependent terms unchanged. However, our main contributions compared to ASGD extend beyond this refinement:

(i) First convex guarantees under data-dependent delays to exploit smoothness and match tight data-independent scaling. Theorem 4.2 provides the first guarantee in this setting whose leading stochastic term is independent of the number of workers. Worker dependence appears only in a lower-order term, matching the tight data-independent scaling in iterations and workers (Remark 4.3).

(ii) One unified method with a fixed learning rate for both data-independent and data-dependent delays. In the ASGD analysis of Mishchenko et al. (2022), the data-dependent guarantee uses a constant stepsize, whereas the ASGD tight data-independent guarantee uses a delay-adaptive stepsize (Remark 3.3 and Equation (9)). Our framework achieves the tight data-independent rate and the best-known data-dependent rate with a fixed, delay-independent learning rate in both cases. Each run uses a single learning rate selected before training and retained throughout, permitting standard offline tuning without calibrating a delay-adaptive schedule (Theorems 3.1-3.2; Remarks 3.3–3.4).

(iii) Provable robustness to the choice of learning rate. For convex objectives, we establish the stated convergence guarantees across a broad range of learning rates in both delay regimes (Theorems 4.1-4.2, Remark 4.4).

  • Regarding samplewise smoothness. Thank you for raising this point. Smoothness of each stochastic loss is a standard assumption in stochastic optimization, and our result shows what becomes achievable when this structure is exploited. Our contribution is therefore the first demonstration that tight data-independent scaling in iterations and workers is attainable under data-dependent delays with this natural additional smoothness assumption. Theorem 4.2 gives an MM-independent leading stochastic term, with worker dependence confined to a lower-order term (Remark 4.3).

  • Regarding the time complexity. A standard setup in prior optimal time-complexity work [2,3] is the fixed computation model. In this model, worker ii takes cic_i seconds to compute each stochastic gradient. These times may differ across workers but remain fixed throughout training. Workers operate continuously and asynchronously, and the server updates the model whenever a gradient arrives. Appendix L of [2], Equations (49-50), converts ASGD's iteration-complexity bound into a time bound by counting completed gradients: by time tt, workers produce ∑i=1M⌊t/ci⌋\sum_{i=1}^{M}\lfloor t/c_i\rfloor gradients. Algorithm 3 and Theorem 2.1 of [2] then select the appropriate fastest-worker subset, yielding

\min_{1\le m\le M} \frac{mL\Delta/\epsilon+\sigma^2L\Delta/\epsilon^2} {\sum_{i=1}^{m}c_i^{-1}} \right),$$ which matches the lower bound in [2, Theorem 6.4]. Our Theorem 3.1 matches the iteration complexity used in this reduction, so the same conversion and subset-selection argument recovers this optimal time bound for our method. Therefore, our analysis of data-dependent delays provides a basis for future advances toward optimal time complexity when delay also depends on the sampled data.
  • Regarding the paper motivation. Thank you for raising this important point. Coordinated bucketing can indeed reduce workload imbalance when computation costs are predictable from input size. However, computation costs may be unknown in advance and become apparent only during execution. For example, in GRPO-based reasoning [4], the same prompt can produce reasoning rollouts of different lengths, so generation costs cannot be determined from prompt length alone. Such variability makes it difficult to construct computationally uniform buckets in advance, and assigning fixed buckets to workers can still leave sample-dependent delays within each worker's workload. Our framework complements these scheduling strategies by providing convergence guarantees when asynchronous arrival times remain correlated with the sampled data, without requiring a prior partition by computation cost. We have expanded the motivation and discussion of related work to explain this distinction more clearly.

  • Regarding the empirical scope and scaling evidence. We thank the reviewer for this comment. Following your feedback, we added CIFAR-10 experiments with ResNet-18 and M∈5,7,9M\in{5,7,9} workers, covering data-independent delays and three levels of data dependence (q1∈0.1,0.3,0.5q_1\in{0.1,0.3,0.5}). Ordered μ2\mu^2-SGD achieves the highest peak accuracy across all tested configurations, while the ordered methods remain effective over a broader learning-rate range than their unordered counterparts (please see Section 5 and Appendix D.6). These experiments directly support our central theoretical claims: ordered updates improve optimization and learning-rate robustness across data-dependence levels, worker counts, and delay settings.


[1] Mishchenko, K., Bach, F., Even, M., and Woodworth, B. Asynchronous SGD Beats Minibatch SGD Under Arbitrary Delays. NeurIPS, 2022.

[2] Tyurin, A., and Richtárik, P. Optimal Time Complexities of Parallel Stochastic Optimization Methods Under a Fixed Computation Model. NeurIPS, 2023.

[3] Maranjyan, A., Tyurin, A., and Richtárik, P. Ringmaster ASGD: The First Asynchronous SGD with Optimal Time Complexity. ICML, 2025.

[4] Guo, D., et al. DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning. arXiv:2501.12948, 2025.

Reviewer_TaoUOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies asynchronous SGD when delays depend on sample characteristics, potentially causing slower examples to be underrepresented. It proposes ordered momentum, which weights arriving delayed gradients according to their original time indices. The framework is combined with STORM-style variance reduction and an Anytime-SGD-type averaging scheme to derive convergence guarantees for smooth convex and non-convex objectives under data-independent and data-dependent delays.

Critical strengths

(1) theoretical formulation. Data-dependent delays can induce implicit sample reweighting. A smooth-convex guarantee with an MM-independent leading term would be a meaningful advance if the assumptions and algorithm correspondence are established. (2) The ordered-momentum way sounds. Aligning delayed updates with their original time indices provides a coherent way to reason about the difference between asynchronous and idealized synchronous momentum.

Critical weaknesses

(1) The experiments do not appear to match the algorithm underlying the main convex theorem. The theorem uses αt=t\alpha_t=t, whereas the experiments use a constant-parameter variant. Without a separate guarantee for the tested variant, the experiments do not directly validate the headline theoretical result. (2) The empirical evidence is limited to substantiate the parallel-scaling and realistic-delay claims. The study uses a small CNN on Fashion-MNIST, only two worker counts, and a constructed quality-dependent delay process. It does not demonstrate scaling with MM, wall-clock acceleration, or behavior under naturally variable-compute workloads.

Questions for authors

(1) Clarify the update rule used in the experiments: Algorithm 2 with αt=t\alpha_t=t, or the constant-parameter update in Section 5? If the latter, what convergence guarantee applies to that specific implementation? (2) In Algorithm 2, how are multiple workers' first responses at the common initial point handled? Why does the initialization treatment differ from Algorithm 1, and can duplicate initial gradients enter the accumulated update?

2 comments

We thank the reviewer for the thoughtful feedback. We appreciate your recognition of the significance of a worker-independent leading term and the rationale behind ordered momentum.

  • Regarding the hyperparameter choices. Thank you for pointing this out. Indeed, our convex theorem uses αt=t\alpha_t=t, whereas our neural-network experiments use a constant-parameter variant for nonconvex training. Our choices follow common practice in optimization, where convex theory guides algorithm design and practical parameters are adapted to nonconvex training. For example, Adam's convex analysis [2] uses decreasing parameter schedules at tt, while its neural-network experiments use a constant base learning rate and fixed momentum. We similarly follow the fixed-parameter implementation of μ2\mu^2-SGD in [1, Appendix H.3], and the common momentum choice of 0.90.9 for the momentum baselines.

  • Regarding the empirical scope and scaling evidence. We thank the reviewer for these suggestions, which have helped strengthen our work. Following your feedback, we added CIFAR-10 experiments with ResNet-18 and M∈5,7,9M\in{5,7,9} workers, covering data-independent delays and three levels of data dependence (q1∈0.1,0.3,0.5q_1\in{0.1,0.3,0.5}). Ordered μ2\mu^2-SGD achieves the highest peak accuracy across all tested configurations, while the ordered methods remain effective over a broader learning-rate range than their unordered counterparts (please see Section 5 and Appendix D.6). Our simulator also incorporates heterogeneous worker arrival rates: worker ii arrives with probability pi∝ip_i\propto i, producing different average delays across workers and delays that vary throughout training (Appendix D.4). These experiments directly support our central theoretical claims: ordered updates improve optimization and learning-rate robustness across data-dependence levels, worker counts, and delay settings.

  • Regarding the initialization. Thank you for raising this great question. Algorithm 2 intentionally includes every worker's first response at the common initial point x1x_1. The different initialization conventions were chosen to simplify the respective analyses. In Algorithm 1, keeping only the first initial response makes the discrepancy from ideal momentum consist solely of pending gradients (Equations (6)-(8)). Retaining all initial responses would preserve the asymptotic rate but require tracking the extra initial contributions. In Algorithm 2, retaining all initial responses simplifies the analysis of STORM's correction term (Equation (11)): we can pair the extra initial contributions with pending corrected increments and bound their differences using smoothness (Appendix C, Lemmas C.4–C.5). Nevertheless, using Algorithm 1's initialization could also yield the same asymptotic rate by bounding the omitted initial contributions separately. Thus, either algorithm can retain all initial responses or only the first without changing its asymptotic convergence rate.


[1] Tehila Dahan and Kfir Y. Levy. Do Stochastic, Feel Noiseless: Stable Stochastic Optimization via a Double Momentum. ICLR, 2025.

[2] Sashank J. Reddi, Satyen Kale, and Sanjiv Kumar. On the Convergence of Adam and Beyond. ICLR, 2018.

Thank you for the clarification. My concerns have been addressed, and I will maintain my original rating.

Reviewer_hy1MOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies asynchronous stochastic optimization under data-independent and data-dependent delays. It proposes momentum updates weighted by gradient computation indices and extends the framework using STORM and parameter averaging. The paper presents convergence guarantees for non-convex and convex objectives, alongside simulated asynchronous experiments on Fashion-MNIST examining learning-rate robustness.

Critical strengths

None

Critical weaknesses
  1. Insufficient distinction from OrMo in [1]. The proposed method closely resembles OrMo in both naming and its principle of organizing momentum according to gradient computation indices. While the paper extends the theoretical guarantees, the distinction is insufficiently clarified for the non-convex data-dependent setting. In particular, it remains unclear whether this result requires new analytical techniques beyond adapting OrMo’s fixed-step-size analysis under the stronger gradient-boundedness assumption.
  2. Missing comparison with OrMo in [1]. Despite its close methodological connection, OrMo is absent from the experiments, leaving the practical benefits of the proposed modifications over existing ordered momentum unclear.

[1] Chang-Wei Shi, Yi-Rui Yang, Wu-Jun Li. Ordered Momentum for Asynchronous SGD. NeurIPS 2024.

Questions for authors

None

1 comment

Thank you for your feedback and the opportunity to clarify our contributions. Our approach shares the ordering principle introduced by Shi et al. in OrMo and establishes new guarantees: (i) For smooth convex objectives under data-dependent delays, we provide the first guarantee exploiting smoothness and the first whose leading stochastic term does not grow with the number of workers. This data-dependent bound is also the first to match the tight data-independent scaling in iterations and workers. (ii) For nonconvex objectives, we provide a unified approach with a fixed, delay-independent learning rate that achieves the tight data-independent rate and the best-known data-dependent rate. These guarantees use the same gradient assumptions as prior work in each regime. The fixed learning rate supports a unified approach to both data-independent and data-dependent delays and permits standard offline tuning, with a single learning rate selected before training and retained throughout, without calibrating a delay-adaptive schedule. We explain these results and their assumptions below.

  • Nonconvex, data-independent delays: tight rates with a fixed learning rate. OrMo establishes constant-step convergence in Theorem 1, but its sharper data-independent guarantee in Theorem 2 requires delay-adaptive steps, as do related guarantees in prior work [1]. Our Theorem 3.1 achieves the tight rate with a fixed, delay-independent learning rate, under the same assumptions as prior work [1,2]. No bounded-gradient assumption is required. A fixed, delay-independent learning rate offers two benefits: (i) it provides one unified approach for both data-independent and data-dependent delays, and (ii) it enables standard offline tuning: a single learning rate can be selected before training and retained throughout, without calibrating a delay-adaptive schedule.

  • Data-dependent delays: matching the best-known rate under the same gradient assumptions. Our Theorem 3.2 matches the best-known nonconvex rate under the same assumptions as Mishchenko et al. [1, Theorem 2], including the uniform gradient bound. The distinction from OrMo concerns which gradients the assumption controls: OrMo's Assumption 2 bounds the second moment of a freshly sampled gradient. Under data-dependent delays, pending gradients may not follow the original sampling distribution, since slower samples are more likely to remain pending. Consequently, a fresh-sample second-moment bound does not automatically control the contribution of pending gradients, whereas a uniform gradient bound does. Specifically, in our work, the proof of Lemma B.5 in Appendix B uses Assumption 2.4 to establish ∥bt∥≤β(M−1)G\|b_t\|\le\beta(M-1)G, where btb_t denotes the contribution of pending gradients defined in Equations (6)-(8). Thus, our data-dependent guarantee uses the same gradient assumption as the best-known result, while our tighter data-independent guarantee in Point 1 does not require this assumption.

  • Smooth convex optimization: the first data-dependent guarantee matching tight data-independent scaling. We show that combining ordering with double momentum yields Ordered μ2\mu^2-SGD. Under the stated sample-smoothness and bounded-gradient assumptions, Theorem 4.2 gives

\le O\left( \frac{D(\sigma+D\sigma_L)}{\sqrt{T}} +\frac{D(G+DL)M}{T} \right),$$ where $T$ counts updates and $M$ denotes workers. The previous best convex guarantee was $O(DG\sqrt{M/T})$ [1]. **Our result removes the leading $\sqrt M$ penalty, with worker dependence confined to the lower-order $M/T$ term.** To the best of our knowledge, this is the first convex guarantee to exploit smoothness under data-dependent delays and the first to match the tight update and worker dependence known under data-independent delays. It shows that data-dependent delays need not compromise the leading-order benefit of parallelization. The guarantee also holds across a broad range of learning rates, reducing sensitivity to tuning. 2. **Experimental comparison with OrMo** Thank you for this suggestion. A direct comparison with OrMo would be interesting for understanding the practical differences between ordering formulations. Our experiments, however, were designed to assess the robustness gained through ordering, the performance benefits of double momentum under data-dependent delays, and performance against standard asynchronous SGD baselines. We isolate the contribution of ordering by comparing each ordered method with its unordered counterpart. These comparisons provide empirical support for the benefits motivated by our theoretical results. --- [1] Mishchenko, K., Bach, F., Even, M., and Woodworth, B. Asynchronous SGD Beats Minibatch SGD Under Arbitrary Delays. NeurIPS, 2022. [2] Shi, C.-W., Yang, Y.-R., and Li, W\.-J. Ordered Momentum for Asynchronous SGD. NeurIPS, 2024.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.