Faster Stochastic Optimization with Arbitrary Delays via Adaptive Asynchronous Mini-Batching
Authors: Amit Attia
Ofir Gaash
Tomer Koren
Venue: ICML 2025 poster (2025)
Keywords: Asynchronous
delay
stochastic
optimization
arbitrary
mini-batching
batching
Primary area: theory->optimization
TL;DR: Improved rates for asynchronous stochastic optimization with better delay adaptivity via asynchronous mini-batching

Abstract: We consider the problem of asynchronous stochastic optimization, where an optimization algorithm makes updates based on stale stochastic gradients of the objective that are subject to an arbitrary (possibly adversarial) sequence of delays. We present a procedure which, for any given $q \in (0,1]$, transforms any standard stochastic first-order method to an asynchronous method with convergence guarantee depending on the $q$-quantile delay of the sequence. This approach leads to convergence rates of the form $O(\tau_q/qT+\sigma/\sqrt{qT})$ for non-convex and $O(\tau_q^2/(q T)^2+\sigma/\sqrt{qT})$ for convex smooth problems, where $\tau_q$ is the $q$-quantile delay, generalizing and improving on existing results that depend on the average delay. We further show a method that automatically adapts to all quantiles simultaneously, without any prior knowledge of the delays, achieving convergence rates of the form $O(\inf_{q} \tau_q/qT+\sigma/\sqrt{qT})$ for non-convex and $O(\inf_{q} \tau_q^2/(q T)^2+\sigma/\sqrt{qT})$ for convex smooth problems. Our technique is based on asynchronous mini-batching with a careful batch-size selection and filtering of stale gradients.

Faster Stochastic Optimization with Arbitrary Delays via Adaptive Asynchronous Mini-Batching
Amit Attia
Ofir Gaash
Tomer Koren 1
Abstract
server for averaging, followed by an update step to the model. primary drawback of this method is the syn- chronization performed by the server, which confines the iteration time to be aligned with that of the slowest machine. Hence, variation in arrival time of stochastic gradients due to different factors such as hardware imbalances and varying communication loads, can dramatically degrade optimiza- tion performance.
We consider the problem of asynchronous stochas- tic optimization, where an optimization algo- rithm makes updates based stale stochas- tic gradients of the objective that are subject to an arbitrary (possibly adversarial) sequence of delays. We present a procedure which, for any given q (0, I], transforms any stan- dard stochastic first-order method to an asyn- chronous method with convergence guarantee de- pending on the q-quantile delay of the sequence. This approach leads to convergence rates of the form /TT + t o/V for non-convex and O(Fg/(/T)² + oo/vqT) for convex smooth prob- lems, where Ty is the q-quantile delay, gener- alizing and improving on existing results that depend on the average delay. We further show method that automatically adapts to all quan- tiles simultaneously, without any prior knowl- edge of the delays, achieving convergence rates of the form 0 (inf, ///q + o//qg) for non- convex and (inf (qT) / VQT) for con- vex smooth problems. Our technique based on asynchronous mini-batching with a careful batch- size selection and filtering of stale gradients.
An approach to mitigate degradation caused by delayed gra- dient computation is asynchronous stochastic optimization (Nedié al., 2001; Agarwal & Duchi, 2011; I; Chaturapruck et al., 2015; Lian et al., 2015; Feyzmahdavian et al., 201 6), where stochastic gradients from each worker are sent to a server, which applies them immediately and without syn- chronization. Thus, an update executed as soon as a stochastic gradient received by the server, independent of other pending gradients. significant challenge in these methods is the use of stale gradients, i.c., gradients that were computed in earlier steps and thus suffer from substantial de- lays, potentially rendering them outdated. Numerous studies have investigated asynchronous optimization under various delay models, including recent results under constant delay (Arjevani et al., 2020; Stich Karimireddy, 2020), constant compute time per machine (Tyurin & Richtarik, 2023), and the more general arbitrary delay model (Aviv al., 2021; Cohen et al., 2021; Mishchenko et al., 2022; Koloskova et al., 2022; Feyzmahdavian & Johansson, 2023), where the sequence of delays is entirely arbitrary, and possibly generated by an adversary. The latter challenging setting is the focus of our work.
1. Introduction
Stochastic first-order optimization methods play pivotal role in modern machine learning. Given their sequential nature, large-scale applications employ distributed optimiza- tion techniques to leverage multiple cores machines. Mini-batching (Cotter et al., 2011; Dekel et al., 2012; Duchi et al., 2012), perhaps the most common approach, involves computing several stochastic gradients of a single model across number of distributed workers, sending them to
Early work on asynchronous stochastic optimization consid- ered constant bounded delay and showed that the maximal delay only affects lower-order term in the convergence rates, first for quadratic objectives (Arjevani et al., 2020) and subsequently for general smooth functions (Stich & Karimireddy, 2020). More recent studies in the arbitrary delay model established that a tighter dependence can be obtained, moving from dependency on the maximal delay to bounds depending the average delay (Cohen et al., 2021; Aviv et al., 2021; Feyzmahdavian & Johansson, 2023) or the number of distributed workers (Mishchenko et al., 2022; Koloskova et al., 2022).
Blavatnik School of Computer Science, Tel Aviv University "Google Research Tel Aviv. Correspondence to: Amit Attia <ami- tattia mai..tau.ac.il>.
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Faster Stochastic Optimization with Arbitrary Delays via Adaptive Asynchronous Mini-Batching
However, existing results for the arbitrary delay model suf- fer from several shortcomings. First and foremost, while the dependence on the average delay is tight in some scenarios (e.g., with constant, or nearly constant delays), it remains un- clear whether better guarantees can be achieved in situations with large variations in delays. Indeed, the average delay is known not to be robust to outliers, which are common in vastly distributed settings, and ideally one would desire to rely on more robust statistic of the delay sequence, such as the median. Second, no accelerated rates have been es- tablished for convex smooth optimization, and many of the existing convergence results, notably in non-convex smooth optimization, require a known bound on the average delay or on the number of workers. Lastly, the design and analysis of asynchronous stochastic optimization methods are rather ad-hoc, necessitating the analysis of methods from scratch for each and every optimization scenario.
upper bound on the respective quantile delay.
Furthermore, to our knowledge, this result yields the first accelerated convergence guarantee for convex smooth prob- lems with arbitrary delays. The results are established in a fully black-box manner, requiring only the simpler anal- yses of classical methods instead of specialized analyses in the asynchronous setting. We also note that many more convergence results may be obtained using our procedure with other standard optimization methods, for example us- ing SGD for strongly convex objectíves, results with high- probability guarantees and with sate-of-thheart adaptive methods such as AdaGrad-noma (Ward et al., 2020; Faw et al., 2022; Attia & Koren, 2023; Liu et al., 2023) and other parameter-free methods (Attia & Koren, 2024; Khaled & Jin, 2024; Kreisler et al., 2024).
Black-box conversion for all quantiles simultaneously. Our second main contribution is more intricate black-box procedure which does not require any upper bound on the delays but instead adaptively and automatically matches the convergence rate corresponding to the best quantile-delay bound in hindsight. The fourth column of Table presents the results of the procedure when coupled with SGD and accelerated SGD.
1.1. Summary of Contributions
In this work address the shortcomings mentioned above. Our main contributions are summarized as follows:
Black-box conversion for given quantile delay. Our first contribution is simple black-box procedure for trans- forming standard stochastic optmizaation algorithms into asynchronous optimization algorithms with convergence rates depending on the median delay, and more generally- on any quantile of choice of the delay sequence. More specifically, given any q and an upper bound Tg over the q q-quantile delay, and given virtually any standard stochastic first-order optimization method, our procedure produces an asynchronous optimization method whose convergence rate depends on Tg rather than on the average delay. When coupled with SGD for non-convex or convex Lipschitz ob- jectives, and with accelerated SGD for convex smooth ob- jectives, we establish sfate-of-the-ee convergence results in the respective asynchronous optimization settings; these are detailed in the third column of Table 1.
The results provide the first convergence guarantees for asynchronous non-convex smooth and convex Lipschitz problems that does not require any bound of the average delay (or on the number of machines), and accelcrated rates for convex smooth optimization. In addition, we recall that the average and median delays could be overly pes- simistic compared to other quantile delays (we discuss this in Appendix C), while our adaptive quantile guarantee auto- matically adjusts to the best quantile bound in hindsight and therefore avoids suboptimal factors in its convergence rate.
Experimental Evaluation. Finally, we demonstrate that coupling SGD with our first proposed black-box conver- sion improves performance over vanilla asynchronous SGD when training a neural network on a classification task in a simulated asynchronous computation setting.
The guarantees for non-convex and convex optimization improve upon previous results that depend on the average delay bound (Cohen et al., 2021; Mishchenko et al., 2022: Koloskova et al., 2022; Feyzmahdavian & Johansson, 2023). When considering q = 0.5 for example, the improvement follows since the median is always bounded by twice the average delay, but it can also be arbitrarily smaller than the average delay.' In Appendix C we further demonstrate cases where the median itself is significantly larger than other, smaller quantiles of the sequence; our procedure is able to provide bounds depending on the latter, provided an
1.2. Discussion and Relation to Previous Work
Fixed delay model. Earlier work on delayed stochastic optimization considered a model where the delay is fixed. The work of Arjevani et al. (2020) on quadratic objectives followed by the results of Stich & Karimireddy (2020) for general smooth objectives established that the delay param- eter affects the "deterministic" low-order convergence term of SGD, which can be extended to dependence on the maximal delay in the more general arbitrary delay model. This dependence on the maximal delay is the best one can achieve for (fixed stepsize) vanilla SGD in the arbitrary de-
1 Indeed, this follows from a simple application of Markov's inequality: Tmed I Tavg// / 2 Tmed) I 2Tagg where is chosen uniformly at random. On the other hand, for the delay sequence d, = 1[1 > T/2+ + 1](1- 1), we have med O and Tavg 2(7).
2

---

Two later studies focused on the arbitrary delay model but under the assumption of a bounded number of machines (Koloskova al., 2022; Mishchenko et al., 2022). By ad- justing the stepsizes of SGD according to this quantity they provided guarantees that depends on the number of ma- chines. As previously observed, the average delay is in fact bounded by the number of machines (see Appendix B for a Faster Stochastic Optimization with Arbitrary Delays via Adaptive Asynchronous Mini-Batchin
Table 1: Convergence results for rounds of asynchronous stochastic optimization with arbitrary delays (other delay models are omitted from the table); Tavg is the average delay and Tq is the q quaunttile delay. Note that quantile-delay bounds are superior to average-delay bounds, as the median delay (q = 1/2) is always bounded by twice the average delay, and may be significantly smaller; see Appendix C for details. Only the results of Algorithm 2 and (Aviv et al., 2021) depend on the actual delay parameters and not on known upper bounds. The results of Koloskova et al. (2022); Mishchenko al. (2022) depend in fact on the number of machines in master-worker setup, which upper bounds the average delay (see Appendix B).
PRIOR TIATE-OF-THE-AE
ALGORITHM (COR, 2)
ALGORITHM 2
CENTRALIZED OPTIMIZATION
SETTING
(THMS. 3.6)
non-convex, smooth
1+T
T
+
VT
ar [a]
1+Ta
qT
VqT
+ VeT inf q7
14Tg
$ +
Ø [d] vT
convex, smooth
T+T
+
VT
or [b]
(qTT= + VqT
I+r
1+t inf (qT)) + iT
VqT
7 [el
VT
convex, non-smooth
VItTug
(I+cr)
Vi+T,+ VqT
inf,
VI+r,to vT
1 [c]
vT
vT
"(Cohen et al., 2021; Mishchenko et al., 2022; Koloskova et al.. 2022), (AAivv et al., 2021; Cohen et al., 2021; Feyzmahdavian & Johansson, 2023), "(Mishchenko et al., 2022). (Ghaddimi & Lan, 2013), 'LLan, 2012).
layed model, without further modifications to the algorithm: for completeness, we prove this formally in Appendix D.
Other delay models. While the arbitrary delay model has garnered attention in recent years, additional delay models were considered in previous work. Sra et al. (2016) studied the convergence of asynchronous SGD while either assum- ing a uniform delay distribution with bounded support or delay distributions with bounded first and second mo- ments. Closely related to our paper is the work by Tyurin Richtarik (2023), who use mini-batching to achieve guaran- tees for non-convex, convex and convex smooth optimiza- tion (included accelerated rates) using standard optimization methods. The asynchronous model of (Tyurin & Richtarik, 2023) is limited to constant compute time per machine with a finite number of machines, and does not support vari- ation in delays due to variable communication times and failures of machines, like the arbitrary delays does. Our approach may be viewed as a considerable generalization of the asynchronous mini-batching technique the arbitrary delay model, achieving adaptivity to the delay quantiles instead of the top-m machines as in (Tyurin & Richtarik, 2023). Yet another delay model studied in several works involves delayed updates to specific coordinates in a shared parameter vector (Recht et al., 2011; Mania et al., 2017: Leblond et al., 2018).
Bounded average delay. Several recent works targeted the arbitrary delay model, devising methods which obtain better convergence rates that does not depend on the maxi- mal delay. Cohen et al. (2021) proposed the "picky SGD" method, where stale gradients are ignored if they are far from the current step, obtaining rates that depends on the average delay for non-convex and convex-smooth problems. Although their method does not implicitly require a known delay bound, to ensure convergence given a fixed steps bud- get an average delay bound is required. In addition, their method provides a guarantee only for the best encountered point (which cannot be computed efficiently) instead of the output of the algorithm, and non- ancelereeee rates for convex-smooth objectives. Feyzmahdavian & Johansson (2023) provides a guarantee for convex smooth optimiza- tion that depends on the average delay by filtering gradients with delay larger than twice the average delay bound (which is essentially used as a median delay bound). Similarly to the other works, a known bound is required and only a non- non-accelerated rate is provided. Aviv et al. (2021) is the only work we are aware of that does not require known delay bound, but their result holds only for convex-smoode problems and does not yield accelerated rates. Our quantile- adaptive results, on the other hand, avoid the limitations mentioned above.
Asynchronous mini-batching. Several works used mini- batching in an asynchronous setting. Feyzmahdavian et al. (2016) considered the use of mini- mini-batching at the worker level, using a maximal delay bound and achieving sub- optimal results with respect to the maximal delay. We on the other hand use mini- mini-batching across workers to reduce the effect of stale gradients. Dutta et al. (2018) discussed several variants of synchronous and asynchronous SGD (in- cluding K-batch sync SGD which is similar to our use of asynchronous miii-batching! focusing on the wall clock- time given certain distribution assumptions on the compute time per worker. While providing insight regarding the run- time of the variants, they do not consider the fact that one
short proof) and as such we improve upon these results in a similar fashion.
3

---

Faster Stochastic Optimization with Arbitrary Delays via Adaptive Asynchronous Mini-Batching
can increase the batch size of SGD to a certain point (at the cost of fewer update steps) without degrading the theoreti- cal performance. As mentioned above, the closely related "Rennala SGD" method of Tyurin & Richtarik (2023) used asynchronous mini-batching in a more restricted fixed com- putation model, where each machine m computes gradients at a constant Am time.
arbitrarity long or hang indefinitely. Notably, their method requires prior knowledge of delay distributions and allowing worker restarts mid-computation.
2. Preliminaries
2.1. Stochastic Optimization Setup
In this work we are interested in minimization of a dif- ferentiable function f W - R for some convex set " S Rd. We assume a standard stochastic first-order model, in which we are provided with unbiased gradient oracle g W - Rd with bounded variance, i.e., for any w,
Beyond homogeneous i.i.d. data. One way to move be- yond the standard assumption of homogeneous i.i.d. data is to consider asynchronous optimization with heteroge- neous data, where different workers access disjoint subsets of the training set (Mishchenko et al., 2022; Koloskova et al., 2022; Tyurin & Richtarik, 2023; Islamov et al., 2024). Prior work in this setting often relies on additional struc- tural assumptions-for example, fixed per-machine delays (Tyurin & Richtarik, 2023, Theorem A.4) or specific dis- tributional assumptions (Mishchenko et al., 2022, Assump- tion 2>-wiich are typically required ensure that data on slower machines is accessed frequently enough for effective optimization. Moreover, recent work has explored the im- pact of Markovian sampling strategies, where temporally correlated samples induce biased gradient oracles, as com- monly encountered in reinforcement learning, on optimiza- tion with delayed feedback (Adibi et al., 2024; Dal Fabbro et al., 2024). Extending our framework to accommodate such forms of data heterogeneity and temporal dependence presents promising direction for future research.
[lg fww) and E[llg(w) V f(w)]] s o²
for some o 2 O. In the following sections we will discuss algorithms which receive an initialization wi WW per- forms T gradient queries and output a point w. We consider the following optimization scenarios:
(i) Non-convex setting. In this case we assume that the domain is unconstrained (W Rd). f is B-smooth, and lower bounded by some f*. We also assume that the algorithm receives a bound F f(w)) ff.
(ii) Conver non-smooth setting. Here we assume that the domain has bounded diameter, i.e., for any x, W. ||x - yll S D for some D > O, and that f is convex and G- G-Lipschitz over W.
(iii) Convex smooth setting. Finally, we also consider the setting where domain is unconstrained ('W = Rd) and the objective f is convex, ß-smooth, and admits a minimizer w* E arg min (w) We also assume that the algorithm receives a bound D 2 [[ -w
Delayed feedback in online learning and Multi-A Armed Bandits. Scenarios of delayed feedback were also stud- ied in the literature on online learning and multi-armed bandits (Dudik et al., 2011; Joulani et al., 2013; Vernade et al., 2017; Gael et al., 2020). In particular, the work of Lancewicki et al. (2021) achieves a regret guarantee with an adaptivity to the quantiles of the delays distribution, analo- gous our result in the stochastic optimization setup.
2.2. Asynchronous Optimization with Arbitrary Delays
We consider the same asynchronous optimization model as in (Aviv et al., 2021; Cohen et al., 2021), which consists of T rounds, where each round involves the following: (i) The algorithm chooses a model Wy; (ii) the algorithm receives a pair (gt, d,), where 8, is a stochastic gradient of f at Wy-d,- The delays d, here are entirely arbitrary, and can be thought of as chosen by oblivious adversary (in advanced, before the actual optimization process begins). Note this means that the delays are assumed to be independent (in a probabilistic sense) of the stochastic gradients observed during optimization.
Concurrent work. Recently and concurrently to our work, Tyurin (2025) and Maranjyan et al. (2024) studied de- lay models that extend the fixed-compute framework of Tyurin & Richtarik (2023). Most relevant to our work, Tyurin (2025) demonstrated that SGD with gradient filter- ing and accumulation is optimal in their time-delay model, by proving a lower bound for zero-respecting first-order algorithms. While their computational model accommo- dates arbitrary delays, it deviates from prior asynchronous frameworks (c.g.. Cohen et al., 2021; Mishchenko et al., 2022; Koloskova et al., 2022) and results in recursive con- vergence bounds that lack direct interpretation. In contrast, our approach provides more informative guarantees derived from natural empirical quantities, such as the quantiles of observed delays. Maranjyan et al. (2024), on the other hand, addresses scenarios where worker computations may take
Throughout, we let Tavg denote the average delay; Tied de- note the median delay; and Tg denote the q-quantile delay
2A function ff is said to be f-smooth if for any x, E W, IV vf(ii & Blxx yll. This condition also implies that for any x, E W. f(y) & f(x) +V(()) (((x))(yy-- x))x)++ + f - xI|2. 3we define a q-quantile of the delay sequence for q E (0, 1J as

---

(ii) Accelerated stochastic gradient descent (accelerated SGD, Lan, 2020), which guarantees in the convex smooth setting that (Lan, 2020, Proposition 4.4) Faster Stochastic Optimization with Arbitrary Delays via Adaptive Asynchronous Mini-Batching
We further treat the quantile delays (Tg for q E (0, IJ) as integers. This can be done without loss of generality be- cause the delays are all integers, so [tg] remains a valid g-quantile, and smaller quantile delays tighten our guaran- tees.
to asynchronous optimization rates using the asynchronous mini-batching scheme.
Algorithm 1: Asynchronous mini batthig
Input: Batch size B, stochastic optimization algorithm A(o,, K)
2.3. Classical Stochastic First-Order Optimization
1 1
# rounds count
Our asynchronous mini-batching technique enables the di- rect application of classical stochastic optimization methods in a delayed setting. Since we use these methods in a black- box manner, we do not present them here but rather only state the relevant rates of convergence. The exact conver- gence results we give here are taken from Lan (2020) and are specified in more detail in Appendix A.
for k < 1,2..... K do
# queries count
Get query We from A
1k +/! b 0
# first step with w, = W.
8k -0
while b B do
Play wi W Receive (gr.di) if ck S 1 d, then Rk c Rx + BB b b+1 1 r+1+1
# ensures w = Wx
Following are the algorithms we use in our work, which re- ceive an initialization w/ E W, performs V' gradient queries and output a point w:
Send response ğI: to A Output result produced by A
(i) Stochastic gradient descent (SGD, Lan, 2020), which in the non-convex setting guarantees that [( = O(BF/T+ /VBF/ /T)), and in the convex smooth setting provides the guarantee [[ - [w]"]] = O(BD² + D/VT) (Lan, 2020, Corollary 6.1).
Theorem 1. Let F be some function class of differentiable functions, let f E I and let be a stochastic first-order oracle with o2-bounded variance. Let A(or K) be a K- query stochastic first-sticfrrs--rrdde first-order optimization algorithm for class Ff with a convergence rate guarantee of Ratelf, or, K). For T asynchronous rounds, let Tq be the q-quantile de- lay for some q E (0, and let B = max Eg) for some tq 2 Tq. Then the output of Algorithm I with batch size B and A(or/VB, LqT 25g) has a convergence rate guarantee of Rate(f fofffo//// / Fg), L4T/(1 + +24g)
(ii) Projected stochastic gradient descent (PSGD, Lan, 2020), which in the convex non-smooth setting pro- vides a guarantee of E[ - min f(w)] = DDD(++o)/VT) (Lan, 2020, Theorem 4.1).
(W)
Theorem I uses a delay bound of the q-quantile delay and an optimization algorithm, inheriting the convergence rate of the original algorithm with a modified effective number of steps that depends on the delay quantile and decreased stochastic variance bound due to the mini-batching. Note that the above guarantee can be significantly stronger than that of naive synchronous mini-batching. where the iteration time is determined by the slowest machine, since the pro- posed method allows faster machines to contribute multiple times per batch. To better understand the result we present the following corollary, which is a direct application of the theorem with the classical stochastic methods detailed in Appendix A.
=
3. Asynchronous Mini-Batching
In this section we present and analyze general template for mini-batching with asynchronous computation. The template, presented in Algorithm 1, receives a batch size parameter and a stochastic optimization algorithm A(r, K), an algorithm performing K point queries for stochastic gra- dients which has a variance bounded by ? to compute an output point. Then the template uses the asynchronous computations to simulate mini-batched optimization. ignor- ing stale gradients with respect to the inner iterations of A according to their delays.
Corollary 2. Let f :W- - R be differentiable func- tion, : W - Rd a first-order oracle of f with variance bounded by x² 2 0, T > 0 the number of asynchronous rounds, E (0. and Êg > 0 such that T4 S &g. where Tq is the q-quantile delay. Then the following holds:
Following is our main result about Algorithm 1, which pro- vides black-box conversion of standard optimization rates
any Ty 2 0 that satisfies both Pr(d s TT) 2 q and Pr(d 2 Ty) 2 1 q, where d is sampled uniformly from (d]...., .d........ We also define the I-quantile TI Tmax-
(i) In the non- non-comvex smooth setting, Algorithm I with nuned SGD and batch size of max(1, (1, Fg) produce w
5

---

Faster Stochastic Optimization with Arbitrary Delays via Adaptive Asynchronous Mini-Batching
which satisfy
T asynchronous rounds, a sufficient condition for an ouipul to be produced is
E[ITS(M)]] (g) q7
(1
OBBF
VqT
qT Tq
K S sup gE
(i) In the convex smooth setting. Algorithm I with tuned SGD and batch size of max Fq) produce w which satisfy
Proof of Lemma Let be the number of responses A receives and assume by contradiction that K' K. Let q (0, IJ. At least [q'"] rounds have delay less equal Tq. Let n(k) be the number of asynchronous rounds with delay less or equal Tq at times I r << [k+1- Assume by contradiction that n(k) > B Tq for some k, and let S (a).... an(k)) be the rounds during the k'th iteration with da, S Tq ordered in an increasing order. For any i Ty (which implies that 2 Tq as both are integers), as the sequence is non-decreasing and di fg.
ELS(W) - f(w)) = of
(1 (1+ F))BB2
Do VqT
q7
(iii) In the convex smooth setting, Algorithm 1 with tined accelerated SGD and batch size of max Rg) pro- duce which satisfy
Do - - f(w"] of (1+ PBD
a; 1x 2 a: a1
Ty day
(qT)2
VqT
which means that the inner "if" condition is satisfied and contradicts the condition of the while loop, b B, since there are at least B rounds a; E S with > Ty (because our assumption by contradiction yields [S] 2 B Tq + as we deal with integers). Thus, nt(k s B B+ for all E [K']. As each B consecutive rounds with delay less or equal Tq must account for response to A, and we have least [qT] such rounds.
(iv) In the convex Lipschitz setting, Algorithm with tuned projected SGD and batch size of max 1, Rq} produce which satisfy
DC D(v1+ 1+ F G
E[f
min f(w)] = WEW
VqT
Proof. The result follows by a simple application of Theo- rem which provides a rate
qT'
K'
B Tq
ofte(f..o/ 5g). LgT/
As this is true for any q E (0, 1].
qT
with each of the standard convergence guarantees (Lem- mas 3 to 6 in Appendix A).
K' > sup qE(0.11
2 K
O
B
Tgg
which contradicts the assumption K'
We shortly remark that, as the median delay is bounded by twice the average delay and may be much smaller, and the number of machines is always larger than the average delay (see Appendices B and C for details), our results pro- vide tighter guarantees than existing results that depend an average delay bound or the number of machines (Cohen et al., 2021; Mishchenko et al., 2022; Koloskova et al., 2022; Feyzmahdavian Johansson, 2023), without requiring a specialized optimization analysis in the asynchronous set- ting. In addition, are the first provide an accelerated rate in the convex smooth setting.
We proceed to prove the main result.
Proof of Theorem By Lemma w is produced since
q"T d'E(0.1) Tg¹
qP'
ql'
sup
2
2
=
B
TT
1 25g
The fx S r- d, condition ensures that the gradient at round is of Wx. as w, W for all f. S t f We conclude using the linearity of the variance to bound the variance of the mini-batch.
Following is the key lemma for proving Theorem 1, which provides a condition to ensure that я receives sufficiently many updates so as to produce a effective result. Its proof follows.
E |l V
S max 1, Fg
Lemma 1. Let B E N and A(a, K) a stochastic optimiza- tion algorithm for some K E and o 2 O. Then when running Algorithm I with batch size B and algorithm A for
invoking the rate guarantee of
a(oo/mmax (.).////T(1111111 (1)T((1+2)))).
6

---

Faster Stochastic Optimization with Arbitrary Delays via Adaptive Asynchronous Mini-Batchhn
4. Quantile Adaptivity
Algorithm 2: Asynchronous mini-batching sweep
The method described in the previous section require as input an upper bound of a given quantile of the delays. Next, we show how to achieve more robust guarantees without prior knowledge about the delays, by establishing guaran- tees that are competitive with respect to all quantiles simul- tancously.
Input: Batch sizes B,, Epoch lengths K,, K K-uueyy algorithm ((K)))
# rounds count
for i < ..2 do Initialize A(K,) for k +- 1,2...., K; do # query count th epoch
Get query w/ from (i)
First, let us clarify our objective. We begin with the smooth non-convex case. Let 4 E (0, I] be an arbitrary quantile. Using Corollary with the tight quantile delay bound Tq. we can obtain a rate of
# #frrst step with w, (
b - 0
8
while b < B, do
(1+ B/) (1ET
(1
O BNBF
Play wr W/
(8)
G7
VqT
Receive (8,, dz)
(i)
1 d, then ensures wr-d, =0
As each q e (0, 1] produce difference guarantee, our objective is to provide guarantee of
- (1)
8k
8k
+ B
b- b-b+1
of inf [0,00
(1 BF
OBBT
1+1
Send response 8(() to A Receive output W; from A
qp'
VqT
without knowing in advance which quantile q achieves this infimum.
for some F 2 f(w1) - f then
Our quantile-adaptive template of asynchronous mini- batching appears in Algorithm 2. Since the best quantile (for which the best convergence rate is achieved) is not known in advance, it cannot be used to tune the batch size. For that reason, the template extends Algorithm I by perform- ing multiple asynchronous mini-batching iterations with different batch sizes and time horizons, essentially making it into an any-time algorithm using a doubling procedure (Cesa-Bianchi & Lugosi, 2006). By carefully selecting the parameters, we can achieve the desired quantile adaptivity.
24(1 + 2T. gE(0.1)
24 NBF
[[IV][
inf
qT
VqT
(8) W = Rd, f is convex, B-smooth and admits a min- imizer w*, setting A(K) to be K-steps accelerated SGD initialized at w with stepsize 4z. K; = 2 .and
o K,K, 1)2
B, max max 1,
1282-12 1D2
Following is our second main result which provides quantile adaptivity by coupling Algorithm 2 with SGD and acceler- ated SGD. Additional results using SGD in the convex and convex smooth settings appear in Appendix E.
for some D 2 [| - wl. then E[S(ww) - [[(w**] is
bounded by
192(1 + +2
720
Theorem 3. Let W S. d be a convex set, f:W- - R be differentiable function, g :W- - Rd an umbiased gradient oracle of f with bboundded variance, T E N and w E W. Running Algorithm 2 for T asynchronous steps with some parameters A, Bi, Bz.... and Tı, .2...., let W- (W1,...,wy w) be the outputs of A, and let be Wi if W is non-empty and wi otherwise. Then the following holds:
inf qE(0,11
T2T2
VqT
Note that the infimum over quantiles in the statement above is at least as good as the median (or any other given quan- tile), improving upon Corollary 2 by automatically adapting to the best quantile without requiring any prior knowledge of a quantile upper bound. This is achieved by maximiz- ing the batch size according to the underlying rate of A instead of using the delay bound. As discussed at length in Sections 1.1 and 1.2, this adaptivity to quantile delays is more robust than existing average delay dependent results, and can further achieve accelerated guarantees for convex smooth objectives.
(i) If = =d, f is B-smooth and lower bounded by ft. setting A(K) to be K-steps SGD initialized w with stepsize B.
K; 2 and B, max (1, < 1.
We omit the variance input parameter of A in Algorithm 2 since is not used.
2,3F
7

---

Faster Stochastic Optimization with Arbitrary Delays via Adaptive Asynchronous Mini-Batchin
Next is the key lemma of the procedure which links the total number of rounds 7' with the effective number of responses A receives. It is essentially an extension of Lemma I and follows the same proof technique. For the proof see Ap- pendix F.
( To that end note that 8k is the average of By i..d. unbiased estimations of f & )) and by the linearity of the variance ) has variance bounded by o2/ Thus, our selection of parameters enables us to use Lemma 3 and establish that
Lemma 2. Let B1, Bz.... .......e be a non-decreasing sequence of positive integers and K; = 2'-1 for i E N. Running Algo- rithum for T E I asynchronous steps, let W = (W1,.... W1) be the outputs of A. Then assuming W not empty. for any q e (0, 1].
2BF K
BF 6BF B 1
E [[IV/(W)II]]
+
K₁
24 + 3BH 240 vBF VqT
qT
qi 2( + Kral
As this holds for any q E (0, 1].
24(1 + 2Tq
24 NBF VqT
Following is the proof of item (i) of Theorem 3; we defer the proof of other items to Appendix F.
E| E[IV/f(>))]]] < inf gE(0.1]
0
qT
5. Experimental Evaluation
Proof of Theorem 3 (i). If W is empty, then T < Bj (as
Ti = and the condition = 1 S d, is always satisfied). Hence, as T 2 1, B1 1 and T 2pF, and from smoothness,
To illustrate the benefits of asynchronous mini-batching, we compare "vanilla" asynchronous SGD (denoted Asyne- SGD) with practical variant of our mini-batch method (Algorithm 1), which uses SGD, denoted Async-MB Async-MB-SGII MB-SGD, for training fully connected neural network on the Fashion- MNIST classification dataset (Xiao et al., 2017). 5 The dataset consists of 60,000 training images and 10,000 test images, each of size 28 x 28 pixels and labeled across 10 classes. We use test accuracy as the evaluation metric.
|V/(()) /V/((II & 2BF < o² T q7
for all q (0. 1]. where the first inequality follows by using standard property of smooth functions, V f(w)ll x 2B(f(w)- f*), which is established by the smoothness property between w' = B ((w) and w,
Consider a scenario with a con- stant delay, d, = т, for all E [T]. When running Algo- rithm 1 with batch size т, only one model update occurs every 2r gradient computations, and r I of those gradi- ents are discarded. Although the large amount of discarded gradients only affects the constant factors in the theoretical analysis, it is inefficient in practice. To avoid discarding many gradient computations that are only slightly stale, we modify the condition 'if fx S t-d, d, then" in Algorithm to "if max 221) 11-d, d, then". This change allows the use of slightly older gradients, resulting in an effective delay of at most 2, while increasing the proportion of computations that contribute to model updates. Although this modification in- troduces a small amount of gradient staleness, the improved utilization of computed gradients is beneficial in practice. Our experiments report performance using this variant.
Practical modifications.
f - -(w)) S f(wt) - f(w)
S vf((w) - - w) + B
2 _llu0 ml
2B IVf(w)]
We proceed to the case where W is not empty. Let q E
(0, 1]. By Lemma 2, qT < 2(B + Tg) K141 B/+1* S 17,
4(1 25g) 4(1) K, I
qT $ 2(1 + K1-1
9T
If Bia1 > max(1, Tg).
40 2x2
4o VBF
qI s 4B S
BF
K
Asynchronous workers setup. We adopt the two-phase
asynchronous simulation framework of Cohen et al. (2021), In the first phase, simulate compute times for each worker by drawing from a weighted mixture of two Poisson distributions. In the second phase, we simulate training by having each worker deliver gradients to central server
We are left with applying a standard convergence result for SGD, which is detailed Lemma 3 and establishes that
E [
2BF K
8F2
K
'We also experimented with filtering gradients whose delays exceed the number of machines, as proposed by Koloskova al. (2022), but observed performance similar to that of Asyne-SGD.
where w is the output (a uniformly sampled iterate) of K- steps SGD with fixed stepsize y = min(1/B, 2BK)
8

---

Faster Stochastic Optimization with Arbitrary Delays via Adaptive Asynchronous Mini-Batthinn
Table Fashion -NNIOT test accuracies for Asyne-SGD and Asyne- Berue-MB-SSe MB-SGD across different numbers of workers and update steps. The test accuracy column reports mean = standard deviation across runs with different seeds.
NUM. WORKERS
NUM. STEPS
METHOD
LEARNING RATE
TEST ACCURACY
Async-SGD
0.021544
0.8449 = 0.0013
40
7,500
Async-MB-SGD(B=2)
0.100000
0.8457 = 0.0004
Asyne-SGID
0.010000
0.8585 0.0017
160
30,000
Async-MB-SGD(B-
0.215443
0.8620 = 0.0008
Async-SGD
0.002154
0.8623 = 0.0015
640
120,000
Async-MBB Sernc-MB-SGIB MB-SGD(B=8)
0.100000
0.8737 + 0.0002
Eryer
0.25
16pe VB 583
0.85
Aoyr PE) SSC
0.55
PO/TY Sp10
0.90
4.11
0.70
0.72
0.20
0.65
1000
2000
3000
4000
3992
6000
7000
0.65
3000
38:000
155000
20000
25000
30000
0.55
20000
40000
00000
30202
100000
120000
Step
Step
Step
Figure 1: Comparison of Tashion-MNIST test accuracy for Async-SGD and ABynC-MB-SGD with varying numbers of workers and update steps. (left) 40 workers, 7,500 steps, (middle) 160 workers, 30,000 steps, (right) 640 workers, 120,000 steps. Each plot presents the mean and standard deviation across 3 runs.
according the generated compute schedule. Specifically, we follow schedule B of Cohen et al. (2021), where each compute time is drawn from a Poisson distribution with parameter P with probability 0.92 and from a Poisson dis- tribution with parameter 150P with probability 0.08, using P == 4.06. To avoid compute times of O, the Poisson distri- butions are shifted by +1. In contrast to Cohen al. (2021), we sample single compute time per update instead of sep- arating the gradient computation and the gradient update. We conduct experiments with 40, 160, and 640 workers, using 7,500, 30,000, and 120,000 update steps, respectively. The linear relationship between the number of workers and update steps reflects the increase in total computation when scaling the number of workers over a fixed time budget.
set 21, 8, 16, 32). For the best set of hyperparameters. report the mean and standard deviation across 3 runs.
5.1. Results and Discussion
Table 2 reports test accuracy under various worker-step configurations. Asyne-SGD and Async-MB-SORe perform similarly with 40 workers, with slight edge to Async-MB- SGD with an accuracy of 84.57%. On the other hand, when the number of workers increases to 160 and 640, Async-MB- SGD consistently outperforms Async-SGD, with accuracy gaps of 0.35% and 1.1%. Notably, Async-MB-SCC uses significantly larger stepsize, which aligns with expecta- tions: the method experiences smaller effective delays due to gradient filtering and benefits from reduced variance via mini-ban batching. Figure 1 presents test accuracy plots under different configurations. We observe smoother curves with MinncMBBSSGDD particularly at larger worker counts. This behavior likely also results from the method's ability to reduce the effective delay of gradient updates.
Model and training setup. We train a three-layer fully connected neural network with input dimension 728 = 28 hidden layers of sizes 256 and 128, an output layer of size 10, and ReLU activations. The model is trained using the cross-entropy loss. To reduce the variation of the last iterate, we use exponential moving averaging with decay 0.99. Each worker uses a local mini-batch of size 8. The learning rate is selected separately for each algorithm from geometric grid with multiplicative factor VTO: for Async-SGD we search over the range [0.001, 1.0], and for Async-MB- [0.01, 1.0]. For Async-MB-SGII we additionally tune the aggregation batch size B (i.e., the number of updates the server accumulates before modifying the model) over the
These results highlight the robustness of Async-MB-SGD to the scale of the number of workers. By mitigating the effects of delayed updates through gradient filtering and mini-batching, the method maintains strong performance and supports larger learning rates even under highly asyn- chronous conditions. This suggests that Asyne-MB-SGI. can serve as a practical alternative to vanilla asynchronous SGD in large-scale distributed training settings.
over

---

Faster Stochastic Optimization with Arbitrary Delays via Adaptive Asynchronous Mini- Mini-Batching
Acknowledgements
Cesa-Bianchi, N. and Lugosi, G. Prediction, learning, and games. Cambridge university press, 2006.
This project has received funding from the European Re- search Council (ERC) under the European Union's 's Horizon 2020 research and innovation program (grant agreement No. 101078075). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council. Neither the European Union nor the granting au- thority can be held responsible for them. This work received additional support from the Israel Science Foundation (ISF, grant numbers 2549/19 and 3174/23), a grant from the Tel Aviv University Center for Al and Data Science (TAD), from the Len Blavatnik and the Blavatnik Family founda- tion, from the Prof. Amnon Shashua and Mrs. Anat Ramaty Shashua Foundation, and fellowship from the Israeli Coun- cil for Higher Education.
Chaturapruck, S., Duchi, J. C., and Ré, C. Asynchronous stochastic convex optimization: the noise in the noise and SGD don't care. Advances in Neural Information Processing Systems, 28, 2015.
Cohen, A., Daniely, A., Drori, Y., Koren, T., and Schain, M. Asynchronous stochastic optimization robust to arbi- trary delays. Advances in Neural Information Processing Systems, 34:9024-9035, 2021.
Cotter, A., Shamir, O., Srebro, N., and Sridharan, K. Better mini-batch algorithms via accelerated gradient methods. Advances neural information processing systems, 24, 2011.
Dal Fabbro, N., Adibi, A., Poor, H. V., Kulkarni, S. R., Mitra, A., and Pappas, G. J. Dasa: Delay-adaptive multi- agent stochastic approximation. In 2024 IEEE 63rd Con- ference on Decision and Control (CDC), pp. 3889-3896. IEEE, 2024.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work. none which we feel must be specifically highlighted here.
Dekel, O.,
R., Shamir, O., and Xiao, Optimal distributed online prediction using mini-batches. Journal of Machine Learning Research, 13(1), 2012.
References
Duchi, J. C., Bartlett, P. L., and Wainwright, M. J. Ran- domized smoothing for stochastic optimization. SIAM Journal on Optimization, 22(2):674-701, 2012.
Adibi, A., Dal Fabbro, N., Schenato, L., Kulkarni, S., Poor, H. V., Pappas, J.J., Hassani, H., and Mitra, A. Stochastic approximation with delayed updates: Finite-time rates under markovian sampling. In International Conference Artificial Intelligence and Statistics, pp. 2746-2754. PMLR, 2024.
Dudik, M., Hsu, D., Kale, S., Karampatziakis, N., Langford,
J., Reyzin, L., and Zhang, T. Efficient optimal learning for contextual bandits. In Proceedings of the Twenty-Sevent Conference on Uncertainty Artificial Intelligence, pp. 168, 2011.
Agarwal, A. and Duchi, J. C. Distributed delayed stochastic optimization. Advances in neural information processing systems, 24, 2011.
Dutta, S., Joshi, G., Ghosh, S., Dube, P., and Nagpurkar, P. Slow and stale gradients can win the race: Error- runtime trade-offs in distributed SGD. In International conference on artificial intelligence and statistics, pp- 803-812, PMLR, 2018
Arjevani, Y. Shamir, O., and Srebro, N. A tight convergence analysis for stochastic gradient descent with delayed up- dates. In Algorithmic Learning Theory, pp. 111-132. PMLR, 2020.
Attia, A. and Koren, T. SGD with adagrad stepsizes: full adaptivity with high probability unknown parameters, unbounded gradients and affine variance. In Interna- tional Conference on Machine Learning, pp. 1147-1171. PMLR, 2023.
Faw, M., Tziotis, I., Caramanis, C., Mokhtari, A., Shakkot- tai, S., and Ward, R. A. The power of adaptivity in SGD: Self-tuning step sizes with unbounded gradients and affine variance. In COLT, 2022.
Feyzmahdavian, H. R. and Johansson, M. Asynchronous iterations in optimization: New sequence results and sharper algorithmic guarantees. Journal of Machine Learning Research, 24( 2023.
Attia, A. and Koren, T. How free is parameter-free stochastic optimization? In International Conference on Machine Learning, pp. 2009-2034. PMLR, 2024.
Aviy, R. Z., Hakimi, I., Schuster, A., and Levy, K. Y. Asyn- chronous distributed learning: Adapting to gradient de- lays without prior knowledge. In International Confer- ence on Machine Learning, pp. 436 445. PMLR, 2021.
Feyzmahdavian, H. R., Aytekin, A., and Johansson, M.
An asynchronous mini-batch algorithm for regularized stochastic optimization. IEEE Transactions on Automatic Control, 61(1))3774--3754, 2016.
10

---

Faster Stochastic Optimization with Arbitrary Delays via Adaptive Asynchronous Mini-Batching
Gael, M. A., Vernade, C., Carpentier, A., and Valko, M. Stochastic bandits with arm-dependent delays. In Interna- tional Conference on Machine Learning, pp. 3348-3356. PMLR. 2020.
Mania, H., Pan, X., Papailiopoulos, D., Recht, B., Ramchan- dran, K., and Jordan, M. I. Perturbed iterate analysis for asynchronous stochastic optimization. SIAM Journal on Optimization, 27(4):2202-2) 2229, 2017.
Ghadimi, S. and Lan, G. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM journal optimization, 23(44)2341-2366) 2013.
Maranjyan, A., Omar, O. S., and Richtárik, P. Mindflayer: Efficient asynchronous parallel sgd in the presence of heterogeneous and random worker compute times. In OPT 2024: Optimization for Machine Learning, 2024.
Islamov, R., Safaryan, M., and Alistarh, D. Asgrad: A sharp unified analysis of asynchronous-SCn International Conference on Artificial Intelligence and Statistics, pp. 649-657. PMLR, 2024.
algorithms. In
Mishchenko, K., Bach, F., Even, M., and Woodworth, B. Asynchronous SGD beats minibatch SGD under arbitrary delays. Advances in Neural Information Processing Sys- tems, 35:420 433, 2022.
Joulani, P., Gyorgy, A., and Szepesvári, C. Online learning under delayed feedback. In International conference on machine learning, pp. 1453-1455 1461. PMLR, 2013.
Nedié, A., Bertsekas, D. P.,, and Borkar, V. S. Distributed asynchronous incremental subgradient methods, Studies in Computational Mathematics, 8(C):381-44)) 1077, 2001.
Khaled, A. and Jin, C. Tuning-free stochastic optimization. In International Conference Machine Learning, pp. 23622-23661. PMLR, 2024.
Recht, B., Re, C., Wright, S., and Niu, F. Hogwild!: lock- free approach parallelizing stochastic gradient descent. Advances neural information processing systems, 24, 2011.
Koloskova, A., Stich, S. U., and Jaggi, M. Sharper conver- gence guarantees for asynchronous SGD for distributed and federated learning. Advances in Neural Information Processing Systems, 13:1022-17215, 2022.
Sra, S., Yu, A. W., Li, M., and Smola, A. Adadelay: Delay adaptive distributed stochastic optimization. In Artificial Intelligence and Statistics, pp. 957-965. PMLR, 2016.
Kreisler, I., Ivgi, M., Hinder, O., and Carmon, Y. Accel- erated parameter-free stochastic optimization. The Thirty Seventh Annual Conference on Learning Theory, pp. 3257-3324. PMLR, 2024.
Stich, S. U. and Karimireddy, S. The error-feedback framework: Better rates for SGD with delayed gradients and compressed updates. The Journal of Machine Learn- ing Research, 21(1):9613-9645 2020.
Lan, G. An optimal method for stochastic composite opti- mization. Mathematical Programming, 133(():365-397 2012.
Tyurin, A. Tight time complexities in parallel stochastic optimization with arbitrary computation dynamics. In International Conference on Learning Representations, 2025.
Lan, G. First-order and stochastic optimization methods for machine learning, volume 1. Springer, 2020.
Tyurin, A. and Richtarik, P. Optimal time complexities of parallel stochastic optimization methods under a fixed computation model. Advances in Neural Information Processing Systems, 36, 2023.
Lancewicki, T., Segal, S., Koren, T., and Mansour, Y. Stochastic multi-armed bandits with unrestricted delay distributions. In International Conference on Machine Learning, pp. 5969-5978. PMLR, 2021.
Vernade, C., Cappé, O., and Perchet, V. Stochastic ban- dit models for delayed conversions. In Conference on Uncertainty Artificial Intelligence, 2017.
Leblond, R., Pedregosa, F., and Lacoste-Julien, Improved asynchronous parallel optimization analysis for stochas- tic incremental methods. Journal of Machine Learning Research, 1: 68, 2018.
Ward, R., Wu, X., and Bottou, L. Adagrad stepsizes: Sharp convergence over nonconvex landscapes. Journal of Ma- chine Learning Research, 21(219):1-30, 2020.
Lian, X., Huang, Y., Li, Y., and Liu, Asynchronous parallel stochastic gradient for nonconvex optimization. Advances in neural information processing systems, 28, 2015.
Xiao, H., Rasul, K., and Vollgraf, R. Fashion-mmin
novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXiv: 2017.
Liu, Z., Nguyen, D.,, Nguyen, T. H., Ene, A., and Nguyen, H. High probability convergence of stochastic gradient methods. In International Conference on Machine Learn- ing, pp. 21884-21914, PMLR, 2023.

---

Faster Stochastic Optimization with Arbitrary Delays via Adaptive Asynchronous Mini- Batching
A. Standard Convergence Bounds in Stochastic Optimization
Convergence result SGD for non-convex smooth optimization from Lan (2020) (Corollary 6.1).
Lemma 3. Let f Rd - R be a ß-smooth function lower bounded by f Let g Rd + Rd be an unbiased gradient oracle of f with bb-boudded variance. Then running SGD (termed RSGD in Lan, 2020) for K steps, initialized at w1 ae and with stepsizes Yı= min B1B BKK, where F 2 f(w1) - f*, produce w which satisfy
E [
2BF
BF
K
Convergence result of SGD for convex smooth optimization from Lan (2020) (Corollary 6.1).
Lemma 4. Let f : Rd RR be a B-smooth convex function admitting a minimizer w*. Let g RR Rd be an unbiased gradient oracle of f with 2² bounded variance. Then running SGD (termed RSGD in Lan, 2020) for K steps, initialized at W1 E Rd and with stepsizes ys = m/B o where 2 ||ll - w produce w which satisfy
E - ((w)) = BD
2r
+
K
VK
Convergence result of accelerated SGD (AC-SA) for convex smooth optimization from Lan (2020) (Proposition 4.4).
Lemma 5. Let f Rd - D. be a B-smooth convex function admitting a minimizer w Let g Rd - Rd be an unbiased gradient oracle of f with o² bounded variance. Then running accelerated SGD (termed AC-SA in Lan, 2020) for K steps, initialized at w1 E Rd and with parameters a, = 1+1
2 and Yt = yt where
3D2
min
4B
|4r2 1)2
and D 2 ||w] - wl produce w which satisfy
4BD²
4mD
+1)
V3K
Convergence result of SGD for convex Lipschitz optimization from Lan (2020) (Theorem 4.1, Equation 4.1.12).
Lemma 6. Let W c. Rd be conver with diameter bounded by D. Let f W R be G-Lipschitz convex function and w* arg min f(w). Let g Rd + Rd be unbiased sub- sub-gradient oracle of f with o² bounded variance. Then rumning projected SGD (termed stochastic mirror descent in Lan, 2020) for K steps, initialized at w E W and with stepsizes y, D/ [(G o²),, produce w which satisfy
2D 2DVG
E[S(W) [(w*)]
S
VK
B. Average Delay is Bounded by Number of Machines
In the arbitrary delay model, it was previously remarked (Koloskova et al., 2022; Feyzmahdavian & Johansson, 2023) that the gradients are produced by constant number machines (the setting Koloskova et al. (2022); Mishchenko al. (2022) considered), the average delay smaller than the number of machines. For completeness we state and prove this property below.
Let di.....dy dr be an arbitrary delay sequence produced by machines. Then the average delay is lower bounded by the number of machines. In particular, $ ΣT_ di s M
Lemma
Proof. For any m E [M], let Sm = (km.1, km.2..... km.n(m) be the rounds where the gradient was computed by machine m, where nk) is the total number of gradients produced by machine m. Rearranging the summation of delays and treating
12

---

Faster Stochastic Optimization with Arbitrary Delays via Adaptive Asynchronous Mini-Batchin Batching
km.0 0,
T Σ
n(m)
ni n(m)
de
Σ
km.i
km.
Σ
Km,i Km,i-
[=1
ME
M
E=
MEIM
F=1
T+
Σ
mm.)(m)
ME[M]
As km,nim) # kmd mi(me) if m' (as each step has only single gradient),
T
T
M(T - M 1+))
Σ
d -T
Σ
km.n(m)
-
Σ
-=
2
MEIM|
2MT M M 27
$ T(MM
2
Dividing both sides by T we conclude -E d 3-MM
C. Best Quantile Bound Arbitrarily Improves over Average and Median
As we establish in Theorem and Corollary 2, given bound of the median delay (or any other quantile), it possible to convert classical optimization methods to asynchronous optimization methods black-box manner. Note that by simple application of Markov's inequality, the median delay is bounded by twice the average delay, as Tmed S Tavg/ Pr(dd Tmed) s Taag where is chosen uniformly random. On the other hand, for the delay sequence d, 1[r T/2 1] 1), have Tavg = (27)) and significantly smaller Tmed = O.
A natural question is whether we can improve beyond the average or median delay dependency. To gain intuition consider the following simple delay sequence, which is produced by performing asynchronous optimization with M machines where one machine times as fast for n steps,
d = 0
if S n
otherwise.
In the B-smooth non-convex case, assuming o = 0, it is straightforward to see that the best approach is to perform SGD and ignore all stale gradients, as they do not provide additional information, achieving convergence rate of
o
(B(((w)) n
( 12 n+M--
o BC (B((W)))) ( T
of (B(((w)) -ft q7
where q = -+ the maximal quantile of the gradients with zero delay. case y < 1. the median and average delays n
will be (2(1),, and dependence on them will lead to far worse guarantees. To that end, we would like result more robust to the delay distribution which better ignores outliers.
D. Lower Bound for "Vanilla" Fixed Stepsize Asynchronous SGD
The following theorem shows that, without further assumptions or modifications to the algorithm, the performance of vanilla (non-adaptive) asynchronous SGD with fixed stepsize must degrade according to the maximal delay, similarly to the upper bound of Stich & Karimireddy (2020). In particular, assuming Tmax o(T), the delay sequence defined Theorem satisfies Tavg = o( Tmux). The result may seem inconsistent with the upper bound of asynchronous SGD from Koloskova et al. (2022), which degrades as Tavg Tmax- However, this is not the case, their definition of average delay includes "imaginary" delays from machines that return results after round T, rather than accounting solely for the observed sequence.
Theorem 4. For any T E N, Timx E [T 2] and w1 E R, there exists delay sequence of length T with maximal delay Tmax and average delay bounded by 2 TT, which can be produced by Tmax + I machines, and a B-smooth convex function f: :: IR + It admitting a minimizer w*, such that for any n > B(l+Tmu) the iterates T -teps asynchronous SGD with the delay sequence and deterministic gradients, initialized at w with stepsize n7, satisfy
6
T |/ f(w))12
4(1+ Tmax B( (Wf(w)) ))
T
T
13

---

Faster Stochastic Optimization with Arbitrary Delays via Adaptive Asynchronous Mini-Ban Batching
and
(1 + Tmlx) - w=
T Σ s(w) - f(w*) 2
Note that the above theorem holds for 17 6/B(1 Tmax)) For smaller value of 7, the worst-case convergence guarantee of standard SGD (even without noise delays) is (2((1 + B/T), which is also tight in the worst case. We cover this case in Appendix D.I.
Proof of Theorrm 4. Let f(w) - [[wlß which f-smooth and convex function admitting a minimizer w* 0. We consider the following delay sequence,
1 1-1 if $ Tmax + 1;
d,
otherwise.
Note that the maximal delay is Tmax and
1 Tau++
(Tmax + T)Tax
mmax
Tavg T
2T
T
In addition, this sequence can be made with Tmax machines, where the first Tmax I rounds are produced by different
machines and the rest are produced by the last. The trajectory of the first mmax 2 iterates can be written
Wi w1 71 I)V w1 np(11 1)).
Thus, the average squared gradient norm can be bounded by
B² Taax
Σ V [w()))
Σ
(1-np(1 1))?
I= 22+2
Note that treat Tmax modification as max + 2Tmax. As
number, this is done for simplicity and the odd case affects only slight constant
Bi Tima +1y+ for 2 Tmax/2 2, nB((1 1) 2 3 and
1 I IV
1 ?
+2
Σ
Σ
4
T 1=1
T
Tima /2+2
1/21 (Tmax + 1)
2
T
By a standard application smoothness, f(w)) - f(w*) S &fllwi - 1=1 Hence,
(Tmax T Σ [lf(w)))12 4B(s(w1) ((w*)) (Tmax 1)
And for the second inequality, as f(w,) f(w*) = =111w,11= 2B || /lV[((
Σ -
- 1
2BT Σ | (ww))l
T
B||wi w (Tmax + +)
T
14

---

Faster Stochastic Optimization with Arbitrary Delays via Adaptive Asynchronous Mini-Batee Batching
D.I. Lower Bound for "Vanilla" Asynchronous SGD with Small Fixed Stepsize
In Theorem 4 provided a lower bound for f-smooth optimization using fixed stepsize asynchronous SGD with stepsize
n |I++mm where Tmax is the maximal delay of the arbitrary delay sequence. Next, complement this result with simple lower bound for any delay sequence (which holds in particular for the centralized case by setting d, 0 for all 6 the same lower bound of Theorem 4 r e [T]), that has an inverse dependence on the stepsize, and yields for 1j $ f(1+T
(up to constant factors).
Theorem 5. For any T E N, E R. B O and O, there exists B-smooth convex function f R RR admitting minimizer w* E I], such that for any delay sequence di....,dy .r. the iterates of I steps asynchronous (SJGD with the delay sequence and deterministic gradients, initialized at and with stepsize 1, satisfy
B(((w))- f(w)))
Wf(w))11
T E
2 2max 1, 2Bn77
and
1 T Σ (ww))-(ww) T
B|| w| w=11 8 max (1, 2,n7T"
Proof. Without loss of generality, we will assume that w1 2 0 and let w* -1 (otherwise, use w* and similar argument will hold). Let f(w) =llw w= for e min (2r/))) which is B-smooth and convex function admitting minimizer w*.
We will prove by induction that { (w) w s (w, - w s (wl - w)) for all r E [7]. The base case t = 1 is immediate since W1 w* > 0. At step 1,
W/+1 W, v/ f(:-dd) w1 - Vf(Ws-d,) w1 nE Σ
(Ws-d, w3)
x=1
Hence, by the induction assumption and the definition of e,
1 W7+1 w (wi )* - pee(ww-w>> 2 (w] - w)).
On the other hand, ws-d, w* 2 {(11 w*) by the induction,
(W++1- - (W1 w*) m/ >
(Wa-d, w S (W1 w
1=1
concluding the proof by induction. Hence,
2 T w. 11
2 T
Wi w* 11= B(f(wi)- - ((w*))
Σ V (w:))1
Σ
Σ
T 1
47
2 2max 2max(1,2 (1, 1,28177}
ml
1=
and
T f(w,) - ) fw:))
T ww
T
Bll 11
Σ
I|i - wf
2T [=1
8T
max (1 (1, 2,B
[=1
1=1
E. Additional Results using Algorithm 2
Following are additional applications Algorithm 2 using projected SGD in the convex non-smooth and SGD in the convex smooth setting. Their proofs follow.
15

---

Faster Stochastic Optimization with Arbitrary Delays via Adaptive Asynchronous Mini-Batchie
Theorem 6. Let W Rd be convex with diameter bounded by D, f W R. be G-Lipschitz convex, function and w* arg wew fw)). Let g W R be an unbiased gradient oracle of f with o--bounded variance, T N and W1 E W. Let A(K be stochastic mirror descent initialized at with stepsize
D
Y1
(G2 +
where
= max
1,
G2
Let W (W1,-. (....... W1) be the oulpuls of A by running Algorithm 2 for T N asynchronous sleps with parameters A,
K; 2 and Bi B. Then
DG 3 + Do V48
[(w))] s
inf gE(0.1]
VqT
where w W, if W is not empty, and w1 otherwise.
Theorem 7. Let f Rd - R. be a B-smooth convex function admitting minimizer w Rd - Rd be an unbiased gradient oracle of f with bo-boddded variance, T N and Rd,, Let A(K) be SGD initialized at wi with stepsize Yk B. Let W = (W1..... W1) be the oulputs of A by running Algorithm for T e N asynchronous steps with parameters A.
o²Ki
2
and
B₁ max
Then
12(1 + 2T2)
or 288
E[ f(w*)]
inf qE(0,1)
qT
Nq
where w = W if W is not empty, and w1 otherwise.
E.1. Proof of Theorem 6
If W is empty, then T < B (as Ti and the condition 1=1(") S d, is always satisfied). Hence, as T 2 1,
T 0²
62
and using the Lipschitz and diameter assumptions,
Do vT
Do
- - f(=")(ww=+))) f(w1) f(w") DG
VqT
for all q (0, 1]. We proceed to the case where W is not empty. Let (0. 1]. By Lemma 2,
qi' < 2(B + K1-1-
If 1,
D² +02/B)
8(1 2T, 2Tg) D2
qT 2211 2T,
K, <
ql
If B max(1,7y), or > G, B [o2 and
D² + +D/BB)
8B2 0² o2/B)
24D20²
qT S 4BKr,
5
K1
qT
qT
16

---

Faster Stochastic Optimization with Arbitrary Delays via Adaptive Asynchronous Mini-Batching
(7) where the last inequality follows by BG² < 20 We are left with applying Lemma To that end note that & is the average of B i.i.d. unbiased estimations of f ). and by the linearity of the variance has variance bounded by o² /B. Thus, our selection of parameters enable us to use Lemma 6 and establish that
[ 2D DD
32 2nq) + V96
VK,
VqT
As this holds for any (0, l],
2Tg) Do VqT
- ([
s inf
qE(0.1]
E.2. Proof Theorem?
W is empty, then 7 < Bj (as Ti I and the condition
-=110 11 d, is always satisfied), Hence, as 7 2
o²
7
B²D22
and from smoothness,
BD2
oD
rD
f(w) <
2
2VT
2vqT
for all q e (0. 1]. We proceed to the case where W is not empty. Let q (0. 1]. By Lemma 2,
qi' < ((81+1 K1111
If Bia s Tg)
1
4(1 4Tg)
qi 2(1+ 21
K,
qT
If B,41 > max(1,Tg).
802 i+1 B²D2
I o v3
qi s K S
K1
BD
We are left with applying Lemma 4. To that end note that 8 is the average of B, i.i.d. unbiased estimations of ( (1) and by the linearity of the variance has variance bounded by o²/B,, Thus, our selection of parameters enable us to use Lemma 5 and establish that
BD2 +
20D 3BD2 K, VB,K,
12 (T,++2,)BB*
o D2888
E(s(w))
S S
K,
qT
VqT
As this holds for any E 1].
12(1 + BD2
о DDV288
- f(w")] inf
qE(0.1]
qT
VqT
F. Proofs of Section 4
F.1. Proof of Lemma 2
i [1 + 1] and & E [K,]. Let n(i, k) be the number of rounds with delay less or equal at times 1 S <
k41 for
(0)
K; and 1 S < 1 ((+1) for Kj. Assume by contradiction that n(i, k) B, Ty. and let (a....., ap, an be the
17

---

Faster Stochastic Optimization with Arbitrary Delays via Adaptive Asynchronous Mini-Batching
rounds of the k) iteration with da; Tq ordered in increasing order. For any i Ty. as the sequence is non-decreasing and di 2 xx
a: 1--1 2 aj - a 2 Tq 2 day
which means that the inner "if"" condition is satisfied and contradicts the condition of the while loop, b s B, since there is at
least B + rounds with > Tg. Thus, n(i, k) s B; + Tq for all E [ 1] and & [K]. As each B, + Tq rounds with delay less or equal zy during the i'th iteration must account a response to A, and as we have least [47] such rounds total,
7+1 qi
(B Tq).
i=1
otherwise wy will not be the last produced wy. Hence, as (Bi), is non-decreasing and (Ki); is geometric series,
[+1
qi (Bi-1 Tq)
Σ
K₁ 2( K1+1.
F.2. Proof of Theorem 3
For completeness, we restate each part of Theorem as full theorem and provide the proofs.
Theorem 8 (Theorem 3 (i)). Let f R - R be B-smooth function lower bounded by f*, g R Rd an unbiased gradient oracle of f with o² bouudddd variance, E and w1 E Rd, Let A(K) be SGD initialized at w1 with stepsize B Let W = (W1...., W1) be the outputs of A by running Algorithum 2 for T E N asynchronous rounds with parameters A,
K; 2 and
B; = max (1.
2BF
for some F 2 f(w)) f*. Then
24(1 + 2Tg
2Br
E [[IV/[[]]
inf qE(0,1)
+
q7'
VqT
where W Wy is W is not empty, and otherwise.
The proof of Theorem 3 (i) is already provided in Section 4.
Theorem 9 (Theorem 3 (ii).. Let f : Rd - R be a B-smooth convex function admitting minimizer w* g Rd - Rd be an unbiased gradient oracle of f with -b-uuddeed variance, T N and w1 Rd. Let A(K) be accelerated SGD initialized 2
at with parameters a, r+T and y, yt where = IB and D 2 ||w w II. Let W = (Wi...., W1) be the outputs of A by running Algorithm 2 for T E N asynchronous rounds with parameters A,
o K2 + 1)2
K, = 2
and
B = =mmax 1,
12
Then
192(1 + )TD2
48 VqT
((w)) inf qE(0.1)
q2T2
where w w if W is not empty, and wi otherwise.
Proof of Theorem 9, If W is empty, then T < Bi (as Ti = and the condition ==1 s / d, is always satisfied). Hence, as T 2 1,
D2
D2
18

---

Faster Stochastic Optimization with Arbitrary Delays via Adaptive Asynchronous Mini-Batchin Batching
and from smoothness,
BD2
rD
rD
f(w) -
2
2VT
2V4T
for all q (0, I]. We proceed to the case where W is empty. Let 9 (0. By Lemma
qi 2(11+ K441.
If By+1 & Tg)
16(1 + 2Ty) 92112
qT s 2(1+
Ki(Ki +1)
K
Bys1 > m
qi' S 414 S
20 (K++1 1)2
1+1
(i(K)+1) S
32/33
40 BD
3B2
BD
We are left with applying Lemma 5. To that end note that 8k is the average of By i.i.d. unbiased estimations of V ()). and by the linearity of the variance has variance bounded by o²/Bi. Thus, our selection of parameters enable us to use Lemma 5 and establish that
k
4BD2
4G
12BD2 K1(K,+1) $
192(1 BDD
48o D
- f(w") 11( V
9²T2
VqT
As this holds for any 4 (0, 1].
192(1 2xg)) 2BD2
48 D) VqT
((
inf gE(0.1)
9212
19


Reviews:
[{"review_id": "TJXNyNxbxH", "reviewer": "Reviewer_A1zA", "summary": "This paper proposes an asynchronous mini-batch black-box algorithm that aggregates asynchronously computed stochastic gradients as input to any stochastic-gradient-type optimization algorithm. In contrast to performing biased update using stale stochastic gradients, the proposed algorithm adaptively aggregates delayed gradients according to the delay length $d_t$. Analysis is provided to demonstrate the effect of batch size $B = \\max \\\\{1, \\bar{\\tau}_q\\\\}$ and its dependence to the delay quantile $\\tau_q$ on the convergence rate for multiple kinds of objective functions. Furthermore, another variant of algorithm that adopts increasing batch size is proposed, suggesting that the increasing batch size would achieve a tighter convergence bound that is optimal over the delay quantile $\\tau_q$.", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the feedback. Due to space constraints, we provide our responses to the main points below.\n\n> “What does “Play $w_t=\\tilde{w}_k$” means?”\n\nIn the asynchronous paradigm we consider, at each step $t$ the algorithm plays a point $w_t$ (essentially the current model at time $t$). This line means that the point the algorithm selects is $\\tilde{w}_k$.\n\n> “Since $w_{t-d_t}=\\tilde{w}_k$, at the iteration $k$-th of algorithm $A$…always receives a mini-batch…how the asynchrony in the proposed algorithm can achieve acceleration against synchronous SGD…”\n\nConsider a scenario with $M$ workers, where one is significantly slower while the remaining workers are fast (e.g., three times as fast). Synchronous mini-batch SGD with batch size $M$ would wait for the slow worker at each iteration. In contrast, our algorithm with batch size $M$ leverages the fast workers to compute the one missing gradient, achieving a 1.5x speedup.\n\n> “Explanation regarding the above ambiguities shall be included…”\n\nWe will provide a more detailed version of the proof of Lemma 1 in the final version. Throughout the proofs, we treated the quantile delays ($\\tau_q$) as integers, which can be done without loss of generality because (A) the delays are all integers, so $\\lfloor\\tau_q\\rfloor$ is also a $q$-quantile, and (B) smaller delay is better. So, we can always use $\\lfloor \\tau_q \\rfloor$ instead of $\\tau_q$. We will state it more clearly in the final version---thanks for pointing this out. Below are more details on the specific transitions the review mentioned.\n\n> “...how $a_i-a_1\\leq\\tau_q$ is obtained in line 310.”\n\nAs the integer sequence $a_1,..,a_{n(k)}$ is increasing, $a_i\\geq a_1+(i-1)$. As $i>\\tau_q$, $i\\geq \\tau_q+1$ (these are integers), so $a_i\\geq a_1+\\tau_q$.\n\n> “...how the argument \"since there are at least $B+1$ rounds with $i>\\tau_q$.\" is obtained in line 314.”\n\nWe assumed by contradiction that $n(k)>B+\\tau_q$, where $n(k)$ is the number of rounds with delay less or equal $\\tau_q$. Working with integers, $n(k)\\geq B+\\tau_q+1$. So the last $B+1$ of these will have indices $i>\\tau_q$.\n\n> “By the notation $\\mathcal{A}(\\sigma,K)$, I assume algorithm $A$ queried and received $K$ stochastic gradients…how do we introduce another $K’$...”\n\nWe differentiate between $K$, which is the number of updates $A$ needs to produce an output, and $K’$, the actual number of updates received. $K’$ cannot be larger than $K$ due to the loop structure, but we need to prove that $T$ asynchronous steps are enough to produce $K$ updates to $A$, which is ensured by proving that $K’\\geq K$.\n\n> “...how the second inequality in line 324 is obtained.”\n\nThe second inequality is a part of Lemma 1. What we prove in the Lemma is that if this inequality holds, then $K’\\geq K$.\n\n> “I suggest the authors to provide…proof for the case of smaller $\\eta$...as claimed in the paragraph of line 390.”\n\nWe will include the proof for this case and are happy to provide further elaboration if requested by the reviewer.\n\n> “The claim of this paper would be more convincing if the authors can present numerical experiments…”\n\nOur work is primarily theoretical, focusing on providing improved convergence guarantees for asynchronous stochastic optimization and improving our understanding of this fundamental problem. That said, we agree with the reviewer that a numerical evaluation comparing our methods to classical asynchronous algorithms can further strengthen our results. Since the rebuttal period this year is extremely short, we will only be able to complete this for the final version. Specifically, our plan is to implement a simulated environment of delays, and to conduct a small-scale experiment with synthetic data, allowing for a larger number of simulated machines, as well as a larger experiment (with a deep NN on a standard benchmark) with a smaller number of simulated machines.\n\n> “The proof of Theorem 4 considered the mini-batching algorithm, which is not the vanilla asynchronous SGD algorithm [Stich & Karimireddy, 2020] [Arjevani et al., 2020] as claimed in the first paragraph of Section 5.”\n\nThe vanilla asynchronous SGD algorithm is SGD which performs update steps in an asynchronous manner. The asynchronous SGD algorithm presented in [Stich & Karimireddy, 2020] is the instance of vanilla asynchronous SGD with constant delay. To accommodate arbitrary delays, previous works (e.g., Mishchenko et al., 2022) extended asynchronous SGD to general delays. Theorem 4 follows the definition of asynchronous SGD with arbitrary delays.\n\n> “According to Table 1…for large enough $T$…$O(\\sigma/\\sqrt{qT})$ would be slower than the existing $O(\\sigma/\\sqrt{T})$ rate….”\n\nAs we remark in lines 111-113 and in Section C, for $q=0.5$, our new rates are of the same order or better than those of previous work. The reason is that $\\tau_q\\leq 2\\tau_{avg}$ when $q=0.5$. As the median is a more robust quantity to outliers than the average, our bounds are preferable.", "claims_and_evidence": "As discussed below under \"Theoretical Claims\".", "methods_and_evaluation_criteria": "# Regarding Algorithm 1\n- What does \"Play $w_t = \\tilde{w}_k$\" means? \n- Since $w_{t-d_t} = \\tilde{w}_k$, at the iteration $k$-th of algorithm $\\mathcal{A}$, $\\mathcal{A}$ always receives a mini-batch of stochastic gradients evaluated on $\\tilde{w}_k$. From here, for simplicity consider when $\\mathcal{A}$ is SGD, it seems that Algorithm 1 is only a synchronous SGD that waits for $B$ mini-batches from multiple workers at every iteration. I found it confusing as it differs from the usual asynchronous gradient paradigm. It would be more clear if the authors could expand on the discussion of how the asynchrony in the proposed algorithm can achieve acceleration against synchronous SGD, e.g., in consideration of the larger batch size $B = \\max \\\\{ 1, \\bar{\\tau}_q \\\\}$ used in Algorithm 1.", "theoretical_claims": "# Regarding the proof of Lemma 1\n- It is not intuitive to see how $a_i - a_1 \\ge \\tau_q$ is obtained in line 310. \n- Similarly, it is not clear how the argument \"since there are at least $B+1$ rounds with $i > \\tau_q$.\" is obtained in line 314.\n- By the notation $\\mathcal{A}(\\sigma, K)$, I assume algorithm $\\mathcal{A}$ queried and received $K$ stochastic gradients, as stated in Algorithm 1 because $k$ the iteration counter increases only after line 266. Therefore, it is not clear how do we introduce another $K'$ in line 300 and what is the meaning behind assuming $K' < K$.\n- It is not explained how the second inequality in line 324 is obtained.\n\nExplanation regarding the above ambiguities shall be included in the proof.\n\n# Regarding Theorem 4\n- The proof of Theorem 4 considered the mini-batching algorithm, which is not the vanilla asynchronous SGD algorithm [[Stich & Karimireddy, 2020]](https://jmlr.csail.mit.edu/papers/volume21/19-748/19-748.pdf) [[Arjevani et al., 2020]](https://proceedings.mlr.press/v117/arjevani20a/arjevani20a.pdf) as claimed in the first paragraph of Section 5.\n- I suggest the authors to provide references / proof for the case of smaller $\\eta$, i.e., when $\\eta \\leq 6 / \\beta (1 + \\tau_{\\rm max})$, as claimed in the paragraph of line 390.", "experimental_designs_or_analyses": "- This paper lacks numerical experiments.\n- It is not shown how to choose the step size $\\beta$ and batch size sequence $B_i$ in practice. For instance, in order to achieve the optimal upper bound suggested in Theorem 3, one must know the optimal $q^\\star$ and correspondingly $\\tau_{q^\\star}$ in order to choose $B_i, K_i$ that satisfy the conditions required in Theorem 3.", "relation_to_broader_scientific_literature": "The proposed algorithm is orthogonal to classical asynchronous gradient algorithm such as [[Arjevani et al., 2020]](https://proceedings.mlr.press/v117/arjevani20a/arjevani20a.pdf), in the sense that the proposed algorithm avoids applying biased gradient steps by filtering and buffering the delayed gradients.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "As discussed below.", "other_comments_or_suggestions": "- The claim of this paper would be more convincing if the authors can present numerical experiments on extremely large $\\tau_{\\rm avg}$ and show the benefit of Algorithm 1 against classical asynchronous algorithm such as [[Arjevani et al., 2020]](https://proceedings.mlr.press/v117/arjevani20a/arjevani20a.pdf).\n- According to Table 1 in the non-convex setting, for large enough $T$ such that the $\\mathcal{O}(1/\\sqrt{T})$ term dominates the error bound, the proposed convergence rate $\\mathcal{O}(\\sigma / \\sqrt{qT})$ would be slower than the existing $\\mathcal{O}(\\sigma / \\sqrt{T})$ rate for $q \\in [0,1]$.", "questions_for_authors": "No.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ucv77rfC2j", "reviewer": "Reviewer_Tmk7", "summary": "The authors consider the problem of stochastic optimization with delays. Concretely, they minimize an objective function $f:\\mathcal{W} \\to\\mathbb{R}$ for a convex set $\\mathcal{W} \\subseteq \\mathbb{R}^d$. They consider access to a stochastic unbiased gradient oracle with variance $\\sigma^2$. Additionally, at each round $t$, the gradient oracle provides the stochastic gradient at $w_{t-d_t}$ where the delay sequence $d_t$ can be arbitrary. The goal is to obtain optimization algorithms that obtain best convergence rates after $T$ rounds in terms of the delay distribution.\n\n\nThe authors consider arbitrary delay distribution, with no assumptions on the delay, while existing works make several simplifying assumptions on delay distribution (fixed delay, bounded delay, fixed delay per machine or knowledge of delay distributions).\n\n\nUnder arbitrary delays, the authors provide a method (Algorithm 1), where given a black-box algorithm for stochastic optimization, given an upper bound $\\bar{\\tau}_q \\geq \\tau_q$, they select the corresponding batch size $B = \\max (1,\\bar{\\tau}_q )$ and the number of iterations for the algorithm $K = qT / (1 + 2\\bar{\\tau}_q ) $. \n\nUsing this they run the black-box algorithm, to obtain the best possible convergence rates in terms of $\\tau_q$ for smooth non-convex, smooth convex, and non-smooth convex objectives. See Table 1 for the exact rates. Here, $q\\in (0,1)$ denotes the quantile and $\\tau_q$ denotes the delay quantile values. Crucially, these are much better than existing works that can only do this for $\\tau_{avg}$ or the average delay.\n\n\nFurther, to eliminate the dependence on knowledge of the upper bound of $\\tau_{q}$, they use a doubling trick in Algorithm 2, to run several copies of Algorithm 1, with geometrically increasing number of rounds in each copy and increasing batch-sizes determined by the corresponding function class. Again, applying this to all function classes above, they obtain an $\\inf_{q\\in (0,1)}$ for their convergence rates achieving the best possible(Theorem 3 and Table 1).\n\n\nFinally, they show that vanilla SGD with fixed step size without modifications or additional assumptions will always incur the maximum delay in Theorem 4.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the feedback—please see below our responses to the main points you raised.\n\n> “The authors provided **no experiments**. As the goal of this paper is to propose an algorithm, I request the authors to provide some experiments for their algorithm in practice.”\n\nOur work is primarily theoretical, focusing on providing improved convergence guarantees for asynchronous stochastic optimization and improving our understanding of this fundamental problem. That said, we agree with the reviewer that a numerical evaluation comparing our methods to classical asynchronous algorithms can further strengthen our results. Since the rebuttal period this year is extremely short, we will only be able to complete this for the final version. Specifically, in agreement with your suggestions, our plan is to implement a simulated environment of delays, and to conduct a small-scale experiment with synthetic data, allowing for a larger number of simulated machines, as well as a larger experiment (with a deep NN on a standard benchmark) with a smaller number of simulated machines.\n\n> “One issue with several stochastic optimization algorithms, even those in (Lan 2020), are that the optimal step sizes depend on problem parameters like smoothness, or suboptimality gap. So, when implementing algorithms in practice, especially on NNs, one has to resort to tuning. In the case of Algorithm 2 here, the batch size $B_i$ also depend on problem parameters, so the authors should show if a tuning procedure alongwith some growth conditions on $B_i$ is sufficient in practice. ”\n\nCompared to Algorithm 1, Algorithm 2 performs an outer sweep over different batch sizes. This addition is made to identify the optimal batch size, as the number of non-stale updates is unknown without prior knowledge of the delays. In a tuning scenario, one can directly tune the batch size, resulting in a simpler asynchronous algorithm that aggregates gradients for a mini-batch synchronous algorithm (essentially Algorithm 1 with a tuned batch size). We will include your suggestion in the experiments we will complete for the final version.\n\n> “**Lower bound**: I see that (Tyurin 2024) has a lower bound for delay distributions in their Theorem 1. Does the lower bound hold here, as this does not seem to be a zero-respecting algorithm. Also, I understand that it is concurrent work, but I request the authors to provide a more detailed comparison.”\n\nThe lower bound from the concurrent work (Tyurin 2024) applies, in their specific delay model,  to the algorithms we discuss. The main distinction between our paper and (Tyurin 2024) lies in the computational model: they introduce a framework that deviates significantly from the arbitrary delay models considered in prior work (e.g., Cohen et al., 2021; Mishchenko et al., 2022; Koloskova et al., 2022). While their model is general, it is also somewhat abstract, resulting in somewhat more complex guarantees compared to the (arguably) more intuitive quantile-based convergence guarantees we provide. On the other hand, (Tyurin 2024) also establishes the optimality of filtering stale gradient technique with a well tuned batch size by proving a lower bound for zero-respecting first-order algorithms. We will include a more detailed comparison in the revision.\n\n> “**Delay distributions independent of stochastic gradients**: In Line 188-189, the authors assume that delay distributions are independent of stochastic gradients. Are there cases in distributed optimization where this is violated, for instance where machines with a bad delay and gradient noise, but the average gradient noise over all machine is small? Also, do existing works like (Tyurin & Richtarik 2023) handle these cases?”\n\nThe scenario you refer to falls within the setting of asynchronous optimization with heterogeneous data, where different workers have access to different samples. Some works address this setting but require additional assumptions, such as fixed delays per machine (Theorem A.4 of Tyurin & Richtarik, 2023) or certain distributional assumptions (Assumption 2 of Mishchenko et al., 2022). Supporting this case without additional assumptions is not feasible, as the data on slower machines must be accessed sufficiently many times for effective minimization. This could indeed be a valuable extension, but one that probably deserves a separate study.\n\nThanks for pointing out typos and further suggestions.", "claims_and_evidence": "- **Core-idea for black-box conversion** : The core-idea behind their Algorithm 1 is to construct a mini-batch of $B$ gradients in an asynchronous fashion. They run $K$ steps of the algorithm with batch size $B$. In each step, they wait until $B$ stochastic gradients have been obtained to update the model. By choosing $B$ carefully, they can control both the number of steps and the delay in steps in terms of $\\tau_q$. They state this in Lemma 1 and provide the proof just after it.\n- **Core-idea for anytime algorithm**: To extend Algorithm 1 to Algorithm 2, they use the doubling trick on number of rounds $K_i$ for the $i^{th}$ instantiation of Algorithm 1. This allows them to obtain a similar bound on the batch size $B_i$, number of steps of black-box algorithm $K_i$, number of rounds $T$ and delay quantile $\\tau_q$ for any $q\\in (0,1)$ in Lemma 2. The proof is simple but insightful. To go from here to the convergence rates for any function class, they plug in the batch size in any convergence rate, then find its optimal value to recover the best possible rate for the function class in terms.\n- **Lower-bound and additional results**: The lower bound  as well as the suboptimality of average delay versus that of best case quantile are shown by constructing arbitrarily bad delay distributions.", "methods_and_evaluation_criteria": "The authors provided **no experiments**. As the goal of this paper is to propose an algorithm, I request the authors to provide some experiments for their algorithm in practice. Ideally one synthetic example(quadratics with gaussian noise) and 1 real world neural network example on any bad delay distribution where $\\tau_{avg}/\\tau_{median}$ is large would do. \n\nOne issue with several stochastic optimization algorithms, even those in (Lan 2020), are that the optimal step sizes depend on problem parameters like smoothness, or suboptimality gap. So, when implementing algorithms in practice, especially on NNs, one has to resort to tuning. In the case of Algorithm 2 here, the batch size $B_i$ also depend on problem parameters, so the authors should show if a tuning procedure alongwith some growth conditions on $B_i$ is sufficient in practice. For instance, for non-convex smooth objectives, the authors can choose to find the value of $\\frac{\\sigma^2}{2\\beta F}$ by tuning.", "theoretical_claims": "- All the theoretical claims are correct and in fact have simple proofs that the authors have explained very clearly. \n- I would like to add that both Algorithm 1 and 2 are quite simple and can be applied to any black-box algorithm, which makes the method quite novel and insightful.", "experimental_designs_or_analyses": "See Methods and Evaluation Criteria.", "relation_to_broader_scientific_literature": "The key contribution is to provide a generic recipe for conversion of arbitrary optimization algorithms to handle arbitrary delays by mini-batching. The insight is quite novel, and turns a hard problem, that people can solve for specific delay distributions using complicated algorithms, into a simple one.", "essential_references_not_discussed": "I think the authors might want to motivate the doubling trick as it has been used previously in online learning for anytime algorithms, eg -(van Erven et al 2011). Apart from that the literature review is pretty thorough.\n\n**References** \n- (van Erven et al 2011) Adaptive Hedging. NeurIPS.", "other_strengths_and_weaknesses": "None.", "other_comments_or_suggestions": "- **Presentation**: I think certain parts of the main paper can be moved to the appendix and an experiment section and conclusion can be included. For instance, in Line 376-382 right column, is a standard property of smoothness and just a reference for it, like Nesterov's book can be provided. Also, the proof for the lower bound can be moved to the appendix. Apart from this, footnote 2 on page 4 is incomplete, there are two \"the\" in the first line of Page 8 and, on the sample page, \"Lemma 3\" is applied, but it hasn't been defined what this Lemma states.", "questions_for_authors": "- **Lower bound**: I see that (Tyurin 2024) has a lower bound for delay distributions in their Theorem 1. Does the lower bound hold here, as this does not seem to be a zero-respecting algorithm. Also, I understand that it is concurrent work, but I request the authors to provide a more detailed comparison.\n- **Delay distributions independent of stochastic gradients**: In Line 188-189, the authors assume that delay distributions are independent of stochastic gradients. Are there cases in distributed optimization where this is violated, for instance where machines with a bad delay and gradient noise, but the average gradient noise over all machine is small? Also, do existing works like (Tyurin \\& Richtarik 2023) handle these cases?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1bJgJgAVpR", "reviewer": "Reviewer_d4yS", "summary": "N/A", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback and for your transparency regarding your familiarity with the field in relation to the review.\n\n> “The algorithms are poorly written, to the point of being nearly incomprehensible.”\n\nThe algorithms aggregate gradients for mini-batching while filtering stale ones based on the delay. Algorithm 2 employs an additional outer loop to determine the optimal batch size, which is unknown in advance, using the standard doubling technique.\n\n> “It seems quite difficult to claim an acceleration in convergence without demonstrating it through a simulation study.”\n\nAccelerated SGD and accelerated rates are standard terms associated with Nesterov’s seminal accelerated gradient method and its stochastic variants, which achieve convergence rates of $O(1/T^2 + \\sigma / \\sqrt{T})$, without necessarily a connection to empirical performance.", "claims_and_evidence": "N/A", "methods_and_evaluation_criteria": "N/A", "theoretical_claims": "N/A", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "N/A", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "I do not believe I am sufficiently qualified to review this paper. However, I can make two observations:\n\nThe algorithms are poorly written, to the point of being nearly incomprehensible. It seems quite difficult to claim an acceleration in convergence without demonstrating it through a simulation study.\n\nConcerning the rate, since I am not competent, I'll follow the other reviewers' opinions.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "4bgf7xZYT1", "reviewer": "Reviewer_P5Nu", "summary": "This paper studies the convergence of asynchronous stochastic methods, and the key differences with the literature include 1) a relatively general algorithm framework; 2) a new model/characterization of the delays, which, compared to delay models like maximum/average delay, can characterize the delays better. They derive convergence results in terms of their delay model, and show the advantage through comparison with the literature.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the review and strong support! Please see below our responses to the main points you raised.\n\n> “I would expect a theoretical bound $\\bar{\\tau}_q$ on $\\tau_q$. This is because that $\\bar{\\tau}_q$ is used to determine $B$ in Algorithm 1, while $B$ may affect $\\tau_q$. Therefore, without a theoretical bound, $\\bar{\\tau}_q$ may be difficult to determine.”\n\n$\\tau_q$ may range from $0$ to $\\Omega(T)$, depending on the adversary determining the delays, as we do not impose any assumptions on their distribution. Consequently, Algorithm 1 requires external knowledge ($\\bar{\\tau}_q$) about the observed delays. This is analogous to the use of the average delay (or an upper bound on it) in previous work, except that quantiles are less sensitive to outliers.\n\n> “The adaptivity result in Theorem 3 is impressive, but I still don't understand how this adaptivity is achieved. I would expect the authors to explain more.”\n\nThe somewhat surprising adaptivity stems from two key components. First, (synchronous) SGD can be used with a large batch size—determined by problem parameters—with minimal degradation in performance, even though the number of update steps is reduced, as long as the noise term dominates the error. Second, the sweep of batch sizes bypasses the discrepancy between the number of asynchronous updates that are not filtered (which is unknown) and the number of updates to $\\mathcal{A}$. This doubling trick, at the cost of a small constant, enables us to “simulate” knowledge of the number of updates $\\mathcal{A}$ will receive.\n\n> “Does Theorem 1 allow for the same parameter range of the algorithm $\\mathcal{A}(\\sigma,K)$? I ask this question because many methods such as delayed gradient descent requires the step-size to be inversely proportional to the maximum delay to guarantee convergence.”\n\nThis is a good distinction. There are no constraints on the parameter range of $\\mathcal{A}$ that stem from the asynchronous nature of the problem. The only effect of asynchronous gradients on $\\mathcal{A}$ is the number of update steps, which is unknown in advance and thus requires a bound $\\bar{\\tau}_q$ or a batch size sweep.\n\nThank you for pointing out additional relevant works. We will expand the literature review to include these settings in the final version.", "claims_and_evidence": "Yes, the claims are supported by their theory.", "methods_and_evaluation_criteria": "Didn't propose any new method.", "theoretical_claims": "No.", "experimental_designs_or_analyses": "No experiments.", "relation_to_broader_scientific_literature": "Limited.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "1. Strength: They consider general asynchronous stochastic methods under a new delay model which is much better than average/maximum delay. They derived strong results, especially Theorem 3 which shows that the algorithm can adapt to $q$ in the $q$-quantile delay model to achieve faster convergence. This is impressive.\n\n2. Weakness: \n\n- I would expect a theoretical bound $\\bar{\\tau}_q$ on $\\tau_q$. This is because that $\\bar{\\tau}_q$ is used to determine $B$ in Algorithm 1, while $B$ may affect $\\tau_q$. Therefore, without a theoretical bound, $\\bar{\\tau}_q$ may be difficult to determine.\n\n- The adaptivity result in Theorem 3 is impressive, but I still don't understand how this adaptivity is achieved. I would expect the authors to explain more.\n\n- The literature review is slightly narrow. Specifically,  many works consider the setting where each agent has a private local cost function, while they are not surveyed. I understand that the focus of this paper does not include that setting, but since this paper considers \"asynchronous\" methods, I would encourage the authors to survey papers in that category. To list a few:\n\n[A] Mishchenko K, Iutzeler F, Malick J, et al, A delay-tolerant proximal-gradient algorithm for distributed learning, International conference on machine learning. PMLR, pp. 3587-3595, 2018.\n\n[B] Soori S, Mishchenko K, Mokhtari A, et al, DAve-QN: A distributed averaged quasi-Newton method with local superlinear convergence rate, International conference on artificial intelligence and statistics. PMLR, pp. 1965-1976, 2020.\n\n[C] Wu X, Magnusson S, Feyzmahdavian H R, et al, Delay-adaptive step-sizes for asynchronous learning, International Conference on Machine Learning, pp. 24093-24113, 2022.\n\nAlso, there are several papers that allow for arbitrary delays or attempt to adapt to the real delay patterns, such as [C] and\n\n[D] Hannah, Robert, Fei Feng, and Wotao Yin. \"A2BCD: Asynchronous acceleration with optimal complexity.\" International Conference on Learning Representations. 2019.", "other_comments_or_suggestions": "I was not aware of some issues pointed out by Reviewer A1zA. Now I have read them and agree with his concern.\n\nHowever, the q-quantile delay model used in this paper is new to me and is a better delay model compared to the \"upper bound of delay\" used in most existing works. Convergence analysis under the new model can help to reflect the effect of delay distribution rather than the maximum delay. Therefore, this paper may have general meaning to the community of asynchronous optimization.", "questions_for_authors": "Does Theorem 1 allow for the same parameter range of the algorithm $A(\\sigma, K)$? I ask this question because many methods such as delayed gradient descent requires the step-size to be inversely proportional to the maximum delay to guarantee convergence.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hsfM54NwtO", "reviewer": "Reviewer_31cT", "summary": "The paper introduces a framework for asynchronous stochastic optimization that leverages quantile delays instead of traditional average delay measures. It presents a black-box conversion that transforms any standard stochastic first-order method into an asynchronous version with only simple analyses of classical methods. It also provides an adaptive procedure for asynchronous non-convex smooth and convex Lipschitz problems that automatically tunes to the best quantile without needing prior knowledge of the delay distribution, yielding accelerated rates.\n\n## update after rebuttal\n\nWhile this is a theoretical paper, numerical validation could have been included in this submission to further demonstrate the usability and robustness of their framework as a 'black-box' conversion to any first-order stochastic methods. Therefore, although the analysis of quantile delays sounds new to me, I will keep my current rating 3 due to the lack of experiments.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the feedback—please see below our responses to the main points you raised.\n\n> “This work is entirely theoretical; the lack of empirical evaluation limits the practical effectiveness and robustness of Algorithms 1 and 2 in real-world scenarios.”\n\nOur work is primarily theoretical, focusing on providing improved convergence guarantees for asynchronous stochastic optimization and improving our understanding of this fundamental problem. That said, we agree with the reviewer that a numerical evaluation comparing our methods to classical asynchronous algorithms can further strengthen our results. Since the rebuttal period this year is extremely short, we will only be able to complete this for the final version. Specifically, our plan is to implement a simulated environment of delays, and to conduct a small-scale experiment with synthetic data, allowing for a larger number of simulated machines, as well as a larger experiment (with a deep NN on a standard benchmark) with a smaller number of simulated machines.\n\n> “Do the authors plan to include empirical validations, and can you share any preliminary results?”\n\nSee comment above.\n\n> “Does the method in this paper cover heavy-tailed or non-stationary delay distributions?”\n\nNote that we actually consider arbitrary sequences of delays that need not come from a probability distribution. Therefore we do support any kind of distribution (as a special case), including heavy tailed and/or non-stationary distributions.\n\nThanks for pointing out additional references and further suggestions.", "claims_and_evidence": "The submission provides rigorous theoretical proofs for convergence rates based on a chosen quantile of delays and accelerated convergence rates for convex smooth problems. In addition, the adaptive variant in Algorithm 2 does not require pre-specified delay bounds and automatically adapts to the best quantile in hindsight.\n\nWhile the theoretical evidence is solid within its assumptions, the paper could further strengthen its theoretical findings with empirical validations or simulation studies for practical benefits.", "methods_and_evaluation_criteria": "The theoretical results in this paper are built heavily upon the theorem with classical stochastic methods from existing works (Lan, 2012, 2020), but it makes sense to modify the existing results to be adapted to asynchronous optimization under arbitrary delays.", "theoretical_claims": "I checked the proofs of main theorems in the main body and didn't observe any technical errors.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "The paper makes the following key contributions to the asynchronous optimization literature:\n- Replace average delay measures with quantile delays for more robust convergence guarantees.\n- Propose a black-box conversion that adapts standard stochastic methods to asynchronous settings.\n- Introduce an adaptive mechanism that tunes automatically to the best quantile delay without prior knowledge.\n- Achieve accelerated convergence rates in convex smooth settings, addressing gaps left by prior works such as Cohen et al. (2021) and Mishchenko et al. (2022), and relating to recent adaptive methods, e.g., Tyurin (2024).", "essential_references_not_discussed": "Some recent related works in stochastic optimization with delayed updates are missing, e.g., [1,2].\n\n[1]. Adibi, A., Dal Fabbro, N., Schenato, L., Kulkarni, S., Poor, H.V., Pappas, G.J., Hassani, H. and Mitra, A. Stochastic approximation with delayed updates: Finite-time rates under markovian sampling. In International Conference on Artificial Intelligence and Statistics (pp. 2746-2754), 2024.\n[2]. Dal Fabbro N, Adibi A, Poor HV, Kulkarni SR, Mitra A, Pappas GJ. Dasa: Delay-adaptive multi-agent stochastic approximation. In IEEE Conference on Decision and Control (pp. 3889-3896). 2024.", "other_strengths_and_weaknesses": "Strengths:\n1. The paper offers a novel perspective by replacing average delay measures with quantile delays, which provides a more robust framework for asynchronous optimization.\n2. It presents detailed and rigorous convergence proofs, extending classical results to handle arbitrary delays and even achieving accelerated rates in convex smooth settings.\n3. The adaptive procedure that automatically tunes to the best quantile without prior knowledge is innovative and has potential for broad applicability in distributed systems.\n\nWeaknesses:\n\n1. This work is entirely theoretical; the lack of empirical evaluation limits the practical effectiveness and robustness of Algorithms 1 and 2 in real-world scenarios.", "other_comments_or_suggestions": "It would be beneficial to discuss potential extensions of the framework to weak smooth conditions (such as [1]), which have wide applications in deep neural network training. In addition, addressing Markovian noise that leads to biased gradient oracles, often seen in reinforcement learning, would be valuable.\n\n[1]. Zhang, J., He, T., Sra, S. and Jadbabaie, A., Why Gradient Clipping Accelerates Training: A Theoretical Justification for Adaptivity. In International Conference on Learning Representations, 2020.", "questions_for_authors": "1. Do the authors plan to include empirical validations, and can you share any preliminary results?\n2. Does the method in this paper cover heavy-tailed or non-stationary delay distributions?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper studies the theoretical convergence rates of mini-batching asynchronous SGD algorithm via a blackbox model. Using a computation model that is similar to that of Rennala SGD, or so called "Fixed Compute Model", the paper first studies the effect of different delay quantiles $q$ on the convergence rate using a similar algorithm to Rennala SGD, then an adaptive method based on an exponentially increasing "epoch" size is studied, which achieves the convergence rate with optimal quantile without knowing $q$ in advance. 

The 5 reviewers have a split in opinions at the initial review. A few reviewers found the proposed analysis to be new and interesting. On the other hand, reviewers also raised issues on the writing  quality, and on the significance of the new results in practice, especially in the absence of any numerical experiments to substantiate the authors' claim. Although the authors promised to include numerical experiments in the next revision, it is too early to judge if the latter can be successful. As such, the opinions have remained split after the rebuttal. 

The paper has thus generated a lot of discussions during the AC Reviewer Discussion phase, which has cleared some confusions during the review phase. In my opinion, while I appreciate the theoretical contributions of proposing a simple scheme to achieve the best rate robust to different quantiles of delay, I found the paper's positioning and presentation to be suboptimal. As it stands, the main contribution for the paper is more of a theoretical one. The current presentation would have misled (some of) its readers into finding its values from the more practical perspective, yet this is one of its main weaknesses. At the moment due to the lack of numerical experiments, it cannot be judged if the proposed algorithms are practical. 

As such, I am recommending a "Weak Accept" for the paper, where it can be included in the proceedings if there is sufficient space in the program.
Decision: Accept (poster)