Shadowheart SGD: Distributed Asynchronous SGD with Optimal Time Complexity Under Arbitrary Computation and Communication Heterogeneity
Authors: Alexander Tyurin
Marta Pozzi
Ivan Ilin
Peter Richtárik
Venue: NeurIPS 2024 poster (2024)
Keywords: nonconvex optimization
parallel methods
asynchronous methods
lower bounds
compressed communication
Primary area: optimization

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.

Shadowheart SGD: Distributed Asynchronous SGD with Optimal Time Complexity Under Arbitrary Computation and Communication Heterogeneity
Alexander Tyurin KAUST; AIRI, Skoltech!
Marta Pozzi
Ivan Ilin KAUST
Peter Richtárik KAUST
KAUST; University Pavia
Abstract
We consider nonconvex stochastic optimization problems in the asynchronous centralized distributed setup where the communication times from workers 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 Shadoowharrdd 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 corresponding method.
1iDD-hhtttt provably improves the time
Introduction
consider the nonconvex smooth optimization problem
{f(x) RE-DE ((x; }. 2E3d
min
where f(:-) X R. and D3 is distribution on Se * 0. Given 0, seek to find
a possibility random point such that E[[ S Such a point & is called an e-stationary point. We focus on solving the problem in the following setup:
able to compute stochastic gradients V {) of f, in parallel and asyn- chronously, and it takes (at most) h seconds for worker to compute a single stochastic gradient; (b) the workers are connected to a server which acts as a communication hub;
(a) n workers/nodes
(c) the workers can communicate with the server in parallel and asynchronously; it takes (at most) 7i seconds for worker send compressed message to the server; compression is performed via applying lossy communication compression to the communicated message (a vector from R see Def. 2.1:
(d) the server can broadcast compressed vectors the workers in (at most) Tserv seconds; compres- sion is performed via applying a lossy communication compression operator to the communicated message (a vector from R see Def. A.I.
The main goal of this work to find an optimal optimization strategy/method that would work uniformly well in all scenarios characterized by the values of the computation times hi...., hn and
"King Abdullah University of Science and Technology. Thuwal, Saudi Arabia
1 AIRI, Moscow, Russia
Skolkovo Institute of Science and Technology, Moscow, Russia University of Pavia, Pavia, Italy
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Table I: Time Complexities of Centralized Distributed Algorithms. Assume that it takes at most hy seconds to worker i to calculate a stochastic gradient and f; seconds to send one coordinateffloat to server. Abbreviations: L smoothness constant, & error tolerance, A f(x²) f # of workers, d dimension of the problem. We take the RandK compressor with K = 1 (Def. D.I) (as an example) in QSGD and Shadowheart SGD. Due to Property 6.2, the choice K is optimal for Shadowheart SGD up to a constant factor.
Complecit
Tane Compleilee tn Sonze Rlcaance As la Vi [n] loqed performncce
mast fur F so Wi is (kk Lak watker dow)
Nanorial Compusiee
10f
Minbbash SGD
uas Me,, d5i (+م ممام
lacaositar)
mast (i,
X10
(Khial and
(Alisai A. 2017)
CSGD 050
Ab) maxtAr, +J ((g +1 dي + م
(scaosttar)
(osen) cgp whate stall
X3
K10P
X10*
Fleemada SGD
(yydds and Hiztaikk, 3033C
Asynchroncus
wet man ho Mee
(ndeaa)
2. mas (6, (t, up (wors) wieen Pualoe legge)
K10P
x10
K1.5
Shazonehcon 9GD (ur Fi Kgg.
maxe (n if /eaaes
(Coillory
Louer Reced
(a 1..2 (bi,
D
compleiis of Studwwheet SGD
that the compbeity the coepeting cestrolted netleds and reiest, We dow that (1lo the optivel the soaalosit in the fusily of contraliedd metheds with coepeaskaa use Section 5 and Theerera 0.5)
Sectien
Upan boand comppaiii are datieal Homsda 502 Auverorea Howesa, weeas dutiee beasl tang Theeren 0.5 witk Oue sloual lake dr, insind wiko upply dasedaatos yennttaia
comptocties compl cutles the congeting lecl wime compure io the ooe plosity ooor uxtiad thatooeertetoo Sr. euarple Mentuk 9900 08933 and cireaus 9950 be warie the factres x x 18', and LP repostiely
report
"The lover boand covameeed wab Rtadi companseee and dimasaion (LL/)))
communication times Ti...., Tn and Tserv- 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 {ri} and take, for instance, the RandK compressor (see Def. D. and Sec. 2.2) (sends K random entries). Then T; is # of seconds required to send K coordinates of 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 T, K x i.. and, T; is 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 т; seconds send the compressed message.
From the viewpoint of federated learning (Konečný et al., 2016; Kairouz et al., 2021), our work is 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: smooth- ness, bouud-boundedness and bounded variance.
Assumption 1.1. f is differentiable & T-ssooth, i.e., [ Vs(ii) < T. || vll. Va. y E Rd. Assumption 1.2. There exist f E I such that f(x) 2 f for all æ E Rd. We define A == f(x9) f", where 20 E RRd is a starting point of all algorithms we consider.
Assumption 1.3, For all x E Rd the stochastic gradients v. {) are unbiased, and their variance is bounded by ²² 2 0, i.e., E.g (x; {)] = fz) and ((;=) {f())
o².
To simplify the exposition. in what follows we first focus on the regime in which the broadcast cost can be ignored. We describe strategy for extending our algorithm to the more general regime in Sec. A.
2 Related Work
2.1 Communication time can be ignored
We now briefly review related work and important concepts. Consider the regime when the communication cost is negligible (T, 0 for all i), and the computation times by are arbitrary

---

but fixed. It is well-known that under Assumptions 1.1, 1.2, and 1.3, the vanilla SGD method xkt1 x² (** where 2 E F is starting point, and ?
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 e-stationary point is O (LA/e+ o SGD run on a single worker whose computation time is h seconds would have time complexity O (h1 x (LA/s + o² L)/3)) seconds. The time complexity of Minibatch SGD with n workers, i.c.,
x
V far 5
can be shown (Gower et al., 2019) to be
O MMmax
LA
LA ne
where hmax == maXiej]] h2 where [n] denotes {1..... n). The dependence on Amax is due to Minibatch SGD employing synchronous parallelism which forces it 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 improvement since Mmax 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((//a E ),)- x (L-//- + o' LA/ne")), which improves the dependence from Amax to the harmonic mean of the computation times. Subsequently, Tyurin and Richtárik (2023c) developed the Rennala SGD method whose time complexity is
min mEin)
1 1=1
ho;;
x
o² LA
mg?
(4)
where π is permutation forwhich hn, S ...
< h
They also showed that the time complexity (4)
optimal by providing a matching lower bound.
2.2 Communication time is factor
In many practical scenarios, communication times can be the main bottleneck, and can not be ignored, e.g.. in distributeddffederrte 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 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 Dr is distribution on Sy.
Definition 2.1. A mapping Rd x S, - IRd is an unbiased compressor if there exists w 2 0 such that [xx; v)] = x, [ep[[[C( x||²] E ||x||| for all x. Let U(w) denote the family of such compressors
Assumption 2.2. Samples from De 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., 202 Horváth et al., 2022). One of the most straightforward methods which use compression QSGD (Alistarh et al., 2017):
1+1
Σ C. (vS(a*;<)))
(5)
For convenience, following the previous literature, use the shorteuts C(a; v) C(x) and C(x; Cyj (x) assuming that and Viy are mutually independent. 'It is also called the distributed compressed stochastic gradient descent method (DCGD/DCSGD) (Khaled and
Richtárik, 2020).
3

---

where each worker calculates one stochastic gradient, compresses it using C, E U(w) drawn indepen- dently, and sends the server. The server aggregates the compressed vectors and performs step (5). With a proper stepsize choice 7 QSGD converges after O (1//n + 1) x LA/s + (w 1) x o² LA/ne") iterations' (Khaled and Richtárik, 2020). Let's assume it takes T; seconds for worker i to send one compressed vector to the server. Since the workers act in parallel, the time complexity QSGD is
max (4, + Ti) x ((H: 1) + (w + 1) 1)0 kE[n]
(6)
We can go through 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.
3 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:
SGD (Algorithm 1)-that guarantees to find an etstaioonary 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 L., (-) whose definition is implicit (see Def. 3.1), we show (see Sec. 7) that T. is not worse than the time complexity of known centralized 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 the first such result in the literature.
We develop a new
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.
4 Development of Shadowheart SGD
Our method bears some resemblance to Rennala SGD (Tyurin and Richtárik, 2023c) and QSGD (Alistarh 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)[Scc.7] behind the design of Rennala SGD that 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 2++1 = x.h -7g", where
Cij Σ
V ch)
w.mbb,
In Shadowheart SGD, worker i calculates b, stochastic gradients, adds them up to form Ehe v and compresses the result m, 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 wy: the server aggregates the Σi= m, compressed messages across all workers by performing a conic combination with coefficient Σn w.m,b, for messages coming from worker i. One can easily show that (9) is equivalent to Alg. I. Note that we recover QSGD (see (5)) as special (suboptimal) case with w;- b. my for all E [n].
7 For w O, the rate reduces to the rate of Minibatch SGD. WW say that a method is centralized if the workers calculate stochastic gradients only at points calculated by the server.

---

Algorithm Shadowheart SGD
Definition 3.1 (Equilibrium Time).
1: Input: starting point xº E Rd. stepsize 7 >
A mapping Rzo
x I 22
(Rzo R20)
0, ratio e²/c, computation times h, > 0, and communication times T; > 0 for i [n]
(hum)
X x R220 R20)
+ R20
2: Find equilibrium time t" using Def. 3.1
3: Set b;
6: and m,
for all i [n]
(hn.Ta.)
h;
4: Find SA = (i [n] b, Am,, 0}
with inputs w, w,o²/e h1, TI, Ti..... has Ta is called the equilibrium time if is defined as follows. Find permuta- tion that sorts the pairs (h4, T.) max Tx, S.... < max(h Ta and find the solution (0) [0, 00) in of
5: for k = =00.1..... 1
6: Run Alg. in active workers SA
7: Broadcast .* bi, my to active workers SA
8: Initialize gd
9:
for i E SA in parallel do
10: Wi (a) (bew w m,;
11:
for j = -,...,, do Receive Cip (o.) from worker i
1=1 27 w
13:
g² = g + C, (gt)
14:
end for
for all j E [ni]. Then the mapping returns the value
15:
end for
16:
g" 9²| (E1=1 w,m,bi)
17:
x xkt xh 79
(w,,, o²/e, ee, h1, Ti,... Nn: Tn)) min maxx Tay J. s²(()) (i) E [0, ooj. jE(m)
18:
end for
Algorithm 2 Strategy of Worker
(8)
We shall to (w, o²/e, [h; Tl.).
the short notation
1: Receive x² bi, my from server, init of
2: for -= 1,..... ........ do
3: Calculate Vf(x" ck) Sil
sh
De
is possible that permutation is not unique. The result of the mapping does not depend on the choice of the permutation. See the proof of Prop- erty 4.1.
4: gº = + vf(=",5h ck
5: end for
do 7: Send Cij (g.) = (g/: ut)) to server,
6: for
1, =
"For convenience, we use the projectively ex- tended real line and define 1/0 cc.
Ut ~ Du, Cij E U(w)
8: end for
If and a² 0, then w;
The weights {w;) are chosen so as to minimize the variance in the proof of Lemma H. However, we still need to find the right values for b; and m,, Since the computation and communication times of worker are h; and т;, respectively, the following strategy makes intuitive sense: the server sets some time budget t for all workers, and each worker then calculates L//n.] stochastic gradients and sends [4/r_] compressed vectors to the server. But what the right way to choose t? f 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 f 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 L² which depends on the quantities w, "²/e, hi, TI...., hns Tns 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 it is possible to give a more explicit formula in general. To provide for some peace of mind, 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 lower bound that involves the same mapping. Thus, the equilibrium time is not an "artifact" of our method, but is of fundamental nature. We use the cquilibrium time t" in Shadowheart SGD when we choose b; and m,.
5

---

Our first main result provides iteration complexity:
Theorem 4.2. Lett Assumptions 1.1, 1.2, 1.3, 2.2 hold. Let take 7 1/2L in Shadowheart SGD
(Alg. 1). Then long K 2 16LA/E, we have the guarantee K Ek=
K-1 E || S
|
This result guarantees that Shadowheart SGD will converge after O (1///)) iterations. Our second main result provides a much more relevant complexity measure: time complexity.
Corollary 4.3. Shadowheart SGD (Alg. converges after most T, seconds, where
T. = 32LA x t" (w, "e, Ti,........ has Tn)
(10)
Surprisingly, 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 Table for summary).
4.1 Tighter result with per-iteration times h and T.
slight modification of Alg. leads to Alg. 4, which can work with iteration-dependent computation and communication times h and r7". Our main result in this setup is Theorem H.3; here present its corollary.
Theorem 4.4. Alg. 4 converges after
LGLA
2t (w, o² /2/,, h / ....,,,,...... ,. (..
(11)
seconds, where h > and T > are computation and communication times for worker in iteration k.
For presentation simplicity sake, in the main part we continue to work with static {hi} and (Ti).
4.2 On the problem of estimating the times in Algorithms and 4
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. it does not require the knowledge of (h;) and {T;} (or { and [r,"] } in the case of Alg. 4), and does not calculate the equilibrium time t". However, byproduct this flexibility, this method has a slightly worse time complexity guarantee. In order to present our result, we need to define auxiliary sequence.
Definition 4.5. Assume that the workers have computation and communication times less or equal to {h+) and {T.}. Assume that fug is the actual time required to calculate the j"h stochastic gradient by worker i, Annin > is the smallest possible computation time. Then
sup suPicoSImar 1s,(649) 4max
fmax Aanin
k20 infresstmax bL044))
max = 128 t" (w, o²/e, (ha, Tr), ma, TT))))
That is, r E [1, oo] is the largest ratio between the fastest and the slowest computation of stochastic gradients in local time windows. r; defines degree of fluctuations in computation times. Note that r; describes local fluctuations; it is true that r; S supy>1 Raa/infz2a R... for all i E [r] and ri can be arbitrarily smaller.
corollary of our main result in this part (Theorem M.I) is presented next.
Corollary 4.6. If the computation and communication times are positive, the time complexity of Alg. is LA t" (w, o² /e/e, maxx(h; Ts), min (Tor,, (h, 7.ll up to constant factor, where 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 parallel, and it does not know the times h; and t; (or h and 75)). That is why this method gets a suboptimal complexity and depends computation times do not fluctuate significantly, i.e., r; = @(1), and ii) T; S hy for all i [M], then this complexity reduces to the optimal complexity LA/e x t* (w, /2/2, [h, T.).).
Nevertheless, if we assume that i) the

---

Lower Bound
Protocol Simplified Representation of Protocol 9
1: Init S on the server (all available information)
2: while True do
3: Server calculates new point I using S and broadcasts I and S to any worker
(broadcasting does not take time)
4: end while
th Worker (in parallel):
5: while True do
6: Receives & and S, calculates as many stochastic gradients as it want at the point こ (each calculation takes h1 seconds), aggregates all available information, and sends compressed vectors (each dispatch takes т; 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 to understand it might be possible improve this complexity. Sec. O we formalize our setup and show in Theorem 0.5 that up to constant factor, the result (10) is optimal. Here we present a simplified illustration of our approach.
Protocol 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 0.5, we show that to constant factor, no method described by Protocol 3 can converge faster than (10) seconds. In order use our lower bound, the workers must calculate stochastic gradients at point that was calculated by the server.
Let briefly explain the proof's idea. The general approach is the same in (Nesterov, 2003; Arjevani et al., 2022; Huang et al., 2022): we take the "difficult" function (Sec. P.I), which has large gradients while the last coordinate equals zero. Every algorithm starts with the point x0 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 Po s/0². Even if the stochastic oracle returns a non-zero coordinate for some worker, the corresponding communication oracle on this worker also has return non-zero coordinate, which happens with probability Pe RJ 1/w+1. We fix the RandK compressor in the lower bound theorem with K s /.//((++1), 1),, and the number of coordinates parallel, they can discover and send to the server the next non-zero coordinate not earlier than after minme[n] {mmm TmHmm] seconds, where 17m and Pm are i.i.d. geometric random variables with Po and Pw. With high probability, we show that this quantity S2(t" (2/p., 1/p- The number of coordinates is se LAfe. Therefore, the lower bound is (10) seconds to a constant factor.
L.Af;; thus, indeed, Pa 2 1/w+1. Since all workers work in
pe h1, Ti.... Ans Tn)).
Equilibrium Time
Since the time complexity (10) of Shadowheart SGD is optimal, we believe that the equilibrium time a fundamental mapping that should be investigated more deeply.
6.1 Calculation strategy
The calculation t" requires us to sort max (o,cchh,77) r... 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).
6.2 Intuition behind the equilibrium time L**
Assuming we found an optimal jr in (8), we have f" max(max(h Tay- J. s [[*)]. The first observation is that 1" does not depend on the workers that correspond to max max ( +17 +: b........... J.... max ( J. Since these values are greater or equal to max(h : Tay. J. the mapping "decides" to ignore them because they are too slow. The following
7

---

derivations are not rigorous and are merely supposed to offer some intuition. We define a; := Tm and B, 0 /e. Next, using (7), we have
Anada 1 20, "
R ~s
E
max + +
Σ
(12)
+23
iEM
iEM
where M {i [in] max at 3r) 2 a181
Solving this, one can get that
Σ iEM
Σ FEM
(13)
ag
Thus, s s"()) divides the active workers into two groups M and [i*] \ 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(o;, _3,] 2 "=84/s"(")) & s" (j")
min 3. Intuitively, the last inequality means that if T; h; small worker can quickly com- pute gradient or send a compressed vector), it belongs to M. Otherwise, if a worker's computation and communication performance are balanced, belongs to [j*] A.
6.3 Properties of the equilibrium time
We now provide some properties and particular cases to understand t* better. One can find the proof' and more properties in Sec. E. The first result says that t" is monotonic.
Property 6.1. @ w 0, 00,0 2 of
0, h 2 0, Fn 2 Tn 2 0, then t" (a, [h,, a.)1) t" (w, /e, [h,, T.
hn 2 0, and
Consider the RandK compressor. If it takes î sec to send one coordinate by worker i, then, up to constant factor, Property 6.2 ensures that an optimal choice of K is
Property 6.2. For all K
d... h1, T1...., hn in t" (4/ by K+ ..... Ang kfn) 2 to (d 1, o² o,, t..... May tn).
O. we have 24 x
6.4 Examples
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* (w, '=e,, f1,, Ti, ........ fyy Tn). Example 6.3. [Infinitely Fast Worker] If exists j E [n]] such that T,
and hy = 0, then t 0.
Example 6.4. [Infinitely Slow Workers] If = сo and h; xo for all i [n:] then t" = co.
Example 6.5. (Equal Performance) T: = T and h = h for all i E [n)]. then
max
rue h, T,
n nr v
ho
Tho
(14)
In the next example, consider the setting from Sec. 2.1. Example 6.6 and Corollary 4.3 restore the optimal rate (4) of Rennala SGD. Example 6.6. [Infinitely Fast Communication] If = 0 for all i [m], then
))
t" 2 min max ham me(n)
d²
m
min mE(n)
m
(1
o² mE
(15)
Toms
where क is permutation that sorts (he
The following examples show that t" is robust slow workers workers that do not participate.
Example 6.7. [gnoring Slow Workers] h, and T are fixed and finite for all S p. and max hy. T&} = m E IR for all > p, then, for m large enough, we have t" (w, o 2//,, [h4 7.ll) =
(w, 0e/,, T.l)).
Example 6.8. [Partial Participation] If max 7 oo for all P 1, then
t",,," [h+, m.lf))))) = (w, o²/e, [h,, T..
FFrom the proof, it is clear that the result tight up to constant factor.
8

---

7 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 basclines easier, we consider the RandK compressor with K 1. Using Theorem D.2, we have w takes i; seconds to send one coordinate to the server, thus = f; since we use Rand1. Also, it takes di; send a non-compressed vector for all E [n].
We also assume that worker
Minibatch SGD and QSGD. It is well known (Lan, 2020) that the number of iterations of Minibatch SGD required to find e-solution is O (L2/E + = 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 a constant factor)
TMB max (h, + df:) kE(n]
LA
LLLA n2
(16)
In Sec. J, we compare (16) with (10) and show Comparison 7.1. T. = (mTm).
However, there are many regimes when T, < TMB. For instance, if max f;} = oo for some worker (Example 6.8). then TMB = 30 and T. < oc. Also, under the conditions of Example 6.7, m + (X, we get TMB + oo whereas T, is bounded. The same reasoning applies to QSGD because its time complexity (6) depends on max4e(n] (h; + f.) Due 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 5; + 0 for all E [ml, 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 ñt > O for all E [n]. We can apply the result from Theorem 0.5 Rennala SGD, thus the time complexity of Rennala SGD is not better than
TR LA x t" (0, /²/ h1, dii..... fiy dfn)).
(17)
Note that Asynchronous SGD also has the same lower bound. In Sec. J, we compare (17) with (10) and show
Comparison 7.2. T. OTTR).
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 prove it. Take
h; = h for all i < n, h = oo, and A = + for all i E [n].
(18)
Due to (16) and (17), the time complexities of Minibatch SGD and QSGD are oo, and the time complexities of Asynchronous SGD and Rennala SGD are not smaller than
(max [1, di,
ha
LA
which
"= a (max (h, dr) (A)
[m-1]=
From (14), the time complexity of Shadowheart SGD is most
o (max /,, I-II [n-1)=
haa #d 1ye
which "=300 O (max (h, +) 44
Thus. Shadowheart SGD can be d times faster than all previous methods if the number of workers large. Using the same reasoning, Shadowheart SGD can be n times faster if the dimension or ł is large. Due to the continuity of the complexities, such huge differences hold even if we take n < oo, and start considering more heterogenous times h2 and 7; by perturbating (18).
7.2 The fastest worker works locally
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 o > 1. Then, the time complexity of such algorithm (Lan, 2020) is TsGD

---

min;g[n] h; x LA/E. Clearly, comparing TSOD and (10), if f; are large enough, then TSaD can be smaller than T.. However. this does not contradict our lower bounds because this method does not satisfy the conditions of Theorem 0.5: it does not communicate with the server. In other words, the communication channel too slow, does not make sense to communicate. One may now ask: "Under which conditions is it beneficial to communicate?" Comparing Tsgp and (10), one can see that (10) is better when (d - 1, -,/²/8 f fI...., fun Ta) S. mitl:e]]]] h2 x / 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, +, f(d-1)/n, Ao² /ne,, v (d
ho In the regime when n is large enough or ε is small enough, we have t* < ho"/e, and Alg. 7 has better convergence guarantees. On the other hand, if + is large enough, then is possible that t' > ho"/c.
Acknowledgments and Disclosure of Funding
The research reported in this publication was supported by funding from King Abdullah University of Science and Technology (KAUST): i) KAUST Baseline Research Scheme, ii) Center of Excellence for Generative AI, under award number 5940, iii) SDAIA-KAUSE Center of Excellence in Artificial Intelligence and Data Science. The work of A.T. was partially supported by the Analytical center under the RF Government (subsidy agreement 000000DD33031225500000 Grant No. 70-2021-00145
References
Alistarh, D., Grubic, D., Li, J., Tomioka, R., and Vojnovic, M. (2017). QSGD: Communication- efficient SGD via gradient quantization and encoding. In Advances in Neural Information Process- ing Systems (NIPS), pages 1709-1720.
Arjevani, Y., Carmon, Y., Duchi, J. C., Foster, D. Srebro, N., and Woodworth, B. (2022). Lower bounds for non-convex stochastic optimization. Mathematical Programming, pages 1-50.
Beznosikov, A., Horváth, S., Richtárik, P., and Safaryan, M. (2020). On biased compression for distributed learning, arXiv preprint arXiv:2002. 12410.
Carmon, Y., Duchi, J. C., Hinder, O., and Sidford, A. (2020). Lower bounds for finding stationary points i. Mathematical Programming. 184(1):71-120.
Chen, J., Pan, X., Monga, R., Bengio. S., and Jozefowicz, R. (2016). Revisiting distributed syn- chronous sgd. arXiv preprint arXiv:1604.00981.
Cohen, A., Daniely, A., Drori, Y., Koren, T., and Schain, M. (2021). Asynchronous stochastic optimization robust to arbitrary delays. Advances in Neural Information Processing Systems, 34:9024-9035.
Dutta, S., Joshi, G., Ghosh, S., Dube, P., and Nagpurkar, P. (2018). Slow and stale gradients can win the race: Error-runtime trade-off's in distributed SGD. In International Conference on Artificial Intelligence and Statistics, pages 803-812. PMLR.
Feyzmahdavian, H. R., Aytekin, A., and Johansson, M. (2016). An asynchronous mini-batch algorithm for regularized stochastic optimization. IEEE Transactions Automatic Control, 61(12):770-3354,
Gauthier, F., Gogineni, V. C., Werner, S., Huang, Y.-F,, and Kuh, A. (2023). Asynchronous online federated learning with reduced communication requirements. arXiv preprint arXiv:2303. 15226.
Ghadimi, S. and Lan, G. (2013). Stochastic first-and order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341-238 -336888...
Gorbunov, E.. Burlachenko, K., Li, Z., and Richtárik, P. (2021). MARINA:
Faster non-convex
distributed learning with compression. In 38th International Conference on Machine Learning.
Gower, R. M., Loizou, N., Qian, X., Sailanbayev, A., Shulgin, E., and Richtárik, P. (2019). SGD: General analysis and improved rates. In International Conference on Machine Learning, pages 5200-5209. PMLR.
10

---

Gruntkowska, K., Tyurin, A., and Richtárik, P. (2023). EF21-P and friends: Improved theoreti- cal communication complexity for distributed optimization with bidirectional compression. In International Conference Machine Learning, pages 1176-11180 1807. PMLR.
Horväth, S., Ho. C.-Y,, Horváth, v., Sahu, A. N., Canini, M., and Richtárik, P. (2022). Natural compression for distributed deep learning. In Mathematical and Scientific Machine Learning, pages 129-141. PMLR.
Huang, X., Chen, Y., Yin, W., and Yuan, K. (2022). Lower bounds and nearly optimal algorithms in distributed learning with communication compression. arXiv preprint arXiv:2206. 03665.
Jia, J., Liu, J., Zhou, C., Tian, H., Dong, M., and Dou, D. (2023). Efficient asynchronous federated learning with sparsification and quantization. arXiv preprint arXiv:2312.
Kairouz, P., McMahan, H. B., Avent, B., Bellet, A., Bennis, M., Bhagoji, A. N., Bonawitz, K.,
Charles, Z., Cormode, G., Cummings, R., et al. (2021). Advances and open problems in federated learning. Foundations and Trends in Machine Learning, 14(1-2):1-210.
Khaled, A. and Richtárik, P. (2020). Better theory for SGD in the nonconvex world. arXiv preprint arXiv:2002.03322,
Koloskova, A., Stich, S. U., and Jaggi. M. (2022). Sharper convergence guarantees for asynchronous SGD for distributed and federated learning. arXiv preprint arXiv:2206.0830)
Konečný, J., McMahan, H. B., Yu, F. X., Richtárik, P., Suresh, A. T., and Bacon, D. (2016). Federated learning: Strategies for improving communication efficiency. arXiv preprint arXiv: 1610.05492.
Lan, G. (2020). First-order and stochastic optimization methods for machine learning. Springer.
LeCun, Y., Cortes, C., and Burges, C. (2010). Mnist handwritten digit database. ATT Labs [Online]. Available: http://yann. feccu.ccmm/xxd//mmis... 2.
Li, Z.,, Kovalev, D., Qian, X., and Richtárik, P. (2020). Acceleration for compressed gradient descent in distributed and federated optimization. In International Conference on Machine Learning-
McMahan, B., Moore, E., Ramage, D., Hampson, S., and y Arcas, B. A. (2017). Communication- efficient learning of deep networks from decentralized data. In Artificial intelligence and statistics, pages 1273- 1282. PMLR.
Mishchenko, K., Bach, F., Even, M., and Woodworth, B. (2022), Asynchronous SGD beats minibatch SGD under arbitrary delays. arXiv preprint arXiv:2206.0704 07638.
Mishchenko, K., Gorbunov, E., Takáč, M., and Richtárik, (2019). Distributed learning with compressed gradient differences. arXiv preprint arXiv: 1001:09000009000
Nemirovskij, A. S. and Yudin, D. B. (1983). Problem complexity and method efficiency in optimiza- tion.
Nesterov, Y. (2003). Introductory lectures on convex optimization: A basic course, volume 87.
Springer Science & Business Media.
Nesterov, Y. (2018). Lectures on convex optimization, volume 137. Springer.
Nguyen, L., Nguyen, H., Dijk, M., Richtárik, P., Scheinberg, K., and Takác, M. (2018). SGD and hogwild! convergence without the bounded gradients ussumption. In International Conference Machine Learning, pages 3750-3758. PMLR.
Ramesh, A., Pavlov, M., Goh, G., Gray, S., Voss, C., Radford, A., Chen, M., and Sutskever, I. (2021). Zero-shot -ixaato-image generation. In International Conference on Machine Learning, pages 8821-8831 PMLR.
Recht, B., Re, C.,, Wright, S., and Niu, (2011). Hogwild!: A lock-free approach to parallelizing stochastic gradient descent. Advances in Neural Information Processing Systems, 24.

---

Richtárik, P., Sokolov, I., and Fatkhullin,, I. (2021). EF21: A new, simpler, theoretically better, and practically faster enror feedback. arXiv preprint (rXX::20060052033
Seide, F., Fu, H., Droppo, J., Li, G., and Yu, D. (2014). 1-bit stochastic gradient descent and its application to data-parallel distributed training of speech DNNs. In Fifteenth Annual Conference of the International Speech Communication Association.
Tyurin, A. and Richtárik, P. (2023a). A computation and communication efficient method for distributed nonconvex problems in the partial participation setting. Advances in Neural Information Processing Systems (NeurIPS).
Tyurin, A. and Richtárik, P. (2023b). DASHA: Distributed nonconvex optimization with communica- tion compression, optimal oracle complexity, and no client synchronization. 11th International Conference on Learning Representations (ICLR).
Tyurin, A. and Richtárik, P. (2023c). Optimal time complexities of parallel stochastic optimization methods under fixed computation model. Advances in Neural Information Processing Systems (NeurIPS).
Vogels, T., Karimireddy, S. P., and Jaggi. M. (2019). PowerSGD: Practical low-rank gradient compression for distributed optimization. In Neural Information Processing Systems.
Wang, J., Lu, Y., Yuan, B., Chen, B., Liang, P., De Sa, C., Re, C., and Zhang, C. (2023). Cocktailsgd: Fine-tuning foundation models over 500mbps networks. In International Conference on Machine Learning, pages 36058-36076. PMLR.
Xu, H., Ho, C.-Y., Abdelmoniem, A. M., Dutta, A., Bergou, E. H., Karatsenidis, K., Canini, M., and Kalnis, P. (2021a). Grace: A compressed communication framework for distributed machine learning. In 202/ IEEE 41 International Conference on Distributed Computing Systems (ICDCS), pages 561-572. IEFE.
Xu, H., Kostopoulou, K., Dutta, A., Li, X., Ntoulas, A., and Kalnis, (2021b). Deepreduce: A sparse- tensor communication framework for federated deep learning. Advances in Neural Information Processing Systems, 156-21163.
12

---

Contents
1
Introduction
2 Related Work
2.1
Communication time can be ignored
2.2
Communication time is factor
3
Summary of Contributions
Development Shadowheart SGD
4.1 Tighter result with per-iteration times h and T.
4.2 On the problem of estimating the times in Algorithms and 4
5
Lower Bound
6
Equilibrium Time
6.1
Calculation strategy
6.2
Intuition behind the equilibrium time t*
6.3
Properties of the equilibrium time t*
6.4
Examples
7
Comparison with Baselines
7.1
Shadowheart SGD is strictly better in many regimes.
7.2
The fastest worker works locally
Bidirectional Compression
15
Frequently Used Notation
16
C Basic Facts
16
RandK Compressor
17
E Proofs of the Properties of the Equilibrium Time
17
F Derivations of the Examples for the Equilibrium Time
24
G Generic Lemma For Unbiased Gradient Estimators
27
H Proof's for Algorithms 1 and 4
30
I The Classical SGD Theorem
32
J Comparison with Baselines
33
13

---

K Description of Alg. 5 in the Bidirectional Setting
35
Proofs for Alg. 5
35
M Development of Adaptive Shadowheart SGD
37
Proofs for Alg. 7
38
0 Construction of the Lower Bound
42
Proof of Theorem 0.5
44
P.I The "Worst Case" Function
44
P.1.1 Proof of Lemma P.2
46
P.2
Proof of Lemma P.3
52
P.3 Another Construction
54
Experiments
55
Experiments with Logistic Regression
55
Q.2 Experiments with quadratic optimization tasks and multiplicative noise
56
Q.2.1 Discussion of the experiments from Sec. Q.2.2
56
Q.2.2 Plots
56
Q.3 Experiments with quadratic optimization tasks and additive noise
57
Q.3.1 Plots
58
14

---

A Bidirectional Compression
In this section, we discuss simple way to use the Shadowheart SGD techniques in the setup when broadcasting is expensive (Line 7 in Alg. 1); i.e. when Teerv > 0. We will employ the following family of compressors.
Definition A.1. A mapping C Rd x S + IRd is biased compressor if there exists (0, such that
Bn [[(=;;)) =1|² - (1-a) |x=|,, Ye R².
(19)
We shall use the shorteut C(:;)) C(x)), and denote the family of such biased compressors as B(a).
The family B(o:) is more general than U(w) in the sense that C e U(w), then (w 1) + B((w+1)-t) 1)- It includes the Topk and RankK compressors (Vogels et al., 2019; Beznosikov et al., 2020), among many others.
Let Ceery E BBa) be the compressor used by the server. We use the primal error-feedbuck mechanism EF21-P (Gruntkowska et al., 2023) which requires to add the following changes to Alg. 1 and Alg. 2. We add the steps
p Czerv (xe k+
w²),
w 1+++ w + p
to Alg. and broadcast p**1 instead of z This change leads Bidirectional Shadowheart SGD (Alg. 5). Alg. 2, the workers should receive +*+ calculate w and use w instead of x 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 y
16l Then as long as K 2
708LA Bidirectional Shadowheart SGD (Alg. 5) guarantees to find an s-stationary point.
Corollary A.3. the broadcast time Cuerv is not greater than Twerv, then Bidirectional Shadowheart
SGD (Alg. 5) converges after at most
Te,serv
768LA
(Taerv + 26 21" (w, o²/e, [bi, mi]))
(20)
seconds.
Remark A.4. If the broadcast cost can't be ignored, the time complexity of Alg. changes from (10) to
16LA x (rfull + 2t" 2t" /²/e, [hs, Tdl))) T.
(21)
where r 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 bidirec- tional algorithm. Consider that Cserv TopK with K < d. We can see (20) that depends on Tserv, that is much less than full "aerv because K & d. At the same time, (20) 1/a times larger than (21). This is a standard price for the fact that we use biased compressor (e.g. (Richtárik et al., 2021; Gruntkowska al., 2023)). However, a is very close in practice (Beznosikov 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. is never worse than Alg.
Comparison A.5. Assume that takes dgery seconds to send one coordinate from the server to the workers. If we take K 2 min {d, t" (w, o² " [h,,
in TopK, then T', sevv 0 (T.).
full disery the bottleneck in (21) with Alg. 1, i.c., diserv > t*, then one can take K / Pacvv < dl in TopK with Alg. 5 and improve the time complexity.
serv
15

---

B Frequently Used Notation
We thought table of frequently used notation could be useful. Here it is:
Notation
Meaning
tolerance
Function f RR + R whose E-stationary point we want to find (see (I))
Smoothness parameter f (see Assumption 1.1)
Lower bound on f (see (1.2))
3
Stochastic gradients V f(:;E) have variance bounded by o² (sce Assumption 1.3)
Starting point of all algorithms; a vector in Rd
Positive stepsize used by all algorithms
A
A f(x")
number of workers
hy
Maximal time it takes for worker to compute one stochustic gradient of f((:E) Minibatch size associated with worker (worker compresses minibatch gradients) Number of compressed messages sent to the server by worker i in single iteration Set of unbiased compressors with variance parameter
b
U(w)
0 (see Definition 2.1)
Cip
Compressors used by worker ;; Caj E U(w). E [1..... m.)
Maximal time it takes for worker to communicate vector C.y(.). where Ciy U(ww), to the server Time it takes to send to worker one float to the server (equal to of the Randl compressor is used)
B(a)
Set of biased compressors with contraction parameter 0 a S 1 (see Definition A.I)
Curv
Compressor used by the server; Canr E B(a)
Maximal time it takes for server to broadcast non-compressed vector from 12 to the workers Maximal time it takes for server to broadcast vector Curr(.)), where Cuery [B()), to the workers
ware
Terv
Time it takes for server to broadeast one float to the workers
Equilibrium time; function w. "/=, hı, ....... hn,
Tu (see Definition 3.1)
Time complexity of Shadowheart SGD (see Corollary 4.3)
TMB
Time complexity of Minibatch SGD
(16))
TB
Time complexity of Rennala SGD (see (17))
9 O(f)
Exist such that g(2) < C f(z) all 2 2
9 9())
Exist such that g(2) 2
((2) all z Z
9 O())
g O(f) and g ()()
(a.
Set E Z a S
fl..... n)
C Basic Facts
Here collect some basic facts which are used repeatedly in the proofs.
Variance decomposition. Let _d random vector with finite mean and finite variance. Then for any deterministic vector E gd we have the identity
E [| E [=]]|]]]
= E || cl
[2] cll
(22)
Lemma C.1. Consider sequence .1..... In E [0, 1]. then
Im II (1 qm))
Proof. We prove by induction. For 1, is it true: 1 - E Fm II (1 9m). Assume that that true for Then
Σ
II (1 4m).
4m
m=1
m=1
Multiply both parts by 1 - In E [0, 1] to obtain
II (1 4m (1 (n) 1
4m
1
On
4n + On
Σ
4m
2 -
Im
m=1
m=1
m=1
m=l
m=l
since 9m [0, 1] for all m [n].
16

---

D RandK Compressor
Definition D.1. Assume that S is a random subset from [d],[S] K, K E [d]. A stochastic mapping
C: Rd x Sy + 1 is RandK
d
C(x;
Σ
zjej.
K
jES
where {es is the standard unit basis.
Theorem D.2. CfC is RandK, then C U ( -
One can find the proof in (Beznosikov et al., 2020).
E Proofs of the Properties of the Equilibrium Time
Property 4.1. If all inputs of the equilibrium time are non-negative, then the equilibrium time is well defined.
Proof.
(Part 1: 5* (j) is well-defined)
First, we show that s* (j) is well-defined for all j E [ra]. We fix j E [nx] and consider the equation from Def. 3.1:
(23)
2Tx 47,, a 2h
axe
(+)
((+)
w.t s. The function ((s) is non-increasing function for all 2 0, and the function (ss) is an increasing function for all s 2 0. Let us consider two cases.
1) Exists p S j such that Ta and Nr," = 0, then
-1
Σ
1
oss)
+
(co) 0.
2T
4rm; by he oww 2hr, o²
0
8xE
for all 0, then the only solution to the equation is ===0 0. 2) Otherwise, we have
-1
((8) = Σ i=1 2T
> 0
1rs, Ar. dzw ax8
2h,,, 0²
2hn 0²
1=1
2Tz
for all 2 0. Then (()) > 0 (can be equal to oo). Using (b()) 0 and the monotonicity of the functions, one can show the unique solution (greater zero) exists.
a permutation æ unique, then the formula minje(m] max max(h Tx, ( well-defined and can finish the proof.
(Purt 2: non-unique permutation) We assume that there exists i [n] such that max(h;, n
Otherwise,
minjeln] max max(hs, Tx, sh)*(()))))))) = oo for any permutation. Next, note that s 1) (j) for all j because
2Tx
47s, Ne, mww 2hr,0² oxe
2T
45x, Mr, mpw exe
2hr o²
for all > 0. We will use this property later.
17

---

Consider that there are two non non- -quualqul permutations и and क that sort the pairs (hq, by max h,, Te). and there are two corresponding solutions s" (j) and s" (j). Each permutation divides the pairs (he, Ti) into the same equívalence classes:
max max(
Tm,
max ( Tmys < max T =... max(h Tmpp2 } <
C₁
C2
max( Jail
max Tan
max(hes 12 Tnnnni
max(hrss Tmp22 < -....
C1
The order within each class can be different, but the elements are the same, Next, since (j+1)5 s* (j) for all n, we can conclude that the minimum in
min max max(maxt max (hn,, Tr, s()} JEIN
is attained for j" such that max s Tay. J < max max(hry ( Taynss) Tappe } (max(ham Fan11 = xc). Since max (/rz. Tr,,) < max max, (M 41), we have max ( Tzş,) = max (1z T7,... Therefore, we obtain
min max (max TayJ, (T) max Tay- fny-b s [ maxxmax(hbr Tay. J, (5²))}²²² jE(m)
Also, for all j E [m]] such that max(hry Tnş} ) < max/hrsm Tasth have
2Tz, w + 4Te,he, hr, mpw
axc + 2h o²
2T w + Aa, oaw
2hg o²
Aml
Therefore, get s* (j*)= =( and
min max(max ( Try }, s" (i) = max max hay. Ta,- 1..3..50 11*)) 2 min max max 1R, (1)). jE(n]
SE[N]
Using the same reasoning, we can show that
min max mmax ) 5* (i)) 2 min max J 8 (j)}. jE(n]
jEIn]
means that min max (max ( JR, }. 5" (i)} = minjejn] max(max W Ta, J. s" (j)}, thus the final result of the mapping does not depend on chosen permutation.
Property 6.1. If 2 w > 0, / 2 / 2 0. hy 2 hy 2 0, 2 n 2 O..... Th 2 hn 2 0, and
Fn 2 Tn 2 0, then t" (a, /e, (he, Tll)) 2 t" (w, " [h,, l.)
Proof. Assume that æ is permutation that sorts the pairs (1), by max Ti); and a is permutation that sorts the pairs (h2, 7,) by max (he, F.), then
2T + 47x, ter d'w
+ 2hr,a
2F 1 + 17s, ha, 83 2hs 8z
86
for all j [n]. It means 8*())= > 8J),,, where s²()) and 5'() are the solutions of the equation (7) with the pairs (hi, Tι) and (he, 7.) and corresponding permutations л and म. Also, we have max (bay, Tny) S max max(ha, FRy) for all j E [n]. Therefore, we have
(w. 02/e, h1, Ti...., hns Tx) min max max((ry Tay 3. (J) S min max(max(ha, Jx 3. +x)) jE(n)
jE
= (w, 0²/ ,,, ,,.... ,,,,,,..., Fn).
Property E.I. For all c (0, and w, o² /e Tly..., An, Tn 2 0, we have f 2. h1, TI.... bn, Tn) cx ts (w, 0²/e, hy, Ti,... has Tn).
18

---

Proof.
Using the definition of the equilibrium time, we have
(w, o² /e, h1, Th.... , Tm) = min max bay Tag 3 (j)},
_E(n]
where sJ) is the solution of
17,, o'w
21, o²
8,
(24)
2Tx w
86
and
flexwicx'%l ,.... hus Tn)
min max Tn,3 s(()) je/n
where si( is the solution of
-1
Te No. aww +
2ch+,0 o²
8.
2CT,, w +
Using simple algebra, we obtain
Σ
2CT w + 40 To, Bua mw n
= c
4Ta olw
2h,,0² o²
2T W +
g
Thus, (i) is the solution of
-1
Σ
(25)
2Taww + on 2ha o2
Comparing (24) and (25), one can see that (5( = cx for all j E [n]]. Using this and E (0, 1}. we get
o hi, Th.... hny Tn) min max Tay cx jE(m)
cx s² (j)}
x min max (max Jn J, 8" (i)} 1" (w, d²/e, by T1, ........ hn Tn).
jE(n]
Property E.2. For all c 2 and w, 0²/e, h1,
Tn 2 0, we have
(cx w x d²/ /e, h1, , hn, Fn) S x t" (w, 0² /2, h1 hns Tn).
Proof. The proof of this property repeats the proof of Property E. up to the last inequality. Using C 2 1, we get
(' (c / ....... hns Tn) min max Ta, cx s s'(i) 5E(n)
S x min max(max J, (i)) = c t" (w, 2/ hy m..... An: Tn). jE(n]
Property E.3. For all c E (0, 1] and w, 02//,11 hi .I...., Iin Tn 2 0, we have
(c w, d2/ [h, T 2 c x (w, / [h,, Tll) and t" (w,c x 0² r(lf) 2 c x
(ww,0%/ [h,, T.))).
For all e > 1 and w. o2 hi, hi........................... (w, o²/e, A, and to (w,e x o² 0²/e, [h,, Tdll) ex ts (w, o [h, T(l))
Tn > O, we have (c x w, o,,2 (.).7)))
5 cx
Remark E.4. We can obtain stronger inequalities. See Properties E.1 and E.2.
19

---

Proof. For all c E (0, 1], using Properties 6.1 and E.I, we have
(c w, /0, h1, TI..., hn Tn) 2 t" w.c /e, TI. Tr...,, An Tn) cxt (w, / /e, Frr.., has Tn)
and
(w For all 2 1, using Properties 6.1 and E.2, we have
b,, Tn) 2 1- (c x wx d " cx (w, 0 N1, r.....y Was Tn)
("(c w, o /e, Th...., ,.....,,..... Tn) S 1s (c w, c of TI, Nn, S (w, o² M1, T....- nay Tnl
and
(" /1, ha, S (t we o /,, TI, Ma, Tn) Scxt(w . Ma
has Tn)
Property F.5. For all e and w, o oe,e ,
TI...., .n......::.......... In 2 0, we have
(w, / x hi x Th..., x bns c Tn) = xx (w, / h1, has Tn).
Proof. For c 0, clear. Assume that 0. Using the definition of the equilibrium time, have
(w, d' h1, .I... Ans Tm) min max max ha,, Txy b, (j)),
sE(n]
where s"( is the solution of
-1
Σ 1=1
8,
(26)
2Tx NT,,ng,020 2h,
and (w, (W,,0%/e.c h x , Cx An, X Tx)
min max(max fc x May. &2)),, jE(n)
where (0) is the solution of
Σ
16 oo
2ch
2CT w +
+
For both cases, take the same permutation Using simple algebra, obtain
i
Lo o aw
2cha o²
=c
4t oew
2h, o²
2CT w +
2T w +
s5
c
Thus, (i) is the solution of
-1
(27)
2T + 4Ta Rew
2hg oz
6
Comparing (26) and (27), see that s5(1)
s" (j) for all j E in]. Using this, get (w,," /o,e x hif0 X e Wn, x Rn) = min max (mnx fc by,, e x Try F 8 (i)) jE(n]
=ex min mmx Tr, JEIn]
)()) ), c t" (w, 0²/e, hi, II...., hn. Tn)
Property E.6. We fix nonempty subset S = (ki,.... .ki....,,u.. km from the set [n] with size m 2 1. For all w. ,2/e,, h1, .I...., hns Tn 2 O, we have
(w, 2 h1, Fı. An, Tn) S = (w, /2/ Thi ...., Aeees Tkmm
20

---

Proof. Using Property 6.1 with T; = oc and h4 oo for all i & S and F, = and h; h2 for all i S, we have
t" (w, /e/ h1, Ti... has Tn) S t (w, o²/e, /e, h1, F1, Ans Fn).
Next, using Def. 3.1, we obtain
t" (w, 02 /e, h1, F2, Fi..... An, Fn) = min m Mnys Fxz s (j)},
jEin]
where s sj) is the solution of
(28)
2T + 18,, hr, dpw 2h a²
ex2
w.r.t 8 for all j E [n], and æ permutation that sorts max (h,, 7i} in such a way that the set (....... Tm equals to the set fki...., km J (the order of elements can be different). Such permuta- tion exists because max Fi} oo for all & S. Using max(ha. Far = oc for all m, we have
(w,, /0,,, h1, ..,..., hn. T,)) min max Fa, J, s. (J)}
(29)
jE(m]
By the construction of (28) and (29) depend only on the elements from S. Thus, we have ("w,, //, hu, Th...., hns Tm) S t" (w, o /e,, //e,h (1,
Fn) FI,..., has
(w, o²/e, hKg Tkys .... h Tkmm
t" (w, /e, hur The....s hRm Th
Property E.7. For /e, h1, $1.... :......h.. Nn: Fn 2 O, we have
12t (0, o² d²/e, h1, di hns dir.) 2 t (d 1, ,/,/,,, h1, t...., Nn: fn)
Proof. For d = 1, it is clear. Assume that d >>>>>>>>> 1. Using the definition of 1", we have
a²
8" (0, hi, Nn, din) 2 min max max max din, }. JE(n]
(30)
where स is permutation that sorts maxfhi di.). Assume that j is the minimal index that minimizes (30). Then
max(ha dia } o²
t' dt, hn, din) 2 max
(31)
h
Let us define
1= = (d- (, ,,,... Bns kn).
Using Property E.6, we have
1. S 1" 1, May fm :......, Maye taye).
Using Def. 3.1 of t", we get
1, < max max max max(ltz, f, 8
(32)
jEb"
where s* is the solution of
1 dfr Nn (d-
(33)
2h, 0z
2ix,
(d
1)
1=1
ax6
21

---

1) Let us take s 12 max ((d-1) maxjel
tRy; o² (E/
1
}
Since s 2 (d
big
1) maxjeb"1 Tay, we have
Σ
W4
1=1 nt (d - 1)
48a, hg o2 (d-1) 2hg,
n (d - 1)
4hg,
2hg
i=1
-1
1
2 (d 1)
6hg o²
$ 12
min
TR. (d 1)
im
If there exists E [5*]] such that (d-1
then
hapo
1
min
Ta. (d
0
T&p (d
and
-1
Σ
1
12(d 1)
S 12( 1)
max tay. jEli-]
2ir (d - 1) +
4ta, hy (d
+ 2,, o²
8766
Otherwise, we have
1
min
in, (d - 1)
he
he
1=1
1=1
and
-1
0²
Σ
12
12
27a, (d 1) + 48a, hy (d
2h, o²
E
h
8'
Considering both cases, we have
-1
σ²
1
< 12 max
(d-1)
max JEG
:,.
8.
27a (d 1) + 4Fs, Ne, oe, (d-1)
2he o²
hige
x
It means that s* < s' because s is the solution of (33). Using (32), we get
I, S 12 max
max max (1ays FR. max (d - 1) max JEli"
TR
JEL'
Time
i=1
Using d d21 and ding I max max diny) ), we get
0²
1
I. 12 max
max max (bengs din max jE(
max max (ha din 8Ebr-]
has
1
< 12 max
max max(h dis jE(=*
li:
i=1
22

---

Due to maXje(j*] max(hz, h dia,1 } = max(ha dia and (31), we obtain
= / /e, fI.... May in) S 12 max max(h dix
lis
- 12t (0, / /e,,, h1, dii,.................. has din))
Property 6.2. For all K E [1.d] h1, $1....,
Nn: in 2 0. we have 24 x
1" 14/-1,4 1,,% b1, K An, Kin) 2 to (d - 1, ///e/,,,,, h. An, fa).
- 1,
Proof.
(Part 1: K 5 2+1)
For all K v d+1
we have
d
t"
1,0%% Ki, Kt. hns Kin
min max max/max(h,, Kix, s (i),, (34) jEIn
K
where s s"(j) is the solution of
i=1 2k (# 1) + 4KFs, Me, o2,,o2( ( -1)
2k o²
8xe
and π a permutation that sorts max maxfhj, Ktt}: }. Also, assume that j" minimizer in (34). For all j E [n], we get
(
i=1 2K ( -1) +
het 0² (
4Ktr, hr,
2h
(())xx
48 Ne, (d( K)
2h, r²
i=1 2t. (d K) +
+
Since K
d+1 2
have
-1
80 2
Σ
1=1
24 (d - 1) +
48r, nr (d
x* xi)xx
+
2h o²
and
2x 2x
Σ
(35)
2ix (d - 1)
14, Nn o o2(d-1) 2x.0 (xxx(i)xx
2h, 0²
At the same time, using Property E.6, we have
1n (d - 1, 0,,"/,,,, 21 f....., An: Fn) E t" (d 1, 02/e, Nwy "......,,,,,...
May. fay.)
S max max max max,, (,, jEb"*
(36)
where <(()) is the solution of
4F n (d-
2h,, ae
S.
24. (d - 1) +
axe
From (35), we can conclude that 2 x s" (i*)) 2 s'()). Using this and (36), we obtain
to (d - 1, o2/e,, h1, ......, in) S max max max( h 2r, ). J. 2s (j*) jel
23

---

max max max
JEli1
max max max Kta, 8 (j"))
Note that maXje(i-] max(ha, Kta,) max hn a thus
to 1/de,,""/,,11. f1......... An in) s max Kta },s) = 2t ( d
1, o h1 Kfi....... ....,,.,,....................... ,n, Kin
K
(Part 2: K > d+1) d+1 2
For all K >
using Property 6.1, we get
ta d
1. h1, Kt ........ hn Kin 2 t"
K
1/,,,
1 d d 0,,²/0 h1, 11
hnn
2
Next, using Property E.5, we have
(x
-1.11 h1, Kt. Ans Kin
2 2
is left to use Property E.7 to get
1" ( d - 1, /1, Kii,..., An Kin
2 - t" (d
M1, 51 0/,
Am in).
K
24
F Derivations of the Examples for the Equilibrium Time
Example 6.3. [Infinitely Fast Worker] If exists j E [n] such that Tj 0 and hy = 0, then t" 0.
Proof. Let take permutation where क Such a permutation exists because max Ty} 0. By the definition of t", we have
to (w, 11, Th.... Nns Tn) min max max (hax ( (()) jE(n]
< max (/ s.
(37)
max s (1)),
where s s1(1) is the solution of
Σ
47x, A- dww
2h 0z
8.
iml
2Tx w +
Since
Σ
- =0
4Tx, Str,he, 2h o²
2Tx w
86
we obtain (*(1)= =0 We substitute it to (37) to get 1" (w, / hi, ...... Mnn =
Example 6.4. [Infinitely Slow Workers] If T. = oo and h2 = oo for all i [n]. then t" = 00.
Proof. By the definition of t", we have
(w /2/, hy, Ti, Ti.... hns Tn) min max (max Try s0)) s = min max s((i)} 00.
jE(m]
jEin]
24

---

Example 6.5. [Equal Performance] If = T and h4 = h for all i E [n], then" 10
1" < max
h, T, T hr?
rhertw
(14)
Proof. By the definition, we have
(w, / h1, T Nns Tn) = min max s), s²)) max J min si)) = max TJ. s
je(m]
jE(n]
(38)
where is the solution of
2Tw +
4tharw 2ha²
Since
-1
-1
2rw
4
2ha²
2Tw 4wh
2h
2Tw
4whor 2hr
7
871
n1
88
85
we have to solve and find the non-negative solution of the quadratic equation
2Tw n
2ho² ne
Arho
s²
0.
ne
The solution is
Tw
1022
Tw
ho2
2
4Tho
TW
ha"
Tho
+
+
2
+
n2
nE
ne
nE
Ne
nE
Therefore, have
Tw ho
Tho?
1" (w, " , Th, "al...,,au, ,n, Tn) S max max mnax(h,77 T,2
ne
h1 T, Tw ho²
Tho?
$ 6max
ne
ne
Example 6.6. [Infinitely Fast Communication] If 0 for all i E [m], then
(1+ a² ) (15)
hamm o²
ta 2 min max me(n)
min mE(n]
where π is permutation that sorts {h
Proof. By the definition, have (w, /²/e, hi, TI. ....... Ans Fn) minze(m) max(ha, s² (i),
where s (j) is the solution of
2h
8.
1=1
Therefore, we have
o²
o²
(w, 02/2, hi, TI...., Any Tn) < min max
hzy
θ
min jE(ni
h +
Σ
/E/n|
he.
E
im
Using Lemma F.I, we obtain
("s, (uw,02/s, hi, TI...., In, Tn) S min max
lizs
-
min
j +
-
jE(n]
jE(n
h
Foromm the proof, is clear that the result tight up to constant factor.
25

---

Lemma F.1. Let us consider the two functions
g h1 +a
Σ h4
p()) (j aa)
h4
for all j E [n], where h4 2 for all E [n], a 2 0, and h ... ... S nns Then
min g(i) min p(i) s min g(o) JE(n] jEin|
jE[m]
minte(m) h(t) 0. Assume that h1 > 0. Using the fact that a harmonic mean is less or equal to the maximum, we have
Proof. If h1 O, then p(1) h(1 = 0 and [m] [m] p(t)
min p(j) = min (j + a)
min JE[n]
hy + a
min g()). JE
jEIm|
sEin]
Thus, we proved the upper bound. Next, assume that j" is the smallest minimizer of p(j). jf 1, then
min p(i) = p(1) = (1 + a) = h1 + ah, = s(1) 2 min g(i).
sC(m]
jE(n]
Otherwise, if > 1, then p(j*) S p(j"
1). Using simple algebra, obtain
+
$ {5" a
h4
i=1
# (j"+aa
Σ h;
S -5 10
Σ h;
:=1
$
h+
h3g
==1
5' 1
+
hy. < (j" aa)
his
Using the last inequality, we get
-1
-1
f' 1
min p()= = (i" + a)
1
(j" +a)
Σ Σm
+ 2
+a)
(j
+a)
Σ1
JE[m)
hi
2
h4
i=1
-1
1
2 h1.
+
a
=
9(0)) 2 min g())
2
2
2
2
jE(m
i=1
Example 6.7. [gnoring Slow Workers] If h4 and Ti are fixed and finite for all S p, and max hy, T&- = m E IR for all i > p, then, for m large enough, we have t' (w, //2,, [h4, T.l1
(w,, a² //, T.P)
Proof. By the definition, we have
tw, hy, Ti....,,, Ta) = min max max(max (hago Try 1 8())
jEjn]
26

---

For m >> () max {h,, Trh. we have max (h,, T.) < m for all S and the set {l.....pl .p
equals to {TII....: TpJ. Thus, we get
(w,, / h1, Th.... Any Tn) min
min m Txy J (()}, (EEp)
min je ve(n-lmm))
max(m,,"(i))
min (w, h1, T1, hp Tp), min jElptI.....t
maxfm, s (i)1}
By taking m (w / hi, Th...,, Th...,,pp Tp), we obtain
min je [) max/m, s" [i}} 2 m > (" 0² 0²/e, h1, hp.
Therefore, we have
(w, o² h1, TI,...,, Ans Tn) (w, /2/c n1, T1.... Np: Tp)-
Example 6.8. [Partial Participation] If max xo for all > 2 1, then (w,," /e, [hi, m (w, /e, T.l).
Proof. By the definition, we have
(w,,"//e, /1, Ti........... , An Tn) = min max (ha,, Tay J. (j)}, %E(n]
where π is permutation such that the set 1 .... An equals to the set {p 1,..., n... Such permutation exists because max h,, Ti = oo for > p. Using this, we have
min max/max Fr s())
(w, d²/e, e/ehh h1s TI..... hns Tn) = min
min max Tx, J. (i}}, (Elp)
je I...)]
min
min max mmax (hy, Tr, }, (1),,, (jElp)
min max(max(/m) hT Tay J (i)} jElpl
= =w, /²/e, h1, 11,,,,,... TI.... hp. Tp).
G Generic Lemma For Unbiased Gradient Estimators
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 estimator
by Vsat
g²
WisCis
ek
Li=1
E Waybis i=1
where m, 2 0 for all E [n]. big 2 for all E [n] and j E [mg]] are ordered batch sizes (b11 < be.m; for all
[n]). wyj 2 are weights for all [n] and E [mj], and Ei=l EØ= Wiybij > 0, Cij E U (wig) are mutually independent compressors from Def. 2.1 for all i [n] and j E [mme) and * Bd is arbitrary point. Then E
k V V((x))
and
m2
-
E En Wisbis)
im1j=l
11
m+
m7
mi
+
2 Σ Ena Wiy Wiybis
w
bi
min (byg. hip Jw Win
(39)
27

---

Proof. First, we show the gradient estimator is unbiased:
byj v Tfaa sti)
E
E
WiyCes
2i=1 2==1 Wiy
bij
wi
Cis
v f(x*; sshi)
Σ F
i== ا== Wiy bug i=
5=1
1=1
Using Def. 2.1 and Assumption 1.3, we have
11
Wiy Wiybi big Vs(x*)) = vs((a).
a Li=1 وド= bi
my
1=1
1=
Next, estimate the variance
E
||ga
E
WisCij
sa E3i
vs(att)
Di=1
j=1
Wight
iml
j=l
bij
E
CrsCes
Σ
V vf(="
Σ
W vf(
> プ Wiybis
1=1
Using the independence and (22), have ||g* - V
m;
m:; Σ
Σ
E
Σ
CryCis
V
fa :
biybis vf((*t)
Ei 2 Wis
mi Σ
big
E
WiyCis
V
Wij
V
( ck)
Ei 2 Wisble
1=1
T
bus
m
ct)
Σ
VS(x*)
Wij
Σi E Wisbes
Ø=1
(40)
Using the independence of the compressors and Def. 2.1, we get
27
12
m
biz
bis
h
w
E
Ci
V
f(
ck)
Σ
((
Σ D
2
Wizbis
i=1
j=1
72
beg vi(a
$
w
W
thi
EE_ En Wisbis
j=1
In the view of (22), the independence of the stochastic gradients, and Assumption 1.3, we obtain
27
mi
byg
bis
11 <
Σ
(x**)
ER Ege Waybess
1=
j=1
28

---

1
W bi
V )(
siml 2 Wizbis)
1=
big
1
V
n 1= j= Wiybes)
my
1=1 j=1
1
me
bi
|l( ?
Ei=1 دح= Wiybts)
1
1
why DofWejoo
w Buj
Ei= شز Weybes)
Ei= دك Wsybes)
i=
i=
We now consider
by
m.
12
E
Wey
Σ
EL= Eド= Wiybis)
Let us consider the set Su = {i [mm]] | bey} for all i, E N. Then we can rewrite the norm in the following way
bi Σ
12
Σ
wis
(V V[((at))
Eh E
my j= Wiybis
JES
The stochastic vectors are independent, thus
biams
12
Σ
Wij
E
| - V \
n iil / Wigbis)
x=1
1=1
JESu
berms
$
Σ
Wii
0².
EE Ejzi Waybes
1=11
JES
Note that
biom
2
Wij
Wip-
JESa
JESu PES.
The number of appearances of the term Wip in the sum equals to min bip) Thus
m. my
L <
min(bry, dep ) Wuy
Cf En W.ybey
We now substitute the bounds on 1, and 1z to (40), and get (39).
29

---

Algorithm 4 Shadowheart SGD
(Alg. is equivalent Alg. when hf ht and 7 +²)
1: Input: starting point x", stepsize y, the ratio ///-
2: for k == 0, 1..... K do
3: Find the maximum computation speeds h > 0
and compressors' communication speeds T. >> 0 of the workers in the current iteration
4: Find the equilibrium time t using Def. 3.1 with ny and r.
and m, + for all E [n] (t", by and m, are local and can be different in 5: Set 6, = M
every iteration)
6:
Find active workers SA = {i E [m] by A m, > 0} Run Alg. in all active workers Sx Broadcast x=, bi. and m, to all active workers SA Init gZ
7:
8:
9:
10:
for i SA in parallel do
Wi (g) (bew o + m; o²) =²)-
11:
+m;
12:
my for j = -,...,,; do Receive Cij (gt) from the 7th worker
g* = 9 + wrCCg (gt)
15:
end for
16:
end for
17:
gd/ (2i=1 wim;bi)) x k+1 x 79
9"
18:
19:
end for
(a)
If = 0 and g" O, then uy = 1
H Proofs for Algorithms 1 and 4
In the appendix, we work with Alg. instead of Alg. Alg. 4 more general and estimates all the parameters based on local per-iteration times h and T5 instead of h; and T. All results for Alg. 1 can be easily obtained by taking hy = h4 and Th T;.
Lemma H.1. Consider that Assumptions 1.3 and 2.2 hold. Then the gradient estimator (9) with the weights w. from Alg. 4 is unbiased and
E 1 V vf(aa)]
Σ 1:b:Amm:0
bmm 0² + m; oa
(1V +s).
(41)
biw +
Proof. Alg. 4 implements the gradient estimator (9). We can use Lemma G.1 with bij = bi, wij
and Wiy = w for E [n] and j [m..]. Using (39), we have
E ||0*
w w bi wis
[ 2+
En= E Wiybes
mi
m2 mi
Wiy bijawiso
min ( (bij. dip why Wipo?
Σn Di=1 Ej=1 Why Wiybis)
ia (m)bbw) V f(**))]
+
En miwpbr)
wf (mibooo? + bym
En m.n,)b))
==1
We add nonnegative terms to the last inequality obtain
w2 midlfw + mibwa o² + +bmm 8 ||
Σ
En m. m.bb)))
E
1=1
30

---

? (mibfwe + mibwwo? b;m?
EE= m2
1=1
wi m,,fy + m,b,uu + bymi (1VS(>+))
E m,w;b;)
1=1
Using the choice of the weights Wi, we get (41). Lemma H.2. Consider two quantities 2 and o² 2 O, and N. Also, consider a sequence of positive pairs (1hi, Te) We take k and m, + for all i [m], where t" = (w, N0,0//5, h1, Tl, ha.....,hh has Tn) the equilibrium time from Def. 3.1. Then
-1
ba
Σ
11.
Am brw + a
a2
m4
Proof. Assume that j E [n] is the smallest index that minimizes max max(max (max (bw,: Jry (t,),&(()) (i),, then
t max maxx Tzy- s. {j*)}}
(42)
Therefore, we have t" 2 max fh phyy. Tw,, 2 max (h Fxy } for all; S j" since max Tay are sorted. means that bry
and May
for all j S j. Using this, we have
han
Tng
1
Σ
b
bR me:
tb:bLAm;30 30 byw + w + m o
b w w + m
wa? by mxx
o²
my,
b
Since baz
2 and myz for all j Therefore, obtain
2 1, we can also conclude that bR, 2
and
Mej
2
ma, 2 2Tx;
5
25 w
4r,, ho war (1
2h, o² the
2r (5
4r,, hr wa² 2h oz
+
(6"'"") + x
t"
(j**
4T, Now xx(e)xxe
2k, o²
2Tz w
where the last inequality follows from (42). Recall that s" (j*) is the solution of the equation (7). Thus
sj
4r,, 4T,, w0? wo²
2h o²
2T w +
and
1
1 1 s-(i²)
x x8* = 1.
Theorem H.3. Assume that Assumptions 1.1, 1.2, 1.3, 2.2 hold. Let us take 7 27. in Alg. 4. Then for all iterations
16LA
K >
(43)
Alg. 4 guarantees that 1 K-1 E
||]
Se.
31

---

Proof. Let us fix any iteration & E N. Consider that 9& is o-algebra generated by ,". Then. given Gk: xt is deterministic vector. Using Lemma H.1, have
......
E
1
9h
b + m
[[Vf(+))(++))
1:bpAmm50 bew + w
Note that the choice of the parameters in Alg. 4 satisfy the conditions of Lemma H.2. Thus, we have
E
-
|I
+E
for all & 2 O. is left to use the standard SGD analysis from Theorem I.1 with = and C' - to finish the proof.
Theorem 4.2. Lett Assumptions 1.1, 1.2, 1.3, 2.2 hold. Let us take 7 = 1/2L in Shadowheart SGD
(Alg. 1). Then as long as 2 16LA/E, we have the guarantee Σ K-1 E ||[ S..
Proof. It immediately follows from Theorem H.3 for h4 A and 7..
Theorem 4.4. Alg. 4 converges after
20 (w,, ,²/e,, M Tf,.................. n
(11)
k=
seconds, where h > 0 and + are computation and communication times for worker in iteration k.
Proof. Let fix iteration index ie E [m]. In every iteration, every worker calculates b; stochastic gradients and sends m, compressed vectors. Thus, the processing time of each iteration is not greater than
max h b; + Ti m2 = max 1E
h
+ T
sE(n! < 2t (w, /²/=, h -.. .......... h:: =
h
(44)
Using the fact that the number of iterations equals to (43), we finally get (11).
Corollary 4.3. Shadowheart SGD (Alg. 1) converges after most T. seconds, where
T. 32LA 1st (w, o² / h1, .., ,,y Tn)-
(10)
Proof. It immediately follows from Theorem 4.4 for h = h/ and Tq =/..
I The Classical SGD Theorem
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:
k+1 xx - >)
where
1 L(1 B) 2LC
min
For all 2 0, the vector g(x) a random vector such that E, g(("')) Mc vf(a*),
E [lo(a=* - v
9n
s B B|| +C,
(45)
32

---

where GR is o-algebra generated by g(=")....,,(** The quantities B and C are arbitrary nonnegative constants. Then
K
Σ E
[V](at)]
K=
for
K 2 4LA(1+ B)
SLAC
62
Proof.
From Assumption 1.1, we have
[(*+t1) s f(x*) + (V)(x*)) x,,,=, - -xt) -,,+++=
L
2
In²
=f(x²) - (V g(x")) +
||9(at))12
2
We denote G as a sigma-algebra generated by ,,...,((*** obtain
). Using unbiasedness and (45),
[[( 8d (((x-)) - (1- (2)
||]
+ 422
[lo(0t) - V[((at) (/ g+
2
1 B)
|| + LT2
S f(zx)) -9 y
2
2
Since S [] we get
[ + In2C
E [[s g0 S $( - 2
2
We subtract f and take the full expectation to obtain
|(ل{a})) + L92C
[[s(a [-] s E [f(x*) |"] - F
2
2
Next, we sum the inequality for & E {0. .0.....44 K - 1}:
K-1
KLT2
E { - fr1 s f(x0) - f" Σ
E ||]
2
K
E
[|] ||² ||
KLYC
2
Finally, we rearrange the terms and use that [f(x*]- - fo] 2 0:
K
24
Σ E
< g
+ LGC.
K
k=0
The choice of y and K ensures that
Σ
[|>
E
Se.
K K=U
J Comparison with Baselines
In the following proofs, we use assumptions and definitions from Sec. 7. Comparison 7.1. T. O(TM)).
33

---

Proof. Without loss of generality, we assume that all workers are sorted by max f.). For the Randl compressor, we have w d 1. From Corollary 4.3, we know that the time complexity of Alg. is
LA T. = x (w, /e, ti,..., In, fn)
up to constant factor. Using Def. 3.1 tf, we have
LA
T. I max/max ( in), sn))) x
(46)
where s"(n) is the solution of
Σ 24t 18,b,0Aw axe
+ 2h.0²
8.
(47)
Let us take s' = 12 ma]) max
wti }. Using simple bounds, we have
ne
24t + 4tch,03w i=1
+ 2h
24t + 14ihyo3 8xx + 2h:02
s'xe
maxie(()
22v + o'xe + 2h.0²
max,e[m]
Since s 2 w maxee(n] Fe we get
maXie[n] (2i + 1h:o² + 2h:0²
Σ
2:w + 4w
8'x + 22
hoo" wti
12 max max
c
S
It means that snnn) & 8 since s² (n)n is the solution of (47). Using the properties of max and (46),
we get
h1o2
LA
T.
0
max
max An: in): max max
vE[n]
nE
11,02
LA
O
max
max (h; + (w + 1)Ft), 1E(m]
max (E(M)
+ max max iE(n)
ne
LA
LALA
1 ))
LA
O
max
max (/1 + (w + 1)f,) sE(n]
maxx h1 X sEin]
ne2
max (w + 1) X |E|s
LA
LA
O max (h4 + (w 1)tt)
(E(m)
n
LA
LL
)) ng²
=0 max (hi + dri))
+
(E(n)
where we use w d.
Comparison 7.2. T, (TR)).
Proof. From Sec. 7, we know that
LA
T.
(w, oz o2/e, 11, f....., Ans tn)
and
LA
Tk =
x t" (0, o²/e, h1, di hnn din).
8
Using Property E.7, we get T, = OTTk) since = d for Rand1.
34

---

K Description of Alg. 5 in the Bidirectional Setting
In this section, we provide the modification of Alg. with the EF21-P mechanism (Gruntkowska et al., 2023). Almost all steps are the same 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², stepsize y, the ratio /²/c
2: for k 0, 1....... K do
3: Find the current computation speeds h > 0
and communication speeds T." > 0 of the workers
4: Find the equilibrium time t" using Def. 3.1
5: Set b,
- for all [n] Find active workers SA = [i E [m]
x and m,
6:
b, A m, 0}
7:
Run Alg. in all workers
8:
Broadcast bi, and my to all workers Init of =
9:
10: for i SA in parallel do
+ +m; o² -1 for j = l,...,,.. do
Wi (a) (bew
12:
13:
Receive Cip (gf) from the 7th worker g²= gt + WrCij (ot)
14:
15:
end for
16:
end for
ge 9²| (Ei= wim,bss
18:
x k+1 x² - 2
19:
p*+1 Czerv (x wk)
20: k+1 w pht11
21:
Broadcast p
to all workers
22: end for
(a) If = 0 and Ø² = 0, then ui = 1
Algorithm 6 tt Worker's Strategy (init all workers with w" x0)
1: Receive 6, and m, from the server then
2: if 6, A m;
3: Init g. = 0
4: for 1o by do
5:
Calculate V (w ch), = " + V s(w"; gl)
sh De
6:
7: end for
8:
for j
11
do
9:
Send Ci (g.)
(gt: u the server,
D ~ DD, Cij- E U(w)
end for
11: end if
Receive --1 from the server
13: wh+11 w + u+1
L Proofs for Alg. 5
Theorem A.2. Let Assumptions 1.1, 1.2, 1.3, 2.2 hold. Choose T6T. Then as long as K >
LG Bidirectional Shadowheart SGD (Alg. 5) guarantees to find etattonnaryy point.
35

---

Proof. In the bidirectional setting, the idea of proof is the same as in Theorem H.3, Let us fix any iteration & N. The gradient estimator has the same structure as (9) but with w instead of x
g
Cij
ff(w"; ;
w.mbb
Consider that 9% is a o-algebra generated by all random variables from the iterations O,..., k - 1. Then, given Gk, w is a deterministic vector. Using Lemma H.1 with x² = w and Lemma H.2, have
E
I1o
vf(w=>)] G - f
||| +E
for all &o 2 O. is left to use Theorem E.3 from (Gruntkowska et al., 2023) with 2 and C' to ensure that minogegk- E
after 768LA iterations.
L
Corollary A.3. the broadcast time of Eeerv is not greater than Tserv, then Bidirectional Shadowheart
SGD (Alg. 5) converges after at most
T. sery
768LA
(Taerv + 28 (w, / [1g (i)
(20)
06
seconds.
Proof. Let us fix an iteration index & E [n]. In every iteration, the server broadcasts one compressed vector, every worker calculates stochastic gradients and sends m, compressed vectors. Thus, the processing time of each iteration is not greater than
1"
Tserv + max (heb + of m/
TeeTV + max iEinl
N
+
iE(n]
Teerv + 2t (w, a² "²/=,, h" T/ .....
P..
Teerv + 2t" (w, o² o²/2, h1, T1..... hns Tn).
Using the converge from Theorem A.2, finally get (20).
Comparison A.5. Assume that it takes Egery seconds to send one coordinate from the server to the workers. we take z min {d, (w, ///,, [hi, //ser) in TopK, then T. T.,erv O (T.).
Proof. From the assumption, we have Tserv = Kiserv and serv = diserv. For TopK, a 2 K/d.
Therefore, up to constant factor, obtain
LA
T serv
x
(Teorv ('(w, [hi, r(l)))
dLA
x
(K + t" (w, /²/,, [hi, T:l1))
Ke
dLA
dLA
Teerv
+
t" (w, (w,""/e, lhs, [i]l
KE
dLA
(LL
LA Tserv; 1' (wo, 0² [hs, mil)
Tscrv + max
dLA
LA
< 2
Teorv
t' o/,,o///, [1.,,
Also, up to constant factor, we have
LA
T.
X full
(Terrv + (w, /², [bi, T: rz)
LA
X (ditser + (w, /²/e, [hg T)
dLA
LA
Teerv +
to (w, 0²/8, [h,, T.77)
Therefore, Tr.srr O (T.).
36

---

M Development of Adaptive Shadowheart SGD
Algorithm 7 Adaptive Shadowheart SGD
1: Input: starting point x", stepsize y, the ratio /
2: for k 0, ........ K do
3: Run Alg. in all workers
4: Broadcast = to the workers
5: Init I, for all i E [n]
-1
6: while
Σ 1:4,30
Σ
wea Pmmae
o² Ise
do
7:
Receive Ca.li,m... (9t) 4 and ms,t; from some worker (we indicate this worker with
8:
if miJ, = and 1 > 1 then
9:
0: D: + m,- Or and O: = 0
10:
end if
11:
Ô: + Cidiimaa (9:)
12:
end while
Init g
14:
for [m] l > 0 do
9t D: + mi,t, 9i
16:
wi (a)
Eラ=1 mij
1:
Σラ=ı l.mays +
wa?
40²
6
gt g"
+ wigi
18:
end for
19: g" = /²/ Ei: Wi Σ/=13)
20: x x+1 x 7
21:
end for
(a) wf = 0 and o² = 0, then w; =
In this section, we design new method that, unlike Alg. 1 and 4, does not require the bounds on computations times. automatically understands when stop the collection of compressed vectors in g².
Let us consider Alg. 7, which we call Adaptive Shadowheart SGD. implements the following gradient estimator:
mii
W6
Cisp
Σ (f((tt)tt))
(48)
Giml W:
m
The idea is that each worker calculate and send compressed vectors in parallel: while the next stochas- tic gradients fx" : are calculating, the workers are sending Cij. (Ein V <t:)) to server. The main difficulty is to understand when stop. It turns out that is sufficient 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 7 = I in Alg, Then for all 2I
iterations K 2 16LA Alg. guarantees that K Ek= [| |1 Se.
K-1
Corollary 4.6. the computation and communicution times are positive, the time complexity of Alg. is LA (ws, 0²/e, [max Ti), min (Teis, max nhax(h,, Tz))]t up to constant factor, where is defined in Def. 4.5.
37

---

Algorithm 8 7th Worker's Strategy
1: Receive n² from the server
2: Init 4, =
3: Calculate 9i - Vf(a"; shi), en ~ De
4: while True do
5: Start calculating fz(=;; 11 Stitt ~ De. and go to the next step
6: Init mi.l. =0
7:
while ; (i,,,+1) is not calculated OR mil. 0 do mi, = -mi,, + 1
8:
9:
Send Ci.s.ma,. (g:) la and maj, to the server, Ci E ((w)
10: end while
11: 9i = 9: Vf(a;; (1,.111)
12: 4 +1
13:
end while
N Proofs for Alg. 7
Lemma N.1. Consider that Assumptions 1.3 and 2.2 hold. Then the gradient estimator (48) with the parameters from Alg. is unbiased and
E I|o** vf(aa)]1 54
Σ
Σ
w mase
o²
(IV + +c).
12mi
1
4E
se|n]:4200
(49)
Proof. Alg. 7 implements the gradient estimator (48). Note that since Cisp E U(w), then
mij "n= Cijp E U(*/mg). Therefore, we can use Lemma G.1 with wij = w/mo, bij = j. Waj = Wi, and m. = I,, and get
1
j2w
[f(++)1
V
2
Ei wi E/
Mij
1=1
jwo
1. 4
Σ
+ Σ Σ min (1, p}o²
1
En We Ej=1)
Mij
5m1
jml pm1
Since E/=1 E/ min p) - 19, we have
-f(a->)11 x
j
Vf
)1
Ei wi Eソm
2
w
==1
mij
+
1
Σ
n
1: Σ
jwo
1,02
3
En_ we Σ}
mij
i=1
j=1
38

---

We add nonnegative terms to the last inequality to obtain
E III*
j2w w
ju o²
1302
| [z]())]
s
+
Li E}=15
mij
mij
8
jml
1
jewe
1
jwo
+
W
+1902
Σ i==
wi -5 5
1=1
|=1
Maj
j=l
mij
p2w
ju o²
+ )1300
(IV8(++))(+E) +c)
Σ
w
+ Σ
E
-i=
2=1
j=l
mij
j=l
mij
E
Using Σj= 12
1 2, we obtain
jaw
Mij & + 120²) (17)(()))(+)).
ju o²
E -loo-vS((t
w
El= m,(
Mij
In the last two sums, we bound the terms with 4 to get
n
4
Plw
1. La o²
+ (²=²) (1V)6+))(+0)
[1o0- Eh w;
wi
Mij
Mij &
is left use the choice of the weights wi to obtain (49).
Theorem M.1. Let Assumptions I.I, 1.2, 1.3, 2.2 hold. Let us take 7 -K11
1 in Alg. 7. Then for all
2L
iterations K 2 16LA Alg. 7 guarantees that 1 K
[|]]((+)]|
S
Proof. The proof of this theorem is very close to the proof of Theorem H.3. Let fix any iteration & N. Consider that GR is o-algebra generated by o....., ....,gg* g-1 Then, given Gk, a²t a deterministic vector. Using Lemma N.1, we have
E | vs(>>>>
9h
S 4
Σ
w Pmije
0² +
(1V
Pmmss
LE
:4:00
:4:00
The algorithm is constructed in such a way that the first bracket in the last inequality is less or equal (see Line Alg. 7). Thus
E
||o - vf
9 < |f(x>)]| +E
for all & 2 O. It is left to use the standard SGD analysis from Theorem I.I with = and C' = C to ensure that the algorithm converges after 16LA iterations.
Corollary 4.6. If the computation and communication times are positive, the time complexity of Alg. is LA t" (w, o²/e, mmax(h; T,), min (Trrs, max(h;, T. T.lll)) up constant factor, where Ty is defined in Def. 4.5.
Proof. Let us fix an iteration and take k E [K]. It is sufficient to find a time required to send enough compressed vectors such that the inequality
-1
4
Σ
w
0²
S1
P Fmii
mmsss
4,5
:E(n]:1:20
39

---

holds. 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 to
H := kE(m] 1,.00
1.
(50)
Aw
+
20
7,5
Let us show that
:= 128 x (w, /e, max (h,, Ti min frim max max(11, m max max Fn), min (Turn, max(hn {n)
is 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 permutation æ that sorts the input pairs (max(h;, Ti), min (Trr max hi T:}}) by
max { (max (hi, T min (rr, max (hi, T())).
This term equals to max h, 7... Without loss of generality, we assume that the sequence max(h; T sorted, thus æ; i for all E [n]. Therefore, have
= 128 min
T (i),
(51)
JE(M]
where 8 s"(j is the solution of the equation
-1 -1
4 min {T,,,, max [h;, rr) max(h;, Ti Jow
2 mmxx Mi, T; 7/102
2mi (Trr,, max(h; nH) w +
=
(52)
for j E [m].
Let us define j" as the smallest by index minimizer in (51). Then
128 (y
Assume that 4 is the number of iterations (the number of calculated stochastic gradients) that the 7th worker does by the time f'. Since t' 2 4 max(hy-- Ty- and the workers are sorted by max (h,, ri)s we have l' 2 (h; + T.) for all i S 5r. Therefore, for all S j", the 7th worker will have time to calculate and send at least one compressed vector, i.e., I 2 1 for i S.
Next, the 7th worker requires at most Tr seconds to send a compressed vector and it waits for at least one calculated gradient. Consider that the computation time of the jth stochastic gradient in the 4t iteration equals to hyy- Thus 5 I Σ} (hy + Ti) Indeed, if 5 Ej (hy + T.). then the 7thh worker will have time to calculate and send at least one more compressed vector because
2 2 2 max(fh; T.} 2 h4 + T3 for all i < jr It would contradict the definition of 4,. Therefore, we have
t'
(hly Ti)
max hi + 4T7 ]E(l.]
j=1
and
t
4 2
(53)
2
max h Ti
jEllil
At the same time, by the definition of 4, we have
li
Ttmin
because Amiin > 0 the smallest possible calculating time. Therefore, have
Lmax
1, < Imax
huin
40

---

where max is defined in Def. 4.5 (tmax 2 t). Since 4 2 1 for all i S j",
we get
H =
Σ
1:
Aw
4
Awo2
20²
mig
13 masse
7,8
:0:0
1=1
==1
(54)
Aw
1
4wo
402
P Mim
1 mmie
415
1=1
j=1
Using (53), we obtain
80
max hij + T3 JE(L.
4 B
80 (14 + Ti) 160² max Ti)
+T))
el
gt!
el'
For every jth stochastic gradient, the 7th worker sends at least one compressed vector or h
compressed vectors because it is possible that Ti S h:y then the worker will have time to send more than one compressed vector. Therefore, we have
min h
h Ti
h
JE(4]
maj max
max
2 max
2T:
2T,
and
To
T2
min
2 min
maj
min h
min h
j=1
jE(L.)
(E(
Using the last inequality and (53), we get
max ]E[L]
h
+
min
12
Mij
t
min h [E((:]
max max h Ta)
JELL
Tx
min
1'
min h SE(L,]
max mmax M
TH)
max mmx h 73 jE(t]
8Ti
SE(L.
min
x
min h jeNl]
max ( max hy m.)
max h
It is clear that T <
sC[la]
If T3
min M then T = Sr. F
x
selta
RE-
If 2 min h
jE[l.]
SElla
jE
h ZERl
and T. < max
hk then JE(4]
JER;
If T.
li then jE(l]]
max
8T. 7
S
min SER
max A
Szz
JEUJ
min K
Thus, we have
max h JE[[.]
maxx max h Tr. jE(t.)
8T
min
maj
min h Je[[s]
41

---

max (max hij Tsb
8T
sup maal
h
min
X
t'
inf jEllmar
t
8Ty
8 max
{ [12, Tz
min
e'
where we use the definition of 7i. Using the last inequality and 4 2 4 mmax(h;:7:) we have
w
A
mirli
Mijel;
j=1
j=1
32w min (Teri, max (hi, ri}}
32wd² min (nr, max max(h;; Tc}}
t'
et/l
32w min (Tr,, max h4, Ti))
128wo min (Ters, max his Ta33 max Ti.
<
(t1)
where we use (53) and max h S h4- One can substitute the bounds on and (54) and obtain SERL]
5"
w min (or,, max (1. ni)) + wo min (Teri, max (h,, m.) max (hs, Tx) + o² max mhix Ti)
H. 2 128
=t²)
et
Note that 1' 2 128s (j*), thus
w min {Ti max(h;, Tib + wo? min frr max Ti max (/i, r,} 8 (x*()*)))
oa max Ti)
H
+ ej*()*)
s*(())
-1
2w min (re,,, max 77, + 4wo min (Te max (ly, 7.) max max 71) e (
20 max (14, Ti) (}*)
=0'(i") 2w min min (Te,s max(h,, ri)) + 4wo² min (Te max (ha 7h max(h; Ti.
20 max h4s Ti
()*
is left to use the definition of s s"")) (see (52)) to obtain that H 2 s" (j*) *1 =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.I, the time complexity is less or equal to x t'.
O Construction of the Lower Bound
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 s-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 s-solution. We refer to detailed explanation (Tyurin and Richtárik, Sectioss 3-6].
First, we define an oracle that emulates the process of computing stochastic gradients or the process of sending compressed vector (Tyurin and Richtárik, Section 4]:
0g.
D
R
200 X
RRd
(0,1) x RRzo x Rdd {0. (R>o x Rd (0,1)) x
point
control
imput state
output state
(1, 1);
0), 1, 8g
(11,, 1);
0), c 1, 1, / < 8: +
such that
Ot, (s0, (
(0,0,00, ((),0,0),
( {)), c 1,8 1, f 8t + T
0), c= 0.
(55)
42

---

where & ~ D. 9 is an arbitrary mapping such that R x 8 - R 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 Compression
1: Input: function(s) f E F, computation oracles (OI,... On) E O()), communication oracles (G1 ... C.) E U algorithm A ((B*, .Y. N..... N A C.O
2: 8, 2/.0 = 5; = for all i E [n]]
3: for k 0 0......0 do
4: (th+1 geti .effktl Cc.ttt, ,It) .........
th+1 2 th
5: (ot1 -9,t+s) k+l) = Optn(thtt1 ,Ith , csatt sk+s (ik
Vj iktt, 8j 2f.ttl = =8] 1ith 15+1== =0 6: Spie *+1 = Na+n (."....,," " -. sfttt);
7:
(8,441 g Ear (1 Ipee clitt1 sp4t))
8: end for
In this protocol, the server via Bh returns new point x² and broadcasts it to the 1 worker. Then, the worker calls the oracle O,t+1 that calculates stochastic gradients. Next, the oracle returns k+1 the vector 9,t+1 and the worker processes it with N Finally, the worker sends gprt* to the oracle C that sends compressed vectors the server. Using the parameters cf and cC,++1, it can decide if it wants to start/stop the process of gradient calculation and the process of communicating a compressed vector (See Sec. 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 al., 2022: Carmon et al., 2020): Definition O.1 (Function Class FA.L). We assume that function f Rd + R is differentiable, [V](x)) - ( < || yll Vz, E Rd, (L-smooth) and f(0) - infzex< f(x S A (A- bounded). The set of all functions with such properties denote by Fa.
Next, we define the class of algorithms that we analyze.
Definition 0.2 (Algorithm Class Az).. Let us consider Protocol 9. We say that the sequence of tuples of mappings A {(B*, N ] k= is vero-respecting algorithm, if
1. B Rd x x Fd + Rxo x N x N x Rd for all k 2 1, and Dd
A times
N x Rdd.
2. For all & 2 1 and and g'.....g g E Rdd gh+1 2 th where th+1 and the are defined as (1++1 ....) B* (gt) ..... ....." and (uk,...) ....)= = Bg) ................................ x
3. No. R x x RRd gd x Rd + Rdd for all 2 and for all i E [n].
times
1++
4. supp (x*) C Uن supp (g¹). and supp 1 C U supp (9¹) U supp (o(en)),
for all h E No, where supp(x): = (i E [d] I # 0)-
The set of all algorithms with this properties we define as An.
The properties and 3 are only required to define the domains of the mappings. The property ensures that these mappings are zero-respecting (Arjevani et al., 2022). The property is explained in (Tyurin and Richtárik, 2Secion 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 FA. it returns n oracles that require hy,... hn seconds to calculate a stochastic gradient. These oracles emulate the real behavior where the workers have different processing times.
43

---

Definition 0.3 (Computation Oracle Class Oh h ). Let us consider an oracle class such that, D for any f FA.L. it returns oracles O; = =h for all E [n], where [z {) is an unbiased
oe-variance-boundde mapping (see Assumption 1.3). The oracles h₁ f are defined in (55). We define such oracle class as O hi.....h..''
The following oracle class emulates the behavior of compressors. It returns oracles that require Ti...., Tn seconds to send a compressed vector to the server.
). Let consider an oracle class such that, returns oracles ć, of for all i [n], where C is an unbiased compressor with a parameter i.e. C E ((w) (see Def. 2.1). The oracles CC.P are defined in (55). We define such oracle class as U "
Definition O.4 (Communication Oracle Class Ui
Finally, we present our lower bound theorem:
Theorem 0.5. Lel us consider Protocol 9. We take any hú > 0, T;
for all i E [m], w 2 is the dimension of the Fa.L, computation oracles
>
0, A, e, o² > such that C1 and w + +1 T," where T = construction. For any algorithm A An, there exists a function
AL
oge
(O On) E O b1 hu (f), and communication oracles (C1....,
Cn) E U ".....n.
12 such that
E infREs, Vf(x*)
where S. = {k E No | S St} and
LA &
I 03
(w, o /e, (1, Th.... Nns Tn).
The quantities C1, c22 and 03 are universal constants. Protocol
The sequences xt and th are defined in
Proof of Theorem 0.5
P.1 The "Worst Case" Function
Let us consider the "worst case" function, which is a standard function to obtain lower bounds the nonconvex world. We define
prog(z) max 0 24 + 0} (xo 1).
In our proofs, we use the construction from (Carmon et al., 2020; Arjevani et al., 2022). For any T N, the authors define
Pr(x) = -1() + Σ (- (z))),
(56)
where
[0: exp (1
x S 1/2,
and ((x) = ve I" e dl.
(x)
2 1/2,
122-11²
The main property of the function (x) is that its gradients are large unless prog(z) 2 T. Lemma P.1 (Carmon et al. (2020); Arjevani et al. (2022)). The function Fr satisfies:
1. (0) inf Fx( < T where A = 12.
We avoid this constraint using slightly different construction of compressor. However, the number of non-zero returned values by the new construction random. See. P.3. The function f defined on Rº with 7' = θ (Z4/e), and the constructed compressor C' preserves only K [T/++]] non-zero coordinates.
44

---

2. The function Fr is 1-sooothh where 1 152.
3. For all x E R², [V)r( S Too: where Yoo = 23.
4. For all x: E RRT prog V (x)))) & prog (a: +1.
5. For all x E R², if prog(z) < T, then [Fr(2))| 1.
for all i E [m], w 2 is the dimension of the construction. For any algorithm A Azz there exists a function FA.L, computation oracles (O....., ,On) E O ki, (f), and communication oracles
Theorem 0.5. Let consider Protocol 9. We take any h; > 0, >
0, 0, such that < c1 L, and w + S T, where T- AL
C.) E U ",....."
14 such that
E infkes, [/(x>)]| > e, where S. = { E No | 5t and
LA t' (w, o /e,
t cs
h2, Th..... ,,,s Tu).
The quantities 61, 022 and og are universal constants. Protocol 9.
The sequences 2²th and the are defined in
Proof.
Without loss of generality, we assume that the workers are sorted by max Ti} max(h1, m S S. max ]
(Step 1: Fa.).
Let us fix À > and take the function f(x) = LA² Fr (+) where the function Fr is defined in
2,
Sec. P.I. Tyurin and Richtárik (2023c)[Sec. D.2, Proof of Thm. 6.4] show that the function f is
T-smooth and f(0) - inf iinf f(x)) < A if
A
T
LA
Thus, we have f E FA.L-
(Step 2: Oracle Class) Let us construct stochastic gradient mapping. For our lower bound, we take
[V == vzf(x)
( +
[ 1 > prog(x))
[ (E) Vo E R.T,
and D -Berooull(p) for all E [n], where E (0, 1]. We denote [æ], as the jth index of a vector
RT Let us take
_²
min
o 2
Then Tyurin and Richtárik (Sec. D.2, Proof of Thm. 6.4] show that this mapping is unbiased and o ---uariaceebbuudde.
(Step 3: Compression Operator) 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, 1-variance bounded, i.e..
we know that C is unbiased and T
K
Es [C(x; x,
Es S) <
T -1) K
|el|
Va E R²,
where
(C(;; JT. jES, 0, j jÆS,
Vj E
We avoid this constraint using slightly different construction of compressor. However, the number of non-zero returned values by the new construction random. See. P.3. "The function f defined on Rº with 7' = θ (Z4/z), and the constructed compressor C preserves only K [T/++]] non-zero coordinates.
45

---

and S an uniformly random subset of [2] without replacement. is sufficient to take K w+1 to ensure that C E (ww). Let us define P. = generate random subsets S described above.
K. 7. We take mutually independent distributions D. that
(Step Analysis of Protocol)
Let us take
V2el
to ensure that [|] L2x2 Lemma P.I. Thus
VVT (+)l > 2x1 [prog(x) < 2] for all a E R², where we use
AL 2sl1 A
(57)
and
1207 0²
min
Protocol 9 generates the sequence {x* 100 k=
We have
inf kES.
[[((=**) ||?
2E inf 1 [prog(**) < <T]. keS,
(58)
Using Lemma P.2 with 1/2 and (58), we obtain
inf kES.
[
2 2&P
inf 1 [prog(=*) <T 21 > kES,
for
T
{
a2
AT
-1)
t S
48
t"
max
12
1
h1, T1.... An, Tn
8E4,
By the assumption of the theorem, we have w - 1 < T. Therefore, we get the series of inequalities:
T
T
w
K
T
and, using Properties 6.1 and E. we have
T
σ²
max
h1, T1,.......
Kno Tn
K
200g
11
0²
8*
max
T Mas Tn
2012
1
1
σ²
8"
W,
h1s Ti...,, Tn
2-
2
x t" (w, (w,02/1 02 h1 .i.... Nn, Ta),
2x2
Thus, we can take
AL 8el, A o
-1)
1" (w, KI, An Ta)
48
2-2
P.1.1 Proof of Lemma P.2
Lemma P2. Let us fix T, T E N such that T S T', consider Protocol 9 with an algorithm A E Ans differentiable function f RT" R such that prog V f(x)) prog(x) for all domain(f).
46

---

1. We take stochastic oracles O, = 0
with the distributions D. = Bernoull(ppe)
E (0, 11, h4 > O, and the mappings
(1 (++ 1i prog(t))
-1)
- Po
[s(;; = Vz[(x)
VOER" VE (0, (T).
(59)
2. We take compression oracles C. C. with the distributions Dj = uniform K, T") (= "uniformly random subset of [T"] of the size K without replacement" and the mappings
[C(:;; ([(z
T Jij K
JES, 1
Yor EERR", SA [n)
(60)
0,
O. We define Pu == K. We assume that the workers are sorted by max hm Tm3 max(hi, m1) S ... max Ta). With probability not less than 1 - 6, the following inequality
To
holds:
inf 1 [prog( < <T] 21
kES.
for
T ( =logo)
5 t- (1/pur 1/po, h1s T1s...... has Tn)
48
where S. =- (K No 1h < <t}, the iterates th and att are defined in Protocol 9, and t is the equilibrium time from Def. 3.1.
Proof.
(Part 1): The Construction Random Variables.
Let us fix 2 0 and define the smallest index k(i) of the sequence when the progress prog(z+(()) equals :
k(i)= == inf { E No prog(=")} E No U {oo}
If infres, I [prog(=*)) < 1 < 1 holds, then exists k E S, such that prog(=*) thus, by the definition of k(1), {k(1) t t, and k(1) < co. Note that {*(1) is the smallest time when we make progress to the 1h (first) coordinate.
Since 00 0 and A is zero-respecting algorithm, the algorithm return vector x² with non-zero first coordinate only some of returned by the stochastic gradients oracles and compression oracles have the first coordinate not equal to zero. The oracles O; and ć, are constructed in such a coordinate based i.i.d. bernoulli and uniform trials.
way (see (59) and (60)) that they According to Protocol 9, even if a stochastic oracle returns non-zero coordinate, it would not mean that the server will get a non-zero coordinate because subsequent compression oracle also has to return a non-zero coordinate.
Every time when the oracle (55) evaluates g(sz: it draws i.i.d. random variables & D. Let us enumerate them:
1. For the stochasticccomputtiinn oracles O = O² D
we consider the sequence ( 3 where gmm.j is bernoulli random variable drawn in jth call of g( in the mh worker Line 5 of Protocol 9.
2. For the compression oracles é; = Of we consider the sequence {Smm. 1 gmm is uniform random variable drawn in jth call of g(s.; {) in the m worker in Line 7 Protocol
1g=1 where
Let us define the following useful random variables based on previous definitions. We define
in (e0llee..(ttt0 (i+6%% -1) = and E N) N (x)),
m.j < 00, bn 00,
Mm =
T},
00,
(61)
47

---

inf(il E sm.(ttt and i N) E ENNNN (oc), 00,
m. 00; m.j 00,
Pmd
VjE [I....,T}.
(62)
where
1. For all m E [m], 2 1, 6m. E NU [oo) is the first index of the sequence {<m=)] } that started calculating in (55) in the stochastic oracle On in or after the iteration k(j - 1).
2. For all m E [m]. 2 1, bm. E NU {oo} the first index of the sequence { } that started calculating (55) in the compression oracle Cm in or after the iteration k(j 1).
3. For all E [m], 2 1, if m.j - oo, then e cc. For all E [m],. j 2 if bm, < xo, then e E {oo} is the first index the sequence {5m that started calculating in (55) in the stochastic oracle Om in or after the iteration k 1) and the first moment when 5th gm.(ttb.) m. -1 = 1 for some i 2 1.
4. For all E [n], j 2 1, if By oo, then m co. For all m E j 2 1, 1,ifb% X2, then em.j NU {00} the first index of the sequence { j==1 that started calculating in (55) in the compression oracle C. in or after the iteration k(j 1) and the first moment when (m. -1 for some i > 1.
2 It possible that such indexes do not exist, then we take 6mm.5 00, by = 0o, Em = oo, or m oo, accordingly. By the construction, em 2 Dm and e 2 1m..5
Let us clarify the definitions. At the beginning zo O, thus k(0) = O. It would mean that the first index of the sequence ( when the worker evaluates ( E) in (55), simply equals 6h, 1 or 6%,1 = x0 (by the definition, it equals to oc if the oracle was never called). Assume that b% = 1, then 7m, = inf gm. = 1 and E N} is the first time when the oracle draws a "successful" random bernoulli trial. This random variable is distributed according the geometric distribution. Then, < can be equal to 7m,, + 1 or xc. At some (random) iteration k(1), the algorithm A can get the first non-zero coordinate through g², then 6 u is the next index of the sequence { 3 that
started calculating in (55).15 15
The server gets a non-zero coordinate at least one worker draws a successful bernoulli trial, and this coordinate belongs to set generated by the uniform distribution. It takes h2 seconds generate one bernoulli trial and T, seconds to generate one uniform trial.
Then, := infres, 1 prog(r**) < 1| < holds, then
f : min [hm7m,, + Tmpmm,) S t(1) meIn]
because Am + Tm/4mm11 is the time required to generate Mm. bernoulli and fmm11 uniform trials. In other words, the algorithm can not progress to the next coordinate before the moment when least one worker generates "successful" bernoulli and uniform trials.
Using the same reasoning, ( 2 t + Eg, where
i min Umm + Jmflm.j me [m]
Let let us consider an example with the m worker. Assume that it starts calculations of stochastic gradients and with 7m.1 = 5 (as example) it gets "successful" trial: 5" "m".mmm....1 gm (g"h.1 = em 0). And only then, starting with eftt 1 the compression oracle can get vector with non-zero coordinate. Even if there previous "successful" trial: 1 Sum,* for some i < eftt This trial did not return vector with non- zero coordinate because the stochastic oracle did not return a vector with a non-zero coordinate by that time.
Assume that e 10, then the server waits for Mm.11 inf{i 1 e gmm(ttel" -1)), Assume that fmm,1 7, then the time moment, when 1 E gmm(pm..1 +elt. 1) 1 E (7+100))))) is the first possible moment when the m worker send a vector with non-zero coordinate the server.
48

---

Combining the observations, if infRes, 1 [prog(e*) <
holds,
then
Ej minsela] (hankss + T(pls)) S ( Thus
P inf [prog(**) < T| < S P
Σ 4 st P Σ
min (hmps + TiMles) st) jeIn
14 2 0.
keS,
(Part 2): The Chernoff Method
Let us fix 8 2 0 and é 2 0. Using the Chernoff method, we have
I
Σ S
P
8
st
exp
-
> t
2 exp (-st)
(63)
T
I E
exp
$
Let bound the expected value separately. For j [T], let us define 9j as the algebaa generated by random variables
,., bnj cl.b",
2.22 11 ,8
<n. ,5 gni
1
(64)
b 1.j..... b
S4.1 S1.2
S gm.2
Sm.
The o-algebra Gr contains all information about the random variables before the moment when prog (oog(x)) T - 1. Then, we have
T
T str
E
exp
Σ 4
=
E
E
exp
8
4
GT
Note that if the random variables from (64) are "fixed," then i is deterministic for all i [T - 1] because & is a deterministic function of (64), and does not depend on other subsequent random variables.
Let us show using a contradiction proof. Without the loss of generality, assume that - depends on g! 1. & (64). By the definition of b",r. it would mean that the first time when the server can get a vector g² with a non-zero coordinate the index - is after the moment (k)T-1), We get contradiction since + 1) is the first time when the algorithm return an iterate with a non-zero
coordinate in the index T 1.
Thus, & is meaaurrabee for all E [T and
E
exp
E exp
E exp (-stT)
(65)
Let us fix 1' 2 0, then, since i 2 0, we have
e str
Gr
E Φ i < 1l Cr
PP (ir < (((gT)
E :F(e-sto
ir > 1 (1 - P (lr S (((g))
< P (tr t' Gr) +e at' (1 P (or t' Gr))
(66)
We now use the result of the following lemma that we prove separately.
49

---

Lemma P.3. Using the notations from the proof of Lemma P.2, we have
P( (t 2
II
1 - (1 pw)l ) (1- po)
(1-(1-po)(mm) (mm))
(67)
m==1
for all j [T].
Let us temporarily define
p=) 1 ) (1-(1-po) (--1-(1-p))
p' =
1 - 1
m=1
We substitute (67) to (66) and (65) to obtain
S pp' + te st' (1 (1-p') E exp -s Σ 1/ ) (f (1-1))
E
exp
4
Next, using (63), we get
P
Σ i s S at (1 (1-)'))²
(1
sf (1 (cth
Let us take 8 = 3/4, and get
P
Σ 4 si
S eel (1 (e- 1)b1 s -I''-
(68)
Let us recall the definition p':
(1-(1-C) (1 p ) (1 (1 (1----) (1-(1-p))lmm) nm))ltu)))
- II
II (1 gm) m2
=
m=
(1- (1- pw) [tmil) 1
(1- (1 pa) pr)](mn) km
where we define Qm ==
E [0, 1]. Using Lemma C.I,
we have
p' <
4m
m=1
Using the inequality 16 1 (1 - p) < pm for all E [0, 1] and m E No, we can get the following three inequalities:
t'
pm - 1 11-11- Po)
Po
hm
4m < 1 - (1 - S Pw
1'
Tm
and
Jm 1 (1 (1-(1-p))(t)) ) (I-(1- (1-(1-po)) (1-1p)) -p) < Pw
t'
t
Po
Tm
hm
Therefore, get
:'
t
t'
Om < min
Dr
hm
Pa
Tm
Po
Tin
We implicitly assume that 1 (1 - p)
0
and O. See footnote 17 for the details.
50

---

and
t'
t'
min
Po
Pw
PwPo
(69)
1mm
Atm
m=11
Now, we have take the right t'. Assume that s" s²( is the solution of
2mm Σ
(70)
+
1rm Amm
+
24mm
m=
and
== E [n] 50 (J) (han [m]
(, = 00.
Then we take 24 (j*) j 1, then
1
2r1 hn (r*) + 2h1
2r1 + 2h1
2T 2/11
PePas
Otherwise, if jr 1, since 8² (² S (j
1), we have
5
2mm
4 4rmhm + p.
2hm Po
Pur
+
2mm Pu
PuPa " (i" +
2hm
27,
+
2h
m=
Dw
Po
-1
2Tm
P.P. 0"" +
4 Am
2bm
max( Tz-
Pw
Po
By the definitions of s* (f" 1) and j have
5" -1) 2 max(h
2 4r Bm Pu
2km
m=1
P.P.s (5 -1
Po
Therefore, get
-1 (S)) max(hy-. Tz- max(hy-,Ty-)
max max(h J
Using s s²()") 2 max Ty. }. we obtain
=' 24
max
2 max Ty- ). s,"),,(("))) 48 jE(m
min max/max(hh... Ty), s()))
(71)
We use the last incquality later. Let us return the inequality (69). Using the definition of j*,
obtain
1'
or
0 for all > j and
Tm
t'
p'
min
Po
Pwi
PwoPo
lim
N
m=1
5*
t'
t'
t
Σ
min
Po
Pes
PwPo
hmm
Tm
Tm
hm
Dott'
part'
Pwpott?
min
hm
Tin
Tinban
51

---

where we use [x] have
I for all æ 2 0. Using max v, 2 (a + + for all v, 2 0, we
hm pott
Tmn Putt DuPot
p'
max
Im
Tem Pum
Am. paf
m=1
m=1
put
Pupa
Since t' 24 8 (j"), we obtain
3
p' 5
24 m= P))
24h
25m m=1 Pu*"()")
+
4T R PuPo (s (5-)) Pa*
2h
PuPe (f-)
Past (5*)
Note that s" si()) is the solution of (70), thus, we get
Substituting this inequality to (68), we obtain
T
f
3
1/1---7
i=
For 8 5 1' 2 log o), have
P
Σ
1 s
58.
Recall that the definition of t'. Using (71), have
t' 2' min max (hj, 8 {1)).
48 jEIn]
The last term equals to the equilibrium time 1" (3/p-s 1/p., b1, -1.-.. Nu: Tn) from Def. 3.1 since the pairs (hjs are sorted by max h Ty}. Thus, we obtain
t' N (1/m/on 1/p., his The Nn)T.)
48
Finally, we obtain
T
IP inf [prog(=*) <<] <1 S
Σ
1 S
(72)
kes.
1=1
for
S 1 (V/P// 1/a, Ti, h,. Tn)
( + log
48
P.2 Proof of Lemma P.3
Lemma P.3. Using the notations from the proof of Lemma P.2, we have
(1
1 (1 pb) fmm 1) (1-(1-Pa)) poo (m))
(1, (() < II
(67)
m=1
for all E
Proof. We prove the result for T.. The proofs for the cases < j < T are the same. We consider the conditional probability
P (fr s (T) = min {Am + T TmHmm.T s (T)
mE
52

---

Let us consider the o-algebra Hr generated by (64) with j = T and
</ RT cl,,,
,
11 :...,
("1 ,5
gmi ..... , chee2
(73)
....... T
, s12
S s1
Sm.1 Sm.
By the construction, 6n, 2 m
and em 2 M Since Gr S Hr, we have
PP (fr S 1' 9r) E P
min (hmMm,r + Fmffm,) S Hr) Hr me/n]
gr
Since Gr S Hr, then bh,T is mrammasur.ble. By the definition of e 1m,7 are Hy-mmasurable.. Let us show using a contradiction proof. Without the loss of generality, assume that 7 depends on gl.om.r & (73). It would mean that the first time, when g. after the iteration k(T 1), happens with 2 e",,T At the same time, by the definition of e there exists < em.r such that gm. = 1 calculated after the iteration k(T - 1). We get a contradiction. Given Hr, Pm,T are mutually independent since {Smm.) are mutually independent and e are Hy-measurable Therefore, we have
==
P (l, S (() = E P
min (kmmmm + TmHm,, S l' Hr mc(n)
GT
1 E
P
(hamer + Tmpmm t'} Hr Gr
(74)
m==1
1 - E
IP (mmmma T + T ((Hl)) GT
Let us consider the probability P Phhm + Tm Tm > ((H)):
P P T t'(HT)
P (hm T + TmmMm, $ t H())
2 1 P (MmmlmmT S L', TmHm,,T S l' (T))
1 E [hm S (') [TmMm,T S t']l Hr]
because the event (hm S [m][(mm Tm is tecamuaure,le,, we have
S t'} follows from [hm TmummT S t). Since
PP (h + TmHlm,T ('(HT) 2 1 - [[ [TmHm, S E'] HT] [Am TM, S St)
(75)
(TmHMm,T {(()r [hm S 17..
Let us consider the probability P (TmJkm,T S ((()T)) Given Hr, if c oc, then Mm, co and P (TmJAm,T S ('(Hr) = 0. Otherwise, if e = 00, then
Pm, inf (i+e 1) and i N).
and it is distributed with the geometric distribution with pa. Thus, we have
P (TmHHm.TT < {((())) = ( - pw)) +m e s (1 pu) |
0,
m = 00
We implicitly assume that 1 - (1 - p.) 0f and 0, because if t' < Tm, then
P (Tm Mm, $ t') = 0 for the pm.r from the geometric distribution for all pa E (0, 1].
53

---

because the probability that 5th coordinate belongs to 5th.(ite-1) equals to Pa. We substitute this inequality (75) and get
P Tm. + TmpMm {(1H))) 2 (1 (1- pw) +
1 Mm S t7
Next, we substitute this inequality to (74) and obtain
P (tr (T) 51- II
(1-
Umm s(1) 1
GT
Given GT, T are independent because 6,,T
r are meassurrall.. Thus
P (tr S (T) <1
II
1
E [ [mm S st'19 1 1- (1 pw) mm
II
1 -
P (hmHma.T S <(IST) 1 - pw) (m)l
m=1
Using the same reasoning as with /mm,1' we get
(1 1 po) mmm
8 m.
S 11--1 - -pp) [ 1
PhhmmlmT & (T)
0,
because, given Gr, Tm.T equals oo or a random variable distributed according to the geometric distribution with Po. Therefore, we obtain
n
1 (1 pw) ( pu)l
(I-(1 po) (1-((p)))))))
(fr S GT) < II
P.3 Another Construction
In the proof of Theorem 0.5, we could use the following construction:
(Step 3: Compression Operator) Let us define Pw := w+11 In our construction, we take compressor that outputs random coordinates of input vector, scaled by 1/p., where each coordinate is taken with the probability Pw. Each worker has access to the independent compressed realizations of a such compressor. More formally, we assume that
1 oj
je S, Vje
S]I; =
0,
i j&S.
where a random subset of [T], where each element from [7] appears with the probability pa independently. Then
Es ([(=;))]]] 23
and
Es [IC(=;)))]] =Es
Es
Σ
aijest S
2
=EP P(jE S)
2
Σ
2 (w
+ 11 ?
p
p2
J=1
Pw
Thus, have C E U(w). We take mutually independent distributions Df that generate random subsets described above.
This construction is also valid and does not require the assumption w 1 LA/S. However, unlike the construction from Theorem O.5, this construction can return random number of non-zero coordinates.
54

---

Experiments
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.
Q.1 Experiments with Logistic Regression
4x
AgyeE DISS SURE SND 06IE65
520 dig dis 85345
Mivsene 068 300 AD6
CSCD 3.25
widdut 920 Map
3x
30-4
20-1
20
10070
20:05 (seconds)
30303
200300 300000 a00000 503020 700020 200000 times (seconds)
(a) Experiment with computation speeds h, vi and high communications speeds à Vi/d
(b) Experiment with computation speeds h4 vi and low communications speeds f, vi/d
34x
FAY thowoer SID See dec 0005S5
32x10
M-staro Side 290
10th Seasine dhe
28-
20
24x 10-
200000
times (seconds)
(c) Experiment with computation speeds h, Vi and medium communications speeds +, vi/83/4
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 fix the number workers to n = 100, each worker has access to the MNIST dataset and sample 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 SGD SGDone the method described in Sec. 7, where SGD is run on the fastest worker locally. In Shadowheart SGD, we fine-tune the parameter / E 51,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 Rand with K = 700.
We assume that the computations time h; of stochastic gradient equals Vi seconds in the th worker. We consider three communication time setups, where it takes i seconds to send one coordinate from the tth worker to the server and
1. +. Vi/d (High-speed communications),
Vi/d3/4 (Medium-speed communications),
3. + = Vi/dt/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 not expensive to send non-compressed vector in the "high-speed communications" regime. SGDone is the slowest since it utilizes only one worker.
55

---

Next, we analyze Figure 1b, where Shadowheart SGD and SGD have the best performance. SGD improves the convergence relative to other methods because the communication speed much slower than in Figure la, and it is expensive to send non-compressed vector.
One see that Shadowheart SGD is very robust to all regimes and has of the best convergence rates in all experiments. Notably, in the "medium-speed communications" regime, where it is still expensive send non-compressed vector, our new method converges faster than other baseline methods.
Q.2 Experiments with quadratic optimization tasks and multiplicative noise
In 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 consider
f(x)
2 x Ar - bxx
for all x E Rd and take d = 1000,
2
-1
0
A
1
-1
Radd and
1 b
RR...
4
:
-1
0
0
2
We consider the following stochastic gradients:
( p (1)) Va E Rdd
[f(x;))); vzf(a) 1 1 1 prog(z)]
(76)
where E Bemnouli(p) for all i E [n]] and p E (0, 1]. We denote [æl, as the jth index of vector x E Rdd In our experiments, we take the starting point x² = [vd,0, o,.......) 0] and p E {10-3, 3, 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 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, SGDonn 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.
Q.2.2 Plots
In these experiments, we take n 10000, p 10-3 Vi, t4 vi/d as base parameters; in each plot, we vary one parameter.
10-3
10-2
(Rx))
10.1
10"1
30003
1000 times (seconds)
15000
200000
2300000
300000
5000
1000
250000 times (seconds)
15000
200000
300000
(a) n = 10000, p-00, h
Vi,
+
(b) n = 10000, p=000,p=1000 10 h Vi
Vi/d2/4
Figure 2: SGD starts to slow down relative to Shadowheart SGD and other methods when we increase the noise.
56

---

MONOOMEE VO THE REINIING
10
(bx)
250005
300000
times (seconds)
times (seconds)
(a) 10000, p 10 h.
Vi, A
Vi/d
(b) 10000,
10 h. Vi
vi/d
Figure 3: The non-compressed methods Asynchronous SGD and Minibatch SGD slow down relative to Shadowheart SGD when we increase the communication times.
10-1
10a0
20000
100000
150000
200000
250000
300000
50000
100000
150000 (seconds)
200000
250000
300000
times (seconds)
(a) n 10000, p=
Vi, vT/a'/4
(b) n
10000,
10 1, 1, Vi/d2/4
Figure 4: Shadowheart SGD improves when we decrease the computation times from Vē 1.
Q.3 Experiments with quadratic optimization tasks and additive noise
In this section, we consider the same problem in Sec. Q.2. However, unlike the multiplicative noise, we consider the following additive noise:
Vs (1,
Vo E Rdd
where ( ~~ (0, o²) is sample from the normal distribution. Be default, we take n = 100 workers, the dimension d = 100, and use the Randl compressor (w d/1 - = 99), xo [1, -.. _]T,,
10-1 10-4; thus, the ratio "e 102. For all methods, we choose the step sizes in such way that they converge to the same neighborhood of the stationary point.
In Figure 5, we sample hy and tf from the uniform distribution U (0.1,, 1), hence the communication and computation time vary on each iteration for each client. If we increase the number of clients n, Shadowheart SGD improves (Fig. 5) compared other methods, confirming
theory.
In Figure 6, we can see the similar results with different ratios o²/c: Shadowheart SGD much better when the ratio is large (Fig. 6). On the other hand, when o is small (Fig. 6a) SGD can be better because, intuitively, we only need a few workers to find the minimum with a small noise (see also Sec. 7).
Next, we perform series experiments with different computation time and communication times ratios. We take +//nt for all i [r)], where >> O.
In Figure 7, we take h.-h U (0.1, 1) and t ~ c (O.11, 1). Shadowheart SGD better in the high and medium communication speed regimes (Fig. 7b), when the communication times are not too large. On the other hand, with large e = 10², Shadowheart SGD spends much time on sending gradients to the server, whereas SGDone does not spend time on communication and does not compress (Fig. 7c). Similar to Figure 7, obtain the results with h Vi and J. c Vi in Figure 8.
57

---

Q.3.1 Plots
20
20
20
10"0
20-1
1200
2002
3200
4000
3000
1320
2002
3200
4038
3000
1320
2002
3200
4030
1000
Time."
Time,
Time,
(a) 12 = 10
(b) n7 = 10
(c) m = 10
Figure 5: 11 4/ ~ (0011,1)
10"
20"
12-4
10-1
10-2
503
1000
1002
2002
2510
3000
1000 1500
2002
2300
3000
Time.
Timee
Time.
(a)
1
(b) 00/= 10
(c) / 10
Figure 6: 1 ~ 1(01,11)
10"
20"5
-0-
30
36
260
1000
10
(c) c 10
Figure 7: h3 ~ =c
Randroncc
fondrinc OS0
30-
107
1350
2008
3000
c050
5000
1850
2005
3500
5000
1860
2005
3000
5000
Time,
(a) c 10
(b) c = 11
(c)
Figure 8: 12 = Vi, = =c.
58

---

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

---

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

---

reproducible, they Answer: [Yes]
Justification: In the supplementary material
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. cc/
wwwssssoollloooooooooooooooilloo oolicyy for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: / //nips.co. wttpccccppcpccpeeeceeeecccccceee httpppppluiidss////ppppppppapaal Caaeee//ooeeummiiee swwiissssssoiiiiiee
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Section Q
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: While each particular experiment in every plot from Section Q was run with one seed, the amount of provided experiments and considered settings can give high confidence in our judgments that the experimental part supports the theoretical part, which is our main contribution.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by emror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
61

---

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.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Section Q
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well 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 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: http://p...cccllcccc/ccccooeeeee
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 to preserve anonymity (e.g.. if there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our work considers 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.
62

---

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

---

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


Reviews:
[{"review_id": "hk1izASy8Y", "reviewer": "Reviewer_zjmf", "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.", "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?\n2. 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": "Yes", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. **Novel Method**: The introduction of Shadowheart SGD guarantees finding an $\\varepsilon$-stationary point with optimal time complexity in heterogeneous environments.\n2. **Theoretical Contributions**: The paper provides rigorous proofs showing that Shadowheart SGD has better or equal time complexity compared to existing centralized methods.\n3. **Optimal Time Complexity**: The time complexity analysis shows that Shadowheart SGD can be significantly better than previous methods in many regimes.", "weaknesses": "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.\n2. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the positive review! Let us address the weaknesses and questions:\n\n > 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.\n\nUnfortunately, with the equilibrium time, we have a situation like the math community has, for instance, with the Gamma function, which also does not have an explicit formula, but it does not make the Gamma function less useful. We devoted the whole Section 6 explaining the idea behind the equilibrium time. Note that in Section 6.1, we describe an algorithm for finding the equilibrium time numerically.\n\n> Can the process of calculating equilibrium time be simplified or made more intuitive? Are there any practical algorithms or tools recommended for this calculation?\n\nYes, we describe an algorithm in Section 6.1. \n\n> 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.\n\n> 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?\n\nIt is easy to show that Shadowheart SGD requires the number of training samples less than Rennala SGD and Asynchronous SGD. All these three algorithms utilize the computation resources almost all the time during optimization processes, meaning that they use \n$$\\approx \\sum_{i=1}^n \\lfloor\\frac{t}{h_i}\\rfloor$$\ntraining samples by a time $t.$ Since the time complexity $t_{\\textnormal{shadowheart}}$ of Shadowheart SGD is smaller than in other methods, we can conclude that\n$$\\sum_{i=1}^n \\lfloor\\frac{t_{\\textnormal{shadowheart}}}{h_i}\\rfloor < \\sum_{i=1}^n \\lfloor\\frac{t_{\\textnormal{rennala}}}{h_i}\\rfloor$$\nand \n$$\\sum_{i=1}^n \\lfloor\\frac{t_{\\textnormal{shadowheart}}}{h_i}\\rfloor < \\sum_{i=1}^n \\lfloor\\frac{t_{\\textnormal{asynchronous}}}{h_i}\\rfloor.$$ Therefore, Shadowheart SGD uses less training samples to find an $\\varepsilon$--stationary point.\n\nComparing to Minibatch SGD, which requires $\\frac{n L \\Delta}{\\varepsilon} + \\frac{\\sigma^2 L \\Delta}{\\varepsilon^2}$ training data to find an $\\varepsilon$--stationary point, our method indeed can *calculate* more stochastic gradients because $b_i = \\lfloor \\frac{t^*}{h_i} \\rfloor$ can be large if $h_i$ is small. However, Minibatch SGD provably requires more time to solve the problem since some workers are idle during the optimization processes (see Lines 55-56 and Table 1). Notice that we work with i.i.d. stochastic gradients, and nothing stops us from reusing previously used training samples. For instance, we can organize a stochastic gradient calculation in a way that workers calculate $\\nabla f(x;\\xi),$ where $\\xi$ is a uniformly random sample *with replacement*. \n\nWhat if we can not reuse samples? When we were writing the paper, we tried to use all workers' time and utilize them as much as we could to improve the performance. That is why we take $b_i = \\lfloor \\frac{t^*}{h_i} \\rfloor.$ But if we want to limit the number of samples that Shadowheart SGD uses, then we can slightly modify this algorithm and take $b_i = \\min \\left[\\lfloor \\frac{t^*}{h_i} \\rfloor, b_{\\max}\\right],$ where $b_{\\max}$ is some parameter that bounds the number of used samples.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "90ukkTvuau", "reviewer": "Reviewer_Ptpi", "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.", "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. \n\n2. 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": "Nothing big, but please see my comments above in the weaknesses.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well written, and a reader not familiar with the literature gets to a very good understanding of the current literature in the area after reading the first few sections of the paper. The results are also presented in a transparent, easy to understand, and mathematically sound manner. The studied problem is a fundamental problem in distributed optimization, and underlies several more complicated seeming problems in Federated learning. The authors attempt at showing optimality of their procedure at least for RandK also provides context on any scope for improvement in the current result. Finally, the authors consider several important extreme limits as well as baselines, making clear comparisons with them. Overall, it is a good paper with only some flaws that can be corrected using remarks and small additional comments, that can be accommodated in the camera ready version. \n\nI support accepting the paper, and am happy to further increase my score based on author rebuttal and discussion.", "weaknesses": "I have the following comments in a decreasing order of importance:\n\n1. 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. \n\n2. 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. \n\n3. The authors should comment on when (12) is a reasonable approximation, even if the calculations are not exact. \n\n4. 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\",", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your very positive comments! We now respond to weaknesses: \n\n> 1. I am not sure if the lower bound actually holds for all unbiased compression schemes. \n\nIn the lower bound (Theorem O.5), we chose the particular compressor, Rand$K.$ Thus, indeed, our lower bound works only with one compressor. We do not hide this since we state in Theorem O.5, saying, \"there exists ... communication oracles,\" which indicates that the theorem works with fixed compressors. We also admit this in Line 205 of the main part. We will add this detail more explicitly. \n\nWe want to note that choosing one particular bad compressor (RandK compressor in this case) is the same as choosing one particular bad function, which is the standard approach in the literature. For instance, Yurii Nesterov, in his celebrated book [1] (like many other works), chooses one particular bad function (special quadratic function) to show the lower bounds. As far as we know, nobody showed that the lower bounds from [1] work for *any* function (because it is a very difficult task, and possibly it is not true). Proving the lower bound for any compressor can be also very difficult and even impossible.\n\n> 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. \n\n> 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.\n\nLet us clarify this weakness and question. The parameter $\\tau_i$ is # of seconds required to send a compressed vector $C(x)$ to the server (e.g., Line 20). For simplicity, let us consider the Rand$K$ compressor. Then $\\tau_i$ is # of seconds required to send $K$ non-zero coordinates of the vector $x.$ Now assume that the communication is proportional to the number of coordinates/bits that a worker sends, i.e., it takes \n$\\dot{\\tau}_i$ seconds is to send a **one coordinate/bit** (see Section 7). Then, clearly, we have\n$$\\tau_i = K \\times \\dot{\\tau}_i,$$ and, indeed, $\\tau_i$ is a function of $K!$ Hence, $\\tau_i$ is proportional to the number of coordinates/bits that a worker sends in one compressed message, which we believe is in line with the expectations of the reviewer. We discuss this in Section 7 for Rand$1$ in detail when comparing the methods. In general, we do not specify the exact dependencies between communication times $\\tau_i$ and the number of bits/information that a compressor sends. While it is clear for RandK, for all possible compressors the dependence can be very nontrivial, so we decided to abstract from this away. The optimal time complexity ((10) from the paper) captures bits communication using the times $\\tau_i.$ We agree that this should be noted and clarified in the main part, thank you!\n\nP.S. We also asked ourselves what would be the optimal choice of $K$ in Rand$K$ to get the best possible time complexity. It turns out an optimal choice is $K = 1$ (up to a constant factor). See Property 6.2.\n\n> 3. The authors should comment on when...\n\nThis $\\approx$ is tight up to a constant because \n$$\\frac{1}{2 x} \\leq \\frac{1}{x + y} \\leq \\frac{1}{x}$$ if $x \\geq y,$\nand \n$$\\frac{1}{2 y} \\leq \\frac{1}{x + y} \\leq \\frac{1}{y}$$ if $y \\geq x.$\n\n> 4. Small typos\n\nThank you for your attention. We will fix them.\n\n> 1. Do the authors have thoughts on statistical heterogeneity can be considered in this setting? \n\nThis is a good future research direction that we indeed consider right now. But in this paper, we decided to focus on this setting due to the current non-trivial and non-obvious results (e.g. the equilibrium time) that we believe deserve a separate paper.\n\n[1]: Nesterov, Yurii, Lectures on convex optimization, 2018", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "SIhepzDT59", "reviewer": "Reviewer_VesE", "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.", "questions": "See question on equilibrium time above.", "limitations": "The paper is mostly theoretical and does not have negative societal impact.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The main strength is the development of an optimal method.\n\nThe paper contribution is outlined and clearly presented.\n\nThe proposed method is compared to others in several regimes of communication delays, showing how Shadowheart SGD can outperform its counterparts.", "weaknesses": "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].\n\nAlso citation of MARINA on line 76, page 3 is missing.\n\n[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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for the review! Let us clarify the weaknesses and questions:\n\n> Personally, I did not understand the discussion of equilibrium time well. I understand that it comes from the analysis; also the examples are illustrative. \n\nIndeed, the equilibrium time, in some sense, is a \"mixing time,\" a time when the server can aggregate enough information from stochastic vectors to confidently do the optimization step since randomness is stabilized by that time. We believe one of the best possible intuitive explanations of the equilibrium time is presented in Lines 130-138. The larger time $t,$ the larger $b_i$ and $m_i.$ Due to the law of large numbers, $g^k$ tends to exact gradient $\\nabla f(x^k)$ when $t \\to \\infty.$ The equilibrium time $t^*$, in some sense, says when $g^k$ is close enough to $\\nabla f(x^k)$, and the server can confidently do the next optimization step.\n\n> Also citation of MARINA on line 76, page 3 is missing.\n\nWe will add the relevant citation. Thank you.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "KBP2JH0uzN", "reviewer": "Reviewer_U2d9", "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.", "questions": "1. In page 3, why $D_v$ is a distribution on $\\mathbb{S}_{\\xi}$?", "limitations": "The paper only focuses on the IID dataset.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The paper considered a general scenario of distributed/federated learning by considering asynchronous SGD, arbitrary computation and communication time, and unbiased compression. \n\n2. The paper proposed a new and non-trivial algorithm called Shadowheart SGD, which is optimal in terms of time complexity. \n\n3. The paper introduced equilibrium time, which is a key parameter to characterize the number of computations and communications in Shadowheart SGD. \n\n4. The the paper also proposed Adaptive Showheart SGD, which does not require the knowledge of equilibrium time, the communication and the computation times.", "weaknesses": "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. \n\n2. 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. \n\n3. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the comments! Let us respond to the weaknesses:\n\n> 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.\n\nWe are sorry if some parts of the paper are not clear. We will be happy to clarify the results. Note that we have an extensive list of notations in Section B. The intuitive explanations of our algorithm, the lower bound, and the equilibrium time are presented in Sections 4, 5, and 6.\n\n> 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.\n\nThis is true, we do not hide this (Lines 33-34). However, in this paper, we chose to focus on this homogeneous setting due to the significant and unexpected results it yields, such as the equilibrium time. We believe that we developed enough new results for one paper. Of course, the non-IID setup is equally important, and we are currently considering it, but it will require a separate project.\n\n> 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.\n\nNotice that our experiments are deliberately and scrupulously designed to capture the dependencies from the theory. We have many plots with different input parameters to understand the behaviors of algorithms. But in order to run controlled experiments, we have to exclude all external noise and parameters that more complex losses and models introduce. That is why we choose standard optimization problems that have fewer hyperparameters and uncertainties.\n\n> In page 3, why\n\nThere is a typo. Thank you, we will fix it!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: 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.
Decision: Accept (poster)