On the Optimal Time Complexities in Decentralized Stochastic Asynchronous Optimization

Authors: alexander tyurin kaust
skoltech ‡ peter
richtárik  kaust
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-08 12:04:41

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.

Main paper: 
 introduction: 
 We consider the smooth nonconvex optimization problemEQUATIONwhere f : R d × S ξ → R, and D ξ is a distribution on a non-empty set S ξ . For a given ε > 0, we want to find a possibly random point x, called an ε-stationary point, such that E[∥∇f (x)∥ 2 ] ≤ ε. We analyze the heterogeneous setup and the convex setup with smooth and non-smooth functions in Sections C and D.We investigate the following decentralized asynchronous setup. Assume that we have n workers/nodes with the associated computation times {h i }, and communications times {ρ i→j }. It takes less or equal to h i ∈ [0, ∞] seconds to compute a stochastic gradient by the i th node, and less or equal ρ i→j ∈ [0, ∞] seconds to send directly a vector v ∈ R d from the i th node to the j th node (it is possible that h i = ∞ and ρ i→j = ∞). All computations and communications can be done asynchronously and in parallel. We would like to emphasize that h i ∈ [0, ∞] and ρ i→j ∈ [0, ∞] 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 a vector h ∈ R n such that h i ∈ [0, ∞], and a matrix of distances {ρ i→j } i,j ∈ R n×n such that ρ i→j ∈ [0, ∞] for all i, j ∈ [n] and The shortest distance between nodes 5 and 3 is τ 5→3 = ρ 5→1 + ρ 1→2 + ρ 2→3 . Note that ρ 5→3 = ∞. On the right: an example of a spanning tree that illustrates the shortest paths from every node to node 3. The shortest distance between nodes 6 and 3 is τ 6→3 = ∞ because ρ 6→i = ∞ for all i ̸ = 6. ρ i→i = 0 for all i ∈ [n]. Every worker i is connected to any other worker j with two edges i → 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 :EQUATIONwhereP i→j := [(k 1 , k 2 ), . . . , (k m , k m+1 )] ∀m ∈ N ∀p ∈ [m + 1] ∀k p ∈ [n],k 1 = i, k m+1 = j, ∀j ∈ {2, . . . , m} k j-1 ̸ = k j ̸ = k j+1is the set of all possible paths without loops from worker i to worker j for all i, j ∈ [n]. One can easily show that the triangle inequality τ i→j ≤ τ i→k + τ k→j holds for all i, j, k ∈ [n]. Note that τ i→j ≤ ρ i→j for all i, j ∈ [n]. It is important to distinguish τ i→j and ρ i→j because it is possible that τ i→j < ρ i→j = ∞ if workers i and j are connected by an edge ρ i→j = ∞, and there is a path through other workers (see Fig. 1 ).We work with the following standard assumption from smooth nonconvex stochastic optimization literature.Assumption 1. f is differentiable and L-smooth, i.e., ∥∇f (x) -∇f (y)∥ ≤ L ∥x -y∥ ∀x, y ∈ R d .Assumption 2. There exist f * ∈ R such that f (x) ≥ f * for all x ∈ R d .Assumption 3. For all x ∈ R d , stochastic gradients ∇f (x; ξ) are unbiased and σ 2 -variancebounded, i.e., E ξ [∇f (x; ξ)] = ∇f (x) and E ξ [∥∇f (x; ξ) -∇f (x)∥ 2 ] ≤ σ 2 , where σ 2 ≥ 0. We also assume that computation and communication times are statistically independent of stochastic gradients.2 Previous Results 
