Shadowheart SGD: Distributed Asynchronous SGD with Optimal Time Complexity Under Arbitrary Computation and Communication Heterogeneity

Authors: alexander tyurin kaust
marta  pozzi
ivan ilin kaust
peter richtárik kaust
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-08 10:05:12

Abstract: We consider nonconvex stochastic optimization problems in the asynchronous centralized distributed setup where the communication times from workers to a server can not be ignored, and the computation and communication times are potentially different for all workers. Using an unbiassed compression technique, we develop a new method—Shadowheart SGD—that provably improves the time complexities of all previous centralized methods. Moreover, we show that the time complexity of Shadowheart SGD is optimal in the family of centralized methods with compressed communication. We also consider the bidirectional setup, where broadcasting from the server to the workers is non-negligible, and develop a corresponding method.

Main paper: 
 introduction: 
 We consider the nonconvex smooth optimization problemEQUATIONwhere f (•; •) : R d × S ξ → R, and D ξ is a distribution on S ξ ̸ = ∅. Given ε > 0, we seek to find a possibility random point x such that E[∥∇f (x)∥ 2 ] ≤ ε. Such a point x is called an ε-stationary point. We focus on solving the problem in the following setup:(a) n workers/nodes are able to compute stochastic gradients ∇f (x; ξ) of f, in parallel and asynchronously, and it takes (at most) h i seconds for worker i to compute a single stochastic gradient;(b) the workers are connected to a server which acts as a communication hub;(c) the workers can communicate with the server in parallel and asynchronously; it takes (at most) τ i seconds for worker i to send a compressed message to the server; compression is performed via applying lossy communication compression to the communicated message (a vector from R d ); see Def. 2.1;(d) the server can broadcast compressed vectors to the workers in (at most) τ serv seconds; compression is performed via applying a lossy communication compression operator to the communicated message (a vector from R d ); see Def. A.1.The main goal of this work is to find an optimal optimization strategy/method that would work uniformly well in all scenarios characterized by the values of the computation times h 1 , . . . , h n and Table 1 : Time Complexities of Centralized Distributed Algorithms. Assume that it takes at most h i seconds to worker i to calculate a stochastic gradient and τi seconds to send one coordinate/float to server. Abbreviations: L = smoothness constant, ε = error tolerance, ∆ = f (x 0 ) -f * , n = # of workers, d = dimension of the problem. We take the RandK compressor with K = 1 (Def. D.1) (as an example) in QSGD and Shadowheart SGD. Due to Property 6.2, the choice K = 1 is optimal for Shadowheart SGD up to a constant factor.Time Complexity Time Complexities in Some Regimes max{hn, τn} → ∞, max{hi, τi} < ∞ ∀i < n (the last worker is slow)hi = h, τi = τ ∀i ∈ [n] (equal performance)Numerical Comparison (b) σ 2/ε = 1 10 3 10 6Minibatch SGD (see ( 2)) maxi∈[n] max{hi, d τi} L∆ ε + σ 2 L∆ nε2 ∞ (non-robust) max{h, d τ , d τ σ 2 nε , hσ 2 nε } L∆ ε(worse, e.g., when τ , d or n large)×10 3 ×10 3 ×10 4QSGD (see ( 5)) (Alistarh et al., 2017 ) (Khaled and Richtárik, 2020) max i∈ [n] max{hi, τi}d n + 1 L∆ ε + dσ 2 L∆ nε2 ∞ (non-robust) ≥ dhσ 2 nε L∆ ε(worse, e.g., when ε small) ×3 ×10 2 ×10 4Rennala SGD (Tyurin and Richtárik, 2023c) ,Asynchronous SGD (e.g., (Mishchenko et al., 2022) )≥ min j∈[n] max hπ j , d τπ j , σ 2 ε j i=1 1 hπ i -1 L∆ ε (a) < ∞ (robust) ≥ max h, d τ , hσ 2 nε L∆ ε(worse, e.g., when τ , d or n large)×10 2 ×10 ×1.5Shadowheart SGD (see (9) and Alg. 1) (Corollary 4.3)t * (d -1, σ 2 /ε, [hi, τi] n 1 ) L∆ ε (c) < ∞ (robust) max h, τ , d τ n , d τ hσ2 nε , hσ 2 nε L∆ ε ×1 ×1 ×1Lower Bound (see Section 5 and Theorem O.5)t * (d -1, σ 2 /ε, [hi, τi] n 1 ) L∆ ε (d) - - - - -The time complexity of Shadowheart SGD is not worse than the time complexity of the competing centralized methods, and is strictly better in many regimes (see Section 7.1). We show that (10) is the optimal time complexity in the family of centralized methods with compression (see Section 5 and Theorem O.5). (a) Upper bound time complexities are not derived for Rennala SGD and Asynchronous SGD. However, we can derive the lower bound using Theorem O.5 with ω = 0. One should take d τi instead of τi when apply Theorem O.5 because these methods send d coordinates. π is a permutation that sorts max{hi, d τi} : max{hπ 1 , d τπ1 } ≤ • • • ≤ max{hπ n , d τπn } (b) We numerically compute time complexities for d = 10 6 , n = 10 3 , hi ∼ U (0.1, 1), τi ∼ U (0.1, 1) (uniform i.i.d.), and three noise regimes σ 2 /ε ∈ {1, 10 3 , 10 6 }. We report the factors by which the time complexities of the competing methods are worse compared to the time complexity of our method Shadowheart SGD. So, for example, Minibatch SGD, QSGD and Asynchronous SGD can be worse by the factors ×10 4 , ×10 4 , and ×10 2 , respectively. (c) The mapping t * is defined in Def. 3.1. (d) The lower bound constructed with the RandK compressor and the dimension d = Θ (L∆/ε) .communication times τ 1 , . . . , τ n and τ serv . Since we allow these times to be arbitrarily heterogeneous, designing a single algorithm that would be optimal in all these scenarios seems challenging.Let us clarify what we mean by {τ i } and take, for instance, the RandK compressor (see Def. D.1 and Sec. 2.2) (sends K random entries). Then τ i is # of seconds required to send K coordinates of a vector. Now assume that the communication is proportional to the number of coordinates/bits that a worker sends, i.e., it takes τi seconds to send a one coordinate/bit. Then, clearly, we have τ i = K × τi . and, τ i is a function of K. While the dependence is clear for RandK, for all possible compressors, the dependence on the amount of sent information can be less nontrivial. We generally fix an arbitrary unbiased compressor and assume it takes τ i seconds to send the compressed message.From the viewpoint of federated learning (Konečný et al., 2016; Kairouz et al., 2021) , our work is a theoretical study of device heterogeneity. Moreover, our formalism captures both cross-silo and cross-device settings as special cases. Due to our in-depth focus on device heterogeneity and the challenges that need to be overcome, we do not consider statistical heterogeneity, and leave an extension to this setup to future work.We rely on assumptions which are standard in the literature on stochastic gradient methods: smoothness, lower-boundedness and bounded variance. Assumption 1.1. f is differentiable & L-smooth, i.e., ∥∇f (x) -∇f (y)∥ ≤ L ∥x -y∥, ∀x, y ∈ R d .Assumption 1.2. There exist f * ∈ R such that f (x) ≥ f * for all x ∈ R d . We define ∆ := f (x 0 ) -f * , where x 0 ∈ R d is a starting point of all algorithms we consider.Assumption 1.3. For all x ∈ R d , the stochastic gradients ∇f (x; ξ) are unbiased, and their variance is bounded by σ 2 ≥ 0, i.e., E ξ [∇f (x; ξ)] = ∇f (x) and E ξ [∥∇f (x; ξ) -∇f (x)∥ 2 ] ≤ σ 2 .To simplify the exposition, in what follows we first focus on the regime in which the broadcast cost can be ignored. We describe a strategy for extending our algorithm to the more general regime in Sec. A.2 Related Work 
communication time can be ignored: 
 We now briefly review related work and important concepts. Consider the regime when the communication cost is negligible (τ i = 0 for all i), and the computation times h i are arbitrary but fixed. It is well-known that under Assumptions 1.1, 1.2, and 1.3, the vanilla SGD method x k+1 = x k -γ∇f (x k ; ξ k ), where x 0 ∈ R d is a starting point, and γ > 0 is the step size, solves (1) using the optimal number of stochastic gradients (Ghadimi and Lan, 2013; Arjevani et al., 2022) . Since the # of iterations of SGD to get an ε-stationary point is O L∆ /ε + σ 2 L∆ /ε 2 , SGD run on a single worker whose computation time is h 1 seconds would have time complexity O h 1 × L∆ /ε + σ 2 L∆ /ε 2 seconds. The time complexity of Minibatch SGD with n workers, i.e.,EQUATIONcan be shown (Gower et al., 2019) to beEQUATION)where h max := max i∈[n] h i , where [n] denotes {1, . . . , n}. The dependence on h max is due to Minibatch SGD employing synchronous parallelism which forces it to wait for the slowest worker.While the stochastic part of (3) can be n times smaller than in the single worker case, (3) does not guarantee an improvement since h max can be arbitrarily large. In real systems, computation times can be very heterogeneous and vary in time in chaotic ways (Dutta et al., 2018; Chen et al., 2016) .Recently, Cohen et al. (2021) ; Mishchenko et al. (2022) and Koloskova et al. (2022) showed that it is possible to improve upon (3) using the celebrated Asynchronous SGD method (Recht et al., 2011; Feyzmahdavian et al., 2016; Nguyen et al., 2018) and get the time complexity O(( 1 /n n i=11 hi ) -1 × L∆ /ε + σ 2 L∆ /nε 2 ), which improves the dependence from h max to the harmonic mean of the computation times. Subsequently, Tyurin and Richtárik (2023c) developed the Rennala SGD method whose time complexity isEQUATION)where π is a permutation forwhich h π1 ≤ • • • ≤ h πn . They also showed that the time complexity ( 4) is optimal by providing a matching lower bound.In many practical scenarios, communication times can be the main bottleneck, and can not be ignored, e.g., in distributed/federated training of machine learning models (Ramesh et al., 2021; Kairouz et al., 2021; Wang et al., 2023) . There are two main techniques for reducing the communication bottleneck: local training steps (McMahan et al., 2017) and compressed communication (Seide et al., 2014; Alistarh et al., 2017) . In our work, we investigate the latter technique. In particular, efficient methods with compressed communication such as DIANA (Mishchenko et al., 2019) , Accelerated DIANA (Li et al., 2020) , MARINA (Gorbunov et al., 2021) and DASHA (Tyurin and Richtárik, 2023b) employ unbiased compressors, defined next. Assume that S ν is a nonempty arbitrary set of samples, and D ν is a distribution on S ν . Definition 2.1. A mapping C : R d × S ν → R d is an unbiased compressor if there exists ω ≥ 0 such that E ν [C(x; ν)] = x, E ν [∥C(x; ν) -x∥ 2 ] ≤ ω ∥x∥ 2 for all x. Let U(ω) denote the family of such compressors5 . Assumption 2.2. Samples from D ξ and D ν are mutually independent.The canonical example of an unbiased compressor is the RandK compressor (see Def. D.1) that scales K random entries of the input vector x by d /K and zeros out the rest. Many more examples of unbiased compressors are considered in the literature (Beznosikov et al., 2020; Xu et al., 2021a; Horváth et al., 2022) . One of the most straightforward methods which use compression is QSGD6 (Alistarh et al., 2017) :EQUATIONwhere each worker calculates one stochastic gradient, compresses it using C i ∈ U(ω) drawn independently, and sends it to the server. The server aggregates the compressed vectors and performs step (5). With a proper stepsize choice γ, QSGD converges after O ( ω /n + 1) × L∆ /ε + (ω + 1) × σ 2 L∆ /nε 2 iterations7 (Khaled and Richtárik, 2020 ). Let's assume it takes τ i seconds for worker i to send one compressed vector to the server. Since the workers act in parallel, the time complexity of QSGD isEQUATION)We can go through a similar exercise with any other method that uses compressed communication (e.g., (Tyurin and Richtárik, 2023a; Gauthier et al., 2023; Jia et al., 2023) ). Nevertheless, as far as we know, the optimal time complexities for asynchronous centralized distributed optimization with communication compression are not known.Ĉi = O C,D C i τi, we consider the sequence {S m,j } ∞ j=1 , where S m,j is a uniform random variable drawn in j th call of g(s x ; ξ) in the m th worker in Line 7 of Protocol 9.Let us define the following useful random variables based on previous definitions. We define 2. For all m ∈ [n], j ≥ 1, b µ m,j ∈ N ∪ {∞} is the first index of the sequence {S m,j } ∞ j=1 that started calculating in (55) in the compression oracle Ĉm in or after the iteration k(j -1).EQUATION 
summary of contributions: 
 In the regime in which the communication time can be ignored (see Sec. 2.1), Tyurin and Richtárik (2023c) showed that (4) is the optimal time complexity. In this work we endeavor to take the next step: we wish to understand the fundamental limits of the regime in which communication time is a factor. Our main contributions are: ♠ We develop a new method-Shadowheart SGD (Algorithm 1)-that guarantees to find an ε-stationary point of problem (1) with time complexity T * given in (10) . While the general expression we give for T * is hard to parse since it involves the equilibrium time t * (•) whose definition is implicit (see Def. 3.1), we show (see Sec. 7) that T * is not worse than the time complexity of known centralized8 methods, and also who that it can be strictly better in many regimes, even by many degrees of magnitude (see Sec. 7.1 and Table 1 ). ♣ In Sec. 5 we show that (10) is the optimal time complexity in the family of centralized methods with compression. This is the first such result in the literature. ♦ We also developed Adaptive Shadowheart SGD (Sec. 4.2 and M), which does not require the knowledge of the computation and communication times and can work with arbitrary changing times. Moreover, we designed Bidirectional Shadowheart SGD (Sec. A), which works in the regime when broadcast cost not negligible as well.♥ Our theoretical study of Shadowheart SGD is supported by judiciously designed synthetic experiments and machine-learning experiments with logistic regression; see Sec. Q.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 O.5. Let us consider Protocol 9. We take any h i > 0, τ i > 0 for all i ∈ [n], ω ≥ 0, L, ∆, ε, σ 2 > 0 such that ε < c 1 L∆ and ω + 1 ≤ T,13 where T = ∆L c2ε is the dimension of the construction. For any algorithm A ∈ A zr , there exists a function f ∈ F ∆,L , computation oracles(O 1 , . . . , O n ) ∈ O σ 2h1,...,hn (f ), and communication oracles ( Ĉ1 , . . . , Ĉn ) ∈ U ω τ1,...,τn ,14 such thatE inf k∈St ∇f (x k ) 2 > ε, where S t := k ∈ N 0 | t k ≤ t and t = c 3 × L∆ ε × t * (ω, σ 2 /ε, h 1 , τ 1 , . . . , h n , τ n ).The quantities c 1 , c 2 , and c 3 are universal constants. The sequences x k and t k are defined in Protocol 9.Proof.Without loss of generality, we assume that the workers are sorted bymax{h i , τ i } : max{h 1 , τ 1 } ≤ • • • ≤ max{h n , τ n }. (Step 1: f ∈ F ∆,L ) Let us fix λ > 0 and take the function f (x) := Lλ 2 l1 F T x λ, where the function F T is defined in Sec. P.1. Tyurin and Richtárik (2023c) [Sec. D.2, Proof of Thm. 6.4] show that the function f is L-smooth and f (0) -inf x∈R T f (x) ≤ ∆ if T = ∆l 1 Lλ 2 ∆ 0 .Thus, we have f ∈ F ∆,L .(Step 2: Oracle Class) Let us construct a stochastic gradient mapping. For our lower bound, we take[∇f (x; ξ)] j := ∇ j f (x) 1 + 1 [j > prog(x)] ξ p -1 ∀x ∈ R T ,andD ∇f i = Bernoulli(p) for all i ∈ [n], where p ∈ (0, 1]. We denote [x] j as the j th index of a vector x ∈ R T . Let us takep = min L 2 λ 2 γ 2 ∞ σ 2 l 2 1 , 1 .Then Tyurin and Richtárik (2023c)[Sec. D.2, Proof of Thm. 6.4] show that this mapping is unbiased and σ 2 -variance-bounded.(Step 3: Compression Operator) In our construction, we take the RandK compressor (outputs K random values of an input vector without replacement, scaled by T /K (Def. D.1)). From Theorem D.2, we know that C is unbiased and T K -1-variance bounded, i.e.,E S [C(x; S)] = x, E S ∥C(x; S) -x∥ 2 ≤ T K -1 ∥x∥ 2 , ∀x ∈ R T ,where[C(x; S)] j := T K x j , j ∈ S, 0, j ̸ ∈ S, ∀j ∈ [T ].and S is an uniformly random subset of [T ] without replacement. It is sufficient to take K = T ω+1 to ensure that C ∈ U(ω). Let us define p ω := K T . We take mutually independent distributions D C i that generate random subsets S described above.(Step 4: Analysis of Protocol) Let us take Protocol 9 generates the sequence {x k } ∞ k=0 . We haveλ = √ 2εl 1 L to ensure that ∥∇f (x)∥ 2 = L 2 λ 2 l 2 1 ∇F T ( x λ ) 2 > 2ε1 [prog(x) < T ] for all x ∈ R T ,EQUATIONUsing Lemma P.2 with δ = 1/2 and (58), we obtainE inf k∈St ∇f (x k ) 2 ≥ 2εP inf k∈St 1 prog(x k ) < T ≥ 1 > ε for t ≤ 1 48 t * T K , max σ 2 2εγ 2 ∞ , 1 , h 1 , τ 1 , . . . , h n , τ n ∆L 8εl 1 ∆ 0 -1 .By the assumption of the theorem, we have ω + 1 ≤ T. Therefore, we get the series of inequalities:T K = T T ω+1≥ ω + 1 2 and, using Properties 6.1 and E.1, we havet * T K , max σ 2 2εγ 2 ∞ , 1 , h 1 , τ 1 , . . . , h n , τ n ≥ t * ω + 1 2 , max σ 2 2εγ 2 ∞ , 1 , h 1 , τ 1 , . . . , h n , τ n ≥ t * 1 2γ 2 ∞ × ω, 1 2γ 2 ∞ × σ 2 ε , h 1 , τ 1 , . . . , h n , τ n ≥ 1 2γ 2 ∞ × t * ω, σ 2 /ε, h 1 , τ 1 , . . . , h n , τ n ,Thus, we can taket = 1 48 × 1 2γ 2 ∞ × t * ω, σ 2 /ε, h 1 , τ 1 , . . . , h n , τ n ∆L 8εl 1 ∆ 0 -1 .P.1.1 Proof of Lemma P.2 Lemma P.2. Let us fix T, T ′ ∈ N such that T ≤ T ′ , consider Protocol 9 with an algorithm A ∈ A zr , a differentiable function f : R T ′ → R such that prog(∇f (x)) ≤ prog(x)+1 for all x ∈ domain(f ).1. We take stochastic oracles O i = O ∇f ,D ∇f i hi with the distributions D ∇f i = Bernoulli(p σ ), p σ ∈ (0, 1], h i > 0, and the mappingsEQUATION2. We take compression oracles Ĉi = O C,D C i τi with the distributions D C i = uniform(K, T ′ ) (= "uniformly random subset of [T ′ ] of the size K without replacement") and the mappingsEQUATIONτ i > 0. We define p ω := K T ′ . We assume that the workers are sorted by max{h m , τ m } : max{h 1 , τ 1 } ≤ • • • ≤ max{h n , τ n }. With probability not less than 1 -δ, the following inequality holds:inf k∈St 1 prog(x k ) < T ≥ 1 for t ≤ 1 48 t * ( 1 /pω, 1 /pσ, h 1 , τ 1 , . . . , h n , τ n ) T 2 + log δ ,where S t := k ∈ N 0 | t k ≤ t , the iterates t k and x k are defined in Protocol 9, and t * is the equilibrium time from Def. 3.1.Proof.(Part 1): The Construction of Random Variables.Let us fix t ≥ 0 and define the smallest index k(i) of the sequence when the progress prog(x k(i) ) equals i :k(i) := inf k ∈ N 0 | i = prog(x k ) ∈ N 0 ∪ {∞}.If inf k∈St 1 prog(x k ) < 1 < 1 holds, then exists k ∈ S t such that prog(x k ) = 1, thus, by the definition of k(1), t k(1) ≤ t k ≤ t, and k(1) < ∞. Note that t k(1) is the smallest time when we make progress to the 1 th (first) coordinate.Since x 0 = 0 and A is a zero-respecting algorithm, the algorithm can return a vector x k with a non-zero first coordinate only if some of returned by the stochastic gradients oracles and compression oracles have the first coordinate not equal to zero. The oracles O i and Ĉi are constructed in such a way (see ( 59) and ( 60)) that they zero out a coordinate based on i.i.d. bernoulli and uniform trials. According to Protocol 9, even if a stochastic oracle returns a non-zero coordinate, it would not mean that the server will get a non-zero coordinate because a subsequent compression oracle also has to return a non-zero coordinate.Every time when the oracle (55) evaluates g(s x ; ξ), it draws i.i.d. random variables ξ ∼ D. Let us enumerate them:1. For the stochastic/computation oraclesO i = O ∇f ,D ∇f i hi, we consider the sequence {ξ m,j } ∞ j=1 , where ξ m,j is a bernoulli random variable drawn in j th call of g(s x ; ξ) in the m th worker in Line 5 of Protocol 9.m ∈ [n], j ≥ 1, if b η m,j = ∞, then e η m,j = ∞. For all m ∈ [n], j ≥ 1, if b η m,j < ∞, then e η m,j ∈ N ∪ {∞}is the first index of the sequence {ξ m,j } ∞ j=1 that started calculating in (55) in the stochastic oracle O m in or after the iteration k(j -1) and the first moment when ξ m,(i+b η m,j -1) = 1 for some i ≥ 1. 
