On the Optimal Time Complexities in Decentralized Stochastic Asynchronous Optimization
Authors: Alexander Tyurin
Peter Richtárik
Venue: NeurIPS 2024 poster (2024)
Keywords: nonconvex and convex optimization
stochastic optimization
asynchronous methods
decentralized optimization
lower bounds
Primary area: optimization

Abstract: We consider the decentralized stochastic asynchronous optimization setup, where many workers asynchronously calculate stochastic gradients and asynchronously communicate with each other using edges in a multigraph. For both homogeneous and heterogeneous setups, we prove new time complexity lower bounds under the assumption that computation and communication speeds are bounded by constants. After that, we developed a new nearly optimal method, Fragile SGD, and a new optimal method, Amelie SGD, that converge with arbitrary heterogeneous computation and communication speeds and match our lower bounds (up to a logarithmic factor in the homogeneous setting). Our time complexities are new, nearly optimal, and provably improve all previous asynchronous/synchronous stochastic methods in the decentralized setup.

On the Optimal Time Complexities in Decentralized Stochastic Asynchronous Optimization
Alexander Tyurin KAUST; AIRI, Skoltech!
Peter Richtárik KAUST
Abstract
We consider the decentralized stochastic asynchronous optimization setup, where many workers asynchronously calculate stochastic gradients and asynchronously communicate with each other using edges in multigraph. For both homogeneous and heterogeneous setups, we prove new time complexity lower bounds under the assumption that computation and communication speeds bounded. We develop a new nearly optimal method, Fragile SGD, and a new optimal method, Amelie SGD, that converge under arbitrary heterogeneous computation and communication speeds and match our lower bounds (up to logarithmic factor in the homogeneous setting). Our time complexities are new, nearly optimal, and provably improve all previous asynchronous/yycchmmouu stochastic methods in the decentralized setup.
Introduction
We consider the smooth nonconvex optimization problem min ZE3d
[(x))==<<<>> = (f(x;)))
where f Rd x Sg + R, and D₃ distribution on non-empty Sç. For given > 0, we
want to find a possibly random point T. called an e-stationary point, such that /[][V]( < &. We analyze the heterogeneous setup and the convex setup with smooth and non-smooth functions in Sections and D.
1.1 Decentralized setup with times
We investigate the following decentralized asynchronous setup. Assume that have workers/nodes with the associated computation times {h,), and communications times {P:= It takes less or equal to h; [0, oo] seconds to compute a stochastic gradient by the 7th node, and less or equal Pi-+j E [0, oo] seconds send directly a vector Id from the 7th node to the jth node (it is possible that h2 = oc and Pi-j oc). All computations and communications can be done asynchronously and in parallel. We would like to emphasize that h, [0, ooj and Pı-+, E [0, oo) are only upper bounds, and the real and effective computation and communication times can be arbitrarily heterogeneous and random. For simplicity of presentation, we assume the upper bounds are static; however, in Section 5.5, we explain that our result can be trivially extended to the case when the upper bounds are dynamic.
We consider any weighted directed multigraph parameterized by vector h E R" such that h; E [0, oo], and matrix of distances (ps-)))a,j E Raxn such that Pi-ッf E [0, oo] for all i.j E [m] and
"King Abdullah University of Science and Technology, Thuwal, Saudi Arabia
AIRI, Moscow, Russia
Skolkovo Institute of Science Technology, Moscow, Russia
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

6
2
4
1
3
3
5
3
5
4
3
2
are omitted. The shortest distance between nodes 5 and is 75-33 = P5-11 + p1 + p2->3- Note that P5->3 = Do. On the right: an example of spanning tree that illustrates the shortest paths from every node to node The shortest distance between nodes 6 and TB->3 = oo because pg-si = op for all * 6.
Figure I: On the left: example of a multigraph with = 6. The edges with Pi-+j
Pi-s: = for all i [n]. Every worker is connected to any other worker j with two edges + j and j + i. For this setup. it would be convenient to define the distance of the shortest path from worker i to worker j
min path putheP--)
Σ
Pa-to E [0, o0];
Epath
where Pi-j [[(k,, h2),,,,2),,.. h2),.... (kims ki++)] Vm E Nvp [m + 1] E [n],
1 = i, km+1 = J. {2..... m kj-1 * k; + kj+1
is the set of all possible paths without loops from worker to worker j for all i, E [nx] One can easily show that the triangle inequality Ti-ij I Ti-sk + Tk-s holds for all i, Ti-t S Pi-+j for all i,j E [n). It is important to distinguish T--j and Pi-ッj because it is possible that Titt < Pi-tj 0o workers i and j are connected by an edge pi-+5 = oc, and there a path through other workers (see Fig. 1).
[n]. Note that
We work with the following standard assumption from smooth nonconvex stochastic optimization literature.
Assumption 1. f is differentiable and T-smooth, ie, [V - V S L. || - vll Vx, E Rd. Assumption 2. There exist f" E TK such that f(x) 2 f for all Rd.
Assumption For all x E Rdd stochastic gradients Vf {) are unbiased and o2-variance- bounded, i.e., [ E)] f((x) and [e]lVf((;; {) f(x)]] < a², where o² 2 0. We also assume that computation and communication times are statistically independent of stochastic gradients.
Previous Results
2.1 Time complexity with one worker
For the case when = 1 and Ti-+1 = 0, convergence rates and time complexities of problem (1) are well-understood. It is well-known that the stochastic gradient method (SGD), i.c., *+1 = 1
yV {** where { are i.idd. from De. has the optimal oracle complexity O + o² LáL/2
(Ghadimi and Lan, 2013; Arjevani al., 2022). Assuming that the computation time of one stochastic gradient is bounded by h1, can conclude that the optimal time complexity is
Mingl θ h1 x
(LA +
LA
('LA) 2
(3)
seconds in the worst case.
2.2 Parallel optimization without communication costs
Assume that n and Tę- for all i,j E [n], and computation times of stochastic stochastic gradients are arbitrarily heterogeneous. The simplest baseline method in this setup is Minibatch SGD,

---

Table 1: Homogeneous Case (1). The time complexities to get an e-stationary point in the nonconvex
setting. We assume that Tzjj = Tj-i for all ř, E [n|] in this table. Abbr.: o² is defined as
EgllVV - (f < o² for all x E R L is a smoothness constant of f. A = f(=") f
Method
The Worst-Case Time Complexity Guarantees
Comment
Suboptimal for instance, it "linearly""n depends ZEim)
Minibatch SGD
maX
mAx [.JE
max h2 (E.0)
a² iA LA +
ne?
SWIFT (Borsstein 2023)
Suhoptimal since, for instance, it
"linearly depends on max h;;
FE(n]
Asynchronous SGD (Even et ol., 2024)
Suhoptimal, for instance,
even if Tu-3 0', E [x]
Fragile (Corollary 1)
LA
min 1" (*(* [Ns]] ( ) sE(G]
Optimal up to log n factor
Lower Bound (Theurem 1)
AA min e' (e [hd]i-21 (==11==1)"
The mapping t" defined in Definition 2.
et is not trivial to infor the time complexities for these methods. However, in Section 5.4, we discuss some cases where it is transparent that the obtained results are suboptimal.
ot Meaning that the corresponding time complexity + oc if maaxg])))) [n] by + co.
i...
x k+
x
f(r </
(4)
where { are i..d. from De and the gradient V fa {f) is calculated in worker i in parallel. This method waits for stochastic gradients from all workers; thus, is not robust to "stragglers" and in the worst case the time complexity of such an algorithm is
max h, x (L.2 LA )) iE(n]
T θ
which depends on the time max h; of the slowest worker. There are many other more advanced methods including Picky SGD (Cohen et al., 2021), Asynchronous SGD (e.g.. (Recht et al., 2011; Nguyen et al., 2018; Mishchenko et al., 2022; Koloskova al., 2022)), and Rennala SGD (Tyurin and Richtárik, 2023) that are designed to be robust to workers' chaotic computation times. Under the assumption that the computation times of the workers are heterogeneous and bounded by {h:}, Tyurin and Richtárik (2023) showed that Rennala SGD is the first method that achieves the optimal time complexity
--=
= - min mE/n]
(
("A
LA +
o² OLLA
(5)
Reunala
An,
me²
im
where is permutation that sorts h; hr S ... Tr= for all parameters.
1,,,- For instance, one see that Remnala
S
2.3 Parallel optimization with communication costs Ti++j
We now consider the setup where workers' communication times can not be ignored. This problem leads to research field called decentralized optimization. This setup is the primary case for us. All n workers calculate stochastic gradients in parallel and communicate with each other. Numerous works consider this setup, and we refer to Yang et al. (2019); Koloskova (2024) for detailed surveys. Typically, methods in this setting use the gossip matrix framework (Duchi et al., 2011; Shi et al., 2015; Koloskova et al., 2021) and get iteration converge rate that depends the spectral gap of mixing matrix. However, such rates do not give the physical time of algorithms (see also Section B).
Let us consider a straightforward baseline: Minibatch SGD. We can implement (4) in way that all workers calculate one stochastic gradient (takes most max h, seconds) and then aggregate them to one pivot worker j* (takes most max4e(m) Te-s" seconds). Then, pivot worker j" calculates
3

---

Table 2: Heterogeneous Case (17). Time complexities to get an e-stationary point in the nonconvex setting. Abbr.: 0² is defined as Eg (z; (x)
smoothness constant of f = 1 Σ A f(2)) -
I o² for all x E R E [n], L is a
Method
The Worst-Cuse Time Complexity Guarantees
Comment
Minibatch SGD
LA max
max max T max hr) (,5[[n]
suboptimal o f/2 large
se|n]
RolyyGDD Gradient Tracking (Vogels et al., 2021) (Liu al., 2024)
requires local Ly-smooth, suboptimul / large (even e L;; L)
hi
sE(m)
Asynchroncus SQD (Even al., 2024)
requires similarity of the functions {.f+) requires local L, -moooh.
Amelie SGD and Lower Bound (Thm. and Cor. 2)
max
max [.3E[())
Ti-jy max (E(m)
ne
Σ he
Optimal to a constant factor
a new point 2+* and broadcasts all workers (takes maX Ty--s seconds). One can easily see that the time complexity of such a procedure is
} ( (+ + LG
miini == θ max
max (.JE())
Ti-jj max h; [E
(6)
We can analyze any other asynchronous decentralized method, which will be done with more advanced methods in Section 5.4.
But what is the best possible (optimal) time complexity we can get the setting from Section 1.1?
Unlike the setups from Sections 2.1 and 2.2 when the communication times are zero (Ti-aj = 0 for
all j e [n]), the optimal time complexity and an optimal method for the case Ti-j 2 for all
j E [n] are not known. Our main goal in this paper is to solve this problem.
3 Contributions
We consider the class of functions that satisfy the setup and the assumptions from Section 1.1 and show that (informally) it is impossible to develop method that will converge faster than (7) seconds. Next, we develop a new asynchronous stochastic method, Fragile SGD, that is nearly optimal (i.e., almost matches this lower bound; see Table 1 and Corollary 1). This is the first such method. It provably improves on Asynchronous SGD (Even et al., 2024) and all other synchronous and asynchronous methods (Bornstein et al., 2023). We also consider the heterogeneous setup (see Table and Section C), where we discover the optimal time complexity by proving another lower bound and developing new optimal method, Amelie SGD, with weak assumptions. The developed methods can guarantee the iteration complexity O (LA/s) with arbitrarily heterogeneous random computation and communication times (Theorems and 8). Our findings are extended the convex setup in Section D, where we developed new accelerated methods, Accelerated Fragile SGD and Accelerated Amelie SGD.
Lower Bound
In order to construct our lower bound, we consider any (zero-respecting) method that can be repre- sented by Protocol 1. This protocol captures all virtually distributed synchronous and asynchronous methods, such as Minibatch SGD, SWIFT (Bornstein al., 2023), Asynchronous SGD (Even al., 2024), and Gradient Tracking (Koloskova et al., 2021).
For all such methods we prove the following theorem.
Theorem 1 (Lower Bound; Simplified Presentation of Theorem 19). Consider Protocol 1 with V.(::)) We take any h; 2 O and Ti-bj 2 0 for all i,j E [n) such that Ti-sj & Tr-k + Tk-ij for all cLA for some universal constant
i, k E [n]. We fix L, A E, d² that satisfy the inequality
'because je(s Th-4 & maXie(n) Tr-ja + maxxe(n) -x S 2 maxi,jei Tei by the triangle in- equality

---

For any (zero-respecting] algoritim, there exists a fffunction f. which satisfy Assumptions 1, 2 and f0) A, and stochastic gradient mapping f((-),, which satisfies Assumption 3, such that the required time to find soluutioon
LA min (* (Wi (Te (T==)) sE(m
(7)
log
2
LA
min min max max (Taaa N N Σ
(8)
log
JEIn] KE(P]
where, for E [m], my.
Ty. is permutation that sorts {max Ti-+j; i hi ) bee, max (T tis Merga
I max{Txx.. +ds (t
Protocol Simplified Presentation of Protocol 8
1: Init S; 9 (all available information) on worker i for all i E [n]]
2: Run the following two loops each worker parallel
3: while True do
4: Calculate a new point a based on St
(takes seconds) (takes h, seconds) (atomic operation, takes seconds)
5: Calculate a stochastic gradient f((t: {) (or vf(((()))
E~ De
6: Atomic add [((x;; (or Vii(>f; E)) to S,
7: end while
8: while True do
9: Scnd any vector from Ed based St to any worker and go to the next step of this loop (takes Ti-jj seconds to send; worker j adds this vector to Sj)
without waiting
10: end while
(a): When we prove the lower bounds, we allow algorithms to send as many vectors as they want in parallel from worker worker j for all * [ra].
The intuition and meaning of the formula (8) is discussed in Section 5.2. Note that if we take n = 1 and 71-11 = 0 our lower bound reduces to the lower bound (3) up log factor. Moreover, if we take n > 1 and Ti 0 for all i. [n], then (8) reduces to (5) up to a log factor. Thus, (8) is nearly consistent with the lower bounds from (Arjevani al., 2022: Tyurin and Richtárik, 2023). We
get extra log n factor due to the generality of our setup. The reason is technical, and we explain Section E.5.
nutshell, the lower problem reduces to the analysis of the concentration of the time series y" : minje[m] v and yo == min [w,-1 + h.n + イ where vf = 0 for all E [n]], and [v/}} are i.i.d. geometric random variables. This analysis is not trivial due to the minse]n] operations. Virtually all previous works that analyzed lower bounds did not have such problem because they analyzed time series with a sum structure (e.g.. 8² = - TT-1 eT, where {e*} are some random variables, and 7 0).
Let us define auxiliary function simplify readability.
Definition 2 (Equilibrium Time). A mapping t* R22 X 1 X R7 R20 with inputs (scalar), [h (vector), and [ (vector) is called the equilibrium time if it is defined follows. Find a permutation" и that sorts max Fr, h.} as max (T,, h S max max(7 A }. Then the mapping returns the value
7
(s, (hel (T.)))) min max max(Tax k kE(n)
[0, oo).
(9)
New Method: Fragile SGD
We introduce a novel optimization method characterized by time complexities that closely align with the lower bounds established in Section 4. Our algorithms leverage spanning trees. A spanning tree a tree (undirected unweighted graph) encompassing all workers. The edges of spanning trees are virtual and not related to the edges defined in Section 1.1 (see Fig. 1).
It is possible that permutation is not unique, then the result of the mapping does not depend on the choice.
5

---

Algorithm 2 Fragile SGD
1: Input: starting point _²,, stepsize 7, batch size S, pivot worker j", spanning trees st and sine
2: Start Process O (Algorithm 3) in worker j
3: Start Process i (Algorithm 4) in all workers for all [n]] (including worker j*)
Algorithm 3 Process 0 (running in worker j*)
1: for k 0. ,....: K do
2: Send x to Process j*
tiles Tye "5* seconds
3: Init (g*: = (0,0)
4: while < 5 do
5:
Wait for message (g)) send st seas) from Process j
6:
ge + gÿ- vendi s = sh + 55. send
7: end while
8: x .++1 x g
9:
end for
Algorithm 4 Process i (rumning in worker
next = (0, 0) for all E (o....,,K K 1)(0), kimx 2: Run the following three functions in parallel
1: Init (giieeu gk
3: function
4: while True
5: Get new point t sent by Process next so
not necessrilyy equils the curret from
6: Atomic update kiax = max [E, kimax) )
7: for all p such that ne. (p) = do
Di breadessts F further
8:
(h zº to Process and go to the next step without waiting most seconds end for
9:
10: while not received
point
immediittely stops loop when receives point
Calculate V (ax E~
takes at most As second
Run atomic add g.,next = De
nexxt
sh next +
13: end while
14: end while
15:
end function
16: function ReceiieVvctossFrooPrrriovss Workers
17: while True
18: Wait for message (op. s sp.vena) from any Process p such that next,7,;" (p)
&h Run atomic add offnexx = of nexa + Sprsendt ..nee
o i,next + gh
p.send
20: Atomic update kmax max (he, kimax)
21:
end while
end function
23:
function Send VenteeeeTToexeWWooee
while True
25:
Atomic init 9 F.wan
kmax Aimax
Ranax Amax Is,next innxt and reset Amox O, S
Smox 0
26: (h (olrens Aimar to Process next, (i) and wait takes at most manlla y (4) seconds to wait
27: end while
28:
end function
(a): To simplify the listing of the algorithm, we assume here that worker can store K auxiliary vectors in the memory. One can see that it's not necessary, and is sufficient to maintain only one vector Amax. particular, it sufficient to modify the logic Lines and where we run add operations only if k kmax and
k= kmax- The efficient implementation has ((d) floats memory complexity per worker. Send
may try to send through the same edge. In this case, we can interleave their communications and decrease the speed each line by at most two.
(b): www.rrrrhrrnnnnCaaluaattttteeeee

---

Definition 3 (mapping nextr,;(i) Take spanning tree T and fix any worker j E [n]. For i = j. we define nextr.y( (t) O. For all i * J E in], we define nextr,;(i) as the index of the next worker on the path of the spanning tree T from worker i to worker j.
Our new method, Fragile SGD, is presented in Algorithms 2, 4, and 3. While Fragile SGD seems be lengthy, the idea is pretry simple. All workers do three jobs in parallel: calculate stochastic gradients, receive vectors, and send vectors through spanning trees. A pivot worker aggregates all stochastic gradients in &" and, at some moment, does r**1 = I² - -7g". The algorithms formalize this idea.
Algorithm 2 requires a starting point z", a stepsize y, batch size S, the index j* of pivot worker, and spanning trees st and shee for the input. We need two spanning she and st trees because, in general, the fastest communication of vector from j to i and from i to j should be arranged through two different paths. Algorithm 2 starts n + 1 processes running in parallel. Note that the pivot worker j runs two parallel processes, called Process 0 and Process j", and any other worker i runs one Process i. Process O broadcasts a new point x through shee to all other processes and goes to the loop where waits for messages from Process j" Process starts three functions that will be running in parallel: i) the first function's 's job is to receive a new point, broadcast it further, and start the calculation of stochastic gradients, ii) the second function receives stochastic gradients from all previous processes that are sending vectors to worker j", jiii) the third function sends vectors the next worker on the path to j". By the definition of nextzz,5-()) (t), all calculated stochastic vectors are sent to worker jr, where they are first aggregated in Process j", and then, since ge (j*) - 0, Process j will send gfessend to Process O. This process waits for the moment when the number of stochastic gradients 8 aggregated in n is greater or equal to S. When it happens, the loop stops, and Process 0 does a gradient-like step. The structure of the algorithm and the idea of spanning trees resemble the ideas from (Vogels et al., 2021; Tyurin and Richtárik, 2023). The main observation is that this algorithm is equivalent to x++1 = x² - 3 Ei= (i(x;; { where s 2 S and { are i..dd samples. Note that all stochastic gradients calculated at points x², ,...... k will be ignored in the htth iteration of Algorithm 3.
Theorem 4. Let Assumptions 1, 2, and 3 hold. We take q = 1/2T. batch size S = max{[=²/2 1}, any pivot worker j" E [ni) and any spanning trees st and sine in Algorithm 2. For all K 2 16LA/e, 1 K Ek=
we get
K-1
E ff("")) S.
The proof is simple and uses standard techniques from (Lan, 2020; Khaled and Richtárik, 2022). The result of the theorem holds even if h = 0o and Ti-j = oo for all i,j E [n]] because h;2 and Ti only upper bounds on the real computation and communications speeds. In Algorithm 3, each iteration &s can be arbitrarily slow, and still, the result of Theorem 4 holds and the method converges after (LA/E) iterations. The next result gives time complexity guarantees for our algorithm.
Theorem S. Consider the assumptions and the parameters from Theorem 4. For any pivor worker j [n]] and spanning trees st and stre, Algorithm converges after at most
θ (LA ts (o² /s, [ho]i [Pi---- + ()===)(==)))
(10)
seconds, where Ji-13" (i) is an upper bound on the times required to send a vector from worker i to worker jr (from worker jr to worker i) along the spanning tree st (spanning tree slne).
Note that our method does not need the knowledge of {hi} and {pر- to guarantee the time complexity rate, and automatically obtains it.
Corollary 1. Consider the assumptions and the parameters from Theorem 5. Let us take a pivor worker j arg min (d'//e, [6.]ā=1 [T++j T---l==)) and a spanning tree st (spanning tree stoe)
jE(n)
that connects every worker i to worker j* (worker j to every worker i) with the shortest distance Ts (T)) Then Algorithm 2 converges after al most
T. = θ
LA min to (0"/ [ [Te-s + (1)))==))) jE[n
(11)
Def 2
θ
LA min min max max max(Tx +s + Ty-aa ha b o²
(12)
Je(n] kE(n)
seconds, where, for all j E [n], Ty. is permutation that sorts {max + TJ hi )
7

---

This corollary has better time complexity guarantees than Theorem 5 because, by the definition of Ts-tj: Ta-jj S Pi-zj for al i.j E [n]. However, requires the particular choice of pivot worker and spanning trees.
5.1 Discussion
Comparing the lower bound (7) with the upper bound (11), one can see that Fragile SGD has a nearly optimal time complexity. If we ignore the log n factor in (7) and assume that T--j Ty-ss for all 2,j E [n]] which a weak assumption in many applications, then Fragile SGD is optimal.
Unlike most works (Even et al., 2024; Lian et al., 2018; Koloskova et al., 2021) in the decentralized setting, our time complexity guarantees do not depend on the spectral gap of the mixing matrix that defines the topology of the multigraph. The structure of the multigraph is coded in the times {T:mÿ} } We believe that this is an advantage our guarantees since (1I) defines a physical time instead of an iteration rate that depends on the spectral gap.
5.2 Interpretation of the upper and lower bounds (11) and (7)
One interesting property of our algorithm that some workers will potentially never contribute to optimization because either their computations are too slow or communication times j" 1oo large. Thus, only a subset of the workers should work to get the optimal time complexity!
Assume in this subsection that the computation and communication are fixed to {he] and {Ti-a}}- One can see that (12) is the mingelo] minkkej] over some formula. In view of our algorithm, an index j that minimizes in (12) is the index of pivot worker that is the most "central" in the multigraph. An index k- that minimizes minkejn] defines a set of workers {I. xT* that can potentially contribute to optimization, The algorithm and and the time complexity will not depend on workers {T +1,...... " ,n} because they are too slow or they are too far from worker j". Thus, up to a constant factor, we have T. = LAVe max { max Tx ---"""
- x. Mry x= J: d=/e( (><">> 1//a,y..) }}, where T. +
-ラー the time required communicate with the farthest worker that can contribute to optimization, RT is the computa-
tion time of the slowest worker that can contribute to optimization, and a <'/=(E/ i=1 1/nxge.) the time required to "eliminate" enough noise before the algorithm does an update of x."
5.3 Limitations
To get the nearly optimal complexity, it is crucial to select the right pivot worker j" and spanning trees according to the rules of Corollary 1, which depend on the knowledge of the bounds of times. For now, we believe that is this a price for the optimality. Note that Theorem does not require this knowledge and it works with any j and any spanning tree; thus, we can use any heuristic to estimate an optimal j* and optimal spanning trees. One possible strategy is estimate the performance of workers and the communication channels using load testings.
5.4 Comparison with previous methods
Let us discuss the time complexities of previous methods. Note that none of the previous methods converge faster than (7) due our lower bound. First, consider (6) of Minibatch SGD. This time complexity depends on the slowest computation time max;g[1] h; and the slowest communication times maXi.je[m] Ti-aj. In the asynchronous setup, it is possible that one the workers is a straggler, i.e, max,e[n] ha s 0c, and Minibatch SGD can be arbitrarily slow. Our time complexities (10) and (12) robust to stragglers, and ignore them. Assume the last worker is straggler and h, 2o, then one can take permutations with J = n for all j E [m). and the minimum operator minke(s] in (12) will not choose l = n because max
+ Ty-mms.n N= = oo for all j E [n]] TT, max(Tr,,
We now consider recent work by Even et al. (2024), where the authors analyzed Asynchronous SGD the decentralized setting. In the homogeneous setting, their converge rate depends on the maximum compute delay and, thus, is not robust to stragglers. For the case тІ = 0, our time complexity (11) reduces to (5). At the same time, it was shown (Tyurin and Richtárik, 2023) that the time complexity of Asynchronous SGD for T-++ 0 is strongly worse than (5); thus, the result by Even et al. (2024) is
8

---

suboptimal in our setting even if Ti++; = 0 for all i.j [n]. The papers by Bornstein et al. (2023); Lian al. (2018) also consider the same setting, and they share a logic in that they sample a random worker and wail while it is calculating a stochastic gradient. If one of the workers is a straggler, they can wait arbitrarily long, while our method automatically ignores slow computations.
5.5 Time complexity with dynamic bounds
We easily generalize Theorem 5 to the case when bounds the times not static.
Theorem 6. Consider the assumptions and the parameters from Theorem 4. In each iteration k of Algoritim 3, the computation times of worker are bounded by hy Let us fix any pivot worker [n] and any spanning trees st and stre. Then Algorithu 2 converges after most
+ Ek=D [16LA/c] (00 Iut- + +1 =1
(13)
seconds, where pr (1))-1)) is upper bound on limes required to send vector from worker to worker jr (from worker j worker along the spanning tree st (spanning tree stoc) in iteration of Algorithm 3.
This result is more general than (10), and it shows that our method is robust changing com- putation {he } and communication { times bounds during optimization processes. For in- stance, worker n can have either slow computation or communication to j" the first iteration, i.e. max h = ( R then our method will ignore it, but if max(hi, M 1 1i=-j,,5, 1r small the second iteration, then our method can potentially use the stochastic gradients from worker
6 Example: Line Circle
T3-1
3p
0
P
0
P
7
T3-5
2p
T3-22 P
Figure 2: Line with Pit1-i = Pi-++1 = p for all E [n - 1]. Pi-j = oo otherwise. For all i i [m), edges and are merged and visualized with undirected edge.
Let us consider Line graphs where we can get more explicit and interpretable formulas for (11). We analyze ND-Mesh, ND-Torus, and Star graphs in Section A. Surprisingly, even in some simple cases like Line or Star graphs, as far as we know, we provide new time complexity results and insights. In Section J, show that theoretical results are supported by computational experiments.
We take Line graph with the computation speeds h; = h for all E [n], and the communication speeds of the edges Pi-sit1 Pi+1-ii for all i E [n 1] and Pi-j oo for all other i, E [n]. One can easily show the time required to send a vector between two workers i, [m] equals
Th-z Tj-i pli jl. See an example with n = 7 in Fig. 2. We can substitute these values to (11) and get
Tine
LA min min max max - Jy h), jEin] kEin)
oah Ek
(14)
where Tj.1 = T222, 4333 = j + 1,j - or Tj2 R33 = j- ----1,, 1,j so forth. For simplicity, assume that n is odd, then, clearly, j 1-1 minimizes minzejs] and Time
(only for n - 11-12 2) and
ohh/e
if /2///0 $
LA
min dE (O.... )
max { {od, h, [2d+1]
a² ال La h
pot o2n/ne,
if v /2/eep if /a'h/sp 2
(15)

---

According to (15), there are three time complexity regimes: i) slow communication, i.e. Vo'N/ep S this inequality means that p so large, that communication between workers will increase the convergence speed, and the best strategy is to work with only one worker!, ii) medium communication, iee. > /e"h/ep 1, more than one worker will participate in the optimization process; however, not all of them!, some workers will not contribute since their distances T to the pivot worker j" are large, iii) fast communication, i.e., ho 2 n, all n. workers will participate in optimization because p is small.
As far as we know, the result (15) is new even for such a simple structure as line. Note that these regimes are fundamental and can not be improved due to our lower bound (up to logarithmic factors). For Circle graphs, the result is the same up to constant factor.
7 Heterogeneous Setup
In Section C (in more details), consider and analyze the problem
{ f(z) xE
Σ BEWDD (
min
where fi R& Se. + _ and & are random variables with some distributions D, on For i E [r2,, worker can only access fi. We show that the optimal time complexity is
For all
Σ h4 )m)
+
LA max
max Mi-+jo max hi, o² (JEfa
(16)
(E(n)
in the heterogeneous setting achieved by a new method, Amelie SGD (Algorithm 5). Amelie SGD closely related Rennala SGD but with essential algorithmic changes to make it work with heterogeneous functions. The obtained complexity (16) is worse than (12), which is expected because the heterogeneous setting is more challenging than the homogeneous setting.
8 Highlights of Experiments
In Section J, we present experiments with quadratic optimization problems, logistic regression, and a neural network substantiate our theoretical findings. Here, focus highlighting the results from the logistic regression experiments:
0.440
(ngile pul DEST 20
Fook SCl Best See Soptr
kibbarc 500 the Me120
0.330
30
G6925
20-
Tegél 5000 back dier 100dme La houh wich eill bankii 1dd
22
0.915
0.4 times (seconds)
1e6
0.5
0.2
times (seconds)
0.4
1.5 le6
Figure 3: The communication time 10 seconds (Slow communication) in 2D-Mesh
On MNIST dataset (LeCun et al., 2010) with 100 workers, Fragile SGD is much faster and has better test accuracy than Minibatch SGD.
Acknowledgments and Disclosure of Funding
The research reported in this publication was supported by funding from King Abdullah University of Science and Technology (KAUST): i) KAUST Baseline Research Scheme, ii) Center of Excellence for Generative AI, under award number 5940, iii) SDAIA-KAUST Center of Excellence in Artificial Intelligence and Data Science. The work of A.T. was partially supported by the Analytical center under the RF Government (subsidy agreement 000000007:3022P5000002 Grant No. 70-2021-00145 02.11.20
10

---

References
Arjevani, Y., Carmon, Y., Duchi, C., Foster, D. J., Srebro, N., and Woodworth, B. (2022). Lower bounds for non-convex stochastic optimization. Mathematical Programming, pages 1-50.
Bornstein, M., Rabbani, T., Wang, E., Bedi, A. S., and Huang, F. (2023). SWIFT: Rapid decentralized federated learning via wait-free model communication. The 1 Ith International Conference on Learning Representations (ICIR).
Carmon, Y., Duchi, J. C., Hinder, O., and Sidford, A. (2020). Lower bounds for finding stationary points i. Mathematical Programming, 184(1):71-120.
Cohen, A., Daniely, A., Drori, Y., Koren, T., and Schain, M. (2021). Asynchronous stochastic optimization robust to arbitrary delays. Advances in Neural Information Processing Systems, 34:9024 9035.
Duchi, C., Agarwal, A., and Wainwright, M. J. (2011). Dual averaging for distributed optimization: Convergence analysis and network scaling. IEEE Transactions on Automatic control, 57(3)5592- 606.
Even, M., Koloskova, A., and Massoulié, L. (2024). Asynchronous SGD on graphs: A unified framework for asynchronous decentralized and federated optimization. In Artificial Intelligence and Statistics. PMLR.
Floyd, R. W. (1962). Algorithm 97: shortest path. Communications the the ACM, 5(6):34
Ghadimi, S. and Lan, G. (2013). Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, (144)224412266
Huang. X., Chen, Y., Yin, W., and Yuan, K. (2022). Lower bounds and nearly optimal algorithms in distributed learning with communication compression. Advances in Neural Information Processing Systems (NeurIPS).
Khaled, A. and Richtárik, P. (2022). Better theory for SGD in the nonconvex world. Transactions on Machine Learning Research.
Koloskova, A. (2024). Optimization algorithms for decentralized, distributed and collaborative machine learning. Technical report, EPFL.
Koloskova, A., Lin, T., and Stich, U. (2021). An improved analysis of gradient tracking for decentralized machine learning, Advances in Neural Information Processing Systems, 34:1 1422- 11435.
Koloskova, A., Stich, U., and Jaggi, M. (2022). Sharper convergence guarantees for asynchronous SGD for distributed and federated learning. Advances in Neural Information Processing Systems (NeurIPS).
Lan, G. (2020). First-order and stochastic optimization methods for machine learning. Springer.
LeCun, Y., Cortes, C., and Burges, C. (2010). Mnist handwritten digit database. ATT Labs [Online]. Available: http://yann.. www.n..eecccccoo. wwwp....o//xx///mnss.tttmmm 2.
Lian, X., Zhang, W., Zhang, C., and Liu, J. (2018). Asynchronous decentralized parallel stochastic
gradient descent. In International Conference on Machine Learning, pages 3043-3052. PMLR.
Liu, Y., Lin, T., Koloskova, A., and Stich, S. U. (2024). Decentralized gradient tracking with local steps. Optimization Methods and Software, pages 1-28.
Lu, Y. and De Sa, C. (2021). Optimal complexity in decentralized training. International Conference Machine Learning, pages
PMLR.
Mishchenko, K., Bach, F., Even, M., and Woodworth, B. (2022). Asynchronous SGD beats minibatch SGD under arbitrary delays. Advances Neural Information Processing Systems (NeurIPS).
Nesterov, Y. (1983). A method of solving a convex programming problem with convergence rate (1/k** 2). Doklady Akademii Nauk SSSR, 269(3):543.

---

Nguyen, L.. Nguyen, P. H., Dijk, M., Richtárik, P., Scheinberg, K., and Takáe, M. (2018). SGD and hogwild! convergence without the bounded gradients assumption. In International Conference on Machine Learning, pages 7758. PMLR.
Recht, B., Re, C., Wright, S., and Niu, F. (2011). Hogwild!: A lock-free approach to parallelizing stochastic gradient descent. Advances Neural Information Processing Systems, 24.
Scaman, K., Bach, F., Bubeck, S., Lee, Y. T., and Massoulié, L. (2017). Optimal algorithms for smooth and strongly convex distributed optimization in networks. In International Conference Machine Learning, pages 3027-3036. PMLR.
Shi, W. Ling, Q. Wu, G., and Yin, W. (2015). A proximal gradient algorithm for decentralized composite optimization. IEEE Transactions on Signal Processing. 63(22):6013-6033.
Tyurin, A., Pozzi, M., Ilin, I., and Richtárik, (2024). Shadowheart SGD: Distributed asynchronous SGD with optimal time complexity under arbitrary computation and communication heterogeneity. arXiv preprint arXiv:2402.0475:
Tyurin, A. and Richtárik, P. (2023). Optimal time complexities of parallel stochastic optimization
methods under fixed computation model. Advances in Neural Information Processing Systems (NeurIPS).
Van Handel, R. (2014). Probability in high dimension. Lecture Notes (Princeton University).
Vogels, T., He, L., Koloskova, A., Karimireddy, S. P., Lin, T., Stich, S. U., and Jaggi, M. (2021). RelaySum for decentralized deep learning on heterogeneous data. Advances Neural Information Processing Systems, 34.
Yang. T., Yi, X., Wu, J., Yuan, Y., Wu, D., Meng. Z., Hong, Y., Wang, H., Lin, Z., and Johansson, K. H. (2019). A survey of distributed optimization. Annual Reviews in Control, 47:278-305.
12

---

Contents
Introduction
1.1
Decentralized setup with times
2
Previous Results
2.1
Time complexity with one worker
2.2
Parallel optimization without communication costs
2.3
Parallel optimization with communication costs Ti++
3
Contributions
4
Lower Bound
5
New Method: Fragile SGD
5.1
Discussion
5.2
Interpretation the upper and lower bounds (11) and (7)
5.3
Limitations
8
5.4
Comparison with previous methods
8
5.5
Time complexity with dynamic bounds
6
Example: Line Circle
7
Heterogeneous Setup
10
8 Highlights of Experiments
10
More Examples
15
A.I ND-Mesh or ND-Tonus
15
A.2 Star graph
16
A.3 General case
16
B On the Connection to the Gossip Framework
16
C Heterogeneous Setup
17
C.I Lower bound
17
C.2 Amelie SGD: optimal method in the heterogeneous setting
17
C33 Discussion...
19
C.4 Comparison with previous methods
19
D Convex Functions in the Homogeneous and Heterogeneous Setups
19
D.I Assumptions in convex world
19
D.2 Homogeneous setup and nonsmooth case
20
D.3 Homogeneous setup and smooth case
20
13

---

D.4
Heterogeneous setup and nonsmooth case
21
D.5
Heterogeneous setup and smooth case
................................
22
D.6 On lower bounds
................................
23
D.7
Previous works
23
Lower Bound: Diving Deeper into the Construction
24
E,1
Description of Protocols and
24
E.2 Lower bound
25
E.3
Proof sketch of Theorem 19
26
E,4 Full proof of Theorem 19.
28
E.5 Proof of Lemma 2
31
E.6
Proof of Lemma
34
Lower Bound in the Heterogeneous Setup
36
G Proof of the Time Complexity for Homogeneous Case
38
Proof of the Time Complexity for Heterogeneous Case
41
I Classical SGD Theory
44
J Experiments
46
J.1 Experiments with Logistic Regression: Fast vs Slow Communication
48
J.2 Experiments with ResNet-18
48
14

---

16
25
p
p
P
3
5
26
P
p
P
P
27
6
8
10
13
22
P
P
P
23
11
13
14
15
P
P
P
15
24
P
P
P
10
19
16
17
18
19
20
0
20
P
P
22
23
24
25
12
21
(a) 2D-Mesh
(b) 3D-Mesh
Figure 4: Examples ND-Mesh graphs. For all é o E [m]] edges + and j - are merged and visualized with one undirected edge.
A
More Examples
A.1 ND-Mesh or ND-Torus
We now consider generalization of Line graphs: ND-Mesh graphs. Figures and 4b, we present examples of 2D-Mesh and 3D-Mesh. For simplicity, assume that n (2k + 1) for some k E N. The computation speeds h; for all E [n], and the communicate speeds of the edges Pi-oj = if workers i and j are connected in mesh and Pi-ij &o for all other i, [ni]. Using geometrical reasoning, clear an index j", that minimizes (11), corresponds to the worker in the middle of graph (13 in Figures 4a and 14 in Figures 4b). Therefore,
(1A
LA
o²h Tn h, ke })
TDD-Mesh = θ
min max kE(m]
For now, let consider 2D-Mesh graph. The number of workers, that have the length of the shortest path to j" equals to 0, is 1. The number of workers, that have the length of the shortest path to j less or equal to p, is 5. The number of workers, that have the length of the shortest path to j less equal to 2p. is 13. In general, the number of workers, that have the length of the shortest path to j less or equal to Vkp, is ((k) for all k E (O...., θ (n)). It means
T2D-Mesh = θ
LA
min
max Vkp. h
2²h
}
((n)
(k
1)=
2/3
dah
dhh
S 1,
θ
LA
h
+
22/
12h
1/3
TL
ah
2/3
1,
pe
2/3
ahh
ne
pe
Using the same reasoning, for the general case with ND-Mesh graph, we get
LA
2²h
TND-Mesh =
min 8 ke((U...((n))
max
I/N p. h, (k + 1)e
N/(++1)
a²h
oah
II,
LA
1/(N+1)
N/(N+1)
θ
h
NI(+11) 2h
oh
>1,
pe N/(N+1)
ah
2
As in Line graphs, these complexities have three regimes depending on the problem's parameters. Up to constant factor, the same conclusions apply to ND-Torus.
15

---

A.2 Star graph
Let us consider Star graphs with different compulation and communication speeds. Let us graph with n + workers, where one worker with the index nt + 1 is in the center, and all other workers are only directly connected worker
Then,
T Pi-++1 Pn+1-*j Vi [n and Tioi Vi E [n].
Using these constraints, we can simplify (11). There are two possible best strategies: i) a pivot worker j" works locally without communications, ii) pivot worker j works with communications but would necessary require to communicate through the central worker; in this case, the central worker 1 is pivot worker. Therefore, we get
LA
o2hg
Taar min
min max JEjN
hij
LA
o²
min max max max((pmm) (f -nn+1 + Px+1 Put1-1844100 h n ml
Σ
hootia
since TR+1-t%e41 Pa+11 + for all & E [n+ 1]. Let us slightly simplify the result and assume that broadcasting from the central worker fast, i.e., Put1-+i S Pi--n+1 for all i E [n + 1], then
LA
o2h E
sun = min
min max JEjn
hy:
Tam omm.
LA
k
min max kE/n]
max max P tat1, h :
8
Tratoomn
Tyurin al. (2024) also considered Star graphs and showed that Tisst comm. is the optimal time complexity for methods that communicate through the central worker. Our result is more general since we also consider decentralized methods and capture the term Tatow comm. that can be potentially smaller if communication is slow. Tyurin et al. (2024) conjectured that T is the optimal bound, and we proved (up log factor) here.
A.3 General case
We show how one can use our generic result (11) to get an explicit formula some cases. For the general case with arbitrary communication and computation times, the minimizers j and & in (11) can be found in the following way. First, we have to find Ti-j using any algorithm that solves the
all-pairs shortest path problem (e.g., Floyd-Warshall algorithm (Floyd, 1962)). Once we know Ti-jj we should sort {max Ti-si, ht } for all j E [n]] to find the permutations. Finally, we have enough information to calculate from Definition 2.
B
On the Connection to the Gossip Framework
Most of the previous methods were designed for different setting, gossip-type communication. In fact, our setting is more general than the gossip communication. Indeed, recall that in the gossip com- munication, worker i is allowed to get vectors from other workers through the operation Σø=1 WijFjj our setting for the case when the communication time where Waj E {0, 1}. This is equivalent if wij is not zero, and worker é sums the received vectors. Psy = 00 when Wij is zero, and Pij
But our setting is richer since allow different communication and computation times and allow workers to do whatever they like with vectors (not only to sum).
Moreover, the gossip framework codes the communication graph through the matrix (wyy.. We propose to code graphs through the times {Piz} ((Tyy)). Our approach is closer to real scenarios because, explained previously, it includes the gossip framework.
16

---

C
Heterogeneous Setup
We now consider the heterogeneous setting. The only difference is instead of (1), we consider the following problem.
min rER"
{(x)
Σ Eg BEND (f)(
(17)
f((x):
where fi 1&d x gg + IRd and & are random variables with some distributions D, on Sg. We now present our upper and lower bounds and discuss them.
C.1 Lower bound
In Section prove the following lower bound.
Theorem 7 (Lower Bound; Simplified Presentation of Theorem 20). Consider Protocol I with -f(ss)). We take any h& 2 0 and Ti-aj 2 O for all i, E [ni] such that Ti-j S Tiisk Tk-+j for all i, j E [n]. We fix L, A, o2 > that satisfy the inequality E < cLA for some universal constant c.
For any (zero-respecting) algorithm, there exists a function f 1. Σ fe, which satisfy Assumptions 1,
2 and ((0) - < A, and stochastic gradient mappings V (15 ), which satisfy Assumption 3 (Eg V (x;;;; [i(x)) and Eg [i [=(()) S o ), such that the required time to find E-solution is
LA
o²
h4 )})
Ω
max
max (Je(n)
Ti-s max h4s [E(n)
me
seconds.
C.2 Amelie SGD: optimal method in the heterogeneous setting
We now present a new method based on Malenia SGD from (Tyurin and Richtárik, 2023) and our Fragile SGD. As in Fragile SGD, we also have + 1 processes rumning in all workers. The main idea that all workers calculate stochastic gradients parallel and accumulate them locally. Process zero waits for the moment when by- 2 S Process i calculates b; in Line 20 of Algorithm 7, and sends it to Process nextzz,-- (i). Thus, by- accumulates the sum E s which decreases with time since a is the number of calculated stochastic gradients in worker i in different moments of time. Therefore, hy. 2 will hold at some point of time if workers continue computing gradients. Finally, Algorithm runs all reduce and does the update of k
Theorem 8. Let Assumptions I and 2 hold for the function f and Assumption 3 holds for the functions foror all E [n). We take 1/2L, the parameter S max{ /2/=] _). any pivot worker j E [n], and any spanning trees st and stne; in Algorithm 5. For all iterations number 2 16T. we get V Se.
EKK1 K-1
Note that Theorem states the convergence of Amelie SGD if the computation and communication speeds are unbounded.
Theorem 9. Consider the assumptions and the parameters from Theorem 8. For any pivot worker j* [n] and any spanning trees st and stre, Algorithm 5 converges after at most
LA
1
θ
max
max μiーメj max hig (.jE[N]
h
sEIn]
i=1
seconds, where -3- (1)=->) is an upper bound on times required to send vector from worker to worker 5" (from worker jr to worker i) along the spanning tree st (spanning tree stee) for all i [n].
17

---

Algorithm 5 Amelie SGD
Input: starting point xº, stepsize ", parameter S, pivot worker j", spanning trees st and siae
2: Start Process O (Alg. 6) in worker j
3:
Start Process (Alg. 7) all workers for all i [n] (including worker j*)
Algorithm 6 Process 0 (running in worker j*)
for k 0, ,,...., K 1 do
2: Broadcast x to all workers using the spanning tree stne
3: Init s
4: while s* < do
5: Wait for message by- from Process j*
6: Calculate s bya
7: end while
8: Run all reduce with l ( find g" = Σ
using the spanning tree st
87
9: h+1 7
end for
Algorithm 7 Process i (running worker
while True do
2: Get new point x broadcasted by Process 0
3: Init (gf s (0,0) 0)
4: Init bip = x: for all p [n]] s.t. next (p) =
5:
Run the following three functions parallel and go to Line 24
6: function CacullaeSSochastiiCraaiiene
7: while True
8: Calculate vf(=*,;)) { &~ D.
9: Run atomic add of = of sf = +1
end while
11: end function
function ReciieCouneesFFooPPPrrssssooo Workes
13: while True
Wait for message b, from any Process s.t. next,z,j 3z (p) =i
15:
Run atomic update bi,p bp
16:
end while
17:
end function
18:
function SendCoumne/ToNeetWooeee
19:
while True
20:
Run atomic sum b, =
Σ
B + o7
pe pE[n]]:est,z..p (p)=z
21:
Send b; E R U {oo} (one float) to Process next (i) and wait while sending
(Process j" sends to Process 0 by the definition of next,,,,- (.))
22:
end while
23: end function
24:
Wait for new point. If receives new point, stop all computations in functions, and continue
25:
Ignore all non-received messages
26: end while
18

---

Corollary 2. Consider the assumptions and the parameters from Theorem 9. Let us take any pivor worker j [n]] and a spanning tree st (spanning tree stee) that connects every worker to worker j' (worker j to worker i) with the shortest distance Ti- (Tz--ih, then Algorithm 5 converges after at most
LA
d²
71
)})
max
max Ti max hi: [.j[[n]
2 11
(18)
g
=E(n]
ne
71
seconds.
C.3 Discussion
Corollary 2 together with Theorem 7 states that the time complexity (18) is optimal. The result is
pessimistic since the time complexity depends on the "diameter" maX4.j 7i-t5 and the slowest observed in (Lu and De Sa, 2021; Tyurin and
performance maXie[m] h4. A similar dependence Richtárik, 2023). As in (Tyurin and Richtárik, 2023), the stochastic term 0 /n/ne (//n Di=1 hy) depends on the average of {h:} if o// is large.
C.4 Comparison with previous methods
Let us consider Minibatch SGD described in Section 2.3. This method converges after
TA max (
o² max max Ti-ji max h.) })
max
Ti max his RE(n] nE (JEim]
(.f ml
sE(n]
seconds the heterogeneous setting. If of is large, then Amelie SGD can be at least
max max Ti-sh max hi3/ (j((n
(E(m)
times faster than Minibatch SGD. There are many more advanced methods (Lu and De Sa, 2021; Vogels et al., 2021; Even al., 2024) that work in decentralized stochastic heterogeneous setting. Lu and De Sa (2021) developed similar lower and upper bounds, but there are at least three main differences: i) they derived an iteration complexity instead of time complexity and assumed the performances of all workers are the same ii) the obtained lower bound holds only for one particular multigraph while our complexity holds for any multigraph iii) they assumed the smoothness of fi, while we consider the smoothness of f. The RelaySGD and Gradient Tracking methods by Vogels et al. (2021); Liu et al. (2024) wait for the slowest worker; thus, they depend on max;e|n] h; in all regimes of d²/e, unlike our method. Even et al. (2024) consider the heterogeneous asynchronous setting, but their method assumes the similarity of the functions fi, which is not required in our method, and Amelie SGD converges even if there is no similarity of functions.
D Convex Functions in the Homogeneous and Heterogeneous Setups
We will be slightly more brief in the convex setting since the idea, the structure of time complexities, and the general approach do not change significantly. For instance, instead of the time complexity (1I) that we get for the nonconvex case, the nonsmooth convex case, we get (20). Thus, we will
get θ x" minje[m] t* ("*/as², ....) instead of θ مA minje(m) t* (d') The same idea applics to the smooth convex case. In the convex setting, we need the following assumptions.
D.1 Assumptions in convex world
Assumption 4. The function f is convex and attains a minimum at some point x² E Rd
Assumption 5. The function f is M -Liiscchitz, i.e.,
If(x) - f()) S M ||x - -lll Ve, y e Rd
for some M E (0)
19

---

Assumption 6. all IR stochhstiic (sub)gradients fz; are unbiased and are o² variance-
bounded, ie, BE-D [V](2;)) {)] E (z()) and ES-D | [x;; {
BE-D [V[(=;))] S S where
o² 2 O.
D.2 Homogeneous setup and nonsmooth case
Theorem 10. Let Assumptions 4, 5 and 6 hold. Choose any = max { [[<//r²] ,1}, stepsize ? = M240278 2M T
O. Let take the batch size & any pivot worker j E [n], and any spanning trees st and slic in Algorithm 2. Then after K 2M2 1²/22 iterations the method guarantees [{(**]] [(x*) S, where E EK-1 x² and = =11=* 11~==~-'" x
Proof. The proof of Theorem 10 is almost the same in Theorem 4 (see Section G). The proof of Theorem states that the steps of Fragile SGD are equivalent to the classical SGD method. Thus, we use the classical result from the literature (Lan, 2020). Using Theorem 22, we get
E [f(**)]
f(x") E
2M
1
0² (M²
x
x 10
2
5
?²
2
for the stepsize
7
M + o²
2M M
where use the fact that S 2 d² o²/M12
Theorem 11. Consider the assumptions and the parameters from Theorem 10. For any pivot worker j [n] and spanning trees and stye, Algorithm converges after at most
(M
(M (d//MM² (ho]i [15-33' + -1- +1---111=1)
(19)
seconds, where [Di-ij (1iz--2) is upper bound on times required to send vector from worker to worker jr (from worker jr to worker i) along the spanning tree st (spanning tree stoe).
Proof. The proof identical the proof of Theorem 5.
Corollary 3. Consider the assumptions and the parameters from Theorem 11. Let us take pivor worker j = arg minje(m] t" (d/arr, [hd] [T-o5 + T)-il:= and a spanning tree st (spanning tree slie) that connects every worker to worker j (worker j to every worker i) with the shortest distance Ti-aj" (z)) Then Algorithm 2 converges after at most
(
M R²
min t² (²(02/////0/ [hi (T-yy Ty-nl==)) jE(n]
(20)
seconds.
D.3 Homogeneous setup and smooth case
In the homogeneous and smooth case, we will slightly modify Fragile SGD. Instead of Line 8 of Algorithm 3, we use the following steps:
7++1 7 (k + 1), ax+1 2/(k+
y A+1 = (1 - a2t1)a* + autiu" (u = x²)
n r+1 n 7kt1
(21)
sh g":
z k+1 (1 abt1)a* + a411
We will call such method the Accelerated Fragile SGD method. The idea use the acceleration technique from (Lan, 2020) (which is based on (Nesterov, 1983)).
20

---

Theorem 12. Let Assumptions 4, and 3 hold. Choose any > 0. Let us take the batch size = max { 1 min
3R'S 1/2
any pivot worker j", and any spanning trees st and slnc Accelerated Method 2 (Accelerated Fragile SGD), then after K 2 8/IR iterations the method guarantees that E Ve
42' +
[f f(x*)((=++))))))()) S where R = || - 2011
Proof. Using the reasoning in Theorem Accelerated Fragile SGD is just the classical accelerated stochastic gradient method with a batch size greater or equal to S. We can use Proposition 4.4 from Lan (2020). For the stepsize
3R2
1/2
7 min
4L
A 1)((
2)
we have
4LR
4V
[[(=*)]] f(x²)( s
K2 +
VSK
Therefore,
E [f(x*)] -(xx) S
K SVLR Ve
VLR o² R2
max
V8 22
where we the choice of S.
Theorem 13. Consider the assumptions and the parameters from Theorem 12. For any pivot worker
j [n] and spanning trees st and si Accelerated Algorithm 2 (Accelerated Fragile SGD) converges after at most
VLR VE
o²R E3/2VI'
[hi]ii,,lP-pp + My -
(22)
seconds, where (1-++j (1ig->s) an upper bound times required to send vector from worker to worker (from worker j" to worker i) along the spanning tree st (spanning tree stoa).
Proof. The proof is identical to the proof of Theorem 5.
Corollary 4. Consider the assumptions and the parameters from Theorem 13. Let us take a pivor worker j* arg minje(n) t*
/3/2/I' [ho] [Ti+s + T==+)==)) and spanning tree st (spanning tree sthe) that connects every worker to worker ja (worker j* to every worker i) with the shortest distance Tu-z5" (i). Then Accelerated Algorithm 2 (Accelerated Fragile SGD) converges after at most
o²R
(
VLR min to JE(n)
o²R R
θ
(TIS ---1)=11
(23)
Ve
///2
seconds.
D.4 Heterogeneous setup and nonsmooth case
Consider the optimization problem (17). Theorem 14. Let Assumptions 4, 5 hold for the function I and Assumption 6 holds for the func- tions Sa for all [n].. Choose any & >> O. Let us take the batch size S max { ,n), 7 = M2+0219 E [ ]. any pivot worker j* E [n], and any spanning trees st and stoe. in Algorithm 5, then after K 2M5 ne2R2 /22 iterations the method guarantees that E [f(**]] f( S
where TK R ΣK-1 4 and R =|10" zºI1.
21

---

Proof. The proof of Theorem 14 is almost the same as in Theorems 8 (see Section H). The proof of Theorem states that the steps of Amelie SGD are equivalent to the classical SGD method. Thus, we can use the classical result from the literature (lan, 2020). Using Theorem 22, we get
[](**]] f(x") E
2M
x² 2013
x² (M²
x
x 2012
2
2²
22
for the stepsize
E
E
M +
0²
E
2M
M
where we use the fact that S 2 /M/.
Theorem 15. Consider the assumptions and the parameters from Theorem 14. For any pivot worker j E [n] and any spanning trees st and stee, Algorithm 5 converges after at most
(ME
M2R² R2
a² nM²
+
max
(i-ッj his iE(n]
h4
(24)
E2
i.Ei
seconds, where 1i-z3' (ufj-=s) ) is upper bound times required to send vector from worker to
worker j" (worker j to worker i) along the spanning tree st. (spanning free slnc) for all [n].
Proof. The proof is identical to the proof of Theorem 9.
Corollary Consider the assumptions and the parameters from Theorem 15. Let us take any pivot worker j [m] and spanning tree st (spanning tree slnc) that connects every worker to worker j' (worker j to worker i) with the shortest distance Tz-43" (Tj=-shh, then Algorithm converges after at most
M R2
σ²
1
Σ h4 )}
+
max
max Ti-si max hi: i.jEmn]
E2
sE|n]
n.22
seconds.
D.5
Heterogeneous setup and smooth case
Consider the optimization problem (17). In this section, the same idea as in Section D.3. We will modify Amelie SGD and, instead of Line from Algorithm 6, we use the lines (21). call such method the Accelerated Amelie SGD method.
Theorem 16. Let Assumptions 4 and hold for the function f and Assumption 3 holds for the .n.
functions ft. Choose any 0. Let us take the batch size S = max (
1/2
7 min AL'
3R2S
any pivot worker jr, and any spanning trees st and she
in Accelerated Method (Accelerated Amelie SGD), then after K
> SvLR Ve
iterations the method
guarantees that IE [x] f(x*) < E, where R = || x =
Proof. Accelerated Amelie SGD equivalent to the accelerated stochastic gradient method with mini-batch from Lan (2020). The proof repeats the proofs of Theorem 12 and Theorem 8.
O
Theorem 17. Consider the assumptions and the parameters from Theorem 16. For any pivot worker j [n] and any spanning trees st and stee Accelerated Algorithm 5 (Accelerated Amelie SGD) converges after at most
VLR
o²R
max μ4ーj max h. (JEMM
h;
(25)
1E[m]
//2
i=1
seconds, where uZ (1fj-)))
2 is an upper bound on times required to send vector from worker to worker (worker jr to worker i) along the spanning tree st (spanning tree stoe) for all i E [n].
22

---

Proof. The proof is identical to the proof of Theorem 9.
Corollary 6. Consider the assumptions and the parameters from Theorem 17. Let us take any pivot worker j [n]] and spanning tree st (spanning tree sire) that connects every worker to worker j' (worker j to worker i) with the shortest distance Ti-ij" (Tz=-s), then Accelerated Algorithm (Accelerated Amelie SGD) converges after most
VLR VE
o²R
2 h4 )
θ
Ti+js max h4:
(26)
sc[n]
nE VL
seconds.
D.6
On lower bounds
In previous subsections, we provide upper bounds on the time complexities for different classes of convex functions and optimization problems. Using the same reasoning as in Section 4 and (Tyurin and Richtárik, (S23)(n B], we conjecture that the obtained upper bounds are tight and optimal (up to log factors in the homogeneous case).
D.7 Previous works
Let consider the time complexities (20) and (23) (accelerated rate) in the homogeneous and convex cases. When Ti- for all i E [n]] Even et al. (2024) recovers the time complexity (nonaccelerated in the smooth case) of Asynchronous SGD (Mishchenko et al., 2022: Koloskova et al., 2022) which is suboptimal (Tyurin and Richtárik, 2023). When the communication is free, we recover the time complexity (accelerated in the smooth case) of Accelerated Rennala SGD from (Tyurin and Richtárik, 2023), which is optimal if ri-
for all i. E [n.]
In the heterogeneous and convex setting, (26) improves the result from (Even et al., 2024) since (26) is an accelerated rate and does not depend on a quantity that measures the similarity of the functions f.. When 2017). However, when > 0, as far as we know, the time complexity (26) is new in the convex smooth setting.
the result (26) is consistent with the lower bound from (Scaman al.,
23

---

E Lower Bound: Diving Deeper into the Construction
Protocol 8 Time Multiple Oracles Protocol with Communication
1: Input: function f (or functions f:) computation oracles {O: O()) communication oracles
{C [0 algorithm {[M*, L D* P n VÝ. ..... v.).., V E A
2: 8 $/ = 0 for all i,J E [n]. p P N
4.0
3: for = 0 O..... 00 do
4:
(1*+1 c++l)= MM (g) ................................ In 9i
Fn 11...
th+1 th
5:
if ck++1 = =0 then
6:
get L L" In. g. ....... Fn. In.... I .......... g.)
7:
a P (g) 19 1
8:
($
h,++1 ghhi1l
k-1) = O (th
+1
x
1111
(1111)
DVj + shtl, : :,}
h,+11
k+1
9j
9:
else
10:
jk+1 jttl ptt1 = D (g) ... In
Φi pi..... ....... gii)
11:
oftt = Visn (1/410/ gptt1)
12:
(8,4t1,5 1 , g
k+1
0 g++ -pttt (t++1 ; jett ghtt pp+t1)
h+1
J,ke
D-jj # jkttl 9g
k+1 = 0, vi + jkt1
j + jkitt # pht1 s.+11 T.k
13:
end if
14:
end for
In Section 4, we present a brief overview and simplified theorem for the lower bound. We now provide formal and strict mathematical construction.
E.1 Description of Protocols 8 and
One way how we can formalize Protocol I is use Protocol 8. Let us explain it. Using Protocol we consider any possible method that works in our distributed asynchronous setting. The mapping M of the algorithm returns the time + (ignore for now) and c If c 0, then the algorithm decides to start the calculation of a stochastic gradient: it determines the index f of worker that will start the calculation, then, using all locally available information giet...... - it calculates a new point x. 2f++1, and passes this point to the computation oracle 0,,42 that will return a new stochastic gradient after ha++1 seconds. If c+1 = 1, then the algorithm decides to communicate a vector: returns the indices ;++1 and jk+1 of two workers that will communicate, and the index ph+1 E N of a communication oracle, calculates oft+ in worker +++1 using only all locally available
that will send information o... gi and passes it to the communication oracle C the vector after - seconds.
The computation oracles define
R O
R20
Rd
(R20 Rd x (0,
(Rzo x Rdd x t0, 1}) xBd
time
point
inpul state
output state
(11, 1,,
0), 8g = 0,
such that
O,(t, (St, (
(181, 1),
0), 8q 1, t 8: + h4s
(27)
((0,0,0,
V (s(aa; E)),
8g = 1, 1 2 8t + his
where & ~~2 D.
The communication oracles we define
CP
R
R x {0.1))
+ R x Rd x {0, 1}) xRd
point
input state
output
24

---

((t,,,
0). 8q 0,
such that 25 82,
((s,, 82,1);
0). = t < 3t + Ti-s
(28)
(00,0,0,
82). bq t St + Ti-sj-
The idea is that the computation oracle (27) emulates the behavior of a real worker that requires h; seconds calculate stochastic gradient. The communication oracle emulates the behavior of a real communication channel that requires Ti++ seconds to send vector from worker to worker j.
One can see that, for all j E [m), an algorithm can access infinite number of communication oracles Ci=j; C Cejj..... We allow an algorithm to send as many vectors from worker to worker in parallel it wants.
We now discuss the role of th+1, One can see that the time + 1 is returned by the algorithm, and gh+1 called with (K+1 for the first vector because (s )y 0 (see (27)) at the beginning. Then, by the
passed to the oracles Ojo+1 and Ch -++1- Consider that Op+41
time, then it will return construction of (27), the oracle will return a non-zero vector in the second output only the algorithm
returns a time that is greater or equal to g + h,t+1. The same idea applies to Cp - it was called +++1 for the first time, then worker j will get non-zero vector only if the algorithm passes a time that is greater or equal to gk+1 + Taa++
The oracles force the algorithm to increase the time t otherwise, it will not get new information (s {) in (27)) about the function. One crucial constraint is g > th, meaning that the algorithm can not "cheat" and travel into the past. The idea of such a protocol was proposed in Tyurin and Richtárik (2023), and refer to Sections 3-5 for a detailed description. A more readable and less formal version of Protocol is presented in the Protocol
E.2 Lower bound
Before state the main theorem, let us define the class of zero-respecting algorithms.
Definition 18 (Algorithm Class Az). Let us consider Protocol 8. We say that the sequence of tuples of mappings {[M*, L* D* pk pk ViK V ) is a zero-respecting algorithm,
1. M Rd x ... x Rd + Rz0 x {0, 13 for all & 2 1, and M E Rg x {0,1}.
nxk times
2. L Rd ... x Rdd
[n] for all & 2 1, and 1 E [m].
n times
3. D Rd x
x Rd
[n] in] N for all 22 1, and D E [m] x [m]
nxk times
4. For all [n], Pf
Rd x ... x Rdd + Rd for all & 2 1, and Po e Rd.
times
5. For all [m), V/ Rd
Rd
Rd for all l 2 and V Rd.
times
6. For all k 2 1 and gf. In gi
Ln ......,
............................ thh E Rd.
|++1 > 1/
where th+1 and t are defined (t++1 )...) M (g)) ... gh. pf...., .t.............. .......)) and (I.,...) k (ot gh o4 ......... F P : .
k
gn 1).
7. For all i E [n], supp (a+² C _ 1-1 supp g and supp (x c U supp (st) for all
& No, where supp (z) == {i E [d] x
+ 0}
The set of all algorithms with this properties we define as A..
25

---

Constraints 1-5 define domains of the mappings. Constraint 6 is required to ensure that the time sequence t does not decrease. Constraint 7 is a standard assumption that an algorithm is zero- respecting (Arjevani et al., 2022).
Theorem 19. Consider Protocol 8. We take any his 2 O and Ti-jj 2 0 for all i, E [n] such that Ti-oi S Tr-tk + Tk-2j for all i, k.j E [n]. We fix L, E. > O that satisfy the inequality L.. For any algorithm A Aa, there exists function f. which satisfy Assumptions I, 2 and f(0) f A, and a stochastic gradient mapping ff(:))), which satisfy Assumption 3, such that
inf [e(
||[(+t}]]
> E, where St = {kr E NN 1th $1.
LA
min min max max T=y,N max Mage o² jE[n]k[[m
t= X logn +
Possi
where j. is a permutation that sorts max Te-ts); i.e,
max(hsya To I ..... S max maxflix f/irs.n Tayn-+s
for all j E [n]. The quantities d' and are universal constants. The sequences x and th are defined in Protocol 8.
E.3
Proof sketch of Theorem 19
Let us provide a proof sketch that will give intuition behind the theorem. The full proof starts in Section E.4.
Proof Sketch.
Part 1: Construct function and stochastic gradient
The first part of the proof is standard (Carmon al., 2020; Arjevani al., 2022; Tyurin and Richtárik, 2023; Huang et al., 2022; Lu and De Sa, 2021), and we delegate it to Section E.4. For any algorithm, we construct oracles and "worst-case" function such that
inf kE
inf kES.,iE(m]
[prog(x:) < T)
(29)
where prog(x) == max(i 2 0 x; + 0} (=o and T R. LA/e. This inequality says that while all points in Protocol 8 have the last coordinate equals 0 by the time f, an algorithm can not find an e e-stationary point.
Since we assume that A E Arr is zero-respecting, the only way to discover the next non-zero coordinate through stochastic gradients. They are constructed in the following way (Arjevani et al., 2022):
[f = v,f(x) (1+16= prog(z))
-)) 5 p (
Vx E RRT
and { ~ Bernoull(p)) for all E [n], where z 8/02. We denote [m]; as the 5th index of vector E RT. The stochastic gradient equals to the exact gradient except for the last non-zero coordinate: zeros out with the high probability 1-p.
Part 2: The Level Game
In essence, the protocol is equivalent to the following collaborative game. Each worker i starts with level f, = 0. The goal is to reach level T with least one worker as fast as possible. There are two ways how worker can increase its level: i) worker flips one coin per time from & ~ (p))) takes h; seconds to flip one coin, and if the worker is lucky, i.e., < = 1, then moves to the next level & = f; + 1; ii) worker i can share its level with another worker j, and it takes Tę seconds (we are allowed to run this operation again even if the previous is not finished). Both options can be exccuted in parallel. What is the minimum possible time to reach the game's ' goal?
26

---

Since all workers have the levels equal to 0 at the beginning. they should flip coins in parallel and wait for the moment when at least one worker moves level 1. We define 17, as the number of flips in worker i to get 1. Clearly, nf Geometric(p) are i.i.d. geometric random variables with the probability p. With any strategy, it necessary to wait least
v} = min (hmm + + iE(n)
seconds to reach level in worker because once worker flips E = 1, will take at least T-++j seconds to share level 1 to worker j due to the triangle inequality Ti-+j S Ti-sk + Tk-+ for all j, E [n], and we should minimize h,n + Ti-jj over all workers. We now use mathematical induction prove that is necessary to wait at least
min {ut - + h + T(-j) EE(m]
seconds to reach level T, where we define yf := 0 for E [n]] and {nz } are i.idd random variables from Geometric(p). The base case is proven above. Assume that it is true for ,,..., T 1, then worker i requires at least v!" v.-1 han? seconds to flip coin that moves to level T, it takes least Ti-t seconds share the level T, it is necessary wait least min - han Ti-s) seconds in worker to get level T. Ultimately, the minimum possible time to reach the game's goal is
= min y jEin]
From the previous result, we can conclude that if 1 then
inf kES..E(m)
||/[(>>))|* >
(30)
for any algorithm A E Az-
Part 3: The high probability bound of y
Let us fix any determenistic value E IR and take
1
t
2 y
(31)
Using (30), we have
E
inf
||/
E
inf
|
8J
P P >
1) > >P P3 > 8) 2E.
Thus, it is sufficient to find any y E IR such that
IP (y"
(32)
2
The sequence y" is a well-define time series. In Lemma we show that (32) holds with
{ m max(Taaa Nog. o²
LA
5= θ
min min max
logn +
jE(m) kE[m)
Tj is permutation that sorts max ( (4s Tt Te-ssh i.e,
max ma ( T=p1 S max (h Tay. -
for all j [n). We substitute this to (31) and get the result of theorem.
27

---

E.4 Full proof of Theorem 19
This section considers the standard "worst case" function that helps to provide lower bounds in the nonconvex world. Let us define
prog(x) max 0 0}
(Io 1).
For any T N, Carmon al. (2020); Arjevani et (2022) define
Fr(o) - (1))((11)
((-=,-1)0(-1) ((x:1))(x;),,,
(33)
2
where
0,
x S 1/2,
and x(x) = ve vel== e dt.
(xx
exp (1- (2x-
x 2 1/2,
12--112
We will only rely on the following facts.
Lemma (Carmon et al. (2020); Arjevani et al. (2022)). The function FT satisfies:
1. Fr(() zer Fr(x) I AT, where A
12.
2. The function Fr is smoohh,, where 1
152.
3. For all a E R², [[V/T())] Yoo: where Yoo 23.
4. For all E RT, prog (x)) S prog (z) + 1.
5. For all x E R if prog(2) T, then [|VF[ >
Theorem 19. Consider Protocol 8. We take any h; 2 O and Tizj 2 0 for all i,j E [m] such that
Ti S Ti-kk + Tk-t for all i, k,k, E [n]. We fix L, a. > 0 that satisfy the inequality Ans there exists a function f. which satisfy Assumptions 1, 2 and f(0) fo < A, and a stochastic gradient mapping f((:)),, which satisfy Assumption 3, such that
è Lİ. For any algorithm
inf ke
> E, where S. = [/e E No 1thh st}.
LA
2
c= logn
min min max maxt Tasi -is hagel jE(n) KE(m)
where n. permutation that sorts max Ti-zg b ie.,
max(ha Tas S ... S max ( -
for all E [n]. The quantities d' and are universal constants. The sequences a and th are defined in Protocol 8.
Proof.
Part 1: The Worst Case Function
This part of the proof mirrors the proofs from Carmon et al. (2020); Arjevani et al. (2022); Tyurin and Richtárik (2023); Huang al. (2022); Lu and De Sa (2021). We provide it for completeness. The goal of this part to construct a hard instance.
We fix À > 0, T E and take the function f(x) = LA? Fr (+) in Section E.4. Note that the function f is L-smooth:
where the function Fr is defined
[V](x) - f((r)
LA
T
F
VFT
(4) LA
=
-1I vll
Vz, E Idd
where 1 -mmoothness of Fr (Lemmaa 1). Let us take
Ah
LA
28

---

then
LA² (Fr (0)
inf Fr(x)) LA A.. "ER"
f(0)
inf f())= ZERT
11
We showed that the function f satisfy Assumptions 2 and f(0) - f S..
For each worker i we take an oracle Oz, from (27) with the mapping 9 such that
[V == vxf(x) I+ (++1 1j > prog(z)) { (1-1) Vx E R²"
and D. = Bernouili(p)) for all é E [n], where E (0, 1]. We denote [x], as the jth index of a vector a E R², This stochastic gradient is unbiased and vavaraacce-buuuded. We have
V.)(2) (1 (1+ 1 prog(z)]
E - 1)) V.f(s)
p
for all i E [T], and
(6-1))
E - max
V v E
JE[T]
because the difference is non-zero only in one coordinate. Thus
[V(())]
(1 p)
12
V FT (*) 1 (1 (1-1)
E |V [()))
P
Pi
2 Teo p)
S 0²
P/p
where we use Lemma 1 and take
1,2 2
100
p min
1
0212
Let us take
22e1
A =
L
to ensure that
1,22² l7
FT (2) 28 Vrr (z) 2
[V)(')
for all x E RRT, From Lemma
we know that if prog(x) < T, then V FT)()) > 1. Thus, we get
[+) > 2e1 [prog(>) < T
(34)
Therefore,
AL 2El, A
T
(35)
and
{ (20%0 02
min
.13
(36)
The inequality (34) implies
inf ke
[((x))) > 25
inf kes.)e(m)
1 [prog(a)) < <T],
(37)
where ] === are sequences from Protocol 8. Part Reduction to Lower Bound Time Series
We now focus on (27). In (27), when the oracle in worker i calculates new stochastic gradient, it
29

---

samples a random variable & ~ D. This is equivalent to the procedure if we had T infinite sequences of if..d Bernuulii random variables
2111
(prog(#2) = 0)
2.1
2.2
(prog(s>) 1)
15i 1...
,
T.
(prog(sx)) = T 1)
for all E [n] and the oracle would look at the progress of 8æ and take the next non-taken Bernoulli random variable in the sequence that corresponds to that progress. For instance, prog(sx) j for the first time in worker i, then the oracle will apply e/ in (27). The next time when it gets prog(s2) j will apply e/2 and One by one, we get ii.d Bernoulli random variables. Let us define
t inf E EN =1]
for all E [n]] and & E [T]. This is the first Bernoulli random variable from the sequence 5 ck.2 that equals 1. The random variables [n²²] are i.idd geometrically distributed random variables with the probability p.
The next steps mirror Proof Sketch from Theorem 19. The oracles constructed in such a way that takes h; seconds to caleulate stochastic gradient, and least T-++j seconds to send vector from one worker to another. Using the same reasoning as in the Level Game in Proof Sketch of Theorem 19, the first time moment when worker j can get vector with the first non-zero coordinate greater or equal
v = min (hen + + (E(m)
because, at the beginning, each worker calculates stochastic gradients with prog(s,,) 0 and should wait at least h.z seconds to get stochastic gradient with the progress equals 1. Then, can share this vector with any other worker j. but it takes at least Ta-z seconds.
As in Proof Sketch of Theorem 19, we can use mathematical induction to prove that it is necessary to wait at least
V
(v7-1 + hamg T=-n)) (E(m)
min
seconds to get a point such that prog(s=) T. The base case for yf has been proven. Worker i requires at least y + han? seconds wait for the moment when the corresponding oracle will return a stochastic gradient with progress T because y TT is the first time possible time to get a vector with progress - by the induction, and it will take least additional h,ng seconds to calculate ni" vectors with prog(s2) = in (27). Also, takes at least Tı-j seconds to share vector, so is necessary to wait at least min4e(n] Ty + han + { seconds worker get the first vector with progress T.
In the end, the fastest possible time to get vector with progress T is at least
y" min y
jE(n]
Part 3: Reduction to the concentration of yz
The last statement means that prog(=+) T for all i E [ni] and k such that /x S 114"" Therefore, obtain
inf kES
||/
2c
(38)
for
1 t < "
where
AL 2el AU
AL
CT
30

---

and n/! ~ Geometric(p) with
2e
min fsr - -
1
p min
where er 3648 and Cp 1058 are universal constants. Let us fix any determenistic value ÿ E R and take
1 t = 2
(39)
Using (38), we have
inf ieEn ||
2
inf
v" [({\a\||
PQ'> > Φ) 25.
Se
Thus, it sufficient to find any ÿ IR such that
P P(y" 2
(40)
In the following lemma we use the notation of this theorem. We prove Section E.5.
Lemma 2. With
1
LA
D = cx log
min min max (T5,a-- MT J JE(m) ke(a)
(41)
am
we have P (y" S 9) S 2. where Ty is permutation that sorts max 12s, Tinssh iee.
max max(hag.r T+ S ... S max ( Tain
for all E [n]]. The quantity is universal constant.
Using Lemma 2, we can conclude that (40) holds and
E
inf
||
>
for
LA
0²
1 2
min min max max jE(n) kE(n)
log n 1 E
E.5 Proof of Lemma
Lemma 2, With
1 LA
σ² max Tri jj hn &
9 = c
min min max JE(m) kE(n)
(41)
log + 1 s
we have (DT S 50) S 2 where ny is permutation that sorts max (hi, Ti Ti-asl ie,
T= I m mmxx Tay.n
for all j e [n)). The quantity e is a universal constant.
Proof. Using the Chernoff method for any 0, we get
P (yy² < = P (-sy² 2 sst = P c -ay-
2 e stt
S e [e-os"
ッ )
exp
min jE(n]
maxexp (-sy²²) jE
31

---

We have a maximum operation that complicates the analysis. In response to this problem, we use well-known trick that bounds a maximum by a sum.
P P S t) S a
E exxp (-sy])] ne max E [exp (-sy²)
(42)
je(m]
We refer to (Van Handel, [Part II] for the explanation why it can be (almost) tight. This is the main reason why we get an extra log factor in (41). Let us consider the last exponent separately and use the same trick again:
E exp (-sh²)] = E exp
-8 min {ur -- + thot + T(-13) iE(n)
E
max
(-s {2, k-1 + hanh + romss))
Next, we get
E exp (-sy
}]
E (exp (-8 {u, hank + r(-)))]
Σ E e (bonttttt) E [exp (-sy 1)]
In the last equality we use the independence. max E exp (-sy," ,y(""))
We now bound E [exp (-syh-1) by
and get
E eepp (-sy)))
S i=1
E
l (hort (
E lexp (-syt
Σ
f (Min + (e))
max E [exp KE(n)
Let us fix any 8y >> 0 for all j E [m]] and take = ma 8y. Then
E exp sy }
n
E *s sllhrt
max E (exp (-sy(-1) "]] (E(m)
(43)
Let us fix Ey > 0 and consider
n
a = Σ E e (
(44)
Then, we can use the following inequalities:
E (hant +T--;) [hmn + T S [g] + s (1- [han + T S E11]]
aj
E
I Iham + To-t [وا - (1 - 1 1hith + Tros S {(11)
i=1
n
354y + (1 - e s5d Σ
E [1 Ihanh k + T S [tl]
= ne
n
< ne
354 +
I [hank + Te-e3 S Gll
P (hin) Ti-sj S (,)
< ne
354 +
P (ham < <tz) I [ stz).
32

---

Since of ~ Geometric(p). we get
p1
P Phas (t) = 1 (1
sp
hi
Then
i Ti- S St:].
0 S ne 9,6y +
hi
i=1
For all E [n]. we take any permutation Tj.- that sorts max (hi, Ti ; i.e.
max,, TT,, S max Tri, -5)
We have
Oj S ne 85ts +
Σ
tg
[T S [4/]
(45)
Recall that & > 0 is a parameter. In the following technical lemma, we choose Ł and show that the second term in (45) is "small." We prove it in Section E.6.
Lemma 3. For any n 2 1, h4 2 O 2 for all i.j E [m], and E (0, 1], we have
[ S [5]
for all j E [n], where
E = min max
max FOax(TTx,) Txy K
(46)
8 ke(m)
and nj. a permutation that sorts max To i.e.
max T I max (h Tasn
for all j E [n]]
Using Lemma 3 and (45), get
aj S ne
854 +
8
for j [n)). Let us take
log 8n
8j
(47)
1j
get
0j S
5
-1
8
8
for all j E [n). Using (44) and (43), we obtain
E Tepp (-sy²) se-
max E (exp (-sy, 1))
(48)
for all j E [n]. We can conclude that
max
E (exp (-sy $ S
max E. [exp sy}} s - iE[n]
where use the same reasoning in the recursion and vg = 0 for all j E [n]. We substitute the inequality (42):
PP (v* S t) S =t- = st-nn
33

---

It is sufficient to take l = T and any
1 s 1 T log n log 2
min min max 8log 8n ie(n) ke[n]
{ max ( Mos,e
Σ
k
-1
log + log 1 2 (
to get
P Pv² St - 2'
where we use the definitions ma 8, (46) and (47). Recall the choice of and p in (35) and (36): T= cr AL and = min { cp 2 1} for some universal constants Cr and cp- Since
we have the condition e < é' LA for some universal constant d' in the conditions Theorem 19, we can conclude that we can take
LA
o² { max (Txx(T=Aa-)- M E
min min max aEjn] kEjn)
Σ
logn n
+ E
h
where is a universal constant.
E.6 Proof of Lemma
Lemma 3. For any 2 1, h4 2 0 2 ffr all i,j E [m], and E (0, 1]. we have
[T [z] -
1=1
for all j [n), where
Ł, := min max
Tx h
P
(46)
8 kE(n)
and nj. a permutation that sorts max T i.e.
max(h Ta S ... S max Tasn
for all j E [n].
Let us define ke E [n] as the largest index that minimizes (46).
(Part 1): bound ł, by max(Tnga 1i- hey 11 Let us consider the case
n. We have two options:
Let (Txx(TT -ss Myy.er
Ex Reyaa
then
h1+1
max max(Tag.* + h 1
p hay
(49)
since max max(Trg, (Tn hr,,) are sorted. Then, we get
p Hoss
max max maxtTry.e - Ao a
(49) max Tay 11 h S max
Try + A
34

---

The first inequality follows from the fact that h- is the largest minimizer.
2.
Let max max(TR + m }
El=
k''
then it is not possible that because it would yield the inequality
Rey,
max (7 M
EE
+1
Σ
Σ
max Ta T +2 h Bagar+s
Σ
P
bags
The last inequality contradicts the fact that k is the largest minimizer. Thus, if k and max(TTrau- -ts, MTg.e.
E
p Bugg
-1
then
i < max max +i 1
Σ
max (T -tj 4.
Pe
In total, we have
< max m (T +5i M
if k* n. Using this inequality, get
S
1
TTg. S Styl
(50)
hmgg
i=1
for any k.,
(Part 2)
We have three options:
If
Σ hay.a
max (Tr, -gs , }, then, using (50) and
|x| S for all
2 0, we get
Eg lizy.
[Try [44 Sp b
P
1
1
p
8
1
p
hTy
8
i=1
If
E hey,
p_)
< max((T
+ n } and 6. 1, then
[T S [tg]
[T +1 [t]] =0
haya
h
because
k'
E, = 8 max max ma N }
p
max (Tr h N < maxf TTy - 1 My }.
heg
8
Ehin bay, ) < max Mnax(TTy,N +s, M } and h² > 1, then I max Tx, Ma
3. If
and
f
1 [Taya -5 S [tt]] =0
h
for all S k* such that max(Tr (ayx + hTy.) max( uo -tj: 1 }. If this equality holds for all
i < 1e," then
E
[T. S St, = 0.
h
35

---

Otherwise, there exists < k- such that max T Aay.et < max xx5 -.j A Amgar and
1
Ij Aogii
1 TTy
- [g]
1 T S [t/]
MTg..
It is not possible that (as.e borg.ed
Σ
because would yield the inequality
hegge
fj 8
max TT -j. M May,x
max (ooat Mngier
8
max
max T Mayce
P Misgis
that contradicts the fact that Łj is the minimum (see (46)). Thus, have
E S max
Pogel Σ
P
p
8
hTyy
and
ij
i
[4/] =
1 Imp.a+s
[//]
S
hagge
i=1
1
p
In total, we have
[Tp
5ty s
for ł from (46).
F Lower Bound in the Heterogeneous Setup
In this case, we consider the following oracle mappings. For all i E [n], we define
O
R2o Rd time
(Rzo R (0.1))
RRoo Rd (0, xB"
point
inpur state
ouipul state
(1,,2, 1);
8q
such that
Oc(t, (st,
Sz. 84)) = ((se, Sz, 1), 0,0,0,0),
0), 1, f < + his
(51)
V Vi E)),
8q 1, 1 > 8t hi,
where & D. Unlike (27), the mapping (51) returns V fi(iiE)..
Theorem 20. Consider Protocol with the mappings (51). We take any h; 2 0 and Ti-zj 2 for all i,j E [n]] such that Ti-ij S Ti-sk + Tk-ii for all i, k,j E [n]. We fix L, E, the inequality < eı LA. For any algorithm A E An, there exists a function f 7 which and f(0) f < A, and stochastic gradient mappings
that satisfy
-i Sú. which
satisfy Assumptions
satisfy Assumption 3 (Eg (x) = V(((x) and Bell Ve(()))((;;))) - { < o such that
inf 3eS
> E, where S = [kr E Nolth St}.
LA max
max Te-si max h4s +² (JE[M)
1= 02
h4
(E(n)
ME
The quantities e₁ and 02 are universal constants. The sequences x and th defined in Protocol 8.
36

---

Proof. The last two terms in the max follow from Theorem A.2 by Tyurin and Richtárik (2023), who considered the same setup but with Ti-aj 0 for all i,j E [n]] is left prove the first term. Let us fix À > O. Let take any pair (i,5) of workers such that m, Ti=+j = Ti-j-- Next, we split the blocks of the function (r) from (33) and define two new functions:
FT,1(x) == -1()
Σ
((-I=-1))(--)) V (2)-1))((i)), (52)
ie (2....... T)a121
and
Fra(2):=
Σ ((-2)11)((-0)) ((I=-1)(<zi)]-
iE((....TT) 12-0
We consider the following functions f;:
nLX² F4,1 (5) i=ī,
f((x) =
nld? F (+)
i= j,
0,
i i and i }.
Then, we get
8 1
( /nL>²
nLA
(m)
LX²
f(x) f((2)
n
n
4
Fr,1
41
Fr,2
A
1
Fi
Let us show that the function is L-smooth:
[VV - = LA
FT
Fr
s L.
||
yl1
1
Let us take
A
T=
LA
then
inf f(z) = (Fr (0) inf Fr(x)) S LAT xER
LX²
f(0)
SA.
11 We showed that the function f satisfy Assumptions 1, and f(0) ff" SA.
ZERT
4
In the oracles O. we simply take the non-stochastic mappings (z: = ff((z) that are unbiased and O-variance-bounded.
We take
LIVE A =
L
to ensure that
[V](()] = L2
L2X²
VFr
for all x E IR such that prog(r) < T. In the last inequality, we use Lemma 1. Thus
AL
T
heAD
Only workers and j contain the information about the function f. The function f is a zero-chain function, and we split between workers and j. Due to this splitting, workers i and j have to communicate to find the next non-zero coordinate. Only worker can get a non-zero value in the first coordinate through the gradient of Fr,1- Next, this worker can not get a non-zero value in the second coordinate due to the construction of (52). Thus, it has to pass vector with a non-zero value the first coordinate to worker j because only this worker can get a non-zero value the second coordinate. This communication takes at least тー- seconds. Using the same reasoning, worker has to send a vector to worker i once worker has discovered non-zero value in the second coordinate.
37

---

An algorithm has to repeat such communications at least T-1 times to find vector r E R² such that prog(z) T.
Thus, we get
inf ke
for
max Ti-+J
AL 1431
-1)
t = 7-3
2
2
G Proof of the Time Complexity for Homogeneous Case
Theorem 4. Let Assumptions 2, and 3 hold. We take n = 1/2L, batch size S max{[=2/=]] 1}, any pivol worker jr E {[n,, and any spanning trees sl and sine in Algorithm For all K 2 16LA/e, we get 1 K Ek=
E
vf(=>) E.
Proof. Algorithm produces the sequence xe such as gk+1 = x -0000 = x 7g. where
gh = g =
By the design of the algorithm,
fa*
where the & are independent random samples and s 2 S. We do not dismiss the possibility that the computation and communication times are random, so s can random. Assume Ví. is r-algebra generated by all computation and communication times and go ......."* Using the independence and Assumption 3, we have
g then s is V4 Ve-measurable.
E g
Gk
E
E
Gk
=
E
E
:5)) M&]
Gh Vs(x*t
sh
and
E 11
9k
E
E
1
ff
-
Vi
G#
E
E
|| -
V/
(sk)
1=1
o² S
E
G
where GR is a allggebaa generated by z0 ..... k-1 We use well-known SGD result (Ghadimi and Lan, 2013; Khaled and Richtárik, 2022). Using Theorem 21, for the stepsize
8S 02
7 21
min
we have
K
Σ
E
||>>)>>
|
Se,
K
R=0
38

---

if
K SAL
S
+
E28
Using the choice of S, we get that Algorithm 2 converges after
16AL K Z
8
steps with
ES min
1
2L
0²
2L
Theorem S. Consider the assumptions and the parameters from Theorem 4. For any pivot worker j' [n]] and spanning trees and slie, Algorithm converges after at most
θ LA 1s (o²) /c, [bu]i= [Pi-3j" + -)---()
(10)
seconds, where Pi-rj" (e) .) is an upper bound on the times required to send vector from worker i to worker jr (from worker j to worker i) along the spanning tree st (spanning tree stoe).
Proof. Due to Theorem we know that Algorithm finds an s-stationary point after most K θ (LA) iterations. It is left to bound the time of one iteration to prove the theorem.
For all j E [n], we define Tj. as permutation that sorts {max {pi-o + pj-ri; h:: 1 as max (MT5,1 +j M5a ( S ... S mmxx -j + pj A
Let us define the index
k- arg min max RE(n]
max(Ury + jijt May S
and the set
=² E [n] k}}
that represents a set of the "fastest" workers that can potentially contribute to an optimization process.
We take
2 max
max -2j" + - and , S.
longe
(53)
= 2 min max max + pjr-xyy h S
kEin]
Mayai
In the following steps of the proof we show that every iteration takes at most
3
(Step Ur: Calculate enough stochastic gradients (Step 2): Send stochnstic gradients to Process j* (Step 3): Brondcast new point
seconds.
(Step 1): Since it takes at most h; seconds to calculate a stochastic gradient in worker i, all workers from the set A will calculate at least
k²
Σ S
(54)
h4
stochastic gradients after i seconds the point A We have
f 2 2 max((ua, -- --* + 143 -ts ua: 1 May } Z 2 maxxfuy -43" + - knye.t (55)
39

---

S. for all i S k* by the definition of the permutations ..... Therefore,
2 2h
for all S kt, Thus, using (54) and
[x]
$ for all 2 1, we get
f (53)
Σ
2h 2
EEA
Therefore, after i seconds the algorithm will calculate at least S stochastic gradients at the point x using the workers A".
(Step 2): By the design of Algorithm 4, once stochastic gradient ff(==; {) is calculated, it is added to p. Then, Dimen is assigned to 9 gi which is sent to Process nex (t). Finally, Process 5 (i) receives Fi,send and adds it to g Knext., (e)) Thus, the stochastic gradient Vf {) is presented in the sum of Inext, 5- (n)). of Process nexty7,; (1). At some point, Process 0 in worker j' will receive vector g.,sond where the stochastic gradient fa="; {) is presented.
Let us bound the time required to transmit a stochastic gradient to Process 0 of worker j". Once stochastic gradient { calculated in Process from A", it added a vector gi in Process i. It will take at most 2ni- seconds to transmit Process next 5 (i) because it takes at most Pi-mnext,i. seconds to wait for the transmission of a message Di where the stochastic gradient Vf(="; is not presented, and an additional (i--onxs,..,..0 seconds to send the next s/isend where it will present. After that, Process next,t,j" (i) will receive yf.snnd where the stochastic gradient (=(==; presents, and add the vector g. Inextzz, (i)) Then, will take at most 2 (f) mex((eex (1) seconds to send a vector, where the stochastic gradient fa(a" {) presents, to Process next (nex (i)) and so forth. In total, after finite number of such steps stochastic gradient calculated in Process i will be transmitted to Process 0 of worker j" From Definition 3 of next,,,", we can conclude that the vector (a {) will be transmitted through the path between workers i and j in the spanning tree st. Thus, it will take at most 2/1z-as' seconds by the definition of p4-j""
Using (55) and the definition of A", we have 82 2 (a,x
+ My - - 2 2 max + My*-+ -2, -a, 2 2pr-35" (56)
for all i E A Therefore, it will take at most seconds to calculate at least S stochastic gradients, and at most seconds to send all these stochastic gradients to Process
(Step 3): It is left to estimate the time of the broadcast steps (Lines 7-9 in Algorithm 4) through the spanning tree sthe By the definition of pl-- the time required to broadcast x² to Process i through the spanning tree sthe is less equal 2445- - since, in all edges from jL to i, workers wait most p. seconds while edges are blocked by previous communications, and additional p. seconds to send zf to next workers. Using (55) and the definition of A', we have
E ス 2 max( +ン + - ,. h 2 max(f4-5 + 4s h4 2 2
Thus, every worker from A will get æ after i seconds. By combining all times, we can conclude that every iteration in Algorithm 3 will take most f + E E t 3 seconds.
left to show that
1= max max ( M -5 + P3* - -my-
N ,
(57)
If S > 1, then S =
[ < 20 /c, so is true. Otherwise, if S < 1, then
7 < max
max (iax((UTyr.a) + 113- +x, x May J.
< 2 max Imax(Ma, +-* + pJj + w- May eo to Aang, w pV- - h 2
2 max( Ma- +
40

---

and (57) holds. Notice that the r.h.s. of (57) equals to O (t"(o"/e, (hil/, Ipc-s- + Mj -j--)((=)) where t" the equilibrium time defined in Definition 2.
Theorem 6. Consider the assumptions and the parameters from Theorem 4. In each iteration of Algorithm 3, the computation times of worker are bounded by l.. Let us fix any pivol worker j E [n] and any spanning trees st and stre. Then Algorithu 2 converges after at most
+ E
KO
T16LA/E] 1700%,,,1/1, IuL-s- + + (11--11-1))
(13)
seconds, where -3 (+)) an upper bound on times required to send vector from worker to worker j" (from worker j to worker i) along the spanning tree st. (spanning tree slic) in iteration of Algorithm 3.
Proof. The proof is almost the same in Theorem 5. If we fix pivot worker j", then the hth iteration will finish after at most
cx e' (e, 16 [ui-ag- + -
seconds, where is a universal constant, According to Theorem 4, the number of iterations is at most 16LA Therefore, the total required time is at most
LALA
(ri + (
C X
k=0
H Proof of the Time Complexity for Heterogeneous Case
Theorem Let Assumptions and 2 hold for the function and Assumption 3 holds for the functions
for all i E [n]] We take yy = 1/2L, the parameter S = max{ /=| .n), any pivot worker j E [n], and any spanning trees st. and slae; in Algorithm 5. For all iterations number K 2 16T. we get K >EE
[ S.
Proof. Algorithm 5 produces the sequence x² such that
z k+l x² -99² 2² -
th
Vi( (6)
9i
where the Eiy are independent random samples. Using the independence and Assumption 3, we have [ 9x] = ( and
E
||0h
vf(x>)]
g
E
E6) Σ ((*)
Gk
(58)
m
where GR o-algebra generated by g ........'"
9 6-1 We do not dismiss the possibility that the computation and communication times are random, of can be random. Assume V4. is oralgebra generated by all computation and communication times and "......*-. then se is meamauuuable for all E (r). Using the independence of stochastic gradients and the times and the tower property, we get
41

---

1 *
vf(l"))]
9k
Eiy) - n
E
E
Σ
((((t)))
V/
9k
(59)
T1
Vficoty) |2]
E
E
fi(x
V/2
n
E
E
( - vf((=*))] |1
9k
E
g
(60)
Algorithm waits for the moment when s _
n which is equivalent to
n by 5
(61)
The value by- is calculated in Line 20 of Algorithm 7. Due to the asynchronous nature of the algorithm, only conclude that
by-
Σ
b
1
(62)
Pc [m] Inexta,. (p)=
because sy. can be increased by the time when Process O will receive by. Using Line 15 from Algorithm unroll the recursion in (62) and get
by:
(63)
Let us substitute this inequality to (61) and (60) and get
o² s
E
f(x
9K
s
As in Theorem 4, we can use the classical SGD result. Using Theorem 21, for the stepsize
1, ES 0
min
2L
we have
K-1
Σ
[
se,
K
SAL
8ALo2
K>
E2S
Using the choice of S, we get that Algorithm 5 converges after
K> 16AL
E
steps with
5 1,
2T. min
2T.
42

---

Theorem 9. Consider the assumptions and the parameters from Theorem 8. For any pivor worker j [n]] and any spanning trees st and stee Algorithm 5 converges after at most
LA
o² ne
max
max 1.jE/m]
Pi-ojo max his sE[n]
n1
seconds, where -3- (uz=-p)) ) is an upper bound on times required to send vector from worker to worker j" (from worker jr to worker i) along the spanning tree st (spanning tree sinc) for all E [n].
Proof. Due Theorem 8, the algorithm converges after K O (LA/s) iterations. Thus, it left to bound the time of one iteration. At the beginning of every iteration Process 0 broadcasts 2., which takes at most jj Ma-+j seconds. Then, Algorithm waits for the moment when s 2 g
which is equivalent n² 2 by.. Thus, Algorithm waits for the moment when n² 2 by. We will
return to this fact later.
Let us consider the term
S
1
n
where of is the number of stochastic gradients calculated in worker i. Let us fix any time 7> 0. Then, stochastic gradients by the time é. Using this, get
worker i will calculate least
h;
S
1
n
hi
Let us take
S
=
max h4
h4
iE(n]
n
n
Then, since
| 2 z for all
1, we get
i
>
and
h.
2h
S
12
1
2s
Σ
hos
nt
Using
25 (2 En 11), we get
S
11
2
and
5 n²
(64)
S
1=1
after at most ? seconds.
Recall that Algorithm 6 waits for the moment when n² S 2 by- Note that by the time when Process 0 re- ceives by-, the counter sf can be the same or increased; thus, by- captures potentially outdated informa- tion about s We know that (64) holds after at most seconds. In Line 20 of Algorithm 7, Processes re- cursively collect 1 to by-. Such procedure will take most 2 max Mi+55 < 2 max;,je(w) Pi+j
seconds. Thus, the value 6,- will be less equal
a² i after at most + maxi,je(m) Pi-z seconds.
43

---

The all reduce operation in (8) will take at most [m Hi-+j seconds. Thus, the total time of one iteration can be bounded by
max f
Mi-tj +(E+ 2 max (i-+)) +
max Mi-tj i.jemm
broadcast
all reduce
S
1
0
max Pi-j + max h iE[n]
+
h4
1.jE/m]
1=1
o²
0 max Pi-j
max h4
+
hi
1.j[[n]
1c(m]
ne
im1
seconds.
I Classical SGD Theory
We reprove the classical SGD result (Ghadimi and Lan, 2013; Khaled and Richtárik, 2022), for completeness.
Theorem 21. Let Assumptions I and 2 hold. We consider the SGD method:
k+L = x >9(***,
where
2L min {
7
For all k 2 0, the vector g(x) is a random vector such that E [(( v.((**),
E
-
vf(=*)]l Ge < s²²
(65)
where G% a o-algebra generated by g(x²) ((x")).....) g(x -(xx-1))) Then
K 1
E
[+ se
K
k=
for
SAL
SALo2
K
+
8
g²
Proof. From Assumption we have
f(x s f(**) + (z ) k++
2²)) +
L
|| 2012
2
= 7 x(xx))) +
|1g(0))
We denote g as a sigma-algebra generated by g(x)). obtain
Using unbiasedness and (65),
[(( g* S s(x*) - (1- In
||
122
(ol(l(aa)) V/(a>)
+ 2
2
$ {((
1 2
In
||>
L720²
2
Since 7 S 1/r, we get
LY20²
E [f(x
ffaat) - ?
2
2
44

---

We subtract f" and take the full expectation to obtain
InPo²
E B|s f - 1 - 2
E
[|]
+
2
Next, we sum the inequality for & E (0....,, --1:: 1}:
K-1
KL7²0²
E [[((xk) [-] 5 ((x9) - 5
Σ
E
||]
2
K-1
Σ E ||V/((=))]* + KLyP0²
A
2
km
Finally, we rearrange the terms and use that E [f(=*)
- fr] N 0:
1 K-1
|12] - yk
2A
+ Lyo
The choice of and K ensures that
K
E
[|]
Se.
K
R=
Theorem 22. Let Assumptions 4 and 5 hold. We consider the SGD method:
x+1
x 79(a**)
where
M + 0²
For all k 2 0, the vector g(x) is a random vector such that E g(x |gg]] E @f((tt
E [[lo(a*)) - E (9(x*)) G.] 9h 0²
where GR is a o-algebra generated by g(x:'),..... ,(xt-11)1 Then
K
1 ) f(x²) S
E
(66)
K
k=0
for
K> (M2 + ) 1-- x01
Proof. We denote G as a sigma-algebra generated by g(xk-, Using the convexity, for all E Rdd we have
f(z) 2 f(**) + (E [9(2*)| 8d) x - x²) = f(x + E (0(x")) - - |
Note that
(9(x*), x z4a = (g(x=)), J k+I - xt) + (a(xx)) ) x t1
-
=- ||9(a*)) )1²
(ar xttl x k1
= -->1l0(a") 2
+
|1
8+1 ||2 +
1
- x1 11
||
x²
27
27
2
--2110(0>)1 1
1
| x
11
1
||0
b ||
2n
27
45

---

and
- E [119 | -I(10((=*)
-B( 9| 112 9t
[| 1|2 S 0² + M??
Therefore, we get
f(x²) s f(x) + [(((t)), xt - =2)1
= =(()) + 2 F [10((*) [|((a)111///)/ g*
+
1
||
x*
11²
1
R3
||a01~1000 - g*
27
27
f((x) + 2 (M² + + +
-
||
2²1
E
x
1| 1|² gt
27
27
By taking the full expectation and summing the last inequality for from 0 K
1, we obtain
E
K-
Σ
<K(() + Ky (M2 o²) +
1
20112
1
EE
110
x 11?
27
27
<f(()) + Ky (M² + 0²) +
1
x 2012
2n
Let divide the last inequality by K, take a = x², and use the convexity:
K-1 t ]
E
f(x)) 2 (M² + 02) + 24
1100 - =011
K
The choices of y and K ensure that (66) holds.
Experiments
We now consider Fragile SGD with Minibatch SGD on quadratic optimization tasks with stochastic gradients. The working enviromment was emulated in Python 3.8 with one Intel(R) (R) Gold 6248 CPU @ 2.50GHz. The homogeneous optimization problem (I) is constructed in the following way. We take
1 [x) -" Ar - bJx Vx E Rd
d = 1000,
-1
A 1
-1
E RRddd
and b b= 4
1 R
-1
Let us define [z], as the jth index a vector æ E Rd. All n workers calculate the stochastic gradients
prog(z)) ( (5-1) ()) Wo E Rd Vi E [n].
[f(x)()] = [V)()),, [1+1
where E ~ Bernouill((). p E (0, 1]. In our experiments, we take p= 0.001 and the starting point
x0 [V o...o.....0 T We emulate our setup by considering that the 7th worker requires h; = 1 second calculate stochastic gradient. And we assume that the workers have the structure of 2D) Mesh (see Figure 4a) and take Pi-ッj = P E {0.1, 100) seconds for all edges that connect workers in 2D-Mesh. We take n = 100. all methods we tune step sizes from the set {2 i E [-20, 20] In Fragile SGD, fine-tune the batch size S from the set (10, 20, 40, 80, 120).
The results are presented Figures 5, 6, and 7. The plots are fully consisted with Table One can see that when the communication is fast (Fig. 5), there is no big difference between the methods because both Fragile SGD and Minibatch SGD use workers in the optimization steps. However, when we start decreasing the communication speed, observe that Fragile SGD converges faster.
46

---

We looked deeper into the optimization processes of Fragile SGD in Figure 7 and observed that only 13 of 100 workers contribute the optimization process for the batch size S 120. Other workers are too far away from the pivot worker, and their contributions can only slow down optimization.
Size:
Fragile SGD: Batch Size: Step size: 2.0
Batch Size: 120
Minibatch SGD: Step size: 2.0
Minibatch
-
Minibateh SGD: Step size: 0.125
f(x*)
10-3
20000
40000
60000
80000
100000
times (seconds)
Figure 5: The communication time p 0.1 seconds (Fast communication)
Fragile SGD: Batch Size: Step size:
fragile SGD: Batch Size: Step
Fragile SGD: Batch Size: Step size:
Minibatch SGD: Step 2.0
Minibatch SGD: Step size: 1.0
10-2
Minibatch SCD:
f(x*)
20000
40000
60000
80000
100000
times (seconds)
Figure 6: The communication time seconds (Medium speed communication)
Fragile SGD: Batch Size: 120 Stop size: 2.0
Fragile Size: Step size: 2.0
FraglleiGDD: Batch Size: 200 Stop size: 2.0
Minibatch SCD: Step size: 2.0
Miribatch SGD: Step size: 1.0
1
Minibatch SGD: Step size:
f(x-) - f(x""
10
20000
40000
60000
80000
100000
times (seconds)
Figure 7: The communication time p 10 seconds (Slow communication)
47

---

J.1 Experiments with Logistic Regression: Fast vs Slow Communication
We now repeat the previous experiments but with logistic regression on MNIST dataset (LeCun et al., 2010) with 100 workers. We consider two regimes: fast and slow communication between workers. One can see that when the communication is fast, the gap between the methods small, which is expected and compliant with the theory. However, Fragile SGD is much faster and has better test accuracy when the communication is slow.
0.300
3x10
Pueir 129 Sinvate
0.345
28x10
ribuct 900 Mi viausa 9:0
$26x10-
0.933
224110
0.933
Riadhis Roaic 120
Papple Denn Sin
22x10
50000
100000 150000 200030 250003 300000 350000 400000
0.920
50000
200000
153000 200002 232000 300203 400000 (seconds)
Figure 8: The communication time p 0.1 seconds (Fast communication)
28x
un tno werln seuct une serih.
Accuracy (Test)
0.925
-
Hogis
22x
elsech 500 dee ate 20
03
(soconds)
31
1.0
0310
0.0
0.2
0.4
(seconds)
0.5
1.8
Figure The communication time p 10 seconds (Slow communication)
J.2 Experiments with ResNet-18
We test algorithms an image recognition task, CIFARIO (Krizhevsky et al., 2009), with the ResNer- 18 (He al., 2016) deep neural network (the number of parameters 10²). use the torus structure and 9 workers. We run all methods with the step sizes {0.025, 0.25, 2.5J. Our findings from low-scale experiments are also evident the large-scale experiments. Fragile SGD converges faster than Minibatch SGD in terms of function values. When compare accuracies the test split of MNIST, the superiority of Fragile SGD is even more transparent.
Tay's SAEC ENILSS
Us AUA
Accurary
100
0.75
Srevsee
Mrten 5o0 me 8.55
5000
10000
20003
25000
30000
0.70
10000
19363
20000
25300
30503
(seconds)
times
Figure 10: ResNet-18 CIFARIO dataset with workers and the structure with the communi-
cation time = seconds (Medium communication)
48

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Table 1, the main part of the paper, Section C
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Section 5.3
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
49

---

Justification:
Section 1. .1, and the appendix
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: Section
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
50

---

Answer: [Yes]
Justification:
The code in the supplementary materials.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.c cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
/nips. wwtppcccccccccccccccccccccccclct htaaa//ggiieeee/eeeuiiieeeee /Coo//eoomissssseeeee ceniiisssoooicyyyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification: Section
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: We provide the top 3 best plots for each algorithm reduce randomness factors in Section J.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
51

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Section
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the ines?
NeurIPS Code of Ethics https: https://ourrpp...cpppbbcc///e/e/
Answer: [Yes]
Justification:
We have read the code of ethics, and our paper does not violate it.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
We consider mathematical problem for machine learning.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
52

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We consider a mathematical problem for machine learning.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
53

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: The code and documentation in the supplementary materials.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
54


Reviews:
[{"review_id": "ST4Swn7VND", "reviewer": "Reviewer_1dR2", "summary": "This paper examines the time complexity lower bounds in decentralized stochastic asynchronous optimization. It introduces two methods, Fragile SGD and Amelie SGD, which achieve near-optimal and optimal convergence, respectively. The paper also provides convergence analysis for various settings.", "questions": "1. Could you provide empirical results for the proposed methods?\n\n2. Could you provide more discussion about the relationship between the pivot worker and the server?", "limitations": "Most limitations are listed in the weaknesses section.", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The topic of studying the exact communication costs is interesting since this should be a crucial problem in decentralized learning. This also brings us a new perspective on decentralized learning.", "weaknesses": "1. I believe it is crucial to  **provide empirical results** to demonstrate the effectiveness of the proposed method from two key aspects: the efficiency, which underscores the method’s effectiveness, and the final accuracy, which ensures overall performance guarantee. I would consider raising the score if solid empirical results were provided.\n\n2. I think the proposed methods heavily relies on the pivot worker, which represents a different concept of convergence dependency compared to the spectral gap. If I understand correctly, the framework benefits from a tree-like structure; however, this structure necessitates that the pivot worker possesses significantly greater computation and communication capabilities, almost functioning as a server. For instance, as mentioned in Line 141, “A pivot worker aggregates all stochastic gradients.” Therefore, I think the proposed method acts as a compromise between the centralized “server-client” framework and a decentralized one. Could you please discuss more on the relationship between the pivot worker and the server?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and review. In the following responses, we address the raised problems. **In particular, we prepared extra experiments to support our theoretical results, which the reviewer can find in the global rebuttal's PDF. We also have experiments in Section I of the paper.** Let us respond to the weaknesses and questions:\n\n> I believe it is crucial to provide empirical results to demonstrate the effectiveness of the proposed method from two key aspects:..\n\n> Could you provide empirical results for the proposed methods?\n\nIn Section I of our paper, we have already conducted experiments with quadratic optimization problems and showed that our theoretical results align with numerical computations. Nevertheless, we have run extra experiments to support our results in the submission. Please consider our results in the pdf we submitted in the global rebuttal. There, we consider experiments with logistic regression and a neural network and show that our new method has the best convergence rate and accuracy in different settings. We will add highlights of the experiments to the extra page of the camera-ready version of the paper.\n\nWe believe that we have addressed all concerns raised by the reviewer by conducting extra experiments, and hope that the reviewer will reconsider the score.\n\n> I think the proposed methods heavily relies on the pivot worker, which represents a different concept of convergence dependency compared to the spectral gap. ...\n\n> Could you provide more discussion about the relationship between the pivot worker and the server?\n\nWe agree that our Fragile SGD and Amelie SGD, in some sense, mimic a centralized algorithm. But note that the goal of the paper is to find fundamental time limits of the decentralized optimization in the homogeneous and heterogeneous setup. The standard way to accomplish this goal is to prove a lower bound (Theorem 7) and find a method that attains this lower bound (Fragile SGD, Corollary 1). We have the freedom to design an optimal method in any way as long as this method satisfies the setup's constraints. We designed Fragile SGD and Amelies SGD, valid methods in the decentralized setup. One can design a method without pivot workers and spanning trees, but any other method will never get a time complexity better than our new methods due to the lower bounds.\n\nLet us give a comment on the statement \"... the pivot worker possesses significantly greater computation and communication capabilities ...\" This is not always true. For instance, consider the example from Section 6. In this example, almost all workers have the same computation and communication capabilities, but we chose the middle worker due to its relative position to other workers. At the same time, all workers are equally loaded with communications and computations. They all calculate stochastic gradients, send and receive the same amount of vectors per second (except the the first and the last worker since they have only one edge). The pivot worker runs an extra process, Process 0, that only aggregates vectors in $g^k.$ However, the aggregation is a negligible operation compared to stochastic gradient computations.", "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": "", "extra_scores": {}}, {"review_id": "QufPfr8CQD", "reviewer": "Reviewer_VUTZ", "summary": "The paper addresses the decentralized stochastic asynchronous optimization setup. The authors establish new time complexity lower bounds for both homogeneous and heterogeneous setups, assuming bounded computation and communication speeds. They introduce two methods: Fragile SGD, a nearly optimal method, and Amelie SGD, an optimal method. Their methods leverage spanning trees to solve the problem. These methods achieve convergence under arbitrary heterogeneous computation and communication speeds and match the derived lower bounds, up to a logarithmic factor in the homogeneous setting.", "questions": "In practical applications, we often cannot choose which node serves as the central node and are instead constrained by existing conditions. In such scenarios, will the proposed algorithm still maintain its current advantages?", "limitations": "I believe the authors have discussed the limitations of their method.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "Originality: \nThe innovative use of spanning trees to address the decentralized stochastic asynchronous optimization problem represents a significant departure from existing algorithms, introducing new theoretical contributions. Furthermore, the proposed algorithm exhibits greater robustness compared to previous methods, meaning that the impact of the worst-performing nodes on the overall update speed is minimized or even eliminated.\nSignificance:\nThe contributions of this paper to the field are significant. It offers a novel approach(spanning tree) for analyzing computational time complexity, which could be beneficial for the time complexity analysis of other decentralized stochastic asynchronous optimization algorithms. Additionally, the proposed method may assist in practical applications by providing insights into the selection of central nodes.\nQuality:\nThe paper provides a detailed explanation of the prerequisite knowledge, a thorough proof process, and a comprehensive introduction to the algorithm's features. Additionally, it includes another algorithm and experimental results in the appendix, offering a well-rounded and complete presentation of the material.", "weaknesses": "Regarding the structure of the paper, I think there are several issues. First, one of the two algorithms mentioned in the abstract is relegated entirely to the appendix, which is inappropriate for the paper’s structure. Second, the experimental results are also exclusively placed in the appendix, which does not conform to standard layout. Finally, Section 6(Example: line or circle), which serves as the conclusion, fails to provide an effective summary of the entire paper and instead functions more as the concluding part of the theoretical analysis.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time! Let us address the weaknesses:\n\n>  First, one of the two algorithms mentioned in the abstract is relegated entirely to the appendix, which is inappropriate for the paper’s structure.\n\nWe agree. However, all algorithms, theorems, and discussions that are relegated to the appendix do not give, conceptually and significantly, new information and algorithmic insights. We tried to showcase the most important ideas in the main part. In the camera-ready version, having an extra page, we will provide more important details from the appendix.\n\n> Second, the experimental results are also exclusively placed in the appendix, which does not conform to standard layout. \n\nThe main goal of this paper is to provide fundamental and theoretical limits of the decentralized setup. We tried to focus on theoretical questions in the main part. For instance, we believe adding details about our lower bounds is more important than experiments. Having said that, we will add experiment highlights on the extra page. Moreover, we prepared extra experiments with logistic regression and a neural network that the reviewer can find in the global rebuttal response, which we will add to the camera-ready version.\n\n> Finally, Section 6(Example: line or circle), which serves as the conclusion, fails to provide an effective summary of the entire paper and instead functions more as the concluding part of the theoretical analysis.\n\nFollowing many previous conference papers published at NeurIPS, the role of the conclusion section plays the Contributions section (Section 3). This section gives a comprehensive overview of the paper. Section 6(Example: line or circle) is not a conclusion. It provides an example with clearer formulas and intuition. We can add a conclusion section instead of Section 6, but it will sacrifice an important example illustrating our new time complexities.\n\n> In practical applications, we often cannot choose which node serves as the central node and are instead constrained by existing conditions. In such scenarios, will the proposed algorithm still maintain its current advantages?\n\nWe answer this question in Section 5.3. Let us clarify it here. In general, one can choose any pivot worker and spanning trees, and the methods will converge (Theorem 5) with the time complexity (10) from the paper. \nBut to get the best possible convergence time, one should use the rule from Corollary 1. Then we can guarantee the time complexity (11) from the paper, which is optimal (up to log factor). Comparing (10) and (11), one can see the difference is only in $\\mu_{i \\to j}$ and $\\tau_{i \\to j},$ which have the relation $\\tau_{i \\to j} \\leq \\mu_{i \\to j}.$ The term $\\mu_{i \\to j}$ depends on how we choose a pivot worker and spanning trees in the algorithm. See also the discussion in Lines 181-183, 209-214.\n\nIn order to find optimal spanning trees and an optimal pivot worker using the rule from Corollary 1, one has to know $\\tau_{i \\to j}$ and $h_i.$ In practice, one can run a *load testing* program that estimates $\\tau_{i \\to j}$ and $h_i.$ Then, one can substitute these estimations to the formulas to find optimal spanning trees and an optimal pivot worker.\n\nWe believe that all the weaknesses pointed out by the reviewer can be addressed with an additional page in the camera-ready version of the paper. We hope that we have responded to all questions and weaknesses. If you have more questions, then please let us know.", "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": "", "extra_scores": {}}, {"review_id": "nLihRl3O9A", "reviewer": "Reviewer_YQkr", "summary": "This paper considers the decentralizd optimization problem, where clients have heterogeneous computation and communication times. The paper proved a lower bound on the optimal physical time complexity (wherein the physical computation and communication times are take into consideration). It proposed Fragile SGD, an asynchronous decentralized first order method that matches this lower bound up to a logarithmic factor. It further considers the data heterogenous setting and proposed Amelie SGD that matches the lower bound in such a setting.", "questions": "see weaknesses.", "limitations": "see weaknesses.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Unlike most other previous works, this paper takes into consideration the physical computation time and communication time of the clients in the decentralized network. The paper then proves a lower bound for decentralized optimization in terms of the physical time, and it proposed a nearly optimal algorithm Fragile SGD with matching physical running time. This is an interesting research setting, for which one could argue is more realistic, since whereas previous works on decentralized asynchrounous algorithms mostly considered the iteration complexity without worrying about the physical computation and communication time. In addition, unlike many other previous theoretical works on decentralized optimization where message passing is typically restricted to gossip type communications, this paper considers relayed communications where communication between any nodes on the graph are relayed on certain paths (in Fragile SGD, the paths are on certain spanning trees). These are all interesting additions to discussions around decentralized asynchronous algorithms.", "weaknesses": "1. This is also somewhat related to the strengths part. While the paper keeps referring to and comparing against some previous works (e.g. Even et al 2024), I do not think that there is a fair comparison to start with. Ultimately, the setting in which this paper is concerned is rather different from the previous works', where previous works typically only considers Gossip type communication and measures the convergence speed in terms of, number of iterations, communication rounds etc, but not the physical time of the whole process. Such a comparison is particular strange when the authors claimed that their method's convergence time does not depend on the spectral gap while previous works do -- this is obviously the case because previous works considers gossiping which is fundamentally constrained by the spectral gap while this paper allows any pair of clients to communicate via some paths on the graphs which is not directly constrained by the spectral gap (but can be otherwise more directly constrained by, say, the diameter of the graph).\n\n2. The second point is also somewhat related. I appreciate it that the authors takes computation and communication times into consideration. This might be somewhat a more realistic setting than what some previous works considers on the surface, but I'm still not very convinced that such a setting is actually closer to reality than the others. One could argue that the works in this paper is to some extend overfitting on certain metrics which are not necessarily a good measurement of the methods' performances in reality, just like the other (seemingly) simpler setting previous works consider. \n\n3. Fragile SGD requires a pivot worker which is, in some sense, at the center of the graph, to coordinate the updates. It also requires the knowledge of a spanning tree connecting the pivot worker to and from all other workers. Now suppose we take the pivot worker as the server, and set the communication time of all other workers as the distance from the worker to the pivot on the spanning tree, and we consider a the distributed asynchronous optimization problem with a centralized server. My understanding is that, conceptually speaking, the setting that the authors consider is closer to this hypothetical setting than to the more canonical decentralized setting that previous papers consider.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review! We now respond to the weaknesses:\n\n> 1. This is also somewhat related to the strengths part. While the paper keeps referring to and comparing against some previous works...\n\nBefore we answer this comment, note that our new methods are optimal (up to log factor) for all possible parameters $h_i, \\tau_{i \\to j}, ...$, so if we want to show that some other method is worse, it is enough to show in one (practical) scenario (take $\\tau_{i \\to j} = 0$ for instance). Returning back to the comment, we totally agree that most of the previous methods designed their methods for a different setting, Gossip-type communication, but it does not mean that we can not compare the previous methods with our new methods. For instance, we consider Asynchronous SGD in the Gossip framework (Even et al 2024) in the scenario when the communication is free or negligible (Section 5.4). This scenario is equivalent to the setting when the Gossip matrix $w_{ij}$ is non-zero for all $i \\neq j$ (in one step, one worker can send a vector to all other workers because communication is free). We explain that even in this scenario, when Asynchronous SGD is allowed for free to send one vector to other workers, it is worse than our method. We did similar work with other methods and showed that they are strongly worse (Sections 5.4, B.4, and C.7).\n\nIn fact, our setting is more general than the Gossip communication. Indeed, recall that in the Gossip communication, a worker is allowed to get vectors $\\{x_j\\}$ from other workers through the operation $\\sum_{j=1}^n w_{ij} x_j,$ where $w_{ij}$ either zero or not zero. This is equivalent to our setting for the case when the communication time $\\rho_{ij} = \\infty$ when $w_{ij}$ is zero, and $\\rho_{ij} = 1$ if $w_{ij}$ is not zero, and worker $i$ sums the received vectors. But our setting is richer since we allow different communication and computation times, and allow workers to do with vectors whatever they like (not only to sum).\nWe should probably add this paragraph to the paper. Thank you for the good comment!\n\nFinally, the Gossip framework codes the communication graph through the matrix $W = [w_{ij}]$. We propose to code graphs through the times $\\rho_{i \\to j}$ ($\\tau_{i \\to j}$). Our approach is closer to real scenarios because, as we explained previously, it includes the Gossip framework.\n\n> 2. The second point is also somewhat related. I appreciate it that the authors takes computation and communication times into consideration...\n\nIn the previous comment, we explained that our time complexity framework is more general. As a consequence, it includes more realistic scenarios than the Gossip framework, for instance. We argue that the time complexity metric is one of the most natural metrics for parallel setting, unlike the iteration complexity metric. Our assumptions are generic and only assume that communication and computation take time, so it is not clear where we overfitted our methods. Of course, it is possible to add other time restrictions to take this setup closer to reality, but our work can be a starting point.\n\n> 3. Fragile SGD requires a pivot worker which is, in some sense, at the center of the graph, to coordinate the updates...\n\nFragile SGD and Amelie SGD were designed to show that our lower bounds are tight (up to log factor). We do not deny the possibility of designing methods without pivot workers and spanning trees. However, any other method without these algorithmic components will not beat these methods due to the lower bounds. The fact that the methods distinguish one pivot worker does not contradict the decentralized setting. We agree that Fragile SGD and Amelie SGD, in some sense, mimic the centralized setup, but we are totally allowed to do it. Note that we can design similar methods in the Gossip setting, taking one pivot worker that aggregates all vectors from other workers using $W$ through several steps: in the first step, the pivot worker aggregates vectors from the neighbors $\\sum_{j=1}^n w_{ij} x_j,$ in the second step, it aggregates the vector from the neighbors of the neighbors $\\sum_{j=1}^n w_{ij} w_{jk} x_k,$ where $w_{jk} x_k$ is calculated in the first step in worker $j,$ and so on. This way, we can aggregate all information in one worker.", "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": "", "extra_scores": {}}, {"review_id": "RSJNETNdxv", "reviewer": "Reviewer_qqc5", "summary": "The paper presents new theoretical advancements in decentralized stochastic asynchronous optimization. They introduce two new methods: Fragile SGD and Amelie SGD. Fragile SGD is designed for homogeneous setups, while Amelie SGD addresses heterogeneous setups. Both methods aim to achieve near-optimal time complexities under arbitrary heterogeneous computation and communication speeds. The paper establishes new lower bounds for time complexities in these setups and proves that the proposed methods match these bounds up to logarithmic factors.", "questions": "I have no questions.", "limitations": "Limitations are addressed in the paper (selecting optimal pivot worker)", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "The paper is well-written and organized, making significant theoretical contributions by establishing new lower bounds for time complexities in decentralized asynchronous optimization. The introduction and analysis of Fragile SGD and Amelie SGD add value to the field. Additionally, the proposed methods demonstrate robustness to dynamic computation and communication times.", "weaknesses": "1. Although the algorithms are interpretable, they may be challenging to implement in practical systems. \n\n2. There is limited experimental validation of the proposed methods.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the positive evaluation of our work! Let us respond to the weaknesses:\n\n> Although the algorithms are interpretable, they may be challenging to implement in practical systems.\n\nWe agree that our algorithms seem too lengthy, but the goal was to provide a very detailed listing to ensure that the algorithms can be implemented correctly and without challenges. We tried to give as many details as possible.\n\n> There is limited experimental validation of the proposed methods.\n\nThe main target of the paper was to obtain the fundamental limits of decentralized optimization. Thus, we focused our attention on theoretical results and lower bounds, which we believe are important to understand the nature of decentralized optimization. In Section I, we run our algorithms to test our theory and ensure that the dependencies that appear in theory are reflected in practice. *Moreover, we prepared extra experiments with logistic regression and a neural network that the reviewer can find in the global rebuttal response, which we will add to the camera-ready version.*", "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": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers and the AC for their time and effort. **In the attached PDF**, we added extra experiments with logistic regression and a neural network to support our theoretical claims. These experiments, together with the experiments from Section I, provide solid evidence that our method is efficient and generalizes well (has good accuracy on test splits of datasets).

We want to emphasize that this is the first work to provide *optimal theoretical time complexities* for the challenging decentralized setting with heterogeneous computation and communication times. It was not a trivial task because it required us to develop new proof techniques to prove the lower bounds (see the descriptions in Section 4). We discovered many phenomena, such as *not all workers* should work to achieve optimality in the homogeneous setting (see Section 5.2). Moreover, we derive time complexities with non-trivial dependencies for Line, Torus, and Star graphs, which were unknown in the literature. We believe that these theoretical results, which include lower bounds and optimal methods, are of significant importance to the community working on decentralized methods. 

Thank you again! If you have more questions, we will be happy to provide more details.

Meta-review: This paper presents an innovative application of spanning trees in decentralized stochastic asynchronous optimization, contributing significantly to the theoretical foundations of the field. The proposed algorithm improves robustness by mitigating the influence of the worst-performing nodes and provides valuable insights into both computational time complexity and practical applications. The paper is well-written, offering detailed explanations, rigorous proofs, and comprehensive supplementary materials. One reviewer expressed a concern regarding the role of the pivot worker, which the authors satisfactorily addressed during the rebuttal phase. Therefore, we recommend accepting this paper.
Decision: Accept (poster)