time complexity with one worker: 
 For the case when n = 1 and τ 1→1 = 0, convergence rates and time complexities of problem (1) are well-understood. It is well-known that the stochastic gradient method (SGD), i.e., x k+1 = x k -γ∇f (x k ; ξ k ), where {ξ k } are i.i.d. from D ξ , has the optimal oracle complexity Θ( L∆ /ε + σ 2 L∆ /ε 2 ) (Ghadimi and Lan, 2013; Arjevani et al., 2022) . Assuming that the computation time of one stochastic gradient is bounded by h 1 , we can conclude that the optimal time complexity isT τ =0 single := Θ h 1 × L∆ ε + σ 2 L∆ ε 2(3) seconds in the worst case.Assume that n > 1 and τ i→j = 0 for all i, j ∈ [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 ε-stationary point in the nonconvex setting. We assume that τ i→j = τ j→i for all i, j ∈ [n] in this table. Abbr.: σ 2 is defined as E ξ [∥∇f (x; ξ) -∇f (x)∥ 2 ] ≤ σ 2 for all x ∈ R d , L is a smoothness constant of f, ∆ := f (x 0 ) -f * .Minibatch SGD max max i,j∈ [n] τi→j , maxi∈[n] hi L∆ ε + σ 2 L∆ nε 2Suboptimal since, for instance, it "linearly" (c) depends on max i∈ [n] hi SWIFT (Bornstein et al., 2023 ) - (b) Suboptimal since, for instance, it "linearly" (c) depends on max i∈ [n] hi Asynchronous SGD (Even et al., 2024 ) - (b) Suboptimal, for instance, even if τi→j = 0 ∀i, j ∈ [n] Fragile SGD (Corollary 1)L∆ ε min j∈[n] t * ( σ 2 /ε, [hi] n i=1 , [τi→j ] n i=1 ) (a)Optimal up to log n factor Lower Bound (Theorem 1)1 log n+1 L∆ ε min j∈[n] t * ( σ 2 /ε, [hi] n i=1 , [τi→j ] n i=1 ) (a)- (a) The mapping t * is defined in Definition 2. (b) It is not trivial to infer 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. (c) Meaning that the corresponding time complexity → ∞ if max i∈[n] hi → ∞.i.e.,EQUATIONwhere {ξ k i } are i.i.d. from D ξ and the gradient ∇f (x k ; ξ k i ) is calculated in worker i in parallel. This method waits for stochastic gradients from all workers; thus, it is not robust to "stragglers" and in the worst case the time complexity of such an algorithm isT τ =0 mini := Θ max i∈[n] h i × L∆ ε + σ 2 L∆ nε 2, which depends on the time max i∈[n] h i 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 et 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 i }, Tyurin and Richtárik (2023) showed that Rennala SGD is the first method that achieves the optimal time complexityEQUATION)where π is a permutation that sorts h i :h π1 ≤ • • • ≤ h πn . For instance, one can see that T τ =0 Rennala ≤ T τ =0mini for all parameters.We now consider the setup where workers' communication times can not be ignored. This problem leads to a 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 an iteration converge rate that depends on the spectral gap of a 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 a way that all workers calculate one stochastic gradient (takes at most max i∈[n] h i seconds) and then aggregate them to one pivot worker j * (takes at most max i∈[n] τ i→j * seconds). Then, pivot worker j * calculates Table 2 : Heterogeneous Case (17). Time complexities to get an ε-stationary point in the nonconvex setting. Abbr.: σ 2 is defined as hi} suboptimal if σ 2 /ε is largeE ξ [∥∇f i (x; ξ) -∇f i (x)∥ 2 ] ≤ σ 2 for all x ∈ R d , i ∈ [n], L is a smoothness constant of f = 1 n n i=1 f i , ∆ := f (x 0 ) -f * .RelaySGD, Gradient Tracking (Vogels et al., 2021 ) (Liu et al., 2024 )≥ max i∈[n] L i ∆ ε σ 2 nε max i∈[n]hi requires local Li-smooth. of fi, suboptimal if σ 2 /ε is large (even if max i∈[n] Li = L) Asynchronous SGD (Even et al., 2024) requires similarity of the functions {fi}, requires local Li-smooth. of fi Amelie SGD and Lower Bound (Thm. 7 and Cor. 2)L∆ ε max max i,j∈[n] τi→j , max i∈[n] hi, σ 2 nε 1 n n i=1hi Optimal up to a constant factor a new point x k+1 and broadcasts it to all workers (takes max i∈[n] τ j * →i seconds). One can easily see that the time complexity of such a procedure is4 EQUATION)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 in the setting from Section 1.1?Unlike the setups from Sections 2.1 and 2.2 when the communication times are zero (τ i→j = 0 for all i, j ∈ [n]), the optimal time complexity and an optimal method for the case τ i→j ≥ 0 for all i, j ∈ [n] are not known. Our main goal in this paper is to solve this problem.π j,k * →j , h π j,k * } < k * i=1 p hπ j,i -1 , then it is not possible that max{τ π j,k * +1 →j , h π j,k * +1 } < k * +1 i=1 p hπ j,i -1because it would yield the inequalitytj = 1 8 k * i=1 p h πj,i -1 ≥ 1 8 k * +1 i=1 p h πj,i -1 = 1 8 max    max{τ π j,k * +1 →j , h π j,k * +1 }, k * +1 i=1 p h πj,i -1    .The last inequality contradicts the fact that k * is the largest minimizer. Thus, if k * < n andmax{τ π j,k * →j , h π j,k * } < k * i=1 p hπ j,i -1 , then tj < 1 8 max    max{τ π j,k * +1 →j , h π j,k * +1 }, k * +1 i=1 p h πj,i -1    = 1 8 max{τ π j,k * +1 →j , h π j,k * +1 }.In total, we havetj < max{τ π j,k * +1 →j , h π j,k * +1 } if k * < n.Using this inequality, we getEQUATIONfor any k * . (Part 2)We have three options:1. If k * i=1 p hπ j,i -1≥ max{τ π j,k * →j , h π j,k * }, then, using (50) and ⌊x⌋ ≤ x for all x ≥ 0, we getp n i=1 tj h πj,i 1 τ πj,i→j ≤ tj ≤ p k * i=1 tj h πj,i = 1 8 k * i=1 p h πj,i -1 p k * i=1 1 h πj,i = 1 8 . 2. If k * i=1 p hπ j,i -1 < max{τ π j,k * →j , h π j,k * } and k * = 1, then p n i=1 tj h πj,i 1 τ πj,i→j ≤ tj = p tj h π j,k * 1 τ π j,k * →j ≤ tj = 0 because tj = 1 8 max    max{τ π j,k * →j , h π j,k * }, k * i=1 p h πj,i -1    = 1 8 max{τ π j,k * →j , h π j,k * } < max{τ π j,k * →j , h π j,k * }. 3. If k * i=1 p hπ j,i -1 < max{τ π j,k * →j , h π j,k * } and k * > 1, then tj = 1 8 max{τ π j,k * →j , h π j,k * } and tj h πj,i 1 τ πj,i→j ≤ tj = 0 for all i ≤ k * such that max{τ πj,i→j , h πj,i } = max{τ π j,k * →j , h π j,k * }. If this equality holds for all i ≤ k * , then p n i=1 tj h πj,i 1 τ πj,i→j ≤ tj = 0.Otherwise, there exists ℓ < k * such that max{τ π j,ℓ →j , h π j,ℓ } < max{τ π j,k * →j , h π j,k * } andp n i=1 tj h πj,i 1 τ πj,i→j ≤ tj = p ℓ i=1 tj h πj,i 1 τ πj,i→j ≤ tj . It is not possible that max{τ π j,ℓ →j , h π j,ℓ } ≥ ℓ i=1 p hπ j,i -1because it would yield the inequalitytj = 1 8 max{τ π j,k * →j , h π j,k * } > 1 8 max{τ π j,ℓ →j , h π j,ℓ } = 1 8 max    max{τ π j,ℓ →j , h π j,ℓ }, ℓ i=1 p h πj,i -1   that contradicts the fact that tj is the minimum (see ( 46)). Thus, we havetj ≤ 1 8 max    max{τ π j,ℓ →j , h π j,ℓ }, ℓ i=1 p h πj,i -1    = 1 8 ℓ i=1 p h πj,i -1 and p n i=1 tj h πj,i 1 τ πj,i→j ≤ tj = p ℓ i=1 tj h πj,i 1 τ πj,i→j ≤ tj ≤ p ℓ i=1 tj h πj,i ≤ 1 8 ℓ i=1 p h πj,i -1 p ℓ i=1 1 h πj,i ≤ 1 8 .In total, we havep n i=1 tj h πj,i 1 τ πj,i→j ≤ tj ≤ 1 8for tj from (46).In this case, we consider the following oracle mappings. For all i ∈ [n], we defineEQUATIONwhere ξ ∼ D. Unlike ( 27), the mapping (51) returns ∇f i (s x ; ξ). Theorem 20. Consider Protocol 8 with the mappings (51). We take any h i ≥ 0 and τ i→j ≥ 0 for all i, j ∈ [n] such that τ i→j ≤ τ i→k + τ k→j for all i, k, j ∈ [n]. We fix L, ∆, ε, σ 2 > 0 that satisfy the inequality ε < c 1 L∆. For any algorithm A ∈ A zr , there exists a function f = 1 n n i=1 f i , which satisfy Assumptions 1, 2 and f (0) -f * ≤ ∆, and stochastic gradient mappings∇f i (•; •), which satisfy Assumption 3 (E ξ [∇f i (x; ξ)] = ∇f i (x) and E ξ [∥∇f i (x; ξ) -∇f i (x)∥ 2 ] ≤ σ 2 ), such that E inf k∈St,i∈[n] ∇f (x k i ) 2 > ε, where S t := k ∈ N 0 | t k ≤ t , t = c 2 × L∆ ε max max i,j∈[n] τ i→j , max i∈[n] h i , σ 2 nε 1 n n i=1 h i ,The quantities c 1 and c 2 are universal constants. The sequences x k and t k are defined in Protocol 8.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 τ i→j = 0 for all i, j ∈ [n]. It is left to prove the first term. Let us fix λ > 0. Let us take any pair ( ī, j) of workers such that max i,j∈[n] τ i→j = τī → j . Next, we split the blocks of the function F T (x) from ( 33) and define two new functions:EQUATIONandF T,2 (x) := i∈{2,...,T },i | 2=0 [Ψ(-x i-1 )Φ(-x i ) -Ψ(x i-1 )Φ(x i )] .We consider the following functions f i :f i (x) :=      nLλ 2 l1 F T,1 x λ , i = ī, nLλ 2 l1 F T,2 x λ , i = j, 0, i ̸ = ī and i ̸ = j.Then, we getf (x) = 1 n n i=1 f i (x) = 1 n nLλ 2 l 1 F T,1 x λ + nLλ 2 l 1 F T,2 x λ = Lλ 2 l 1 F T x λ .Let us show that the function f is L-smooth:∥∇f (x) -∇f (y)∥ = Lλ l 1 ∇F T x λ -∇F T y λ ≤ L ∥x -y∥ .Let us takeT = ∆l 1 Lλ 2 ∆ 0 , then f (0) -inf x∈R T f (x) = Lλ 2 l 1 (F T (0) -inf x∈R T F T (x)) ≤ Lλ 2 ∆ 0 T l 1 ≤ ∆.We showed that the function f satisfy Assumptions 1, 2 and f (0) -f * ≤ ∆.In the oracles O i , we simply take the non-stochastic mappings ∇f i (x; ξ) := ∇f i (x) that are unbiased and 0-variance-bounded.We takeλ = l 1 √ ε L to ensure that ∥∇f (x)∥ 2 = L 2 λ 2 l 2 1 ∇F T x λ 2 > L 2 λ 2 l 2 1 = εfor all x ∈ R T such that prog(x) < T. In the last inequality, we use Lemma 1. ThusT = ∆L l 1 ε∆ 0 .Only workers ī and j contain the information about the function f. The function f is a zero-chain function, and we split it between workers ī and j. Due to this splitting, workers ī 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 F T,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 a vector with a non-zero value in the first coordinate to worker j because only this worker can get a non-zero value in the second coordinate. This communication takes at least τī → j seconds. Using the same reasoning, worker j has to send a vector to worker ī once worker j has discovered a non-zero value in the second coordinate.An algorithm has to repeat such communications at least T -1 2 times to find a vector x ∈ R T such that prog(x) = T.Thus, we getinf k∈St,i∈[n] ∇f (x k i ) 2 > ε for t = τī → j T -1 2 = max i,j∈[n] τ i→j 2 ∆L l 1 ε∆ 0 -1 .Theorem 4. Let Assumptions 1, 2, and 3 hold. We take γ = 1/2L, batch size S = max{ σ 2 /ε , 1}, any pivot worker j * ∈ [n], and any spanning trees st and st bc in Algorithm 2. For all K ≥ 16L∆/ε,we get 1 K K-1 k=0 E ∇f (x k ) 2 ≤ ε.Proof. Algorithm 2 produces the sequence x k such asx k+1 = x k -γ s k g k = x k -γḡ k, where ḡk := 1 s k g k . By the design of the algorithm,ḡk = 1 s k s k i=1 ∇f (x k ; ξ i ),where the ξ i are independent random samples and s k ≥ S. We do not dismiss the possibility that the computation and communication times are random, so s k can be random. Assume V k is a σ-algebra generated by all computation and communication times and g 0 , . . . , g k-1 , then s k is V k -measurable.Using the independence and Assumption 3, we haveE ḡk G k = E   E   1 s k s k i=1 ∇f (x k ; ξ i ) V k   G k   = E   1 s k s k i=1 E ∇f (x k ; ξ i ) V k G k   = ∇f (x k ) and E ḡk -∇f (x k ) 2 G k = E    E    1 s k s k i=1 ∇f (x k ; ξ i ) -∇f (x k ) 2 V k    G k    = E   1 (s k ) 2 s k i=1 E ∇f (x k ; ξ i ) -∇f (x k ) 2 V k G k   ≤ E σ 2 s k G k ≤ σ 2 S .where G k is a σ-algebra generated by ḡ0 , . . . , ḡk-1 . We can use a well-known SGD result (Ghadimi and Lan, 2013; Khaled and Richtárik, 2022) . Using Theorem 21, for the stepsizeγ = 1 2L min 1, εS σ 2 ,we have1 K K-1 k=0 E ∇f (x k ) 2 ≤ ε, if K ≥ 8∆L ε + 8∆Lσ 2 ε 2 S .Using the choice of S, we get that Algorithm 2 converges afterK ≥ 16∆L ε steps with γ = 1 2L min 1, εS σ 2 = 1 2L .Theorem 5. Consider the assumptions and the parameters from Theorem 4. For any pivot worker j * ∈ [n] and spanning trees st and st bc , Algorithm 2 converges after at mostEQUATIONseconds, where µ i→j * (µ j * →i ) is an upper bound on the times required to send a vector from worker i to worker j * (from worker j * to worker i) along the spanning tree st (spanning tree st bc ).Proof. Due to Theorem 4, we know that Algorithm 3 finds an ε-stationary point after at most K = Θ L∆ ε iterations. It is left to bound the time of one iteration to prove the theorem.For all j ∈ [n], we define π j,• as a permutation that sorts{max{µ i→j + µ j→i , h i }} n i=1 as max{µ πj,1→j + µ j→πj,1 , h πj,1 } ≤ • • • ≤ max{µ πj,n→j + µ j→πj,n , h πj,n }.k * = arg min k∈[n] max    max{µ π j * ,k →j * + µ j * →π j * ,k , h π j * ,k }, S k i=1 1 h π j * ,i -1    .and the setA * := {π j * ,i ∈ [n] | i ≤ k * }that represents a set of the "fastest" workers that can potentially contribute to an optimization process. We takeEQUATIONIn the following steps of the proof we show that every iteration takes at most t for all i ≤ k * . Thus, using (54) and ⌊x⌋ ≥ x 2 for all x ≥ 1, we get(EQUATION≥ S.Therefore, after t seconds the algorithm will calculate at least S stochastic gradients at the point x k using the workers A * .(Step 2): By the design of Algorithm 4, once a stochastic gradient ∇f (x k ; ξ) is calculated, it is added to g k i,next . Then, g k i,next is assigned to g k i,send which is sent to Process next st,j * (i). Finally, Process next st,j * (i) receives g k i,send and adds it to g k (next st,j * (i)),next . Thus, the stochastic gradient ∇f (x k ; ξ) is presented in the sum of g k (next st,j * (i)),next of Process next st,j * (i). At some point, Process 0 in worker j * will receive a vector g k•,send where the stochastic gradient ∇f (x k ; ξ) is presented. Let us bound the time required to transmit a stochastic gradient to Process 0 of worker j * . Once a stochastic gradient ∇f (x k ; ξ) is calculated in Process i from A * , it is added to a vector g k i,next in Process i. It will take at most 2ρ i→next st,j * (i) seconds to transmit it to Process next st,j * (i) because it takes at most ρ i→next st,j * (i) seconds to wait for the transmission of a message g k i,send where the stochastic gradient ∇f (x k ; ξ) is not presented, and an additional ρ i→next st,j * (i) seconds to send the next g k i,send where it will present. After that, Process next st,j * (i) will receive g k i,send , where the stochastic gradient ∇f (x k ; ξ) presents, and add the vector g k i,send to g k (next st,j * (i)),next . Then, it will take at most 2ρ next st,j * (i)→next(next st,j * (i)) seconds to send a vector, where the stochastic gradient ∇f (x k ; ξ) presents, to Process next(next st,j * (i)) and so forth. In total, after a finite number of such steps a stochastic gradient calculated in Process i will be transmitted to Process 0 of worker j * . From Definition 3 of next st,j * , we can conclude that the vector ∇f (x k ; ξ) will be transmitted through the path between workers i and j * in the spanning tree st. Thus, it will take at most 2µ i→j * seconds by the definition of µ i→j * .Using (55) and the definition of A * , we have t ≥ 2 max{µ π j * ,k * →j * + µ j * →π j * ,k * , h π j * ,k * } ≥ 2 max{µ i→j * + µ j * →i , h i } ≥ 2µ i→j * (56) for all i ∈ A * . Therefore, it will take at most t seconds to calculate at least S stochastic gradients, and at most t seconds to send all these stochastic gradients to Process 0.(Step 3): It is left to estimate the time of the broadcast steps (Lines 7-9 in Algorithm 4) through the spanning tree st bc . By the definition of µ j * →i , the time required to broadcast x k to Process i through the spanning tree st bc is less or equal to 2µ j * →i since, in all edges from j * to i, workers wait at most ρ •→• seconds while edges are blocked by previous communications, and additional ρ •→• seconds to send x k to next workers. Using (55) and the definition of A * , we havet ≥ 2 max{µ π j * ,k * →j * + µ j * →π j * ,k * , h π j * ,k * } ≥ 2 max{µ i→j * + µ j * →i , h i } ≥ 2µ j * →i .Thus, every worker from A * will get x k after t seconds. By combining all times, we can conclude that every iteration in Algorithm 3 will take at most t + t + t = 3 t seconds.It left to show thatEQUATION) If S > 1, then S = max{ σ 2 /ε , 1} = σ 2 /ε ≤ 2σ 2 /ε, so it is true. Otherwise, if S ≤ 1, then t ≤ 2 max    max{µ π j * ,k * →j * + µ j * →π j * ,k * , h π j * ,k * }, k * i=1 1 h π j * ,i -1    ≤ 2 max max{µ π j * ,k * →j * + µ j * →π j * ,k * , h π j * ,k * }, h π j * ,k * = 2 max{µ π j * ,k * →j * + µ j * →π j * ,k * , h π j * ,k * }and (57) holds. Notice that the r.h.s. of (57) equals to O t * ( σ 2 /ε, [h i ] n i=1 , [µ i→j * + µ j * →i ] n i=1 ), where t * is the equilibrium time defined in Definition 2. Theorem 6. Consider the assumptions and the parameters from Theorem 4. In each iteration k of Algorithm 3, the computation times of worker i are bounded by h k i . Let us fix any pivot worker j * ∈ [n] and any spanning trees st and st bc . Then Algorithm 2 converges after at mostEQUATIONseconds, where µ k i→j * (µ k j * →i ) is an upper bound on times required to send a vector from worker i to worker j * (from worker j * to worker i) along the spanning tree st (spanning tree st bc ) in iteration k of Algorithm 3.Proof. The proof is almost the same as in Theorem 5. If we fix a pivot worker j * , then the k th iteration will finish after at mostc × t * ( σ 2 /ε, [h k i ] n i=1 , [µ k i→j * + µ k j * →i ] n i=1 )seconds, where c is a universal constant. According to Theorem 4, the number of iterations is at most 16L∆ ε. Therefore, the total required time is at mostc × ⌈ 16L∆ ε ⌉ k=0 t * ( σ 2 /ε, [h k i ] n i=1 , [µ k i→j * + µ k j * →i ] n i=1 ).H Proof of the Time Complexity for Heterogeneous Case Theorem 8. Let Assumptions 1 and 2 hold for the function f and Assumption 3 holds for the functions f i for all i ∈ [n]. We take γ = 1/2L, the parameter S = max{ σ 2 /ε , n}, any pivot worker j * ∈ [n], and any spanning trees st and st bc , in Algorithm 5. For all iterations number K ≥ 16L∆/ε, we get1 K K-1 k=0 E ∇f (x k ) 2 ≤ ε.Proof. Algorithm 5 produces the sequence x k such thatx k+1 = x k -γg k = x k -γ 1 n n i=1 1 s k i g k i = x k -γ   1 n n i=1 1 s k i s k i j=1 ∇f i (x k ; ξ ij )   ,where the ξ ij are independent random samples. Using the independence and Assumption 3, we haveEQUATION)where G k is a σ-algebra generated by g 0 , . . . , g k-1 . We do not dismiss the possibility that the computation and communication times are random, so s k i can be random. Assume V k is a σ-algebra generated by all computation and communication times and g 0 , . . . , g k-1 , then s k i is V k -measurable for all i ∈ [n]. Using the independence of stochastic gradients and the times and the tower property, we getEQUATION)Algorithm 6 waits for the moment when s k ≥ S n , which is equivalent toEQUATIONThe value b j * is calculated in Line 20 of Algorithm 7. Due to the asynchronous nature of the algorithm, we can only conclude thatEQUATIONbecause s k j * can be increased by the time when Process 0 will receive b j * . Using Line 15 from Algorithm 7, we can unroll the recursion in (62) and getEQUATIONLet us substitute this inequality to (61) and (60) and getE g k -∇f (x k ) 2 G k ≤ σ 2 S .As in Theorem 4, we can use the classical SGD result. Using Theorem 21, for the stepsizeγ = 1 2L min 1, εS σ 2 ,we have1 K K-1 k=0 E ∇f (x k ) 2 ≤ ε, if K ≥ 8∆L ε + 8∆Lσ 2 ε 2 S .Using the choice of S, we get that Algorithm 5 converges afterK ≥ 16∆L ε steps with γ = 1 2L min 1, εS σ 2 = 1 2L .Theorem 9. Consider the assumptions and the parameters from Theorem 8. For any pivot worker j * ∈ [n] and any spanning trees st and st bc , Algorithm 5 converges after at mostΘ L∆ ε max max i,j∈[n] µ i→j , max i∈[n] h i , σ 2 nε 1 n n i=1 h i seconds, where µ k i→j * (µ k j * →i) is an upper bound on times required to send a vector from worker i to worker j * (from worker j * to worker i) along the spanning tree st (spanning tree st bc ) for all i ∈ [n].Proof. Due to Theorem 8, the algorithm converges after K = Θ (L∆/ε) iterations. Thus, it left to bound the time of one iteration. At the beginning of every iteration Process 0 broadcasts x k , which takes at most max i,j∈[n] µ i→j seconds. Then, Algorithm 6 waits for the moment when s k ≥ S n , which is equivalent to n 2 S ≥ b j * . Thus, Algorithm 6 waits for the moment when n 2 S ≥ b j * . We will return to this fact later.Let us consider the termS n 2 n i=1 1 s k i ,where s k i is the number of stochastic gradients calculated in worker i. Let us fix any time t > 0. Then, worker i will calculate at least t hi stochastic gradients by the time t. Using this, we getS n 2 n i=1 1 s k i ≤ S n 2 n i=1 1 t hi . Let us take t = 2 max i∈[n] h i + S n 1 n n i=1 h i .Then, since ⌊x⌋ ≥ x 2 for all x ≥ 1, we get t hi ≥ t 2hi andEQUATION)after at most t seconds.Recall that Algorithm 6 waits for the moment when n 2 S ≥ b j * . Note that by the time when Process 0 receives b j * , the counter s k i can be the same or increased; thus, b j * captures potentially outdated information about s k i . We know that (64) holds after at most t seconds. In Line 20 of Algorithm 7, Processes recursively collect 1 s k i to b j * . Such a procedure will take at most 2 max i∈[n] µ i→j * ≤ 2 max i,j∈[n] µ i→j seconds. Thus, the value b j * will be less or equal n 2 S after at most t + 2 max i,j∈[n] µ i→j seconds.The all reduce operation in (8) will take at most max i,j∈[n] µ i→j seconds. Thus, the total time of one iteration can be bounded bymax i,j∈[n] µ i→j broadcast +( t + 2 max i,j∈[n] µ i→j ) + max i,j∈[n] µ i→j all reduce = O max i,j∈[n] µ i→j + max i∈[n] h i + S n 1 n n i=1 h i = O max i,j∈[n] µ i→j + max i∈[n] h i + σ 2 nε 1 n n i=1 h i .seconds.We reprove the classical SGD result (Ghadimi and Lan, 2013; Khaled and Richtárik, 2022) , for completeness.Theorem 21. Let Assumptions 1 and 2 hold. We consider the SGD method:x k+1 = x k -γg(x k ), where γ = 1 2L min 1, ε σ 2For all k ≥ 0, the vector g(x) is a random vector such that E gEQUATIONwhere G k is a σ-algebra generated by g(x 0 ), . . . , g(x k-1 ). Then1 K K-1 k=0 E ∇f (x k ) 2 ≤ ε for K ≥ 8∆L ε + 8∆Lσ 2 ε 2 .Proof. From Assumption 1, we havef (x k+1 ) ≤ f (x k ) + ∇f (x k ), x k+1 -x k + L 2 x k+1 -x k 2 = f (x k ) -γ ∇f (x k ), g(x k ) + Lγ 2 2 g(x k ) 2 .We denote G k as a sigma-algebra generated by g(x 0 ), . . . , g(x k-1 ). Using unbiasedness and (65), we obtainE f (x k+1 ) G k ≤ f (x k ) -γ 1 - Lγ 2 ∇f (x k ) 2 + Lγ 2 2 E g(x k ) -∇f (x k ) 2 G k ≤ f (x k ) -γ 1 - Lγ 2 ∇f (x k ) 2 + Lγ 2 σ 2 2 . Since γ ≤ 1 /L, we get E f (x k+1 ) G k ≤ f (x k ) - γ 2 ∇f (x k ) 2 + Lγ 2 σ 2 2 .We subtract f * and take the full expectation to obtainE f (x k+1 ) -f * ≤ E f (x k ) -f * - γ 2 E ∇f (x k ) 2 + Lγ 2 σ 2 2 .Next, we sum the inequality for k ∈ {0, . . . , K -1}:E f (x K ) -f * ≤ f (x 0 ) -f * - K-1 k=0 γ 2 E ∇f (x k ) 2 + KLγ 2 σ 2 2 = ∆ - K-1 k=0 γ 2 E ∇f (x k ) 2 + KLγ 2 σ 2 2 .Finally, we rearrange the terms and use that Ef (x K ) -f * ≥ 0: 1 K K-1 k=0 E ∇f (x k ) 2 ≤ 2∆ γK + Lγσ 2 .The choice of γ and K ensures that1 K K-1 k=0 E ∇f (x k ) 2 ≤ ε.Theorem 22. Let Assumptions 4 and 5 hold. We consider the SGD method:x k+1 = x k -γg(x k ), where γ = ε M 2 + σ 2For all k ≥ 0, the vector g(x) is a random vector such that E g(x k ) G k ∈ ∂f (x k ) E g(x k ) -E g(x k ) G k 2 G k ≤ σ 2 ,where G k is a σ-algebra generated by g(x 0 ), . . . , g(x k-1 ). ThenE f 1 K K-1 k=0 x k -f (x * ) ≤ ε (66) for K ≥ (M 2 + σ 2 ) x * -x 0 2 ε 2 .Proof. We denote G k as a sigma-algebra generated by g(x 0 ), . . . , g(x k-1 ). Using the convexity, for all x ∈ R d , we havef (x) ≥ f (x k ) + E g(x k ) G k , x -x k = f (x k ) + E g(x k ), x -x k G k . Note that g(x k ), x -x k = g(x k ), x k+1 -x k + g(x k ), x -x k+1 = -γ g(x k ) 2 + 1 γ x k -x k+1 , x -x k+1 = -γ g(x k ) 2 + 1 2γ x k -x k+1 2 + 1 2γ x -x k+1 2 - 1 2γ x -x k 2 = - γ 2 g(x k ) 2 + 1 2γ x -x k+1 2 - 1 2γ x -x k 2 and E g(x k ) 2 G k = E g(x k ) -E g(x k ) G k 2 G k + E g(x k ) G k 2 ≤ σ 2 + M 2 .Therefore, we getf (x k ) ≤ f (x) + E g(x k ), x k -x G k = f (x) + γ 2 E g(x k ) 2 G k + 1 2γ x -x k 2 - 1 2γ E x -x k+1 2 G k ≤ f (x) + γ 2 M 2 + σ 2 + 1 2γ x -x k 2 - 1 2γ E x -x k+1 2 G k .By taking the full expectation and summing the last inequality for t from 0 to K -1, we obtainE K-1 k=0 f (x k ) ≤ Kf (x) + Kγ 2 M 2 + σ 2 + 1 2γ x -x 0 2 - 1 2γ E x -x K 2 ≤ Kf (x) + Kγ 2 M 2 + σ 2 + 1 2γ x -x 0 2 .Let divide the last inequality by K, take x = x * , and use the convexity:E f 1 K K-1 k=0 x k -f (x * ) ≤ γ 2 M 2 + σ 2 + 1 2γKx * -x 0 2 .The choices of γ and K ensure that (66) holds.We now consider Fragile SGD with Minibatch SGD on quadratic optimization tasks with stochastic gradients. The working environment was emulated in Python 3.8 with one Intel(R) Xeon(R) Gold 6248 CPU @ 2.50GHz. The homogeneous optimization problem (1) is constructed in the following way. We take Let us define [x] j as the j th index of a vector x ∈ R d . All n workers calculate the stochastic gradientsf (x) = 1 2 x ⊤ Ax -b ⊤ x ∀x ∈[∇f (x; ξ)] j := [∇f (x)] j 1 + 1 [j > prog(x)] ξ p -1 ∀x ∈ R d , ∀i ∈ [n],where ξ ∼ Bernouilli(p), p ∈ (0, 1]. In our experiments, we take p = 0.001 and the starting point x 0 = [ √ d, 0, . . . , 0] ⊤ . We emulate our setup by considering that the i th worker requires h i = 1 second to calculate a stochastic gradient. And we assume that the workers have the structure of 2D-Mesh (see Figure 4a ) and take ρ i→j = ρ ∈ {0.1, 1, 10} seconds for all edges that connect workers in 2D-Mesh. We take n = 100. In all methods we fine-tune step sizes from the set {2 i | i ∈ [-20, 20]}. In Fragile SGD, we fine-tune the batch size S from the set {10, 20, 40, 80, 120}.The results are presented in Figures 5, 6 , and 7. The plots are fully consisted with Table 1 . 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 all workers in the optimization steps. However, when we start decreasing the communication speed, we observe that Fragile SGD converges faster.We looked deeper into the optimization processes of Fragile SGD in Figure 7 and observed that only 13 of 100 workers contribute to 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. 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 is 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. ). We use the torus structure and 9 workers. We run all methods with the step sizes {0.025, 0.25, 2.5}. Our findings from the low-scale experiments are also evident in the large-scale experiments. Fragile SGD converges faster than Minibatch SGD in terms of function values. When we compare accuracies on the test split of MNIST, the superiority of Fragile SGD is even more transparent. • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It 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 a 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 or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
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 a 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 2 and Section C), where we discover the optimal time complexity by proving another lower bound and developing a new optimal method, Amelie SGD, with weak assumptions. The developed methods can guarantee the iteration complexity O ( L∆ /ε) with arbitrarily heterogeneous random computation and communication times (Theorems 4 and 8). Our findings are extended to the convex setup in Section D, where we developed new accelerated methods, Accelerated Fragile SGD and Accelerated Amelie SGD.x ∈ R T , ∥∇F T (x)∥ ∞ ≤ γ ∞ , where γ ∞ = 23. 4. For all x ∈ R T , prog(∇F T (x)) ≤ prog(x) + 1.5. For all x ∈ R T , if prog(x) < T, then ∥∇F T (x)∥ > 1. Theorem 19. Consider Protocol 8. We take any h i ≥ 0 and τ i→j ≥ 0 for all i, j ∈ [n] such that τ i→j ≤ τ i→k + τ k→j for all i, k, j ∈ [n]. We fix L, ∆, ε, σ 2 > 0 that satisfy the inequality ε < c ′ L∆. For any algorithm A ∈ A zr , there exists a function f, which satisfy Assumptions 1, 2 and f (0) -f * ≤ ∆, and a stochastic gradient mapping ∇f (•; •), which satisfy Assumption 3, such thatE inf k∈St,i∈[n] ∇f (x k i ) 2 > ε, where S t := k ∈ N 0 | t k ≤ t , t = c × 1 log n + 1 L∆ ε min j∈[n] min k∈[n] max    max{τ π j,k →j , h π j,k }, σ 2 ε k i=1 1 h πj,i -1    ,where π j,• is a permutation that sorts max{h i , τ i→j }, i.e., 2022); Lu and De Sa (2021) . We provide it for completeness. The goal of this part to construct a hard instance.max{h πj,1 , τ πj,1→j } ≤ • • • ≤ max{h πj,n ,We fix λ > 0, T ∈ N and take the function f (x) := Lλ 2 l1 F T x λ , where the function F T is defined in Section E.4. Note that the function f is L-smooth:∥∇f (x) -∇f (y)∥ = Lλ l 1 ∇F T x λ -∇F T y λ ≤ Lλ x λ - y λ = L ∥x -y∥ ∀x, y ∈ R d ,where l 1 -smoothness of F T (Lemma 1). Let us takeT = ∆l 1 Lλ 2 ∆ 0 , then f (0) -inf x∈R T f (x) = Lλ 2 l 1 (F T (0) -inf x∈R T F T (x)) ≤ Lλ 2 ∆ 0 T l 1 ≤ ∆.We showed that the function f satisfy Assumptions 1, 2 and f (0) -f * ≤ ∆.For each worker i we take an oracle O i , from ( 27) with the mapping g such that[∇f (x; ξ)] j := ∇ j f (x) 1 + 1 [j > prog(x)] ξ p -1 ∀x ∈ R T ,andD i = Bernouilli(p) for all i ∈ [n], where p ∈ (0, 1]. We denote [x] j as the j th index of a vector x ∈ R T . This stochastic gradient is unbiased and σ 2 -variance-bounded. We haveE [[∇f (x, ξ)] i ] = ∇ i f (x) 1 + 1 [i > prog(x)] E [ξ] p -1 = ∇ i f (x)for all i ∈ [T ], andE ∥∇f (x; ξ) -∇f (x)∥ 2 ≤ max j∈[T ] |∇ j f (x)| 2 E ξ p -1 2because the difference is non-zero only in one coordinate. ThusE ∥∇f (x, ξ) -∇f (x)∥ 2 ≤ ∥∇f (x)∥ 2 ∞ (1 -p) p = L 2 λ 2 ∇F T x λ 2 ∞ (1 -p) l 2 1 p ≤ L 2 λ 2 γ 2 ∞ (1 -p) l 2 1 p ≤ σ 2 ,where we use Lemma 1 and takep = min L 2 λ 2 γ 2 ∞ σ 2 l 2 1 , 1 .Let us takeλ = √ 2εl 1 L to ensure that ∥∇f (x)∥ 2 = L 2 λ 2 l 2 1 ∇F T x λ 2 = 2ε ∇F T x λ 2 for all x ∈ R T .From Lemma 1, we know that if prog(x) < T, then ∥∇F T (x)∥ > 1. Thus, we getEQUATIONTherefore,EQUATION)The inequality (34) impliesEQUATIONwhere {x k i } ∞ k=0 are sequences from Protocol 8. Part 2: Reduction to Lower Bound Time Series We now focus on (27). In ( 27), when the oracle in worker i calculates a new stochastic gradient, it samples a random variable ξ ∼ D. This is equivalent to the procedure if we had T infinite sequences of i.i.d. Bernoulli random variablesξ 1,1 i , ξ 1,2 i , . . . (prog(s x ) = 0) ξ 2,1 i , ξ 2,2 i , . . . (prog(s x ) = 1) . . . ξ T,1 i , ξ T,2 i , . . . (prog(s x ) = T -1)for all i ∈ [n] and the oracle would look at the progress of s x and take the next non-taken Bernoulli random variable in the sequence that corresponds to that progress. For instance, if prog(s x ) = j for the first time in worker i, then the oracle will apply ξ j,1 i in ( 27). The next time when it gets prog(s x ) = j it will apply ξ j,2 i and so on. One by one, we get i.i.d. Bernoulli random variables. Let us defineη k i = inf{j ∈ N | ξ k,j i = 1} for all i ∈ [n] and k ∈ [T ]. This is the first Bernoulli random variable from the sequence ξ k,1 i , ξ k,2 i , . . . that equals 1. The random variables {η k i } are i.i.d. 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 it takes h i seconds to calculate a stochastic gradient, and at least τ i→j seconds to send a 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 a vector with the first non-zero coordinate greater or equaly 1 j := min i∈[n] h i η 1 i + τ i→jbecause, at the beginning, each worker i calculates stochastic gradients with prog(s x ) = 0 and should wait at least h i η 1 i seconds to get a stochastic gradient with the progress equals 1. Then, it can share this vector with any other worker j, but it takes at least τ i→j seconds.As in Proof Sketch of Theorem 19, we can use mathematical induction to prove that it is necessary to wait at leasty T j := min i∈[n] y T -1 i + h i η T i + τ i→jseconds to get a point such that prog(s x ) = T. The base case for y 1 j has been proven. Worker i requires at least y T -1 i + h i η T i seconds to wait for the moment when the corresponding oracle will return a stochastic gradient with progress T because y T -1 i is the first time possible time to get a vector with progress T -1 by the induction, and it will take at least additional h i η T i seconds to calculate η T i vectors with prog(s x ) = T -1 in ( 27). Also, it takes at least τ i→j seconds to share a vector, so it is necessary to wait at least min i∈[n] y T -1 i + h i η T i + τ i→j seconds in worker i to get the first vector with progress T.In the end, the fastest possible time to get a vector with progress T is at leasty T := min j∈[n] y T j .Part 3: Reduction to the concentration of y T The last statement means that prog(x k i ) < T for all i ∈ [n] and k such that t k ≤ 1 2 y T . Therefore, we obtaininf k∈St,i∈[n] ∇f (x k i ) 2 > 2ε (38) for t ≤ 1 2 y T ,whereT = ∆L 2εl 1 ∆ 0 = c T • ∆L ε and η j i ∼ Geometric(p) with p = min 2εγ 2 ∞ σ 2 , 1 = min c p • ε σ 2 , 1 ,where c T = 3648 -1 and c p = 1058 are universal constants. Let us fix any determenistic value ȳ ∈ R and takeEQUATION)Using ( 38), we haveE inf k∈St,i∈[n] ∇f (x k i ) 2 ≥ E inf k∈St,i∈[n] ∇f (x k i ) 2 y T > ȳ P y T > ȳ > P y T > ȳ 2ε.Thus, it is sufficient to find any ȳ ∈ R such thatEQUATION)In the following lemma we use the notation of this theorem. We prove it in Section E.5.EQUATION)we have P y T ≤ ȳ ≤ 1 2 , where π j,• is a permutation that sorts max{h i , τ i→j }, i.e., max{h πj,1 , τ πj,1→j } ≤ • • • ≤ max{h πj,n , τ πj,n→j } for all j ∈ [n].The quantity c is a universal constant.Using Lemma 2, we can conclude that (40) holds andEQUATIONwe have P y T ≤ ȳ ≤ 1 2 , where π j,• is a permutation that sorts max{h i , τ i→j }, i.e.,max{h πj,1 , τ πj,1→j } ≤ • • • ≤ max{h πj,n , τ πj,n→j } for all j ∈ [n].The quantity c is a universal constant.Proof. Using the Chernoff method for any s > 0, we getP y k ≤ t = P -sy k ≥ -st = P e -sy k ≥ e -st ≤ e st E e -sy k = e st E exp -s min j∈[n] y k j = e st E max j∈[n]exp -sy k j .We have a maximum operation that complicates the analysis. In response to this problem, we use a well-known trick that bounds a maximum by a sum.EQUATIONWe refer to (Van Handel, 2014) [Part II] for the explanation why it can be (almost) tight. This is the main reason why we get an extra log n factor in (41). Let us consider the last exponent separately and use the same trick again:E exp -sy k j = E exp -s min i∈[n] y k-1 i + h i η k i + τ i→j = E max i∈[n] exp -s y k-1 i + h i η k i + τ i→j .Next, we getE exp -sy k j ≤ n i=1 E exp -s y k-1 i + h i η k i + τ i→j = n i=1 E e -s(hiη k i +τi→j ) E exp -sy k-1 i .In the last equality we use the independence. We now boundE exp -sy k-1 i by max i∈[n] E exp -sy k-1 i and get E exp -sy k j ≤ n i=1 E e -s(hiη k i +τi→j ) E exp -sy k-1 i ≤ n i=1 E e -s(hiη k i +τi→j ) max i∈[n] E exp -sy k-1 i .Let us fix any s j > 0 for all j ∈ [n] and take s = max j∈[n] s j . ThenEQUATIONLet us fix tj > 0 and considerEQUATIONThen, we can use the following inequalities:a j ≤ n i=1 E e -sj (hiη k i +τi→j ) 1 h i η k i + τ i→j ≤ tj + e -sj (hiη k i +τi→j ) 1 -1 h i η k i + τ i→j ≤ tj ≤ n i=1 E 1 h i η k i + τ i→j ≤ tj + e -sj tj 1 -1 h i η k i + τ i→j ≤ tj = ne -sj tj + (1 -e -sj tj ) n i=1 E 1 h i η k i + τ i→j ≤ tj ≤ ne -sj tj + n i=1 E 1 h i η k i + τ i→j ≤ tj ≤ ne -sj tj + n i=1 P h i η k i + τ i→j ≤ tj ≤ ne -sj tj + n i=1 P h i η k i ≤ tj 1 [τ i→j ≤ tj ] .Since η k i ∼ Geometric(p), we getP h i η k i ≤ tj = 1 -(1 -p) tj h i ≤ p tj h i .Thena j ≤ ne -sj tj + p n i=1 tj h i 1 [τ i→j ≤ tj ] .For all j ∈ [n], we take any permutation π j,• that sorts max{h i , τ i→j }, i.e.,max{h πj,1 , τ πj,1→j } ≤ • • • ≤ max{h πj,n , τ πj,n→j }.We haveEQUATIONRecall that tj > 0 is a parameter. In the following technical lemma, we choose tj and show that the second term in ( 45) is "small." We prove it in Section E.6.Lemma 3. For any n ≥ 1, h i ≥ 0,τ i→j ≥ 0 for all i, j ∈ [n], and p ∈ (0, 1], we havep n i=1 tj h πj,i 1 τ πj,i→j ≤ tj ≤ 1 8 for all j ∈ [n],whereEQUATIONand π j,• is a permutation that sorts max{h i , τ i→j }, i.e.,max{h πj,1 , τ πj,1→j } ≤ • • • ≤ max{h πj,n , τ πj,n→j } for all j ∈ [n].Using Lemma 3 and (45), we getEQUATIONto geta j ≤ 1 8 + 1 8 ≤ e -1 .for all j ∈ [n]. Using ( 44) and ( 43), we obtainEQUATIONfor all j ∈ [n]. We can conclude thatmax i∈[n] E exp -sy k i ≤ e -1 max i∈[n] E exp -sy k-1 i ≤ e -k ,where use the same reasoning in the recursion and y 0 j = 0 for all j ∈ [n]. We substitute the inequality to (42):P y k ≤ t ≤ ne st-k = e st-k+log nIt is sufficient to take k = T and anyt ≤ 1 s T -log n + log 1 2 = 1 8 log 8n min i∈[n] min k∈[n] max    max{τ π j,k →j , h π j,k }, k i=1 p h πj,i -1    T -log n + log 1 2 to get P y T ≤ t ≤ 1 2 ,where we use the definitions s = max i∈[n] s i , (46) and ( 47). Recall the choice of T and p in ( 35) and ( 36):T = c T • ∆L ε and p = min c p • ε σ 2 , 1for some universal constants c T and c p . Since we have the condition ε < c ′ L∆ for some universal constant c ′ in the conditions of Theorem 19, we can conclude that we can taket = c × 1 log n + 1 L∆ ε min i∈[n] min k∈[n] max    max{τ π j,k →j , h π j,k }, σ 2 ε k i=1 1 h πj,i -1    ,where c is a universal constant.Lemma 3. For any n ≥ 1, h i ≥ 0,τ i→j ≥ 0 for all i, j ∈ [n], and p ∈ (0, 1], we havep n i=1 tj h πj,i 1 τ πj,i→j ≤ tj ≤ 1 8 for all j ∈ [n],whereEQUATION)and π j,• is a permutation that sorts max{h i , τ i→j }, i.e.,max{h πj,1 , τ πj,1→j } ≤ • • • ≤ max{h πj,n , τ πj,n→j } for all j ∈ [n].Let us define k * ∈ [n] as the largest index that minimizes (46). (Part 1): bound tj by max{τ π j,k * +1 →j , h π j,k * +1 } Let us consider the case k * < n. We have two options:EQUATIONsince max{τ πj,i→j , h πj,i } are sorted. Then, we gettj < 1 8 max    max{τ π j,k * +1 →j , h π j,k * +1 }, k * +1 i=1 p h πj,i -1    (49) = 1 8 max{τ π j,k * +1 →j , h π j,k * +1 } ≤ max{τ π j,k * +1 →j , h π j,k * +1 }The first inequality follows from the fact that k * is the largest minimizer. 
lower bound: 
 In order to construct our lower bound, we consider any (zero-respecting) method that can be represented by Protocol 1. This protocol captures all virtually distributed synchronous and asynchronous methods, such as Minibatch SGD, SWIFT (Bornstein et al., 2023) , Asynchronous SGD (Even et 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 ∇f (•; •). We take any h i ≥ 0 and τ i→j ≥ 0 for all i, j ∈ [n] such that τ i→j ≤ τ i→k + τ k→j for all i, k, j ∈ [n]. We fix L, ∆, ε, σ 2 > 0 that satisfy the inequality ε < cL∆ for some universal constant c. For any (zero-respecting) algorithm, there exists a function f, which satisfy Assumptions 1, 2 and f (0) -f * ≤ ∆, and a stochastic gradient mapping ∇f (•; •), which satisfies Assumption 3, such that the required time to find ε-solution isEQUATIONwhere, for j ∈ [n], π j,• is a permutation that sorts {max{τ i→j , h i }} n i=1 , i.e., max{τ πj,1→j , h πj,1 } ≤ Send (a) any vector from R d based on S i to any worker j and go to the next step of this loop without waiting (takes τ i→j seconds to send; worker j adds this vector to S j ) 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 i to worker j for all i ̸= j ∈ [n].The intuition and meaning of the formula ( 8) is discussed in Section 5.2. Note that if we take n = 1 and τ 1→1 = 0 our lower bound reduces to the lower bound (3) up to a log factor. Moreover, if we take n > 1 and τ i→j = 0 for all i, j ∈ [n], then (8) reduces to (5) up to a log factor. Thus, (8) is nearly consistent with the lower bounds from (Arjevani et al., 2022; Tyurin and Richtárik, 2023) . We get an extra log n factor due to the generality of our setup. The reason is technical, and we explain it in Section E.5. In a nutshell, the lower problem reduces to the analysis of the concentration of the time series y T := min j∈[n] y T j and y Tj := min i∈[n] y T -1 i + h i η T i + τ i→j, where y 0 i = 0 for all i ∈ [n], and {η k i } are i.i.d. geometric random variables. This analysis is not trivial due to the min i∈ [n] operations. Virtually all previous works that analyzed lower bounds did not have such a problem because they analyzed time series with a sum structure (e.g., ȳT := ȳT -1 + ϱ T , where {ϱ k } are some random variables, and ȳ0 = 0). vector) , and [τ i ] n i=1 (vector) is called the equilibrium time if it is defined as follows. Find a permutation5 π that sorts max{τ i , h i } as max{τ π1 , h π1 } ≤ • • • ≤ max{τ πn , h πn }. Then the mapping returns the valueEQUATIONEQUATION5 New Method: Fragile SGDWe 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 is 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 ).Algorithm 2 Fragile SGD 1: Input: starting point x 0 , stepsize γ, batch size S, pivot worker j * , spanning trees st and st bc 2: Start Process 0 (Algorithm 3) in worker j * 3: Start Process i (Algorithm 4) in all workers for all i ∈ [n] (including worker j * )Algorithm 3 Process 0 (running in worker j * )1: for k = 0, 1, . . . , K -1 do 2:Send x k to Process j * ▷ takes τ j * →j * = 0 seconds 3:Init (g k , s k ) = (0, 0) 4:while s < S do 5:Wait for a message (g k j * ,send , s k j * ,send ) from Process j * 6:g k = g k + g k j * ,send ; s k = s k + s k j * ,send 7:end while 8:x k+1 = x kγ s k g k 9: end for Algorithm 4 Process i (running in worker i) a) , k max = 0 2: Run the following three functions in parallel 3: function BroadcastFurtherAndCalculateStochasticGradients for all p such that next stbc,j * (p) = i do ▷ broadcasts x k further 8:1: Init (g k i,next , s k i,next ) = (0, 0) for all k ∈ {0, . . . , K -1} (Send (b) x k to Process p and go to the next step without waiting ▷ takes at most τ i→p seconds to send 9: end for end while 28: end function (a): To simplify the listing of the algorithm, we assume here that a worker can store K auxiliary vectors in the memory. One can see that it's not necessary, and it is sufficient to maintain only one vector g kmax i,next . In particular, it is sufficient to modify the logic of Lines 12 and 19, where we run the add operations only if k = kmax and k = kmax. The efficient implementation has O(d) floats memory complexity per worker. (b): BroadcastFurtherAndCalculateStochasticGradients and SendVectorsToNextWorker may try to send through the same edge. In this case, we can interleave their communications and decrease the speed of each line by at most two.Definition 3 (mapping next T,j (i)). Take a spanning tree T and fix any worker j ∈ [n]. For i = j, we define next T,j (i) = 0. For all i ̸ = j ∈ [n], we define next T,j (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 to be lengthy, the idea is pretty 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 g k and, at some moment, does x k+1 = x k -γg k . The algorithms formalize this idea.Algorithm 2 requires a starting point x 0 , a stepsize γ, a batch size S, the index j * of a pivot worker, and spanning trees st and st bc for the input. We need two spanning st bc and st trees because, in general, the fastest communication of a 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 0 broadcasts a new point x k through st bc to all other processes and goes to the loop where it waits for messages from Process j * . Process i starts three functions that will be running in parallel: i) the first function'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 * , iii) the third function sends vectors the next worker on the path to j * . By the definition of next st,j * (•), all calculated stochastic vectors are sent to worker j * , where they are first aggregated in Process j * , and then, since next st,j * (j * ) = 0, Process j * will send g k j * ,send to Process 0. This process waits for the moment when the number of stochastic gradients s k aggregated in g k 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 tox k+1 = x k -γ s k s k i=1 ∇f (x k ; ξ k i ), where s k ≥ S and {ξ k i } are i.i.d. samples. Note that all stochastic gradients calculated at points x 0 , . . . , x k-1 will be ignored in the k th iteration of Algorithm 3. Theorem 4. Let Assumptions 1, 2, and 3 hold. We take γ = 1/2L, batch size S = max{ σ 2 /ε , 1}, any pivot worker j * ∈ [n], and any spanning trees st and st bc in Algorithm 2. For all K ≥ 16L∆/ε,we get 1 K K-1 k=0 E ∇f (x k ) 2 ≤ ε.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 i = ∞ and τ i→j = ∞ for all i, j ∈ [n] because h i and τ i→j are only upper bounds on the real computation and communications speeds. In Algorithm 3, each iteration k can be arbitrarily slow, and still, the result of Theorem 4 holds and the method converges after O(L∆/ε) iterations. The next result gives time complexity guarantees for our algorithm. Theorem 5. Consider the assumptions and the parameters from Theorem 4. For any pivot worker j * ∈ [n] and spanning trees st and st bc , Algorithm 2 converges after at mostEQUATIONseconds, where µ i→j * (µ j * →i ) is an upper bound on the times required to send a vector from worker i to worker j * (from worker j * to worker i) along the spanning tree st (spanning tree st bc ).Note that our method does not need the knowledge of {h i } and {µ i→j } to guarantee the time complexity rate, and it automatically obtains it. Corollary 1. Consider the assumptions and the parameters from Theorem 5. Let us take a pivot worker j * = arg minj∈[n] t * ( σ 2 /ε, [h i ] n i=1 , [τ i→j + τ j→i ] n i=1), and a spanning tree st (spanning tree st bc ) that connects every worker i to worker j * (worker j * to every worker i) with the shortest distance τ i→j * (τ j * →i ). Then Algorithm 2 converges after at mostT * := Θ L∆ ε min j∈[n] t * ( σ 2 /ε, [h i ] n i=1 , [τ i→j + τ j→i ] n i=1 ) (11) Def 2 ≡ Θ L∆ ε min j∈[n] min k∈[n] max max{τ π j,k →j + τ j→π j,k , h π j,k }, σ 2 ε k i=1 1 hπ j,i -1 (12)seconds, where, for all j ∈ [n], π j,• is a permutation that sorts {max{τ i→j + τ j→i , h i }} n i=1 .This corollary has better time complexity guarantees than Theorem 5 because, by the definition of τ i→j , τ i→j ≤ µ i→j for al i, j ∈ [n]. However, it requires the particular choice of a pivot worker and spanning trees. 
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 τ i→j = τ j→i for all i, j ∈ [n], which is 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 {τ i→j }.We believe that this is an advantage of our guarantees since (11) 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 is that some workers will potentially never contribute to optimization because either their computations are too slow or communication times to j * are too 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 {h i } and {τ i→j }.One can see that ( 12) is the min j∈[n] min k∈[n] over some formula. In view of our algorithm, an index j * that minimizes in ( 12) is the index of a pivot worker that is the most "central" in the multigraph. An index k * that minimizes min k∈[n] defines a set of workers {π j * ,1 , . . . π j * ,k * } that can potentially contribute to optimization. The algorithm and and the time complexity will not depend on workers {π j * ,k * +1 , . . . π j * ,n } because they are too slow or they are too far from worker j * . Thus, up to a constant factor, we haveT * = L∆ /ε max max{τ π j * ,k * →j * + τ j * →π j * ,k * , h π j * ,k * }, σ 2 /ε k * i=1 1 /hπ j * ,i -1, where τ π j * ,k * →j * + τ j * →π j * ,k * is the time required to communicate with the farthest worker that can contribute to optimization, h π j * ,k * is the computation time of the slowest worker that can contribute to optimization, and σ 2 /ε k * i=11 /hπ j * ,i -1 is the time required to "eliminate" enough noise before the algorithm does an update of x k .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 5 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 to estimate the performance of workers and the communication channels using load testings.Let us discuss the time complexities of previous methods. We now consider a recent work by Even et al. (2024) , where the authors analyzed Asynchronous SGD in 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 τ i→j = 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 τ i→j = 0 is strongly worse than (5); thus, the result by Even et al. (2024) is suboptimal in our setting even if τ i→j = 0 for all i, j ∈ [n]. The papers by Bornstein et al. (2023) ; Lian et al. (2018) also consider the same setting, and they share a logic in that they sample a random worker and wait 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.We can easily generalize Theorem 5 to the case when bounds on the times are not static. Theorem 6. Consider the assumptions and the parameters from Theorem 4. In each iteration k of Algorithm 3, the computation times of worker i are bounded by h k i . Let us fix any pivot worker j * ∈ [n] and any spanning trees st and st bc . Then Algorithm 2 converges after at mostEQUATIONseconds, where µ k i→j * (µ k j * →i ) is an upper bound on times required to send a vector from worker i to worker j * (from worker j * to worker i) along the spanning tree st (spanning tree st bc ) in iteration k of Algorithm 3. This result is more general than (10), and it shows that our method is robust to changing computation {h k i } and communication {µ k i→j } times bounds during optimization processes. For instance, worker n can have either slow computation or communication to j * in the first iteration, i.e., max{h 1 n , µ 1 n→j * , µ 1 j * →n } ≈ ∞, then our method will ignore it, but if max{h 2 n , µ 2 n→j * , µ 2 j * →n } is small in the second iteration, then our method can potentially use the stochastic gradients from worker n.6 Example: Line or Circle1 2 3 4 5 6 7 ρ ρ ρ ρ ρ ρ τ 3→5 = 2ρ τ 3→6 = 3ρ τ 3→2 = ρ Figure 2: Line with ρ i+1→i = ρ i→i+1 = ρ for all i ∈ [n -1], ρ i→j = ∞ otherwise. For all i ̸ = j ∈ [n], edges i → j and j → i are merged and visualized with one 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, we show that our theoretical results are supported by computational experiments.We take a Line graph with the computation speeds h i = h for all i ∈ [n], and the communication speeds of the edgesρ i→i+1 = ρ i+1→i = ρ for all i ∈ [n -1] and ρ i→j = ∞ for all other i, j ∈ [n].One can easily show the time required to send a vector between two workers i, j ∈ [n] equals τ i→j = τ j→i = ρ|i -j|. See an example with n = 7 in Fig. 2 . We can substitute these values to (11) and getEQUATIONwhere π j,1 = j, π j,2 , π j,3 = j + 1, j -1 or π j,2 , π j,3 = j -1, j + 1 (only for n -1 ≥ j ≥ 2) and so forth. For simplicity, assume that n is odd, then, clearly, j * = n-1 2 + 1 minimizes min j∈[n] andEQUATION)According to (15), there are three time complexity regimes: i) slow communication, i.e., σ 2 h /ερ ≤ 1, this inequality means that ρ is so large, that communication between workers will not increase the convergence speed, and the best strategy is to work with only one worker!, ii) medium communication, i.e., n > σ 2 h /ερ > 1, more than one worker will participate in the optimization process; however, not all of them!, some workers will not contribute since their distances τ j * →• to the pivot worker j * are large, iii) fast communication, i.e., σ 2 h /ερ ≥ n, all n workers will participate in optimization because ρ is small.As far as we know, the result ( 15) is new even for such a simple structure as a 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 a constant factor. 
heterogeneous setup: 
 In Section C (in more details), we consider and analyze the problemmin x∈R d f (x) := 1 n n i=1 E ξi∼Di [f i (x; ξ i )] ,where f i : R d × S ξi → R d and ξ i are random variables with some distributions D i on S ξi . For all i ∈ [n], worker i can only access f i . We show that the optimal time complexity isΘ L∆ ε max max i,j∈[n] µ i→j , max i∈[n] h i , σ 2 nε 1 n n i=1 h i (16)in the heterogeneous setting achieved by a new method, Amelie SGD (Algorithm 5). Amelie SGD is closely related to 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.i ∈ [n], supp x k i ⊆ k j=1 supp g j i , and supp v k i ⊆ k j=1 supp g j i , for all k ∈ N 0 , where supp(x) := {i ∈ [d] | x i ̸ = 0}.The set of all algorithms with this properties we define as A zr .Constraints 1-5 define domains of the mappings. Constraint 6 is required to ensure that the time sequence t k does not decrease. Constraint 7 is a standard assumption that an algorithm is zerorespecting (Arjevani et al., 2022) . Theorem 19. Consider Protocol 8. We take any h i ≥ 0 and τ i→j ≥ 0 for all i, j ∈ [n] such that τ i→j ≤ τ i→k + τ k→j for all i, k, j ∈ [n]. We fix L, ∆, ε, σ 2 > 0 that satisfy the inequality ε < c ′ L∆. For any algorithm A ∈ A zr , there exists a function f, which satisfy Assumptions 1, 2 and f (0) -f * ≤ ∆, and a stochastic gradient mapping ∇f (•; •), which satisfy Assumption 3, such thatE inf k∈St,i∈[n] ∇f (x k i ) 2 > ε, where S t := k ∈ N 0 | t k ≤ t , t = c × 1 log n + 1 L∆ ε min j∈[n] min k∈[n] max    max{τ π j,k →j , h π j,k }, σ 2 ε k i=1 1 h πj,i -1    ,where π j,• is a permutation that sorts max{h i , τ i→j }, i.e.,max{h πj,1 , τ πj,1→j } ≤ • • • ≤ max{h πj,n , τ πj,n→j } for all j ∈ [n].The quantities c ′ and c are universal constants. The sequences x k and t k are defined in Protocol 8.Let us provide a proof sketch that will give intuition behind the theorem. The full proof starts in Section E.4.Proof Sketch.The first part of the proof is standard (Carmon et al., 2020; Arjevani et 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 a "worst-case" function such thatEQUATIONwhere prog(x) := max{i ≥ 0 | x i ̸ = 0} (x 0 ≡ 1) and T ≈ L∆ /ε. This inequality says that while all points in Protocol 8 have the last coordinate equals 0 by the time t, an algorithm can not find an ε-stationary point.Since we assume that A ∈ A zr is zero-respecting, the only way to discover the next non-zero coordinate is through stochastic gradients. They are constructed in the following way (Arjevani et al., 2022) :[∇f (x; ξ)] j := ∇ j f (x) 1 + 1 [j > prog(x)] ξ p -1 ∀x ∈ R T ,and ξ ∼ Bernoulli(p) for all i ∈ [n], where p ≈ ε /σ 2 . We denote [x] j as the j th index of a vectorx ∈ R T . The stochastic gradient equals to the exact gradient except for the last non-zero coordinate: it zeros out it with the high probability 1 -p.Part 2: The Level GameIn essence, the protocol is equivalent to the following collaborative game. Each worker i starts with level ℓ i = 0. The goal is to reach level T with at least one worker as fast as possible. There are two ways how a worker can increase its level: i) worker i flips one coin per time from ξ ∼ Bernoulli(p), it takes h i seconds to flip one coin, and if the worker is lucky, i.e., ξ = 1, then it moves to the next level ℓ i = ℓ i + 1; ii) worker i can share its level with another worker j, and it takes τ i→j seconds (we are allowed to run this operation again even if the previous is not finished). Both options can be executed in parallel. What is the minimum possible time to reach the game's goal?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 to level 1. We define η 1 i as the number of flips in worker i to get ξ = 1. Clearly, η 1 i ∼ Geometric(p) are i.i.d. geometric random variables with the probability p. With any strategy, it is necessary to wait at leasty 1 j := min i∈[n] h i η 1 i + τ i→jseconds to reach level 1 in worker j because once worker i flips ξ = 1, it will take at least τ i→j seconds to share level 1 to worker j due to the triangle inequality τ i→j ≤ τ i→k + τ k→j for all i, j, k ∈ [n], and we should minimize h i η 1 i + τ i→j over all workers. We now use mathematical induction to prove that it is necessary to wait at leasty T j := min i∈[n] y T -1 i + h i η T i + τ i→jseconds to reach level T, where we define y 0 i := 0 for all i ∈ [n] and {η T i } are i.i.d. random variables from Geometric(p). The base case is proven above. Assume that it is true for 1, . . . , T -1, then worker i requires at least y T -1 i + h i η T i seconds to flip a coin that moves to level T, it takes at least τ i→j seconds to share the level T, so it is necessary to wait at least min i∈[n] y T -1 i + h i η T i + τ i→j seconds in worker i to get level T. Ultimately, the minimum possible time to reach the game's goal isy T := min j∈[n] y T j .From the previous result, we can conclude that if t ≤ 1 2 y T , thenEQUATIONfor any algorithm A ∈ A zr .Part 3: The high probability bound of y TLet us fix any determenistic value ȳ ∈ R and takeEQUATIONUsing (30), we haveE inf k∈St,i∈[n] ∇f (x k i ) 2 ≥ E inf k∈St,i∈[n] ∇f (x k i ) 2 y T > ȳ P y T > ȳ > P y T > ȳ 2ε.Thus, it is sufficient to find any ȳ ∈ R such thatEQUATION)The sequence y T is a well-define time series. In Lemma 2, we show that (32) holds withȳ = Θ   1 log n + 1 L∆ ε min j∈[n] min k∈[n] max    max{τ π j,k →j , h π j,k }, σ 2 ε k i=1 1 h πj,i -1      , π j,• is a permutation that sorts max{h i , τ i→j }, i.e.,max{h πj,1 , τ πj,1→j } ≤ • • • ≤ max{h πj,n , τ πj,n→j } for all j ∈ [n].We substitute this ȳ to (31) and get the result of theorem.This section considers the standard "worst case" function that helps to provide lower bounds in the nonconvex world. Let us define prog(x) := max{i ≥ 0 | x i ̸ = 0} (x 0 ≡ 1).For any T ∈ N, Carmon et al. (2020) ; Arjevani et al. (2022) defineEQUATIONwhereΨ(x) = 0, x ≤ 1/2, exp 1 - 1 (2x-1) 2 , x ≥ 1/2,andΦ(x) = √ e x -∞ e -1 2 t 2dt.We will only rely on the following facts.Lemma 1 (Carmon et al. (2020) ; Arjevani et al. (2022) ). The function F T satisfies:1. F T (0) -inf x∈R T F T (x) ≤ ∆ 0 T, where ∆ 0 = 12.2. The function F T is l 1 -smooth, where l 1 = 152. 