development of shadowheart sgd: 
 Our method bears some resemblance to Rennala SGD (Tyurin and Richtárik, 2023c) and QSGD (Alistarh et al., 2017) , and involves some additional algorithmic elements which play a key role. First, we adopted the main suggestion of Tyurin and Richtárik (2023c)[Sec.7] behind the design of Rennala SGD that an optimal method should calculate stochastic gradients at the last iterate. Second, QSGD served as an inspiration for how to perform gradient compression. In particular, Shadowheart SGD has the form x k+1 = x k -γg k , whereEQUATIONIn Shadowheart SGD, worker i calculates b i stochastic gradients, adds them up to form bi l=1 ∇f (x k ; ξ k il ), and compresses the result m i times using independently drawn compressors. The compressed messages are sent to the server. The first non-trivial step in the design of our method is the presence of weights w i : the server aggregates the n i=1 m i compressed messages across all workers by performing a conic combination with coefficient wi n i=1 wimibi for messages coming from worker i. One can easily show that ( 9) is equivalent to Alg. 1. Note that we recover QSGD (see ( 5)) as a special (suboptimal) case withw i = b i = m i = 1 for all i ∈ [n]. Algorithm 1 Shadowheart SGD 1: Input: starting point x 0 ∈ R d , stepsize γ > 0, ratio σ 2 /ε, computation times h i > 0, and communication times τ i > 0 for i ∈ [n] 2: Find equilibrium time t * using Def. 3.1 3: Set b i = t * hi and m i = t * τi for all i ∈ [n] 4: Find S A = {i ∈ [n] : b i ∧ m i > 0} 5: for k = 0, 1, . . . , K -1 do 6: Run Alg. 2 in active workers S A 7: Broadcast x k , b i , m i to active workers S A 8: Initialize g k = 0 9: for i ∈ S A in parallel do 10: w i (a) = b i ω + ω σ 2 ε + m i σ 2 ε -111:for j = 1, . . . , m i do 12:Receive C ij g k i from worker i 13:g k = g k + w i C ij g k i 14:end for 15:end for 16:g k = g k / ( n i=1 w i m i b i )17:x k+1 = x k -γg k 18: end for Algorithm 2 Strategy of Worker i 1: Receive x k , b i , m i from server, init g k i = 0 2: for l = 1, . . . , b i do 3: Calculate ∇f (x k ; ξ k il ), ξ k il ∼ D ξ 4: g k i = g k i + ∇f (x k ; ξ k il ) 5: end for 6: for j = 1, . . . , m i do 7: Send C ij g k i ≡ C g k i ; ν k ij to server, ν k ij ∼ D ν , C ij ∈ U(ω) 8: end for Definition 3.1 (Equilibrium Time). A mapping t * : R ≥0 ω × R ≥0 σ 2 /ε × (R ≥0 × R ≥0 ) (h1,τ1) × • • • × (R ≥0 × R ≥0 ) (hn,τn) → R ≥0 with inputs ω, σ 2 /ε, h 1 , τ 1 , . . . , h n , τ n is called the equilibrium time if it is defined as follows.Find a permutation a π that sorts the pairs(h i , τ i ) as max{h π1 , τ π1 } ≤ • • • ≤ max{h πn , τ πn } and find the solution s * (j) ∈ [0, ∞] in s of b j i=1 1 2τπ i ω+ 4τπ i hπ i σ 2 ω s×ε + 2hπ i σ 2 ε -1 = s (7) for all j ∈ [n].Then the mapping returns the valuet * (ω, σ 2 /ε, h 1 , τ 1 , . . . , h n , τ n ) ≡ min j∈[n] max{max{h πj , τ πj }, s * (j)} ∈ [0, ∞]. (8) We shall use the short notation t * (ω, σ 2 /ε, [h i , τ i ] n 1 ).a It is possible that a permutation is not unique. The result of the mapping does not depend on the choice of the permutation. See the proof of Property 4.1.b For convenience, we use the projectively extended real line and define 1/0 = ∞.(a) : If ω = 0 and σ 2 ε = 0, then w i = 1The weights {w i } are chosen so as to minimize the variance in the proof of Lemma H.1. However, we still need to find the right values for b i and m i . Since the computation and communication times of worker i are h i and τ i , respectively, the following strategy makes intuitive sense: the server sets some time budget t for all workers, and each worker then calculates ⌊ t /hi⌋ stochastic gradients and sends ⌊ t /τi⌋ compressed vectors to the server. But what is the right way to choose t? If t is too small, then, intuitively, some workers may not have time to calculate "enough" gradients, or may even not have time to send any messages to the server. On the other hand, if t is too large, then the workers will eventually send information of diminishing utility which will not be worth the extra time this takes.We find out that, and this one of the key insights of our work, that there exists an optimal time budget t * which depends on the quantities ω, σ 2 /ε, h 1 , τ 1 , . . . , h n , τ n , for which we coin the name equilibrium time; see Def. 3.1. Admittedly, the definition of the equilibrium time is implicit; we do not know if it is possible to give a more explicit formula in general. To provide for some peace of mind, we prove the following property: Property 4.1. If all inputs of the equilibrium time are non-negative, then the equilibrium time is well defined.More importantly, in Sec. 5 we provide a lower bound that involves the same mapping. Thus, the equilibrium time is not an "artifact" of our method, but is of a fundamental nature. We use the equilibrium time t * in Shadowheart SGD when we choose b i and m i .Our first main result provides iteration complexity: Theorem 4.2. Lett Assumptions 1.1, 1.2, 1.3, 2.2 hold. Let us take γ = 1/2L in Shadowheart SGD (Alg. 1). Then as long as K ≥ 16L∆/ε, we have the guarantee1 K K-1 k=0 E ∇f (x k ) 2 ≤ ε.This result guarantees that Shadowheart SGD will converge after O ( L∆ /ε) iterations. Our second main result provides a much more relevant complexity measure: time complexity. Corollary 4.3. Shadowheart SGD (Alg. 1) converges after at most T * seconds, whereEQUATIONSurprisingly, we show in Sec. 5 that our time complexity guarantee ( 10) is optimal for the family of centralized methods with compressed communication. Moreover, in Sec. 7 and 7.1, we show that ( 10) is no worse and can be significantly better than the time complexities of previous centralized methods (see also 16L∆ ε ⌉ k=0 2t * (ω, σ 2 /ε, h k 1 , τ k 1 , . . . , h k n , τ k n ) (11)seconds, where h k i > 0 and τ k i > 0 are computation and communication times for worker i in iteration k.For presentation simplicity sake, in the main part we continue to work with static {h i } and {τ i }.One of the main features of asynchronous methods (e.g., Rennala SGD, Asynchronous SGD) is their adaptivity to and independence from processing times. In Sec. M, we design Adaptive Shadowheart SGD (Alg. 7) with this feature. Unlike Alg. 1, it does not require the knowledge of {h i } and {τ i } (or {h k i } and {τ k i } in the case of Alg. 4), and does not calculate the equilibrium time t * . However, as a byproduct of this flexibility, this method has a slightly worse time complexity guarantee. In order to present our result, we need to define an auxiliary sequence. Definition 4.5. Assume that the workers have computation and communication times less or equal to {h i } and {τ i }. Assume that hij is the actual time required to calculate the j th stochastic gradient by worker i, h min > 0 is the smallest possible computation time. Then ] is the largest ratio between the fastest and the slowest computation of stochastic gradients in local time windows. r i defines a degree of fluctuations in computation times. Note that r i describes local fluctuations; it is true that r i ≤ sup j≥1 hi,j /inf j≥1 hi,j for all i ∈ [n] and r i can be arbitrarily smaller.r i := sup k≥0 sup 1≤j≤lmax hi,(k+j) inf 1≤j≤lmax hi,(k+j) , l max := tmax hmin , t max := 128 × t * (ω, σ 2 /ε, [max{h i , τ i }, max{h i , τ i }] n 1 ). That is, r i ∈ [1, ∞A corollary of our main result in this part (Theorem M.1) is presented next. Corollary 4.6. If the computation and communication times are positive, the time complexity of Alg. 7 isL∆ ε × t * (ω, σ 2 /ε, [max{h i , τ i }, min {τ i r i , max{h i , τ i }}] n 1) up to a constant factor, where r i is defined in Def. 4.5.Unlike Alg. 1 and Alg. 4, Alg. 7 is more "greedy"; it calculates stochastic gradients and sends compressed vectors in parallel, and it does not know the times h i and τ i (or h k i and τ k i ). That is why this method gets a suboptimal complexity and depends on r i . Nevertheless, if we assume that i) the computation times do not fluctuate significantly, i.e., r i = Θ(1), and ii) τ i ≤ h i for all i ∈ [n], then this complexity reduces to the optimal complexity L∆ /ε × t * (ω, σ 2 /ε, [h i , τ i ] n 1 ).m ∈ [n], j ≥ 1, if b η m,j = ∞, then e µ m,j = ∞. For all m ∈ [n], j ≥ 1, if b η m,j < ∞, then e µ m,j ∈ N ∪ {∞}is the first index of the sequence {S m,j } ∞ j=1 that started calculating in (55) in the compression oracle Ĉm in or after the iteration k(j -1) and the first moment when ξ m,(i+b η m,j -1) = 1 for some i ≥ 1.It possible that such indexes do not exist, then we take b η m,j = ∞, b µ m,j = ∞, e η m,j = ∞, or e µ m,j = ∞, accordingly. By the construction, e η m,j ≥ b η m,j and e µ m,j ≥ b µ m,j . Let us clarify the definitions. At the beginning x 0 = 0, thus k(0) = 0. It would mean that the first index of the sequence {ξ m,j } ∞ j=1 , when the worker evaluates g(s x ; ξ) in ( 55), simply equals b η m,1 = 1 or b η m,1 = ∞ (by the definition, it equals to ∞ if the oracle was never called). Assume that b η m,1 = 1, then η m,1 = inf{i | ξ m,i = 1 and i ∈ N} is the first time when the oracle draws a "successful" random bernoulli trial. This random variable is distributed according to the geometric distribution.Then, e η m,1 can be equal to η m,1 + 1 or ∞. At some (random) iteration k(1), the algorithm A can get the first non-zero coordinate through g k , then b µ m,2 is the next index of the sequence {ξ m,j } ∞ j=1 that started calculating in (55). 15 The server gets a non-zero coordinate if at least one worker draws a successful bernoulli trial, and this coordinate belongs to a set generated by the uniform distribution. It takes h i seconds to generate one bernoulli trial and τ i seconds to generate one uniform trial.Then, if := inf k∈St 1 prog(x k ) < 1 < 1 holds, thent1 := min m∈[n] {h m η m,1 + τ m µ m,1 } ≤ t k(1) .because h m η m,1 + τ m µ m,1 is the time required to generate η m,1 bernoulli and µ m,1 uniform trials. In other words, the algorithm can not progress to the next coordinate before the moment when at least one worker generates "successful" bernoulli and uniform trials.Using the same reasoning, t k(j) ≥ t k(j-1) + tj , where tj := min m∈ [n] {h m η m,j + τ m µ m,j } .15 Let us consider an example with the m th worker. Assume that it starts calculations of stochastic gradients and with ηm,1 = 5 (as an example) it gets a "successful" trial: ξ m,ηm,η m,1 = ξ m,5 = 1 (ξ m,1 = • • • = ξ m,4 = 0). And only then, starting with e µ m,1 , the compression oracle can get a vector with a non-zero coordinate. Even if there was a previous "successful" trial: 1 ∈ S m,i for some i < e µ m,1 . This trial did not return a vector with a non-zero coordinate because the stochastic oracle did not return a vector with a non-zero coordinate by that time.Assume that e µ m,1 = 10, then the server waits for µm,1 = inf{i | 1 ∈ S m,(i+e µ m,1 -1) }. Assume that µm,1 = 7, then the time moment, when 1 ∈ S m,(µ m,1 +e µ m,1 -1) = 1 ∈ S m,(7+10-1) , is the first possible moment when the m th worker can send a vector with a non-zero coordinate to the server.k∈St 1 prog(x k ) < T < 1 holds, then T j=1 min j∈[n] (h i η i,j + τ i µ i,j ) ≤ t k(T ) ≤ t. Thus P inf k∈St 1 prog(x k ) < T < 1 ≤ P T i=1 ti ≤ t = P T i=1 min j∈[n](h i η i,j + τ i µ i,j ) ≤ t ∀t ≥ 0. EQUATIONThe σ-algebra G T contains all information about the random variables before the moment when prog(x k ) = T -1. Then, we haveE exp -s T i=1 ti = E E exp -s T -1 i=1 ti -s tT G T .Note that if the random variables from (64) are "fixed," then ti is deterministic for all i ∈ [T -1] because ti is a deterministic function of (64), and does not depend on other subsequent random variables.Let us show it using a contradiction proof. Without the loss of generality, assume that tT -1 depends on ξ 1,b η 1,T ̸ ∈ (64). By the definition of b η 1,T , it would mean that the first time when the server can get a vector g k with a non-zero coordinate in the index T -1 is after the moment t k(T -1) . We get a contradiction since t k(T -1) is the first time when the algorithm return an iterate with a non-zero coordinate in the index T -1.EQUATIONLet us fix t ′ ≥ 0, then, since tT ≥ 0, we haveEQUATION)We now use the result of the following lemma that we prove separately.Lemma P.3. Using the notations from the proof of Lemma P.2, we haveP tj ≤ t ′ G j ≤ 1 - n m=1 1 -1 -(1 -p ω ) t ′ τm 1 -(1 -p σ ) t ′ hm (67) for all j ∈ [T ].Let us temporarily definep ′ := 1 - n m=1 1 -1 -(1 -p ω ) t ′ τm 1 -(1 -p σ ) t ′ hmWe substitute (67) to ( 66) and ( 65) to obtainE exp -s T i=1 ti ≤ p ′ + e -st ′ (1 -p ′ ) E exp -s T -1 i=1 ti ≤ p ′ + e -st ′ (1 -p ′ ) T .Next, using (63), we getP T i=1 ti ≤ t ≤ e s t p ′ + e -st ′ (1 -p ′ ) T = e s t-st ′ T 1 + e st ′ -1 p ′ T .Let us take s = 1 /t ′ , and getEQUATIONLet us recall the definition of p ′ :p ′ := 1 - n m=1 1 -1 -(1 -p ω ) t ′ τm 1 -(1 -p σ ) t ′ hm = 1 - n m=1 (1 -q m )where we define qm := 1 -(1 -p ω ) t ′ τm 1 -(1 -p σ ) t ′ hm ∈ [0, 1]. Using Lemma C.1, we have p ′ ≤ n m=1 q m .Using the inequality16 1 -(1 -p) m ≤ pm for all p ∈ [0, 1] and m ∈ N 0 , we can get the following three inequalities:EQUATIONq m ≤ 1 -(1 -p ω ) t ′ τm 1 -(1 -p σ ) t ′ hm ≤ p ω t ′ τ m p σ t ′ h m .Therefore, we getEQUATIONNow, we have to take the right t ′ . Assume that s * (j) is the solution ofEQUATIONandj * = inf {j ∈ [n] | s * (j) < max{h j+1 , τ j+1 }} ∈ [n], max{h n+1 , τ n+1 } ≡ ∞.Then we take t ′ = 1 24 s * (j * ).If j * = 1, then s * (j * ) = 1 2τ1 pω + 4τ1h1 pωpσs * (j * ) + 2h1 pσ -1 ≥ 1 2τ1 pω + 2h1 pσ -1 ≥ 1 2τ 1 + 2h 1 -1 ≥ 1 2 max{h 1 , τ 1 }.Otherwise, if j * > 1, since s * (j * ) ≤ s * (j * -1), we haves * (j * ) =   j * m=1 1 2τm pω + 4τmhm pωpσs * (j * ) + 2hm pσ   -1 ≥   j * -1 m=1 1 2τm pω + 4τmhm pωpσs * (j * -1) + 2hm pσ + 1 2τ j * pω + 2h j * pσ   -1 ≥   j * -1 m=1 1 2τm pω + 4τmhm pωpσs * (j * -1) + 2hm pσ + 1 max{h j * , τ j * }   -1.By the definitions of s * (j * -1) and j * , we have  j * -1 m=1 1 2τm pω + 4τmhm pωpσs * (j * -1) + 2hm pσ   -1 = s * (j * -1) ≥ max{h j * , τ j * }.Therefore, we gets * (j * ) ≥ 1 max{h j * , τ j * } + 1 max{h j * , τ j * } -1 = 1 2 max{h j * , τ j * }.Using s * (j * ) ≥ 1 2 max{h j * , τ j * }, we obtainEQUATIONWe use the last inequality later. Let us return to the inequality (69). Using the definition of j * , we obtain t ′ τm = 0 or t ′ hm = 0 for all m > j * andp ′ ≤ n m=1 min p σ t ′ h m , p ω t ′ τ m , p ω p σ t ′ τ m t ′ h m = j * m=1 min p σ t ′ h m , p ω t ′ τ m , p ω p σ t ′ τ m t ′ h m ≤ j * m=1 min p σ t ′ h m , p ω t ′ τ m , p ω p σ t ′2 τ m h m ,where we use ⌊x⌋ ≤ x for all x ≥ 0. Using max{x, y, z} ≥ 1 3 (x + y + z) for all x, y, z ≥ 0, we havep ′ ≤ j * m=1 max h m p σ t ′ , τ m p ω t ′ , τ m h m p ω p σ t ′2 -1 ≤ j * m=1 3 τm pωt ′ + τmhm pωpσt ′2 + hm pσt ′ . Since t ′ = 1 24 s * (j * ), we obtain p ′ ≤ j * m=1 3 24τm pωs * (j * ) + 24 2 τmhm pωpσ(s * (j * )) 2 + 24hm pσs * (j * ) ≤ 1 4 j * m=1 1 2τm pωs * (j * ) + 4τmhm pωpσ(s * (j * )) 2 + 2hm pσs * (j * ).Note that s * (j * ) is the solution of ( 70), thus, we getp ′ ≤ 1 4 .Substituting this inequality to (68), we obtainP T i=1 ti ≤ t ≤ e t/t ′ -T 2 .For t ≤ t ′ T 2 + log δ , we haveP T i=1 ti ≤ t ≤ δ.Recall that the definition of t ′ . Using (71), we havet ′ ≥ 1 48 min j∈[n]max{max{h j , τ j }, s * (j)}.The last term equals to the equilibrium time t * ( 1 /pω, 1 /pσ, h 1 , τ 1 , . . . , h n , τ n ) from Def. 3.1 since the pairs (h j , τ j ) are sorted by max{h j , τ j }. Thus, we obtaint ′ ≥ 1 48 t * ( 1 /pω, 1 /pσ, h 1 , τ 1 , . . . , h n , τ n ).Finally, we obtainP inf k∈St 1 prog(x k ) < T < 1 ≤ P T i=1 ti ≤ t ≤ δ (72) for t ≤ 1 48 t * ( 1 /pω, 1 /pσ, h 1 , τ 1 , . . . , h n , τ n ) T 2 + log δ .P.2 Proof of Lemma P.3 Lemma P.3. Using the notations from the proof of Lemma P.2, we haveP tj ≤ t ′ G j ≤ 1 - n m=1 1 -1 -(1 -p ω ) t ′ τm 1 -(1 -p σ ) t ′ hm (67) for all j ∈ [T ].Proof. We prove the result for j = T. The proofs for the cases 1 ≤ j < T are the same. We consider the conditional probabilityP tT ≤ t ′ G T = P min m∈[n] {h m η m,T + τ m µ m,T } ≤ t ′ G T .Let us consider the σ-algebra H T generated by (64) with j = T and e η 1,T , . . . , e η n,T ξ 1,1 , ξ 1,2 , . . . , ξ 1,e η 1,T -1 , . . . ξ n,1 , ξ n,2 , . . . , ξ 1,e η n,T -1 , e µ 1,T , . . . , e µ n,T , S 1,1 , S 1,2 , . . . , S 1,e µ 1,T -1 , . . . S n,1 , S n,2 , . . . , S n,e µ n,T -1 .(73)By the construction, e η m,T ≥ b η m,T and e µ m,T ≥ b µ m,T . Since G T ⊆ H T , we haveP tT ≤ t ′ G T = E P min m∈[n] {h m η m,T + τ m µ m,T } ≤ t ′ H T G T . Since G T ⊆ H T , then b µ m,T is H T -measurable.By the definition of e η m,T , η m,T are H T -measurable. Let us show it using a contradiction proof. Without the loss of generality, assume that η m,T depends on ξ 1,e η m,T ̸ ∈ (73). It would mean that the first time, when ξ m,i = 1 after the iteration k(T -1), happens with i ≥ e η m,T . At the same time, by the definition of e η m,T , there exists i < e η m,T such that ξ m,i = 1 calculated after the iteration k(T -1). We get a contradiction. Given H T , µ m,T are mutually independent since {S m,j } ∞ j=1 are mutually independent and e µ m,T are H T -measurable. Therefore, we haveEQUATIONLet us consider the probability P (h m η m,T + τ m µ m,T > t ′ |H T ) :EQUATIONLet us consider the probability (i+e-1) and i ∈ N}.P (τ m µ m,T ≤ t ′ |H T ) . Given H T , if e µ m,T = ∞, then µ m,T = ∞ and P (τ m µ m,T ≤ t ′ |H T ) = 0. Otherwise, if e µ m,T = e < ∞, then µ m,T = inf{i | j ∈ S m,and it is distributed with the geometric distribution with p ω . Thus, we have 17 17 We implicitly assume that 1 -(1 -pω)P (τ m µ m,T ≤ t ′ |H T ) = 1 -(1 -p ω ) t ′ τm , e µ m,T < ∞ 0, e µ m,T = ∞ ≤ 1 -(1 -p ω ) t ′ τm ,t ′ τm = 0 if pω = 1 and t ′ τm = 0, because if t ′ < τm, then P (τmµm,T ≤ t ′ ) = 0 for the r.v. µm,T from the geometric distribution for all pω ∈ (0, 1].because the probability that j th coordinate belongs to S m,(i+e-1) equals to p ω . We substitute this inequality to (75) and getP (h m η m,T + τ m µ m,T > t ′ |H T ) ≥ 1 -1 -(1 -p ω ) t ′ τm 1 [h m η m,T ≤ t ′ ] .Next, we substitute this inequality to (74) and obtainP tT ≤ t ′ G T ≤ 1 -E n m=1 1 -1 -(1 -p ω ) t ′ τm 1 [h m η m,T ≤ t ′ ] G T .Given G T , η m,T are independent because b η m,T are G T -measurable. ThusP tT ≤ t ′ G T ≤ 1 - n m=1 1 -1 -(1 -p ω ) t ′ τm E [ 1 [h m η m,T ≤ t ′ ]| G T ] = 1 - n m=1 1 -1 -(1 -p ω ) t ′ τm P (h m η m,T ≤ t ′ |G T ) .Using the same reasoning as with µ m,T , we getP (h m η m,T ≤ t ′ |G T ) = 1 -(1 -p σ ) t ′ hm , b η m,T < ∞ 0, b η m,T = ∞ ≤ 1 -(1 -p σ ) t ′ hm .because, given G T , η m,T equals ∞ or a random variable distributed according to the geometric distribution with p σ . Therefore, we obtainP tT ≤ t ′ G T ≤ 1 - n m=1 1 -1 -(1 -p ω ) t ′ τm 1 -(1 -p σ )t ′ hm .In the proof of Theorem O.5, we could use the following construction:(Step 3: Compression Operator) Let us define p ω := 1 ω+1 . In our construction, we take a compressor that outputs random coordinates of an input vector, scaled by 1 /pω, where each coordinate is taken with the probability p ω . Each worker has access to the independent compressed realizations of a such compressor. More formally, we assume that[C(x; S)] j := 1 pω x j , j ∈ S, 0, j ̸ ∈ S, ∀j ∈ [T ],where S is a random subset of [T ], where each element from [T ] appears with the probability p ω independently. ThenE S [[C(x; S)] j ] = x j and E S ∥C(x; S)∥ 2 = E S   T j=1 1 [j ∈ S] 1 p 2 ω x 2 j   = T j=1 P (j ∈ S) 1 p 2 ω x 2 j = T j=1 1 p ω x 2 j = (ω + 1) ∥x∥ 2 .Thus, we have C ∈ U(ω). We take mutually independent distributions D C i that generate random subsets S described above. This construction is also valid and does not require the assumption ω + 1 ≲ L∆ /ε. However, unlike the construction from Theorem O.5, this construction can return a random number of non-zero coordinates.The experiments were prepared in Python. The distributed environment was emulated on machines with Intel(R) Xeon(R) Gold 6226R CPU @ 2.90GHz and 64 cores. We start our experiments with a practical setup: a logistic regression problem with the MNIST dataset (LeCun et al., 2010) . The optimization steps of algorithms are emulated in Python, where we fix the number of workers to n = 100, each worker has access to the MNIST dataset and sample 4 samples when calculating a stochastic gradient. We compare Shadowheart SGD with QSGD, Asynchronous SGD (we implement the version from (Koloskova et al., 2022) ), Minibatch SGD, and SGDone. SGDone is the method described in Sec. 7, where SGD is run on the fastest worker locally. In Shadowheart SGD, we fine-tune the parameter σ 2 /ε ∈ {1, 5, 10, 20, 30, 40, 80, 120, 150, 200} . In all the methods, we also finetune the step sizes. The dimension of the problem in the logistic regression problem is d = 7850. In Shadowheart SGD and QSGD, we take RandK with K = 700.We assume that the computations time h i of a stochastic gradient equals to √ i seconds in the i th worker. We consider three communication time setups, where it takes τi seconds to send one coordinate from the i th worker to the server and1. τi = √ i/d (High-speed communications), 2. τi = √ i/d 3/4 (Medium-speed communications), 3. τi = √ i/d 1/2 (Low-speed communications).In the high-speed regime, the communication between the server and the worker is relatively fast. At the same time, in low-speed regimes, communication is expensive. We are ready to present the results of our experiments in Fig. 1a , 1c, and 1b.In Figure 1a , one can see that Shadowheart SGD, Asynchronous SGD, and Minibatch SGD are the fastest because it is not expensive to send a non-compressed vector in the "high-speed communications" regime. SGDone is the slowest since it utilizes only one worker.Next, we analyze Figure 1b , where Shadowheart SGD and SGDone have the best performance. SGDone improves the convergence relative to other methods because the communication speed is much slower than in Figure 1a , and it is expensive to send a non-compressed vector.One can see that Shadowheart SGD is very robust to all regimes and has one of the best convergence rates in all experiments. Notably, in the "medium-speed communications" regime, where it is still expensive to send a non-compressed vector, our new method converges faster than other baseline methods.Q.2 Experiments with quadratic optimization tasks and multiplicative noiseIn real machine learning tasks, it is not easy to control noise. Thus, we generated synthetic quadratic optimization tasks where we can control the noise of stochastic gradients. In particular, we considerf (x) = 1 2 x ⊤ Ax -b ⊤ xfor all x ∈ R d and take d = 1000,A = 1 4      2 -1 0 -1 . . . . . . . . . . . . -1 0 -1 2      ∈ R d×d and b = 1 4     -1 0 . . . 0     ∈ R d .We consider the following stochastic gradients:EQUATIONwhere ξ ∼ Bernoulli(p) for all i ∈ [n], and p ∈ (0, 1]. We denote [x] j as the j th index of a vector x ∈ R d . In our experiments, we take the starting point x 0 = [ √ d, 0, . . . , 0] ⊤ and p ∈ {10 -3 , 10 -4 }; the smaller p the larger the noise of stochastic gradients. Q.2.1 Discussion of the experiments from Sec. Q.2.2 Using this setup, in Figures 2, 3 , 4, we fix all parameters except one that we vary to understand the dependencies. In all experiments, we observe that Shadowheart SGD is the most robust to input changes among other centralized methods (QSGD, Asynchronous SGD, Minibatch SGD) and can converge significantly faster. At the same time, we observe that SGDone can be faster than our method in some setups. It happens in the regimes when communication is expensive (see Figure 2a ), which is expected and discussed in Sec. 7. Even if communication is expensive, SGDone starts to slow down relative to other methods when we increase the noise (compare Figures 2b and 2a ). The following experiments agree with our theoretical discussion in Sec. 7.In these experiments, we take n = 10000, p = 10 -3 , h i = √ i, τi = √ i/d 3/4 as base parameters; in each plot, we vary one parameter. h k i = √ i, τ k i = c • √ i• The assumptions made should be given (e.g., Normally distributed errors).• 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. 
lower bound: 
 Protocol 3 Simplified Representation of Protocol 91: Init S = ∅ on the server (all available information) 2: while True do 3:Server calculates a new point x using S and broadcasts x and S to any worker (broadcasting does not take time) 4: end while i th Worker (in parallel): 5: while True do 6:Receives x and S, calculates as many stochastic gradients as it want at the point x (each calculation takes h i seconds), aggregates all available information, and sends compressed vectors (each dispatch takes τ i seconds), which will be added to the set S 7: end while In Sec. 4, we stated that Shadowheart SGD converges after T * seconds; with T * given in (10). Our next step is to understand if it might be possible to improve this complexity. In Sec. O, we formalize our setup and show in Theorem O.5 that up to a constant factor, the result (10) is optimal. Here we present a simplified illustration of our approach.Protocol 3 can describe all centralized methods (the server updates the iterates, and the workers calculate stochastic gradients at these points), including Minibatch SGD, Asynchronous SGD, Rennala SGD, and Shadowheart SGD. In Theorem O.5, we show that up to a constant factor, no method described by Protocol 3 can converge faster than (10) seconds. In order to use our lower bound, the workers must calculate stochastic gradients at a point that was calculated by the server.Let us briefly explain the proof's idea. The general approach is the same as in (Nesterov, 2003; Arjevani et al., 2022; Huang et al., 2022) : we take the "difficult" function (Sec. P.1), which has large gradients while the last coordinate equals to zero. Every algorithm starts with the point x 0 = 0, and the only way to discover the next coordinate is to calculate a stochastic gradient. Oracles associated with the workers return the next non-zero coordinate with the probability p σ ≈ ε /σ 2 . Even if the stochastic oracle returns a non-zero coordinate for some worker, the corresponding communication oracle on this worker also has to return a non-zero coordinate, which happens with probability p ω ≈ 1 /ω+1. We fix the RandK compressor in the lower bound theorem with K ≈ L∆ /ε(ω+1), and the number of coordinates ≈ L∆ /ε; thus, indeed, p ω ≈ 1 /ω+1. Since all n workers work in parallel, they can discover and send to the server the next non-zero coordinate not earlier than after min m∈[n] {h m η m + τ m µ m } seconds, where η m and µ m are i.i.d. geometric random variables with p σ and p ω . With a high probability, we show that this quantity is Ω(t * ( 1 /pω, 1 /pσ, h 1 , τ 1 , . . . , h n , τ n )). The number of coordinates is ≈ L∆ /ε. Therefore, the lower bound is (10) seconds up to a constant factor. 
equilibrium time: 
 Since the time complexity (10) of Shadowheart SGD is optimal, we believe that the equilibrium time is a fundamental mapping that should be investigated more deeply.The calculation of t * requires us to sort max{h i , τ i }. Next, it is sufficient to solve n equations from (7). In Property 4.1, we prove that (7) has one unique solution that can be easily found, for instance, using the bisection method. Then, is it left to find the minimum in (8).Assuming we found an optimal j * in (8), we have t * = max{max{h π j * , τ π j * }, s * (j * )}. The first observation is that t * does not depend on the workers that correspond to max{h π j * +1 , τ π j * +1 }, . . . , max{h πn , τ πn }. Since these values are greater or equal to max{h π j * , τ π j * }, the mapping "decides" to ignore them because they are too slow. The following derivations are not rigorous and are merely supposed to offer some intuition. We define α i := τ πi ω and β i := hπ i σ 2 /ε. Next, using (7), we haveEQUATIONwhere M := {i ∈ [j * ] : max{α i , β i } ≥ αiβi /s * (j * )}. Solving this, one can get thatEQUATION)Thus, s * (j * ) divides the active workers into two groups M and [j * ] \ M. Both groups contribute to (13) with a harmonic mean-like and a quadratic harmonic mean-like dependences, correspondingly.The transition between two groups is decided by the rule max{α i ,β i } ≥ αiβi /s * (j * ) ⇔ s * (j * ) ≥ min{α i , β i }.Intuitively, the last inequality means that if τ i or h i is small (a worker can quickly compute a gradient or send a compressed vector), it belongs to M. Otherwise, if a worker's computation and communication performance are balanced, it belongs to [j * ] \ M.We now provide some properties and particular cases to understand t * better. One can find the proofs and more properties in Sec. E. The first result says that t * is monotonic. Property 6.1.If ω ≥ ω ≥ 0, σ2 /ε ≥ σ 2 /ε ≥ 0, h1 ≥ h 1 ≥ 0, τ1 ≥ τ 1 ≥ 0, . . . , hn ≥ h n ≥ 0, and τn ≥ τ n ≥ 0, then t * (ω, σ2 /ε, [ hi , τi ] n 1 ) ≥ t * (ω, σ 2 /ε, [h i , τ i ] n 1 ).Consider the RandK compressor. If it takes τi sec to send one coordinate by worker i, then, up to a constant factor, Property 6.2 ensures that an optimal choice of K is 1. Property 6.2. For allK ∈ [1, d], σ 2 /ε, h 1 , τ1 , . . . , h n , τn ≥ 0, we have 24 × t * d /K -1, σ 2 /ε, h 1 , K τ1 , . . . , h n , K τn ≥ t * d -1, σ 2 /ε, h 1 , τ1 , .. . , h n , τn .We now list several examples, starting with simple corner/extreme cases. One can find the derivations in Sec. F. For brevity, we will sometimes write t * instead of t * (ω, σ 2 /ε, h 1 , τ 1 , . . . , h n , τ n ). Example 6.3. [Infinitely Fast Worker] If exists j ∈ [n] such that τ j = 0 and h j = 0, then t * = 0. Example 6.4. [Infinitely Slow Workers] EQUATIONIn the next example, we consider the setting from Sec. EQUATIONwhere π is a permutation that sorts {h i } n i=1 . The following two examples show that t * is robust to slow workers or workers that do not participate. Example 6.7. [Ignoring Slow Workers] If h i and τ i are fixed and finite for all i ≤ p, and max{h i , τ i } = m ∈ R for all i > p, then, for m large enough, we have t * (ω,σ 2 /ε, [h i , τ i ] n 1 ) = t * (ω, σ 2 /ε, [h i , τ i ] p 1 ). Example 6.8. [Partial Participation] If max{h i , τ i } = ∞ for all i > p ≥ 1, then t * (ω, σ 2 /ε, [h i , τ i ] n 1 ) = t * (ω, σ 2 /ε, [h i , τ i ] p 1 ). 
