Asynchronous SGD Beats Minibatch SGD Under Arbitrary Delays
Authors: Konstantin Mishchenko
Francis Bach
Mathieu Even
Blake Woodworth
Venue: NeurIPS 2022 Accept (2022)
Keywords: Stochastic
Convex
Non-convex
Asynchronous
Parallel
Optimization

Abstract: The existing analysis of asynchronous stochastic gradient descent (SGD) degrades dramatically when any delay is large, giving the impression that performance depends primarily on the delay. On the contrary, we prove much better guarantees for the same asynchronous SGD algorithm regardless of the delays in the gradients, depending instead just on the number of parallel devices used to implement the algorithm. Our guarantees are strictly better than the existing analyses, and we also argue that asynchronous SGD outperforms synchronous minibatch SGD in the settings we consider. For our analysis, we introduce a novel recursion based on ``virtual iterates'' and delay-adaptive stepsizes, which allow us to derive state-of-the-art guarantees for both convex and non-convex objectives. 

Asynchronous SGD Beats Minibatch SGD Under Arbitrary Delays
Konstantin Mishchenko
Francis Bach
Mathieu Even
Blake Woodworth
DI ENS, Ecole normale supérieure, Université PSL,, CNRS, INRIA 75005 Paris, France
Abstract
The existing analysis of asynchronous stochastic gradient descent (SGD) degrades dramatically when any delay is large, giving the impression that performance depends primarily the delay. On the contrary, prove much better guarantees for the same asynchronous SGD algorithm regardless the delays in the gradients, depending instead just on the number of parallel devices used to implement the algorithm. Our guarantees are strictly better than the existing analyses, and we also argue that asynchronous SGD outperforms synchronous minibatch SGD in the settings we consider. For our analysis, we introduce a novel recursion based on "virtual iterates" and delay-adaptive stepsizes, which allow us derive state-of-the- art guarantees for both convex and non-convex objectives.
Introduction
We consider solving stochastic optimization problems of the form
(1) which includes machine learning (ML) training objectives, where f(x; {) represents the loss of model parameterized by x on the datum &. Depending on the application, D could represent finite dataset of size n or population distribution. In recent years, such stochastic optimization problems have continued to grow rapidly in size, both in terms of the dimension d of the optimization variable-iss i... the number model parameters in ML-and and in terms of the quantity of data-ie.. the number of samples ....... Sn. ~ 'D being used. With d and n regularly reaching the tens or hundreds of billions, increasingly necessary to use parallel optimization algorithms to handle the large scale and to benefit from data stored on different machines.
minxER" {F(x) Ex {
There are many ways of employing parallelism solve (1), but the most popular approaches in practice are first-order methods based on stochastic gradient descent (SGD). At each iteration, SGD employs stochastic estimates of F to update the parameters as X X 74 V (xx-1ix 1 for an i.i.d. sample - D. Given M machines capable of computing these stochastic gradient estimates V fx: {) in parallel, one approach parallelizing SGD what we call "Minibatch SGD." " This refers to synchronous, parallel algorithm that dispatches the current parameters X;-1 to each of the M machines. waits while they compute and communicate back their gradient estimates
1 g and then takes a minibatch SGD step X = X - 7i 1 ΣM gom This is natural idea with long history [16, 18, 55] and it is commonly used in practice [e.g.. 22]. However, since Minibatch SGD waits for all M of the machines to finish computing their gradient estimates before updating, it proceeds only at the speed of the slowest machine.
3
There are several possible sources of delays: nodes may have heterogeneous hardware with different computational throughputs [23, 25], network latency can slow the communication of gradients, and
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

nodes may even just drop out [45]. Slower "straggler" nodes can arise in many natural parallel settings including training ML models using multiple GPUs [14] or in the cloud, and sensitivity to these stragglers poses serious problem for Minibatch SGD and other similar synchronous algorithms.
1.1 Asynchronous SGD
In this work, consider a different, asynchronous parailel variant of SGD, which we define in Algorithm I and which has a long history [1, 3, 41J. For this method, whenever one of the M machines finishes computing a stochastic gradient, the algorithm immediately uses it take an SGD step, and then that machine begins computing a new stochastic gradient at the newly updated parameters. Because of the asynchronous updates, the other machines are now estimating the gradient at out-of-date parameters, so this algorithm ends up performing updates of the form'
X X 7h f (A)); (k-r(k)),
where rkk is the "ddlay" of the gradient at iteration k which is often much greater than one. Nevertheless, even though the updates are not necessarily well-aligned with the gradient of F at the current parameters, the delays are usually not huge problem in practice [17]. Asynchronous SGD has been particularly popular in reinforcement learning applications [36, 39] and federated learning [13, 43], providing significant speed-ups over Minibatch SGD.
However, the existing theoretical guarantees for Asynchronous SGD are disappointing, and the typical approach to analyzing the algorithm involves assuming that all of the delays are either the same, T(k) = т. or at least upper bounded, r(k) < Tmax [1, 3, 29, 32, 48]. These analyses then show that the number of updates needed to reach accuracy grows linearly with Tmax. which could be very painful. Specifically, suppose we have two parallel workers one fast device that needs just Jus to calculate stochastic gradient, and one slow device that needs 1s. If we use these two machines to implement Asynchronous SGD, the delay of the slow device's 's gradients will be million, because in the second that we wait for the slow machine, the fast one will produce 1 million updates. Consequently, the analysis based on Tmax degrades by a factor of million. But on further reflection, Asynchronous SGD should actually do very well in this scenario, after all, 99. 999999 of the SGD steps taken have gradients with no delay! Even if one update in a million has an enormous delay, it seems fairly clear that few badly oft-of-date gradients should not be enough to ruin the performance of SGD famously robust algorithm.
1.2 Speedup over Minibatch SGD
We will frequently compare Asynchronous SGD to Minibatch SGD (e.g., Table 2), and to make this comparison easier, suppose for simplicity that each worker requires a fixed time of 8m seconds per gradient computation, so in S seconds, each machine computes $/s... stochastic gradients. Importantly, this translates into drastically different numbers of parameter updates for Asynchronous versus Minibatch SGD: the former takes one step per gradient computed, while the latter only takes one step for each gradient from the slowest machine. That is, Asynchronous and Minibatch SGD take
S
min S
K Asyne
and
KMini
9m
1
8m
total steps, respectively. So, it easy to see that Asynchronous SGD takes at least M times more steps than Minibatch SGD in any fixed amount of time, and even more than that when the machines have varying speeds. Soon, we will prove guarantees for Asynchronous SGD that match the guarantee for Minibatch SGD using exactly M times fewer updates, meaning that our Asynchronous SGD guarantees are strictly better than the Minibatch SGD guarantees in terms of runtime.
1.3 Contributions and structure
In this work, we provide a new analysis for Asynchronous SGD, described in Section 2, which we use to prove better convergence guarantees. In contrast to the existing guarantees that are based
AAthoouhh this algorithm is asynchronous the sense that different workers will have un-synchronized iterates, we nevertheless focus on a situation where each SGD step is an atomic/locked update of the parameters X1. This is in contrast to methods using lock-free updates, e.g.. in the style of HOGWILD! [44], where different coordinates of the parameters might be updated and overwritten simultaneously by different workers.

---

Table Comparison of the convergence rates for smooth objectives in terms of K, the total number of stochastic gradients used. For Minibatch SGD with R updates with minibatch size M, it holds K M R. For simplicity, we ignore all logarithmic and constant terms, including the coefficients in front of the exponents. The stated rates are upper bounds on E [x)) in the non-convex case, and E [x)) F*] in the (strongly) convex case.
Method and reference
Convex
Strongly Convex
Non-Convex
Minibatch SGD(M) (M)
M K
pu LM
0²
M K
Gower et al. [21]
+
C
+
+
VK
K
VK
Khaled and Richtárik [26]
Asynchronous SGD
(fixed delay r)
I K
+
a K
K
L
+
d²
T
+
0 VK
K
K
Stich and Karimireddy [48]
Asynchronous SGD
(arbitrary delays)
0
LM
+
M
0
Our work
K
VK
K
K
K
Gower al. [21] analyzed SGD in the strongly convex regime and Khaled and Richtirk [26] in the non convex regime.
on Tmax, ours depend only on the number of workers, M, and show that Asynchronous SGD is better than the Minibatch SGD algorithm described earlier. For Lipschitz-omttinuuus objectives, our results in Section 3 improve over existing Asynchronous and Minibatch SGD guarantees, and the non-smooth, convex setting they are, in fact, minimax optimal. In Section 4, we prove state-of-the-an guarantees for smooth losses, which are summarized in Table 1. We do this by introducing a novel delay-adaptive stepsize schedule " ~ 1/r(k)). The high-level intuition behind proofs is that, although some of the gradients may have very large delay, most of the gradients have delay (M), which is enough for good performance.
1.4 Related work
Asynchronous optimization has long history. In the 1970s, Baudet [8] considered shared-memory asynchronous fixed-point iterations, and an early convergence result for Asynchronous SGD was established by Tsitsiklis et al. [49]. Recent analysis typically relies bounded delays [1, 30, 44, 48]. Sra et al. [46] slightly relax this to random delays with bounded expectation. Zhou et al. [54] allowed delays to grow over time, but only show asymptotic convergence. Some algorithms try to adapt to the delays, but even these are not proven to perform well under arbitrary delays [35, 53]. For more examples of stochastic asynchronous algorithms, we refer readers to the surveys by Assran al.
[6]. Ben-Nun and Hoefler [9].
In the online learning setting, Joulani et al. [24], McMahan and Streeter [33] studied an adaptive asynchronous SGD algorithm. Aviv et al. [7] proved better guarantees on bounded domains by introducing a projection, with rates depending on the average rather than maximum delay. However, their proof relies heavily on the assumption of a bounded domain, while ours applies for optimization over all of Rdd. Relatedly, Cohen et al. [15] prove guarantees for Asynchronous SGD that depend on the average delay, but their results only hold with probability 1
Most closely related to ours, Mania et al. [32] proposed and utilized the analysis tool of "virtual iterates" for Asynchronous SGD under bounded delays. Stich and Karimireddy [48] extended these results, albeit restricting delays to be constant, and Leblond et al. [29] considered lock-free updates. We use the same proof approach, but with a different virtual sequence and different, ddlay-edaptive stepsizes.
In a concurrent work, Koloskova et al. [28] used similar technique to ours to study Asynchronous SGD with potentially unbounded delays. Their bounds are stated using empirical average of the delays rather than M. Compared to the work of Koloskova et al. [28], our theory includes guarantees for non-smooth problems as given in Theorem 1. They, on the other hand, have an extra result for the case of constant stepsize and bounded delays without assuming bounded gradients. Our Theorem that covers non-convex, convex, and strongly convex problems has almost the same delay-adaptive
3