highlights of experiments: 
 In Section J, we present experiments with quadratic optimization problems, logistic regression, and a neural network to substantiate our theoretical findings. Here, we focus on highlighting the results from the logistic regression experiments: 0.0 0.2 0.4 0.6 0.8 1.0 times (seconds) 1e6 2.2 × 10 1 2.4 × 10 1 2.6 × 10 1 2.8 × 10 1 3 × 10 1 f(x t ) f(x *A.1 ND-Mesh or ND-TorusWe now consider a generalization of Line graphs: ND-Mesh graphs. In Figures 4a and 4b , we present examples of 2D-Mesh and 3D-Mesh. For simplicity, assume that n = (2k + 1) N for some k ∈ N.i = h for all i ∈ [n],and the communicate speeds of the edges ρ i→j = ρ if workers i and j are connected in a mesh and ρ i→j = ∞ for all other i, j ∈ [n]. Using geometrical reasoning, it is clear an index j * , that minimizes (11), corresponds to the worker in the middle of a graph (13 in Figures 4a and 14 in Figures 4b). Therefore,T 2D-Mesh = Θ L∆ ε min k∈[n] max τ π j * ,k →j * , h, σ 2 h kε .For now, let us consider a 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 ρ, is 5. The number of workers, that have the length of the shortest path to j * less or equal to 2ρ, is 13. In general, the number of workers, that have the length of the shortest path to j * less or equal to√ kρ, is Θ(k) for all k ∈ {0, . . . , Θ (n)}. It means T 2D-Mesh = Θ L∆ ε min k∈{0,...,Θ(n)} max √ kρ, h, σ 2 h (k + 1)ε = Θ       L∆ ε       h +            σ 2 h ε , σ 2 h ρε 2/3 ≤ 1, ρ 2/3 σ 2 h ε 1/3 , n > σ 2 h ρε 2/3 > 1, σ 2 h nε , σ 2 h ρε 2/3 ≥ n            .Using the same reasoning, for the general case with a ND-Mesh graph, we getT ND-Mesh = Θ L∆ ε min k∈{0,...,Θ(n)} max k 1/N ρ, h, σ 2 h (k + 1)ε = Θ       L∆ ε       h +            σ 2 h ε , σ 2 h ρε N/(N +1) ≤ 1, ρ N/(N +1) σ 2 h ε 1/(N +1) , n > σ 2 h ρε N/(N +1) > 1, σ 2 h nε , σ 2 h ρε N/(N +1) ≥ n             .As in Line graphs, these complexities have three regimes depending on the problem's parameters. Up to a constant factor, the same conclusions apply to ND-Torus.Let us consider Star graphs with different computation and communication speeds. Let us fix a graph with n + 1 workers, where one worker with the index n + 1 is in the center, and all other n workers are only directly connected to worker n + 1. Then,τ i→j = ρ i→n+1 + ρ n+1→j ∀i ̸ = j ∈ [n + 1] and τ i→i = 0 ∀i ∈ [n].Using these constraints, we can simplify (11). There are two possible best strategies: i) a pivot worker j * works locally without communications, ii) a pivot worker j * works with communications but it would necessary require to communicate through the central worker; in this case, the central worker n + 1 is a pivot worker. Therefore, we getT star = min L∆ ε min j∈[n] max h j , σ 2 h j ε L∆ ε min k∈[n] max    max{ρ π n+1,k →n+1 + ρ n+1→π n+1,k , h π n+1,k }, σ 2 ε k i=1 1 h πn+1,i -1    since τ n+1→π n+1,k = ρ n+1→π n+1,k for all k ∈ [n + 1].Let us slightly simplify the result and assume that broadcasting from the central worker is fast, i.e., ρ n+1→i ≤ ρ i→n+1 for all i ∈ [n + 1], thenT star = min L∆ ε min j∈[n] max h j , σ 2 h j ε Tslow comm. , L∆ ε min k∈[n] max    max{ρ π n+1,k →n+1 , h π n+1,k }, σ 2 ε k i=1 1 h πn+1,i -1    Tfast comm.. Tyurin et al. (2024) also considered Star graphs and showed that T fast 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 T slow comm. that can be potentially smaller if communication is slow. Tyurin et al. (2024) conjectured that T star is the optimal bound, and we proved it (up to log factor) here.We show how one can use our generic result (11) to get an explicit formula in some cases. For the general case with arbitrary communication and computation times, the minimizers j and k in (11) can be found in the following way. First, we have to find τ i→j using any algorithm that solves the all-pairs shortest path problem (e.g., Floyd-Warshall algorithm (Floyd, 1962) ). Once we know τ i→j , we should sort {max{τ i→j + τ j→i , h i }} n k=1 for all j ∈ [n] to find the permutations. Finally, we have enough information to calculate t * from Definition 2.Most of the previous methods were designed for a different setting, gossip-type communication. In fact, our setting is more general than the gossip communication. Indeed, recall that in the gossip communication, worker i is allowed to get vectors from other workers through the operation n j=1 w ij x j , where w ij ∈ {0, 1}. This is equivalent to our setting for the case when the communication time ρ ij = ∞ when w ij is zero, and ρ 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 whatever they like with vectors (not only to sum).Moreover, the gossip framework codes the communication graph through the matrix {w ij }. We propose to code graphs through the times {ρ ij } ({τ ij }). Our approach is closer to real scenarios because, as we explained previously, it includes the gossip framework.We now consider the heterogeneous setting. The only difference is instead of (1), we consider the following problem.EQUATION)where f i : R d × S ξi → R d and ξ i are random variables with some distributions D i on S ξi . We now present our upper and lower bounds and discuss them.In Section F, we prove the following lower bound.Theorem 7 (Lower Bound; Simplified Presentation of Theorem 20). Consider Protocol 1 with ∇f i (•; •). We take any h i ≥ 0 and τ i→j ≥ 0 for all i, j ∈ [n] such that τ i→j ≤ τ i→k + τ k→j for all i, k, j ∈ [n]. We fix L, ∆, ε, σ 2 > 0 that satisfy the inequality ε < cL∆ for some universal constant c.For any (zero-respecting) algorithm, there exists a function f = 1 n n i=1 f i , which satisfy Assumptions 1, 2 and f (0) -f * ≤ ∆, and stochastic gradient mappings ∇f i (•; •), which satisfy Assumption 3(E ξ [∇f i (x; ξ)] = ∇f i (x) and E ξ [∥∇f i (x; ξ) -∇f i (x)∥ 2 ] ≤ σ 2 ), such that the required time to find ε-solution is Ω L∆ ε max max i,j∈[n] τ i→j , max i∈[n] h i , σ 2 nε 1 n n i=1 h i seconds.C.2 Amelie SGD: optimal method in the heterogeneous settingWe 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 n + 1 processes running in all workers. The main idea is that all workers calculate stochastic gradients in parallel and accumulate them locally. Process 0 zero waits for the moment when n b j * ≥ S n . Process i calculates b i in Line 20 of Algorithm 7, and sends it to Process next st,j * (i). Thus, b j * accumulates the sum n i=1 1 s k i , which decreases with time since s k i is the number of calculated stochastic gradients in worker i in different moments of time. Therefore, n b j * ≥ S n will hold at some point of time if workers continue computing gradients. Finally, Algorithm 6 runs all reduce and does the update of x k . Theorem 8. Let Assumptions 1 and 2 hold for the function f and Assumption 3 holds for the functions f i for all i ∈ [n]. We take γ = 1/2L, the parameter S = max{ σ 2 /ε , n}, any pivot worker j * ∈ [n], and any spanning trees st and st bc , in Algorithm 5. For all iterations number K ≥ 16L∆/ε, we get1 K K-1 k=0 E ∇f (x k ) 2 ≤ ε.Note that Theorem 8 states the convergence of Amelie SGD even 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 st bc , Algorithm 5 converges after at mostΘ L∆ ε max max i,j∈[n] µ i→j , max i∈[n] h i , σ 2 nε 1 n n i=1 h i seconds, where µ k i→j * (µ k j * →i) is an upper bound on times required to send a vector from worker i to worker j * (from worker j * to worker i) along the spanning tree st (spanning tree st bc ) for all i ∈ [n].Algorithm 5 Amelie SGD 1: Input: starting point x 0 , stepsize γ, parameter S, pivot worker j * , spanning trees st and st bc 2: Start Process 0 (Alg. 6) in worker j * 3: Start Process i (Alg. 7) in all workers for all i ∈ [n] (including worker j * ) Algorithm 6 Process 0 (running in worker j * )1: for k = 0, 1, . . . , K -1 do 2:Broadcast x k to all workers using the spanning tree st bc 3:Init s k = 0 4: while s k < S n do 5:Wait for a message b j * from Process j * 6:Calculates k = n b j * 7:end whileRun all reduce with { 1s k i g k i } n i=1 to find g k = 1 n n i=1 1 s k ig k i using the spanning tree st 9:x k+1 = x k -γg k 10: end for Algorithm 7 Process i (running in worker i)1: while True do 2:Get a new point x k broadcasted by Process 0 3:Init (g k i , s k i ) = (0, 0) 4: Init b i,p = ∞ for all p ∈ [n] s.t. next st,j * (p) = i 5:Run the following three functions in parallel and go to Line 24 Ignore all non-received messages 26: end while Corollary 2. Consider the assumptions and the parameters from Theorem 9. Let us take any pivot worker j * ∈ [n] and a spanning tree st (spanning tree st bc ) that connects every worker i to worker j * (worker j * to worker i) with the shortest distance τ i→j * (τ j * →i ), then Algorithm 5 converges after at mostΘ L∆ ε max max i,j∈[n] τ i→j , max i∈[n] h i , σ 2 nε 1 n n i=1 h i (18)seconds.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" max i,j∈[n] τ i→j and the slowest performance max i∈[n] h i . A similar dependence was observed in (Lu and De Sa, 2021; Tyurin and Richtárik, 2023) . As in (Tyurin and Richtárik, 2023) , the stochastic termσ 2 /nε ( 1 /n n i=1 h i ) depends on the average of {h i } if σ 2/ε is large.Let us consider Minibatch SGD described in Section 2.3. This method converges afterΘ L∆ ε max max i,j∈[n] τ i→j , max i∈[n] h i , σ 2 nε max{ max i,j∈[n] τ i→j , max i∈[n] h i }seconds in the heterogeneous setting. If σ 2 /ε is large, then Amelie SGD can be at leastmax{ max i,j∈[n] τ i→j , max i∈[n] h i }/ 1 n n i=1 h itimes faster than Minibatch SGD. There are many more advanced methods (Lu and De Sa, 2021; Vogels et al., 2021; Even et 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 a 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 f i , 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 i∈[n] h i in all regimes of σ 2 /ε, unlike our method. Even et al. (2024) consider the heterogeneous asynchronous setting, but their method assumes the similarity of the functions f i , which is not required in our method, and Amelie SGD converges even if there is no similarity of functions.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 (11) that we get for the nonconvex case, in the nonsmooth convex case, we get (20). Thus, we will getΘ M 2 R 2 ε 2 min j∈[n] t * ( σ 2 /M 2 , . . . ) instead of Θ L∆ ε min j∈[n] t * ( σ 2 /ε, . . . ) .The same idea applies to the smooth convex case. In the convex setting, we need the following assumptions.Assumption 4. The function f is convex and attains a minimum at some pointx * ∈ R d . Assumption 5. The function f is M -Lipschitz, i.e., |f (x) -f (y)| ≤ M ∥x -y∥ , ∀x, y ∈ R d for some M ∈ (0, ∞].Assumption 6. For all x ∈ R d , stochastic (sub)gradients ∇f (x; ξ) are unbiased and are σ 2 -variancebounded, i.e., E ξ∼D [∇f (x; ξ)] ∈ ∂f (x) and E ξ∼D ∥∇f (x; ξ) -E ξ∼D [∇f (x; ξ)]∥ 2 ≤ σ 2 , where σ 2 ≥ 0.Theorem 10. Let Assumptions 4, 5 and 6 hold. Choose any ε > 0. Let us take the batch sizeS = max σ 2 /M 2 , 1 , stepsize γ = ε M 2 +σ 2 /S ∈ ε 2M 2 , ε M 2 , any pivot worker j * ∈ [n], and any spanning trees st and st bc in Algorithm 2. Then afterK ≥ 2M 2 R 2 /ε 2 iterations the method guarantees E f ( x K ) -f (x * ) ≤ ε, where x K = 1 K K-1 k=0 x k and R = x * -x 0 .Proof. The proof of Theorem 10 is almost the same as in Theorem 4 (see Section G). The proof of Theorem 4 states that the steps of Fragile SGD are equivalent to the classical SGD method. Thus, we can use the classical result from the literature (Lan, 2020) . Using Theorem 22, we getE f ( x K ) -f (x * ) ≤ ε if K ≥ 2M 2 x * -x 0 2 ε 2 ≥ (M 2 + σ 2 S ) x * -x 0 2 ε 2 for the stepsize γ = ε M 2 + σ 2 S ∈ ε 2M 2 , ε M 2 ,where we use the fact that S ≥ σ 2 /M 2 .Theorem 11. Consider the assumptions and the parameters from Theorem 10. For any pivot worker j * ∈ [n] and spanning trees st and st bc , Algorithm 2 converges after at mostEQUATIONseconds, where µ i→j * (µ j * →i ) is an upper bound on times required to send a vector from worker i to worker j * (from worker j * to worker i) along the spanning tree st (spanning tree st bc ).Proof. The proof is identical to the proof of Theorem 5.Corollary 3. Consider the assumptions and the parameters from Theorem 11. Let us take a pivot worker j * = arg min j∈[n] t * ( σ 2 /M 2 , [h i ] n i=1 , [τ i→j + τ j→i ] n i=1), and a spanning tree st (spanning tree st bc ) that connects every worker i to worker j * (worker j * to every worker i) with the shortest distance τ i→j * (τ j * →i ). Then Algorithm 2 converges after at mostEQUATIONseconds.In the homogeneous and smooth case, we will slightly modify Fragile SGD. Instead of Line 8 of Algorithm 3, we use the following steps:γ k+1 = γ • (k + 1), α k+1 = 2/(k + 2) y k+1 = (1 -α k+1 )x k + α k+1 u k , (u 0 = x 0 ) u k+1 = u k - γ k+1 s k g k , x k+1 = (1 -α k+1 )x k + α k+1 u k+1 . (21)We will call such a method the Accelerated Fragile SGD method. The idea is to use the acceleration technique from (Lan, 2020) (which is based on (Nesterov, 1983) ).Theorem 12. Let Assumptions 4, 1 and 3 hold. Choose any ε > 0. Let us take the batch sizeS = max (σ 2 R)/(ε 3/2 √ L) , 1 , γ = min 1 4L , 3R 2 S 4σ 2 (K+1)(K+2) 2 1/2, any pivot worker j * , and any spanning trees st and st bc in Accelerated Method 2 (Accelerated Fragile SGD), then afterK ≥ 8 √ LR √ ε iterations the method guarantees that E f (x K ) -f (x * ) ≤ ε, where R = x * -x 0 .Proof. Using the same reasoning as in Theorem 4, 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γ = min 1 4L , 3R 2 S 4σ 2 (K + 1)(K + 2) 2 1/2 , we have E f (x K ) -f (x * ) ≤ 4LR 2 K 2 + 4 √ σ 2 R 2 √ SK .Therefore,E f (x K ) -f (x * ) ≤ ε if K ≥ 8 √ LR √ ε ≥ 8 max √ LR √ ε , σ 2 R 2 ε 2 S ,where we use 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 st bc , Accelerated Algorithm 2 (Accelerated Fragile SGD) converges after at mostΘ √ LR √ ε t * σ 2 R ε 3/2 √ L , [h i ] n i=1 , [µ i→j * + µ j * →i ] n i=1 (22)seconds, where µ i→j * (µ j * →i ) is an upper bound on times required to send a vector from worker i to worker j * (from worker j * to worker i) along the spanning tree st (spanning tree st bc ).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 pivot worker j * = arg min j∈[n] t * σ 2 R ε 3/2 √ L , [h i ] n i=1 , [τ i→j + τ j→i ] n i=1, and a spanning tree st (spanning tree st bc ) that connects every worker i to worker j * (worker j * to every worker i) with the shortest distance τ i→j * (τ j * →i ). Then Accelerated Algorithm 2 (Accelerated Fragile SGD) converges after at mostEQUATIONseconds.Consider the optimization problem (17). Theorem 14. Let Assumptions 4, 5 hold for the function f and Assumption 6 holds for the functions f i for all i ∈ [n]. Choose any ε > 0. Let us take the batch sizeS = max σ 2 /M 2 , n , γ = ε M 2 +σ 2 /S ∈ ε 2M 2 , εM 2 , any pivot worker j * ∈ [n], and any spanning trees st and st bc , in Algorithm 5, then afterK ≥ 2M 2 R 2 /ε 2 iterations the method guarantees that E f ( x K ) -f (x * ) ≤ ε, where x K = 1 K K-1 k=0 x k and R = x * -x 0 .Proof. The proof of Theorem 14 is almost the same as in Theorems 8 (see Section H). The proof of Theorem 8 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 getE f ( x K ) -f (x * ) ≤ ε if K ≥ 2M 2 x * -x 0 2 ε 2 ≥ (M 2 + σ 2 S ) x * -x 0 2 ε 2 for the stepsize γ = ε M 2 + σ 2 S ∈ ε 2M 2 , ε M 2 ,where we use the fact that S ≥ σ 2 /M 2 .Theorem 15. Consider the assumptions and the parameters from Theorem 14. For any pivot worker j * ∈ [n] and any spanning trees st and st bc , Algorithm 5 converges after at mostΘ M 2 R 2 ε 2 max max i,j∈[n] µ i→j , max i∈[n] h i , σ 2 nM 2 1 n n i=1 h i (24)seconds, where µ k i→j * (µ k j * →i ) is an upper bound on times required to send a vector from worker i to worker j * (worker j * to worker i) along the spanning tree st (spanning tree st bc ) for all i ∈ [n].Proof. The proof is identical to the proof of Theorem 9.Corollary 5. Consider the assumptions and the parameters from Theorem 15. Let us take any pivot worker j * ∈ [n] and a spanning tree st (spanning tree st bc ) that connects every worker i to worker j * (worker j * to worker i) with the shortest distance τ i→j * (τ j * →i ), then Algorithm 5 converges after at mostΘ M 2 R 2 ε 2 max max i,j∈[n] τ i→j , max i∈[n] h i , σ 2 nM 2 1 n n i=1 h i seconds.Consider the optimization problem (17). In this section, we use the same idea as in Section D.3. We will modify Amelie SGD and, instead of Line 9 from Algorithm 6, we use the lines (21). We call such a method the Accelerated Amelie SGD method. Theorem 16. Let Assumptions 4 and 1 hold for the function f and Assumption 3 holds for the functions f i . Choose any ε > 0. Let us take the batch sizeS = max (σ 2 R)/(ε 3/2 √ L) , n , γ = min 1 4L , 3R 2 S 4σ 2 (K+1)(K+2) 2 1/2, any pivot worker j * , and any spanning trees st and st bc in Accelerated Method 5 (Accelerated Amelie SGD), then after K ≥ 8√ LR √ ε iterations the method guarantees that E f (x K ) -f (x * ) ≤ ε, where R = x * -x 0 .Proof. Accelerated Amelie SGD is equivalent to the accelerated stochastic gradient method with a mini-batch from Lan (2020) . The proof repeats the proofs of Theorem 12 and Theorem 8.Theorem 17. Consider the assumptions and the parameters from Theorem 16. For any pivot worker j * ∈ [n] and any spanning trees st and st bc , Accelerated Algorithm 5 (Accelerated Amelie SGD) converges after at mostΘ √ LR √ ε max max i,j∈[n] µ i→j , max i∈[n] h i , σ 2 R nε 3/2 √ L 1 n n i=1 h i (25)seconds, where µ k i→j * (µ k j * →i ) is an upper bound on times required to send a vector from worker i to worker j * (worker j * to worker i) along the spanning tree st (spanning tree st bc ) for all i ∈ [n].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 a spanning tree st (spanning tree st bc ) that connects every worker i to worker j * (worker j * to worker i) with the shortest distance τ i→j * (τ j * →i ), then Accelerated Algorithm 5 (Accelerated Amelie SGD) converges after at mostEQUATIONseconds.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, 2023) [Section B], we conjecture that the obtained upper bounds are tight and optimal (up to log factors in the homogeneous case).Let us consider the time complexities ( 20) and ( 23) (accelerated rate) in the homogeneous and convex cases. When τ i→j = 0 for all i, j ∈ [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 τ i→j = 0 for all i, j ∈ [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 i . When σ = 0, the result ( 26) is consistent with the lower bound from (Scaman et al., 2017) . However, when σ > 0, as far as we know, the time complexity ( 26) is new in the convex smooth setting.Protocol 8 Time Multiple Oracles Protocol with Communication1: Input: function f (or functions f i ) computation oracles {O i } n i=1 ∈ O(f ) communication oracles {C p i→j } i∈[n],j∈[n],p≥1 , algorithm {(M k , L k , D k , P k 1 , . . . , P k n , V k 1 , . . . , V k n )} ∞ k=0 ∈ A 2: s h,0 i = s τ,0 i,j,p = 0 for all i, j ∈ [n], p ∈ N 3: for k = 0, . . . , ∞ do 4: (t k+1 , c k+1 ) = M k (g 1 1 , . . . g 1 n , g 2 1 , . . . , g 2 n , . . . , g k 1 , . . . , g k n ) ▷ t k+1 ≥ t k 5:if c k+1 = 0 then 6:i k+1 = L k (g 1 1 , . . . g 1 n , g 2 1 , . . . , g 2 n , . . . , g k 1 , . . . , g k n )7:x k i k+1 = P k i k+1 (g 1 i k+1 , . . . , g k i k+1 ) 8: (s h,k+1 i k+1 , g k+1 i k+1 ) = O i k+1 (t k+1 , x k i k+1 , s h,k i k+1 ) ▷∀j ̸ = i k+1 : s h,k+1 j = s h,k j , g k+1 j = 0 9: else 10: i k+1 , j k+1 , p k+1 = D k (g 1 1 , . . . g 1 n , g 2 1 , . . . , g 2 n , . . . , g k 1 , . . . , g k n )11:v k i k+1 = V k i k+1 (g 1 i k+1 , . . . , g k i k+1 ) 12: (s τ,k+1 i k+1 ,j k+1 ,p k+1 , g k+1 j k+1 ) = C p k+1 i k+1 →j k+1 (t k+1 , v k i k+1 , s τ,k i k+1 ,j k+1 ,p k+1 ) ▷∀j ̸ = j k+1 : g k+1 j = 0, ∀i ̸ = i k+1 , j ̸ = j k+1 , p ̸ = p k+1 : s τ,k+1i,j,p = s τ,k i,j,p , 13:end if 14: end forIn Section 4, we present a brief overview and simplified theorem for the lower bound. We now provide a formal and strict mathematical construction.One way how we can formalize Protocol 1 is to use Protocol 8. Let us explain it. Using Protocol 8, we consider any possible method that works in our distributed asynchronous setting. The mapping M k of the algorithm returns the time t k+1 (ignore for now) and c k+1 . If c k+1 = 0, then the algorithm decides to start the calculation of a stochastic gradient: it determines the index i k+1 of a worker that will start the calculation, then, using all locally available information g 1 i k+1 , . . . , g k i k+1 , it calculates a new point x k i k+1 , and passes this point to the computation oracle O i k+1 that will return a new stochastic gradient after h i k+1 seconds. If c k+1 = 1, then the algorithm decides to communicate a vector: it returns the indices i k+1 and j k+1 of two workers that will communicate, and the index p k+1 ∈ N of a communication oracle, calculates v k i k+1 in worker i k+1 using only all locally available information g 1 i k+1 , . . . , g k i k+1 , and passes it to the communication oracle C p k+1 i k+1 →j k+1 that will send the vector after τ i k+1 →j k+1 seconds.The computation oracles we define asEQUATIONwhere ξ ∼ D.The communication oracles we define asC p i→j : R ≥0 time × R d point × (R ≥0 × R d × {0, 1}) input state → (R ≥0 × R d × {0, 1}) output state ×R d such that C p i→j (t, x, (s t , s x , s q )) =    ((t,x, 1), 0), s q = 0, ((s t , s x , 1), 0), s q = 1, t < s t + τ i→j , ((0, 0, 0), s x ), s q = 1, t ≥ s t + τ i→j .(28)The idea is that the computation oracle ( 27) emulates the behavior of a real worker i that requires h i seconds to calculate a stochastic gradient. The communication oracle emulates the behavior of a real communication channel that requires τ i→j seconds to send a vector from worker i to worker j.One can see that, for all i ̸ = j ∈ [n], an algorithm can access an infinite number of communication oracles C 1 i→j , C 2 i→j , . . . . We allow an algorithm to send as many vectors from worker i to worker j in parallel as it wants.We now discuss the role of t k+1 . One can see that the time t k+1 is returned by the algorithm, and t k+1 is passed to the oracles O i k+1 and C p k+1 i k+1 →j k+1 . Consider that O i k+1 was called with t k+1 for the first time, then it will return zero vector because (s h,k i k+1 ) q = 0 (see ( 27)) at the beginning. Then, by the construction of ( 27), the oracle will return a non-zero vector in the second output if only the algorithm returns a time that is greater or equal to t k+1 + h i k+1 . The same idea applies to C p k+1 i k+1 →j k+1 : if it was called t k+1 for the first time, then worker j k+1 will get a non-zero vector only if the algorithm passes a time that is greater or equal to t k+1 + τ i k+1 →j k+1 .The oracles force the algorithm to increase the time t k+1 ; otherwise, it will not get new information (∇f (s x ; ξ) in ( 27)) about the function. One crucial constraint is t k+1 ≥ t k , 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 we refer to Sections 3-5 for a detailed description. A more readable and less formal version of Protocol 8 is presented in the Protocol 1.Before we state the main theorem, let us define the class of zero-respecting algorithms. Definition 18 (Algorithm Class A zr ). Let us consider Protocol 8. We say that the sequence of tuples of mappings{(M k , L k , D k , P k 1 , . . . , P k n , V k 1 , . . . , V k n )} ∞ k=0 is a zero-respecting algorithm, if 1. M k : R d × • • • × R d n×k times → R ≥0 × {0, 1} for all k ≥ 1, and M 0 ∈ R ≥0 × {0, 1}. 2. L k : R d × • • • × R d n×k times → [n] for all k ≥ 1, and L 0 ∈ [n]. 3. D k : R d × • • • × R d n×k times → [n] × [n] × N for all k ≥ 1, and D 0 ∈ [n] × [n] × N. 4. For all i ∈ [n], P k i : R d × • • • × R d k times → R d for all k ≥ 1, and P 0 i ∈ R d . 5. For all i ∈ [n], V k i : R d × • • • × R d k times → R d for all k ≥ 1, and V 0 i ∈ R d .6. For all k ≥ 1 and g1 1 , . . . g 1 n , g 2 1 , . . . , g 2 n , . . . , g k 1 , . . . , g k n ∈ R d , t k+1 ≥ t k ,where t k+1 and t k are defined as (t k+1 , . . .) = M k (g 1 1 , . . . g 1 n , g 2 1 , . . . , g 2 n , . . . , g k 1 , . . . , g k n ) and (t k , . . . ) = M k-1 (g 1 1 , . . . g 1 n , g 2 1 , . . . , g 2 n , . . . , g k-1 1 , . . . , g k-1 n ).Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes] Justification: Section J Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or 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). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?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 not 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., if there is a special consideration due to laws or regulations in their jurisdiction). 
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 a mathematical problem for machine learning.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or 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.because max i,j∈[n] τi→j ≤ max i∈[n] τi→j * + max i∈[n] τj * →i ≤ 2 max i,j∈[n] τi→j by the triangle inequalityIt is possible that a permutation is not unique, then the result of the mapping does not depend on the choice. 
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

2. 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?
questions: questions: 1. Could you provide empirical results for the proposed methods?

2. Could you provide more discussion about the relationship between the pivot worker and the server?
limitations: limitations: Most limitations are listed in the weaknesses section.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: 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: limitations: I believe the authors have discussed the limitations of their method.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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).