comparison with baselines: 
 In the previous sections, we did not invoke any assumptions about the compressors except for Def. 2.1. Inspired by Property 6.2, to make the comparisons with the baselines easier, we consider the RandK compressor with K = 1. Using Theorem D.2, we have ω = d -1. We also assume that worker i takes τi seconds to send one coordinate to the server; thus τ i = τi , since we use Rand1. Also, it takes d τi to send a non-compressed vector for all i ∈ [n].Minibatch SGD and QSGD. It is well known (Lan, 2020) that the number of iterations of Minibatch SGD required to find an ε-solution is O L∆ /ε + σ 2 L∆ /ε 2 . In Minibatch SGD, each worker calculates one stochastic gradient and sends a non-compressed vector. Since the server waits for the slowest worker, the time complexity of such method (up to a constant factor) isEQUATION)In Sec. J, we compare ( 16) with (10) and show Comparison 7.1. T * = O(T MB ).However, there are many regimes when T * ≪ T MB . For instance, if max{h i , τi } = ∞ for some worker (Example 6.8), then T MB = ∞ and T * < ∞. Also, under the conditions of Example 6.7, if m → ∞, we get T MB → ∞ whereas T * is bounded. The same reasoning applies to QSGD because its time complexity (6) depends on max i∈[n] (h i + τi ) . Due to Theorem O.5, up to a constant factor, T * is less or equal to (6); see also Table 1 .Rennala SGD and Asynchronous SGD. When the communication time is negligible, Tyurin and Richtárik (2023c) proved that the optimal time complexity is attained by Rennala SGD. When τi → 0 for all i ∈ [n], we show in Example 6.6 that (10) is the same as the time complexity of Rennala SGD obtained by Tyurin and Richtárik (2023c) . Assume τi > 0 for all i ∈ [n]. We can apply the result from Theorem O.5 to Rennala SGD, thus the time complexity of Rennala SGD is not better thanEQUATIONNote that Asynchronous SGD also has the same lower bound. In Sec. J, we compare (17) with (10) and show Comparison 7.2. T * = O(T R ).7.1 Shadowheart SGD is strictly better in many regimes.Due to the non-explicit nature, it is not transparent that the time complexity of Shadowheart SGD is universally strictly better than in all baselines in many practical regimes. Let us prove it. TakeEQUATIONDue to ( 16) and ( 17), the time complexities of Minibatch SGD and QSGD are ∞, and the time complexities of Asynchronous SGD and Rennala SGD are not smaller thanΩ max h, d τ , hσ 2 (n-1)ε L∆ ε , which n→∞ → Ω max {h, d τ } L∆ ε .From ( 14), the time complexity of Shadowheart SGD is at mostO max h, τ , d τ n-1 , hσ 2 (n-1)ε , τ hσ 2 d (n-1)ε L∆ ε , which n→∞ → O max {h, τ } L∆ ε .Thus, Shadowheart SGD can be d times faster than all previous methods if the number of workers n is large. Using the same reasoning, Shadowheart SGD can be n -1 times faster if the dimension d or τ is large. Due to the continuity of the complexities, such huge differences hold even if we take n < ∞, and start considering more heterogenous times h i and τ i by perturbating (18).Another important baseline is the vanilla SGD method, which works on the fastest worker, does not communicate with the server, and performs local steps (non-centralized method). For simplicity, assume that σ 2 /ε ≥ 1. Then, the time complexity of such an algorithm (Lan, 2020) isT SGD := min i∈[n] h i × σ 2 L∆ /ε 2 .Clearly, comparing T SGD and (10), if τi are large enough, then T SGD can be smaller than T * . However, this does not contradict our lower bounds because this method does not satisfy the conditions of Theorem O.5: it does not communicate with the server. In other words, if the communication channel is too slow, it does not make sense to communicate. One may now ask: "Under which conditions is it beneficial to communicate?" Comparing T SGD and (10), one can see that (10) is better when t* (d -1, σ 2 /ε, h 1 , τ1 , . . . , h n , τn ) ≤ min i∈[n] h i × σ 2 /ε.It is sufficient to substitute the initial parameters to this inequality and decide which method to use. For instance, in the view of Example 6.5, one should compare max{h, τ , τ (d-1) /n, hσ 2 /nε, τ hσ 2 (d-1) /nε} vs. hσ 2 /ε. In the regime when n is large enough or ε is small enough, we have t * < hσ 2 /ε, and Alg. 7 has better convergence guarantees. On the other hand, if τ is large enough, then it is possible that t * > hσ 2 /ε. In this section, we discuss a simple way to use the Shadowheart SGD techniques in the setup when broadcasting is expensive (Line 7 in Alg. 1); i.e., when τ serv ≫ 0. We will employ the following family of compressors.EQUATION)We shall use the shortcut C(x; ν) ≡ C(x), and denote the family of such biased compressors as B(α).The familyB(α) is more general than U(ω) in the sense that if C ∈ U(ω), then (ω + 1) -1 C ∈ B((ω + 1) -1). It includes the TopK and RankK compressors (Vogels et al., 2019; Beznosikov et al., 2020) , among many others.Let C serv ∈ B(α) be the compressor used by the server. We use the primal error-feedback mechanism EF21-P (Gruntkowska et al., 2023) which requires us to add the following changes to Alg. 1 and Alg. 2. We add the stepsp k+1 = C serv (x k+1 -w k ), w k+1 = w k + p k+1to Alg. 1 and broadcast p k+1 instead of x k . This change leads to Bidirectional Shadowheart SGD (Alg. 5). In Alg. 2, the workers should receive p k+1 , calculate w k+1 , and use w k instead of x k in the calculations of stochastic gradients. We provide the pseudo-codes of these algorithms in Sec. K.Our main results are:Theorem A.2. Let Assumptions 1.1, 1.2, 1.3, 2.2 hold. Choose γ = α 16L .Then as long as K ≥ 768L∆ αε , Bidirectional Shadowheart SGD (Alg. 5) guarantees to find an ε-stationary point. Corollary A.3. If the broadcast time of C serv is not greater than τ serv , then Bidirectional Shadowheart SGD (Alg. 5) converges after at mostEQUATIONseconds.Remark A.4. If the broadcast cost can't be ignored, the time complexity of Alg. 1 changes from (10) toEQUATIONwhere τ full serv is the time required to broadcast a full/ non-compressed vector. We should compare (21) obtained by the unidirectional algorithm and (20) obtained by the bidirectional algorithm. Consider that C serv = TopK with K ≤ d. We can see ( 20) that depends on τ serv , that is much less than τ full serv because K ≪ d. At the same time, ( 20) is 1 /α times larger than ( 21). This is a standard price for the fact that we use a biased compressor (e.g. (Richtárik et al., 2021; Gruntkowska et al., 2023) ). However, α is very close 1 in practice (Beznosikov et al., 2020; Vogels et al., 2019; Xu et al., 2021b) . It turns out that we can always choose K in TopK (we take this compressor as an example) in such a way that Alg. 5 is never worse than Alg. 1. Comparison A.5. Assume that it takes τserv seconds to send one coordinate from the server to the workers. If we take K ≥ min d, t * (ω, σ 2 /ε, [h i , τ i ] n 1 )/ τserv in TopK, then T * ,serv = O (T * ) .We thought a table of frequently used notation could be useful. Here it is: T MB Time complexity of Minibatch SGD (see (16)) T R Time complexity of Rennala SGD (see (17)) g = O(f ) Exist C > 0 such that g(z) ≤ C × f (z) for all z ∈ Z g = Ω(f ) Exist C > 0 such that g(z) ≥ C × f (z) for all z ∈ Z g = Θ(f ) g = O(f ) and g = Ω(f ) {a, . . . , b} Set {i ∈ Z | a ≤ i ≤ b} [n] {1, . . . , n}Here we collect some basic facts which are used repeatedly in the proofs.Variance decomposition. Let x ∈ R d be a random vector with finite mean and finite variance. Then for any deterministic vector c ∈ R d , we have the identityEQUATION) Lemma C.1. Consider a sequence q 1 , . . . , q n ∈ [0, 1], then 1 - n m=1 q m ≤ n m=1(1 -q m ) .Proof. We prove by induction. For n = 1, is it true: 1 -1 m=1 q m = 1 m=1 (1 -q m ) . Assume that that it is true for n -1. Then 1 - n-1 m=1 q m ≤ n-1 m=1 (1 -q m ) .1 -q n ∈ [0, 1] to obtain n m=1 (1 -q m ) ≥ (1 -q n ) 1 - n-1 m=1 q m = 1 - n-1 m=1 q m -q n + q n n-1 m=1 q m ≥ 1 - n m=1 q m since q m ∈ [0, 1] for all m ∈ [n]. D RandK Compressor Definition D.1. Assume that S is a random subset from [d], |S| = K, K ∈ [d]. A stochastic mapping C : R d × S ν → R d is RandK if C(x; S) = d K j∈S x j e j ,where{e i } d i=1 is the standard unit basis. Theorem D.2. If C is RandK, then C ∈ U d k -1 .One can find the proof in (Beznosikov et al., 2020) .Property 4.1. If all inputs of the equilibrium time are non-negative, then the equilibrium time is well defined.Proof.(Part 1: s * (j) is well-defined) First, we show that s * (j) is well-defined for all j ∈ [n]. We fix j ∈ [n] and consider the equation from Def. 3.1:EQUATIONw.r.t s. The function ϕ(s) is a non-increasing function for all s ≥ 0, and the function ψ(s) is an increasing function for all s ≥ 0. Let us consider two cases.1) Exists p ≤ j such that τ πp ω = 0 andhπ p σ 2 ε = 0, then ϕ(s) =   i̸ =p 1 2τ πi ω + 4τπ i hπ i σ 2 ω s×ε + 2hπ i σ 2 ε + 1 0   -1 = (∞) -1 = 0.for all s ≥ 0, then the only solution to the equation is s = 0.2) Otherwise, we haveϕ(s) = j i=1 1 2τ πi ω + 4τπ i hπ i σ 2 ω s×ε + 2hπ i σ 2 ε -1 ≥ j i=1 1 2τ πi ω + 2hπ i σ 2 ε -1 > 0for all s ≥ 0. Then ϕ(0) > 0 (can be equal to ∞). Using ψ(0) = 0 and the monotonicity of the functions, one can show the unique solution (greater zero) exists.If a permutation π is unique, then the formula min j∈[n] max{max{h πj , τ πj }, s * (j)} is well-defined and we can finish the proof.(Part 2: non-unique permutation) We assume that there exists i ∈[n] such that max{h i , τ i } < ∞. Otherwise, min j∈[n] max{max{h πj , τ πj }, s * (j)} = ∞ for any permutation. Next, note that s * (j + 1) ≤ s * (j) for all j < n because j+1 i=1 1 2τ πi ω + 4τπ i hπ i σ 2 ω s×ε + 2hπ i σ 2 ε -1 ≤ j i=1 1 2τ πi ω + 4τπ i hπ i σ 2 ω s×ε + 2hπ i σ 2 ε -1for all s ≥ 0. We will use this property later.Consider that there are two non-equal permutations π and π that sort the pairs (h i , τ i ) by max{h i , τ i }, and there are two corresponding solutions s * (j) and s * (j). Each permutation divides the pairs (h i , τ i ) into the same equivalence classes:max{h π1 , τ π1 } = • • • = max{h πj 1 , τ πj 1 } C1 < max{h πj 1 +1 , τ πj 1 +1 } = • • • = max{h πj 2 , τ πj 2 } C2 < . . . , max{h π1 , τ π1 } = • • • = max{h πj 1 , τ πj 1 } C1 < max{h πj 1 +1 , τ πj 1 +1 } = • • • = max{h πj 2 , τ πj 2 } C2 < . . . .The order within each class can be different, but the elements are the same. Next, since s * (j + 1) ≤ s * (j) for all j < n, we can conclude that the minimum inmin j∈[n] max{max{h πj , τ πj }, s * (j)} is attained for j * such that max{h π j * , τ π j * } < max{h π j * +1 , τ π j * +1 } (max{h πn+1 , τ πn+1 } ≡ ∞). Since max{h π j * , τ π j * } < max{h π j * +1 , τ π j * +1 }, we have max{h π j * , τ π j * } = max{h πj * , τ πj * }.Therefore, we obtainmin j∈[n] max{max{h πj , τ πj }, s * (j)} = max{max{h π j * , τ π j * }, s * (j * )} = max{max{h πj * , τ πj * }, s * (j * )}.Also, for all j ∈ [n] such that max{h πj , τ πj } < max{h πj+1 , τ πj+1 }, we havej i=1 1 2τ πi ω + 4τπ i hπ i σ 2 ω s×ε + 2hπ i σ 2 ε -1 = j i=1 1 2τ πi ω + 4τπ i hπ i σ 2 ω s×ε + 2hπ i σ 2 ε -1Therefore, we get s * (j * ) = s * (j * ) andmin j∈[n] max{max{h πj , τ πj }, s * (j)} = max{max{h πj * , τ πj * }, s * (j * )} ≥ min j∈[n]max{max{h πj , τ πj }, s * (j)}.Using the same reasoning, we can show thatmin j∈[n] max{max{h πj , τ πj }, s * (j)} ≥ min j∈[n]max{max{h πj , τ πj }, s * (j)}.It means that min j∈[n] max{max{h πj , τ πj }, s * (j)} = min j∈[n] max{max{h πj , τ πj }, s * (j)}, thus the final result of the mapping does not depend on a chosen permutation.Property 6.1. If ω ≥ ω ≥ 0, σ2 /ε ≥ σ 2 /ε ≥ 0, h1 ≥ h 1 ≥ 0, τ1 ≥ τ 1 ≥ 0, . . . , hn ≥ h n ≥ 0, and τn ≥ τ n ≥ 0, then t * (ω, σ2 /ε, [ hi , τi ] n 1 ) ≥ t * (ω, σ 2 /ε, [h i , τ i ] n 1 ).Proof. Assume that π is a permutation that sorts the pairs (h i , τ i ) by max{h i , τ i }, and π is a permutation that sorts the pairs ( hi , τi ) by max{ hi , τi }, thenj i=1 1 2τ πi ω + 4τπ i hπ i σ 2 ω sε + 2hπ i σ 2 ε -1 ≤ j i=1 1 2τ πi ω + 4τπ i hπ i σ2 ω sε + 2 hπ i σ2 ε -1 for all j ∈ [n]. It means s * (j) ≥ s * (j), where s * (j) and s * (j) are the solutions of the equation ( 7) with the pairs (h i , τ i ) and ( hi , τi ) and corresponding permutations π and π. Also, we have max{h πj , τ πj } ≤ max{ hπj , τπj } for all j ∈ [n]. Therefore, we havet * (ω, σ 2 /ε, h 1 , τ 1 , . . . , h n , τ n ) = min j∈[n] max{max{h πj , τ πj }, s * (j)} ≤ min j∈[n] max{max{ hπj , τπj }, s * (j)} = t * (ω, σ2 /ε, h1 , τ1 , . . . , hn , τn ).Property E.1. For all c ∈ (0, 1] and ω, σ 2 /ε, h 1 , τ 1 , . . . , h n , τ n ≥ 0, we havet * (c × ω, c × σ 2 /ε, h 1 , τ 1 , . . . , h n , τ n ) ≥ c × t * (ω, σ 2 /ε, h 1 , τ 1 , . . . , h n , τ n ).Proof. Using the definition of the equilibrium time, we havet * (ω, σ 2 /ε, h 1 , τ 1 , . . . , h n , τ n ) = min j∈[n] max{max{h πj , τ πj }, s * (j)},where s * (j) is the solution ofEQUATIONandt * (c × ω, c × σ 2 /ε, h 1 , τ 1 , . . . , h n , τ n ) = min j∈[n] max{max{h πj , τ πj }, s * c (j)},where s * c (j) is the solution ofj i=1 1 2cτ πi ω + 4c 2 τπ i hπ i σ 2 ω sε + 2chπ i σ 2 ε -1 = s.Using simple algebra, we obtainEQUATIONComparing ( 24) and ( 25), one can see that s * c (j) = c × s * (j) for all j ∈ [n]. Using this and c ∈ (0, 1], we gett * (c × ω, c × σ 2 /ε, h 1 , τ 1 , . . . , h n , τ n ) = min j∈[n] max{max{h πj , τ πj }, c × s * (j)} ≥ c × min j∈[n] max{max{h πj , τ πj }, s * (j)} = c × t * (ω, σ 2 /ε, h 1 , τ 1 , . . . , h n , τ n ).Property E.2. For all c ≥ 1 and ω, σ 2 /ε, h 1 , τ 1 , . . . , h n , τ n ≥ 0, we havet * (c × ω, c × σ 2 /ε, h 1 , τ 1 , . . . , h n , τ n ) ≤ c × t * (ω, σ 2 /ε, h 1 , τ 1 , . . . , h n , τ n ).Proof. The proof of this property repeats the proof of Property E.1 up to the last inequality. Using c ≥ 1, we gett * (c × ω, c × σ 2 /ε, h 1 , τ 1 , . . . , h n , τ n ) = min j∈[n] max{max{h πj , τ πj }, c × s * (j)} ≤ c × min j∈[n] max{max{h πj , τ πj }, s * (j)} = c × t * (ω, σ 2 /ε, h 1 , τ 1 , . . . , h n , τ n ). Property E.3. For all c ∈ (0, 1] and ω, σ 2 /ε, h 1 , τ 1 , . . . , h n , τ n ≥ 0, we have t * (c × ω, σ 2 /ε, [h i , τ i ] n 1 ) ≥ c × t * (ω, σ 2 /ε, [h i , τ i ] n 1 ) and t * (ω, c × σ 2 /ε, [h i , τ i ] n 1 ) ≥ c × t * (ω, σ 2 /ε, [h i , τ i ] n 1 ). For all c ≥ 1 and ω, σ 2 /ε, h 1 , τ 1 , . . . , h n , τ n ≥ 0, we have t * (c × ω, σ 2 /ε, [h i , τ i ] n 1 ) ≤ c × t * (ω, σ 2 /ε, [h i , τ i ] n 1 ) and t * (ω, c × σ 2 /ε, [h i , τ i ] n 1 ) ≤ c × t * (ω, σ 2 /ε, [h i , τ i ] n 1 ) Remark E.4.We can obtain stronger inequalities. See Properties E.1 and E.2.Proof. For all c ∈ (0, 1], using Properties 6.1 and E.1, we havet * (c × ω, σ 2 /ε, h 1 , τ 1 , . . . , h n , τ n ) ≥ t * (c × ω, c × σ 2 /ε, h 1 , τ 1 , . . . , h n , τ n ) ≥ c × t * (ω, σ 2 /ε, h 1 , τ 1 , . . . , h n , τ n ) and t * (ω, c × σ 2 /ε, h 1 , τ 1 , . . . , h n , τ n ) ≥ t * (c × ω, c × σ 2 /ε, h 1 , τ 1 , . . . , h n , τ n ) ≥ c × t * (ω, σ 2 /ε, h 1 , τ 1 , . . . , h n , τ n ).For all c ≥ 1, using Properties 6.1 and E.2, we havet * (c × ω, σ 2 /ε, h 1 , τ 1 , . . . , h n , τ n ) ≤ t * (c × ω, c × σ 2 /ε, h 1 , τ 1 , . . . , h n , τ n ) ≤ c × t * (ω, σ 2 /ε, h 1 , τ 1 , . . . , h n , τ n ) and t * (ω, c × σ 2 /ε, h 1 , τ 1 , . . . , h n , τ n ) ≤ t * (c × ω, c × σ 2 /ε, h 1 , τ 1 , . . . , h n , τ n ) ≤ c × t * (ω, σ 2 /ε, h 1 , τ 1 , . . . , h n , τ n ).Property E.5. For all c ≥ 0 and ω, σ 2 /ε, h 1 , τ 1 , . . . , h n , τ n ≥ 0, we havet * (ω, σ 2 /ε, c × h 1 , c × τ 1 , . . . , c × h n , c × τ n ) = c × t * (ω, σ 2 /ε, h 1 , τ 1 , . . . , h n , τ n ).Proof. For c = 0, it it clear. Assume that c > 0. Using the definition of the equilibrium time, we havet * (ω, σ 2 /ε, h 1 , τ 1 , . . . , h n , τ n ) = min j∈[n] max{max{h πj , τ πj }, s * (j)},where s * (j) is the solution ofEQUATIONandt * (ω, σ 2 /ε, c × h 1 , c × τ 1 , . . . , c × h n , c × τ n ) = min j∈[n] max{max{c × h πj , c × τ πj }, s * c (j)},where s * c (j) is the solution ofj i=1 1 2cτ πi ω + 4c 2 τπ i hπ i σ 2 ω sε + 2chπ i σ 2 ε -1 = s.For both cases, we can take the same permutation π. Using simple algebra, we obtainEQUATIONComparing ( 26) and ( 27), one can see thats * c (j) = c × s * (j) for all j ∈ [n]. Using this, we get t * (ω, σ 2 /ε, c × h 1 , c × τ 1 , . . . , c × h n , c × τ n ) = min j∈[n] max{max{c × h πj , c × τ πj }, c × s * (j)} = c × min j∈[n] max{max{h πj , τ πj }, s * (j)} = c × t * (ω, σ 2 /ε, h 1 , τ 1 , . . . , h n , τ n ).Property E.6. We fix a nonempty subset S = {k 1 , . . . , k m } from the set [n] with a size m ≥ 1. For all ω, σ 2 /ε, h 1 , τ 1 , . . . , h n , τ n ≥ 0, we havet * (ω, σ 2 /ε, h 1 , τ 1 , . . . , h n , τ n ) ≤ t * (ω, σ 2 /ε, h k1 , τ k1 , . . . , h km , τ km ).Proof. Using Property 6.1 with τi = ∞ and hi = ∞ for all i ̸ ∈ S and τi = τ i and hi = h i for all i ∈ S, we havet * (ω, σ 2 /ε, h 1 , τ 1 , . . . , h n , τ n ) ≤ t * (ω, σ 2 /ε, h1 , τ1 , . . . , hn , τn ).Next, using Def. 3.1, we obtaint * (ω, σ 2 /ε, h1 , τ1 , . . . , hn , τn ) = min j∈[n] max{max{ hπj , τπj }, s * (j)},where s * (j) is the solution of  j i=1 1 2τ πi ω + 4τπ i hπ i σ 2 ω s×ε + 2 hπ i σ 2 ε   -1 = s (28) w.r.t s for all j ∈ [n],and π is a permutation that sorts max{ hi , τi } in such a way that the set {π 1 , . . . , π m } equals to the set {k 1 , . . . , k m } (the order of elements can be different). Such permutation exists because max{ hi , τi } = ∞ for all i ̸ ∈ S. Using max{ hπi , τπi } = ∞ for all i > m, we haveEQUATION)By the construction of π, (28) and ( 29) depend only on the elements from S. Thus, we havet * (ω, σ 2 /ε, h 1 , τ 1 , . . . , h n , τ n ) ≤ t * (ω, σ 2 /ε, h1 , τ1 , . . . , hn , τn ) = t * (ω, σ 2 /ε, hk1 , τk1 , . . . , hkm , τkm ) = t * (ω, σ 2 /ε, h k1 , τ k1 , . . . , h km , τ km ).Property E.7. For all σ 2 /ε, h 1 , τ1 , . . . , h n , τn ≥ 0, we have12t * 0, σ 2 /ε, h 1 , d τ1 , . . . , h n , d τn ≥ t * d -1, σ 2 /ε, h 1 , τ1 , . . . , h n , τn . Proof. For d = 1, it is clear. Assume that d > 1.Using the definition of t * , we haveEQUATION)where π is a permutation that sorts max{h i , d τi }. Assume that j * is the minimal index that minimizes (30). ThenEQUATION)Let us defineI * := t * (d -1, σ 2 /ε, h 1 , τ1 , . . . , h n , τn ).Using Property E.6, we haveI * ≤ t * (d -1, σ 2 /ε, h π1 , τπ1 , . . . , h πj * , τπ j * ).Using Def. 3.1 of t * , we getEQUATIONwhere s * is the solution ofEQUATION) Let us take s ′ = 12 max (d -1) max j∈[j * ] τπj , σ 2 ε j * i=1 1 hπ i -1 . Since s ′ ≥ (d - 1) max j∈[j * ] τπj , we have   j * i=1 1 2 τπi (d -1) + 4 τπ i hπ i σ 2 (d-1) s ′ ×ε + 2hπ i σ 2 ε   -1 ≤   j * i=1 1 2 τπi (d -1) + 4hπ i σ 2 ε + 2hπ i σ 2 ε   -1 ≤   j * i=1 1 2 τπi (d -1) + 6hπ i σ 2 ε   -1 ≤ 12   j * i=1 min 1 τπi (d -1),1 hπ i σ 2 ε   -1 . If there exists p ∈ [j * ] such that 1 τπp (d-1) < 1 h πp σ 2 ε , then j * i=1 min 1 τπi (d -1),1 hπ i σ 2 ε ≥ 1 τπp (d -1) and   j * i=1 1 2 τπi (d -1) + 4 τπ i hπ i σ 2 (d-1) s ′ ×ε + 2hπ i σ 2 ε   -1 ≤ 12(d -1) τπp ≤ 12(d -1) max j∈[j * ] τπj .Otherwise, we havej * i=1 min 1 τπi (d -1),1 hπ i σ 2 ε = j * i=1 1 hπ i σ 2 ε and   j * i=1 1 2 τπi (d -1) + 4 τπ i hπ i σ 2 (d-1) s ′ ×ε + 2hπ i σ 2 ε   -1 ≤ 12   j * i=1 1 hπ i σ 2 ε   -1 = 12 σ 2 ε   j * i=1 1 h πi   -1.Considering both cases, we have  j * i=1 1 2 τπi (d -1) + 4 τπ i hπ i σ 2 (d-1) s ′ ×ε + 2hπ i σ 2 ε   -1 ≤ 12 max      (d -1) max j∈[j * ] τπj , σ 2 ε   j * i=1 1 h πi   -1      = s ′ .It means that s * ≤ s ′ because s * is the solution of (33). Using (32), we getI * ≤ 12 max      max j∈[j * ] max{h πj , τπj }, max      (d -1) max j∈[j * ] τπj , σ 2 ε   j * i=1 1 h πi   -1           .Using d ≥ 1 and d τπj ≤ max{h πj , d τπj }, we getI * ≤ 12 max      max j∈[j * ] max{h πj , d τπj }, max      max j∈[j * ] max{h πj , d τπj }, σ 2 ε   j * i=1 1 h πi   -1           ≤ 12 max      max j∈[j * ] max{h πj , d τπj }, σ 2 ε   j * i=1 1 h πi   -1      .Due to max j∈[j * ] max{h πj , d τπj } = max{h πj * , d τπ j * } and (31), we obtainI * = t * (d -1, σ 2 /ε, h 1 , τ1 , . . . , h n , τn ) ≤ 12 max      max{h πj * , d τπ j * }, σ 2 ε   j * i=1 1 h πi   -1      ≤ 12t * 0, σ 2 /ε, h 1 , d τ1 , . . . , h n , d τn . Property 6.2. For all K ∈ [1, d], σ 2 /ε, h 1 , τ1 , . . . , h n , τn ≥ 0, we have 24 × t * d /K -1, σ 2 /ε, h 1 , K τ1 , . . . , h n , K τn ≥ t * d -1, σ 2 /ε, h 1 , τ1 , . . . , h n , τn . Proof. (Part 1: K ≤ d+1 2 ) For all K ≤ d+12 , we haveEQUATIONwhere s * (j) is the solution of  j i=1 1 2K τπi d K -1 + 4K τπ i hπ i σ 2 ( d K -1) s×ε + 2hπ i σ 2 ε   -1 = s,and π is a permutation that sorts max{h j , K τj }. Also, assume that j * is a minimizer in (34). For all j ∈ [n], we getEQUATION)At the same time, using Property E.6, we haveEQUATIONwhere s ′ (j * ) is the solution of  j * i=1 1 2 τπi (d -1) + 4 τπ i hπ i σ 2 (d-1) s×ε + 2hπ i σ 2 ε   -1 = s.From (35), we can conclude that 2 × s * (j * ) ≥ s ′ (j * ). Using this and (36), we obtaint * d -1, σ 2 /ε, h 1 , τ1 , . . . , h n , τn ≤ max{ max j∈[j * ] max{h πj , τπj }, 2s * (j * )} ≤ 2 max{ max j∈[j * ] max{h πj , τπj }, s * (j * )} ≤ 2 max{ max j∈[j * ] max{h πj , K τπj }, s * (j * )}. Note that max j∈[j * ] max{h πj , K τπj } = max{h πj * , K τπ j * }, thus t * d -1, σ 2 /ε, h 1 , τ1 , . . . , h n , τn ≤ 2 max{max{h πj * , K τπ j * }, s * (j * )} = 2t * d K -1, σ 2 /ε, h 1 , K τ1 , . . . , h n , K τn . (Part 2: K > d+12 ) For all K > d+1 2 , using Property 6.1, we gett * d K -1, σ 2 /ε, h 1 , K τ1 , . . . , h n , K τn ≥ t * 0, σ 2 /ε, 1 2 h 1 , d 2 τ1 , . . . , 1 2 h n , d 2 τn .Next, using Property E.5, we havet * d K -1, σ 2 /ε, h 1 , K τ1 , . . . , h n , K τn ≥ 1 2 t * 0, σ 2 /ε, h 1 , d τ1 , . . . , h n , d τn .It is left to use Property E.7 to gett * d K -1, σ 2 /ε, h 1 , K τ1 , . . . , h n , K τn ≥ 1 24 t * d -1, σ 2 /ε, h 1 , τ1 , . . . , h n , τn .Example 6.3. [Infinitely Fast Worker] If exists j ∈ [n] such that τ j = 0 and h j = 0, then t * = 0.Proof. Let us take a permutation π where π 1 = j. Such a permutation exists because max{h j , τ j } = 0. By the definition of t * , we haveEQUATIONwhere s * (1) is the solution of1 i=1 1 2τ πi ω + 4τπ i hπ i σ 2 ω sε + 2hπ i σ 2 ε -1 = s. Since 1 i=1 1 2τ πi ω + 4τπ i hπ i σ 2 ω sε + 2hπ i σ 2 ε -1 = 1 i=1 1 0 -1 = (∞) -1 = 0,we obtain s * (1) = 0. We substitute it to (37) to get t * (ω,σ 2 /ε, h 1 , τ 1 , . . . , h n , τ n ) = 0. Example 6.4. [Infinitely Slow Workers] If τ i = ∞ and h i = ∞ for all i ∈ [n], then t * = ∞.Proof. By the definition of t * , we haveEQUATION)Proof. By the definition, we havet * (ω, σ 2 /ε, h 1 , τ 1 , . . . , h n , τ n ) = min j∈[n] max{max{h, τ }, s * (j)} = max{max{h, τ }, min j∈[n]s * (j)} = max{max{h, τ }, s * } (38) where s * is the solution ofn i=1 1 2τ ω + 4τ hσ 2 ω sε + 2hσ 2 ε -1 = s. Since n i=1 1 2τ ω + 4τ hσ 2 ω sε + 2hσ 2 ε -1 = n 2τ ω + 4τ hσ 2 ω sε + 2hσ 2 ε -1 = 2τ ω n + 4τ hσ 2 ω snε + 2hσ 2 nε ,we have to solve and find the non-negative solution of the quadratic equations 2 -s 2τ ω n + 2hσ 2 nε - 4τ hσ 2 ω nε = 0.The solution iss * = τ ω n + hσ 2 nε + τ ω n + hσ 2 nε 2 + 4τ hσ 2 ω nε ≤ 2 τ ω n + hσ 2 nε + τ hσ 2 ω nε .Therefore, we haveEQUATIONwhere π is a permutation that sorts {h i } n i=1 .Proof. By the definition, we have t * (ω,σ 2 /ε, h 1 , τ 1 , . . . , h n , τ n ) = min j∈[n] max{h πj , s * (j)}, where s * (j) is the solution of j i=1 1 2hπ i σ 2 ε -1 = s.Therefore, we havet * (ω, σ 2 /ε, h 1 , τ 1 , . . . , h n , τ n ) ≤ 2 min j∈[n] max    h πj , σ 2 ε j i=1 1 h πi -1    = Θ   min j∈[n]   h πj + σ 2 ε j i=1 1 h πi -1     .Using Lemma F.1, we obtaint * (ω, σ 2 /ε, h 1 , τ 1 , . . . , h n , τ n ) ≤ 2 min j∈[n] max    h πj , σ 2 ε j i=1 1 h πi -1    = Θ   min j∈[n] j + σ 2 ε j i=1 1 h πi -1   .10 From the proof, it is clear that the result is tight up to a constant factor.Lemma F.1. Let us consider the two functionsg(j) := h j + a j i=1 1 h i -1 , p(j) := (j + a) j i=1 1 h i -1for all j ∈ [n], where h i ≥ 0 for all i ∈ [n], a ≥ 0, andh 1 ≤ • • • ≤ h n . Then 1 2 min j∈[n] g(j) ≤ min j∈[n] p(j) ≤ min j∈[n] g(j) Proof. If h 1 = 0, then p(1) = h(1) = 0 and min i∈[n] p(i) = min i∈[n] h(i) = 0. Assume that h 1 > 0.Using the fact that a harmonic mean is less or equal to the maximum, we havemin j∈[n] p(j) = min j∈[n](j + a)j i=1 1 h i -1 ≤ min j∈[n]   h j + a j i=1 1 h i -1   = min j∈[n]g(j).Thus, we proved the upper bound. Next, assume that j * is the smallest minimizer of p(j).If j * = 1, then min j∈[n] p(j) = p(1) = (1 + a) h 1 = h 1 + ah 1 = g(1) ≥ min j∈[n]g(j).Otherwise, if j * > 1, then p(j * ) ≤ p(j * -1). Using simple algebra, we obtain(j * + a)   j * i=1 1 h i   -1 ≤ (j * -1 + a)   j * -1 i=1 1 h i   -1 ⇔ (j * + a)   j * -1 i=1 1 h i   ≤ (j * -1 + a)   j * i=1 1 h i   ⇔   j * i=1 1 h i   ≤ (j * + a) 1 h j * ⇔ h j * ≤ (j * + a)   j * i=1 1 h i   -1.Using the last inequality, we getmin j∈[n] p(j) = (j * + a)   j * i=1 1 h i   -1 = 1 2 (j * + a)   j * i=1 1 h i   -1 + 1 2 (j * + a)   j * i=1 1 h i   -1 ≥ 1 2 h j * + 1 2 a   j * i=1 1 h i   -1 = 1 2 g(j * ) ≥ 1 2 min j∈[n]g(j).Example 6.7. [Ignoring Slow Workers] If h i and τ i are fixed and finite for all i ≤ p, and max{h i , τ i } = m ∈ R for all i > p, then, for m large enough, we have t * (ω,σ 2 /ε, [h i , τ i ] n 1 ) = t * (ω, σ 2 /ε, [h i , τ i ] p 1 ).Proof. By the definition, we havet * (ω, σ 2 /ε, h 1 , τ 1 , . . . , h n , τ n ) = min j∈[n]max{max{h πj , τ πj }, s * (j)}.For m > max i∈[p] max {h i , τ i }, we have max {h i , τ i } < m for all i ≤ p and the set {1, . . . , p} equals to {π 1 , . . . , π p }. Thus, we get t * (ω, σ 2 /ε, h 1 , τ 1 , . . . , h n , τ n ) =(j)} ≥ m > t * (ω, σ 2 /ε, h 1 , τ 1 , . . . , h p , τ p ).Therefore, we havet * (ω, σ 2 /ε, h 1 , τ 1 , . . . , h n , τ n ) = t * (ω, σ 2 /ε, h 1 , τ 1 , . . . , h p , τ p ). Example 6.8. [Partial Participation] If max{h i , τ i } = ∞ for all i > p ≥ 1, then t * (ω, σ 2 /ε, [h i , τ i ] n 1 ) = t * (ω, σ 2 /ε, [h i , τ i ] p 1 ).Proof. By the definition, we havet * (ω, σ 2 /ε, h 1 , τ 1 , . . . , h n , τ n ) = min j∈[n] max{max{h πj , τ πj }, s * (j)},where π is a permutation such that the set {π p+1 , . . . , π n } equals to the set {p + 1, . . . , n}. Such a permutation exists because max{h i , τ i } = ∞ for all i > p. Using this, we havet * (ω, σ 2 /ε, h 1 , τ 1 , . . . , h n , τ n ) = min min j∈[p] max{max{h πj , τ πj }, s * (j)}, min j∈{p+1,...,n} max{max{h πj , τ πj }, s * (j)} = min min j∈[p] max{max{h πj , τ πj }, s * (j)}, ∞ = min j∈[p]max{max{h πj , τ πj }, s * (j)} = t * (ω, σ 2 /ε, h 1 , τ 1 , . . . , h p , τ p ).We prove the following generic lemma that estimates the variance of the general family of unbiased gradient estimators. Lemma G.1. Consider that Assumptions 1.3 and 2.2 hold. Let us consider the gradient estimatorg k = 1 n i=1 mi j=1 w ij b ij n i=1 mi j=1 w ij C ij   bij l=1 ∇f (x k ; ξ k il )   ,wherem i ≥ 0 for all i ∈ [n], b ij ≥ 0 for all i ∈ [n] and j ∈ [m i ] are ordered batch sizes (b i1 ≤ • • • ≤ b i,mi for all i ∈ [n]), w ij ≥ 0 are weights for all i ∈ [n] and j ∈ [m i ],andEQUATIONProof. First, we show the gradient estimator is unbiased:E g k = E   1 n i=1 mi j=1 w ij b ij n i=1 mi j=1 w ij C ij   bij l=1 ∇f (x k ; ξ k il )     = 1 n i=1 mi j=1 w ij b ij n i=1 mi j=1 w ij E   C ij   bij l=1 ∇f (x k ; ξ k il )     .Using Def. 2.1 and Assumption 1.3, we haveE g k = 1 n i=1 mi j=1 w ij b ij n i=1 mi j=1 w ij b ij ∇f (x k ) = ∇f (x k ).Next, we estimate the varianceE g k -∇f (x k ) 2 = E   1 n i=1 mi j=1 w ij b ij n i=1 mi j=1 w ij C ij   bij l=1 ∇f (x k ; ξ k il )   -∇f (x k )   = 1 n i=1 mi j=1 w ij b ij 2 E    n i=1 mi j=1 w ij C ij   bij l=1 ∇f (x k ; ξ k il )   - n i=1 mi j=1 w ij b ij ∇f (x k ) 2    .Using the independence and ( 22), we haveE g k -∇f (x k ) 2 = 1 n i=1 mi j=1 w ij b ij 2 n i=1 E    mi j=1 w ij C ij   bij l=1 ∇f (x k ; ξ k il )   - mi j=1 w ij b ij ∇f (x k ) 2    = 1 n i=1 mi j=1 w ij b ij 2 n i=1 E    mi j=1 w ij C ij   bij l=1 ∇f (x k ; ξ k il )   - mi j=1 w ij bij l=1 ∇f (x k ; ξ k il ) 2    I1 + 1 n i=1 mi j=1 w ij b ij 2 n i=1 E    mi j=1 w ij bij l=1 ∇f (x k ; ξ k il ) - mi j=1 w ij b ij ∇f (x k ) 2    I2 .(40) Using the independence of the compressors and Def. 2.1, we getI 1 = 1 n i=1 mi j=1 w ij b ij 2 n i=1 mi j=1 w 2 ij E    C ij   bij l=1 ∇f (x k ; ξ k il )   - bij l=1 ∇f (x k ; ξ k il ) 2    ≤ 1 n i=1 mi j=1 w ij b ij 2 n i=1 mi j=1 w 2 ij ω ij E    bij l=1 ∇f (x k ; ξ k il ) 2    .In the view of ( 22), the independence of the stochastic gradients, and Assumption 1.3, we obtainI 1 ≤ 1 n i=1 mi j=1 w ij b ij 2 n i=1 mi j=1 w 2 ij ω ij E    bij l=1 ∇f (x k ; ξ k il ) - bij l=1 ∇f (x k ) 2    + 1 n i=1 mi j=1 w ij b ij 2 n i=1 mi j=1 w 2 ij ω ij b 2 ij ∇f (x k ) 2 = 1 n i=1 mi j=1 w ij b ij 2 n i=1 mi j=1 w 2 ij ω ij bij l=1 E ∇f (x k ; ξ k il ) -∇f (x k ) 2 + 1 n i=1 mi j=1 w ij b ij 2 n i=1 mi j=1 w 2 ij ω ij b 2 ij ∇f (x k ) 2 ≤ 1 n i=1 mi j=1 w ij b ij 2 n i=1 mi j=1 w 2 ij b ij ω ij σ 2 + 1 n i=1 mi j=1 w ij b ij 2 n i=1 mi j=1 w 2 ij b 2 ij ω ij ∇f (x k ) 2 .We now considerI 2 = 1 n i=1 mi j=1 w ij b ij 2 n i=1 E    mi j=1 w ij bij l=1 ∇f (x k ; ξ k il ) - mi j=1 w ij b ij ∇f (x k ) 2    .Let us consider the setS il := {j ∈ [m i ] | l ≤ b ij } for all i, l ∈ N.Then we can rewrite the norm in the following wayI 2 = 1 n i=1 mi j=1 w ij b ij 2 n i=1 E    bi,m i l=1   j∈S il w ij   ∇f (x k ; ξ k il ) -∇f (x k ) 2    .The stochastic vectors are independent, thusI 2 = 1 n i=1 mi j=1 w ij b ij 2 n i=1 bi,m i l=1   j∈S il w ij   2 E ∇f (x k ; ξ k il ) -∇f (x k ) 2 ≤ 1 n i=1 mi j=1 w ij b ij 2 n i=1 bi,m i l=1   j∈S il w ij   2 σ 2 . Note that bi,m i l=1   j∈S il w ij   2 = bi,m i l=1 j∈S il p∈S il w ij w ip .The number of appearances of the term w ij w ip in the sum equals to min{b ij , b ip }. ThusI 2 ≤ 1 n i=1 mi j=1 w ij b ij 2 n i=1 mi j=1 mi p=1 min{b ij , b ip }w ij w ip σ 2 .We now substitute the bounds on I 1 and I 2 to (40), and get (39).Algorithm 4 Shadowheart SGD (Alg. 1 is equivalent to Alg. 4 when h k i = h k and τ k i = τ k ) 1: Input: starting point x 0 , stepsize γ, the ratio σ 2 /ε 2: for k = 0, 1, . . . , K -1 do 3:Find the maximum computation speeds h k i > 0 and compressors' communication speeds τ k i > 0 of the workers in the current iteration 4:Find the equilibrium time t * using Def. 3.1 with h k i and τ k for i ∈ S A in parallel do 11: w i (a) = b i ω + ω σ 2 ε + m i σ 2 ε -112:for j = 1, . . . , m i do 13:Receive C ij g k i from the i th worker 14:g k = g k + w i C ij g k i 15:end for 16:end for 17:g k = g k / ( n i=1 w i m i b i )18:x k+1 = x k -γg k 19: end for (a) : If ω = 0 and σ 2 ε = 0, then w i = 1H Proofs for Algorithms 1 and 4In the appendix, we work with Alg. 4 instead of Alg. 1. Alg. 4 is more general and estimates all the parameters based on local per-iteration times h k i and τ k i instead of h i and τ i . All results for Alg. 1 can be easily obtained by taking h k i = h i and τ k i = τ i . Lemma H.1. Consider that Assumptions 1.3 and 2.2 hold. Then the gradient estimator (9) with the weights w i from Alg. 4 is unbiased andEQUATIONProof. Alg. 4 implements the gradient estimator (9). We can use Lemma G.1 with b ij = b i , w ij = w i and ω ij = ω for all i ∈ [n] and j ∈ [m i ]. Using (39), we haveE g k -∇f (x k ) 2 ≤ 1 n i=1 mi j=1 w ij b ij 2 n i=1 mi j=1 w 2 ij b 2 ij ω ij ∇f (x k ) 2 + 1 n i=1 mi j=1 w ij b ij 2 n i=1   mi j=1 w 2 ij b ij ω ij σ 2 + mi j=1 mi p=1 min{b ij , b ip }w ij w ip σ 2   = 1 ( n i=1 m i w i b i ) 2 n i=1 w 2 i m i b 2 i ω ∇f (x k ) 2 + 1 ( n i=1 m i w i b i ) 2 n i=1 w 2 i m i b i ωσ 2 + b i m 2 i σ 2 .We add nonnegative terms to the last inequality to obtainE g k -∇f (x k ) 2 ≤ 1 ( n i=1 m i w i b i ) 2 n i=1 w 2 i m i b 2 i ω + m i b i ω σ 2 ε + b i m 2 i σ 2 ε ∇f (x k ) 2 + 1 ( n i=1 m i w i b i ) 2 n i=1 w 2 i m i b 2 i ωε + m i b i ωσ 2 + b i m 2 i σ 2 = 1 ( n i=1 m i w i b i ) 2 n i=1 w 2 i m i b 2 i ω + m i b i ω σ 2 ε + b i m 2 i σ 2 ε ∇f (x k ) 2 + ε .Using the choice of the weights w i , we get (41).Lemma H.2. Consider two quantities ω ≥ 0 and σ 2 /ε ≥ 0, and n ∈ N. Also, consider a sequence of positive pairs {(h i , τ i )} n i=1 . We take b i = t * hi and m i = t * τi for all i ∈ [n], where t * ≡ t * ω, σ 2 /ε, h 1 , τ 1 , . . . , h n , τ n is the equilibrium time from Def. 3.1. Theni : bi∧mi>0 b i m i b i ω + ω σ 2 ε + m i σ 2 ε -1 ≤ 1.Proof. Assume that j * ∈ [n] is the smallest index that minimizes max{max{h πj , τ πj }, s * (j)}, thenEQUATIONTherefore, we have t * ≥ max{h π j * , τ π j * } ≥ max{h πj , τ πj } for all j ≤ j * since max{h πj , τ πj } are sorted. It means that b πj = t * hπ j ≥ 1 and m πj = t * τπ j≥ 1 for all j ≤ j * . Using this, we haveI := i : bi∧mi>0 b i m i b i ω + ω σ 2 ε + m i σ 2 ε -1 ≤   j * i=1 b πi m πi b πi ω + ω σ 2 ε + m πi σ 2 ε   -1 =   j * i=1 1 ω mπ i + ωσ 2 bπ i mπ i ε + σ 2 bπ i ε   -1 . Since b πj = t * hπ j ≥ 1 and m πj = t * τπ j≥ 1, we can also conclude that b πj ≥ t * 2hπ j and m πj ≥ t * 2τπ j for all j ≤ j * . Therefore, we obtainI ≤   j * i=1 1 2τπ i ω t * + 4τπ i hπ i ωσ 2 (t * ) 2 ε + 2hπ i σ 2 t * ε   -1 ≤   j * i=1 1 2τπ i ω s * (j * ) + 4τπ i hπ i ωσ 2 (s * (j * )) 2 ε + 2hπ i σ 2 s * (j * )ε   -1 = 1 s * (j * )   j * i=1 1 2τ πi ω + 4τπ i hπ i ωσ 2 s * (j * )×ε + 2hπ i σ 2 ε   -1.where the last inequality follows from (42). Recall that s * (j * ) is the solution of the equation ( 7). Thus  j * i=1 1 2τ πi ω + 4τπ i hπ i ωσ 2 s * (j * )×ε + 2hπ i σ 2 ε   -1 = s * (j * )andI ≤ 1 s * (j * ) × s * (j * ) = 1.Theorem H.3. Assume that Assumptions 1.1, 1.2, 1.3, 2.2 hold. Let us take γ = 1 2L in Alg. 4. Then for all iterationsEQUATIONAlg. 4 guarantees that 1K K-1 k=0 E ∇f (x k ) 2 ≤ ε.Proof. Let us fix any iteration k ∈ N. Consider that G k is a σ-algebra generated by g 0 , . . . , g k-1 . Then, given G k , x k is a deterministic vector. Using Lemma H.1, we haveE g k -∇f (x k ) 2 G k ≤ i : bi∧mi>0 b i m i b i ω + ω σ 2 ε + m i σ 2 ε -1 ∇f (x k ) 2 + ε .Note that the choice of the parameters in Alg. 4 satisfy the conditions of Lemma H.2. Thus, we haveE g k -∇f (x k ) 2 G k ≤ ∇f (x k ) 2 + ε for all k ≥ 0.It is left to use the standard SGD analysis from Theorem I.1 with B = 1 and C = ε to finish the proof.Theorem 4.2. Lett Assumptions 1.1, 1.2, 1.3, 2.2 hold. Let us take γ = 1/2L in Shadowheart SGD (Alg. 1). Then as long as K ≥ 16L∆/ε, we have the guarantee1 K K-1 k=0 E ∇f (x k ) 2 ≤ ε.Proof. It immediately follows from Theorem H.3 for h i = h k i and τ i = τ k i . Theorem 4.4. Alg. 4 converges after⌈ 16L∆ ε ⌉ k=0 2t * (ω, σ 2 /ε, h k 1 , τ k 1 , . . . , h k n , τ k n ) (11)seconds, where h k i > 0 and τ k i > 0 are computation and communication times for worker i in iteration k.In every iteration, every worker calculates b i stochastic gradients and sends m i compressed vectors. Thus, the processing time of each iteration is not greater thanEQUATIONUsing the fact that the number of iterations equals to (43), we finally get (11).Corollary 4.3. Shadowheart SGD (Alg. 1) converges after at most T * seconds, whereEQUATIONProof. It immediately follows from Theorem 4.4 for h i = h k i and τ i = τ k i .Let us consider a slightly modified classical SGD result from (Ghadimi and Lan, 2013; Khaled and Richtárik, 2020) . Theorem I.1. Assume that Assumptions 1.1 and 1.2 hold. We consider the SGD method:EQUATIONFor all k ≥ 0, the vector g(x) is a random vector such thatEQUATIONwhere G k is a σ-algebra generated by g(x 0 ), . . . , g(x k-1 ). The quantities B and C are arbitrary nonnegative constants. Then1 K K-1 k=0 E ∇f (x k ) 2 ≤ ε for K ≥ 4L∆(1 + B) ε + 8L∆C ε 2 .Proof. From Assumption 1.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 (45), 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γ(1 + B) 2 ∇f (x k ) 2 + Lγ 2 C 2 . Since γ ≤ 1 L(1+B) , we get E f (x k+1 ) G k ≤ f (x k ) - γ 2 ∇f (x k ) 2 + Lγ 2 C 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 C 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 C 2 = ∆ - K-1 k=0 γ 2 E ∇f (x k ) 2 + KLγ 2 C 2 .Finally, we rearrange the terms and use that E f (x K ) -f * ≥ 0:1 K K-1 k=0 E ∇f (x k ) 2 ≤ 2∆ γK + LγC.The choice of γ and K ensures that1 K K-1 k=0 E ∇f (x k ) 2 ≤ ε.In the following proofs, we use assumptions and definitions from Sec. 7.Comparison 7.1. T * = O(T MB ).Proof. Without loss of generality, we assume that all workers are sorted by max{h i , τi }. For the Rand1 compressor, we have ω = d -1. From Corollary 4.3, we know that the time complexity of Alg. 1 isT * := L∆ ε × t * (ω, σ 2 /ε, h 1 , τ1 , . . . , h n , τn )up to a constant factor. Using Def. 3.1 of t * , we haveEQUATIONwhere s * (n) is the solution ofEQUATION)Let us take s ′ = 12 max i∈[n] max hiσ 2 nε , ω τi . Using simple bounds, we haven i=1 1 2 τi ω + 4 τihiσ 2 ω s ′ ×ε + 2hiσ 2 ε -1 ≤   n max i∈[n] 2 τi ω + 4 τihiσ 2 ω s ′ ×ε + 2hiσ 2 ε   -1 = max i∈[n] 2 τi ω + 4 τihiσ 2 ω s ′ ×ε + 2hiσ 2 ε n . Since s ′ ≥ ω max i∈[n] τi , we get n i=1 1 2 τi ω + 4 τihiσ 2 ω s ′ ×ε + 2hiσ 2 ε -1 ≤ max i∈[n] 2 τi ω + 4hiσ 2 ε + 2hiσ 2 ε n ≤ 12 max i∈[n] max hiσ 2 ε , ω τi n ≤ s ′ .It means that s * (n) ≤ s ′ since s * (n) is the solution of (47). Using the properties of max and (46), we getT * = O max max{h n , τn }, max i∈[n] max h i σ 2 nε , ω τi × L∆ ε = O max max i∈[n] (h i + (ω + 1) τi ) , max i∈[n] h i σ 2 nε + max i∈[n] ω τi × L∆ ε = O max max i∈[n] (h i + (ω + 1) τi ) × L∆ ε , max i∈[n] h i × σ 2 L∆ nε 2 , max i∈[n] (ω + 1) τi × L∆ ε = O max i∈[n] (h i + (ω + 1) τi ) L∆ ε + σ 2 L∆ nε 2 = O max i∈[n] (h i + d τi ) L∆ ε + σ 2 L∆ nε 2 ,where we use ω + 1 = d.Comparison 7.2. T * = O(T R ).Proof. From Sec. 7, we know thatT * := L∆ ε × t * (ω, σ 2 /ε, h 1 , τ1 , . . . , h n , τn )andT R := L∆ ε × t * (0, σ 2 /ε, h 1 , d τ1 , . . . , h n , d τn ).Using Property E.7, we get T * = O(T R ) since ω = d -1 for Rand1.In this section, we provide the modification of Alg. 4 with the EF21-P mechanism (Gruntkowska et al., 2023) . Almost all steps are the same as in Alg. 4 except for the EF21-P mechanism (we mark the main changes with the color).Algorithm 5 Bidirectional Shadowheart SGD 1: Input: starting point x 0 , stepsize γ, the ratio σ 2 /ε 2: for k = 0, 1, . . . , K -1 do 3:Find the current computation speeds h k i > 0 and communication speeds τ k i > 0 of the workers 4:Find the equilibrium time t * using Def. 3.1 5:Set b i = t * h k i and m i = t * τ k i for all i ∈ [n] 6:Find active workersS A = {i ∈ [n] : b i ∧ m i > 0} 7:Run Alg. 6 in all workers 8:Broadcast b i , and m i to all workers 9:Init g k = 010:for i ∈ S A in parallel do 11: w i (a) = b i ω + ω σ 2 ε + m i σ 2 ε -112:for j = 1, . . . , m i do 13:Receive C ij g k i from the i th worker 14:g k = g k + w i C ij g k i 15:end for 16:end for 17:g k = g k / ( n i=1 w i m i b i )18:x k+1 = x k -γg k 19:p k+1 = C serv (x k+1 -w k ) 20:w k+1 = w k + p k+1Broadcast p k+1 to all workers 22: end for (a) : If ω = 0 and σ 2 ε = 0, then w i = 1Algorithm 6 i th Worker's Strategy (init all workers with w 0 = x 0 ) 1: Receive b i , and m i from the server 2:if b i ∧ m i > 0 then 3: Init g k i = 0 4: for l = 1, . . . , b i do 5: Calculate ∇f (w k ; ξ k il ), ξ k il ∼ D ξ 6: g k i = g k i + ∇f (w k ; ξ k il ) 7:end for 8:for j = 1, . . . , m i do9: Send C ij g k i ≡ C g k i ; ν k ij to the server, ν k ij ∼ D ν , C ij ∈ U(ω) 10:end for 11: end if 12: Receive p k+1 from the server 13: w k+1 = w k + p k+1 L Proofs for Alg. 5 Theorem A.2. Let Assumptions 1.1, 1.2, 1.3, 2.2 hold. Choose γ = α 16L . Then as long as K ≥ 768L∆ αε , Bidirectional Shadowheart SGD (Alg. 5) guarantees to find an ε-stationary point.Proof. In the bidirectional setting, the idea of proof is the same as in Theorem H.3. Let us fix any iteration k ∈ N. The gradient estimator has the same structure as (9) but with w k instead of x k :g k = 1 n i=1 w i m i b i n i=1 w i mi j=1 C ij bi l=1 ∇f (w k ; ξ k il ) ,Consider that G k is a σ-algebra generated by all random variables from the iterations 0, . . . , k -1.Then, given G k , w k is a deterministic vector. Using Lemma H.1 with x k ≡ w k and Lemma H.2, we haveE g k -∇f (w k ) 2 G k ≤ ∇f (w k ) 2 + ε for all k ≥ 0.It is left to use Theorem E.3 from (Gruntkowska et al., 2023) with B = 2 and C = ε to ensure that min 0≤k≤K-1 E ∇f (x k ) 2 ≤ ε after 768L∆ αε iterations.Corollary A.3. If the broadcast time of C serv is not greater than τ serv , then Bidirectional Shadowheart SGD (Alg. 5) converges after at mostEQUATIONseconds.Proof. Let us fix an iteration index k ∈ [n]. In every iteration, the server broadcasts one compressed vector, every worker calculates b i stochastic gradients and sends m i compressed vectors. Thus, the processing time of each iteration is not greater thanτ serv + max i∈[n] h k i b i + τ k i m i = τ serv + max i∈[n] h k i t * h k i + τ k i t * τ k i ≤ τ serv + 2t * (ω, σ 2 /ε, h k 1 , τ k 1 , . . . , h k n , τ k n ) P.6.1 ≤ τ serv + 2t * (ω, σ 2 /ε, h 1 , τ 1 , . . . , h n , τ n ).Using the converge rate from Theorem A.2, we finally get (20).Comparison A.5. Assume that it takes τserv seconds to send one coordinate from the server to the workers. If we take K ≥ min d, t * (ω, σ 2 /ε, [h i , τ i ] n 1 )/ τserv in TopK, then T * ,serv = O (T * ) .Proof. From the assumption, we have τ serv = K τserv and τ full serv = d τserv . For TopK, α ≥ K /d. Therefore, up to a constant factor, we obtainT * ,serv = L∆ αε × τ serv + t * (ω, σ 2 /ε, [h i , τ i ] n 1 ) ≤ dL∆ Kε × K τserv + t * (ω, σ 2 /ε, [h i , τ i ] n 1 ) = dL∆ ε τserv + dL∆ Kε t * (ω, σ 2 /ε, [h i , τ i ] n 1 ) ≤ dL∆ ε τserv + max dL∆ ε τserv , L∆ ε t * (ω, σ 2 /ε, [h i , τ i ] n 1 ) ≤ 2 dL∆ ε τserv + L∆ ε t * (ω, σ 2 /ε, [h i , τ i ] n 1 ) .Also, up to a constant factor, we haveT * = L∆ ε × (τ full serv + t * (ω, σ 2 /ε, [h i , τ i ] n 1 )) = L∆ ε × (d τserv + t * (ω, σ 2 /ε, [h i , τ i ] n 1 )) = dL∆ ε τserv + L∆ ε t * (ω, σ 2 /ε, [h i , τ i ] n 1 ).Therefore, T * ,serv = O (T * ) .Algorithm 7 Adaptive Shadowheart SGD 1: Input: starting point x 0 , stepsize γ, the ratio σ 2 /ε 2: for k = 0, 1, . . . , K -1 do Initl i = 0 for all i ∈ [n] 6: while   i : li>0 li j=1 ω l 2 i mij + ωσ 2 l 3 i mij ε + σ 2 liε -1   -1 > 1 4 do 7:Receive C i,li,m i,l i (g i ) , l i and m i,li from some worker (we indicate this worker with i)8:if m i,li = 1 and l i > 1 then 9:ḡi = ḡi + 1 m i,(l i -1) ĝi and ĝi = 010: end if 11: ĝi = ĝi + C i,li,m i,l i (g i ) 12:end while 13:Init g k = 014:for i ∈ [n] : l i > 0 do 15: ḡi = ḡi + 1 m i,l i ĝi 16: w i (a) = li j=1 ω mij + li j=1 ωσ 2 limij ε + liσ 2 ε -117:g k = g k + w i ḡi 18:end for 19:g k = g k / i : li>0 w i li j=1 j 20:x k+1 = x k -γg k 21: end for (a) : If ω = 0 and σ 2 ε = 0, then w i = 1In this section, we design a new method that, unlike Alg. 1 and 4, does not require the bounds on computations times. It automatically understands when to stop the collection of compressed vectors in g k .Let us consider Alg. 7, which we call Adaptive Shadowheart SGD. It implements the following gradient estimator:EQUATION)The idea is that each worker calculate and send compressed vectors in parallel: while the next stochastic gradients ∇f (x k ; ξ k i,j+1 ) are calculating, the workers are sending C ij• j r=1 ∇f (x k ; ξ k ir ) to server. The main difficulty is to understand when to stop. It turns out that it is sufficient to wait for the moment when the condition in Line 6 of Alg. 7 does not hold. For this method, we can prove the following guarantees.Theorem M.1. Let Assumptions 1.1, 1.2, 1.3, 2.2 hold. Let us take γ = 1 2L in Alg. 7. Then for all iterations K ≥ 16L∆ ε , Alg. 7 guarantees that 1K K-1 k=0 E ∇f (x k ) 2 ≤ ε.Corollary 4.6. If the computation and communication times are positive, the time complexity of Alg. 7 is L∆ ε × t * (ω, σ 2 /ε, [max{h i , τ i }, min {τ i r i , max{h i , τ i }}] n 1 ) up to a constant factor, where r i is defined in Def. 4.5.Algorithm 8 i th Worker's Strategy1: Receive x k from the server 2: Init l i = 1 3: Calculate g i = ∇f (x k ; ξ k i1 ), ξ k i1 ∼ D ξ 4: while True do 5: Start calculating ∇f (x k ; ξ k i,li+1), ξ k i,li+1 ∼ D ξ , and go to the next step 6:Init m i,li = 0 7:while ∇f (x k ; ξ k i,li+1 ) is not calculated OR m i,li = 0 do 8: m i,li = m i,li + 1 9:Send C i,li,m i,l i (g i ) , l i and m i,li to the server, C i,li,m i,l i ∈ U(ω)10:end while 11:g i = g i + ∇f (x k ; ξ k i,li+1)12:l i = l i + 1 13: end while N Proofs for Alg. 7Lemma N.1. Consider that Assumptions 1.3 and 2.2 hold. Then the gradient estimator (48) with the parameters from Alg. 7 is unbiased andEQUATIONProof. Alg. 7 implements the gradient estimator (48). Note that since C ijp ∈ U(ω), then1 mij mij p=1 C ijp ∈ U( ω /mij). Therefore, we can use Lemma G.1 with ω ij = ω /mij, b ij = j, w ij = w i ,and m i = l i , and getE g k -∇f (x k ) 2 ≤ 1 n i=1 w i li j=1 j 2 n i=1 w 2 i li j=1 j 2 ω m ij ∇f (x k ) 2 + 1 n i=1 w i li j=1 j 2 n i=1 w 2 i   li j=1 jωσ 2 m ij + li j=1 li p=1 min{j, p}σ 2   . Since li j=1 li p=1 min{j, p} ≤ l 3 i , we have E g k -∇f (x k ) 2 ≤ 1 n i=1 w i li j=1 j 2 n i=1 w 2 i li j=1 j 2 ω m ij ∇f (x k ) 2 + 1 n i=1 w i li j=1 j 2 n i=1 w 2 i   li j=1 jωσ 2 m ij + l 3 i σ 2   .We add nonnegative terms to the last inequality to obtainE g k -∇f (x k ) 2 ≤ 1 n i=1 w i li j=1 j 2 n i=1 w 2 i   li j=1 j 2 ω m ij + li j=1 jω m ij σ 2 ε + l 3 i σ 2 ε   ∇f (x k ) 2 + 1 n i=1 w i li j=1 j 2 n i=1 w 2 i   li j=1 j 2 ωε m ij + li j=1 jωσ 2 m ij + l 3 i σ 2   = 1 n i=1 w i li j=1 j 2 n i=1 w 2 i   li j=1 j 2 ω m ij + li j=1 jω m ij σ 2 ε + l 3 i σ 2 ε   ∇f (x k ) 2 + ε . Using li j=1 j ≥ l 2 i 2 ,we obtainE g k -∇f (x k ) 2 ≤ 4 ( n i=1 w i l 2 i ) 2 n i=1 w 2 i   li j=1 j 2 ω m ij + li j=1 jω m ij σ 2 ε + l 3 i σ 2 ε   ∇f (x k ) 2 + ε .In the last two sums, we bound the terms j with l i to getE g k -∇f (x k ) 2 ≤ 4 ( n i=1 w i l 2 i ) 2 n i=1 w 2 i   li j=1 l 2 i ω m ij + li j=1 l i ω m ij σ 2 ε + l 3 i σ 2 ε   ∇f (x k ) 2 + ε .It is left to use the choice of the weights w i to obtain (49).Theorem M.1. Let Assumptions 1.1, 1.2, 1.3, 2.2 hold. Let us take γ = 1 2L in Alg. 7. Then for all iterations K ≥ 16L∆ ε , Alg. 7 guarantees that 1K K-1 k=0 E ∇f (x k ) 2 ≤ ε.Proof. The proof of this theorem is very close to the proof of Theorem H.3. Let us fix any iteration k ∈ N. Consider that G k is a σ-algebra generated by g 0 , . . . , g k-1 . Then, given G k , x k is a deterministic vector. Using Lemma N.1, we haveE g k -∇f (x k ) 2 G k ≤ 4    i∈[n] : li>0   li j=1 ω l 2 i m ij + li j=1 ωσ 2 l 3 i m ij ε + σ 2 l i ε   -1    -1 ∇f (x k ) 2 + ε .The algorithm is constructed in such a way that the first bracket in the last inequality is less or equal to 1 (see Line 6 in Alg. 7). ThusE g k -∇f (x k ) 2 G k ≤ ∇f (x k ) 2 + ε for all k ≥ 0.It is left to use the standard SGD analysis from Theorem I.1 with B = 1 and C = ε to ensure that the algorithm converges after 16L∆ ε iterations.Corollary 4.6. If the computation and communication times are positive, the time complexity of Alg. 7 isL∆ ε × t * (ω, σ 2 /ε, [max{h i , τ i }, min {τ i r i , max{h i , τ i }}] n 1) up to a constant factor, where r i is defined in Def. 4.5.Proof. Let us fix an iteration and take k ∈ [K]. It is sufficient to find a time required to send enough compressed vectors such that the inequality4    i∈[n] : li>0   li j=1 ω l 2 i m ij + li j=1 ωσ 2 l 3 i m ij ε + σ 2 l i ε   -1    -1 ≤ 1holds. As soon as this inequality holds, the algorithm stops the loop in Line 6 from Alg. 7. Then the upper bound on the time complexity equals to the number of iterations × the upper bound on the time of each iteration. The previous inequality is equivalent toEQUATION)Let us show thatt ′ := 128 × t * (ω, σ 2 /ε, max{h 1 , τ 1 }, min {τ 1 r 1 , max{h 1 , τ 1 }} , . . . , max{h n , τ n }, min {τ n r n , max{h n , τ n }})is a sufficient time such that (50) holds.By the definition of the equilibrium time t * , in order to apply this mapping, we first have to find a permutation π that sorts the input pairs (max{h i , τ i }, min {τ i r i , max{h i , τ i }}) bymax {max{h i , τ i }, min {τ i r i , max{h i , τ i }}} .This term equals to max{h i , τ i }. Without loss of generality, we assume that the sequence max{h i , τ i } is sorted, thusπ i = i for all i ∈ [n]. Therefore, we haveEQUATIONwhere s * (j) is the solution of the equationj i=1 2 min {τ i r i , max{h i , τ i }} ω + 4 min {τ i r i , max{h i , τ i }} max{h i , τ i }σ 2 ω sε + 2 max{h i , τ i }σ 2 ε -1 -1 = s (52) for all j ∈ [n].Let us define j * as the smallest by index minimizer in (51). Thent ′ = 128 max{max{h j * , τ j * }, s * (j * )}.Assume that l i is the number of iterations (the number of calculated stochastic gradients) that the i th worker does by the time t ′ . Since t ′ ≥ 4 max{h j * , τ j * } and the workers are sorted by max{h i , τ i }, we have t ′ ≥ 2 (h i + τ i ) for all i ≤ j * . Therefore, for all i ≤ j * , the i th worker will have time to calculate and send at least one compressed vector, i.e., l i ≥ 1 for i ≤ j * .Next, the i th worker requires at most τ i seconds to send a compressed vector and it waits for at least one calculated gradient. Consider that the computation time of the j th stochastic gradient in the k th iteration equals toh k ij . Thus t ′ 2 ≤ li j=1 h k ij + τ i . Indeed, if t ′ 2 > li j=1 h k ij + τ i ,then the i th worker will have time to calculate and send at least one more compressed vector because t ′ 2 ≥ 2 max{h i , τ i } ≥ h i + τ i for all i ≤ j * . It would contradict the definition of l i . Therefore, we haveEQUATION)At the same time, by the definition of l i , we havet ′ h min ≥ l i ,because h min > 0 is the smallest possible calculating time. Therefore, we havel i ≤ l max := t max h min ,where t max is defined in Def. 4.5 (t max ≥ t ′ ). Since l i ≥ 1 for all i ≤ j * , we getEQUATION)Using ( 53), we obtainB := 4σ 2 εl i ≤ 8σ 2 max j∈[li] h k ij + τ i εt ′ ≤ 8σ 2 (h i + τ i ) εt ′ ≤ 16σ 2 max{h i , τ i } εt ′ .For every j th stochastic gradient, the i th worker sends at least one compressed vector orh k ij τicompressed vectors because it is possible that τ i ≤ h k ij , then the worker will have time to send more than one compressed vector. Therefore, we havem ij ≥ max h k ij τ i , 1 ≥ max h k ij 2τ i , 1 ≥ max    min j∈[li] h k ij 2τ i , 1    .and1 l i li j=1 1 m ij ≤ 2 l i li j=1 min    τ i min j∈[li] h k ij , 1    = 2 min    τ i min j∈[li] h k ij , 1    .Using the last inequality and (53), we get1 l 2 i li j=1 1 m ij ≤ 4 max j∈[li] h k ij + τ i t ′ min    τ i min j∈[li] h k ij , 1    ≤ 8 max{max j∈[li] h k ij , τ i } t ′ min    τ i min j∈[li] h k ij , 1    = min    8τ i t ′ × max{max j∈[li] h k ij , τ i } min j∈[li] h k ij , 8 max{max j∈[li] h k ij , τ i } t ′    T . It is clear that T ≤ 8 max{ max j∈[l i ] h k ij ,τi} t ′ . If τ i < min j∈[li] h k ij , then T = 8τi t ′ × max j∈[l i ] h k ij min j∈[l i ] h k ij . If τ i ≥ min j∈[li] h k ij and τ i < max j∈[li] h k ij , then T = 8 max j∈[l i ] h k ij t ′ ≤ 8τi t ′ × max j∈[l i ] h k ij min j∈[l i ] h k ij . If τ i ≥ max j∈[li] h k ij , then T = 8τi t ′ ≤ 8τi t ′ × max j∈[l i ] h k ij min j∈[l i ] h k ij .Thus, we have1 l 2 i li j=1 1 m ij ≤ min    8τ i t ′ × max j∈[li] h k ij min j∈[li] h k ij , 8 max{max j∈[li] h k ij , τ i } t ′    ≤ min    8τ i t ′ × sup j∈[lmax] h k ij inf j∈[lmax] h k ij , 8 max{max j∈[li] h k ij , τ i } t ′    ≤ min 8τ i r i t ′ , 8 max{h i , τ i } t ′ ,where we use the definition of r i . Using the last inequality and l i ≥ t ′ 4 max{hi,τi} , we haveA := 4 li j=1 ω m ij l 2 i + 4 li j=1 ωσ 2 m ij εl 3 i ≤ 32ω min {τ i r i , max{h i , τ i }} t ′ + 32ωσ 2 min {τ i r i , max{h i , τ i }} εt ′ l i ≤ 32ω min {τ i r i , max{h i , τ i }} t ′ + 128ωσ 2 min {τ i r i , max{h i , τ i }} max{h i , τ i } ε (t ′ ) 2 ,where we use ( 53) and maxj∈[li] h k ij ≤ h i .One can substitute the bounds on A and B to ( 54) and obtainH ≥ 1 128 j * i=1 ω min {τ i r i , max{h i , τ i }} t ′ + ωσ 2 min {τ i r i , max{h i , τ i }} max{h i , τ i } ε (t ′ ) 2 + σ 2 max{h i , τ i } εt ′ -1 . Note that t ′ ≥ 128s * (j * ), thus H ≥ j * i=1 ω min {τ i r i , max{h i , τ i }} s * (j * ) + ωσ 2 min {τ i r i , max{h i , τ i }} max{h i , τ i } ε (s * (j * )) 2 + σ 2 max{h i , τ i } εs * (j * ) -1 ≥ j * i=1 2ω min {τ i r i , max{h i , τ i }} s * (j * ) + 4ωσ 2 min {τ i r i , max{h i , τ i }} max{h i , τ i } ε (s * (j * )) 2 + 2σ 2 max{h i , τ i } εs * (j * ) -1 = s * (j * ) × j * i=1 2ω min {τ i r i , max{h i , τ i }} + 4ωσ 2 min {τ i r i , max{h i , τ i }} max{h i , τ i } εs * (j * ) + 2σ 2 max{h i , τ i } ε -1.It is left to use the definition of s * (j * ) (see ( 52)) to obtain that H ≥ s * (j * ) × 1 s * (j * ) = 1. It means that after at most t ′ seconds, we can ensure that the algorithm will finish the loop in Line 6 from Alg. 7. In the view of Theorem M.1, the time complexity is less or equal to K × t ′ .We prove the lower bound by generalizing the time multiple oracles protocol from (Tyurin and Richtárik, 2023c) . Note that in the classical approaches (Nemirovskij and Yudin, 1983; Carmon et al., 2020; Arjevani et al., 2022; Nesterov, 2018) , the researchers bound the number of oracle calls required to find an ε-solution. Our approach is based on the idea from (Tyurin and Richtárik, 2023c) , where the authors propose to bound the time required to find an ε-solution. We refer to a detailed explanation to (Tyurin and Richtárik, 2023c) [Sections 3-6].First, we define an oracle that emulates the process of computing stochastic gradients or the process of sending a compressed vector (Tyurin and Richtárik, 2023c) [Section 4]:EQUATIONwhere ξ ∼ D, g is an arbitrary mapping such that g : R d × S → R d , and S is the sample space of a distribution D. Next, we define the time multiple oracles protocol with compression:Protocol 9 Time Multiple Oracles Protocol with Compression1: Input: function(s) f ∈ F, computation oracles (O 1 , ..., O n ) ∈ O(f ), communication oracles ( Ĉ1 , ..., Ĉn ) ∈ U, algorithm A = {(B k , N k 1 , . . . , N k n )} ∞ k=0 ∈ A 2: s ∇f ,0 i = s C,0 i = 0 for all i ∈ [n] 3: for k = 0, . . . , ∞ do 4: (t k+1 , i k+1 , c ∇f ,k+1 , c C,k+1 , x k ) = B k (g 1 , . . . , g k ), ▷ t k+1 ≥ t k 5: (s ∇f ,k+1 i k+1 , g k+1 i k+1 ) = O i k+1 (t k+1 , x k , c ∇f ,k+1 , s ∇f ,k i k+1 ) ∀j ̸ = i k+1 : s ∇f ,k+1 j = s ∇f ,k j , g k+1 j = 0 6: g k+1 pre = N k i k+1 (g 1 , . . . , g k , g 1 i k+1 , . . . , g k+1 i k+1 ), 7: (s C,k+1 i k+1 , g k+1 ) = Ĉi k+1 (t k+1 , g k+1 pre , c C,k+1 , s C,k i k+1 ) 8: end forIn this protocol, the server via B k returns a new point x k , and broadcasts it to the i k+1th worker. Then, the worker calls the oracle O i k+1 that calculates stochastic gradients. Next, the oracle returns the vector g k+1 i k+1 , and the worker processes it with N k i k+1 . Finally, the worker sends g k+1 pre to the oracle Ĉi k+1 that sends compressed vectors to the server. Using the parameters c ∇f ,k+1 and c C,k+1 , it can decide if it wants to start/stop the process of a gradient calculation and the process of communicating a compressed vector (See Sec. F in (Tyurin and Richtárik, 2023c) ). As far as we know, all centralized distributed optimization methods can be described by Protocol 9, including Minibatch SGD, QSGD, Asynchronous SGD, Rennala SGD, and Shadowheart SGD.We consider the standard function class from the optimization literature (Nesterov, 2018; Arjevani et al., 2022; Carmon et al., 2020) :Definition O.1 (Function Class F ∆,L ). We assume that a function f : R d → R is differentiable, ∥∇f (x) -∇f (y)∥ ≤ L ∥x -y∥ ∀x, y ∈ R d , (L-smooth) and f (0) -inf x∈R d f (x) ≤ ∆ (∆- bounded).The set of all functions with such properties we denote by F ∆,L .Next, we define the class of algorithms that we analyze. Definition O.2 (Algorithm Class A zr ). Let us consider Protocol 9. We say that the sequence of tuples of mappingsA = {(B k , N k 1 , . . . , N k n )} ∞ k=0 is a zero-respecting algorithm, if 1. B k : R d × • • • × R d k times → R ≥0 × N × N × N × R d for all k ≥ 1, and B 0 ∈ R ≥0 × N × N × N × R d .2. For all k ≥ 1 and and g 1 , . . . , g k ∈ R d , t k+1 ≥ t k , where t k+1 and t k are defined as (t k+1 , . . .) = B k (g 1 , . . . , g k ) and (t k , . . . ) = B k-1 (g 1 , . . . , g k-1 ). 3. N k i : R d × • • • × R d k times × R d × • • • × R d k+1 times → R d for all k ≥ 0 and for all i ∈ [n]. 4. supp x k ⊆ k j=1 supp g j , and supp g k+1 pre ⊆ k j=1 supp g j k+1 j=1 supp g j i k+1 , 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 .The properties 1 and 3 are only required to define the domains of the mappings. The property 4 ensures that these mappings are zero-respecting (Arjevani et al., 2022) . The property 2 is explained in (Tyurin and Richtárik, 2023c) [Section 4, Definition 4.1]. It ensures that our algorithm does not "travel into the past".The following oracle class is the same as in (Tyurin and Richtárik, 2023c) . For any f ∈ F ∆,L , it returns n oracles that require h 1 , . . . , h n seconds to calculate a stochastic gradient. These oracles emulate the real behavior where the workers have different processing times. The following oracle class emulates the behavior of compressors. It returns n oracles that require τ 1 , . . . , τ n seconds to send a compressed vector to the server. Finally, we present our lower bound theorem: Theorem O.5. Let us consider Protocol 9. We take any , 11 where T = ∆L c2ε is the dimension of the construction. For any algorithm A ∈ A zr , there exists a function f ∈ F ∆,L , computation oraclesh i > 0, τ i > 0 for all i ∈ [n], ω ≥ 0, L, ∆, ε, σ 2 > 0 such that ε < c 1 L∆ and ω + 1 ≤ T(O 1 , . . . , O n ) ∈ O σ 2h1,...,hn (f ), and communication oracles ( Ĉ1 , . . . , Ĉn ) ∈ U ω τ1,...,τn ,12 such thatE inf k∈St ∇f (x k ) 2 > ε, where S t := k ∈ N 0 | t k ≤ t and t = c 3 × L∆ ε × t * (ω, σ 2 /ε, h 1 , τ 1 , . . . , h n , τ n ).The quantities c 1 , c 2 , and c 3 are universal constants. The sequences x k and t k are defined in Protocol 9.P Proof of Theorem O.5P.1 The "Worst Case" FunctionLet us consider the "worst case" function, which is a standard function to obtain lower bounds in the nonconvex world. We define prog(x) := max{i ≥ 0 | x i ̸ = 0} (x 0 ≡ 1).In our proofs, we use the construction from (Carmon et al., 2020; Arjevani et al., 2022) . For any T ∈ N, the authors defineEQUATIONwhereΨ(x) = 0, x ≤ 1/2, exp 1 - 1 (2x-1) 2 , x ≥ 1/2, and Φ(x) = √ e x -∞ e -1 2 t 2 dt.The main property of the function F T (x) is that its gradients are large unless prog(x) ≥ T. Lemma P.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. 
experiments compute resources: 
 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 Q 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). 9. 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: Our work considers a mathematical problem from the machine learning domain.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). 10. Broader Impacts Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? Answer: [NA] Justification: Our work considers a mathematical problem from the machine learning domain.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.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: Our work considers a mathematical problem from the machine learning domain.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes] Justification: Section Q Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.For convenience, following the previous literature, we use the shortcuts C(x; ν) ≡ C(x) and C(x; νij) ≡ Cij(x) assuming that ν and νij are mutually independent.It is also called the distributed compressed stochastic gradient descent method (DCGD/DCSGD)(Khaled and Richtárik, 2020).For ω = 0, the rate reduces to the rate of Minibatch SGD.We say that a method is centralized if the workers calculate stochastic gradients only at points calculated by the server.From the proof, it is clear that the result is tight up to a constant factor.We can avoid this constraint using a slightly different construction of a compressor. However, the number of non-zero returned values by the new construction is random. See Sec. P.3.The function f defined on R T with T = Θ ( L∆ /ε) , and the constructed compressor C preserves only K = ⌈ T /ω+1⌉ non-zero coordinates.We can avoid this constraint using a slightly different construction of a compressor. However, the number of non-zero returned values by the new construction is random. See Sec. P.3.The function f defined on R T with T = Θ ( L∆ /ε) , and the constructed compressor C preserves only K = ⌈ T /ω+1⌉ non-zero coordinates.We implicitly assume that 1 -(1 -p) m = 0 if p = 1 and m = 0. See footnotefor the details. 
 
 Appendix:  