---

stepsize as their Theorem 8 that covers non non-eonvex functions only. For heterogeneous data, we study standard Asynchronous SGD, whereas Koloskova al. [28] used a special scheduling procedure to balance the workers, see also the comments after our Theorem 4.
More broadly, there are numerous other parallel training approaches that could improve upon Mini- batch SGD. Particularly popular lines of work include gradient compression [2, 10, 48), decentralized
communication [31, 40J, and local updates with infrequent communication [27, 34, 47, 50]. These are all orthogonal to asynchrony and can even be combined with it [see, e.g., 5, 19, 38].
1.5 Notation and problem setting
We consider solving the problem (1) under several standard [see, e.g., 11] combinations of conditions on the objective F. We denote the minimum of as F == miny F(x), an upper bound on the initial suboptimality A > F(xx)= F*, and an upper bound on the initial distance to the minimizer B > min x"1 || x E argminy F. Here, and throughout this paper we focus on the Euclidean geometry and use I-Il to denote the Euclidean norm; however, it is likely possible to extend results to other geometries using similar arguments. Our optimization variable lies in R but our algorithm and results are dimension-free, meaning they hold for any d.
A function F is y-strongly convex if for each y, y and subgradient g E 0x()), we have F(y) > F(x) + (g. y -x)++++ 5 --l?. and F is convex this holds for μr = 0. When F and f are convex, we do not necessarily assume they are differentiable, but we abuse notation and use VF(x) and fx(x; <) to denote an arbitrary subgradient at x. The loss f is G-Lipschitz--contmmuuss if for each y,y and E. we have (x; f(y; O) < Gl|x-yyl, ||. which also implies that for each x. | [x: <
G [1]]. The objective F is L-soooth if it is differentiable and its gradient is LLipschitz-contimuuus: for all x,y, |VF(x) F & L||x yll. We may also assume the stochastic gradients have o² bounded variance, meaning that for all x, Eę=Dl fx {) VF(x)]l o².
When the objective is (strongly) convex, we will obtain an upper bound on the expected suboptimality of our algorithm's output, 8, i.e., EF(()) - F* & for some explicit e. On the other hand, when the objective is not convex, it is generally intractable to approximate global minima [42] so, as is common in the literature, we fall back to showing that the algorithm will find an approximate first-order stationary point of the objective: E((VF(()) < e.
Finally, we mainly focus on "homogeneous" optimization, where each machine computes each stochastic gradient using an i.i.d. sample & ~ D. This is in contrast to the "heterogeneous" setting, where different machines have access to data drawn from different sources, meaning that stochastic gradients estimated on different machines can have different distributions (see Section 5).
Delay notation. The gradients used by Algorithm may arrive out of order, so the parameters X; at iteration k will often be updated using stochastic gradients fx(;; [y) evaluated at out-of-date we therefore introduce additional notation for describing the delays.
parameters x, for j < k We use my E [M] to denote the index of the worker whose stochastic gradient estimate is used in iteration & to compute Xg. addition, for each iteration and worker m, we introduce
prev(k, m) max < k mj = m) and next(k, m) min > k mj = m],
which denotes the index of the last iteration before k in which machine returned a gradient, and the index of the first iteration after & (inclusive) that machine m will return a gradient, respectively. (prev(k.m)) We define the current "delay" of this gradient the number of iterations that have happened since prev(k; m), i.e., 7(k, m) == k- prev (ke m). Abusing notation, we shorten to T rkk) == T(k, mx) for the delay of the gradient used compute Xs.
Accordingly, iteration k. machine is in the process of estimating V f (Xprev((k
2 Analysis of Asynchronous SGD via virtual iterates
The central idea in our analysis is to focus on virtual iterate sequence, which tracks, roughly, how the parameters would have evolved if there were no delays. We note that this sequence is only used for the purpose of analysis, and is never actually computed. This technique is related to previous
approaches [29, 32, 48], with the key difference being which virtual sequence we track. Specifically, in addition to Xo. ... XK- the actual sequence of iterates generated by Algorithm l-we introduce

---

Algorithm Asynchronous SGD
Input: initialization X E R stepsizes "kk > 0
2: Each worker m E [M] begins calculating V (x0: 50
3: for == 1,2......
4: Gradient V (xpeett( Sprev (R)m)().mg) arrives from some worker me
5: Update: X₂ X 7% V [xxprev(( (k. e
(keev().m.))
6: Send X3 to worker my, which begins calculating V V f 5
7:
end for
the complementary sequence ......, R which evolves according to
Xk+1 Xx
V 4x 4x*);
where x1 = Xo
mmm (next(1.m)
V V fxxo
and 4 == (nexx(e+11mm))
This virtual sequence X evolves almost according to SGD (without delays), although we note that uses gradients evaluated at X rather than Xy. The stepsize used for this update, ÿik the stepsize that is eventually used by Algorithm when it takes a step using the gradient evaluated at X The core of our proof' showing that X₁ and & remain close using the following Lemma:
Lemma 1. Let { and } be defined as in Algorithm I and (3), respectively. Then for all k " 1
Xk
Σ
(next(kk. V (k.) cm Sprev(k,m))
Proof. First, expand the update of X in Algorithm and of 8g in (3). Denoting ex Xx. 8k.
e
e e 7 V ff (Xprev(k..m)) ()oo(()
カh-1 (x -3)
el
7/ V ( (Xprov(j.mj)) Speev(s.my)
33 [(
M
k-1
Vx(xo: Si
Σ 73 V (prev(,mm)) (.
myy
Σ i V (x
m=
j=1
From here, we note that the second term, which comprises all of the gradients used by Algorithm to make the first & updates, can be rewritten as:
(1e f $7" (mext().m)
and substituting into the expression for o₁ above, there are & cancellations and the claim follows.
How does this help us? For all of our results, our strategy is to show that the virtual iterates R evolve essentially according SGD (without delays), that ||x 8x remains small throughout the algorithm's 's execution, and therefore that the Asynchronous SGD iterates X₃ are nearly as good as SGD without delays. Lemma I is key for the second step. Whereas previous work tries to bound |Xx xxll by reasoning about the delays involved in the first updates, we observe that X & just the of M gradients, our bound naturally incurs dependence on M, but is not directly affected by the delays themselves.
3 Convergence guarantees for Lipschitz losses
We begin by analyzing Algorithm for convex, Lipschitz-continuuur losses:
Theorem 1. Let the objective F be convex, let {(; be G-Lipsehitz-comiinuuu for each &, and let there be a minimizer x" E argming F(x) for which ||x50 x'll & B. Then for any number of
5

---

iterations K > M, Algorithm 1 with constant stepsize Yk - - BB/(//GGM ensures
1
K
3GBVM
B F K
X
Fr
k=
VK
Proof. Let x" E argming F() with ||x0 x01 & B. First, we follow the typical analysis of
stochastic gradient descent [see, e.g.. 11, Theorem 3.2] by expanding the update of X from (3);
E E||x++1 x = E. [|| x=1 + " I1( 2n (V Fxx)) & x*)
F || x11 -
F*) + 2y (V (xx); Xx {x)]
< E [| x"1 112 -2((())))) - FF
2y &
For the first inequality, used the convexity of F and that f(=:E) being G-Lipschitz implies f E) & G for all x; for the second, we again used the G-Lipschitzness of f(: along with the Stuchy-Schwand inequality. Continuing as in the standard SGD analysis, we rearrange the expression, average over K, apply the convexity of F, and telescope the sum to conclude:
{ x 12
GG2
G
K
E
F
Xk
F
Σ K
Xx
(4)
K
2
The first two terms almost exactly match the guarantee of SGD with fixed stepsize ạ. The main difference-and the place where Lemma and the Lipschitzness of the losses plays a key role-is in bounding the third term. Since V [ (pree(k.,)j:$peeeee (pmev(k.m)) & G, we just use the triangle inequality:
x - &
Σ
yV [V((Xproxk em Sprev(k.
< (M - 1)7G.
(5)
me[M]Mma.
Combining this with ||
112 I|xo
m
M
(x(oo:50)) - x11 < 2B2 + 2 C and
plugging in our stepsize (4) completes the proof.
To understand this result, it is instructive recall the worst-case performance of KMini steps of Minibatch SGD [42] in the setting of Theorem
E (X - = 0 (GB////BB KMini
(6)
From this, we see that our guarantee for Asynchronous SGD in Theorem I matches the rate for KMini = K/M steps of Minibatch SGD. Furthermore, at least in the simplified model of Section 1.2, Asynchronous SGD takes at least M times more steps than Minibatch SGD a given span of time, and therefore Theorem 1 guarantees better performance than (6) in terms of runtime. Moreover, previous analyses of Asynchronous SGD [e.g., 48) provide guarantees with Tmax replacing M in our bound. Since necessarily Tmax 2 M, this means that guarantee is never worse than the existing ones and it can be much better, for example, in a case where one severe straggler results in Tmax R K but M & K. In fact, guarantee in Theorem 1 is minimax optimal in the setting that we consider [see 51, Section 4.3), and as summarized in Table 2.
Finally, emphasize that although M appears in the numerator of the error guarantee in Theorem 1, this does not mean that the guarantee necessarily degrades when more parallel workers are added. In particular, adding more workers always means that more gradients will be calculated in any given amount of runtime. More concretely, in the model of Section 1.2 where the machines have fixed speeds, the expression for KAsyme Kssyne (S, $1...., Sm) in (2) implies that adding (M + 1)th machine gives a better guarantee whenever 8M1+1 is smaller than the harmonic mean of $1,...; Sar:
M
M +
M
SM+1
M
SYm
K Assyne (S, 81, ... 8M411)
KAsyne (S, 81 .,, sM)
Following the same high-level approach, we can also analyze Algorithm for non-convex objectives, the proof being deferred to Appendix C.
W...o.g. we can take M & K because most K of the workers are actually able participate in the first K updates of Algorithm 1, and machines that do not participate simply be ignored in the analysis.

---

Table 2: We compare optimization terms the smooth and convex setting and the resulting speed-ups in the fixed-compun dueed-computation-spee model of Section 1.2. We denote smax = max and approximate the maximum delay Tmax Σm= mmax / sm. The speedup is the largest factor such that
Asynchronous SGD attains the same error in S seconds as Minibatch SGD would aS seconds.
Method
# of Updates
Optimization Term
Speedup
Minibatch SGD
R
8 Amax
P
Asynchronous SGD
K Σ m=1
M
S
Tauaa.
1
(prior works)
Sm
Asynchronous SGD (our work)
K Σ M
m==
8m
S
M
2==1
M
Smaz
8m
> 1
Theorem Let F be smooth, E) be A-Lipschirz-continoon for every &, let A 2 F(xo) F*, and let the stochastic gradients have variance at most o². Then Algorithm I with stepsize = min
1/3
ensures for any K 2 M
2ML
L
L-M-G*K
K
MLA
LA
MLAG
2/3
E (Xx))]
O
K
K
K
Convergence guarantees for non-Lipschitz losses
Now, we analyze smooth but not necessarily Lipschitz-contimuous losses. The previous proofs relied crucially on the gradients being bounded in norm in order to control x X4. For general smooth losses, the situation is more difficult because pxpeev))( Em Sprev(k. )Il could be large. Our solution to this issue is to introduce a new delay-adaptive stepsize schedule "/k ~ 1/r(k), which show allows for sufficient control over | Ex Similar stepsizes have been considered by Wu et al. [52] for the PIAG algorithm, while the stepsizes for Asynchronous SGD used in previous analyses typically scale with 1 1/Tmm Tmax [e.g., 48). Thus, our analysis shows that
get away with more aggressive stepsize to get better rates. However, our stepsize choice could be problematic if correlated with the noise in the stochastic gradients because our proofs involve the step:
E Bgng (Arev my)) D 7k V ((x prev(k,m.) (prew(k..m)) 7/k V F (r))
Therefore, we introduce the following assumption about the relationship between the delays and data:
Assumption 1.
The stochastic sequences (E...).....)oo and (r(0), are independent.
This assumption holds, for example, when it takes a fixed amount of computation to evaluate any stochastic gradient, and the combination of the (potentially heterogeneous) computational throughput on the different workers and network latency gives rise to the delays. However, this can fail to hold, for instance, when training model with variable-length inputs, in which case the delays will probably depend on the length of the imput sequences, so it will likely also be related to the gradient noise. The next Theorem shows our convergence guarantees under Assumption for Asynchronous SGD with novel delay-adaptive stepsizes scaling with 1/T(k)):
Theorem 3. Suppose F is L-smooth, that Assumption I holds, that B Elixo 122 for some minimizer x", and A > EF (x)) (xx) F*. Then there exist numerical constants Cı, C22 C3 Ca such that:
1. For convex F, K > M and Y min
4MFL: gVK] Algorithm I ensures
1. -B
}
4LT(K)
MMLB2
oB
E [[ E
+
K
K
where F. is the weighted average² of xi, X defined in (20).
'The weight on each iterate X is proportional fn. which depends on the eventual delay of V (xx; <**),, and thus not yet known at iteration However, on line 4 of Algorithm 1, the worker could simply return both its gradient and the point at which it was evaluated, so that the term Xa can simply be added at iteration next(k 1, m&) rather than iteration & so there is not need to store all of the previous iterates.
7

---

exp
-
504
c+
e x2
2. For p-strongly convex F, K 3 3M, and = min Algorithm ensures
4br(k)
SML
uk
[((((K)) (MLIP exp
c3K
0²
1¹² K²2B""
log
e
ML
μu
o²
where Xx is the weighted average of........
Xx defined in (22).
3. For non-convex F, K E M, and min
Algorithm ensures
Alr(kj
2MT
KLa
MLA
LAg2
E
( & c4
K
K
where Ng is randomly chosen from X1. X XK according to (25).
defer the complete proof of three parts to Appendices D.I, D.2, and D.3. However, to give sense of our approach, we will now sketch the ideas behind the proof of Theorem 3.1:
Proof sketch. We begin following the standard analysis of SGD for smooth, convex objectives. We expand the update & from (3), and the L-smoothness of the objective and the fact that the stepsizes are less than (4L) to obtain the inequality
B| 112
E
&
x 112
2 5h (F(x)) F*) + 12002 2 (Vi(x): (x'),, Xx xn)
A key step above uses Assumption 1 to show 2t. is independent of the gradient noise, meaning
Elfik (V fxx; + X - x*) = Eli (VF(xx), X - -x)] > E(fx(F(x))) - F*)]-
This is, so far, essentially identical the first step of the typical SGD analysis, the only difference being the fourth term. Rearranging the expression and summing over k; this implies
K
K
(Ffu(F((x)) - F*)] & E. E|| x 11
7k (V (xx:
eme
X xx) (7)
1=
k=
A=1
This still resembles the typical SGD analysis except for the third term on the right hand side, but we begin to divergence here. First, must bound this third term, for which introduce the following Lemma, proven by using Lemma to write X & as sum gradients:
Lemma 2. In the setting of Theorem 3.1,
B
K Σ
I
2h (Vf(xii (T X - 8x))
<
EE
(F(())))
16
R=1
k=1
Combining this with (7) and using the convexity of F, we further conclude that
Σ
2
B
F
I=
F
E
|
x=11
A= 24
16
k=
This shows that a weighted average of the iterates- with X2 unconventionally weighted by the stepsize iu rather than typical uniform weights-aate -ttains suboptimality inversely proportional to the sum of the stepsizes. To conclude, we lower bound the sum of stepsizes in the denominator by a term scaling with min(K/Mr BvK/a). All remaining proof details can be found in Appendix D.
To understand the implications, we recall the guarantees for R steps of Minibatch SGD using minibatches of size M in the setting of Theorem which are (ignoring all constants) [20, 42]: the convex setting, (X((())))) - F+] < LB² exp(-#R/2)
2² [[F(()mm) - F LB²
aB
R
VRM
RRM in the strongly convex setting, and E 2 < LA + /TAA'/RM in the non-convex R
setting, Comparing these to the guarantees for Asynchronous SGD in Theorem 3.1-3, we see that up to constants (and logarithmic factors in the strongly convex case), our results match the guarantees of R. K/M steps of Minibatch SGD with minibatch size M. As discussed in Section 1.2, each

---

10
10a
Minibesch S00
Asynchrongus SGD
Adastvv AsySGD
10a
Frequency
10a
10a
10a
109
20000 25000 30000 Number of gradients
600
1200
Delay
Figure 1: We ran an experiment on simple least-squares problem with random data and tuned all stepsizes. On the left, we see that after a fixed number of gradients are used, Asynchronous SGD is slightly better than Minibatch SGD but it is also quite unstable, whereas with delay-adaptive stepsizes is both fast and stable. On the right, we can see the distribution of the delays (note that y-axis is in log scale). Additional details about the experiment can be found in Appendix A.
update of Minibatch SGD takes the time needed by the slowest machine, meaning that in any given amount of time, Asynchronous SGD will complete at least M times more updates than Minibatch would. Therefore, the guarantees in Theorem imply strictly better performance for Algorithm than for Minibatch SGD in terms of guaranteed error after a fixed amount of time, illustrated in Table 2. Figure depicts a simple experiment demonstrating this phenomenon in practice.
The first "optimization" terms in our guarantees match K/M steps of exact gradient descent, com- pletely irrespective of the delays. In convex cases, it is likely that these could be "accelerated" to scale with (K/M) analysis. However, by analogy to existing lower bounds [12, 51] we conjecture that the optimization terms in Theorem 3.1-2 are the best "unaccelerated" rate could hope for, and that the optimization term Theorem 3.3 is optimal. Moreover, despite the delays, the second "statistical" terms in our guarantees minimax optimal amongst all algorithms that use K stochastic gradients [4, 42]. So, when the statistical terms dominate the rate, our guarantees are unimprovable in the worst case, and in fact they even match what could be guaranteed by K steps of SGD without delays. Furthermore, since the optimization terms decrease faster with K, in a realistic scenario where K >> M, the statistical term will eventually dominate the rate and our algorithm will have optimal performance with no penalty from the delayed gradients at all.
exp(-XXpp (/L/////L))) but at the expense of more complex algorithm and
Heterogeneous data setting
Finally, we extend our results the heterogeneous data setting, where each worker m possesses its own local data distribution D,,, giving rise to a local objective F., So the optimization problem in the heterogeneous setting is:
min XER
F(()
1 = M
Σ
Fm (x)
where [x. EgwD,,, (mx
In this setting, we define Asynchronous SGD the same way, with worker having access to the stochastic gradients fm and updates taking the form:
em X X 7x V (Xprev().me) Sprev(k,
(10)
is generally impossible to show that Asynchronous SGD will work well in this setting. Specifically, if F2 = FMs = 0, then the time needed to optimize F is entirely dependent on the speed of the first worker. Moreover, with arbitrary delays, we might only get a single gradient update from the first worker, leaving our analysis, we will require that the gradient dissimilarities between the local functions are bounded and that the identity of the worker used in iteration is independent of the gradient noise:
hope of any useful guarantee. To avoid this issue and to be able to apply
Assumption 2. There exists >> 0 such that / Fm (x) E Elga [x,, m&] Fm,, (xx), and Blllg Fm,, (xx
Fx)) 12 < <2 for all m and x E TRd.
XR. mg
Equipped with the new assumption, we can provide an analogue of Theorem 3 for problem (9):

---

Theorem 4. In the setting of Theorem 3 with the addition of Assumption 2. for % min( 8LT(N 4ML Vo)(K the updates described in (10) ensure for numerical constant c:
1
E [|]VF((*)]|)
c
(MIA K
LA
+5²)
K
where &3 is randomly chosen from X1, XK according to (28).
Comparing Theorem 4-which we prove in Appendix E-with Theorem 3.3, we see that the exact same rate is achieved in the heterogeneous setting up to the additive term <², As described above, we cannot really expect good performance for arbitrarily heterogeneous losses under arbitrary delays, so some dependence on Ç² is unavoidable. Moreover, in many natural settings, ç² can be quite small. For instance, when heterogeneity arises because a large i.i.d. dataset partitioned across the M machines, the degree of heterogeneity C² will be inversely proportional to the number of samples assigned each worker. So although Asynchronous SGD is not well-suited to problem (9) when the delays can be arbitrarily large, at least under Assumption 2, it does not totally break down or diverge.
While Assumption 2 used in Theorem 4 seems unavoidable for studying Asynchronous SGD, it can be circumvented when studying other asynchronous methods. In particular, Koloskova et al. [28] proposed to sample a random worker at each iteration k and add the current points X to its list of points for computing the gradient. Under an extra assumption on the delay pattern, Koloskova al. [28] proved convergence of this method to point with zero gradient, without extra errors. Unfortunately, unlike Asynchronous SGD, their method would not have the speedup shown in Table 2. since after large number of iterations K, all workers would be expected compute roughly j gradients. Since this puts the same load on the slowest worker as Minibatch SGD, the algorithm proposed by Koloskova et al. [28] is useful only when there no worker that fundamentally slower than the others. Our theory, in turn, has an extra Ç² error term, but does not require waiting for the slow workers.
Conclusion
This work studies Asynchronous SGD via virtual-iterate analysis: we prove that in vast variety of convex/smooth, grongly--onvex/smoott and non-conves/smooth the convergence guarantees of Asynchronous SGD improve over that of Minibatch SGD, irrespectively of the delay sequence. We obtained these results by leveraging delay-adaptive stepsizes and proving that Asynchronous SGD is only slowed down by the number of stochastic gradients being computed, rather than the longest delay. We also extend one of these results the case of heterogeneous data and show that Asynchronous SGD can converge an approximate stationary point with the error controlled by data dissimilarity constant.
settings - convex/Lipschizz, wwwcoovvx/L.isccct//snoeo
Acknowledgements
This work was supported by the French government under the management of the Agence Nationale de la Recherche part of the "Investissements d' l'avenir" program, reference (PRAIRIE 31A Institute). We also acknowledge support from the European Research Council (grant SEQUOIA 724063).
References
[1] Alekh Agarwal and John C. Duchi. Distributed delayed stochastic optimization. Advances in Neural Information Processing Systems, 24, 2011. (Cited on pages 2 and 3)
[2] Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. Qsgd: Communication-cfficieee sgd via gradient quantization and encoding. Advances in Neural Information Processing Systems, 30, 2017. (Cited on page 4)
[3] Yossi Arjevani, Ohad Shamir, and Nathan Srebro. A tight convergence analysis for stochastic gradient descent with delayed updates. Algorithmic Learning Theory, pages 111-132. PMIR, 2020. (Cited on page 2)
10

---

[4] Yossi Arjevani, Yair Carmon, John C. Duchi, Dylan J. Foster, Nathan Srebro, and Blake Woodworth. Lower bounds for non-convex stochastic optimization. Mathematical Programmingg pages 1-50, 2022. (Cited page 9)
[5] Mahmoud Assran, Nicolas Loizou, Nicolas Ballas, and Mike Rabbat. Stochastic gradient push for distributed deep learning. In International Conference on Machine Learning, pages 344-353. PMLR, 2019, (Cited page 4)
[6] Mahmoud Assran, Arda Aytekin, Hamid Reza Feyzmahdavian, Mikael Johansson, and Michael G. Rabbat. Advances in asynchronous parallel and distributed optimization. Proceed- ings of the IEEE, 108(1 1):2013-203333 2020. (Cited on page 3)
[7] Rotem Zamir Aviv, Ido Hakimi, Assaf Schuster, and Kfir Yehuda Levy. Asynchronous dis- tributed learning: Adapting to gradient delays without prior knowledge. In Proceedings of the International Conference Machine Learning, volume 139, pages 436-445, 2021. (Cited on page 3)
[8] Gerard M. Baudet. Asynchronous iterative methods for multiprocessors, Journal of the ACM (JACM), 25(2):226-244, 1978. (Cited on page 3)
[9] Tal Ben-Nun and Torsten Hoefler. Demystifying parallel and distributed deep learning: An in-depth concurrency analysis. ACM Computing Surveys (CSUR), 52(4):1-43, 2019. (Cited on page 3)
[10] Jeremy Bernstein, Yu-Xiang Wang, Kamyar Azizzadenesheli, and Animashree Anandkumar. signSGD: Compressed optimisation for non-convex problems. In International Conference Machine Learning, pages 560-569, 2018. (Cited on page 4)
[11] Sébastien Bubeck. Convex optimization: Algorithms and complexity. Foundations and Trends in Machine Learning, 8(3-4):231-3577 2015. (Cited on pages 4 and
[12] Yair Carmon, John C. Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points arXiv preprint arXiv: 1710 2017. (Cited on page 9)
[13] Zheng Chai, Yujing Chen, Ali Anwar, Liang Zhao, Yue Cheng, and Huzefa Rangwala. FedAT: a high-performance and communication-efficcin tiers. In Proceedings of the International Conference for High Performance Computing, Net- working, Storage and Analysis, pages 1-16, 2021. (Cited on page 2)
federated learning system with asynchronous
[14] Jianmin Chen, Xinghao Pan, Rajat Monga, Samy Bengio, and Rafal Jozefowicz. Revisiting distributed synchronous SGD. arXiv preprint arXiv: 1604.00981, 2016. (Cited page 2)
[15] Alon Cohen, Amit Daniely, Yoel Drori, Tomer Koren, and Mariano Schain. Asynchronous stochastic optimization robust to arbitrary delays. Advances Neural Information Processing Systems, 34, 2021. (Cited on page 3)
[16] Andrew Cotter, Ohad Shamir, Nati Srebro, and Karthik Sridharan. Better mini-batch algorithms via accelerated gradient methods. Advances in Neural Information Processing Systems 24, pages 1647-1655, 2011. (Cited page 1)
[17] Jeffrey Dean, Greg Corrado, Rajat Monga, Kai Chen, Matthieu Devin, Mark Mao, Marc aurelio Ranzato, Andrew Senior, Paul Tucker, Ke Yang, et al. Large scale distributed deep networks. Advances in Neural Information Processing Systems, 25, 2012. (Cited on page
[18] Ofer Dekel, Ran prediction using mini-batches. Journal of Machine Learning Research, 155-222, 2012. (Cited on page
Ohad Shamir, and Lin Xiao. Optimal distributed online
[19] Mathieu Even, Hadrien Hendrikx, and Laurent Massoulié. Decentralized optimization with heterogeneous delays: continuous-time approach. arXiv:2106.03358 005500800000.5. 2021. (Cited on page 4)
[20] Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341-236 2013. URL.
org/ a/aabb/s1300 1309. 5549. (Cited on page 8)
11

---

[21] Robert M. Gower, Nicolas Loizou, Xun Qian, Alibek Sailanbayev, Egor Shulgin, and Peter Richtárik, SGD: General analysis and improved rates. International Conference on Machine Learning, pages 5200-5209, 2019. (Cited on page
[22] Priya Goyal, Piotr Dollár, Ross Girshick, Picter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, Andrew Tulloch, Yangging Jia, and Kaiming He. Accurate, large minibatch SGD: Training imagenet in hour. arXiv preprint arXiv: 1006.02770,77, 2017. (Cited on page 1)
[23] Samuel Horváth, Stefanos Laskaridis, Mario Almeida, Ilias Leontiadis, Stylianos I. Venieris, and Nicholas D. Lane. FjORD: Fair and accurate federated learning under heterogeneous targets with ordered dropout. Advances in Neural Information Processing Systems, 34, 2021. (Cited on page 1)
[24] Pooria Joulani, András György, and Csaba Szepesvári. Delay-toleran, online convex optimiza- tion:
Unified analysis and adaptive -araiive-radieent gradient algorithms. In Proceedings the on Artificial Intelligence, volume 30, 2016. (Cited on page 3)
the AAAI Conference
[25] Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Ar- jun Nitin Bhagoji, Keith Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, Rafael G. L. D'Oliveira, Salim EI Rouayheb, David Evans, Josh Gardner, Zachary Garrett, Adria Gascón, Badih Ghazi, Phillip B. Gibbons, Marco Gruteser, Zaid Harchaoui, Chaoyang He, Lie He. Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi. Tara Javidi. Gauri Joshi, Mikhail Khodak, Jakub Konečný, Aleksandra Korolova, Farinaz Koushanfar, Sanmi Koyejo, Tancrède Lepoint, Yang Liu, Prateek Mittal, Mehryar Mohri, Richard Nock, Ayfer Özgür, Rasmus Pagh, Mariana Raykova, Hang Qi, Daniel Ramage, Ramesh Raskar, Dawn Song, Weikang Song, Sebastian U. Stich, Ziteng Sun, Ananda Theertha Suresh, Florian Tramèr, Praneeth Vepakomma, Jianyu Wang, Li Xiong, Zheng Xu, Qiang Yang, Felix X. Yu, Han Yu, and Sen Zhao. Advances and open problems in federated learning, 2019, (Cited on page
[26] Ahmed Khaled and Peter Richtárik. Better theory for SGD in the nonconvex world. arXiv Preprint arXiv:2002.03329, 2020. (Cited on page 3)
[27] Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. Tighter theory for local SGD on identical and heterogeneous data. In International Conference on Artificial Intelligence and Statistics, pages
PMLR, 2020. (Cited on page
[28] Anastasia Koloskova, Sebastian U. Stich, and Martin Jaggi. Sharper convergence guarantees for asynchronous SGD for distributed and federated learning. arXiv preprint arXiv:2206.08307, 2022. (Cited on pages 3, 4, and 10)
[29] Rémi Leblond, Fabian Pedregosa, and Simon Aacoste-Julien, Improved asynchronous paral- lel optimization analysis for stochastic incremental methods. Journal of Machine Learning Research, 19:1-68, 2018. (Cited on pages 2, 3. and 4)
[30] Xiangru Lian, Yijun Huang, Yuncheng Li, and Ji Liu. Asynchronous parallel stochastic gradient for nonconvex optimization, Advances Neural Information Processing Systems, 28, 2015. (Cited on page 3)
[31] Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsieh, Wei Zhang, and Ji Liu. Can decentralized algorithms outperform centralized algorithms? case study for decentralized parallel stochastic gradient descent. Advances in Neural Information Processing Systems, 30, 2017. (Cited on page 4)
[32] Horia Mania, Xinghao Pan, Dimitris Papailiopoulos, Benjamin Recht, Kannan Ramchandran, and Michael I. Jordan. Perturbed iterate analysis for asynchronous stochastic optimization. SIAM Journal on Optimization, 27(4):2202-25 2229, 2017. doi: 10.1137/16M1057000, (Cited on
pages 2, 3, and 4)
[33] Brendan McMahan and Matthew J. Streeter. Delay-tolerant algorithms for asynchronous distributed online learning. Advances Neural Information Processing Systems, 27, 2014. (Cited page
12

---

[34] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-effiee efficient learning of deep networks from decentralized data, In Artificial intelligence and statistics, pages 1273-1282. PMLR, 2017. (Cited on page 4)
[35] Konstantin Mishchenko, Franck lutzeler, Jérôme Malick, and Massih-Rezze Amini. A delay- tolerant proximal-gradient algorithm for distributed learning. In International Conference on Machine Learning, pages 3584-3592, 2018. (Cited on page 3)
[36] Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforce- ment learning. International Conference on Machine Learning, pages 1928-1937, 2016. (Cited on page 2)
[37] Philipp Moritz, Robert Nishihara, Stephanie Wang, Alexey Tumanov, Richard Liaw, Eric Liang, Melih Elibol, Zongheng Yang. William Paul, Michael I. Jordan, and Ion Stoica. Ray: A distributed framework for emerging AI applications. In 13th USENIX Symposium on Operating Systems Design and Implementation (OSDI 18), pages 561-577, 2018. (Cited on page 15)
[38] Giorgi Nadiradze, Amirmojtaba Sabour, Peter Davies, Shigang Li, and Dan Alistarh. Asyn- chronous decentralized SGD with quantized and local updates. Advances in Neural Information Processing Systems, 34, 2021. (Cited on page 4)
[39] Arun Nair, Praveen Srinivasan, Sam Blackwell, Cagdas Alcicek, Rory Fearon, Alessandro De Maria, Vedavyas Panneershelvam, Mustafa Suleyman, Charles Beattie, Stig Petersen, et al. Massively parallel methods for deep reinforcement learning. arXiv preprint arXiv: 000.0047744966
2015. (Cited on page 2)
[40] Angelia Nedić and Asuman Ozdaglar. Distributed subgradient methods for multi agent opti- mization. IEEE Transactions on Automatic Control, 54(1):48-66 61, 2009. (Cited on page 4)
[41] Angelia Nedić, Dimitri P. Bertsekas, and Vivek S. Borkar. Distributed asynchronous incremental subgradient methods. Studies in Computational Mathematics, 8(C):381 1078,, 2001. (Cited on page 2)
[42] Arkadii Semenovich Nemirovsky and David Borisovich Yudin. Problem complexity and method efficiency in optimization. Wiley-Interscience, 1983. (Cited on pages 4, 6, 8, and 9)
[43] John Nguyen, Kshitiz Malik, Hongyuan Zhan, Ashkan Yousefpour, Mike Rabbat, Mani Malek, and Dzmitry Huba. Federated learning with buffered asynchronous aggregation. In International Conference on Artificial Intelligence and Statistics, pages 3581-3607, 2022. (Cited on page 2)
[44] Benjamin Recht, Christopher Re, Stephen Wright, and Feng Niu. Hogwild!: A lock-free ap- proach to parallelizing stochastic gradient descent. Advances in Neural Information Processing Systems, 24, 2011 1. (Cited on pages 2 and
[45] Max Ryabinin, Eduard Gorbunov, Vsevolod Plokhotnyuk, and Gennady Pekhimenko. Moshpit SGD: Commuuniation-efffccieee decentralized training on heterogeneous unreliable devices. Advances Neural Information Processing Systems, 34, 2021. (Cited on page 2)
[46] Suvrit Sra, Adams Wei Yu, Mu Li, and Alexander J. Smola. Adadelay: Delay adaptive distributed stochastic optimization. In Artificial Intelligence and Statistics, pages 957-965. PMLR, 2016. (Cited on page 3)
[47] Sebastian U. Stich. Local SGD converges fast and communicates little. In International Conference on Learning Representations, 2018. (Cited on page 4)
[48] Sebastian U. Stich and Sai Praneeth Karimireddy. The error-feedback framework: Better rates for SGD with delayed gradients and compressed updates. Journal of Machine Learning Research, 21:1-36, 2020. (Cited on pages 2, 3, 4, 6, and 7)
[49] John Tsitsiklis, Dimitri Bertsekas, and Michael Athans. Distributed asynchronous deterministic and stochastic gradient optimization algorithms. IEEE transactions on automatic control, 31))): 803-812, 1986. (Cited on page 3)
13

---

[50] Blake Woodworth, Kumar Kshitij Patel, Sebastian Stich, Zhen Dai. Brian Bullins. Brendan Mcmahan, Ohad Shamir, and Nathan Srebro. Is local SGD better than minibatch SGD? In International Conference Machine Learning, pages 10334-10343. PMLR, 2020. (Cited on page 4)
[51] Blake E. Woodworth, Jialei Wang, Adam Smith, Brendan McMahan, and Nati Srebro. Graph oracle models, lower bounds, and gaps for parallel stochastic optimization. Advances in Neural Information Processing Systems, 31, 2018. (Cited on pages 6 and 9)
[52] Xuyang Wu, Sindri Magnusson, Hamid Reza Feyzmahdavian, and Mikael Johansson. Delay- adaptive step-sizes for asynchronous learning. arXiv preprint arXiv:2202.08550 2022. (Cited on page 7)
[53] Shuxin Zheng, Qi Meng, Taifeng Wang, Wei Chen, Nenghai Yu, Zhi-Ming Ma, and Tie- Yan Liu. Asynchronous stochastic gradient descent with delay compensation. In International Conference on Machine Learning, pages 11294119, 2017. (Cited on page 3)
[54] Zhengyuan Zhou, Panayotis Mertikopoulos, Nicholas Bambos, Peter Glymn, Yinyu Ye, Li-Jia Li, and Li Fei-Fei. Distributed asynchronous optimization with unbounded delays: How slow can you go? In International Conference on Machine Learning, pages 5970-5979, PMLR, 2018. (Cited on page 3)
[55] Martin Zinkevich, Markus Weimer, Lihong Li, and Alex Smola. Parallelized stochastic gradient descent. In Advances in Neural Information Processing Systems, pages 2595-2603, 2010. (Cited on page 1)
14


Reviews:
[{"review_id": "F69afVLYIa", "reviewer": "Reviewer_43Xn", "summary": "This paper analyzes asynchronous SGD (also known as delayed SGD) where stochastic gradients are computed over $M$ machines and sent to a central server and the server updates its iterates every time it receives a noisy gradient. The challenge in analyzing this algorithm is that some slow machines get to compute the gradients at out-dated iterates.\n\nA baseline for this algorithm is a synchronous version called minibatch SGD where the server waits until all the $M$ machines finish gradient computation and makes a single update out of the aggregated minibatch of $M$ gradients.\n\nPrevious analyses on asynchronous SGD assume delays bounded above by $\\tau_{max}$ and then show iteration complexities that grow with $\\tau_{max}$. This paper analyzes asynchronous SGD with *delay-adaptive step sizes* and proves that asynchronous SGD has the same computational complexity as the baseline minibatch SGD, independent of the delays. This in turn implies that due to the asynchronous nature of SGD (i.e., it doesn't have to wait until all $M$ machines finish gradient calculation), it converges faster than minibatch in wall-clock time.", "questions": "Q1. As I detail in L2 below, there is a concurrent work that is very similar to this submission. Can you comment on how your results compare with this concurrent paper?\n\nQ2. In the equation below Line 159, shouldn't the second term have $next(i+1,m_i)$ instead of $next(i,m_i)$, as $next(i,m_i) = i$ always? Correct me if I'm wrong.", "limitations": "L1. In Table 1, it is written that the rates for the strongly convex case shown in this paper is $\\exp(-\\frac{\\mu K}{L M}) + \\frac{\\sigma^2}{K}$. However, from Theorem 3.2 it seems that there should be a leading $M$ factor in the first term. Hiding this leading $M$ term in the strongly convex case is a bad omission in my opinion. (By the way I think $T$ in Theorem 3.2 should be $K$, right?)\n\nL2. This is not necessarily a limitation of this submission, but it is quite unfortunate for the authors that a concurrent paper has presented an overlapping set of results. I am pretty sure that by now the authors would have become aware of the paper \"Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learning\" by Koloskova et al. The paper tackles exactly the same problem as this submission and develops a very similar set of theoretical results. Koloskova et al.'s results depend on $\\tau_{avg}$ but this can be thought as the number of machines ($M$) in this submission (see their Remark 5). In this regard, Koloskova et al.'s Corollary 7 shows a rate that corresponds to Theorem 2 of this paper, and Corollary 9 of theirs matches with Theorem 3.3 of this submission. Reading the two papers, I came up with a quick list of pros and cons of this paper compared to Koloskova et al.:\n\nPros:\n- Koloskova et al. only cover nonconvex smooth cases.\n\nCons:\n- Koloskova et al. study a slightly more general algorithm which captures both minibatch SGD and asynchronous SGD.\n- Koloskova et al. show convergence in heterogeneous case (although with some modification to the algorithm)\n\n…and I'm looking forward to the authors' comments on more detailed comparisons.\n", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "S1. This is a solid contribution improving the theoretical analysis of asynchronous SGD. The paper is well-written and conveys the main ideas clearly. Proof sketches are also quite helpful.\n\nS2. Convergence of asynchronous SGD is analyzed in various setups such as Lipschitz convex (Thm 1), smooth Lipschitz nonconvex (Thm 2), smooth convex (Thm 3.1), smooth strongly convex (Thm 3.2), and smooth nonconvex (Thm 3.3) functions.\n\nW1. It is unfortunate that the analysis does not extend well to heterogeneous setups, leaving an extra $\\zeta^2$ term that prevents global convergence.\n\nOverall, this paper is a solid theoretical contribution to the community and I would like to recommend acceptance of this paper.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "DoopCgpVPRU", "reviewer": "Reviewer_ZU76", "summary": "Authors propose a new way to analyze convergence of asynchronous SGD that does not depend on the maximum delay of gradient updates among the workers but of the number of machines. This is achieved by introducing delay-adaptive step sizes and a new virtual iterate-based analysis.", "questions": "- since the step size is scaled by 1/delay,  if delay is large, would it be just fine to discard those updates alltogether? At least if all machines have data from same distribution.\n- in Table 1, what is sigma?\n- in Table 1, where is the M/K + sigma/sqrt(K) derived in the paper? It would be good to refer to the theorem and show it in the same form in the paper text as in the table.", "limitations": "Limitations not discussed. Societal impact not relevant.", "rating": 3, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n- early part of the paper is nicely written, especially the last paragraph of 1.1 illuminated well the problem of previous analysis\n- studying asynchronous SGD is important topic, as synchronous SGD has serious scalabiity limitations\n- theoretical analysis is structured quite cleanly, and much of the work is in the paper itself instead of appendix\n- good language\n\nWeaknesses\n- I find it suspicious to compute speedups between two Ohs, i.e  O(a) / O(b) does not make sense, because the underlying constants are not known, and may not be the same for left and right side. This makes me consider the claims of the paper overblown. In addition, to claim async SGD wins minibatch SGD over arbitrary delays seems unrealistic: what if there are very large delays for all gradient communication, i.e arbitrary large delays?  Please rephrase the title.\n- there is too much in the paper, so it does not include proper experiments section which would be necessary to validate the (strong) claims.\n- paper structure is messy. Hard to see where the results for Table 1 are derived, as they are presented in different form in the theorems.\n- paper is missing Conclusion/Summary.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "0Eihz5cyk9O", "reviewer": "Reviewer_XzpK", "summary": "In the paper, the authors proposed a new method to analyze the convergence rate of asyn SGD method. The proposed analysis showed that the convergence rate of asyn SGD is not dependent on the delay of the gradients and comparable or even faster than the convergence of mini-batch SGD under certain conditions. ", "questions": "1.  Where is the statement \"99.9999% of the SGD steps taken have gradients with no delay\" obtained?\n2. There are a lot of works showing that asynchronous SGD hurt performance, from the theoretical analysis in the paper, asyn SGD should be at least comparable. Could the authors comment on this? ", "limitations": "NA", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strenges:\n1. Based on the observation that SGD should be robust to the delay and 99.9999% of the SGD steps taken have gradients with no delay, the authors proposed a new analysis for aync-SGD and showed faster convergence rate than previous analysis. \n\nWeaknesses:\n1.  Where is the statement \"99.9999% of the SGD steps taken have gradients with no delay\" obtained?\n2. There are a lot of works showing that asynchronous SGD hurt performance, from the theoretical analysis in the paper, asyn SGD should be at least comparable. Could the authors comment on this? ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept