Asynchronous Stochastic Optimization Robust to Arbitrary Delays
Authors: Alon Cohen
Amit Daniely
Yoel Drori
Tomer Koren
Mariano Schain
Venue: NeurIPS 2021 Poster (2021)
Keywords: Stochastic Optimization
Asynchronous Optimization
Delayed Gradients

Abstract: We consider the problem of stochastic optimization with delayed gradients in which, at each time step $t$, the algorithm makes an update using a stale stochastic gradient from step $t - d_t$ for some arbitrary delay $d_t$.   This setting abstracts asynchronous distributed optimization where a central server receives gradient updates computed by worker machines. These machines can experience computation and communication loads that might vary significantly over time.   In the general non-convex smooth optimization setting, we give a simple and efficient algorithm that requires $O( \sigma^2/\epsilon^4 + \tau/\epsilon^2 )$ steps for finding an $\epsilon$-stationary point $x$.   Here, $\tau$ is the \emph{average} delay $\frac{1}{T}\sum_{t=1}^T d_t$ and $\sigma^2$ is the variance of the stochastic gradients.   This improves over previous work, which showed that stochastic gradient decent achieves the same rate but with respect to the \emph{maximal} delay $\max_{t} d_t$, that can be significantly larger than the average delay especially in heterogeneous distributed systems.   Our experiments demonstrate the efficacy and robustness of our algorithm in cases where the delay distribution is skewed or heavy-tailed.

Asynchronous Stochastic Optimization Robust to Arbitrary Delays
Alon Cohen Tel Aviv University and Google Research Israel alonco@tauex. tau. ac. il
Amit Daniely
Yoel Drori
Hebrew University of Jerusalem and Google Research Israel amit dani el eel@mailll. 1. .uuji.h.ii... ac.il
Google Research Israel dyoel@google.
Tomer Koren
Mariano Schain Google Research Israel marianos@google.
Tel Aviv University and Google Research Israel tkoren@tauex. tau. ac.
Abstract
We consider stochastic optimization with delayed gradients where, at each time step r. the algorithm makes an update using a stale stochastic gradient from step r d, for some arbitrary delay d, This setting abstracts asynchronous distributed optimization where central server receives gradient updates computed by worker machines. These machines can experience computation and communication loads that might vary significantly over time. In the general non-convex smooth optimization setting, we give simple and efficient algorithm that requires ( /c* + +/c/²) steps for finding e-stationary point x, where is the average delay E/= d, and o² is the variance of the stochastic gradients. This improves over previous work, which showed that stochastic gradient decent achieves the same rate but with respect the maximal delay max, d,, that can be significantly larger than the average delay especially in heterogeneous distributed systems. Our experiments demonstrate the efficacy and robustness of our algorithm in cases where the delay distribution skewed heavy-tailed.
Introduction
Gradient-basse based iterative optimization methods are widely used in scrge-scale machine learning applications as they are extremely simple implement and use, and come with mild computational requirements. On the other hand, in their standard formulation they are also inherently serial and synchronous due their iterative nature. For example, in stochastic gradient descent (SGD), each step involves an update of the form xy+1 xx nJ, where is the current iterate, and is (stochastic) gradient vector evaluated at x,. To progress the next step has to be fully determined by the end of step it is required for future gradient queries. Evidently, this scheme has to wait for the computation the gradient gr to complete (this is often the most computationally intensive part in SGD) before it can evaluate Xr+1.
method, the subsequent iterate x,+1
In modern large scale machine learning applications, direct serial implementation of gradient methods like SGD is overly costly, and parallelizing the optimization process over several cores or machines desired. Perhaps the most common parallelization approach via mini-batching. where computation of stochastic gradients is distributed across several worker machines that send updates to a parameter server. The parameter server responsible for accruing the individual updates into single averaged gradient, and consequently, updating the optimization parameters using this gradient.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).

---

While mini-batching is well understood theoretically [e.g.. 16, 9, 8, 10], it is still fundamentally synchronous in nature and its performance adversely determined by the slowest worker machine: the parameter server must wait for all updates from all workers to arrive before it can update the model it maintains. This could cause serious performance issues in heterogeneous distributed networks, where worker machines may be subject to unpredictable loads that vary significantly between workers (due to different hardware, communication bandwidth, etc.) and over time (due to varying users load, power outages, etc.).
An alternative approach that has recently gained popularity is to employ asynchronous gradient updates [e.g., 21, 2. 7, 18, 11]: namely, each worker machine computes gradients independently of the other machines, possibly on different iterates, and sends updates to the parameter server in an asynchronous fashion. This implies the parameter server might be making stale updates based on delayed gradients taken at earlier, out-of-date iterates. While these methods often work well in practice, they have proven to be much more intricate and challenging to analyze theoretically than synchronous gradient methods, and overall our understanding of asynchronous updates remains lacking.
Recently, Arjevani et al. [4] and subsequently Stich and Karimireddy [26] have made significant progress in analyzing delayed asynchronous gradient methods. They have shown that in stochastic optimization, delays only affect lower-order term in the convergence bounds. In other words, if the delays are not too large, the convergence rate of SGD may not be affected by the delays. (4 first proved this for quadratic objectives; 26 then proved a more general result for smooth functions.) More concretely, Stich and Karimireddy [26] showed that SGD with a sufficiently attenuated step size to account for the delays attains an iteration complexity bound of the form
0²
T Tmax
(1)
E²
for finding an e-stationary point of a possibly non-convex smooth objective function (namely, point at which the gradient is of norm I c). Here o² the variance of the noise the stochastic gradients, and max is the maximal possible delay, which is also needed to be known a-priori for properly tuning the SGD step size. Up to the maa factor in the second term, this bound is identical to standard iteration bounds for stochastic non-convex SGD without delays [12].
While the bound in Eq. (1) a significant improvement over previous art, is still lacking in one important aspect: the dependence on the maximal delay could be excessively large in truly asynchronous environments, making the second term in the bound the dominant term. For example, in heterogeneous or massively distributed networks, the maximal delay is effectively determined by the single slowest (or less reliable) worker maihine-which is precisely the issue with synchronous methods we set to address in the first place. Moreover, as Stich and Karimireddy [26] show, the step size used to achieve the bound in Eq. (1) could be as much as m -times smaller than that of without delays, which could severely impact performance in practice.
1.1 Contribution
We propose a new algorithm for stochastic optimization with asynchronous delayed updates, we call "Picky SGD," that is significantly more robust than SGD, especially when the (empirical) distribution of delays is skewed or heavy-tailed and thus the maximal delay could be very large. For general smooth possibly non-convex objectives, our algorithm achieves a convergence bound of the form
T Tavg
where now Tavg is the average delay in retrospect. This is significant improvement over the bound in Eq. (1) whenever T Tavg- & Tmax. which is indeed the case with heavy-tailed delay distributions. Moreover, Picky SGD is very efficient, extremely simple to implement, and does not require to know the average delay Tavg ahead of time for optimal tuning. In fact, the algorithm only relies on a single additional parea--ar beyond the step-size.
Notably, and in contrast to SGD as analyzed previous work [26], our algorithm able to employ a significantly larger effective step size, and thus one could expect it to perform well in practice compared SGD. Indeed, we show experiments that Picky SGD is able to converge quickly on large image classification tasks with relatively high learning rate, even when very large delays
2

---

introduced. In contrast, in the same setting, SGD needs to be configured with a substantially reduced step size be able to converge at all, consequently performing poorly compared to our algorithm.
Finally, we also address the case where f is smooth and convex, in which we give a close variant of algorithm with an iteration complexity bound of the form
2
Tavg
c²
for obtaining point with f(x) f(x") (where x² is minimizer of f over (R.). Here well, our rate matches precisely the one obtained by the state-of-the-art [26], but with the dependence on the maximal delay being replaced with the average delay. For consistency of presentation, defer details on the convex case to the full version of the paper [? and focus here on our algorithm for non-convex optimization.
Concurrently to this work, Aviv et al. [5] derived similar bounds that depend on the average delay. Compared to our contribution, their results are adaptive the smoothness and noise parameters, but on the other hand, are restricted to convex functions and their algorithms are more elaborate and their implementation more involved.
1.2 Additional related work
For general background on distributed asynchronous optimization and basic asymptotic convergence results, we refer to the classic book by Bertsekas and Tsitsiklis [6]. Since the influential work Niu al. [24], there has been significant interest in asynchronous algorithms in related model where there a delay in updating individual parameters in a shared parameter vector (e.g., [25, 19, 28, 17]). This is of course very different from our model, where steps use the full gradient vector in atomic, yet delayed, updates.
Also related to study is the literature Local SGD (e.g., 27 and references therein), which distributed gradient method that perform several local (serial) gradient update steps before communicating with the parameter server with other machines. Local SGD methods have become popular recently since they are used extensively in Federated Learning [20]. We note that the theoretical study in this line of work is mostly concerned with analyzing existing distributed variants of SGD used in practice, whereas we aim to develop and analyze new algorithmic tools to help with mitigating the effect of stale gradients in asynchronous optimization.
related yet orthogonal issue in distribution optimization, which we do not address here, reducing the communication load between the workers and servers. One approach that was recently studied extensively is doing this by compressing gradient updates before they are transmitted over the network. We refer to [3, 14, 26] for further discussion and references.
Setup and Basic Definitions
2.1 Stochastic non-convex smooth optimization
We consider stochastic optimization of f-smooth (not necessarily convex) non-negative function defined over the d-dimensional Euclidean space Rdd. A function f is said to be f-smooth if differentiable and its gradient operator is B-Lipschitz, that is, if [IV vf())l s Bl|x - yll for all x. E Rd. This particular implies (e.g.. (22]) that for all y. y.y. Rd
B -1y x|1
f(y) s f(x Vf()) (y
We assume a stochastic first-order oracle access fü namely, f endowed with stochastic gradient oracle that given a point x e Rd returns random vector g(x), independent of all past randomization, such that (xg(x) xx] (xxx and E[ll@(x) - 22 xx] s 0² for some variance bound 0² 2 O. In this setting, our goal is to find an e-stationary point of f. namely, a point e [Rd such that [[V]())] s c, with as few samples of stochastic gradients as possible.
2.2 Asynchronous delay model
We consider an abstract setting where stochastic gradients (namely, outputs for invocations of the stochastic first-order oracle) are received asynchronously and are subject to arbitrary delays. The asynchronous model can be abstracted as follows. We assume that at each step of the optimization,
3

---

the algorithm obtains pair (Xr-d, 8t) where &r is stochastic gradient at Xy-d, with variance bounded by o²; namely, &r is random vector such that E,gr Vx((xdd,) and E,llgr Vf(x,-,, )l 2|2 < o² for some delay S d, t. Here and throughout, E, [ denotes the expectation conditioned on all randomness drawn before step After processing the received gradient update, the algorithm may query a new stochastic gradient at whatever point it chooses (the result of this query will be received with delay, above).
Few remarks are in order:
We stress that the delays d1, d2.... are entirely arbitrary, possibly chosen by an adversary: in particular, we do not assume they sampled from fixed stationary distribution. Nevertheless, we assume that the delays are independent of the randomness of the stochastic gradients (and of the internal randomness of the optimization algorithm, any).
For simplicity, we assumed above that a stochastic gradient is received at every round t. This is almost without loss of generality: if at some round no feedback is observed, may simply skip the round without affecting the rest of the optimization process (up to a re-indexing of the remaining rounds).
Similarly, we will also assume that only a single gradient is obtained in each step; the scenario that multiple gradients arrive at the same step (as in mini-batched methods) can be simulated by several subsequent iterations in each which a single gradient processed.
3 The Picky SGD Algorithm
We are now ready to present our asynchronous stochastic optimization algorithm, which we call Picky SGD; see pseudo-code in Algorithm 1. The algorithm is essentially variant of stochastic gradient descent, parameterized by learning rate 1) as well as target accuracy e.
Algorithm 1: Picky SGD
1: input: learning rate 17, target accuracy e.
2: for r I..... do
3: receive delayed stochastic gradient &, and point Xı-d, such that E, = (x(--))) (26)) then
4: if [|xx X,-d,
1 ||
5: update: X,+1 = X2 1781-
6: else
7: pass: X1+1 = Xy-
8: end if
9: end for
Picky SGD maintains a sequence of iterates XT. At step the algorithm receives a delayed stochastic gradient gr that was computed an earlier iterate x;-d, (line 3). Then, in line 4, the algorithm tests whether ||x; xx-4 s e/2p. Intuitively, this aims to verify whether the delayed (expected) gradient (x;-d) is "similar" the gradient (x,) at the current iterate x,; due the smoothness of f. we expect that if x,-d, is close to x,. then also the corresponding gradients will be similar. If this condition holds true, the algorithm takes gradient step using 8r with step size r7.
Our main theoretical result is the following guarantee on the success of the algorithm.
Theorem 1. Suppose that Algorithm is initialized at x1 Rd with f(xi) and ran with
o²
T+
c2
T 2 500BF
ct
62
n=
48 min
02
where T be the average delay, i.e., T= (1/7) ET d, Then, with probability at least 1, there is some 1 S S for which fx,))) c.
Observe that the optimal step size Theorem independent of the average delay T. This important for two main reasons: (i) implementing the algorithm does not require knowledge about
'One can thus think the sequence of delays as being fixed ahead time by an oblivious adversary. zWe may, in principle. allow to query the stochastic gradient oracle even on rounds where no feedback received, however this would be redundant in most reasonable instantiations of this model (e.g.. in parameter server architecture).