2. 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. 

3. 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.
questions: questions: see weaknesses.
limitations: limitations: see weaknesses.
paper_summary: paper_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.
strength_weakness: strength_weakness: 1. Although the algorithms are interpretable, they may be challenging to implement in practical systems. 

2. There is limited experimental validation of the proposed methods.
questions: questions: I have no questions.
limitations: limitations: Limitations are addressed in the paper (selecting optimal pivot worker)

Comments: title: Official Comment by Authors
Official Comment by Authors
comment: Thank you for addressing my concerns. I will adjust my score accordingly.
We apologize for the additional comment, but we would like to include one more important remark about the paper.

The goal of this paper is to find the *optimal theoretical time complexities*. To do so, we proved the lower bounds (which we believe are overlooked), and we think this is a non-trivial task that required us to develop new proof techniques that we discuss in detail in Sections 4 and D.3. Fragile SGD and Amelie SGD are practical and valid methods that do not violate the restrictions of the decentralized setup, and designed to show that these lower bounds are tight through our theorems. This is the standard approach in optimization (see [1, 2, 3]).

We thank the reviewer for taking part in the discussion.

[1] Nesterov, Y. (2018). Lectures on convex optimization, volume 137. Springer.

[2] Carmon, Y., Duchi, J. C., Hinder, O., and Sidford, A. (2020). Lower bounds for finding stationary points i. Mathematical Programming, 184(1):71–120.