Decision: This paper studies a centralized distributed stochastic optimization algorithm focusing on the time complexities thru optimizing the allocation of computation time of the workers under knowledge of the computation time & delay time of these workers. While the paper has received generally positive reviews and I thus recommend acceptance. However, it should be noted that some of the important concepts such as the notion of equilibrium time is not well explained, and the paper has deferred much of these important discussions to the appendix. I recommend the authors to consider these comments and revise their paper thoroughly before publication.

Reviews: review: paper_summary: paper_summary: The paper presents a novel method for non-convex stochastic optimization in an asynchronous centralized distributed setup, focusing on improving time complexity in heterogeneous environments. Additionally, the authors demonstrate that the proposed method achieves theoretically optimal time complexity under compression.
strength_weakness: strength_weakness: 1. The definition and calculation of equilibrium time are complex and not very intuitive. The implicit nature of this definition might make practical implementation and understanding challenging.
2. While the proposed method improves time complexity, the paper does not fully discuss the impact on final convergence and loss in real-world scenarios with limited training datasets. Additionally, the experiments only compare the loss of different SGD methods under the same wall time, but it would be insightful to know if Shadowheart SGD maintains lower loss when comparing the number of training samples.
questions: questions: 1. Can the process of calculating equilibrium time be simplified or made more intuitive? Are there any practical algorithms or tools recommended for this calculation?
2. Similar to Weakness 2. Regarding the impact on convergence and loss in scenarios with limited training datasets, how does Shadowheart SGD perform when comparing the loss against the number of training samples?
limitations: limitations: Yes
paper_summary: paper_summary: This paper considers distributed and centralized smooth non-convex optimization when workers have different computation and communication speeds. These different speeds on the workers (and even possibly the server) characterize the problem's device heterogeneity. The authors provide a new algorithm that uses unbiased compression and, more importantly, assigns a time budget for each communication round to optimize for total time complexity. This time budget is calculated based on the speeds of different workers and is the main contribution of this paper. Adapting classic lower bounds for distributed zero-respecting algorithms, and using RandK compression algorithm, the authors show their algorithm is optimal. The authors also offer extensions, such as an adaptive variant of their algorithm, and consider the setting when server communication requires some time.
strength_weakness: strength_weakness: I have the following comments in a decreasing order of importance:

