Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learning
Authors: Anastasia Koloskova
Sebastian U Stich
Martin Jaggi
Venue: NeurIPS 2022 Accept (2022)
Keywords: asynchronous SGD
delayed SGD
stochastic optimization
Federated Learning
distributed optimization

Abstract: We study the asynchronous stochastic gradient descent algorithm, for distributed training over $n$ workers that might be heterogeneous. In this algorithm, workers compute stochastic gradients in parallel at their own pace and return them to the server without any synchronization.

Existing convergence rates of this algorithm for non-convex smooth objectives depend on the maximum delay $\tau_{\max}$ and reach an $\epsilon$-stationary point after $O\!\left(\sigma^2\epsilon^{-2}+ \tau_{\max}\epsilon^{-1}\right)$ iterations,  where $\sigma$ is the variance of stochastic gradients. In this work (i) we obtain a tighter convergence rate of $O\!\left(\sigma^2\epsilon^{-2}+ \sqrt{\tau_{\max}\tau_{avg}}\epsilon^{-1}\right)$ *without any change in the algorithm* where $\tau_{avg}$ is the average delay, which can be significantly smaller than $\tau_{\max}$. We also provide (ii) a simple delay-adaptive learning rate scheme, under which asynchronous SGD achieves a convergence rate of $O\!\left(\sigma^2\epsilon^{-2}+ \tau_{avg}\epsilon^{-1}\right)$, and does not require any extra hyperparameter tuning nor extra communications. Our result allows to show *for the first time* that asynchronous SGD is *always faster* than mini-batch SGD. In addition, (iii) we consider the case of heterogeneous functions motivated by federated learning applications and improve the convergence rate by proving a weaker dependence on the maximum delay compared to prior works.

Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learning
Anastasia Koloskova EPFL
Sebastian Stich
Martin Jaggi EPFL martin. jrriinjjagiiepfl.... ch
CISPA stich@cispa.de
anstasiia.Kolookova@@ppt..
Abstract
We study the asynchronous stochastic gradient descent algorithm for distributed training over workers which have varying computation and communication frequency over time. In this algorithm, workers compute stochastic gradients in parallel at their own pace and return those to the server without any synchronization. Existing convergence rates for this algorithm for non-convex smooth objectives depend on the maximum gradient delay Tmax and show that an e-stationary point is reached after ( + Tmax iterations, where denotes the variance of stochastic gradients. In this work
tighter convergence rate of 0 v T without any change in the algorithm, where Tang is the average delay, which can be significantly smaller than Tmax- We also provide (ii) simple delay-adaptive learning rate scheme, under which asynchronous SGD achieves a convergence rate of O + TaugE =1)ge-)). and does not require any extra hyperparameter tuning nor extra communications. Our result allows to show for the first time that asynchronous SGD is always faster than mini-batch SGD. In addition, (iii) we consider the case of heterogencous functions motivated by federated learning applications and improve the convergence rate by proving a weaker dependence on the maximum delay compared to prior works. In particular, we show that the heterogeneity term in convergence rate only affected by the average delay within each worker.
obtain
Introduction
The stochastic gradient descent (SGD) algorithm 43 13
and its variants (momentum SGD, Adam, etc.) form the foundation of modern machine learning and frequently achieve state of the art results. With recent growth in the size of models and available training data, parallel and distributed versions of SGD are becoming increasingly important [57] 17 16). Without those, modern state-of-the art language models 44 generative models 440 41. and many others
(50) would not be possible. In the distributed setting, also known as data-parallel training, optimization is distributed over many compute devices working in parallel (e.g. cores, GPUs cluster) in order to speed up training. Every worker computes gradients on a subset of the training data, and the resulting gradients are aggregated (averaged) on server.
The same type of SGD variants also form the core algorithms for federated learning applications [34 24 where the training process is naturally distributed over many user devices, or clients, that keep their local data private, and only transfer (e.g. encrypted or differentially private) gradients to the server.
rich literature exists on the convergence theory above mentioned parallel SGD methods, see e.g. 17 3 and references therein. Plain parallel SGD still faces many challenges in practice, motivat-
CISPA Helmholtz Center for Information Security
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

ing research on various approaches to improve efficiency of distributed learning and mini-batch SGD. This includes for example communication compression techniques [2] 48 49). decentralized com-
munication 22 7 36
26
or performing several local SGD steps on workers before communicating
with the server 30
47
These approaches
synchronous communication, where workers in each round are required to wait for the slowest one, before being able to start the next round of computations. In the presence of such straggler nodes or nodes that have different computation speeds, other workers face significant idle times. Asynchronous variants of SGD are aimed to solve such inefficiencies and use available workers more effectively. In asynchronous SGD, each worker starts the next computation immediately after finishing computing its own gradient, without waiting for any other workers. This especially important in the presence of straggler nodes. Asynchronous algorithms were studied In this paper we focus on such challenging asynchronous variants of SGD and provide an improved theoretical analysis of convergence compared to prior works.
both in distributed and federated learning settings [42 31 27
46 37
Most existing work has studied the convergence behavior of asynchronous SGD for the setting of homogeneous distributed training data, where worker's objectives are i.i.d.. This assumption however is only realistic e.g. in shared- implementations where all processes can access the same data 42 Under this assumption, can be proven that asynchronous SGD finds an - + Imax iterations [48], gz the maximum delay
approximate stationary point (squared gradient norm bounded by E) in O ( for smooth non-convex objective functions. This complexity bound depends of the gradients Taax and the gradient variance a >> 0. Unfortunately, the maximal delay is a very pessimistic metric, not well reflecting the true behavior in practice. For instance, if a worker struggles just once, the maximum delay is large, while we would still expect reasonable overall convergence.
Two recent works [15 9 tackle this issue by proposing two new delay-adaptive algorithms that achieve a convergence rate that depends only on the average delay of the applied gradients, with Aviv et al.
[9] considering only the convex optimization and Cohen et al. [15] providing a rate of O + Tavg for smooth non-convex functions. The average delay can be much smaller than the maximal delay, and thus these methods are robust to rare stragglers. However, Cohen et al. [[5] requires twice more communications at every step, and an extra hyperparameter to tune. Aviv et al. [9] analyze only convex functions and assume a bound on the variance of the delays, which can frequently degrade with the maximum delay Tmax. Moreover, both works require the assumption that gradients are uniformly bounded.
In the realistic case of heterogeneous objective functions, that is in particular relevant in federated learning applications [24]. all the existent convergence rates of asynchronous SGD depend on the maximum delay 377
Contributions.
For standard asynchronous SGD with constant stepsize, and with non-convex L-smooth homo- geneous objective functions, we prove the tighter convergence rate of O + //Tv to e-small error. Under the additional assumption of bounded gradients, we obtain convergence G
rate of ( 2 Tavg
Tave)
where G is the bound on the norm of gradients. The previously
best known rate was ( + Imaxx
With homogeneous objective functions, we provide delay-adaptive stepsize scheme that does not require tuning of any extra hyperparameters, and converges at the rate of O + Janz for non-convex L-smooth functions.
This result allows show that asynchronous SGD is always better than mini-batch SGD regardless of the delays pattern (under assumption that the server can perform operations with zero time).
We also consider distributed optimization with heterogeneous objectives where the delays can depend on the workers and give the convergence rate of Ox + S + Toup 1 Ln Crr
VTag Tmax , where Çi's measure functions heterogeneity and F; is the average delay of worker i. This rate improves over the best sreviously-known results that had worse dependence on the maximum delay Tmax-
2

---

2 Related Work
Asynchronous SGD. The research field of asynchronous optimization can be traced back least to 1989 (.T]. Recent works are heavily focused on its SGD variants, such as Hogwild! SGD [39] which deals with coordinate- analysis by removing the bounded gradient assumption. Our work does not focus on such coordinate- wise asynchrony as relies on sparsity assumption that is not realistic in modern machine learning applications. Mania et al. [31 introduces the perturbed iterate framework which enabled theoretical advances with tighter convergence rates
asynchronity. Nguyen et al. [8] provided a tighter convergence
48 46). Leblond et al. [27 focus on asynchronous variance-
reduced methods.
28, 48 18 focused on asynchronous SGD variants where workers communicate with the server without any synchronization, but these communications are considered to be atomic. All of these works provide convergence guarantees that depend on the maximum delay Tmax with 6 48 providing the first tight convergence rates under assumption that the delays are always constant for quadratic and general (convex, strongly convex and non-convex) functions correspondingly. Stich al. (46] showed a connection of large batches and delays, although still depending only on the maximum delay. Even et al. [19] consider a continuized view of the time (rather than classical per-iteration time) for asynchronous algorithms on a decentralized network. 3) improve the convergence rates of asynchronous SGD to depend Vmmax however assuming bounded gradients. Under bounded gradients our convergence rates completely remove dependence on the maximum delay Tmax.
Many works [ 14 20
Delay-adaptive methods. The works [56 55 45 51 33 [8] considered delay-adaptive schemes to mitigate adversarial effect of stragglers, however with convergence rates that still depend on the maximum delay Tmax- Only Cohen et al. [15] in the non-convex, and Aviv et al. 9 in the convex case able obtain convergence rates depending on the average delay Tavg- Concurrent to stepsize scheme and derive convergence guarantees similar to ours. Similar us, they considered asynchronous SGD with constant stepsizes, but under different assumptions: assuming only Lipschitz-continuity of functions instead of Lipschitz- smoothness. They did not discuss the connection of the number of workers to the average delay. For the heterogeneous case they chose a different approach than ours and provide a delay-adaptive learning rate that converges only an approximate solution, but allows workers be arbitrarily long delayed (including the case when some of the workers are never responding).
our work, Mishchenko et al. [35] provide a
Asynchronous federated learning. In typical federated learning (FL) applications [34,, clients or workers frequently have very different computing powers/speed. This makes especially appealing for practitioners to use asynchronous algorithms for FL
47
37
54
g
53
23
10
52 with
many of these works focusing on correcting for unequal participation ratio of different clients I0 53 by implementing variance reduction techniques on the server. Nguyen et (37 introduce the FedBuff algorithm that is very close to the algorithm that we consider in this work and show its practical superiority over classical synchronous FL algorithms.
152 22 23
3 Setup
We consider optimization problems where the components of the objective function (i.e. the data for machine learning problems) distributed across n workers (or clients).
min XER
f(x)
[(x)=
1 = n Σ [f(x))==E<D Fx E(. [)]
(I)
Here ft: Rdd + denotes the local objective function that accessible to the worker i E [n] :=
{1....n) n... Each fi is a stochastic function fx(x) Bę-D, Fx(x,)) and clients can only access stochastic gradients (F, E). This setting covers deterministic optimization if F, {) fxxx). Vg. It also covers empirical risk minimization problems by setting D, being uniform distribution
over local dataset {5) ... ...T") } of size m., this case the local functions Si can written as finite
sums: fx(x) 1 Sm j=l ())
Assumptions. For our convergence analysis we rely on following standard assumptions on the functions f; and F;:
3

---

Algorithm ASYNCHRONOUS SGD
input Initial value x()) E F=
server selects set of active workers Co S [n] and sends them x())
2: for t =
- 0,..., do
3: active workers C₁ are computing stochastic gradients in parallel the assigned points
4: once worker j. finishes compute. it sends V VF(x(t-7) &t-r)) the server
5: server updates x(++1) x(9 7/t V F(((tt+))) Se-r)
6: server selects subset A, S [n] of inactive workers, i.e. A; and sends them x(++1)
7: update active worker set C++1 C. Mi) U.
8: end for
Assumption (Bounded variance). We assume that there exists constant 2 0 such that
Bę-D, [V. {) (x)) =o?
Vi E [n]. Vx E R
(2)
Assumption 2 (Bounded function heterogeneity). We assume that there exists constants ÇJ 0, i [m]] such that
[V - (
Vx E Rdd
and define L
Assumption (L-smoothness). Each function Jt: RRd R. E [n]] is differentiable and there exists a constant L 2 0 such that
[Vf(r) - (x((x)l & L L||x -yl
Vx, y E Rd
(4)
For only some of our results we will assume a uniform bound on the gradient norm:
Assumption (Bounded gradient). Each function fú: Rd E [n] is differentiable and there exists a constant G 2 0 such that
[V(()) G2,
Vx E Rdd
(5)
4 Homogeneous Distributed Setting
We start with an important special case of problem IT) where the objective functions are identical
for all workers, i.e. fo fx( = fx) for all i.j E [n], such as in the case homogeneously (i.i.d.) distributed training data. Consequently, this implies that Assumption 2 holds with S, 0, i E [m]. Many classical works have focused on asynchronous algorithms under this homogeneous setting (e.g- 16 48 20 45 28, 46), see the related work for more references). This setting commonly appears in the datacenter setup for distributed training [16] where all nodes (or GPUs) have access to the full dataset or data distribution. Moreover, this special case allows to present main ideas in simplified way, without complicating the presentation due to data heterogeneity. We will later see that most of the results in this section can also be obtained as corollary of the more general heterogeneous functions case (Section 5) by setting C = 0 E [n]]
4.1 Algorithm
We consider standard asynchronous SGD (also known as delayed SGD, or SGD with stale updates) presented in Algorithm [ see e.g. 66 48 20
46) First, the server initializes training by selecting an initial active worker set Co and assigning x (0) to these workers. Throughout the algorithm, the active workers compute gradients at their own speed, based on their local data. On line 4, once some worker (which we denote j.) finishes computing its gradient, it sends the result to the server. On line the server incorporates the received -pooeebl delayed-graddeet,, using a stepsize that can depend on the gradient delay T;- The gradiení delay is defined as the difference between the iteration at which worker j, started compute the gradient and the iteration at which got applied. We index the stochastic noise of the gradients & by iteration t to highlight that previous iterates (t)) for t' t do not depend this stochastic noise. However, the client selects the data sample & at iteration - т when the computation starts. After that, on lines 6-7 the server selects the new active workers out of the ones that currently inactive (including worker j.) and assigns them the latest iterate x (t+1)
45
28

---

In contrast to previous works, we explicitly define the set of workers that are busy with computations every step as C, (the active workers set). Note that this does not pose any restrictions. A main advantage of allowing the sets C. to be different at every step /. lies in the possibility to also cover mini-batch SGD as special case, which we discuss in Example Our theoretical results depend on the size of these sets C₁, a.k.a. the concurrency.
Definition (Coneurrency).. The concurrency To at step is defined as the size of the active worker set Ct, Le. C |Crl. We also define the maximum and average concurrency as
TC mTx
tc = T4I Σ (8)
Note that in many practical scenarios, we have a constant concurrency of n over time, meaning that all workers are active at every step, and thus Tc n.
We discuss two important practical examples that fit into our Algorithm !
Example 2 (Mini-batch SGD). Mini-batch SGD with batch size can be seen special case of A Algorithm| 7 as follows: The server (i) in line I selects all n. workers, Co = [m]; (ii) in line 6 does not select new workers while the gradients from the same batch have not been fully applied yet, i.e.
A = 0 if t mod n # O; (iii) in line 6 selects A. = [m]] ift mod n = 0 to start a new batch.
Example 3 (Asynchronous SGD with maximum concurrency). In practical implementations one should always aim to utilize all resources available and thus (i) in line I select all available workers Co [n]; (ii) in line 6 select re-assign the worker that finished its computations At {jee so that workers are always kept busy with jobs.
4.2 Theoretical analysis: Constant stepsizes
We first formally define the average and maximum delays.
Definition 4 (Average and maximum delays). Let {Fi)T=o) be the delays of the applied gradients in Algorithm [ We define {rī hecrMir) as the delays of gradients which are in flight time T, that is they have remained unapplied at the last step. Each +e is equal to the difference between the last iteration T and the iteration at which worker i started to compute its last gradient. We then define the average and the maximum delays as
T-1
Tang T+
Σ 2-
TE
: (ECT
Σ
Tmax max
max L-I....-
Tt.
max
Co
(6)
iEC, Mire
We further provide key observation on the connection between the average delay and the average concurrency. This observation, is one of the essential elements for achieving improved analysis.
Remark (Key Observation). In Algorithm 7 average delay Tavg as
the average concurrency to is connected to the
T+1
T>[Crl O(īc).
Tang T T+ Tc
We explain this observation on a simple example. Assume that the concurrency is constant every step (TC =T)), and that all workers except one are responding very rarely. Then on steps 4-5 of A onnl this one responding worker would mostly participate. This means that for this one worker the delay тr would be frequently equal to zero, and the overall average delay will be small.
Next, we provide our theoretical results. We first focus on the Asynchronous SGD Algorithm under constant stepsizes, i.c. 7)= 1). This setting was studied many works such as I 20 28 48). Theorem (Constant stepsizes). Under Assumptions
3 there exists constant stepsize
such that for Algorithm holds that T Er= V
I| < e after
0²
VToxmax
iterations.
(8)
E
If we additionally assume bounded gradient Assumption then Ei [A e after
LA
0²
TGG
TC
iterations.
(9)
2
3/2
5

---

Under constant concurrency, we can directly connect TC to the average delay Tavg due to Remark 5 We highlight again that in practice, to get the best utilization of the available resources, practical implementations choose the maximum concurrency possible, which is equal to n.
Corollary 7. If Algorithm the concurrency is constant al every step (thus TC = tc). then under the same conditions as in Theorem 1i the convergence rate of Algorithm iis
o 002 VTavg" Tmax E2
o o²
Taog
Tavg
and
(10)
g3/2
for the case without and with bounded gradients (Assumption respectively.
The previously best known convergence rate for Asynchronous SGD (Algorithm ! under constant stepsizes was given in [48] and is equal to O e + c ). In our theorem we improved the delay dependence from Tmax to / //aayyTaan in the last term without any change in the algorithm, only by taking into account concurrency that is usually fixed in practical implementations anyways. No other work previously made assumption on the number of computing workers in their theoretical analysis. /Taey Timax could be much smaller than Tmax in the presence of rare straggler devices. With an additional assumption of bounded gradients, the dependence the maximum delay can be completely removed.
4.3 Theoretical analysis: Delay-adaptive stepsizes
In many cases, the bounded gradient Assumption is unrealistic [38. meaning that the gradient bound G is often large and thus the rate (9) is loose. In this section show that by weighting the stepsize down for the gradients that have a large delay, once can remove the dependence on the maximum delay mmax without assuming bounded gradients (Assump.)
Theorem 8 (Delay-adaptive stepsizes). There exist parameter 1j stepsizes in Algorithm I dependent on the delays as
ar such that if we set the
1/t
17 < min IL
Ti S 2TC
(11)
To 2TC,
then for Algorithm
under Assumptions
3 holds that
El ni //llll///f
|[
< E after
Eimo ne
(
0²
TC
iterations.
(12)
E2
In our theorem, the stepsize 17, in the case of large delays T, > 2Tc can be an arbitrary value between and min J. Setting the stepsize T): = 0 is equivalent to dropping these gradients.
Proof sketch of Theorem g We give the intuitive proof sketch for the case when we drop gradients with T: > 2TC and we deal with the general case in the Appendix. We know that Tang To TO from Remark [5] It also holds that the number of gradients that have delay larger than the two times the average delay 2aavy is smaller than half of all the gradients (< 3' because delays below by zero (T: 2 0 Vt). Thus, dropping the gradients with the delay тę > 2TC, or equivalently
bounded
setting their stepsize 7/, O, will degrade the convergence rate at most by half, while the maximum
delay among the applied ones now is equal to 2Tg- Thus we can apply the result from [48] with Tmaz 2TC-
Corollary 9. If in Algorithm 7 the concurrency is constant at every step (thus TO Tc), then under the same conditions as in Theorem the convergence rate of Algorithm 7 is
Tang
+
(13)
2
E
4.4 Discussion
Comparison to synchronous optimization. Mini-batch SGD with batch size n has the same degree of parallelism as Algorithm|] with constant concurrency i.e. it has workers computing gradients in parallel. Mini-batch SGD needs
O nz 1) 22 batches of gradients to reach an e-stationary point, and thus needs O + m) gradients, the batch-size is equal to On the

---

contrary, asynchronous SGD A with stepsizes chosen as in [TT achieves exactly the same rate (13) since Tang TC n, while expected per-iteration time is faster than that of mini-batch SGD, as no workers have to wait for others. Thus, our result shows that asynchronous SGD is always faster than mini-batch SGD regardless of the delay pattern. small note that in our reasoning we implicitly assumed that the sever can perform its operations in negligible time.
Tuning the stepsize. It is worth noting that our stepsize rule [1 does not introduce any additional hyperparameters tune compared to the constant stepsize case or to synchronous SGD. TO usually known and can be easily controlled by the server, especially in the practical constant concurrency case. Thus, to implement such stepsize rule (11 one needs to tune only stepsize v), and in case of > 2Tc set stepsize 1/2 +.
Average v.S. maximum delay. In homogeneous environment when every worker computes gradients with same speed during the whole training, the average and maximum delays would be almost equal. However, occasional straggler devices will usually be present. In this case the maximum delay is much larger than the average delay.
Consider a simple example with n = 2 workers, where the first worker computes gradients very fast, while the second worker returns its gradient only the end of the training at the last iteration T. In this case the average delay Tang 2 is a small constant, while the maximum delay Tmax = T. In this case the rate depending only on the maximum delay Tmax would guarantee convergence only up to constant accuracy = (1)). While both rates with /TmaxTav Tayg and with Taog guarantee convergence up to an arbitrary small accuracy.
Comparison to other methods. Cohen et al. 15 recently proposed the PickySGI algorithm that achieves a convergence rate of O Tauz) (same as (3)). Their algorithm discards gradients based on the distance between the current point and the delayed one ||x(() - x xt+- The disadvantage of their method is that it requires sending points x(*- along with the gradients thus incurring twice more communications at every step. Their method also requires tuning an extra hyperparameter. In this work achieve the same convergence any additional communications nor additional tuning compared to synchronous SGD.
with a much simpler method that does not require
[9] also recently proposed the delay-adaptive algorithm with convergence rate depending on the average delay Tang for the convex and strongly convex cases. Although, our convergence rates are for the non-convex case and are not directly comparable to theirs, we highlight some key differences in their analysis. First, their convergence rate depends not only on Tozg but also the variance o,, of the delays, which can degrade with the maximum delay. Second, they require the bounded gradient Assumption 4 In Theorem 6 we show that under Assumption no modifications to the algorithm needed to completely remove the dependence on the maximum delay Tmax
Tightness. As we explained in Example 2 mini-batch SGD is covered by Algorithm I We know
that manc- SGD convergence is lower bounded by O o² ) [5] in terms of batches processed
and thus by O ed + ") in terms of the gradients computed. Our convergence rate given in Theorem coincides with this lower bound as in this case concurrency TO n, Tazg Tc 2.
5 Heterogeneous Distributed Setting
In this section we consider more general problems of the form where the functions f. are different on different workers. This setting is motivated for example by federated learning (34 24 where every worker (client) possesses its own private data, possibly coming from a different data distribution, and thus has its own different local objective function fi-
The setting here is therefore more general than the one considered in previous Section 4 and we will see that some of the results (with the constant stepsizes) in the homogeneous case follow as a special case of the more general results we present in this section.
5.1 Algorithm
We consider asynchronous SGD as given in Algorithm 2 Close variants of this algorithm were studied in several prior works 37 47. In order to simplify the presentation, we consider that concurrency
is constant over time (and thus TO to in Definition D. In order to allow for client subsampling
7

---

often implemented in practical federated learning applications, we allow the concurrency to be smaller than overall number of workers n. The same concurrency model was recently considered in the practical FedBuff algorithm 337
Algorithm 2 ASYNCHRONOUS SGD with concurrency TC
input Initial value (0) E Rd, clients, concurrency
Server:
1: server selects uniformly at random a set of active clients Co of size to and sends them x())
2: for =0 0....., do
3: active clients C₁ are computing stochastic gradients in parallel at the assigned points
4: once some client je finishes compute, it sends F,;, (x (x(1-T+), ((-+) to the server
(x(1
5: server updates (++1) (() 7/ F (x((-r)) ((-r.
6: sever selects a new client k ~ Uniform(1, n] and sends it (((-1)
7: update the active worker multiset C++1 = C. MM3 {Te)
8:
end for
The algorithm is very similar to the homogeneous Algorithm with two key differences: at line the server selects clients out of all clients, and does uniformly random, regardless of the current active worker set C, This means that the same client can get sampled several times, even it didn't t finish its previous job(s) yet (thus is multiset). In this case, the assigned jobs would just pile up on this client.
5.2 Theoretical analysis
We first note that our key observation on the delays (Remark S holds for Algorithm as well. Moreover, we have constant concurrency TO every step, Tavy +(Tc).
Definition 10. Denote (possibly empty) set {Tk Cr to the set of delays from gradients of the client i that are left unapplied at the last iteration of the Algorithm 2
We define the average delay of a client i as
Σ
Cr. k
Tavg
72
T. ::j
where T₃ is the number of times that client was sampled during lines I and of Algorithm Assumption 5. The average delay Tang is independent from the number of times T; that client i was sampled.
Theorem 11 (constant stepsizes). Under Assumptions = such that for Algorithm
3 there exists constant stepsize
it holds that T+1 Et
Vf(x(( I|² < after
2
2
Tang E Gr Tang
iterations,
(14)
2
2
c
Under Assumptions
and additional bounded gradient Assumption it holds that
after
2
Tang c
Tovg
iterations.
(15)
We note that the leading 1 term is affected by heterogeneity Ç² because at every step we apply gradient from only client. This term is usually present in the federated learning algorithms with client subsampling see e.g. 25
5.3 Discussion
Comparison to other works. The recent FedBuff algorithm (37 is similar to our Algorithm 2 Their algorithm allows clients to perform several local steps and the server to wait for more than

---

client to finish compute (aka buffering), which we did not include for simplicity as these aspects are orthogonal the effect of delays.
Disregarding these two orthogonal changes, the FedBuff algorithm is almost equivalent our Algorithm 2 with key difference: they assume that the client je that finishes computation at every step comes from the uniform distribution over all the clients. This is unrealistic to assume in practice because the server cannot control which clients finish computations at every step. In Algorithm 2 we have the more realistic assumption only on the sampling process of the new clients (on line 6) that can be controlled by the server. This reflects practical client sampling in federated learning.
The convergence rate of FedBuff
37 under the bounded gradient assumption is
0 + + 15(+)))mm In contrast, in Theorem 11 we completely remove the depen-
dence on the maximum delay Tmax under bounded gradients (as in Equation 15
Delays. We note that for Theorem 11 we did not impose any assumption on the delays. Thus, our result allows clients and the delays on these clients to be dependent, meaning that some of the clients could be systematically slower than others. Interestingly, the middle heterogeneity term (the term with Çi) is not affected by the maximum delay at all, but is affected by the average delay within each individual client. If all the heterogeneity parameters are equal, i.e. C = Cj. Vi, then the middle term will be affected only by the overall average delay Tavg-
FL algorithms usually apply clipping to the gradients in order guarantee differential privacy (24) This automatically bounds the norm of all applied gradients, making the the constant G in Assumption 4 small. Although we do not provide formal convergence guarantees of asynchronous SGD with gradient clipping, envision that its convergence rate would depend only on the average delay, similar to the bounded gradient case ( thus making the algorithm robust stragglers.
Gradient clipping. Practical implementations
Delay-adaptive stepsiie For homogeneous functions we have shown that addatiie stepsizes result in convergence rate dependent only on the average delay Tavg without assuming bounded gradients (as in Equation (II).. However in the heterogeneous case this is not so straightforward. Delay-adaptive learning rate schemes will introduce bias towards the clients that compute quickly,
and Algorithm 2 would converge to the wrong objective.
is interesting to note that current popular schemes implemented practice for FL over-selects the clients every iteration [12. The server waits only for some percentage (e.g. 80%) of sampled clients and discards the rest. Such a scheme also introduces a bias towards fast workers. A delay-adaptive learning rate scheme is expected introduce less bias the gradients are still applied but with the smaller weight. We leave this question for future practical investigations, as it is not the focus of our current work.
Independent delays. the delays and the clients are independent (e.g. coming from the same distribution for all of the clients), then the convergence rate of Algorithm _ will simplify to 0(2
STaug + /mau (without needing bounded gradient assumption). In this case it is 22 also possible to use delay-adaptive stepsizes (similar to Thcorem to completely remove the dependence on the maximum delays Tmax without assuming bounded gradients.
Extensions. We can extend the Algorithm and our theoretical analysis to allow clients to perform several local steps, before sending back the change in We also extend Algorithm to allow the server to wait for the first K clients to finish computations rather than just one, similar to [37]. These extensions straightforward and excluded them here for simplicity of presentation.
Finally, we can also extend Algorithm 2 to sample new clients as soon as some previous client finished compute, without waiting for the server update on the line 5.
Experiments
In this section we aim to empirically evaluate the effectiveness of our proposed delay-adaptive stepsizes (TT) in the homogeneous case. We use w wa dataset from LIBSVM data library, and evaluate performance logistic regression function defined as f(x) Σ log(1 + exp(-bya, x))

---

batch
batch size 1000
250
constant sepsize
constant sepsize
200
delay adaptivee pringg
10
delay-adaptive dropping
deleg
150
10
delay adaptive weighting down
delay-adaplive weighting down
100
10
10
0
100
200
300
400
500
0
100
200
300
400
500
0
100
200
300
400
500
Iteration
Iteration
ration
batch
batch
150
constant sepsize
constaat size
delay-adeptixe are pping
del ay ad-apivevve cropping del adaptive weighting
delays
100
delay adaptive weighting down
6100
50
10-2
0
10"
100
200
300
400
500
100
200
300
400
500
0
100
200
300
400
500
iteration
Iteration
iteration
Figure I: Comparison of three different stepsize strategies in asynchronous SGD. (left) delay pattern, (middle) convergence curve with batch size 500, (right) convergence curves with batch size 1000. Both adaay-adee stepsize schemes more robust to occasional large delays.
| where a Rdd and b E {-1,1} data samples. wla dataset has 2477 examples and dimension d = 300. We use fixed concurrency with n = 10 workers.
We compare the following three stepsize strategies:
constant stepsizes 1): = 1)
delay-adaptive stepsizes with dropping large-delayed gradients
T $ 2n.
=
0 > 2m,
delay-adaptive stepsizes with weighting down large-delayed gradients
Ts S 2m,
Te
> 2n.
Note that the two last stepsize schemes satisfy the conditions in ITI. For each of the strategies tune only one parameter 17 separately from the logarithmic grid and ensure that the found stepsize is not on the edge of this grid.
Figure 1 presents the results for two different delay patterns. We can see that both of the delay- adaptive stepsizes have comparable performance and are more robust to the large delays than the constant stepsize.
7 Conclusion
In this paper we study the asynchronous SGD algorithm both in homogeneous and heterogeneous settings. By leveraging the notion of concurrency the number of workers that compute gradients in parallel-we ww show much faster convergence rate for asynchronous SGD, improving the dependence on the maximum delay Tmax over prior works, for both homogeneous and heterogeneous objectives. Our proof technique also allows to design a simple delay-adaptive stepsize rule [[]) that attains convergence rate depending only on the average delay Tang that neither requires any additional tuning, nor additional communication. Our techniques allows us to demonstrate that asynchronous SGD is faster than mini-batch SGD for any delay pattern.
Acknowledgments
AK was supported by a Google PhD Fellowship. thank Brendan McMahan, Thijs Vogels, Hadrien Hendrikx, Aditya Vardhan Varre and Maria-Luiza Vladarean for useful discussions and their feedback on the manuscript.
10

---

References
[1] Alekh Agarwal and John C Duchi. Distributed delayed stochastic optimization In Advances in Neural Information Processing Systems 24, pages 873 881. Curran Associates, Inc., 2011.
[2] Dan Alistarh. Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovie. QSGD: Communication efficient SGD via gradient quantization and encoding In Advances in Neural Information Processing Systems 30, pages 1709-1720. Curran Associates, Inc., 2017.
[3] Dan Alistarh, Christopher De Sa, and Nikola Konstantinov, Thh convergence of stochastic gradient descent in asynchronous shared memory. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC '18, page 169-17 178, New York, NY, USA, 2018, Association for Computing Machinery. ISBN 978145035795.. doi: 10.1 144532112334322222211
[4] Dan Alistarh, Torsten Hoefler, Mikael Johansson, Nikola Konstantinov, Sarit Khirirat, and Cedric Renggli. The convergence of sparsificd gradient methods In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. DissaBiancchi, and R. Garnett, editors, NeurIPS Advances in Neural Information Processing Systems
31, pages 5977-5987. Curran Associates, Inc., 2018.
[5] Yossi Arjevani, Yair Carmon, John C. Duchi, Dylan Foster, Nathan Srebro, and Blake E. Woodworth. Lower bounds for non-convex stochastic optimization. ArXiv, ab//1912.023655, 2019.
[6] Yossi Arjevani, Ohad Shamir, and Nathan Srehro. A tight convergence analysis for stochastic gradient descent with delayed updates] In Aryeh Kontorovich and Gergely Neu, editors, Proceedings of the 31st International Conference on Algorithmic Learning Theory, volume 117 of Proceedings of Muchine Learning Rexearch, pages 111-132. PMLR, 08 Feb-1l 1 Feb 2020.
Mahmoud Assran, Nicolas Loizou, Nicolas Ballas, and Michael Rabbat. Stochastic gradient push for distributed deep learning. In Proceedings of the 36th International Conference on Machine Learning (ICML). PMLR, 2019.
[8] Dmitrii Avdiukhin and Shiva Kasiviswanathan. Federated learning under arbitrary communication patterns In Marina Mcila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 425 4355, PMLR, 18 24 Jul 2021.
[9] Rotem Zamir Aviv, Ido Hakimi, Assaf Schuster, and Kfir Yehuda Levy. Learning under delayed feedback: Implicitly adapting to gradient delays. In Proceedings of the 38th International Conference on Machine Learning. PMLR, 2021.
[10] Arda Aytekin, Hamid Reza Feyzmahdavian, and Mikael Johansson. Analysis and implementation of an asynchronous optimization algorithm for the parameter server 2016
[11] D.P. Bertsekas and J.N. Tsitsiklis. Parallel and Distributed Computation: Numerical Methods. Prentice- Hall, 1989.
[12] Keith Bonawitz, Hubert Eichner, Wolfgang Grieskamp, Dzmitry Huba, Alex Ingerman, Vladimir Ivanov, Chloé Kiddon, Jakub Konečný, Stefano Mazzocchi, Brendan McMahan, Timon Van Overveldt, David Petrou, Daniel Ramage, and Jason Roselander. Towards federated learning at scale: System design In A. Talwalkar, V. Smith, and M. Zaharia, editors, Proceedings of Machine Learning and Systems, volume 1, pages 374-388, 2019.
[13] I.. Bottou, F. Curtis, and J. Nocedal, Optimization methods for large-scale machine lcarning SIAM Review, 60(2):223-311, 2018.
[14] Sorathan Chaturapruek, John C Duchi, and Christopher Ré. Asynchronous stochastic convex optimization the noise is in the noise and SGD don't I care In Advances in Neural Information Processing Systems 28, pages 1531-13 11399 Curran Associates, Inc., 2015.
[15] Alon Cohen, Amit Daniely, Yoel Drori, Tomer Koren, and Mariano Schain. Asynchronous stochastic optimization robust to arbitrary delays) In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and Wortman Vaughan, editors, Advances Neural Information Processing Systems, volume 34, pages Curran Associates, Inc., 2021.
[16] Jeffrey Dean, Greg Corrado, Rajat Monga, Kai Chen, Matthieu Devin, Mark Mao, Marc aurelio Ranzato, Andrew Senior, Paul Tucker, Ke Yang, Quoc V. Le, and Andrew Y. Ng. Large scale distributed deep networks. In NIPS Advances in Neural Information Processing Systems, pages 1223 1231, 2012.
11

---

[17] Ofer Dekel, Ran Gilad-Bachrach, Ohad Shamir, and Lin Xiao. Optimal distributed online prediction using mini-batches Journal Machine Learning Resesearch (JMLR), 13(1): 202, 2012.
[18] Sanghamitra Dutta, Gauri Joshi, Soumyadip Ghosh, Parijat Dube, and Priya Nagpurkar. Slow and stale gradients can win the race: Error rrtor-ruttmme trade-off's in distributed sgd In Proceedings of the Twenty-Fine International Conference on Artificial Intelligence and Statistics, pages 803-812. PMLR, 2018.
[19] Mathieu Even, Hadrien Hendrikx, and Laurent Massoulie. Decentralized optimization with heterogeneous delays: a continuous- time approach, 2021.
[20] H. R. Feyzmahdavian, A. Aytekin, and M. Johansson. An asynchronous mini mini-batch algorithm for regu- larized stochastic optimization. IEEE Transactions Automatic Control, 61(12):3740 3754, Dec 2016. ISSN 0018-9286.
[21] Saced Ghadimi and Guanghui Lan. Stochastic first- and zeroth-order methods for nonconvex stochastic programming. SIAM J. Optim., 23:2341-2366 2013.
[22] Margalit Glasgow and Mary Wootters. Asynchronous distributed optimization with stochastic delays 2020.
[23] Xinran Gu, Kaixuan Huang, Jingzhao Zhang, and Longbo Huang. Fast federated learning in the presenee of arbitrary device unavailability In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 12052-12064.
Curran Associates, Inc., 2021.
[24] Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Keith Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, Rafael G. D' Oliveira, Hubert Eichner. Salim EI Rouayheb, David Evans. Josh Gardner, Zachary Garrett, Adrià 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, Mchryar Mohri, Richard Nock, Ayfer Özgür,, Rasmus Pagh, Mariana Raykova, Hang Qi, Danicl 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 federated learning. Foundations and Trends in Machine Learning, 14(1-2): (0112))1-210, 2021.
[25] Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank J. Reddi, Sebastian U. Stich, and Ananda Theertha Suresh. SCAFFOLD: stochastic controlled averaging for on-device federated learning CoRR, abs/1910.06378. 2019.
[26] Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi. and Sebastian U. Stich. A unified theory of decentralized sgd with changing topology and local updates. In Proceedings of the 37th International Conference on Machine Learning (ICML). PMLR, 2020.
[27] Remi Leblond, Fabian Pedregosa, and Simon Lacoste-Julien, Improvedd asynchronous parallel optimization analysis for stochastic incremental methods Journal of Machine Learning Research, 19(81): 1-68, 2018.
[28] Xiangru Lian, Yijun Huang, Yuncheng Li, and Ji Liu. Asynchronous parallel stochastic gradient for nonconvex optimization. In Advances in Neural Information Processing Systems, pages 2737-2745, 2015.
[29] Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsich, Wei Zhang, and Ji Liu. Can decentralized algorithms outperform centralized algorithms? case study for decentralized parallel stochastic gradient descent In Advances in Neural Information Processing Systems 30, pages 5330-5340, Curran Associates, Inc., 2017.
[30] Olvi L. Mangasarian and Mikhail V. Solodov. Backpropagation convergence via deterministic nonmonotone perturbed minimization. J. Cowan, G. Tesauro, and J. Alspector, editors, Advances in Neural Information Processing Systems, volume 6. Morgan-Kaufmann, 1994.
[31] Horia Mania, Xinghao Pan. Dimitris Papailiopoulos. Benjamin Recht, Kannan Ramchandran, and Michael L. Jordan. Perturbed iterate analysis for asynchronous stochastic optimization) SIAM Journal on Optimization, 27(4):2202-22) 2229, 2017. doi: 10.1137/1610570000
[32] Ryan McDonald, Keith Hall, and Gideon Mann. Distributed training strategies for the structured perceptron. In Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics, pages 456 464, Association for Computational Linguisties, 2010.
12

---

[33] Brendan McMahan and Matthew Streeter. Delay-tolerant algorithms for asynchronous distributed online
learning In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 27. Curran Associates, Inc., 2014.
[34] H. Brendan McMahan, Eider Moore, Daniel Ramage, and Blaise Aguera Arcas. Federated learning of arXiv preprint arXiv: 602.00669, 2016.
deep networks using model averaging
[35] Konstantin Mishchenko, Francis Bach, Mathieu Even, and Blake Woodworth. Asynchronous SGD beats minibatch SGD under arbitrary delays In Advances in Neural Information Processing Systems. arXiv preprint 11Xv:22066.06333, 2022.
[36] Angelia Nedié. Distributed gradient methods for convex machine learning problems in networks: Dis- tributed optimization. IEEE Signal Processing Magazine, 37 2020.
[37] John Nguyen, Kshitiz Malik, Hongyua Zhan, Ashka Yousefpour, Mike Rabbat, Mani Malek, and Dzmitry Huba. Federated learning with buffered asynchronous aggregation. In Proceedings of The 25th International Conference on Artificial Intelligence and Statistics. PMLR, 2022.
[38] Lam Nguyen, Phuong Ha Nguyen, Marten van Dijk, Peter Richtarik, Katya Scheinberg, and Martin Takac. SGD and Hogwild! Convergence without the bounded gradients assumption In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 3750-3758. PMLR, 10-15 Jul 2018.
[39] Feng Niu, Benjamin Recht, Christopher Re, and Stephen J. Wright. HOGWILD!: A lock-free approach to parallelizing stochastic gradient descent In Proceedings of the 24th International Conference on Neural Information Processing Systems, pages 693-701. Curran Associates Inc., 2011.
[40] Aditya Ramesh, Mikhail Pavlov, Gabriel Goh, Scott Gray, Chelsea Voss, Alec Radford, Mark Chen, and Nya Sutskever. Zero-shot text-to-image generation. In International Conference on Machine Learning, pages 1821-8831, PMLR, 2021.
[41] Aditya Ramesh, Prafulla Dhariwal, Alex Nichol, Casey Chu, and Mark Chen. Hierarchical text-conditional image generation with clip latents. arXiv preprint arXiv:2204. 06/25, 2022.
[42] Benjamin Recht, Christopher Re, Stephen Wright, and Feng Niu. Hogwild: A lock-free approach to parallelizing stochastic gradient descent) In J. Shawe-Taylor, R. S. Zemel, P. L. Bartlett, F. Pereira, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems 24, pages 693-701. Curran Associates, Inc., 2011.
[43] Herbert Robbins and Sutton Monro. A Stochastic Approximation Method. The Annals of Mathematical Statistics, 22(3):40 407400000770000 September 1951.
[44] Mohammad Shoeybi. Mostofa Patwary. Raul Puri, Patrick LeGresley, Jared Casper, and Bryan Catanzaro. Mcgatron-Im: Training multi-billion parameter language models using model parallelism. arXiv preprint arXiv: 190000053, 2019.
[45] Suvrit Sra, Adams Wei Yu, Mu Li, and Alex Smola. AAaadela:: Delay adaptive distributed stochastic optimization In Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, volume 51 of Proceedings of Machine Learning Research, pages 957-965. PMIRR 2016.
[46] Sebastian Stich, Amirkeivan Mohtashami, and Martin Jaggi. Critical parameters for scalable distributed learning with large batches and asynchronous updates In Proceedings of The 24th International Conference Artificial Intelligence and Statistics, pages 4042 4050. PMLR, 2021.
[47] Schastian U. Stich. Local SGD converges fast and communicates little ICLR - International Conference on Learning Representations, art. 10X 2019.
[48] Sebastian U. Stich and Sai Pranceth Karimireddy, The emoorfeedback framework: SGD with delayed gradients Journal of Machine Learning Research, 21(237):1-36, 2020.
[49] Thijs Vogels. Sai Praneeth Karimireddy, and Martin Jaggi. PPowerSGD: Practical low-rank gradient compression for distributed optimization In Advances in Neural Information Processing Systems 32 (NeurIPS), pages 1626-1636. Curran Associates, Inc., 2019.
[50] Meng Wang, Weijie Fu, Xiangnan He, Shijie Hao, and Xindong Wu. A survey on large-scale machine learning. IEEE Transactions on Knowledge and Data Engineering, 2020.
[51] Xuyang Wu, Sindri Magnusson, Hamid Reza Feyzmahdavian, and Mikael Johansson. Delay-adaptive step-sizes for asynchronous learning 2022.
13

---

[52] Yikai Yan, Chaoyue Niu, Yucheng Ding, Zhenzhe Zheng. Fan Wu, Guihai Chen, Shaojie Tang, and Zhihua Wu. Distributed non-convex optimization with sublinear speedup under intermittent client availability 2020.
[53] Haibo Yang, Xin Zhang, Prashant Khanduri, and Jia Liu. Anarchic federated learning 2021.
[54] Hossein Zakerinia, Shayan Talaei, Giorgi Nadiradze, and Dan Alistarh. QuAFL: Federated averaging can be both asynchronous and communication-eflccienn. arXiv preprint arXiv:2206. 10032, 2022.
[55] Wei Zhang, Suyog Gupta, Xiangru Lian, and Ji Liu. Staleness-aware asyne-sgd for distributed deep learning In Proceedings of the Twenty-Fift International Joint Conference Artificial Intelligence (IJCAI-16), 2016.
[56] Shuxin Zheng, Qi Meng. Taifeng Wang. Wei Chen, Nenghai Yu, Zhi-Ming Ma, and Tin-Yan Liu. Asyn- chronous stochastic gradient descent with delay compensation. Proceedings of 34th International Conference on Machine Learning. PMLR, 2017.
[57] Martin Zinkevich, Markus Weimer, Lihong Li, and Alex Smola. Parallelized stochastic gradient descent. In Advances in Neural Information Processing Systems, pages 2595-2603, 2010.
14


Reviews:
[{"review_id": "fr6_BjFtyP9", "reviewer": "Reviewer_88dr", "summary": "The authors provide the analysis of Asynchronous SGD algorithms in the homogeneous and heterogeneous regimes. First, in the homogeneous regime, they provide a better analysis of Asynchronous SGD and get better rates without additional changes in the original algorithm with a constant step size. Next, they omit the dependence on the maximum delay by exploiting the delay-adaptive learning rate scheme. Finally, the authors provide an analysis of the heterogeneous regime, where the dependence on the maximum delay is improved, or the dependence can be omitted under the gradient boundness assumption.", "questions": "Minor problems:\n1. It is better to check terms $\\xi_t$ and $\\xi_{t - \\tau}.$ For instance, in Algorithm 1, I would expect to see $\\nabla F(x^{t - \\tau_t}, \\xi_{t - \\tau_t})$ because $\\xi_{t - \\tau_t}$ was generated at time $t - \\tau_t.$\n2. 640: The line says $\\tau_{avg} \\leq \\tau_C.$ Does it hold for every $T$? Maybe, as in Remark 5, there should be some additional factor in the inequality?\n\nSuggestions:\n1. Recently, Mishchenko et al. prepared \"Asynchronous SGD Beats Minibatch SGD Under Arbitrary Delays\" paper. Can the authors kindly add some sentences where they describe the differences between the papers?\n", "limitations": "No", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper provides very interesting and nontrivial results in a timely topic. Even the fact that the authors improved dependence from $O(\\frac{\\sigma^2}{\\epsilon^2} + \\frac{\\tau_{max}}{\\epsilon})$ to $O(\\frac{\\sigma^2}{\\epsilon^2} + \\frac{\\sqrt{\\tau_{max} \\tau_{avg}}}{\\epsilon})$ is a strong result for a NeurIPS publication. Besides that, the authors improved the convergence rates even further to $O(\\frac{\\sigma^2}{\\epsilon^2} + \\frac{\\tau_{avg}}{\\epsilon})$ using adaptive step sizes. The same order of improvements was done in the heterogeneous setting. \n\nI see that the dependence $O(\\frac{\\sigma^2}{\\epsilon^2} + \\frac{\\tau_{avg}}{\\epsilon})$ was obtained before by Cohen et al. \"Asynchronous Stochastic Optimization Robust to Arbitrary Delays\", but they use an alternative strategy with another hyperparameter that can be difficult to tune.\n\nThe proofs sound to me and I didn't find any major issues. But, I only checked the proof of Theorem 6 in detail.", "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": "YhB8v9ZQjr", "reviewer": "Reviewer_Ukik", "summary": "This paper study the convergence properties of asynchronous SGD for distributed and federated learning. The authors tighten the convergence rate of non-convex smooth objectives that depend on the maximum delay to $\\epsilon$-stationary point from $O\\left(\\sigma^2\\epsilon^{-2}+ \\tau_{\\max}\\epsilon^{-1}\\right)$ to $ O\\left(\\sigma^2\\epsilon^{-2}+ \\sqrt{\\tau_{\\max}\\tau_{avg}}\\epsilon^{-1}\\right)$ without any change to the algorithm., where $\\tau_{\\max}$ is maximal delay and $\\tau_{avg}\\$ is the average delay. Then, the authors propose a new delay-adaptive learning rate scheme of a faster convergence rate of $ O\\!\\left(\\sigma^2\\epsilon^{-2}+ \\tau_{avg}\\epsilon^{-1}\\right)$. This is the first time that asynchronous SGD becomes faster than the synchronous SGD.  The authors also discuss the case of of heterogeneous functions.", "questions": "The authors are encouraged to conduct experiments to verify the advantages of the proposed delay-adaptive learning rate scheme", "limitations": "No limitations and potential negative societal impact are identified, while the authors do not explicitly discuss this in the paper.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros:\n\n+ This paper makes novel and significant contributions in asynchronous SGD for distributed and federated learning. The authors significantly reduce the reliance of the convergence on the maximal delay to the average delay, by leveraging the notion of concurrency. This decreases the worst-case impact of the communications between the workers.\n+ The idea makes sense. The authors suggest that the average delay matters in determining the convergence rather than totally relying on the maximal delay.\n+ The proofs are rigorous and presented clearly. I did not find major flaws.\n+ The literature review is comprehensive and well-discussed. The contributions are well-positioned in the existing results. Readers can easily understand the novelty and contributions of this work compared with the existing works.\n+ This paper is well-written. The paper is organised in a clear structure. \n\nCon:\n\n- My concern is mainly about the proposed algorithm. The authors argue that this algorithm has advanced convergence rate but does not give any experimental results. The authors are encouraged to conduct experiments to verify this statement.", "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": "9atMKYUVYQW", "reviewer": "Reviewer_ZeX4", "summary": "This work provides a theoretic study on the convergence rates of asynchronous SGD under distributed homogeneous and heterogeneous settings. The main contributions are (i) a sharper analysis for the constant stepsize async-SGD, which improves over the existing ones, and (ii) a delay-adaptive stepsize for async-SGD, which leads to the best known convergence rate, and without extra hyperparameter tuning and extra communications required in [13], (iii) improved analysis in the heterogeneous case compared with FedBuff [31].", "questions": "Questions: see comments above.\n\nTypos:\n- Algorithm 1, Line 1: sever -> server.\n- Line 164, C_0 =[n]?\n- Line 287, there exists", "limitations": "The authors have adequately addressed the limitations and potential negative societal impact of their work.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "======= After Rebuttal =========\nThank the authors for the response, which clarified my confusions.\n\n============================\nStrengths:\n- This paper is very well-written and has a nice flow of ideas.\n- The key analytic technique, which I believe is the notion of active set/concurrency, seems pretty novel to me.\n- Simple and intuitive algorithmic constructions with improved convergence guarantees.\n\nWeaknesses (or comments):\n- This work would benefits from some empirical evaluations, given that there is nothing impractical or hard-to-tune in the proposed schemes.\n- The authors claimed that they show \"for the first time, asynchronous SGD is always faster than mini-batch SGD\". Ain't the convergence results in [13] (Picky SGD) already show this, did I miss something?\n- Algorithm 2 does not consider local steps, which is however a key feature of federated learning systems. I am not sure if it is a straightforward extension in theory, especially with delayed updates. Could the authors discuss how the number of local steps would affect the convergence rate in Theorem 10?", "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