[3] Woodworth, B. E., Wang, J., Smith, A., McMahan, B., and Srebro, N. (2018). Graph oracle models, lower bounds, and gaps for parallel stochastic optimization. Advances in Neural Information Processing Systems, 31.
Thank you for raising the score and for the respond.

Let us clarify the role of the pivot worker. 

i)

> For instance, if there are six workers in total, the pivot worker needs to broadcast to the other five workers and receive $g^k$ from them, which significantly increases its communication overhead compared to the other workers.

It largely depends on the structure of a multigraph. If we consider the Line graph (Section 6) or the ND-Mesh (Section A.1), then it is *not* true that the pivot worker has to send vectors to all other workers. Consider Figure 3.a with the 2D-Mesh graph. In this picture, worker $13$ is a pivot worker. During the broadcasting operation, worker 13 sends a vector to workers $8, 12, 18, 14,$ then worker $8$ sends this vector to workers $7, 3, 9,$ worker $12$ sends to workers $17, 11, 7,$ and so on. It's a sequential process where everyone has a comparable load (the pivot worker sends to four workers, while other workers send to three workers). The same reasoning applies when the workers send stochastic gradients to the pivot worker; all workers send almost the same amount of information per second in the Line and the ND-Mesh graphs.

ii) 
> Additionally, the pivot worker runs two parallel processes, and if either of these processes experiences a delay or other system issue, the entire framework could be delayed. 