1. I am not sure if the lower bound actually holds for all unbiased compression schemes. For instance, if the unbiased compression scheme is to add random noise to the gradient vector before arbitrarily picking a direction to communicate, then it woun't be distributed zero-respecting. Ofcourse, with randK this does not happen because if it picks a co-ordinate it wouldn't make it non-zero if it isn't already. This is an important subtlety and should be incorporated in the discussion, but either removing the above compression scheme I mentioned through an additional constraint in the definition of distributed zero-respecting algorithms (with compression), or state that the lower bound is only for randK compression operator. Otherwise, it is not accurate to say the proposed method is optimal. 

2. In the introduction while specifying the scope of the problem, it would also be useful to discuss the issue of bit communication complexity somewhere. It is true that in some settings, the communication time complexity only depends on the total number of communications, but in more optimized channel communication the bit complixty is an important factor as well, and for instance in the general setup $\tau_i$ should be a function of $K$ for say randK compressor. I ofcourse don't expect the authors to solve all problems in a single problem, but discussing this would make the survey more exhaustive in my opinion. 

3. The authors should comment on when (12) is a reasonable approximation, even if the calculations are not exact. 

4. Small typos: line 112 should be "is not negligible", line 134 should have $t/2$ instead of $t$, unless the authors are using some interlacing idea to compute and communicate simultaneously, in line 217 it should be "it is left",
questions: questions: 1. Do the authors have thoughts on statistical heterogeneity can be considered in this setting? I am concerned that the current algorithm might heavily bias the final output towards the databases of agents that are pretty quick. 