---

future, yet-to-be-seen delays; and (ii) even with very large delays, the algorithm can maintain a high effective step size.
We note that the guarantee of Theorem is slightly different from typical bounds in non-convex optimization (e-g.. the bounds appearing in the previous work [14]): our result claims about the minimal gradient norm of any iterate rather than the average gradient norm over the iterates. Arguably, this difference does not represent a very strong limitation: the significance of convergence bounds in non-convex optimization is, in fact, in that they ensure that one of the iterates along the trajectory of the algorithm is indeed an approximate critical point, and the type of bound we establish is indeed sufficient to ensure exactly that.
We further note that while the theorem above only guarantees constant success probability, it is not hard to amplify this probability to an arbitrary 1 8 simply by restarting the algorithm ( I (8)) times (with independent stochastic gradients); with high probability, one of the repetitions will be successful and run through a point with gradient norm S which would imply the guarantee in the theorem with probability least 1 6.
4 Analysis
In this section we analyze Algorithm I and prove our main result. Throughout, we denote X/ = =x,d, and let N, denote the noise vector at step 1, namely N, 8: ff(xx). Note that E[N, x,,x/( = and I| Xy, x;] s o², since the iterates x, are conditionally independent of the noise in gr as this gradient is obtained by the algorithm only at step r, after x,, were determined.
To prove Theorem 1, will analyze variant of the algorithm that will stop making updates once it finds a point with || [x) S (and eventually fails otherwise). That is, if ||x, xxíI > c/2$ or [x)) S then Xy+1 Xy- Else, X,+1 =x,- 782- This variant is impossible to implement (since it needs to compute the exact gradient at each step), but the guarantee of Theorem is valid for this variant if and only if it is valid for the original algorithm: encounters e-stationary point if and only if the other does so.
First, we prove simple technical lemma guarantecing that whenever the algorithm takes step, large gradient norm implies a large decrease in function value. is a variant of the classical "descent lemma," adapted to the case where the gradient step is taken with respect to gradient computed at nearby point.
Lemma 2. Fix x, E Rd with ||x - xxIl '1 s e/2B and [V > e. Let N E Rd a random vector with E[N | xx,x'] = and E[I[N]] xx,x'] S 0². Then.
- -EISS(()) TB (0² (0²+E1V/(>>1)))
N))])))))))]))))) - Ef(x) N
In particular, for our choice of 17 have
"EIVF(''IP&&EEF -E( (Vf(x)) + +N)].
(3)
Proof. Using the smoothness of f (Eq. (2)), we have
f(x - (VF((( + N)) f(x s Vf)((x (Vf(x) +/ + +NI?
Taking expectation over N conditioned on x,x', we get
E[f(x- - N)))= - f(x xx,x
<-nVf(x) <-NVf())V((())++ +/
S |1-p-:/---000//000---------////1
Since e < [V('']| then
||x-x'|| s e
S [Vf(('))
2B 26
5

---

and we have
E[ʃ(x-10 //(xx7((S[(}) N)) -(x) s - 1 [V
e then o² [VVf('') This, with 1 1/4B, yiclds Eq. (3). Ife and e² /40² p, then
r7² S e² 1 B². Plugging that in instead, using VV 2 e, and taking expectations (with respect to to.x,xx) gets Eq. (3).
We next introduce a bit of additional notation. We denote by I, the indicator of event that the algorithm performed an update at time Namely,
1, = [[1x, - -xyll & e/2B and [V > eJ.
Note that 4 = implies that [vVf(x,)]l 2 e for all s = I.....t. Further, we denote by A, fxx) - (x(+1) the improvement time Since non-negative and f(x)) F, we have that for all 1,
Σ A f(x)) f(x+1))
Note that by Lemma 2 we have that EA, 2 0. The rest of the proof is split into two cases: a s c, and
4.1 Case (i): e
This regime is intuitively the "low noise" regime in which the standard deviation of the gradient noise, o, is smaller than the desired accuracy e. We prove the following.
Lemma 3. Suppose that a S e and the algorithm fails with probability 2 1/2 Then s 128 1)/e².
To prove the lemma above, first show that the algorithm must make significant number of updates, as shown by the following lemma. Lemma 4. If the algorithm fails, then the number of updates that it makes is at least T/4(I 1).
Proof. Consider U2r, the number of steps for which the delay d, is least 2T. We must have U2r I T/2 (otherwise the total sum of delays exceeds T7, contradicting the definition of r). On the other hand, let k the number of updates that the algorithm makes. Let f1 < < < ... < Ig be the steps in which times Sn 4 + for n E [1, ...2....411 - 1 - 1]. all those steps no update takes place and xs,, = X We must have ds, for all (otherwise
update is made. Denote to = 0 and fx+1 = T. Now, fix i and consider the steps at
X;-d; for r Sn and an update occurs). In particular we have that ds, 2 2r in at least f/41 -1 f,- - 1 2r steps in [tr, 4+1]. Hence,
k-
U2r 2
(114 4 2r) = k(1 2T).
Finally, it follows that T - A(1 + 2r) s 7/2 which implies k 2
T a(r+1)
Given the lemma above, we prove Lemma by showing that if the algorithm fails, it makes many updates all of which we have [x;]( e. By Lemma this means that in the T time steps of the algorithm, it must decrease the value of ff significantly. Since we start at point in which f(x) & F, we must conclude that T' cannot be too large.
Proof of Lemma 3. Combining Eq. (3) with 17 1/(6)) and Lemma 4, we get that if the algorithm fails with probability 2 then
EA,
ELIVSGO)
E
Σ
I
16B
168
[=1
1=1
é²
2 T
LIIV F=1
algorithm fails
2
E
Σ
4
algorithm fails
2
3266
326
326
4(T 1)*
f=1
This yields the lemma's statement.

---

4.2 Case (ii): >
This is the "high noise" regime. For this case, we prove the following guarantee for the convergence of our algorithm.
Lemma 5. Assume that > and the algorithm fails with probability 2 1. Then,
I
T
E²
et
EA, 2
min
500
02
1=1
In particular,
T s 500
T
0²) +
c ca
This result is attained using the following observation. Consider the iterate of algorithm at time X and the point at which the gradient was computed x = x,-d,- We claim that the algorithm has not decreased the function value sufficiently during the interval [r d,, / 1J. then it is likely to trigger large decline in the function value at time Formally, either EA, is large, or E EA, is large. To show the claim, we first upper bound the distance ||xx, xxy1l in terms of Li=rd, EA, as shown by the following technical lemma.
Lemma 6. For all t and k, it holds that
r+k-1
r4k-1
Σ EAi-
E||x, Xp+&|1 S
EA +
6
1=1
Proof. We have
--
r+k-1
r-k-1
E||x, Xx+k n/
L(V(()) + No)
TE
1Vf(())
+nE
Σ
I.
i=t
We continue bounding the second term above as follows:
r4k
1-1
p+k-1
E
I.N
E
IN
[+k
1
HINN
N
J=
r+
2
(E(N, 1,1,N, for i f)
14K
E
1
T4k-1
0
(VV 2 when I; = 1)
E=1
1602B
14k-1
EA
(Eq. (3), 11 = e//400²
2
1=1
2
r+k-1
B
Ed:
22
7

---

EAi.
( e
1=1
and
1+
r+K-1
1 (
M
f
r+k-1
E
(VV 2 when I; = 1)
is
1+k-1
4
EA,-
(Eq. (3))
CT
This completes the proof.
Given the lemma above, is now clear that Ei---d EA is sufficiently small, then Eljx, - x/1l < e/B which means that the algorithm is likely (with constant probability) to take step at time 1. This argument yields the following.
Corollary 7. Assume that the algorithm fails with probability 1/2 If EA, < e2/125p then EA, 2 e /6462².. In particular,
e² e4
EA,
+
Edi
min
2T
2506
Proof. If Ei EA, 12/125p. then Ellxy-d, x,1 S c/8p by Lemma 6. By Markov inequality, with probability 2 2. we have 1|xr-d, xxll S e/2p. Since the probability that [Vf(xx-a))) aI > is at least 4. we get that EI, 2 1. By Lemma 2 this implies that
...2
EA, 2
1602 64a2B'
which yields our claim.
We now prove our main claim. We show that if the algorithm fails, then in all time steps in which d, s 2r (of which there are at least 7/2), either the algorithm makes substantial step, or it has made significant updates in the interval [r - d,, - 1]. In any case, the function value must necessarily decrease overall in the time steps of the algorithm, concluding that cannot be too large.
Proof of Lemma 5. We have,
EA
EAi-
2T
Esdly 52r
i=t-d4
Hence, using Corollary 7,
Σ
FA 2
EA, +
EA
2T
tid, 52r
i=1-4
1
et x2
(1 : d, S 2T)
min
250B
T
c et
min
2 250p
T min
c ct
500B
r 02
where we used Markov's inequality to show that (t s 2r 2 ŞT.

---

4.3 Concluding the proof
Proof of Theorem 1. In the case o S e, Lemma 3 implies that if > 128 + 1)/e² then the algorithms succeeds with probability greater than 1/2, which yields the theorem in this case, Similarly, Lemma 5 gives our claim in the case when a > c.
5 Experiments
To illustrate the robustness and efficacy of Picky SGD, we present a comparison between the performance of SGD versus Picky SGD under various delay distributions. In particular, we show that Picky SGD requires significantly less iterations to reach a fixes goal and is more robust to varying delay distributions.
5.1
Setup
The main goal of our experimental setup is to be reproducible. For that end, the experimentation is done in two phases. First, we perform simulation to determine the delay d, at each iteration without actually computing any gradients: this is done by simulating N concurrent worker threads sharing and collectively advancing global iteration number, where each worker repeatedly records the current global iteration number Tsttt waits a random amount of time from a prescribed Poisson distribution, then records the new global iteration number t fend and the difference d, fend sstart and increases the global iteration number. This information (a delay schedule) is calculated once for each tested scheme (differing in the number of workers and random distribution, as detailed below), and is stored for use in the second phase.
In the second phase of the experiments, the algorithms SGD and Picky SGD are executed for each delay schedule. Here, at every iteration the gradient computed (if needed) and is kept until its usage as dictated by the schedule (and then applied at the appropriate global iteration number). As a result of this configuration, we get a fully reproducible set of experiments, where the algorithms performance may be compared as they executed over identical delay series of identical statistical properties.
We created four different delay schedules: A baseline schedule (A) using N = 10 workers and sampling the simulated wait from Poisson distribution (this schedule serves to compare Picky SGD and SGD in a setting of relatively small delay variance) and schedules (B) (C) and (D) all using N = 75 workers and sampling the simulated wait from bi-modal mixtures of Poisson distributions of similar mean but increasing variance respectively.4 See Figure 2 in the the full version of the paper [? ] for an illustration of the delay distributions of the four delay schedules used.
All training is performed on the standard CIFAR- 10 dataset [15] using a ResNet56 with 9 blocks model [13] and implemented TensorFlow [1]. We compare Picky SGD (Algorithm 1) to the SGD algorithm which unconditionally updates the state given the stochastic delayed gradient gr (recall that 8, is the stochastic gradient at state x,,
For both algorithms, instead of a constant learning rate 7) we use a piecewise- linear learning rate schedule follows: we consider baseline пo piecewise- linear learning rate schedule that achieves optimal performance in a synchronous distributed optimization setting (that is, for d, = 0) and search (for each of the four delay schedules and each algorithm- delays) for the best multiple of the baseline rate and the best first rate-change point. Alternatively, we also used a cosine decay learning rate schedule (with the duration of the decay as meta parameters). Another meta- peraam-r we optimize is the threshold e/ e/22p) in line 4 of Picky SGD. Batch size 64 was used throughout the experiments. Note that although use chose the threshold value e/2p by an exhaustive search, in practice, a good choice can be found by logging the distance values during a typical execution and choosing a high percentile value. See the full version of the paper [? ] for more details
compensate for the effects of
*Note that up to the training data ordering a computation of steps of Picky SGD or SGD is uniquely determined by the starting state xi and the sequence [1 [ dr
*See the the full version of the paper [? for specific parameter values and implementation details. sWith rate changes at three achieved accuracy points 0.93, 0.98, and 0.99. o This also the best performance achievable in an asynchronous setting.

---

100p 500
120ch
03
560
Patyy 5G0
opach
<poch
Figure I: Accuracy trajectory (with zoom-in on the tail of the convergence) over train epochs for the four delay schedules of Fig. 2, respectively: the key metrics (reported in Table 1) for each trajectory epochs to reach 0.99 accuracy (the number of epochs required to reach the 0.99 accuracy mark) and the baseline learning rate multiplier n//10-
5.2 Results
The accuracy trajectory for the best performing combination of parameters of each algorithm for each the four delay schedules shown in Fig. and summarized Table 1. Clearly, Picky SGD significantly outperforms SGD in terms of the final accuracy and the number of epochs it takes to achieve it. We also emphasize that the generalization performance (that is, the evaluation accuracy not observed to vary across delay schedules the applied
related to the training accuracy) algorithms (see e.g., Fig. 4 in the the full version of the paper ? 1), and that the nature of the results more pronounced when using the alternative cosine decay learning rate schedule (see Fig. 5 in the the full version of the paper ?? D). Specific details of the meta parameters used, and additional performance figures are reported in the full version of the paper ].
Table 1: Summary of the key metrics from Fig. for each of the four delay schedules A, B, C, and D.
Epochs to 0.99%
LR multiplier (1/m1)
Picky SGD
SGD
Picky
SGD
SGD
A
344
350
0.5
0.5
B
333
451
0.2
0.05
337
438
0.2
0.05
288
466
0.2
0.05
5.3 Discussion
We first observe that while the number of epochs it takes Picky SGD to reach the target accuracy mark almost the same across the delay schedules (ranging from 288 344), SGD requires significantly more epochs to attain the target accuracy (ranging from 350 up to 466 for the highest variance delay schedule) this is consistent with the average-delle delay bound dependence of Picky SGD (as stated in Theorem 1) compared to the max-delay bound dependence of SGD. Furthermore, the best baseline learning rate multiplier meta-parameter for Picky SGD is the same (0.2) across all high-variance delay schedules, while the respective meta parameter for SGD is significantly smaller (0.05) and sometimes varying, explaining the need for more steps to reach the target and evidence of Picky SGD superior robustness.
10

---

Acknowledgements
AD is partially supported by the Israeli Science Foundation (ISF) grant 2258/19. TK is partially supported by the Israeli Science Foundation (ISF) grant no. 2549/19, by the Len Blavatnik and the Blavatnik Family foundation, and by the Yandex Initiative in Machine Learning.
References
[1] Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Ian Goodfellow, Andrew Harp, Geoffrey Irving, Michael Isard, Yangqing Jia, Rafal Jozefowicz, Lukasz Kaiser, Manjunath Kudlur, Josh Levenberg. Dandelion Mané, Rajat Monga, Sherry Moore, Derek Murray, Chris Olah, Mike Schuster, Jonathon Shlens, Benoit Steiner, Ilya Sutskever, Kunal Talwar, Paul Tucker, Vincent Vanhoucke, Vijay Vasudevan, Fernanda Viégas, Oriol Vinyals, Pete Warden, Martin Wattenberg, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. TensorFlow: Large-scale machine learning heterogeneous systems, 2015. URL ht h/tp:///wwwww. wttp://www.o.f....o///..e...o www.w/wwwwwwwwwwoooooooooooo.... Software available from tensorflow.org.
[2] Alekh Agarwal and John C Duchi. Distributed delayed stochastic optimization. In 2012 IEEE 51 IEEE Conference on Decision and Control (CDC), pages 5451-5452. IEEE, 2012.
[3] Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. Qsgd: communication--eficieent sgd via gradient quantization and encoding. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pages 1707-1718, 2017.
[4] Yossi Arjevani, Ohad Shamir, and Nathan Srebro. A tight convergence analysis for stochastic gradient descent with delayed updates. In Algorithmic Learning Theory, pages 111-132. PMLR, 2020.
[5] Rotem Zamir Aviv, Ido Hakimi, Assaf Schuster, and Kfir Yehuda Levy. Asynchronous distributed learning Adapting to gradient delays without prior knowledge. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 436-445. PMLR, 18-24 Jul 2021. URL https://proceedding www.:/rrweeeiiinmm.......mm mlr. www.:rees........m...m..mme 139/ awiaaia.
[6] D.P. Bertsekas and J.N. Tsitsiklis. Parallel and Distributed Computation: Numerical Methods. Athena Scientific, 1997.
[7] Sorathan Chaturapruck, John Duchi, and Christopher Ré. Asynchronous stochastic convex optimization: the noise is in the noise and sgd don't care. Advances in Neural Information Processing Systems, 18:1511- 2015.
[8] Andrew Cotter, Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Better mini-batch algorithms via accelerated gradient methods. In Proceedings of the 24th International Conference on Neural Information Processing Systems, pages 1647-1655, 2011.
[9] Ofer Dekel, Ran Balad-Bachrach, Ohad Shamir, and Lin Xiao. Optimal distributed online prediction using nithebatches. Journal of Machine Learning Research, 13(1), 2012.
[10] John C Duchi, Peter L Bartlett, and Martin J Wainwright. Randomized smoothing for stochastic optimization. SIAM Journal on Optimization. 22(2):674-701, 2012.
[11] Hamid Reza Feyzmahdavian, Arda Aytekin, and Mikael Johansson. An asynchronous mini-bated algorithm for regularized stochastic optimization. IEEE Transactions on Automatic Control, 61 (12):3740-3754, 2016.
[12] Saced Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341-236 2013.
[13] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
11

---

[14] Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian Stich, and Martin Jaggi. Error feedback fixes signsgd and other gradient compression schemes. In International Conference on Machine Learning, pages 3252-3261. PMIR, 2019.
[15] A. Krizhevsky. Learning multiple layers of features from tiny images. Technical report,, Computer Science Department, University of Toronto, April 2009.
[16] Guanghui Lan. An optimal method for stochastic composite optimization. Mathematical Programming. 133(1):365-397, 2012.
[17] Rémi Leblond, Fabian Pedregosa, and Simon Lacoste-Julien. Improved asynchronous parallel optimization analysis for stochastic incremental methods, Journal of Machine Learning Research, 19:1-68, 2018.
[18] Xiangru Lian, Yijun Huang. Yuncheng Li, and Ji Liu. Asynchronous parallel stochastic gradient for nonconvex optimization. In Proceedings of the 28th International Conference on Neural Information Processing Dystems-Volune 2, pages 2737-2745, 2015.
[19] Horia Mania, Xinghao Pan, Dimitris Papailiopoulos, Benjamin Recht, Kannan Ramchandran, and Michael Jordan. Perturbed iterate analysis for asynchronous stochastic optimization. SIAM Journal on Optimization, 27(4):2202-227 2229, 2017.
[20] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-efice learning of deep networks from decentralized data. In Artificial Intelligence and Statistics, pages 1273-1282. PMLR, 2017.
[21] Angelia Nedić, Dimitri P Bertsekas, and Vivek S Borkar. Distributed asynchronous incremental subgradient methods. Studies Computational Mathematics, 8(C):381 407, 2001.
[22] Yurii Nesterov. Introductory lectures on convex optimization: A basic course, volume 87.
Springer Science & Business Media, 2003.
[23] Yurii Nesterov et al. Lectures convex optimization, volume 137. Springer, 2018.
[24] Feng Niu, Benjamin Recht, Christopher Re, and Stephen J Wright. Hogwild! lock-free approach to parallelizing stochastic gradient descent. In Proceedings of the 24th International Conference Neural Information Processing Systems, pages 693-701, 2011.
[25] Sashank Reddi, Ahmed Hefny, Suvrit Sra, Barnabás Pöczos, and Alex Smola. On variance reduction in stochastic gradient descent and its asynchronous variants. In Proceedings of the 28th International Conference on Neural Information Processing Systems- 2, pages 2647-2655, 2015.
[26] 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.
[27] 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 on Machine Learning, pages 10334-10343. PMLR, 2020.
[28] Kaiwen Zhou, Fanhua Shang, and James Cheng, A simple stochastic variance reduced algorithm with fast convergence rates, In International Conference on Machine Learning, pages 5980-5989, PMLR, 2018
12


Reviews:
[{"review_id": "yZ-SFRbpjyh", "reviewer": "Reviewer_Y4g4", "summary": "This paper considers the problem of distributed stochastic asynchronous optimization, in which workers send delayed stochastic gradients to a server. The focus is on non-convex smooth objectives, although results for convex objectives are provided in the supplementary material. \n\nStandard asynchronous distributed SGD algorithms are first discussed, and the authors highlight that their step-size (and thus, also their iteration complexity) depends on a bound over the maximum possible delay over all iterations. Instead, this paper introduces an algorithm that does not require to know this bound, and only depends on the average observed delay.\n\nThis algorithm is called Picky-SGD, and its main difference with standard delayed SGD is that the update is only performed if the delayed iterate is close enough to the current iterate. Theoretical results are then given to show that Picky-SGD achieves the standard complexity results for these problems, but replacing the maximum delay by the average one. The proof is then presented in details, and a set of experiments is given to illustrate the superiority of Picky-SGD over delayed SGD. \n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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": "", "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": "The introduction is very well written, quite thorough, and clear. The contributions (both the algorithm and its analysis) are interesting contributions to this field, and could be leveraged beyond this setting. \n\nThe global approach is very intuitive but also quite efficient. Standards algorithms assume a bound on the maximum delay $\\tau$, and they reduce the step-size accordingly so that $x_{t - \\tau_{\\max}}$ is never too far from the current iterate $x_t$ even in the worst case, so that the gradient at $x_{t - \\tau_{\\max}}$ remains relevant. On the other hand, Picky-SGD directly verifies a condition on $\\||x_{t - \\tau} - x_t\\||$ at each step, and thus avoids having to lower the step-size too much. \n\nAlthough this seems conceptually simple, work is then needed to show that the algorithm does not discard too many gradients and converges fast enough. \n\nIn Picky-SGD, the knowledge of $\\tau_\\max$ is replaced by the knowledge of a target accuracy for the algorithm. Yet, this is still a hyperparameter to tune, and generally an extra one compared to standard delayed SGD since the bound on the delay only appeared in the step-size, which is generally tuned anyway. I believe that the authors should be significantly more straightforward about this limitation, since it is not so clearly stated anywhere. \n\nSimilarly, it is expected that the Picky SGD algorithm outperforms standard delayed SGD since it recovers it when taking $A \\rightarrow \\infty$ (with the notations of Appendix C.2.2), which corresponds to accepting all iterations. It is good to show that introducing this extra degree of freedom via the acceptance threshold actually helps, but it seems to be at the cost of extra tuning. Again, I believe that this paper would benefit from highlighting this more clearly. \n\nI would be interested in the practical performances of Picky-SGD in the convex / strongly convex cases, in which the theoretical parameters can generally be used (more than in the non-convex case at least), and so in which SGD and Picky-SGD could be compared in a (almost) tuning-free setting. I do not specifically ask for this kind of experiments in the rebuttal though.    \n\nOther comments:\nI believe that there is a typo in the proof of Lemma 4 (Line 188) in that Markov Inequality should guarantee that $U_{2\\tau} \\leq T/2$ (and not the other way round). This is consistent with the statement of line 193. \n\nThe reference following reference could be relevant:\nHannah, Robert, and Wotao Yin. \"On unbounded delays in asynchronous parallel fixed-point algorithms.\" Journal of Scientific Computing 76.1 (2018): 299-326.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No foreseeable societal impact", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "XBd1VP34AQG", "reviewer": "Reviewer_v3Nq", "summary": "This paper proposes a distributed SGD algorithm, called Picky SGD, for asynchronous implementation of SGD with multiple workers and arbitrary delays. Compared to prior works which analyzed a plain SGD algorithm, the main advantage of picky SGD is that it has a tighter complexity bound of $O(\\sigma^2/\\epsilon^4 + \\tau_{avg}/\\epsilon^2)$ instead of $O(\\sigma^2/\\epsilon^4 + \\tau_{max}/\\epsilon^2)$ as in the prior work. ", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "", "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": "As mentioned above, the main contribution of this paper is a new algorithm with improved complexity bound with respect to the delays in the asynchronous algorithm. The main idea is to perform a selective SGD update only made when the transmitted stochastic gradient is computed from an iterate that is \"close\" to the current one at the server. The proof seems to be follow from standard analysis of distributed SGD (and actually SGD in general). Numerical experiments seem to indicate a better performance of the proposed algorithm compared to standard SGD. \n\nThe reviewer has the following comments:\n\n- The reviewer is concerned with the practicality of the proposed algorithm and the theoretical result provided in the study. \n\nFirst, it should be noted that at every update, the worker has to send both $x_{t-d_t}$ and $g_t$ to the server which involves a doubled communication cost. In addition, given this additional requirement on the communication protocol, it is unclear if the proposed algorithm can be extended to be used with compression, e.g., as studied in [25]. \n\nSecond, the current proof in the paper only analyzes the time complexity with a success probability of greater than 1/2. After Theorem 1, it is stated that this success probability can be \"amplified\" to $1-\\delta$ for any $\\delta > 0$ by repeating the algorithm with $T$ iterations and \"running through a point with gradient norm $\\leq \\epsilon$\". Such scheme appears to be impractical since it involves checking the gradient norms of the iterates, e.g., a distributed system where the gradient is only posessed by the workers and the latter can only be accessed through a stochastic oracle. In general, such existence proof for an $\\epsilon$-stationary point is in contradiction to the stochastic gradient and distributed optimization setting, as it may result in an impractical scheme.\n\nAs a minor point, it should be noted that the algorithm requires an estimate of $\\beta$ and the desired $\\epsilon$ as an input to run the algorithm, which are hard to determine-a-priori in practice. \n\n- In the convergence analysis, there are several confusing technical statements which require further clarifications:\n\n-- On page 5, it is stated that $I_t = 1$ implies $|| \\nabla f(x_s) || \\geq \\epsilon$ for $s=1,...,t$. Why is this true? This statement doesn't seem to hold in general. \n\n-- In the proof of Lemma 4, it is not clear what does it mean by \"By Markov Inequality, $U_{2\\tau} \\geq T/2$\". To the reviewer's best knowledge, the Markov's inequality bounds the probability of the event that a certain non-negative r.v. is greater than a certain constant. Yet in the statement of Lemma 4 nor in the proof of the lemma, there is no specification of any random event nor its probability. Perhaps the reviewer has missed something from the lemma's statement or from the proof, but at the moment I am unable to deduce the said statement. \n\n-- Also in the proof of Lemma 4, it is stated that $U_{2\\tau} \\geq T/2$ and $U_{2\\tau} \\geq T - k(1+2 \\tau)$ imply the statement $k \\geq T/4(\\tau+1)$. Again, the reviewer fails to see why this hold. It seems that the statement would hold instead if $U_{2 \\tau} \\leq T/2$. \n\n-- The proof of Lemma 3 applies Lemma 2. However, the independence between the stochastic gradients and the iterates should be handled carefully. In particular, Lemma 2 requires $x$ and $N$ to be independent random variables. This may not be the case when the lemma is applied in the proof of Lemma 3. Particularly, the latter involves $x = x_t$ and $N = g_t - \\nabla f(x_{t - d_t})$ which may not be independent from each other. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There isn't any potential negative societal impact. The limitation/suggestions for improvement have been discussed in the main review above.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "UwaPLDL2IYN", "reviewer": "Reviewer_iRiS", "summary": "This paper gives an alternative to SGD, called picky SGD, for stochastic optimization with delays. While Stich & Karimireddy proved that SGD was robust to delays as long as the maximum delay is controled, here picky SGD is proved to be robust to much larger delays, as it requires only the average delay (and not the maximum delay) to be controled. This is supported by both theoretical convergence to a stationary point (in the non-convex case) or to a minimum (in the convex case) and with simulations with artificially introduced delays. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "", "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": "The authors expose clearly their results. The simulations show an important improvement of picky SGD over SGD. However, the code is not provided, thus reproducing the experiments would be quite tedious. \n\nAs the central objective of the paper is to replace the dependence in the maximum delay by the average delay, it is natural to ask what empirical evidence do we have that in practical distributed systems, the distribution of delays is heavy tailed. Do you have experiments or references supporting this? The simulations are for heavy-tailed delays that are introduced artificially, thus we could wonder if such delays occur in practice. \n\nThe paper presents their result as a variation over a result of Stich & Karimireddy. However, this papers studies more generally non-uniformly bounded noises (their assumption 3). Stich & Karimireddy explain at great length why this is more relevant to machine learning practice. However, the authors of these papers restrict themselves to uniformly bounded noise, with no comment on this restriction. Could you elaborate? \nAlso, while the theoretical result is well compared with the one of Stich & Karimireddy, the difference in the proof technique is not commented. Is it a variation over the same proof technique? Does picky SGD require completely different techniques? \n\nFinally, I did not succeed in understanding the proof of Theorem 1. It might be only miskates on my side, but I think I need a clarification from the authors.\nMostly, I do not understand the paragraph of l. 159-164. \n- What does it mean for the algorithm to \"fail\"? Does it happen when the algorithm has not found a critical point in a given number of iterations? What is this number of iterations? \n- I do not understand the statement \"the guarantee of Theorem 1 is valid for this variant if and only if it is valid for the original algorithm\". Is it proved somewhere? \n\nIn my attempt to understand the definition of \"fail\", I read the proof of Lemma 4 (I thought that I could understand the statement from the proof). In this proof, two lower bounds are derived for U_{2\\tau}. How can you conclude on an inequality between those two bounds?\nAlso, could you detail the application of Markov inequality? As the delays are arbitrary (and not random), U_{2\\tau} is deterministic and I do not understand how Markov inequality intervenes here. \n\n\nMinor comments:\n- l.70: was it necessary to know \\tau_max in the work of Stich and Karimireddy?\n- why do you assume the function to be non-negative?\n- l.151-155: when amplifying, how do you know which of the final points is successful? Gradients are stochastic thus is it not obvious to test if a point is an approximate critical point.\n\n\n----------- \nI increased my grade after the rebuttal, see below an updated review. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The articulation with the result of Stich & Karimireddy is not detailed enough. I gave suggestions for improving this in the main review. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "MO0qHuRhG65", "reviewer": "Reviewer_TNHX", "summary": "This paper improves the iteration complexity to get $\\epsilon$ small gradients for smooth non-convex functions using SGD with delayed gradients. This setting, in particular, captures asynchronous distributed SGD. The previously known best algorithm [1] accumulates error feedback to provide a $\\sigma^2/\\epsilon^4 + \\tau_{max}/\\epsilon^2$ rate, where $\\tau_{max}$ is the maximum delay in any update. This can be catastrophic in cross-device federated learning with edge devices, where a device gets disconnected for multiple rounds, and then sends its gradient for the update. \n\nThis paper deals with such a scenario in a very simple manner, by measuring the distance between the current iterate and the old iterate at which the gradient was computed, and making the update only if it is smaller than a threshold value. This algorithm is aptly called *picky SGD*. Surprisingly, this removes the need for error feedback and is able to guarantee a $\\sigma^2/\\epsilon^4 + \\tau_{avg}/\\epsilon^2$ rate where $\\tau_{avg}$ is the average delay over all the rounds. Picky SGD with a different threshold also offers state-of-the-art convergence rates for convex smooth functions, with the dependence on the maximum delay changed to the one on average delay.\n\nThe authors also study the effect of sampling the delays from distributions with different levels of variance in their experiments. The results demonstrate that picky SGD requires comparable or fewer steps to reach a fixed level of accuracy than vanilla asynchronous SGD. This is attributed to the fact that picky SGD tolerates a much larger step size than asynchronous SGD.\n\n\n\n**References**\n\n[1] Stich, Sebastian U., and Sai Praneeth Karimireddy. \"The error-feedback framework: Better rates for SGD with delayed gradients and compressed communication.\" arXiv preprint arXiv:1909.05350 (2019).", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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": "", "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": "This is a well-written paper, with a clear description of the goals, contributions, results, and proof sketch. The proposed algorithm is in fact simpler (albeit at the cost of storing the past iterates) than the error-corrected SGD but still improves upon its convergence guarantee, making the upper bound *data-dependent*. I have some concerns though, and I would be happy to increase my score if they are resolved. \n \n1) Can the analysis be extended to a more general noise model like the strong growth model as in [1]? \n\n2) In the theoretical guarantees the paper compares to error-correcting SGD. However, why was it not included as a baseline in the experiments?\n\n3) It is useful to see the magnified tail of the plot, but it might make more sense to plot the y-axis on a log scale. Further, the experiments should be repeated multiple times to kill some noise in the curves and understand the variance of these algorithms. In fact, it would be good to include repetitions for the same delay schedule as well as different delay schedules sampled from the same distribution. \n\n4) It is not clear how the algorithms stop making updates in the experiments. Were they stopped after reaching a particular target accuracy? It doesn't seem to be the case looking at the figure. In setting (D) SGD stops earlier and vice versa for setting (C).  \n\n5) While picky SGD is simpler to analyze and discuss in theory, it has two limitations in practice. First tuning the for the threshold $\\epsilon/2\\beta$, and second storing the past iterates only up to some point in history. How to go around these issues in practice? It is important to show how robust the algorithm is to each of these choices. Also, since memory costs can often be the bottleneck, some wall clock time experiments would also be useful, again over some reasonable range of the tunable parameters. These limitations can make EC-SGD [1] a better choice in some settings because we need to tune it as much as usual SGD. \n\n**Typos**\n\n1) L58 previous art -> previous state of the art\n\n2) L283 SGD -> SGD's\n\n# Final Verdict\n\nI liked this paper overall except for some minor concerns and suggestions. They have been addressed, and the authors have promised to add some important discussions in the revised version. In light of that, I am improving my score. \n\n\n**References**\n\n[1] Stich, Sebastian U., and Sai Praneeth Karimireddy. \"The error-feedback framework: Better rates for SGD with delayed gradients and compressed communication.\" arXiv preprint arXiv:1909.05350 (2019). \n \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Some experimental limitations as mentioned in the main review. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies the convergence of gradient descent with delayed updates. While most prior results depended on a parameter corresponding to the largest encountered delay, this paper derives convergence analysis depending on just the average delay.
The presented algorithm does not need to know the average delay parameter beforehand.

The reviewers found this an overall solid technical contribution and recommend acceptance. 

The authors are strongly encouraged to take the reviewer's feedback into account when preparing the revision, as a few concerns remain:
- reviewer v3Nq spotted some inaccuracies in the proofs, which the author's promised to fix
- while indeed prior methods need 'to know' the maximum delay to set the theoretical step size, in practice the tuning is limited to a single parameter only (the stepsize). The proposed scheme has two hyperparameters (stepsize and threshold), and the reviewers concerns on practical benefits seem justified. It would be great if these comments could be addressed diligently in the revision.

Additionally, I would encourage the authors to comment on the concurrent work [[Aviv et al, Learning Under Delayed Feedback: Implicitly Adapting to Gradient Delays, ICML 2021](http://proceedings.mlr.press/v139/aviv21a/aviv21a.pdf)] published at ICML earlier this year. It would be great to explain the key differences and similarities of the proof techniques and results to the readers.

Decision: Accept (Poster)