Processes $0$ and $j^*$ from Algorithms 3 and 4 are *mathematical abstractions*. In a real implementation, it is possible to merge Process 0 and Process $j^*$ in a way that we move the logic from Process 0 to "function ReceiveVectorsFromPreviousWorkers" of Process $j^*.$ This approach allows us to eliminate the additional process in the pivot worker. In the paper, we decided to split the logic into two processes to enhance readability.

Moreover, note that in real systems, when computers run gradient computations (e.g., with CUDA) and communicate vectors (e.g., via TCP or another standard), the number of running processes can be dozens. So, adding one more running process/thread is a negligible price (which we can avoid using the approach that we described in the previous paragraph).

In total, we only require the pivot worker to run one extra sum operation of two vectors, which is negligible compared to stochastic gradient computations, where workers should run matrix multiplications, activations (sigmoid, ReLU, ....), convolutions, and other operations, which are clearly more complicated.

iii)

Consider the Star graph from Section A.2, where $n$ workers are only connected to one worker in the center (in total, $n + 1$ workers). In this case, the central worker can be a pivot worker. Indeed, in this scenario, the pivot/central worker sends and receives more information per second than other workers. But it's not a problem with our method; it's a problem with the setting. Any other reasonable method in this setting will require the pivot/central worker to work more in order to get fast convergence. For instance, if the pivot/central worker does not send and receive information from another worker, this is counterproductive. This other worker either will be idle or its computations will be ignored.

Thank you for the response. We hope that we've clarified your last question. If you have more, please let us know.
Thanks to the authors for the rebuttal. The authors have mostly addressed my concerns in this paper, particularly regarding the experimental verification. I have raised my score. However, I still have a question about the pivot worker. If we consider that the pivot worker runs an extra aggregation process, this process seems very similar to the traditional aggregation process used in centralized methods. For instance, if there are six workers in total, the pivot worker needs to broadcast to the other five workers and receive $g^k$ from them, which significantly increases its communication overhead compared to the other workers. Additionally, the pivot worker runs two parallel processes, and if either of these processes experiences a delay or other system issue, the entire framework could be delayed. Therefore, I believe the proposed framework implicitly assumes that the pivot worker has significantly greater computational and communication capabilities.
Thanks for the response.
Thanks for the explanation. I do not have any more questions.