2. Do the authors have thoughts on the second weakness I raised above? In particular, it is an open question to obtain algorithms with optimal round and bit communication complexity, and understanding the regime with non-trivial bit complexity can help make progress towards that setting.
limitations: limitations: Nothing big, but please see my comments above in the weaknesses.
paper_summary: paper_summary: The paper proposes a method (Shadowheart SGD) for centralized asynchronous optimization with compression. The lower complexity bounds are proposed, as well. It is shown that Shadowheart SGD achieves the lower bounds, meaning that the method is optimal.
strength_weakness: strength_weakness: Personally, I did not understand the discussion of equilibrium time well. I understand that it comes from the analysis; also the examples are illustrative. But still, can equilibrium time have some interpretation like mixing time or first hit time in Markov chains? Or maybe it is possible to interpret equilibrium time using some random process, like the authors do in [1].

Also citation of MARINA on line 76, page 3 is missing.

[1] Vogels, T., Hendrikx, H., & Jaggi, M. (2022). Beyond spectral gap: The role of the topology in decentralized learning. Advances in Neural Information Processing Systems, 35, 15039-15050.
questions: questions: See question on equilibrium time above.
limitations: limitations: The paper is mostly theoretical and does not have negative societal impact.
paper_summary: paper_summary: The paper studied distributed asynchronous SGD with heterogeneous communication and computation times for non-convex stochastic optimization problems. In particular, the paper proposed a new algorithm called Shadowheart SGD and analyzed his time complexity. The time complexity is proven to be optimal in the famly of centralized methods with compressed communication by providing a lower bound. This time complexity is also shown to be better than those in the literature.
strength_weakness: strength_weakness: 1. The paper was not well written and is very hard to read. It reads like a summary of the results that are in the appendix. In addition, the intuitive explanations are very few and many notations were not well explained. 

2. The paper considered only IID data distribution. This almost rules out the application of the algorithm in federated learning. The results are nice contributions to the existing results but it seems minor. 

3. It lacks experimental results. All the experiments use either logistic regression with MNIST dataset or quadratic optimization and multiplicative noise. Since the paper proposed a new algorithm, i believe the experiments need to be much more extensive.
questions: questions: 1. In page 3, why $D_v$ is a distribution on $\mathbb{S}_{\xi}$?
limitations: limitations: The paper only focuses on the IID dataset.

Comments: title: Answer to Authors
comment: Thanks for the response; I will keep my positive score and recommend accepting the paper with the aforementioned clarifications.
Dear Authors,

Thank you for the reply. I decided to maintain my score.