Improving the Worst-Case Bidirectional Communication Complexity for Nonconvex Distributed Optimization under Function Similarity
Authors: Kaja Gruntkowska
Alexander Tyurin
Peter Richtárik
Venue: NeurIPS 2024 spotlight (2024)
Keywords: Nonconvex Optimization
Distributed Optimization
Federated Learning
Compressed Communication
Primary area: optimization

Abstract: Effective communication between the server and workers plays a key role in distributed optimization. In this paper, we focus on optimizing communication, uncovering inefficiencies in prevalent downlink compression approaches. Considering first the pure setup where the uplink communication costs are negligible, we introduce MARINA-P, a novel method for downlink compression, employing a collection of correlated compressors. Theoretical analysis demonstrates that MARINA-P with permutation compressors can achieve a server-to-worker communication complexity improving with the number of workers, thus being provably superior to existing algorithms. We further show that MARINA-P can serve as a starting point for extensions such as methods supporting bidirectional compression: we introduce M3, a method combining MARINA-P with uplink compression and a momentum step, achieving bidirectional compression with provable improvements in total communication complexity as the number of workers increases. Theoretical findings align closely with empirical experiments, underscoring the efficiency of the proposed algorithms.

Improving the Worst-Case Bidirectional Communication Complexity for Nonconvex Distributed Optimization under Function Similarity
Kaja Gruntkowska
Alexander Tyurin KAUST; AIRI; Skoltech!
Peter Richtárik KAUST
KAUST*
Abstract
Effective communication between the server and workers plays a key role distributed optimization. In this paper, focus optimizing communication, uncovering inefficiencies in prevalent downlink compression approaches. Con- sidering first the pure setup where the uplink communication costs negligible, we introduce MARINA-P, a novel method for downlink compression, employing collection of correlated compressors. Theoretical analysis demonstrates that MARINA-P with permutation compressors can achieve a server-to-worker commu- nication complexity improving with the number of workers, thus being provably superior to existing algorithms. We further show that MARINA-P can serve as a starting point for extensions such as methods supporting bidirectional compression: we introduce M3, a method combining MARINA-P with uplink compression and a momentum step, achieving bidirectional compression with provable improvements in total communication complexity as the number of workers increases. Theoretical findings align closely with empirical experiments, underscoring the efficiency of the proposed algorithms.
Introduction
In federated learning (McMahan et al., 2017; Konečný et al., 2016) and large-scale machine learning (Ramesh et al., 2021; OpenAI, 2023), a typical environment consists of multiple devices work- ing together train model. Facilitating this collaborative process requires the transmission of substantial information (e.g., gradients, current model) between these devices. In the centralized framework, communication takes place via a server. As result, practical challenges arise due to the large size of machine learning models and network speed limitations, potentially creating communication bottleneck (Kairouz et al., 2021; Wang al., 2023a). One possible strategy to reduce this communication burden is to use lossy compression (Seide et al., 2014; Alistarh et al., 2017). Our paper focuses on this research direction.
We consider the following nonconvex distributed optimization task:
= f(()
min aERd
where E Rdd is the vector of parameters of the model, is the number of workers and Rd R. E [n] == (1..... n are smooth nonconvex functions. We investigate the scenario where the functions fi stored on distinct workers, each directly connected to the server via some
* Kiig Ahdullah University of Science and Technology, Thuwal, Saudi Arabia
1 AIRL, Moscow, Russia
"kookkovo Institute of Science and Technology, Moscow, Russia
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

communication port (Kairouz et al., 2021). At present, we operate under the following generic assumptions:
Assumption 1.1. The function is L-smooth, i.., [V) - vf(w) S L || yll Vz, y R
Assumption 1.2. There exists f I such that f(z f Vx R
In the nonconvex world, goal is to find (possibly) random point & such that /|I[S(()) <e. We refer to such a point an e-stationary point.
1.1 Related Work
Before we discuss more advanced optimization methods, let us consider the simplest baseline: the gradient descent (GD) (Lan, 2020), which iteratively performs updates x²+1 x² > >V((=') =
x' 5--7% 7/n Ei= - fz')). In the distributed setting, the method can be implemented as follows: each worker calculates V fz(' and sends to the server where the gradients are aggregated, after which the server takes the step and broadcasts xf+1 back to the workers. With step size Y 1/2, GD finds an s-stationary point after O (/)))) steps, where 8 := f(x") f for a starting point 2 Since at each step the workers and the server send ((d) coordinates/bits. the worker-to-server (w2s, uplink) and server-to-worker (s2w, downlink) communication costs are
db
(2)
Definition 1.3. The worker-to-server (w2s) and server-to-worker (s2w) communication complexities of method are the expected number of coordinates/floats that a worker sends to the server and that the server sends to worker, respectively, to find c-solution. The total communicution complexity is the sum of these complexities.
Unbiased compressors. In this work, to perform lossy compression, we employ mappings from the following family:
Definition 1.4. A stochastic mapping C Rdd - Rdd is unbiased compressor if there exists such that
[[[(x)] = x, [[((a) - x IP] s w ||]|| Va E ERd
We denote the family of such mappings by U(w). A canonical example is the RandK U(4/K 1) sparsifier, which preserves K random coordinates of a vector scaled by d/K (Beznosikov et al., 2020). More examples can be found in Wangni et al. (2018); Beznosikov al. (2020); Szlendak al. (2021); Horváth et al. (2022). A larger family of compressors, called biased compressors, also exists (see Section B). In this paper, we implicitly assume that compressors are mutually independent across iterations of algorithms.
Worker-to-server compression scales with Many previous works ignore the s2w communication costs and focus solely on w2s compression, assuming that broadcasting is free. For nonconvex objective functions, the current tfate-of-the- of-the-arrr art w2s communication complexities achieved by the MARINA and DASHA methods (Gorbunov et al., 2021; Szlendak et al., 2021; Tyurin and Richtárik, 2023b). Here, additional assumptions are needed:
Assumption 1.5. The function fi is s--moh.h. We define 7.2 = A E I? and Lmnax = max4e(1] Li-
Assumption 1.6. For all C e U(w), all calls of C are mutually independent.*
Under Assumptions 1.1, 1.2, 1.5, 1.6, and considering the RandK compressor with K < d//n /n as an example, the w2s communication complexity of both methods
80 (T+ vn - (z))
O
2 i
(4)
Vne
of sent coord.
# of
'This assumptions means that if an algorithm calls a compressor C. at some points 2t, Tma then ((zr)....,C(1) are i..dd

---

where we use the facts that L S L and w = d/K for RandK. The key observation is that that (4) be vn times smaller if L L. Consequently,
when comparing (2) and (4), the communication complexity MARINA/DASHA scales with the number of workers n, and can provably improve the worker-to-server communication complexity O (d8" (/2) achieved by GD.
eerver-to-worke compression does not scale with y., In certain applications, the significance of s2w communication cannot be ignored. In 4G LTE and 5G networks, w2s and s2w communication speeds can be almost the same (Huang et al., 2012) or differ by at most a factor of 10 (Narayaman et al., 2021). Although important, this issue is often overlooked and that is why it is the s2w communication that this work places a central emphasis on.
There exist many papers using communication compression techniques to reduce the s2w communi- cation (Zheng et al., 2019; Liu et al., 2020; Philippenko and Dieuleveut, 2021; Fatkhullin et al., 2021; Gruntkowska et al., 2023; Tyurin and Richtárik, 2023a). However, to the best of our knowledge, under Assumptions 1.1, 1.2, 1.5, and 1.6, the worst case, all previous theoretical s2w communication guarantees are greater or equal to (2). As example, let us consider the result from Gruntkowska et al. [Thorrm E.3]. If the server employs operators from U(w) and we ignore w2s compres- sion, the method from Gruntkowska al. (2023) converges O ([w+1)66 1/2) iterations. Thus, with RandK, the s2w communication complexity is O (K (w+1)6" L/s) - O 1/s). Another method, called CORE, proposed by Yue et al. (2023), achieves s2w and w2s communication complexities equal to O (/)f)) where rf( is a uniform upper bound of the trace of the Hessian. When ri (f) I dT, CORE can improve on GD. However, this complexity does not scale with n and requires an additional assumption about the Hessian of f.
2 Contributions
In our work, we aim investigate whether the server-to-worker and total communication complexities (2) of the vanilla GD method can be improved. We make the following contributions:
1. We start by proving the impossibility of devising a method where the server communi- cates with the workers using unbiased compressors U(w) (or biased compressors from Section B) and achieves an iteration rate faster than (1=+1)28%/+) (Theorem 3.1) under Assumptions 1.1, 1.2 and 1.6. This result provides a lower bound for any method that applies such compressors to vectors sent from the server to the workers every iteration. Moreover, we prove more general iteration lower bound of Ω ((++1) /c) for all methods where the server zeroes out a coordinate with probability 1/(++1 (see Remark 3.2).
2. In view of this result, it is clear that an extra assumption is needed to break the lower bound Q (1w+1)ld//). In response, we introduce novel assumption termed "Functional (LA, LB) Inequality" (see Assumption 4.2). We prove that this assumption is relatively weak and holds, for instance, under the local smoothness of the functions fo (see Assumption 1.5).
We develop new method for downlink compression, MARINA-P, and show that under our new assumption, along with Assumptions 1.1 1.2, and 1.6, it can achieve the iteration rate of
8 (w++1) L'L((+)) O
Vne
(see Theorem D.I with p = 1/(w+1) Lemma A.5). Notably, when La is small and n > 1, this complexity is provably superior to ( L(w+1)/s) and the complexities of the previous compressed methods. In this context, LA serves as a measure of the similarity between the functions fc. and can be bounded by the "variince" of the Hessians of the functions fa (see Theorem 4.8). Thus, MARINA-P the first method whose iteration complexity can provably improve with the number of workers
4. Moreover, MARINA-P can achieve the s2w communication complexity of
O
db L ne
a
When LA is small and n > 1, this communication complexity is provably superior to (2) and the communication complexities of the previous compressed methods.
3

---

5. Our theoretical improvements can be combined with techniques enhancing the w2s com- munication complexities. In particular, by combining MARINA-P with MARINA (Gorbunov et al., 2021) and adding the crucial momentum step, we develop a new method, M3, that guarantees a total communication complexity (s2w + w2s) of
d8 Lenax nt73g
LA
When n 1 and in the close-to- tonse-to-homogeeeuus regime, i.e., when L is small, this complexity is better than (2) and the complexities of the previous bidirectionally compressed methods.
6. Our theoretical results are supported by numerical experiments (see Section F).
Lower Bound under Smoothness
Let us first investigate the possibility of improving the iteration complexity O ((w-1)6"Lee) under As- sumptions 1.1,1.2 and 1.6. In Section G, we consider family of methods that include those proposed Zheng et al. (2019); Liu et (2020); Philippenko and Dieuleveut (2021); Fatkhullin al. (2021); Gruntkowska et al. (2023), where the server communicates with workers using unbiased/biased compressors, and establish that
Theorem 3.1 (Slightly Less Formal Reformulation of Theorem G.5). Under Assumptions 1.1, 1.2 and 1.6, all methods in which the server communicates with clients using different and independent unbiased compressors from U (w) and sends compressed vector to each worker cannot converge before Q2 (1w+1)L8'/s) iterations.
The theorem remains applicable to biased compressors B (a) (see Section B) with lower bound of & (ae)) This is because if C U(w,, then (w + 1)- B ((w (w1+))))) We also establish more general result (Theorem G.4); "all methods in which the server zeroes out coordinate with probability < independently across iterations cannot converge before Ω (L5% iterations."
Remark 3.2.
This lower bound is tight up to constant factor. For instance, under exactly the same assumptions, the EF21-P mechanism from Gruntkowska et al. (2023) converges after θ ((=+))za/+)) iterations. Unlike (4), this convergence rate does not scale with n, and Theorem 3.1 leaves no room for improvement. Consequently, breaking the lower bound requires an additional assumption about structure of the problem. Before presenting our candidate assumption, we first introduce ingredients needed to leverage it to the fullest extent: our novel downlink compression method and the type of compressors we shall employ.
The MARINA-P Method
Let us first recall the MARINA method (Gorbunov et al., 2021; Szlendak et al., 2021):
x rg' é¹ Bernoullip))
V Vi(ttt))
if 1, cf 0
9f
for all i [r],
(5)
where 9d fz(2). Motivated by MARINA, design its primal counterpart, MARINA-P (Algo-
rithm 1). operating in the primal space of the model parameters, as outlined in (6).
At each iteration of MARINA-P. the workers calculate V (w(f) and transmit it to the server. The server then averages the gradients and updates the global model xf. Subsequently, with some (typically small) probability p, the master sends the non-compressed vector r'11 to all workers. Otherwise, the 4t worker receives a compressed vector C (xrf-1 x²). Each worker then uses the received message to compute w t+1 locally. Importantly, C1 (2.+11 - -..)....,C this distinction will form the basis of our forthcoming advancements.
(x(+++1
x²) can differ, and

---

The MARINA-P Method:
Initialize vectors 20, wp, ...... wo R. step size ? > O, probability p S and compressors Cg....,cy E U(wr) for all t 2 0. The method iterates
g'
V)(()))
n
x ++ = x' -agg
c¹ ~ Bernoullipp).
(6)
w w { |
if =
[ + Cx x²)
if 0
for all i [n]
We denote w' == 1/1 Ei= w See the implementation Algorithm 1.
Comparing (5) and (6), MARINA-P P and MARINA are dual methods: both learn control variables (wf and g)), compress the differences (x++11 x² and [(('++1) V=i(=*)), send non-compressed vectors (x and ((((+++)) However, unlike MARINA, which compresses vectors sent from workers to server and operates the dual space of gradients, MARINA-P compresses messages sent from server to workers and operates in the primal space of arguments.
and with some prohability p
Let us take RandK E U(4K - 1) as example. If we set heavy communications of x1+1 and light communications of C in (6), MARINA-P averages sending pd + (1 p) < 2K coordinates per iteration. Then, the lower bound from Theorem G.4 implies that at least Ω (1=+1)6"1/3) iterations of the algorithm are needed.
(w + 1) = K/a to balance
At first glance, it seems that MARINA-P does not offer any extra benefits compared to previous methods, and that is true we could not expect to break the lower bound. However, as we shall soon see, under extra assumption, MARINA-P can achieve communication complexity that improves with n.
4.1
Three ways compress
Existing algorithms performing s2w compression share a common characteristic: each iteration, the server broadcasts the same message to all workers (Zheng et al., 2019; Liu et al., 2020; Fatkhullin al., 2021; Gruntkowska et al., 2023; Tyurin and Richtárik, 2023a).² In contrast, w2s compression methods, each worker sends to the server different message, specific to the data stored on that particular device. analogous approach can taken in the s2w communication: intuitively, sending distinct messages would convey more information, potentially leading to theoretical improvements. This indeed proves to be the case. While the usual approach of the server broadcasting the same vector to all clients does not lead to improvement over (2), allowing these vectors to differ enables a well-crafted method to achieve communication complexity that improves with n (see Corollary D.4).
In Appendix A we provide detailed discussion of the topic and compare the theoretical complexities of MARINA-P when the server employs three different compression techniques: uses one compres- sor and sends the same vector to all clients, uses a collection of independent compressors, or c) uses collection of correlated compressors. We now turn to presenting the technique that gives the best theoretical s2w communication complexity out of these, namely the use set of correlated compressors.
'A notable exception form this rule the MCM method (Philippenko and Dieuleveut, 2021) Appendix A.
5

---

4.2 Recap: permutation compressors PermK
Szlendak et (2021) propose compressors that will play a key role in our new theory. For clarity of presentation, we shall assume that d 2 n and n|d.
Definition 4.1 (PermK (for d 2 and n/d)). Assume that d 2 n and d = m,, where & Noo. Let (T...... TT) be a random permutation of {l....,d) d). For all x E R and each i E 2 ...,................ n). we define
(=(x)==xx =
Cny.
j= 1)+1
Unpacking this definition: when the server compresses vector using PermK compressor, it randomly partitions its coordinates across the workers, so that each client receives a sparse vector containing random subset of entries of the imput vector. Like RandK, PermK is also sparsifier. However, unlike RandK, it does not allow flexibility in choosing K, as it is fixed to d/n. Furthermore, it can be shown (Lemma A.6) that E U(n 1) for all i [n].
An appealing property of PermK is the fact that
c(()==
for all r E Rd deterministically. Here, it is important note that by design, compressors C2 from Definition 4. 1 are correlated, and do not satisfy Assumption 1.6. This correlation proves advantageous Szlendak et al. (2021) show that MARINA with PermK compressors performs provably better than with i...d RandK compressors.
4.3 Warmup: homogeneous quadratics
We are finally ready to present our first result showing that the s2w communication complexity can scale with the number of workers n. To explain the intuition behind our approach, let us consider the simplest (and somewhat impractical) choice of functions ft the homogeneous quadratics:
fx) = 1 Az + b + i [n].
(8)
where A pddd is symmetric but not necessarily positive semidefinite matrix, b Id and e IR We now investigate the operation of MARINA-P with Perm compressors. With probability we have u++1 = x 1+1 Otherwise w²-1 = w + 1 (1 - x²) 2 x++1 (w - x²). Hence, we initialize wp = x. for all é E [n], an inductive argument shows that w = x² deterministically for all / 2 0. Then, substituting the gradients of to (6), one gets
g¹ (Aw) + b) Aw + Art +b= Vf(x')
for all & 2 O. Therefore, MARINA-P with PermK compressor in this setting is essentially smart implementation of vanilla GD! Indeed, for < 1/n, MARINA-P with Permy sends on average S 2d/n coordinates each worker, so the s2w communication complexity is
2d
L
d6 ns
=
GD
which is n times smaller than in (2)!
4.4 Functional (LA, LB) Inequality
From the discussion in Section 3, know that to improve (2), an extra assumption about the structure of the problem needed. Building on the example from Section 4.3, we introduce the Functional (T.A, IB) Inequality.
TThe general definition of Perm/ for mod o is presented in (Szlendak al., 20211) I].

---

Table The worst case communication complexities find an E-stationary point. For simplicity, we compare the complexities with non-homogeneous quadratics: fz) = デ² A, + by x + Ci. where A; E Rd is symmetric but not necessarily positive semidefinite, b, E g and ej E R for d [m). We denote A Ei= As.
Server-to- Workers Communication Complexities (s2w)
Total Communication Complexities (s2w w2s)
Method
Complexity
Method
Complexity
GD
GD
snd ofher comprosca mellack?
undollas compecoral
CORE (Yue al. 2013)
A
CORE
A
(Yin
MARINA-P
46"1 Yo
d6 maxic
independent
vidc
maxilAr1 n=73g
max
|Ar-Al
(Cocoliary D.4)
with Pernik and Randk" (Theorem
MAHINA with Penndc
de ||
de maxiciaillA AAA]
(Conollary 4.7)
complaaitic MARINA and with ParnK are when n > and dineet--emaggerua reginee, whan end |A, ivsmall.
including EF21-P (Grustewsla sla et al., 2023), dist EF-SGD (Zhen 2019), DORE (Liu at. 2020, MCM (Phillipentio and Diculeveu, 2021), and EF21 (Futhhulin
2021).
This oblc showrzees the noulls for Ranl and PennK. gencral roulh for all comproomms provical Sections and
Assumption 4.2 (Functional (LA, LB)
Inequality). There exist constants LA, LB 2 0 such that
2 S 12
v(((+))) -v)+)((())))))
||us|l²)
+
1
1
U4
(9)
for all x, u1,-.., Un E Rdd
Remark 4.3. A similar assumption, termed "Heeerogeneittydriven Lipschitz. Condition on Averaged Gradients", is proposed in Wang al. (2023b). Our assumption aligns with theirs when LB 0. However, our formulation proves to be more powerful. The possibility that LB > 0 becomes instrumental driving the enhancements we introduce.
Assumption 4.2 is defined for all functions together, and intuitively, it tries capture the similarities between the functions f.. For n = 1. inequality (9) reduces to
[) ( s (I23 + 12/)) |ar yll Vx, y E Rdd
equivalent to standard L-smoothness (Assumption 1.1) with L L3 + Li.- The Functional (LA,LB) Inequality is reasonably weak also for n > 1, as the next theorem shows.
Theorem 4.4. For all E [n], assume that the functions f; are L.-shotth (Assumption 1.5). Then, Assumption 4.2 holds with LA- Lmmx and LB 0.
Therefore, Assumption 4.2 holds whenever the functions f; are smooth, which is a standard assump- tion in the literature. Now, returning to the example from Section 4.3,
Theorem 4.5. For all E [n], assume that the functions fi are homogeneous quadratics defined in (8). Then, Assumption 4.2 holds with LA = and LB = A|
Under Assumption 1.5, no information about the similarity of the functions f; is available, yielding LB = 0 and LA in Theorem 4.4. However, once we have some information limiting heterogene- ity, La can decrease. Notably, LA = for homogeneous quadratics. As we shall see Section 4.5, the values LA and Lg significantly influence the s2w communication complexity of MARINA-P, with lower LA values leading to greatly improved performance.
4.5 The Convergence Theory of MARINA-P with PermK
We are ready to present our main convergence result, focusing on the PermK compressor from Section 4.2. This choice simplifies the presentation, but our approach generalizes to much larger class of compression operators. The full theoretical framework, covering all unbiased compressors, detailed in Appendix D.
7

---

Theorem 4.6. Let Assumptions 1.1, 1.2 and 4.2 be satisfied. Set w = x for all i E [m]. Take PermK as C; and (L + LAv 1))= where wp (Lemma A.6). Then, MARINA-P finds an E-stationary point after
o 1 ( (L+ (
iterations.
Corollary 4.7. petp= K/d=1/1 Then, in the view of Theorem 4.6, the average s2w communication complexity of MARINA-P with PermK compressor is
d8
46 LA
(10)
The key observation is that (10) is independent of LB, and only depends on L:A This particular property is specific to correlated compressors with parameter as Perm/,, A similar result holds for independent RandK compressors (see Corollary D.4), but the convergence rate is worse and depends on LB. Nevertheless, this dependence improves with n.
(defined in Appendix A), such
When LA = 0, which is the case for homogeneous quadratics, the step size bound from Theorem 4.6 simplifies to y S 1//,, the standard GD stepsize (recall that this case our method reduces GD). Most importantly. (10) scales with the number of workers n! Even when L > O, for sufficiently big n, (10) can improve (2) to O d6 Lafs).
Let us now investigate how the constants LA and La change in the general case.
4.6 Estimating LA and LB in the General Case
It is clear from Corollary 4.7 that MARINA-P with PermK shines when La is small. To gain further insights into what values LA may take, we now provide an analysis based on the Hessians of functions fi-
Theorem 4.8. Assume that the functions Ji are twice continuously differentiable, L--moooth (As-
sumption 1.5), and that there exist D; 2 O such that
sup
(l(()))) - V DD
(11)
Rn ERd
for all E [n). Then, Assumption 4.2 holds with L = mm D; I 22 maxie[n] Lg and LB = /2 (-
Intuitively, (11) measures the similarity between the functions f.. The above theorem yields a more refined result than Theorem 4.4: it is always true that max,e[n] D; I 2 maxxe]]) Li, and, in fact, max4e[n] D; can be much smaller, as the next result shows.
Theorem 4.9. Assume that f((x) = 2x A₁ + bJ + c, where A; E IRdxd is symmetric but not
necessarily positive semidefinite, b; E Rd and c, E IR for E [n). Define A 1, 2 A, Then, Assumption 4.2 holds with LA 22 (axie(1]
||A All and LB /2 Σ |A.I).
Thus, LA is less than or equal to v max ||A Al which serves as a measure of similarity between the matrices. The smaller values ||A; - All (indicating greater similarity among the functions fi). the smaller the LA value.
In the view of this theorem, the s2w communication complexity of MARINA-P with PermK on non-homogeneous quadratics is
|A
d8 max:cl=) A.-A]
(12)
Since the corresponding complexity of GD is
[A
(13)
the close-to-homent tomeoggeoom regimes (i.e., when max4e(n] ||A, Al is small), the complexity (12) can be provably much smaller than (13). The same reasoning applies to the general case when the

---

The M3 Method
(M3 MARINA-P + Momentum MARINA):
Initialize vectors T0. 1 g.: o E R for all í E [n)], step size > 0. probabilities 0 < pr. PD Σ 1 and compressors Ci ...... Cn E ((wr))((()) _i...., 2 E U(wD) for all t 2 0. The method iterates
x² ++ x² 7g';
with probability pP,
w/th
w/ + C1 x²)
with probability 1 pP,
<t = Buft1 + (1 - -3)2
(Momentum)
(14)
([((tttt) 9 oo + ((( vf((a()
with probability pD:
with probability 1 PD
for all i [n],
where the probabilistic decisions are the same for all [n]] i.c., one coin is tossed for all workers (as in (5) and (6)), and the coins for the first and second probabilistic decisions with pp and PD are independent. We denote wf 1/x Ei= wi, g" 2/1 >i= gi:
2¹ = 1/m Ex= 24. See the implementation in Algorithm 2.
"By P(0) denote family of correlated compressors (defined in Appendix A). includes, among others, Perm K compressors.
functions fo are not quadratics: MARINA-P improves with the number of workers n in the regimes when D; are small (see Theorem 4.8).
Let us note that there is another method, CORE, by Yue et al. (2023), that can also provably outperform GD, achieving the s2w communication complexity of Q (S"rA/c) on non-homogeneous quadratics. Neither their method nor ours universally provides the best possible communication guarantees. Our method excels in the close-to-hmmoeeneuus regimes: for example, if we take A, L for all i E [n], and define L 1/n >i Li, then the complexity of CORE is Z2 (/)),
while ours is O
(66 L
+
d6 max [L, Z. Hence, our guarantees are superior in regimes where
ne
maxig(m) L, L < L. One interesting research direction is to develop universally better method combining the benefits of both approaches.
M3: New Bidirectional Method
In the previous sections, we introduce a new method that provably improves the server-to-worker communication, but ignores the worker-to-server communication overhead. Our aim now is treat MARINA-P as starting point for developing methods applicable to more practical scenarios, by combining it with techniques that compress in the opposite direction. Since the theoretical state-of- the-art w2s communication complexity is obtained by MARINA (see Section 1.1), our next research step was combine the two and analyze "MARINA + MARINA-P", but this naive approach did not yield communication complexity guarantees surpassing (2) in any regime. It becane apparent that some "buffer" step between these two techniques is needed, and this step turned out be the momentum. Our new method, M3 (Algorithm 2), is described in (14).
M3 combines (5), (6), and the momentum step =; =++ But+1 + (1 - 3) which is the key to our improvements. A similar technique is used to reduce the variance in Fatkhullin et al. (2023). Let us explain how M3 works in practice. First, the server calculates *+1 Depending on the first probabilistic decision, it sends either x*+1 or (1 1/:++111")
x²) ) to the workers, who then calculate w !+1 locally. Next, the workers compute 2++1 and depending on the second probabilistic decision, they send either ( or (2 141]- V)((=()) back to the server. The server aggregates the received vectors and calculates As in MARINA, pp and pp chosen in such way that the

---

n=10
n=100
n=1000
10%
109
10
ED
Tos30.
FF21-P. Thp1,
EF21-P. lapt.
MARINA-? Samwland10,
MARINA F, SamoRand,
SumeRandl.
10
MARIN-- Permo
MAILIN-- Rand30,
1
MAIIRNA-P, RandS.
MANNNA-P, Perm..
10
MAIRNAI Poind,
1 Si [
10-2
10 2
10
10
10-3
10-3
10
10
10-4
10-3
10
10-5
10-4
0.0
0.60.8 # bits n (s-to-w) le5
0.0 1.0 1.5 2.0 2.5
0.5
bits / (s-to-w) 1e4
# bits / (s-to-w) le4
Figure I: Experiments on the quadratic optimization problem from Section 6. We plot the norm of the gradient w.r.t. of coordinates sent from the server to the workers.
non-compressed communication does not negatively affect the communication complexity. Therefore, the method predominantly transmits compressed information, with only marginal probability of sending uncompressed vectors.
5.1 The Convergence Theory of M3
For simplicity, we consider PermK in the role of C₁ and RandK in the role of Q The general theory for all unbiased compressors is presented in Section E.
Assumptions 1.1, 1.2, 1.5 and 4.2 be satisfied. Take 7 (T. 34 (ALA + L + 1213 Lmax)) ) PD pp 1/n, B n2/33, wi 2 x0 and
Theorem 5.1.
d. ) all E [n]. Then MARINA-P with C =PermK and Q; RandK with K d/n finds an 8-stationary point after O 6t (n2/3 Lmax + vLAA)) iterations. The total communication complexity is
d6 L
do LA
(15)
nt73
Once again, we observe improvement with the number of workers n, and the obtained complexity (15) can be provably smaller than (2). Indced, in scenarios like federated learning, where the number of
workers (e.g.. mobile phones) is typically large (Kairouz et al., 2021; Chowdhery et al., 2023), the first term can be significantly smaller than as 1./s. The second term can also small in close-to- homogeneous regimes (see Section 4).
Experimental Highlights
This section presents insights from the experiments, with further details and additional results in Appendix The experiment aims empirically test the theoretical results from Section 4. We consider a quadratic optimization problem, where the functions ft are as defined in Theorem 4.9 and
A, E x000003300 We compare GD, MARINA-P sending the same message compressed using a single RandK compressor to all workers ("SameRand from Appendix A), MARINA-P with independent EF21-P with TopK compressor. We
RandK compressors, MARINA-P with PermK compressors, consider n E {10, 100, 1000} and fine-tune the step size for each algorithm. The results, presented Figure align closely with the theory, with MARINA-P using Perm compressors consistently performing best. Moreover, the convergence rate of MARINA-P with Perm K and independent Rand compressors improves with n. Since this is not the case for EF21-P, even though outperforms MARINA-P with independent RandK compressors for 10, falls behind for {100, 1000).
10

---

Acknowledgments and Disclosure of Funding
The research reported in this publication was supported by funding from King Abdullah University of Science and Technology (KAUST): i) KAUST Baseline Research Scheme, ii) Center of Excellence for Generative AI, under award number 5940, iii) SDAIA-KAUST Center of Excellence in Artificial Intelligence and Data Science. The work of A.T. was partially supported by the Analytical center under the RF Government (subsidy agreement (000000D73322/$500000 Grant No. 70-2021-00145 02.1 02.11.2021).
References
Alistarh, D., Grubic, D.. Li, J., Tomioka, R., and Vojnovic, M. (2017). QSGD: Communication- efficient SGD via gradient quantization and encoding. In Advances Neural Information Process- ing Systems (NIPS), pages 1709-1720.
Arjevani, Y., Carmon, Y., Duchi, J. C.,, Foster, D. J., 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, C., Hinder, O., and Sidford, A. (2020). Lower bounds for finding stationary points I. Mathematical Programming, 184(1):71-120.
Chowdhery, A., Narang, S., Devlin, J., Bosma, M., Mishra, G., Roberts, A., Barham, P., Chung, H. W., Sutton, C., Gehrmann, S., et al. (2023). PaLM: Scaling language modeling with pathways. Journal of Machine Learning Research, 24(240):1-113,
Fang, C., Li, C. J., Lin, Z., and Zhang, T. (2018). SPIDER:
Near-optimal non-convex optimization via stochastic path integrated differential estimator. In NeurIPS Information Processing Systems.
Fatkhullin, I., Sokolov, I., Gorbunov, E., Li, Z., and Richtárik, P. (2021). EF21 with bells & whistles:
Practical algorithmic extensions of modern error feedback. arXiv preprint arXiv:21 10.03294
Fatkhullin, I., Tyurin, A., and Richtárik, (2023). Momentum provably improves error feedback! Advances in Neural Information Processing Systems.
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.
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 11761-11 1807. PMLR.
Horváth, S., Ho, C.-Y., Horvath, L., 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, J., Qian, F., Gerber, A., Mao, Z. M., Sen, S., and Spatscheck, O. (2012). close examination of performance and power characteristics of 4G LTE networks. In Proceedings of the 10th international conference on Mobile systems, applications, and services, pages 225-238.
Huang, X., Chen, Y., Yin, W., and Yuan, K. (2022). Lower bounds and nearly optimal algorithms in distributed learning with communication compression. arXiv preprini arXiv:2206.0300 03665.
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 federated learning. Foundations and Trends@ in Machine Learning, 14(1-2):1-210.
Konečný, J., McMahan, H. B., Yu, X., Richtárik, P., Suresh, A. T., and Bacon, (2016). Federated learning: Strategies for improving communication efficiency. arXiv preprint arXiv: 1610,0549.
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://yan.lecun.com wttp.//cccc.coo/////iisssss 2.
Li, Z.,, Bao, H., Zhang, X., and Richtárik, P. (2021). PAGE: A simple and optimal probabilistic gradient estimator for nonconvex optimization. In International Conference on Machine Learning, pages
PMLR.
Liu, X., Li, Y. Tang. J., and Yan, M. (2020). A double residual compression algorithm for efficient distributed learning. In International Conference on Artificial Intelligence and Statistics, pages 133-143, PMLR.
Lu, Y. and De Sa, C. (2021). Optimal complexity in decentralized training. In International Conference on Machine Learning, pages 7111-7123. PMLR.
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.
Narayanan, A., Zhang, X., Zhu, R., Hassan, A., Jin, S., Zhu, X., Zhang, X., Rybkin, D., Yang. Z.,, Mao, Z. M., et al. (2021). A variegated look at 5G in the wild: performance, power, and QoF implications. In Proceedings of the 2021 ACM SIGCOMM 202/ Conference, pages 610-625.
OpenAl (2023). GPT-4 technical report. ArXiv, bbss/303.08874..
Philippenko, C. and Dieuleveut, A. (2021). Preserved central model for faster bidirectional compres- sion in distributed settings. Advances in Neural Information Processing Systems, 34:2387-2399
Ramesh, A., Pavlov, M., Goh, G., Gray, S., Voss, C.,, Radford, A., Chen, M., and Sutskever, I. (2021). Zero-shot text-to-image generation. In International Conference on Machine Learning, pages 8821-8831 PMLR.
Richtárik, P., Sokolov, I., and Fatkhullin, I. (2021). EF21: A new, simpler, theoretically better, and practically faster error feedback. In Neural Information Prucessing Systems. 2021.
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.
Szlendak, R., Tyurin, A., and Richtárik, P. (2021). Permutation compressors for provably faster
distributed nonconvex optimization. In International Conference Learning Representations.
Tyurin, A. and Richtárik, P. (2023a). 2Direction: Theoretically faster distributed training with bidirectional communication compression. Advances in Neural Information Processing Systems.
Tyurin, A. and Richtárik, P. (2023b). DASHA:
Distributed nonconvex optimization with communica- tion compression, optimal oracle complexity, and no client synchronization. 1/th International Conference on Learning Representations (ICLR).
Tyurin, A. and Richtárik, P. (2023c). Optimal time complexities of parallel stochastic optimization methods under a fixed computation model. Advances in Neural Information Processing Systems.
Wang J., Lu, Y., Yuan, B., Chen, B., Liang. P., De Sa, C., Re, C., and AndZZang, C. (2023a). CocktailSGDD: Fine-tuning foundation models over 500Mbps networks. In International Conference on Machine Learning, pages 36058-36076. PMLR.
Wang, J., Wang. S., Chen, R.-R., and Ji, M. (2023b). A new theoretical perspective on data hetero- geneity in federated optimization. In Federated Learning and Analytics in Practice: Algorithms, Systems, Applications, and Opportunities.
Wangni, J., Wang, J., Liu, J., and Zhang, T. (2018). Gradient sparsification for communication- efficient distributed optimization. Advances in Neural Information Processing Systems, 31.
Yue, P., Zhao, H., Fang, C., He, D., Wang, L., Lin, Z., and Zhu, S.-c. (2023), CORE: Common random reconstruction for distributed optimization with provable low communication complexity. arXiv preprint arX9v:2309. 13307.
Zheng, S., Huang, 7.,, and Kwok, (2019). Communication-efficeenn distributed blockwise momen- tum SGD with frror-feedbcck. Advances in Neural Information Processing Systems, 32.
12

---

Contents
Introduction
1.1
Related Work
2
Contributions
3
Lower Bound under Smoothness
4
The MARINA-P Method
4.1 Three ways compress
4.2
Recap: permutation compressors Permy
4.3
Warmup: homogeneous quadratics
4.4
Functional (LA, LB) Inequality
4.5
The Convergence Theory of MARINA-P with PermK
4.6
Estimating LA and LB in the General Case
5
M3:
A New Bidirectional Method
5.1
The Convergence Theory of M3
10
6
Experimental Highlights
10
Three unbiased ways to compress
15
Biased Compressors
17
C Properties of LA and LB
18
D Convergence of MARINA-P in the General Case
21
D.I Main Results
21
D.2 Proofs
22
D.3
condition
27
D.3.1 Main Results
27
D.3.2 Proofs
28
Convergence of M3 in the General Case
30
E.1 Main Results
30
E.2
Proofs
31
E.3 Polyak-Lojasiewiez condition
42
E.3.1 Main Results
42
E.3.2
Proofs
43
Experiments
F1 Experiments with M3 on quadratic optimization tasks
51
13

---

F.2
Experiments with an autoencoder and MNIST
51
F3
Extra experiments with quadratic optimization tasks
52
Proof of the Lower Bounds
55
G.1
The "difficult" function from the nonconvex world..
................................
55
G.2
Theorems
55
G.3 Compressed communication with independent ................................
58
H Useful Identities and Inequalities
60
Notation
14

---

A Three unbiased ways to compress
The main focus of this paper handling the gover-to-worrke communication costs. To explain better where the improvements outlined in the main part of this paper come from, let us first consider the scenario where uplink communication cost is negligible but downilnk communication cost is not. While we do no necessarily say that this is a realistic setup, examining it first enables us to understand how downlink compression should be performed, capturing all the intricacies.
Existing algorithms with lossy s2w and w2s communication have a certain common feature. The compression mechanism employed on the clients is very different from the one used the server: while each client transmits to the server a different message, specific to the data stored on each device, the server broadcasts the same update to all clients. We want to question this algorithmic step and suggest to the reader that if compression is applied multiple times and each worker receives its individual update, then intuitively more information can be transmitted. A well-designed algorithm should be able to take advantage of this.
One can depart from the usual approach of sending the same update to all workers in two ways: a) compress the update n times independently, or b) produce n such updates in a correlated way. Either way, the server broadcasts different compressed messages rather than one, and sends different update to each worker. The key discovery here is that both a) and b) are mathematically provably better than the prevalent approach of sending the same update all clients.
This is a crucial improvement in a system where the above setup is a good approximation of reality. And even if it is not, and the current model is not perfectly capturing the reality, we can accept it for now, as allows us to focus on the novel aspects of the approach. With that said, these considerations serve as starting point for thinking about bidirectional compression: having focused on the simplified setup and equipped with knowledge on how the compression on the master should be performed, employ this mechanism in more complex scenarios (see Section 5).
Let us now describe the three possible ways to perform compression on the server.
"Same" compressors. The prevalent approach in downlink compression is to transmit the same up- date to all workers. To illustrate this, let call a collection ..,..., C,, of compressors "Sn if for all i E [n] we have C; C for some RandK compressor C. Now, consider one iteration ł of MARINA-P with Ran compressor. The server calculates C₁ (a²=1 x') ) for i E [n]]. but in this case, Ci - x²)
C, (x+t1 x²) C'(x'+1 - x²). Thus, applying collection of SameRand compressors to some vector E Id is equivalent to using single RandK compression operator and transmitting the same message C(x) to all workers.
Independent Compressors. Rather than setting (x) C(x) for all i E [n]. one can break the dependency between the messages and allow the compressors to differ. For illustrational purposes, suppose that C,, i E [n] are independent RandK compressors (Assumption 1.6). Then, applying such a collection of mappings to the vector of interest & E Rdd one obtains n distinct and independent sparse vectors Ca (1r)....,
Remark A.1. We are aware of only one method that uses n distinct compressors in downlink compression, Rand-MCM by Philippenko and Dieuleveut (2021). Given the absence of results in the non-convex case. let us compare the communication complexities of Rand-MCM and M3 under the Solyak-Lojasiewice condition (Assumption D.9), which holds under strong convexity. In the strongly convex case, the proved iteration complexity of Rand-MCM is
Ω
Linax
2 P
WPWD
1/2
+
WD
log
Assuming for simplicity that the server and the workers use RandK compressors with K = d/n, this gives the total communication complexity of
Ω
Lmax
3/2 wp
WPW
1/2 D
WD
log
= S
d ddyiLmax
log
8
Vn
1
which is getting worse as the number of workers n increases. Meanwhile, by Corollary 10 the total communication complexity of M3 (where C are the PermK compressors and Qj are independent
15

---

RandK compressors, both with K = d/n) under the Dllyak-Lojasiewicz condition is
o (( [
dLa
80
n2/3pp
+
log
μ
Since n is typically large, the total communication complexity of M3 can be much better than that of Rand-MCM.
Correlated Compressors. In their work, Szlendak et al. (2021) introduce an alternative class of compressors, which satisfy the following condition:
Definition A.2 (AB-inequality (Szlendak al., 2021)). There exist constants A, 2 0 such that the random operators Ci.... Cn satisfy
E [x)())]
= 2;,
(1))))
1 3
|
Σ
Tz
(16)
n
m
71
for all z, 21, E RR If these conditions hold, we write {C:] E UUA, B).
Following on this idea, we introduce the concept of a collection of correlated compressors.
Definition A.3 (Collection of Correlated Compressors). There exists constant such that the random operators Ci.... Cn satisfy:
[x){ = æ
12
Cxx x
||||"
(17)
for all x E Rd. If these conditions hold, we write {C.) E IP()).
Definition A.3 will play key role our upcoming advancements. But what makes this assumption reasonable?
First, it is easy inequality (17) holds with == A - B. It turns out that it is in fact strictly weaker, as the following example shows.
that condition (17) is weaker than (16). Indeed, if (C.) E U(A, B), then
Example A.4. Let 2, d = 1. Let (C. x E RR be a collection independent Cauchy variables indexed by real numbers. Define Ci (w) = u + Cu. and C2(
Su- Then
(C1 (u) + Cz(U)) = u, 2
so C₁ (u) and (u( satisfy Definition A.3 with 0 = O. However, for # u2 by the properties of Cauchy distribution we have
(ui + w2) (u)+
( (CI + 62) +12))
27
E
(((m)+Co(u))
E [c + c + +21ce 00.
Thus, (u) and Cz(u) do not satisfy Definition A.2.
In fact, the condition specified in Definition A.3 does not impose any restrictions on the compres- sor class when working with unbiased compressors, This is because, for any set of compressors Ci...., Cn e U(w), there exists 0 2 0 such that {C, ) E P(0), as shown in the following lemma. Lemma A.5.
Let CI....,C, be collection of compressors such that C, E U(w) for all i E [n]. Then [C.]== IP(W).
16

---

2. Let us further assume that CI....,C Cn, are independent (Assumption 1.6). Then {Cil (w/n)).
Proof.
1. Jensen's inequality gives
|
E
Σ Ci()) u
[IC:(u)
u1]
Def.1.4
-
1 |uul
Σ w
|/ull
==1
so w.
2. Using independence of compressors, we have
E
n 1=1
n Σ
c(u))
u
n
[IC,(u) 100--ullf -112]
Def.1.4
S
n2
Σ
n
w
|u||
|u||
i=1
Thus 0 = s/n.
However, the true advantages of employing correlated compressors become apparent when the definition holds with 0 = 0, as in the case of PermK compressors.
Lemma A.6. Let C Ci...., Cn be a collection of a) SameRandK, b) independent RandK, c) PermK compressors. Then
a) (C E P(W) and C, E U(w) where 4/K 1 for all i [m],
b) (C.) E PP(4/a) and C, U(w) where 4/K for all E [m].
<) (c.) E (0)) and C, U(w) where w = - for all [n].
Proof. Unbiasedness follows easily from definitions of compressors (the proof for PermK com- pressors can be found Szlendak et al. (2021)). That RandK E W(d/K -1 (and hence trivially SameRandK' U(4/k- 1)) is well-known fact. Next, the fact that a) {Cr) E PPW)) for SameRandK compressors and b) (C)) IP(4/n) for independent RandK compressors follows directly from Lemma A.5.
To compute for PermK compressor, first assume that d 2 Then E [[(()))]] ||>||
(Szlendak et al., 2021), so
E (1)) x||] (88)
[[C)(=))
|| -
= (n - 1) ||=1
Similarly, suppose that n, and write n as n qd + r, where & E N and < d. Then E [[C((())]*] 7/a ||=||| (Szlendak et al., 2021), and hence
[IC](()) =|[]] (48) [|C((=)]]] - ||x|| [ -1 | S (n 1) 1=+]
In both cases w Finally, by construction of PermK, we have Σr Cx(x) = x, implying 0 = 0.
In what follows, when considering the Perm/ compressor, shall assume for simplicity that d > The results for d < n are analogous.
B Biased Compressors
In addition to unbiased compressors (Definition 1.4), the literature of compressed methods distin- guishes another class of mappings:
17

---

Algorithm MARINA-P
1: Input: initial model zn Rd (stored on the server), initial model shifts wpy w x (stored on the workers), step size 7 > 0. probability < S 1, compresssors Cj , Cn E (ww))
1''d do 2: for t = ,,.
3: for .,.... in parallel do
4: Calculate fi (wef) and send it to the server
Workers evalunte the gradients at the current model estimate
5:
end for
On the server:
6: g¹ = -i= (w)))
Server averages the messages received from the workers
7:
x 1+ x² 7
Server takes gradient- type step to update the global model
8:
Sample c ~ Bernouli(pp)
9:
if = then
10:
Send (1 ------x)) x²) to worker i for i E [n]]
Server sends compressed messages workers wip,
11:
else
12:
Send x1 to worker for i [n]
same uncompressed message w.p.
13:
end if
On the workers:
14:
for 1,.... n in parallel do
x +1
cf = 1, if c' = 0
15:
1+1 wi
w Cz - -x²)
Worker updates its local model shift
16:
end for end for
17:
Definition B.1. A stochastic mapping C IRd Rd is a biased compressor if there exists (0, 1] such that
E [[(()) - x {|| s1 - a) ||||
Vz E Rd.
(18)
The family of such compressors is denoted by B(a). It is well-known that if C E U(w). then (w + 1)- E BB ((w + 1)-1), meaning that the family of biased compressors is broader. A canonical example is the Topk E (B(/a)) compressor, which preserves the K largest in magnitude coordinates of the input vector (Beznosikov et al., 2020).
C Properties of LA and LB
We first prove the results from Section 4, starting with calculating the constants LA and Lg from Assumption 4.2 in some special cases.
Theorem 4.4. For all E [n], assume that the functions fa are L.-smooth (Assumption 1.5). Then, Assumption 4.2 holds with LA Lunax and LB = O.
Proof. From Assumption 1.5 it follows that
(50)
1 n
V ( u.) vA(=))
VVi(( ux) vf((2))
n
72
i=1
1.5
Lス ||
72
L2 m
n
so Assumption 4.2 holds with LA = Lmax and LB = 0.
Theorem 4.5. For all i E [n), assume that the functions Ji are homogeneous quadratics defined in (8), Then, Assumption 4.2 holds with LA and LB |||
18

---

Proof. It is easy to verify that
2 v(((a))
V -
A (r + us) + - (Ar + 6))
1=1
72
||||
W
meaning that Assumption 4.2 holds with LA = and Lg
||||
Lemma C.I. Let Assumption 1.5 hold. Then, there exist constants LA LB such that Assump- tion 4.2 holds and L' - Li < L
Proof. Assumption 1.5 gives
Vi(x + u.) VA(EE) -VVVA(()))
(50) 1
Vil( +4) vf((2)]
71 i=1
L3 ||ul||
i=1
I max
||us|l?
1=1
and hence Assumption 4.2 holds with I23 1.2
max and T.
Remark C.2. Under Assumption 4.2 we have
Asx.12
Vi(x -v)-)((())
3A Σ
||u,1?
+ L3
1.5.1.5
1
(L3 + L
||u,|
so, in principle, one could always set L3 = 0. However, the bound could tightened by decreas- ing La and increasing LB. The smaller La. the better the performance of our algorithms (see Corollaries D.4 and E.3).
Now, we proceed to prove the result that relates the values of LA and LB to the Hessians of the functions fi.
Theorem 4.8. Assume that the functions fo are twice continuously differentiable, L.-smooth (As-
sumption 1.5), and that there exist D; 2 O such that
sup
- ( <
(11)
ERd
for all E [n]. Then, Assumption 4.2 holds with LA = m2 D; S 22 maxiejm) L; and
Lg = 2 (1 En
Proof. By the fundamental theorem of caleulus,
Vi(x + + - (()())))) = [ fili( + (u,) = (/''/1to+ + u = Quii
19

---

where Q: = 1o fi + dt. Letting Q =
-
Q we can write
10
Vi( u.) v.((z))
04
n
Q
Q o +Q
Σ
1=1
(44)
n
2
QQ Q) u +2 Q
- Σ
14
1=1
(50)
a
QQ: Q) 4 2 2 211211
1
Σ
13
24
1
72
i=1
QQ
Q1 2 | 2 + +2
1
7
i=1
Further,
||Q QI
V f((x + tu,)dt
1
1 n
Σ
V fz tu,)
n
j=l
L. n
V2 + tw;)dt
V2 fz(2 + tuy )d
j=1
2 (1:) v2 55 +t,)) dt
n 1=1
1 Σ
v2 1i + (w,)
r2 ((gg di
==1
$ //¹
D,dt Di.
and
1
1/'
|Q|
42 fz + tuy)dt
V2 Vif + tu,
J=1
1
2 (r tuy)
dt
42 fy (z + +z
0
1 L,dl
1
n
Lj-
n1 j=1
j=1
By combining the above, get
2
1 æ
12
1
1 n
1
(Vill u2) --(()))
<2 n
Σ DF 1|
+2
Σ
Lg
Σ 24
n
i=1
2 max D?) ||u.|12 +2
1
Σ
ト
4
5=1
which means that Assumption 4.2 holds with L3 2(max, DP) and Li 2 2.)
20

---

Remark C.3. that supz,rt
Clearly, if Assumption 1.5 holds, i.e. if there exists L, 2 O such fi(i')) I L, for all i [n], then there exists D; such that
sup 21p0. Fp ER not restrictive. Indeed.
f2((zz) 1 دー {
I D,. which means that this latter condition is
1 Σ vof((z))
V2 f(
1 2 ft
+
fz(2)
n1 j=1
n
j=1
$ Si +
v2 [z1)
Li + 1 n j=1
Lj
However, D, can be small even if the constants { are large, as the next theorem shows.
Theorem 49. Assume that fx(x) 2 A₁ + b, Ci where A; E RRdxd is symmetric but not necessarily positive semidefinite, b; E Rd and c for i E [n]. Define A n -/== A,. Then, Assumption 4.2 holds with LA v2 max ||A All and L.B = v2 ( E AA,I))
Proof. In this case f22)(2) A, and the result easily follows from Theorem 4.8.
D Convergence of MARINA-P in the General Case
D.1 Main Results
As promised, we now present a result generalizing Theorem 4.6 all unbiased compressors.
Theorem D.1. Let Assumptions 1.1, 1.2 and 4.2 be satisfied and suppose that {C E P(O) (Def. A.3) and C₁ U(wp) (Def. for all E [n]. Let
1
0 0<75
L+ v (B3wo + 1330) ( 11
Letting
71.2 1
7T.
Te = f(x))
8r +
Σ
|| - 211
1/ x² x²11?
2p
2p
==1
for each T 2 1 we have
2w | <
TT
Let us provide some important examples: Theorem D.2. Let Assumptions 1.1, 1.2 and 4.2 be satisfied. Choose
L+ 112 + w0/0
for SameRandK compressors
L+ v (I'3 + Lif/m) wo/D)
for independent RandK compressors
+ LAVws//)
for PermK compressors
21

---

and set w x for all i [n]. Then MARINA-P finds an E-stationary point after
80 L+ (12+t2))
for SameRandK compressors for independent RandK compressors
(23+ (L3
T
for PermK compressors
iterations. Remark D.3.
The result for PermK compressors proves Theorem 4.6.
The above theorem demonstrates the complexities for a) SameRandK, b) independent RandK and c) PermK compressors. However, the result applies to any families of compressors such that for all 2 we have a) Ci Ci....,Ch, C, E U(wp) are independent, and c) Ci....., Cj E U(wP) NP((), respectively.
= C. = E U(wp), b)
We now derive the communication complexities:
Corollary D.4. Let us take 1/2 and set K = d/n (corresponding to the sparsification level of PermK compressor). Then, in the view of Theorem D.2, the average s2w communication complexity of MARINA-P is
15
d8
T2
B
for SameRandK compressors
d
L
+
d6
V L3
+
L2
for independent RandK compressors
(19)
46
d5
2 LA)
for PermK compressors
Remark D.5.
The result for PermK compressors proves Corollary 4.7.
The key observation from (19) is the dependence on I. and L.. In particular, LA (which is the case, e.g., for homogeneous quadratics), the above communication complexities are
0
8
+ LB)) +
for SameRandK compressors,
8
d
L
Lg v
for independent RandK compressors,
for PermK compressors.
Hence, only by sending different messages to different clients, one obtains complexities improving with n. particular, for PermK, the complexity scales linearly with the number of workers.
D.2 Proofs
To prove the results from the previous section, we first establish several identities and inequalities satisfied by the sequences (wi,... "al.......,)ee. w hiz-- We start by studying the evolution of the quantity |mu| = what follows, E,, [-] denotes the expectation conditioned on the first iterations.
Lemma D.6. Let C E ((wP) for all [m]. Then
- < (1
Wt - x² =0]] + +(1 -ppwpB [|1a411 2² 2²113]
22

---

Proof. In the view of definition of w we
Ex ++1
x -1+
|| + (xx - -x²) -
(1-p)
(48)
p)
[|| - x²) (x - x')ll |1² +1 p)L, [| x² (19]]
(1 p)wp || z²11 (1 p) || - x²11?
Averaging, taking expectation and using the tower property, we get the result.
This lemma is less powerful: it is not an identity, and hence some information is lost. Moreover, it focuses on single client i, and is therefore not able to take advantage of the correlation among the compressors. On the other hand, it can used in the convergence analysis without any need to restrict the function class.
Next, we study the evolution of the quantity I|wl - 101
Lemma D.7. Let {C:)= 10). Then
B - [11 (1 p)) || x'') 20'l?] (1 p)OE [| -
-x:211 =0(1?]
Proof. In the view of definition of w we get
Eg
|| ||
x.
111
w +1
1+1
=
1=1
1 Σ
(1 - E)E,
(wf + C, -1-11)))) x111
n
27
1
(1- - D)
(xtt1 -x¹) - -(x+t1 - x²) x² =²
7
(48)
- F1
Σ caatt11- -x²) (x. - -aa -(xtt1-aa)
+ (1 pp || - 2011?]]
n2
Def.
(1- p)0 | |
x0 11 - p) I|w0 - 22'1 211??
Taking expectation and using the tower property, get the result.
This lemma is more powerful since it able take advantage of the correlation among the compres- sors. Indeed, if 0 0 (as in the case of PermK compressors), then it becomes an identity:
IE ||
1241 ||] (1 p)B [|w -00==") =²=
We now prove convergence of MARINA-P in the general case.
Theorem D.I. Let Assumptions 1.1, 1.2 and 4.2 be satisfied and suppose that {C E P(0) (Def. A.3) and C₁ E U(wp) (Def. for all E [n]. Let
1
0<75
L / (1aor + 1300 ( (1)
23

---

Letting
2L3 1 Σ |
7L
ve - ((x0)
/ +
- =x11² +
1/w
x 21
2p
2p
1=1
for each T 2 we have
Σ
[
2100
yT
Proof. First, combining the incqualities in Lemmas D.6 and D.7, we get
2
1
E
2+1 - xt 113 +
2 R
|1
x 11
2p
n1
2p
1=1
2
p)
1 n
Σ E ||0
=²11²] +
2L2 (1 p)wupT || - x x²11]]
2p
7
2p
71// (1
- p) [1 100--*"0 - =011²]
||1o - z²61 [13]
+
+
(1 - p)BB
2p
2p
(1 p)
p) Σ
1
E ||wo x x²11²]
71.
(1 p)L [1100= x11]]
2p
2p
i=1
Y (L3wp 17,0) (1 - D)B |1:041 -xx2 1-]
+ 2p
(20)
Next, using Assumption 4.2, we have
E Illo' -
[|1''~vS(''))l'' [[aa)]]]]] = E
(Vi((w)) - v(((2'))
4.2 S
L2
1
|lo - ==111]] + L3GE
n2
w x
11
Combining the above inequality with Lemma H.1 gives
15 S E
[5a]
1
1.
E
|| 1x11
x. =0113]]
+ F
[los - (s('')1?)
2n
2
2
S I [60]
E
1
L
E
|| [1[]]
2
2%
2
1 n
+7 7 2
L3
Σ
E
||
x'
|13]
+ 13B
|||ut= =01((]]
(21)
72
By adding inequalities (20) and (21), we get
E [t+1]= = E [6
+
E
++1 - 2 113
+
E [| - 1211-=++11 11]
2p
2p
1=1
S SE [69]
JE
[12]
1
L
E
||
- x (1()]
2
27
2
+ 2
1
1
Σ
E
[||
x² =11²]
+ E
|1 - -2-"0=1 ==((²]
2
1=1
L
|| - 2²13]] + 2L3 (1 p) || =01
(1 p)
-
2p
2p
2
(LaWp + L330) (1- - p)l ||aot1- - x0113]]
+
2p
24

---

E
[V]]
E
2
L
(LaW + LB30 (1 p)
|| x² 2²11]]
27 2
2p
$ E
V4
E
[f(xt)]]
2
where in the last line we use the assumption on the step size and Lemma H.2. Summing up the above inequality for 0, 1, ..... T 1 and rearranging the terms, we get
2400
E |()()))
& 7
E
E
T T=
With the above result, we can establish the iteration and communication complexities of MARINA- for three different compression schemes described in Appendix A. First, let prove result when independent compressors are used.
Theorem D.8. Let Assumplions 1.1, 1.2 and 4.2 be satisfied and suppose that Ci..... C. is collection independent compressors (Assumption 1.6) such that C₁ U(w) for all [n], E N. Choose
(+ V (L3 + L2/n)) wP/p
and set w x for all i E [n]. Then MARINA-P finds an e-stationary point after
( 80 L+ V (L3 + (////) w//l)
T = 0
iterations.
Proof. In view of Theorem D.I, the step size satisfies the inequality
1
S5 L +
(1urr+ + 12300) -1)
Since by Lemma A.5, when the compressors independent have wr/n, the algorithm converges in
yo T
(Bzup + 13 WP) n
( (
L+
E
Wp
L2 + 12
0
L
+
(22)
p
iterations.
Theorem D.2. Let Assumptions 1.1, 1.2 and 4.2 be satisfied. Choose
-1
L+ (12 + wp/p
for SameRandK compressors
L+ v (I'3 + Li//n) wF/p)
for independent RandK compressors
+ LA/ww/D)
for PermK compressors
25

---

and set w x for all i [n]. Then MARINA-P finds an E-stationary point after
80 L+ (1a+t))==ms
0
for SameRandK compressors for independent RandK compressors
T
80 1+
(LLLAV-P/r
for PermK compressors
iterations.
Proof. In view of Theorem D.I, the step size such that
1
7 S L + (43wp L300) L30) ( (1-1)
We now use Lemma A.6 and substitute the vales of f specific to each compression type. For SameRandK, we have wp, the algorithm converges after
1 ( 10 L+ ++y(ee (1aup + (Bwp) [ (--1))= = ( ( L+
(
WP (L3 + (
T
(23)
iterations. Following the same reasoning as in the proof of Theorem D.8, for RandK we have
40
L+ +
+ 123 wp up) n
( (--1) - To
wp
+
12 +
p
n
(24)
Finally, for PermK we have = 0, so
T= To
L+ [
13wD 1tyu
1 -
TT (=r
L+ LAy (
WP
))
(25)
The result follows from the fact that w x for all i [n].
Corollary D.4. Let us take p = 1/n and set K d/a (corresponding to the sparsification level of Permk compressor). Then, in the view of Theorem D.2, the average s2w communication complexity of MARINA-PPPP is
48 d80
T.
for SameRandK compressors
d8 L
d
I.3
+
1.
for independent RandK compressors
(19)
ne
d8 L
48" g
LA
for PermK compressors
ne
Proof. The expected number of floats server is relaying to each client at each iteration of MARINA-P
pd + (1 p)k + n 2d
n
Next, using the results from Lemma A.6, our choice of compressors and parameters gives d/k 1 n in each of the three cases. Hence, substituting p = 1/n (23), (24) and (25), we obtain the following server-to-worker communication complexities:
26

---

1. for SameRandK compressors:
80 d x
+ up (L LBz)
(p
(1-1))
=
5
d
L
L+
d
VV + L2z (n 1)2
E
n2
n
8
I + d 13 13+ + +12))
2. for RandK compressors.
8
L2 L3 + +
( -
)
8
d
d
/ [33
Lif
L wp
+
(n - 1)2
n
n
80
d
1
0
L + dv
123
+
71
n
3. for PermK compressors:
d
8"
L 1 LzWp
[ (
8
d
L
-
d
(n 1)3
n
&
n
60
d
L dLa )
o
D.3 Polyak-L.ojasiewizz condition condittooooooooi
D.3.1 Main Results
To complete the theory, we now establish convergence result for MARINA-P under the Polyak- Fojasiewicz assumption.
Assumption D.9 (Polyak-L.ojssewwicz condition). The function / satisfies
(PL)
condition with parameter μ,, i.e., for all E IRd there exists x" arg min [(x) such that
2p (f(x) f(x))((x))))))))))))))))))))ff |
(26)
Theorem D.10. Let Assumptions 1.1, 1.2, 4.2 and D.9 be satisfied and suppose that (c E P()))
and C. E U(wp) all i E [n]. Take
p
0 < 7 < min
(27)
2 213 1330) ( -1)
2/
L. v
Letting
27
2 1
L
V' ff(0') ft
|lo 2²11"
+
Σ
m
x²
(28)
n
for each T 721 we have
E V S (1 To.
Corollary D.11. Let C P(0) for all i E [n] fe.g. PermK), choose p 1/(WP + 1). Then, in the view Theorem D.10, Algorithm I ensures that E [f(x²T f² S after
1 max {
[L+ LAWP
L
sp + 1 log
40
1
iterations.
27

---

Corollary D.12. Let C be the PermK compressors (K = dfn). Then, in the view of Corollary D.11, the s2w communication complexity of MARINA-P with PermK
o
((
dL mp
dLA +
40 - log
1
&
D.3.2 Proofs
Theorem D.10. Let Assumptions 1.1, 1.2, 4.2 and D.9 be satisfied and suppose that {c]) P(O) and C. E U(wp) for all i [n]. Take
1
P
0 <<> 7 min
(27)
L v 2
2 + 1300) (7 -
2/1
Letting
27
2 1
n
E || xz 22'11]] + 7
1e = [((x') 1r
w
x²
(28)
P n
for each T 221 have
E
T S (1 - (1-))=² yo
Proof. We proceed similarly as in the proof of Theorem D.1. Combining the inequalities in Lem- mas D.6 and D.7 gives
2LB
E
++ - 119 +
E
| x 221
p
p
1=1
L
1 Σ
||0 - 2² 2²1²²] + 2L3 (1 - p) p)wplE || - x0112]
(1 - p)
n2
+ yLB (1 p)
[11--= - =11 + 2LL (1 p)B || - x11
p) 1 Σ E |loo
x1 x111²] + 711 (1 pT [| -
-x'1= =111?]
p n1
P
+ 7 (L3wp + L230) -D>E || 1133
(29)
p
By adding inequalities (21) and (29), we get
L
71 11
[t] = E 15
Σ E
|| - 00+111
x 1 |13]
p
E
[00
I EE
V
(cc
||3]
(
1
E || - 20(13
2
2
2
L3 - Σ
1
E
|| |
+ L3
|11u0* - -2001 =20111
2
1=1
743
a
|| - x 201 yL. (1 p)E |1 - 20913]]
(1 p)
Σ
P
2 (LAwp- + L330) (1 (1=p)E || - -x(1²
E
189] 2
28

---

L
Y
(ww + LB0 (1 p) E || - x'112)
27
2
p
1
1
E8
|
x2|1²]
+ 7 ( 2/² E
|| w0 x x01
p
2
i=1
Ass. D.9.27)
(1 - 711) [89]
+
7LA
(1 - (1-144)
1
Σ
E W - x²112
P
714) R |11000 - 2211
(1 (1-
p
(1- 7p) E [M]]]
where the last inequality follows from the Lojassewjjsiiiizz condition, Lemma H.2 and our choice of y. Applying the above inequality iteratively, finish the proof.
Corollary D.11. Let C₁ E (O)) for all i E [m]] (e.g. PermK), choose p = 11/(wp + 1). Then, in the view of Theorem D. 10, Algorithm ensures that EE [[(x²) 1*] Se saater
LLWLAWP LAWP
40
wp + 1 log
max
iterations.
Proof. In view of Theorem D.10, the step size satisfies
1
p
7 min
L V 2 (133up + 1200 (2 -1
2/1
Therefore, since 0 = 0 and 1/(wp + 1), the algorithm converges after
+ 2 WL + 1200 (7. -
V
= max
log
1
= 0 max
+
LAWp
up + +1 log
iterations.
Corollary D.12. Let C₁ be the PermK compressors (K = =dn)). Then, in the view of Corollary D.11, the s2w communication complexity of MARINA-P with PermK is
((#
dL np
dLA
100
+ +d)
log
E
Proof. For PermK, n1 1. Therefore, the iteration complexity is
L +
Lan
o max
n
log
Since the expected number of floats the server relaying to each client is
d
2d
pd +
p)
+
the server-to-worker communication complexity n
n
n
dLA
To
max
d log
11
29

---

E Convergence of M3 in the General Case
We now move on to the bidirectionally compressed method. Below a generalization of Theorem 5.1 all unbiased compressors.
E.1 Main Results
Theorem E.1. Let Assumptions 1.1. 1.2, 1.5 and 4.2 hold and suppose that the compressors Q E U(WD) satisfy Assumption 1.6, {c E PP()) and C e ([wp)) for all i [n]. Let r > 0 be such that
/28 L+ V 288 (0r 0 +
1+0pp
L +
up pr
+
Itwppp
L3 +
WDwp3 mpn
+ ub(lteppr) Lmaxx) upn
Letting
2
1 n2
n 1| w
V 8t
9
ff(
+ 1
w¹l
71
n
+ p 100
Σ
x0' x211?
11
where
2
17
L
47L3
Grow p BL
p
327L2
(
(
+
and P
PD'
ppD
pr
327L33
1
+
PP 32
48 1 npn
(B + pP),
M3 ensures that
1r
T-1
40 yT
Σ
We now simplify the above result by considering 0 = 0.
Corollary E.2. Let C E P(O) for all i E [n] (e.g. PermK), choose = 1/(wp + 1), = 1/(WD + 1) and
{ n 1/3
B B=min min
1
+ +1)
Then, the view of Theorem E. the iteration complexity is
Imaxx+ +
(DDWpWWD+)) +1)
1/3
T.max + wD(WD 1)
Imax + Vuplup +1)11a) ))
72
n
We now give the bound for the total communication complexity of M3.
Corollary E.3. Let C be the PermK compressors and Q₁ be the independent (Assumption 1.6) RandK compressors, both with K = d/n. Then, in the view of Corollary E.2, the iteration complexity
V0
2/3 Lmax + nnta))
and the total communication complexity is
T
[dLmax 1/3
+ ddLA))
Remark E.4. The above result proves the complexities from Theorem 5.1.
30

---

Algorithm 2 M3
1: Input: initial model zo IRd (stored the server), initial model shifts w. =f x0 E [n] (stored on the workers), initial gradient estimators g" = (v)(>") (stored on the sever), step size 7. > 0, probabilities 0 PP,PD I 1, compressors .i...., C U(wp) n P(O).
2....., 2n U(wp) for all 2 0.
2: for t 0, ....,, do
3: x+ = x² ='
Server takes gradient type step update the global model
4: Sample cp Berouuli(pp)) cp Bernoulli(pp)
5: For i E [n], send (x - x to worker if cp 0 and x++1 otherwise
6: for I,....n in parallel do
[xt+1
if cp 1;
7:
w f+1
wf + C2 -x')
if c 0,
Worker updatos its local model shift
8:
1+ Bwt + (1 ())
Worker takes the momentum stop
9:
Send (V ff((2))) to the server if cbD 0 and fi ++1
otherwise
10:
end for
11:
if c then
12:
g-+1 " E f((2)t1)
13: else
g g+1 g6 E ((V v)((()))
15:
end if
16:
end for
(maintaining only the sequence g' in the implementation is sufficient; the sequences 9 from (14) are virtual)
E.2 Prools
Similar to our approach from the previous section, we start by establishing several inequalities satisfied by the sequences (wi,..., w/o0 {zi,..., h22 and .gi.....gg'......
Lemma E.5. Let C U(WP) for all i [n] and {CD) E P(0). Then
<|1²]] < [[xtt1 x²) - pr(wf - x²) + (wf - 2till
Eg
+ pp 1| - ell + we || - 1²1
for all E [m], and
E, - < [1x - x²) - pp(w" -x") ) + (w- - =
+ pp 1| - 2²112 + +1||z**1 - 2²112
Proof. Using the definition of wt we have
E, [wt 11
1t1 + (1 (p)) - -x²)
and hence
E,
||0 (+1 - =|[[²]
(48) | + (1 pp))((of x²) =/1
+ +B, [| (21+1 + (1 pP) x²)) 1)1
= ||(00t1 - x0)) - pr(ww - x²) + (w - =1)112
+ +R, [| - (art1 + (1 pr) - =1))113]
Using the definition of w + again, get
Eg [| - =
31

---

=1((tt1 x²) -pp(uc - x²) + (wf 2)) 12
+Pp || - (1 + (1 - pp) - x') ||
+(1 pp) ||lof + (z x²) (xlt1 + (1 - pp)( xz)) =²))
||( - x²) pr(w - x²) + (w} - = + pr(1 pr)) ||u - x²'1
+(1 pr) [|(((((*) +1 - x²) - (x++1 x') + pr pr(wf - x² =0)
(48)
| x²) pr( - x²) + (wi I + pr(1 pr) 2 1 - x²11
+(1 pp pp)pp | xz 11 + (1 pp yE, || [c] x²) (x - x²) x²)1 }1(
Def. 1.4
( xt) pp - x²) + (ut² I + pp ||o x111 up || - x² 11?
Using the same reasoning. we now prove the second inequality:
E,
10 4+1 - - =11]
(48)
|ottl + (1 - (ppp)(n' x²)) ==12 + E2 [|w-t- - (xxtt) + (1- pp) - -x'))]1
= |[x0t1 - x²)= - pp(w" - x²) + (w² - =
+Ez [|lu(t1 - (1/t1 + (1 - (w) - x²) )11)
= -((+tt -x²) - -ppww" x²) + (w² - =) + pr - pp)² 1| x2/1
n
- +(1-pp)lL w² + Σ
c (x - x²) - (1 + (1 - pp) xx²))
i=1
|6/ - xz') pr(w" x²) + (w² 1o4===") = + pp (1 pp)) ||w0 xx' 112
27
+(1 - pP)
72 Σ caatt =²²) - (1 x²) + pp(w' - -z²)
1
(48)
(x - xx') - -ppwww - x²) + +www= -000-200 -11)| + +pp( (1 pp)² I|w0 11w'-xx') =x²11
+(1 pE)
1 c -2'))=(0t+ (441-2")
x²)
+ př pP) 1|10 - 221
A.3 S
|x - x²) pr(w" x²) + (w² =0)11 + pr 1|00 - 281 0 +1| 2011?
Lemma E.6. Let Assumption 1.5 hold, Furthermore, suppose that the compressors O U(wd) satisfy Assumption 1.6 and that C E ((wr) E [n]. Then
1 n
E
WpL2
2
Σ
1
x²1 2
+ + E
1
Σ
1|
woll?
+ 3(wp + 1) [|aft] - - x01]]]
n1
n i=1
1
+ (1 E
V (2
11
i=1
32

---

Proof. First, from the definition of gt*1 we get
n n
E
g +1
(i(
= (1
PD)LE
Σ g
(V v.((((tt))
n
and hence
E
+1)
n
2 - v((()) - 1 Σ (Vi((t))) v((cE))
(1 E
+(1 PPD)E
Σ v((l))
1.1.1.1.1..6
Wp
E
fi ) - v
+ (1 PD)
g¹
1
v
f2())
1.
S
WD
max
1 4+
-
x11?
+ (1 - (1--DD)
Σ
n2
(30)
Let us consider the first term separately:
n
10
E
1111
IE
B/ +1 (1 - B)2 -
n1
71
8
1 n
|| Iw + 2$ 21
72
Using the result from Lemma E.5, we have
1
2 |
E
n2
B
[at+] -x²) x²) - -r((u - x²) + (wf -2/)11?
+
1
10 x1112 wr || - 212
pr
n
(45)
3
1
1 x² || (wp + +3) ||_ 20(l3
E
+ 4pp-
n
where in the last line we use the fact that pp S 1. It remains to substitute the above inequality in (30).
Lemma E.7. Let C E U(wp) for all i E [n] and ( E P(O). Then
| ++ w0! + 11]
< 1 2
2
wi| ||
+ 4
+ wp
E || e+1 - x 2=(13]
3
Pp
| - x" |3|
+ 4pp
1+
E
3
33

---

for all i E [n]. and
1 ===11111 B E || 2f wn
E - w
w01 + + (B) + 0 E
|| =11
+ 4pp
(1
pp
R |110"= - x01
B
Proof. From the definition of
24 1+1
we get
| 122+2
w +1
12]
E
Sw +1 + (1 - -)a w w/tt11]] (1 -3) || ==11²
Then, Lemma E.5 gives
++1 E [
w ++1
(1 - B [1(xx - x²) pp(wu - =x²)= + (w) 2 2/)11²]
+(1 3E
pr | - s²11
+ wp ||a - =011²]
(44)(46))(47))
(1
E
|| ||
2 E
||(x - x²) -p(pwt =²)1("]
3
+E pp
111 + wp
|| =11]]] |
(45)
(1
EE m|
z
3 |||241 10-1-x011
+
4p²
|| - x =1
B
+E
pp
w - =1'1 + wp ||0 - x²113]
EE ||ll
[11]]
+
3 + wp
E |1 10:1-=0010 =011"]]
-
pr
W x² |13]
+4pp
1 +
E
B
The second inequality proved almost in the same way. First,
E -1 wot11 11]
(1 - -3))3 -|0011-20117] ==1
and using Lemma E.5, we obtain
E
|| w 11 ||3]
I (1- _ ||| [1 =2) - pp(w' -x') + (w- - =01²² pp 1| - 20112 + 0 01|2tt1- 2z 201]]]
(44)
1
B E 10' =01²]
-/21/ [|(0041-000 x0)) pp(w" x²)) ||]
2
3
+E
pp
wt
x 112 0 | - =
(45)
1
E
1" zz [|
(1= + +0) E ||a2411 14:41-x000 206
4
E
100
x0 113]
+ pp | x² 191
B
1
3
E
w=
2113] 4 0) B || - 22
2
Pp
ww - 21]
+4pp
1
E
3
34

---

Theorem E.1. Let Assumptions 1.1. 1.2, 1.5 and 4.2 hold and suppose that the compressors Q E U(WD) satisfy Assumption 1.6, {C i=1 E PP()) and C; E ((wp) for all i E [n]. Let y > 0 be such that
S
L+ v 288
(1re + 1
L +
we PP
+
Itwpp
L3 +
wo(l+wapp)
max
1
upp
upp
Letting
Tp = 8 +
g n1 i=1
+1| "1/11=
w²
|| m0l
(=1
n 1
x²11
| x=11
+ p
+
n
where
2,,
17
4 4r
4
Brw BI max
p
32yL.
(
11
+
53
and p
PD'
apD
pp
327L3/
+
PP 33
48 48 y Lanax
(3 + pp), M3 ensures that
pr
npD
ΣΣ [ل[[E))|
400 =0
(TT
Proof. Lemma H.1 gives
E [5t+]]
S E [8y]
R [| [
1
L
E
| - =0|1²] -
+ 2 [100 V [(a)))1
27
2
(44)
E8 [60]
|| ||]
1
L
IE
||at - 2²11a]
27
2
1
++B
v(((+))
+
7
vi((''))
im
(4.2)
E [80)
|| [( |1*]
1
I.
E
| - 2²1
27 2
+yB
f((2g)
+ 4
E
|| - -z' 2=11a]
+ 2 [| - x111]]
EE
[80]
||
( ||
1 L
E
1+ - =010
27 2
+yB
g"
{(((t))
+ 2
Σ
E
||
+ [1uf - x² 11]) m='l"]]
1=1
1=1
+2
E
||
w '1'
+ E
|w' |w''=''1 + =1(])
Let ki, 2, 2 0 be some nen-negative numbers that we define later. Using Lemmas D.6, D.7, E.6 and E.7, we get
12
E |5++||
+ RE
g 1+1
fa(2 1+
+ T
||
w 111
i=1
n
+ yE
+ 1++
w
++1 112
+ pB
|| 100 11
2222
+ μB
w
++1
x y1 -
1=1
35

---

27
< <B - 2 | ||(]
1
L E
- -
+ BB
1
((((z
27
n
+ 2 1 Σ E |||25 -
-w=ll m=2ll"]
+ E
|| |uf - x² 12s)
iml
+ 1
E |||=* -w'1=" w²']""]
+ EE
| 1w==-+"p =1'1
+ Ki
WD wDL2mux
8
1 Σ
|uof - =11
+ 3
Σ w
|||0t1 -
+ 3(wp + 1),82E
127
+ +x(1= -PD)E
g'
)(
2=1
+1
19) (11-
E |||2 - "0'1"]] + 4
1
+ 0)
|| - =²1
3
IE
2
P. B
|u' - =01081
+ 4pp
11
E
(1-2)
B
1
w 11
1
E [|1o4t2 - -2
+ 1
IE
+ 4
+ (wp)
2
3
|uf - -1(13) =111))
P.. B
+ +ppp
1 +
EE
1=1
+ p(1 pP)
[
|||u
- x² 11]]]]
+ AE || 0+1 - 22 (113)
+ +p11 - pp)
E
| - z² 211
+ wpl || - 2²(1²]]
i=1
Taking == pn
7 and 1)
1722 3
we get 7 + +x(11 - pad) = k and 27 T2g + +1 - -8/2) = n,. which gives
E [[5+2] 1 + <E
(2
+ +n ||| || w 11]]
+ vE
+++
mn 11
+ pB
||
- x2t+111 + 1B
1
I ++1 - x 11
1
< E [6']
- 2E
V
L
E
|| - =0-1 + KB
g¹
vf((tt)
2
27
2
+ +
|| - 11?
+
2
1
n
E
|| - 205 [0]]
+ E
[|wo - -0-2= =]]][]] + 2 2y ||'00 x²' =01
n
+
?
wp 1
4pp,32
1
|wo - =0112
+ 335
Σ 1 m
a
PD
n
n
+ 3ww + 1),82R || - =0119]) )
[|a0t))=x11]]]
47 B
g
(4
(
1
0) E || | - [||2] + +pp
1
Pp B
E
|| 291²))
3
36

---

+
v
(1-22)
18
1 12
2
w
+4 (3)
1 + wp E ||lot1 1ast1-x+0 x² x²11]]
2
71
+ +4pP (1+
PP 18
x²' 112)
1+
IE
n2
+ +p(
((11 (1 --ppr -Pr.) )IE ||w0*
x² [1 + AE
|| - x²6 113))
+ a (1 - pp)E
n
211??
+ w |10tt3 - x2]1)]
We rearrange the terms to obtain
E [ 1
+ RE
+ n, ||| - w 11]]]
1=1
+ sE
||
1+1
111 1|
+ pl
x0+111 || -
+ 1E
1 1+1 - x 11 112
1=1
< B [60]] - E
1
E
||lattt - -==1(²] + +EE
g" 1 {((
27
2
||* w/l [10] + 1
33
3rw Lanax
+ 1
+
27132-
+
E
|| w
2
nPD
3/WD(wp + 1)33L22
16
+
max
+ p0 +
+
upp
8
B
( 1
||00411 - 00l1 -1 =21]]]
+ 4v
[wpr + kwWp
+1wPp
3
+ p(1 -pp) + + + 18PP
pP) )) E [|| |1o"" - 201
1+
8
+ [l( pp) + 2 + 4upp
1+ PP
+
4pwppp L2L npD
EE
/ - x² 1
3
We now consider the coefficient of the term all x, 2 0, we get
E
Using the inequality zy S
x² 22
for
p(1 - pp) + LB +
16PL
1
PP)
S p(1 - -pp) + 167L3
1+
PP
+
B
3
3
13
pp
$ p(1 - pp) + 32
1+
=p
for p- p0 32
1 +
pp 0z
With this choice of p, we obtain
E 1 + KE
+ +nE ||| ++1 - w y112
+ yE
++
w + ||
+ pE |1 - - 2111 + μB
1 e+1 - x 1 113
1=1
< E [89] - I
1 - 21) E || - 20|13] -
1 Σ vf((2()
+ KE
g'
2r
n
37

---

|| wLl w01]]] + +pE [| |u x² 211]]
+ nl
+2/13 + 3r B² [
1 n
v
2
E
n2 Σ
2
will?
RPD
+
3ywn(wp + 1),811 max
+ --3yyI
pp
16, LB
1 3
+
0
npD
pp
g2
8
+ 4v ( wp) + HwP
|| x' 1']
+ (u(L - pp)
PP)
4pwDppp3
L
12
+ ((pp-ppp--
2272's + 4upp
[1
+
E
3
npD
71
Next, taking v 4v B
GywDBLa uPD
gives
n V
E [5 + Kl
g
1+
+ +nE ||
w 1113]
i=1
+ wE
| c+1
u0 1
+ pB
|| 100 +1
21 + E
20
e+1 - x 11
iml
$
B [09]
- E
V [f
E
|| - 20113]
+ KB
g¹
1
f(((2
2
yy
2
n2
1 n
+ TnE
|| w01 + pE || |uu" - 2²11"]]
+ /E
Σ
|| |2
w
71
i=1
3/wD(wr + I2 + +327LiB
(1
pp
16
1
+
++
+ 0
uPD
PP
/32
B
3
+4
4443
GrWD max
#W + HwP
E ||
- 20-1()]
3
upD
+
[1( - pP) + 27/13 + +
GrWD 3 2max
pp
1 +
Pp
mpD
B
4/WDppB21. max
n
E
|
x. x011?
nPD
Let us consider the last bracket:
4(1 pp) + 22 + 4
44LL,
+
GywD3L2
max
Pp
1 Pp +
4yw
8
uPD
npd
16yp
24 max
16. 83
[1(1 - pr) + 2
npD
+ 2 max
4ywDpr.32 22
max
nPD
npD
< <1(1 - pp) + 167
1 PP
+
p
24yWDpPL2
(3 18+pr pr + 32)
B
npD
$ (1 - pp) + 327L2
[1 pp
48
T.2 MAX
(B + pr)
npD
38

---

for p= 104=3244 32
1
+
De /34
4 1. npp
+ PPPP For this choice, we get
pp
[[
+ RE
g 1+1
fz
+ +nE |||241 w0 11
vE
|
++1
+ 11?
+ pp
|1
- 119 + 1B
1
w
+
-11 112
n
n2
27
$ <B [6"]
E
[V((z')]1
L
|| + - =211²
+ KB
g"
Σ
n
V (+(
2
27
2
n
n Σ
+ 1
11 u²1 [|]
+ vIE
2/
w|ll
+ pl
|1 -20-0-11 x=111]]
+ tulE
| - 112
71
1=1
+
3ww + -1)3212
max
327
1
Dp
+
16 7/2 B
3 0)
npD
pp
fz2
G, +
+
wp
B
n&DD
+ 32
+
Pp
48 max
(B + pp)
E
|| - 20113]
g2
nPD
(31)
Let us simplify the last bracket.
I :
3wwD(wp + 1) L2
L
+ 32
+
Pp
+
16
+
nPD
Pp
g2
3
B
GY 3L
+
4
A
+ ww
B
T&D
+ 32
1
+
Pp
48ywDWpL3 max
(8 + pp)
Pp
B2
upD
3ywm(wp + +1182
24wwD
24mwDwp
48
487WDWPPP
L
uPD
npD
npD
npD
npD
16y 82
16
32
32nWPPP
3270
32
167
1670
+
+
+
L3..
Pp
82
pp
g²
(32)
We next consider the coefficients of B. 1,3
and 1
max First, for L.g. have
32>0
32ppp0
167
16-0
0
Pp
S 32
+
+
Pr
32
82
B
Pp
3
B2
32
0
Opp
$ 64y
pp
B
132
0
+
Opp
644
Pp
32
Next, the coefficient of L3 can be bounded as
167
167WP
32WWP
32PWPPP
1
Wp
PP
p
) g22
+
3 +
+
< 32%
+
1+
+
82
pp
8²
82
pp
B
Wp
WpPp
1
647
+
pp
B8
Wp
+ wppp
S 644
Pp
822
39

---

and for L we obtain
3ywp(up + +1
24
48 48yWDwPPP
+
+
npD
RPD
upp
npD
D
(wp
1).32
wpB
WPPP
< 727WD
+
npp
npn
upp
RPD
wpB
wppP
< 1447wD
+
uPD
upp
WD 1 + wppp)
1447
n
npp
(ur+1)) since
wal apD
Substituting these inequalities (31) and (32), we get
upD
RpD
[
1+ + RE
+
|||241
w
11
7
+1+111 111
|1:00 1110+11
xxt =1+] fB
1
11
+ pp
W
n
n2
E
[84]
E
V
ff(x')) ||3
L
||
- =211²²] + kB
1 n
vf((2
2
2y
2
n
1 12
n Σ
+ 17
||
ut [1"]
vIE
1/
will?
+ pl
||
x2113]
+ MI
|uo - 10
1=1
1447
(00
0
+ Opp
LB
wp
1 wrpp
L'a
Pp
g2
pp
B²
(WDWP3
(<np
WD(1 wppp)
1.2 max
E
x² -111tt-=0111)
npp
npp
By collecting all the terms w.r.t. E Lemma H.2, we obtain
| x0 1112]
using the step size from the theorem and
/ |
|
E +1 = E 11 + KI
g e+
+
+ nB - 111
- w
+ wE
2/ 1+1
w." +
+ pE
-
+ 1F
|
++1
x 11²
n
< E [5']
V
|| V f
|13]
+ RE
g¹
+ +y
||1a
wet 11?
2
1=1
1
1
+ w/
Σ
2f - will
+ pE
[| | - x² =0]1"]]
+ WE
wu x= 1|²
72
= E [+]]
E
[|]
2
It remains rearrange and sum the last inequality for t 0...., 1.
40

---

Corollary E.2. Let C E P(O) for all i E [n] (e.g. PermK), choose pp = 1/(wp + 1), = 1/(wp + 1) and
wDWppWw (WDRR + +1)
1/3
B = min
n
Then, in the view of Theorem E. the iteration complexity is
y
WDWPlWD + 12
1/3
Lmax + wD(WD
Imax + Vwplwp +1)(x) ))
Iimax +
n
n
Proof.
By Theorem E.1, up to a constant factor, the algorithm converges after
=
40
L +
+
1+
Opp
0pp
LA
+
WP
+
1+WPPP
L3
+
WDWp3
+
WD(1 + wppp)
L max
pp
g2
pp
32
no
Wp
1 wppp
WDWPB npD
wp(1 + wppp)
L
+
I.
I max
B2
pp
8²
npp
10
L
Wp
WDWPB
2wD npp
L +
+
L3
+
L
32
Pp
g2
npD
40
L
2 wpp(wp + +1)+
WDWP(WD + 1)3 2wp(wD + +1)
1 +
-2
+
B²
1,3 +
1.2
max
24
L2
D3
wDwp(wp + 1)8
wD(wD + 1) L + wp(wr + 1)
L+
L max +
iterations, where we use the choice of pp and PD- Using Lemma C.I, we have 12 L3 S L2 12xxx and hence
T < 24
1
WDWP(WD + 1)3
L + wD(WD + 1) L2 L2xxx wp(ww + 1)L33
8
L
V
B2
n
4
(1+
WDWDlWD + 11 2/3
max + wDlWD + L2 + wu(wpp + 1)L3
L+ v
1+
8
8T0
(eDuplWD+1] +11
1/3
wD(WD + +1) Lmmax Vwrlwp - 1)LiA
<
Timax
Tmmax
E
n
n
where we substitute our choice of B.
L
Corollary E.3. Let C be the PermK compressors and Q; be the independent (Assumption 1.6) RandK compressors, both with K = 8/n. Then, in the view of Corollary E.2, the iteration complexity
V0
112 Lmax + nLn))
L
and the total communication complexity is
|dmmxx
+ +ddix))
1/3
Proof. The choice of compressors and parameters ensures that Wp = wp = n (Lemma A.6). Thus, the iteration complexity is
T
(WDWp(WD + t11 1/3
Lmax + wD(WD +1)
Lmax + vwr(wp + 1)LA )1LAA) ))
O
Linax +
8
n
41

---

0 40
Lmax + 2/3 Lmax + Villmax + nuba))
4r0
11//3 Lmax + nLLa) nnta))
Since pp = pD 1/n and K - d/n, on average, the algorithm sends directions. Therefore, the total communication complexity
< 2d
coordinates in both
O d T n
(n2/3 Lmnx + nLa))= = ( 1/3 Limax ddia))
1T00
(
E.3
Jolyak-Eojjsieviin condition
E.3.1 Main Results
As with MARINA-P, we provide the analysis of M3 under the Polyak-Lojasiewiin condition.
Theorem E.8. Let Assumptions 1.1, 1.2, 1.5, 4.2 and D.9 be satisfied and suppose that the com- pressors 2 E U(WD) satisfy Assumption 1.6, {C] P(0) and C₁ E U(wp) for all [n]. Let > 0 be such that
7 :=min min
L+
1536
1+0pe
L
(we
1twppe 3
L3 +
[nwwe wD(L+wppp) npp
Linxx
PF
app
9
(33)
2p
2p
4p
Letting
2
T = 8t +
9
fi [(()))
+ w²1
1==
1
||
10
1=1
+ p 1|100*
2011"
|uf - 1²11
where
27
17 =
Ly
LyL3 + 2
128
(1
+ pe
and T
npD
pp
1287L3
(1 pr
pp
38
L
(3 + pp), M3 ensures that for each T >
upD
E
V S (1 -p)) 4o
Corollary E.9. Let C E P(O) for all E [n] (e.g. PermK), choose = 1/(wp + 1), PD = 1/(WD + +1) and
1/3
B min
n (Wwpp(WD +1)
Then, the view of Theorem E,8, Algorithm 2 ensures that IE [f(x*) fr] S after
(4((Dep(wD+tl) 1/3 pnipptii I.max /up(uptl))
O
max
wp 1WWD + +1, (Dwn((up11)
1/3
log go
12
iterations.
Corollary E.10. Let C; be the PermK compressors and Q¹ be the independent (Assumption 1.6) RandK compressors, both with K d/nn Then, in the view of Corollary E.9, the total communication complexity is
dLmax
+ dLA + log
n0
o
1/3 4
42

---

E.3.2 Proofs
Theorem E,8. Let Assumptions 1.I, 1.2, 1.5, 4.2 and D.9 be satisfied and suppose that the com-
pressors O E ((WD) satisfy Assumption 1.6, [c (O)) and C₁ E &U(p)) for all i E [n]] Let
7 >>0 0 be such that
7 min
++
1536
( Pp
1+0pr
L
(we 1twppe 8
L3 +
[wwwp wD(l+wppe) npp
app
p.c.
p.
8
(33)
2p
2p
4p
Letting
T = + 1i
g
V Si (21)
+
w²1l
1-
w0ll
i=1
1=1
a
+ p +p|lu* 100
x. x11
|wi - 1²11?
where
27 pD
11
8y 12
8-L3 0
+ B
128
(1
+
5t/
and T
hpD
pr
128yL33
1 +
pe
384 1.2
(3 + Pp), M3 ensures that for each T 2
33
AnD
E
V
S
Proof. Starting as in the proof of Theorem E.I, we have
E [8++1 +
RE
+ mB || w0 111
+ vE
| mn
11
+ pF
|||00t1
x [11] + TE
| - ,
1=1
SE [6y]]
Z
v f(x
1
E ||
2² 2011 +
-
v)((ott)
2
27
2
+ +
Σ
E ||
+
S/l1l - x² 11T)
1=1
+ +27
E ||=" - -w-l"" w0'13]
+ EE
|| w - =101 =0-133]
WD Umaxx
Apr:821E
Σ
|uf - 201??
+ 3 E
Σ || wfll
+ K
n2
1=1
- || =011
+ 3(wp + 1)
+ +x(1 - PD)E
g¹
f((2))
n1 i=1
+1
1
8
E
||
20 11'
+ 4
3 + 0
||a - =1|13]] + 4pp
1 Pp
E
|1 - x x0(1a]
2
B
(1-2
8 2
E
Σ
12
+
1
+ wp)
3
43

---

+ App
11
PP 3
E
| x0 ||
71
+ p(1 pp)
E
Iu'
- x²1 x0113] + AE
|| - x4 11²)
1
n
W 201??
+ wpF ||aett - x²') [11]]
+ +1 - pr)
n
27 and 17 8y which gives + x(1 - -PD) =
for some KC 17, P. 2 0. This time, we let
N (1 2 and 27 L + (7(1 0/2) 1 (1 4) PD
Hence
V fi 1-1 ) ||] + 1n [||241] - -0(
E | + kIE
+ +E
| 1+1 w 211
+ pB
|1100t1 +1 - -x +11 + +E
1
+2 - 222
S E [6y) - E
||*]
1
7
E || || - ==(](]]
2
2
12
+ (1
PD 2
E
|]
+ (1-
||| - w (17
4
+2 1 n2
+
E ||
w1|l"]]
+ I |||0]] - x² 111) + 27 2 11ot==''11
71 1=1
+ 27
WD I
4p
n Σ
n
|w z²'1?²
+ +
Σ
n
| w3ll
PD
12
||a041 -=-1=]=+1]]]] ))
+ +3(wp + 1),3²T
+
L B
4
+
E
|100t1 x² |||
+ 4pp
(1+ PP
++
E Ilw't - x²' 21()
B
3
B
+ 1
(1-
2
B
E
Σ
2
w|
+ 4
3 + up
E
||| zzt ||
n
R
+ +ppp
1+
PP B
E
|
72 1=1
+ (1 - (1-Pp)
|||u* - "13]
+ AE
|| - 2- =1(3]
+T T (1 pp)E
|uf- - 201
+ wpp [|act]- - 20'1 117)
Rearranging the terms
88 184+1 17
+ RE
+ TE |||241 -11
1=1
+ >/
|| |a4t1
m !|?
+ pe || xe - 121 + TE
n
< E [8
- 7E
2 |||att1 - 2-117]
L
-
27
44

---

27
+
(1
PD
E
1
V
(=(
+
1
8 4
B
|| - -1===10113
2
n
8
Grwpp 3 L
1 n
| mel??
27 17
E
DpD
n1 i=1
Grwn(wp 1)32 max
+
p0 +
327LB
1
+
0
+ 41 (3)
(3+ + wp) + (ww)
[|1ott1 22 2211²]
apD
B
3
+ [1 (1--p)) pp) + 27 +
32pL
1+
Pp
|110" - x²'18]
8
B
+ +2yL33+ + 4upp [(1 - (p(1pp)
11
PP
SywDp L
| 2² $12)
B
up
n
Considering the coefficient of E
|| -x'
[?]
and using the inequality my I
+2 2
for all x, y 2 0.
we get
p(1 pp1ppp)- + 2 +
L2
1+
Pp) 3
S p(1 - ((pp-p))=a + 32
1+
PP
Pp
B
3
B2
1 Pp
$ p(1 - -pp) + +4
B²
= p (1 PP
where we define p = 12
(1 pr
+
pp
Substituting this choice of p, we obtain
[
+ RE
(2 3
+ tnB |||2 w 11
n
vE
1
2441
+
pB
||ro0t1
+ T
12 |uf +1 - 22 11
n
< S [89]
\ ||²]
(
T
|||at1 10:1-==' -2'11"]
2
27
2
22
+ (1
PD E
g¹
1 Σ {((+))
+1
11- 3 E
||1a* w0 11'
n
4
+ 1 (1 - PP)
E Iuo-
=1]]]] + (~ (=(1-
(1-1
8
+
+2
GrwD B² L
E
2|
20
2
2
npD
(yw + 1) max
Pp
324T.B
1 (1
+ 12
++
+
npD
pp
g2
B
+ 4v
B twp
1
+ TWP
E
|||0011 - x 20113]]
+ 7(1 (T(1-P)) pP) + 2 + 4upp 11
Pp) B
Bywppr.B212 max
E
1
- =011
npD
n1
Similarly, taking
8-L2 +
B apD
gives v/ (1- o + 2 +
= //
up
so
11
E 1 + KE
ge+l (2 11 )
+ +n ||
- -::--00--0 111
n i=1
45

---

+ PE
m |1
+ pb
- + =
1
n
S E [89]
E
{(>)'> |||}
1
E
|| 1 - 2² 2-117]
2
24
2
n
|]
+ (1
PD
E
g" n
Σ
(+f(
+1
1
|||2 w0
2
4
+ 1 (1
PP
E |lw0
11]
+ (1-
8
E
Σ
||
will
2
71
6YWD (wp + 1)82LI mux
1 pp
pp)
3
(
1 + :
+
+ 1287
+
0 +
upn
32
B
88y1
24 24 max
E. 2|lo-t| -o----o01 10' =1]
+4 4
wp
+ TwP
aPD
87L3
24 BI
Pp
+
T(1 - PP) + 27-3 + 4
pp
1
npD
8y +
uuf - =0(1?)
E
NPD
Considering the last bracket, we have
7(1 pp)) + 2 +4
87133
+
24 max
Pp
1+
Pp
8pwppp L
B
apD
apD nip
3
= =r(1-pp) pp) + 2
+
32
32np2,
3
max
p 2 max
3
g2
nip
8yWDpp L
+
app
p
BywnppLemas (8+ pp pp + 82)
S (p))-p))-ap) + 3
1
Pp
+
3
32
uPD
ST(1 - (pp) + +
[+ Pp
192 192 max (3+pp)
Ypp
=T (1- Pp
2
for r = 12
pp
+ pp
(2)
+
381mwD Liox apn
(B + +p)). Then
12
E 18 + KE
+ +n || || w +11]
n 1m1
1+1 m [1]
+ pE |1 e1 - - 111 + -E
| ++ - -
+ vE
n
1=1
< E [69] - 2 ZE
( [|'
1
E || 122 - 20|1"]
2% - 2
12
+ (1
PD
E
g¹
n
+1
1
8
||
m w1'
2
4
1=1
+
1
PP)
2
E
|| |u'
- $112
+ レ
4
7
w1
46

---

+
(1
Pp
E
Rof 2²11
2
T
GrwD(ur + 1),32I
Lmax
(1 (-+ + Pp
32yL (1
+
128
+
B 000)
RPD
Pp
82
B
87L3
24twnBLma
4
+ wp
3
npD
384 L max
128
PP f2
(B+ (p)
- x211"] (34)
npD
where the last bracket can be bounded as
I GyaD(wp + 1),3 L max
PP
L
(1
+ 128
+
0 +
+
B²
B
3
+ 4
L
24
+ wp
+
128
1
+
Pp
B
mpn
3
Pp
g2
384 max
+
(3 + pp)
RPD
SywD(Wp + 1)3²
D
384hWDWP
(8 + (0+p)) Lnax
WP
+
upp
TPD
3
+
32y
+ Wp
+ 128
1
Pr
L3
B
3
PP
B2
+
128y
PP
0 +
32y
+
LB
PP
8
B
6YWD + 1)
967WD
96
384hwDwpB
3847WDWPPP
npn
npn
npn
npp
npn
32y
32wwp
128Twp
128ywppp
1
B
pr
B2
12870
128ypp0
32n
3270
+
+
T
Pp
g2
82
(35)
We next consider the coefficients of L. L3 and L
First, for L have
128~0
128ypr0
327
32-0
Pp
P2p
+
< 1287
+
+
+
Pp
82
82
3
PP
B
32
B2
0pp
1
< 256
+
+
Pp
32
B2
1 1 Opp
256y
pp
8
Next, the coefficient of L3 can be bounded as
327
32
128
128
1 Wp
Pp
1
))
82
Pp
+
g2
< 1287
32 +
Pp
3
+
B2
Wp
WpPP
< 256y
PP
32
Wp
1 WPPP
S 256y
Pp
g2
and for L obtain
(wp + 1)8²
96-WD upn
96YWDWP3
3847WDWP$
3847wpwPPP
Tpp
TPp
uPD
upn
47

---

(pp 1)82
1
wp3
wppp DD
384
nPpD
npD
up
1
wp3
wPpP
768TWD
+
nPD
npD
nPD
wDwp3
WD (1 wPPP)
768y
npp
upp
since
(wp+-))
+
= ApD
Substituting these inequalities to (34) and (35), we get
upD
upD
n
E 18++1 11
+ <I
+ +nBBB
||| -wo 11
n
i=1
n
+ vE
c+1
m 11
+ pp
|1
11
+rE
W ++ - - 2222
< E [8']
2 E
(1**))
||"]
1
7
E
|| - -='1(9]
24
2
27
+ (1
PD 2
E
gt n
a
Vi((+))
+
1
1
8
||
w $12)
4
+ 1
PP
w'
x² $13] + 1
3
n
1
w
11
2
4
72
n
+ (1
Pp 2
| - 2211?
E
12
(6--
0
1 + Opp
wp
1 wppp
+ 7687
13
+
LAA
pr
B2
Pp
B2
+
(WDWD/
wD + wppp)
I Iiaax
E
[1100t1- 22'1 112
npp
npp
By collecting all the terms w.r.t. E | - r0l rd|1²]]
using the step size from the theorem and
Lemma H.2, we obtain
E y +1 = E [6++]]
+ KE
1+
1
+1
mE
|| +1 1|
n 1=1
+ vE
| +++
w 11
+ pB
|| 100 -
222
+ +rE
|
0+1 111
< E [54]
(1r ||| +x<(1 (1-
R
g¹ 1
2
11
(1
9
E
|| 2
w0]l3]] + (1
Pp
E
|lu
x² $113]
+V
1
E
Σ
12 wfll?
+
1
Pp
E
uoo - 2-
2
i=1
im1
48

---

Lastly, Assumption D.9 gives
E
[1]t1]
E
kE
9
fz (2 (
+ +nE - 2
im1
+ M/
++1
= + 11
+ p1E
-
- -x
1=1
+T
w ++ x + 11
1=1
As9.3.9.333) I
1
(1 - 7/4) E [80] + (1 - 7144 E
g
i=1
+n - -44)
|| - w11
+ - 1-44) E
|| | w
+p (1 (011-4)) IE ||w0* x' 112] + -- EE
x²'
(1-7/4 E [w¹]
It remains to apply the last inequality iteratively to finish the proof.
Corollary E.9. Let C E P(0) for all i E [n]] (e.g. PermK), choose pp 1/(wp + 1), PD 1/(WD + 1) and
{ (upuptoo + +1)
1/3
B = min
n
.11
Then, in the view of Theorem E,8, Algorithm 2 ensures that E [f(x*) f*] S after
(+ (HDDpp((u)t))) 1/8 +. upllptii Tmmax + (wppup+))t)
(wnm((u+1)) 1/3
max
wp + 1,WD +
log
iterations.
Proof.
Note that T f(x") ft. In view of condition (33) from Theorem E.8, the step size
satisfies 7 θ min
L+
1 0pr
L3
Wp
1 wppp
L3 +
WDWWB
wD(1 wrpr) upn
L
pp
pp
82
npp
PP PD B
4p }).
2p¹² 2μ²'
Therefore, since 0 0, the algorithm converges after
22 pp
1+2pPp
1.3
up"pp up(ltuppp) uPD
== max
62
log go
#
pr PD
iterations.
Using the choice of pp and PD. we have
Lt d + +33+)+)))+r++tt)) (npiwp Dwpd unlup L
T = 0 max
wp + 1,WD 1, 1
log 2o
49

---

Due to Lemma C.I, we get
L+ [+/ ( "p(-ip-1)sp "p(wp=1))
= max
wp + 1, + 1, log
Using the choice of B, we obtain result the theorem.
Corollary E.10. Let C be the PermK compressors and Q be the independent (Assumption 1.6)
RandK compressors, both with K = d/n. Then, in the view of Corollary E.9, the total communication complexity is
o (( (almex n1/3
dLA + d) log
+
Proof. The choice of compressors and parameters ensures that wp Thus, the iteration complexity is
--1 (Lemma A.6).
(maxx
(1+ 2/33 + n212) Lmax + nLA
T/0
o
max
n. n. n 2/3
log
1
E
2/3 Lmax + nLA
40
O max
n
log
Since = PD = 1/n and K = d/n, on average, the algorithm sends S 2d/n coordinates in both directions. Therefore, the total communication complexity
2/3 Lmax + ALA )
yo
T.max + d
yo
0
max
log
O
max
n473
d log
1
E
11
50

---

10
10a
109
109
[[0((x)))]
10-1
workers
M1le warkers
(d of 100)
M316 (6 workors 1000
M3 werters 1000)
M1 (f wonkara 12001
CORE ofworerss 16)
CORE (dh of workerss 101
CORE 1# - 1001
CORE workers 1991
100000 200000 300000 R00000 500000
100000 200000 300000 400000 500000
#bits (s-to-w)
#bits (w-to-s)
Figure 2: Experiments on the quadratic optimization problem from Section F.1. We plot the norm of the gradient w.r.t. of coordinates sent from the server (s-to-w) and from the workers (w-to-s).
10
liG*)All
10
MARINA-P
MARINA
EF21-P DOGD
EF21-P DOGD
GD
GD
M3
CORE
CORE
10 0.0
0.5
1.5
2.0
10
2.0
#bits / n (s-to-w) 1e7
#bits / (w-to-s)
1e7
Figure 3: Experiments on the autoencoder task from Section F22 We plot the norm of the gradient w.r.t. of coordinates sent from the server (s-to-w) and from the workers (w-to-s).
F
Experiments
The experiments were prepared in Python. The distributed environment emulated on a machine with Intel(R) Xeon(R) Gold 6226R CPU @ 2.90GHz and 64 cores.
F1 Experiments with M3 on quadratic optimization tasks
We consider dloe-to-homogenenee
quadratic optimization problem with A, = (1 + [. where ~ (0, 0.01) for i E [n], and d 1000. We run two algorithms from Table 1, and CORE, and check whether theory matches practice. In M3, we use PermK followed by the natural compressor Cua (Horváth et al., 2022) (composition two unbiased compressors) on the server's side, and RandK followed by Cnat the workers' side. We use K [d/n] {1, 10, 100} for n {1000, 100, 10). In CORE, the number of communicated coordinates is set to 10. We run each experiment times with different seeds and plot the average to reduce the noise factor. Only the step size is fine-tuned for each algorithm.
The results are presented in Figure 2. As expected, CORE does not change its behavior as the number of workers increases from 10 100; this expected since CORE does not depend on n. At the same time, M3 does improve with which supports our findings from Theorem 5.
F.2 Experiments with an autoencoder and MNIST
We now compare MARINA-P, M3, CORE, EF21-P DCGD, and GD non-convex autoencoder problem. We train it on the MNIST dataset (LeCun et al., 2010) with objective function f(D, E) == Σ" -
DEE;
2 + \ DDE - I| where D I xd2 E E dd b, E Ød are samples,
51

---

d1 = 784 is the number of features, d2 16 is the size of the encoding space, À = 0.001 is regularizer, and m 60 000 the number of samples. The dimension of the problem is d 25 088. We randomly split the dataset among followed by the natural compressor Cua on the server's side. On the workers' side, uses RandK and Cnat- For EF21-P DCGD, we take RandK with Cuat both the workers' and server's s sides. In each case, K d//nJ = 250. For CORE, we set the number communicated coordinates to 100. As in previous experiments, only fine-tune the step size, repeat each experiment 5 times, and plot the average results.
100 workers. For MARINA-P and M3, we take Perm
The results are presented in Figure 3. All methods with bidirectional compression: M3, CORE, and EF21-P + DCGD, converge much faster than GD. MARINA-P converges fastest only in the first plot. This is expected since it compresses only from the server to the workers. M3, CORE, and EF21-P + DCGD have similar convergence rates both metrics, with M3 performing better in the low accuracy regime.
F.3 Extra experiments with quadratic optimization tasks
The aim of this of experiments empirically test results under Assumption 4.2. We consider the problem of quadratic minimization with varying level of heterogeneity between the functions stored on the workers. The goal is minimize the squared norm of the gradient of Σ fú, where the functions fi are of form
f1(x) - 1 -55 A bf.x.
Here, A, are d x d matrices generated following the procedure in Algorithm and b, denotes standard normal vector in RR. The constants LA and LB from Assumption 4.2 (in this case, by Theorem 4.8 L = /2 maxig(ni ||A; - A and LB = parameters 1; and of. In particular, for of O, all workers hold the same matrix Ag, and hence in this case LA 0.
(A,l)) are controlled by
We compare the following algorithms:
1. MARINA-P with PermK compressors,
2. MARINA-P with RandK compressors,
3. MARINA-P with SameRandK compressor,
4. EF21-P with TopK compressor,
5. GD.
In all compressed methods, set K d/n and use p k///ain MARINA-P.
The step sizes are tuned from 2 E Z multiples of the values predicted by the theory (indicated by x1, x2... in the plots). We fix d = 300 and generate optimization tasks with n E {10, 100, 900). The results are presented Figures 4,
The empirical results align well with the theory. Among the algorithms tested, MARINA-P with PermK compressor exhibits the best performance, while MARINA-P with SameRandK converges the slowest and comparable to GD. MARINA-P with RandK compressor and EF21-P achieve performance levels somewhere in between. Notably, the differences between the runs of MARINA-P with different compressors become more pronounced as the value of n increases. As anticipated, the performance of MARINA-P with RandK and PermK compressors improves with an increase in the number of workers, while the performance of EF21-P does not follow the same behaviour. Specifically, for 10, EF21-P outperforms MARINA-P with Rand compressor, but this pattern reverses for both 100 and 1000.
52

---

Algorithm 3 Heterogeneous quadratic problem generation
1: Parameters: 0o: "0...., 14 E + Co . 04
Rgo-
2: Let
2
1
X
-1
IR x00
4
0
-1
2
3: for k o..... do
4: Generate & ~ (0, , n [-00, vol for i E [n]
5: for = O..... do
6: Set A KJ (ir + 5. X for E [n]
7: Sample bed ~ (0, Ta) for i E [n]]
8: end for
9: Output: matrices A vectors bid i E [m]. Kr, E [4].
end for
Li-0. -10, 2-16-6-30 6-330
2-3 ---30A 4-333
G- E -330E CHO0E
C2 SCCRRA d-333
12--
4
1000 44530
13 (1-30
13 13000000 LE Ae000
12-
Figure 4: Experiments on the quadratic optimization problem from Section F.3 with = 10 for 1 E (0, 1, 10, 100} and T22 E (100, 1000, 10000, 100000).
53

---

SE -200 PHICC 9-269
Si B. LC-3003 FRESS
5p SE LOCERS CHOOO,
10/
Humber SHt-e
Number
Humber SHRWl)
10
10m
230008 medte
1--288 LOCOD 2H-200 9-333
10
Sunber oi (atbenn
Figure 5: Experiments on the quadratic optimization problem from Section F33 with n 100 for L3 E {0, 1, 10, 100} and L E {100, 1000, 10000, 100000}.
SE- Dj +300
G. CE-3003 PHO0O
CF U -3000
U- Cg LOCERS
of
C0-AA PHERO
36-1
23 CC-
Namberr of
Number torsiin
sumber D (H
Namberr Caiterr
Figure 6: Experiments on the quadratic optimization problem from Section F.3 with n 900 for 23, E (0, 1, 10, 100} and L2, E {100, 1000, 10000, 1000003.
54

---

G Proof of the Lower Bounds
G.1 The "difficult" function from the nonconvex world
In our lower bound, we use the function from Carmon et al. (2020); Arjevani et al. (2022). For any T N, let
Fr(x) = - -V()) +
((=)<-))*(
(36)
where
0, exp
x S 1/2,
and x(x) vc vef { er dt.
(x)
(2p-
2 1/2,
Carmon et al. (2020); Arjevani et (2022) also proved the following properties of the function:
Lemma G.1 (Carmon et al. (2020); Arjevani et al. (2022)). The function For satisfies:
1. Fr inr Fr(x) s T,,, where A 12.
2. The function FT is 11-mmooth, where 4 152.
3. For all x E RT, [ Yoo: where You 23.
4. For all x E R prog V Fr (z)) - prog( (x) +
5. For all RT, if prog x) then || (z)1 >
where prog(x)) = max (i 2 0 x; + 0}
(xo = 1)
The function is standard function that is used to establish lower bounds in the nonconvex world (Carmon et al., 2020; Arjevani et al., 2022; Lu and De Sa, 2021; Tyurin and Richtárik, 2023c).
G.2 Theorems
Our lower bound applies to the family of methods with the following structure:
Protocol Protocol
1: Input: functions fi,..., fn E F, algorithm A, probability
2: for == O...., do do
point: =² (ot gf. ... Ih. 9hh 4: Server aggregates all available information: sf (gl. ... .......................... .
3: Server calculates
5: Server sends sparsified vectors क the workers, where
|3 = [st] nh.
and wł., is random variable such that P (vt, + 00) for all j E [d"] and for all i E [n]. We define d' = dim(dom(f1), and Fl means the jth coordinate.
6: Workers aggregate all available local information and calculate gradients: g k+l
I (s.....,5?)
(L) has access to the gradient oracle of and can call many times as it wants according
to the rules (37) and (38))
7: Workers send k+1 to the server
8: end for
We consider the following standard classes of functions and algorithms:
Definition G.2. Let the function ʃ Ied
R be differentiable, L-smooth (i.e., [VV](x)VVJ()) - v S T. || yl for v, TRd), and f(0) inf ZeRd f(x) S 80. We denote the family of functions that satisfy these properties by Fs0...
55

---

Definition G.3. Consider Protocol 4. A sequence of tuples of mappings A
{(B), B 2,....., B L
k= ] is zero-respecting algorithm, if.
1. B R x ... x Ed R2d for all k 2 1, and Bi E IRd.
2. B Rd R Rd for all & 2 1, and B2, E R for all i [n]
nxk & times
3. T. Rdd
x Rd Rd for all k 2 0 and for all i E [n]-
1++1 times
4. supp (x*) S U U supp (o!) supp (s+)
S U - supp (o))
For all gk+1 ak+1 such that
supp (o C U
supp
j=U
supp (g
C
supp
8 U supp (U(p()))((
(37)
j=0
supp (it
c
supp
supp supp(V Supp((V. Uupp
==0
we have
supp (o. s U supp (oltt),
(38)
for all ls E No and for all e [n], where supp(x) = {i E [d] x + 0}.
We denote the set of all algorithms that satisfy these properties by Az.
The first three properties define the domains of the mapping. The last property is standard assumption for zero-respectie sero-respectin algorithm. Assumption (38) allows the mappings L to calculate gradients.
Assume that the sets ( Ank jeld" ...., .h Jed))) are mutually independent (the variables within one set can be dependent). Let p >> 0, L 0,n 2 2 be any numbers such that ēs < L8 Then, for any algorithm A An, there exists a function f E F80. and functions fi..... fn. such that
Theorem G.4. Consider Protocol
== - fr and E V
for all
1: < c L80
The quantities è and è are universal constants.
Proof. The proof conceptually the same as in Arjevani et al. (2022); Lu and De Sa (2021); Huang et al. (2022); Fang et al. (2018); Carmon et al. (2020); Tyurin and Richtárik (2023c), We fix À > 0, and consider the following function f : T + R:
LXa Fr
f(x)
4
One can show (Arjevani et al., Theoorm 1] that f Fs0
8
(39)
LA
56

---

Next, we define
F((x) (1)(((1)) + E EesjST and (j-1) mod n=0 (V(- ((=l)-)))((=}))) 2siisT and (j-1) mod n=i-1 (M(-lal)-i)\(((c]) (((=))-)))((1)))))
i=1
i>
and
nLA² f((x)
4 F;
The idea is that we take the first block from (36) to the first worker, the second block to the second worker, .... (n + 1)th block to the first worker, and so on. Then, one can show that
Σ =((x)=((0))
Using Lemma G.I, we obtain
2² 1
L 1
[Vf(2)]
VFT
1 1(prog(x) T].
(40)
The functions fi zero-chain (Arjevani et al. 2022): all E ifog(()))
and (j mod n)
1 i, then prog( V (x()) J + 1, and for all E [n], if prog(z) = j and (j mod n) + +1+ * i, then prog( V fz))) zero-respecting algorithms:
Using the zero-chain property and the f'at that consider the family of
1. The first non-zero coordinate can be discovered only by the first worker.
2. Assume that maxi=1 max prog 5 = 1. An algorithm can discover one new non-zero coordinate in the (j + 1)th position only if the (j mod 1)th worker gets non-zero jth coordinate from the server. This is by the construction of the functions fr. Note that for 2 2, one worker cannot discover consecutive coordinates.
Let us define
II the jth iteration, the coordinate with index p = max máx prog gf is not zeroed out in Line 5
&
j=1 ==1
of Protocol 4 to the worker with index (p mod + 1) AND T 12121 (p -p=0tt
0).
Then, have
(prog(=*) 2 T) P ΣE2T-1
Assume that Gj is the o-algebra generated by all randomness up to the jth iteration (inclusive). Then, é is mmmesuurable,, and, by the construction of Line 5 of Protocol 4, IP (gi+1 = < where we also use the assumption of the theorem that the sets of random variables are mutually independent. Using the standard approach with the Chernoff method (Arjevani et al., 2022; Lu and De Sa, 2021; Huang et al., 2022), one can show that
P
Σ 1=0
e 2 T T
sp
for all
T 1 - log
b <
p
2p
and p E (0,1). Therefore, we get
P (prog (x ))>) T)
(41)
57

---

for all
T- log
k 5
2p
Using (40), we have
22>x
E
V > 2&P (|V5((+))1 >20) 25) 2 2cP
1 (prog(2) < 2 2x)
Let us take À 22eh, Then
1 [prog(r) < 2 2g = 2xIP (prog(a:) < <)
| 2&P
(42)
72
From (41) with p 2. get
|
2&P (x) <) 2
(43)
for all
T 1 log 2
2p
From (39), one can conclude that
L
T
2a1 A
By the theorem's 's assumption, L8 2 č. One can choose universal constant such that (42) holds for
L8
k: k = -
Ep
where ④ hides only a universal constant.
G.3 Compressed communication with independent compressors
Protocol 5 is exactly the same Protocol except for Line and describes the family of methods that send compressed vectors from the server to the workers.
Protocol 5 Protocol with Compressors
1: Input: functions fi,... fn E F, algorithm A, compressors CI,... Cn
2: for == o...., oc do
3: Server calculates new point: x* = Cot..... ......,......................... 91 9h)
4: Server aggregates all available information: sy (g (e.......... gf.
Ih
ghi
5: Server sends compressed vectors 5 (xf)) to the workers
6: Workers aggregate all available local information and calculate gradients: gf
I. (sP....,
(Lă has access to the gradient oracle of and can call it many times as it wants according
to the rules (37) and (38))
k+1 7: Workers send 0; to the server
8: end for
Theorem G.5. Consider Protocol 5. Let w 2 0, O,L,8 0, 2 2 be any numbers such that
L88 Then for any algorithm A E An, there exists a function f E F L, functions Ji,-..; In such that f Ei Sú, and i..dd compressors Cn U(w) such that [V >
for all
k < (w + 1)
The quantities ē and è are universal constants.
58

---

Proof. We can use the result of Theorem G.4. It is sufficient to construct an appropriate compressor. Let us define p == 1/w+1. We define the following compressor.
P Di 0,
jES S, E
[C()),
S
where S a random subset of [7] and each element from [T] appears with probability p independently. Then, C is unbiased:
Es [[[(())]]] = Iz
VjER"
and
7
aT = = 1=1
aT - j=1
Es [|((=))]]= = Es Σ
1 J S
p
PÚES)
p²
p²
r
(w+
+ 1) |0:11
Therefore, we get E U(w). Let C, be i.i.d. instantiations of C for all i E [n]. Since C a sparsifier as in Line 5 of Protocol
Theorem G.4 with p = 1/w+1 finish the proof.
L
59

---

H Useful Identities and Inequalities
For all 2, y, 21.... Im
12 and a E (0, 1], we have:
|
+ y/
I (1 + 8) || 2 + +1++ s s l1a11
(44)
m
m
Σ 21
S m
Σ a 2
(45)
1=1
(1 a)
1
S
(46)
2
2'
2
(1 - a)
1
(47)
Variance decomposition: For any random vector X E Ie and any non-random vector E R we
have
||- - =l2 = -Ixxx
E + ||[[] cll?
(48)
Tower property: For any random variables X and Y, we have
E L X Y] E [X]
(49)
Jensen's inequality: If f is a convex function and X is random variable, then
[f((X) 2 f (x]).
(50)
Lemma H.1 (Lemma 2 of Li et al. (2021)). Suppose that function J is L-smooth and let x²+1 xf 79. Then for any g¹ E TRdd and 7 >> 0, we have
f(x $f(x') - 7 [f(''))
L
r+ - ||0411-2""1
=2²1]++ 7 21100 -Vf(=')
27
2
Lemma H.2 (Lemma 5 of Richtárik al. (2021)). Let a, b > 0. 1ʃ0 575
Ta-b then uy² +by S
1
Moreover, the bound is tight up the factor of 2 since 1 min {
1 11
Votb
Va bj Vatb
60

---

I
Notation
Algorithms
number of worfers/hodesslleensveeiieess
stepsize
Ci
Ch
Server-to-workers (primal) compressors
2
1y.... 2
Workers-to-see to-sererr (dual) compressors
WP, wp
Parameters of werker-to-workers (primal) and workers-to-server (dual) compressors
Correlated compressors parameter (Definition A.3)
8
Momentum parameter (see Algorithm 2)
Definitions
U(w)
The family unbiased compressors with parameter w (Definition 1.4)
P(O)
The family of correlated compressors with parameter 0 (Definition A.3) Smoothness parameter of f (Assumption 1.1)
L
Li
Smoothness parameter of fa (Assumption 1.5)
La, LB
Parameters from Assumption 4.2
Notation
[+] = {1, k} for any positive integer k
Ex [ expectation conditioned on the first t iterations
8' f(x²) f" 2 1
" >
LT. Lmax = maxie[s]
w² = 1/n > w/
g = 1/n Ei=1 Di
1/1 Σ 2
Table 2: Frequently used notation.
61

---

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: Sections 3, 4, and 5
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.6 and 5.1
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]
62

---

Justification:
The assumptions and the proofs are in Section 1.1 in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should 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 F
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 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?
63

---

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

---

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

---

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 intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: Section F
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
66

---

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


Reviews:
[{"review_id": "wvIY3AWcuj", "reviewer": "Reviewer_1G9G", "summary": "This paper deals with the downlink (server-to-client) communication cost in federated learning (FL). The main motivation of the paper is to provide a theoretical analysis of the total communication cost with downlink compression. This is achieved considering unbiased or a certain class of biased lossy compression algorithms at the server. First, the authors present an impossibility result (i.e., a converse theorem), showing that faster than certain rate is not possible if the server employs an unbiased compressor (or biased compressor as specified in the paper). Then, they proposed a downlink compression method called MARINA-P, which achieves better iteration than those in the literature. This method, basically, transmits an uncompressed model with a small probability p to all the clients, while the compressed model update is transmitted otherwise. The main twist in the proposed scheme is to transmit different compressed versions to the clients, rather than sending the same compression. In particular, an orthogonal sparse subset of the parameters are sent to each client, so that they together can recover all the parameters. This way, each parameter is considered at least by one of the workers.  Here, the compressed versions transmitted to the users become correlated. The authors show that this correlated compression approach achieves the best convergence rate. Finally, they extend this framework by combining downlink compression with uplink compression using MARINA together with a momentum step.", "questions": "- While the authors have covered most of the relevant literature, as far as I'm aware, one missing paper that I am aware of is the following:\n\nM. Mohammadi Amiri, D. Gündüz, S. R. Kulkarni, and H. V. Poor, \"Federated Learning With Quantized Global Model Updates\" arXiv preprint arXiv:2006.10672, Jun 2020. \n\nHere, not only the authors consider downlink communication, but they actually transmit different updates to different clients. Instead of compressing the difference with rest to the previous global model, here the authors compress the difference with respect to the model updated by the client. This way the gap to the new global model is potentially lower. I can't say how the convergence rates compare, but I would like the authors to comment on the pros/cons of this approach compared to their own. \n\n- How limiting is the assumption that the calls to the compressor are independent? There are some works in the literature that consider time-correlated sparsification, and show improved results (which also makes sense as the sparsity pattern should not change drastically from one iteration to the next). Please provide some comments in the paper if this may be a significant limitation on the practical performance of the considered class of compressors.", "limitations": "As mentioned above: \n- lack of numerical comparisons,\n- one missing reference", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "The paper looks at an important yet under explored aspect of communication in FL. The authors propose a novel server-to-client compression method, and provide upper and lower bounds on the convergence rate under various assumptions. Overall, the assumptions seem reasonable, and are shown to be satisfied by common compressors such as randK (and the introduced permK). \n\nThe proposed compressor is rather simple, but the observation that the best convergence rate is achieved by this particular correlated compression method is interesting.", "weaknesses": "I would say that the lack of any empirical results is the main weakness of the paper. While it is interesting to obtain the theoretical convergence guarantees, one also wonders how these three different compression schemes would perform in practice (for scenarios that satisfy the assumptions, as well as those that do not). \n\nAlso, only sparsification type compression methods are considered. What about quantization? Can the arguments be easily extended to the case with quantization?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback and for recognizing the strengths of our work. We will now address each of your comments in detail.\n\n__Weaknesses__\n\n> The lack of any empirical results is the main weakness of the paper.\n\nWe thank the reviewer for the suggestion. We would like to highlight that our empirical results are presented in Section F.\n\nOur primary focus in this paper was on the theoretical aspects, rather than extensive experimental validation, which is why we placed the empirical section in the appendix. The experiments included are intended to demonstrate that our theoretical results closely align with practical observations, highlighting the robustness of our theoretical framework. In the camera-ready version, having an extra page, we are happy to include the highlights of experiments in the main part of the paper.\n\n> Only sparsification type compression methods are considered. What about quantization? Can the arguments be easily extended to the case with quantization?\n\nYes, of course, our theory already covers quantization. Our general theoretical results (Theorems D.1, D.2, E.1) rely on Definition 1.4, which encompasses a wide range of compression operators. These operators include not only sparsification, but also, for example, natural compression and natural dithering [1], general exponential dithering (a generalization of ternary quantization), general unbiased rounding, and unbiased exponential rounding [2]. Various combinations of these compression methods are also covered. Naturally, our theory also applies to quantization. More information can be found in the references in Section 1.1 of the paper.\n\nIn some theoretical results, we specialize in sparsification to highlight the superiority of permutation compressors. However, the aforementioned theorems demonstrate that our approach is applicable to a variety of other compression schemes as well (all compression techniques satisfying Definition 1.4). \n\nWe agree that we can clarify this point further in the paper and will make the necessary revisions to ensure this.\n\n[1] Horvath, S., Ho, C. Y., Horvath, L., Sahu, A. N., Canini, M., & Richtárik, P. (2022, September). Natural compression for distributed deep learning. In Mathematical and Scientific Machine Learning (pp. 129-141). PMLR.\n\n[2] Beznosikov, A., Horváth, S., Richtárik, P., & Safaryan, M. (2023). On biased compression for distributed learning. Journal of Machine Learning Research, 24(276), 1-50.\n\n__Questions__\n\n> While the authors have covered most of the relevant literature, as far as I'm aware, one missing paper that I am aware of is the following:\nM. Mohammadi Amiri, D. Gündüz, S. R. Kulkarni, and H. V. Poor, \"Federated Learning With Quantized Global Model Updates\" arXiv preprint arXiv:2006.10672, Jun 2020.\nHere, not only the authors consider downlink communication, but they actually transmit different updates to different clients. Instead of compressing the difference with rest to the previous global model, here the authors compress the difference with respect to the model updated by the client. This way the gap to the new global model is potentially lower. I can't say how the convergence rates compare, but I would like the authors to comment on the pros/cons of this approach compared to their own.\n\nThank you for pointing out this reference, we will add this work to the references. We would like to provide our comments on it.\n\nFirst, the statement that _they actually transmit different updates to different clients_ is incorrect. While it is true that the updates transmitted from the devices are different, the server sends the same message $Q(\\theta(t) - \\hat{\\theta}(t-1), q_1)$ to all clients (line 2 of Algorithm 1).\n\nRegarding the theoretical comparison between the proposed LFL and our MARINA-P/M3, a crucial difference lies in the underlying assumptions. Most importantly, the results of [3] rely on the strong convexity of the local loss functions, whereas MARINA-P and M3 operate in the non-convex setting. Additionally, the theory in [3] assumes the boundedness of the stochastic gradients, which is a very restrictive assumption and, in fact, contradicts the strong convexity assumption (see, e.g., [4]). Therefore, the constant $G$ in Theorem 1 can be arbitrarily large, potentially making the upper bound infinite.\n\nWe hope this clarifies the matter.\n\n[4] Nguyen, L., Nguyen, P. H., Dijk, M., Richtárik, P., Scheinberg, K., \\& Takác, M. (2018, July). SGD and Hogwild! convergence without the bounded gradients assumption. In International Conference on Machine Learning (pp. 3750-3758). PMLR.\n\n> How limiting is the assumption that the calls to the compressor are independent? There are some works in the literature that consider time-correlated sparsification, and show improved results (which also makes sense as the sparsity pattern should not change drastically from one iteration to the next). Please provide some comments in the paper if this may be a significant limitation on the practical performance of the considered class of compressors.\n\nThere exist various classes of compressors, each of them coming with some benefits and potentially some drawbacks. The assumption of time-independence is not a limitation. The class of compressors we consider is very wide, as a result of which the theoretical framework we developed covers a broad range of compression operators. Most importantly, the use of permutation compressors enables us to obtain superior complexity results, resulting in the first downlink compression algorithms whose complexities can provably improve with the number of workers.\n\nWe are not aware of any work with theoretical evidence that _the sparsity pattern should not change drastically from one iteration to the next_. We would be grateful if the reviewer could provide such references.\n___\nWe are grateful for the feedback and believe that we have resolved the issues identified. If further information or explanations are required, please do not hesitate to ask.", "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": "FKOZtaTN4f", "reviewer": "Reviewer_vddK", "summary": "This paper addresses optimizing server-to-worker communication in distributed optimization by introducing MARINA-P, a novel method using correlated compressors for downlink compression. The study identifies inefficiencies in current downlink compression approaches and shows that MARINA-P can reduce communication complexity as the number of workers increases. Additionally, MARINA-P serves as a foundation for bidirectional compression methods. The paper also presents M3, which combines MARINA-P with uplink compression and a momentum step, further improving total communication complexity. Both theoretical analyses and empirical experiments validate the efficiency of the proposed algorithms.", "questions": "The role of L_B is not completely clear, as it does not prominently affect communication complexities compared to L_A. Is it that by isolating L_B from L_A, one can effectively reduce L_A  and, consequently, the communication complexities as well? Moreover, the class of functions for which L_B is known to be positive is quite restricted (Theorem 4.5). It would be beneficial to find more general examples.", "limitations": "The paper does not explicitly address its limitations. The only related point is that the proposed method does not consistently outperform the CORE method by Yue et al. (2023) in terms of performance (p. 8).", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper is exceptionally well written, with technical results rigorously proved. One of the main novelties is the use of correlated compressors to achieve a server-to-worker communication complexity that improves with the number of workers.", "weaknesses": "The compressor model (Definition 1.4), while standard in the federated learning literature, is somewhat contrived. It is primarily defined in its current form to facilitate analysis. It remains unclear whether the main conclusions derived under this model can be directly translated to the information-theoretic setting (quantization plus entropy coding), where compression efficiency is measured in terms of bits per sample.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your comments and are grateful for highlighting the positive aspects of our work. We will now proceed to address the concerns you raised and provide clarifications.\n\n__Weaknesses__\n\n> The compressor model (Definition 1.4), while standard in the federated learning literature, is somewhat contrived. It is primarily defined in its current form to facilitate analysis. \n\nAs in all mathematical theories, we need some assumptions about compressors to prove theorems and develop theory. Definition 1.4 is particularly useful because it not only facilitates analysis but also captures a wide variety of compressors. \n\n> It remains unclear whether the main conclusions derived under this model can be directly translated to the information-theoretic setting (quantization plus entropy coding), where compression efficiency is measured in terms of bits per sample.\n\nIn Tables 1 and 2, we compare the compression efficiencies of the algorithms based on the total number of coordinates sent to find a $\\varepsilon$-stationary point. The formulas we compare there do not involve parameters and notations from Definition 1.4. Following the convention in virtually all papers in computer science published at NeurIPS, we ignore the fact that all computations use float32/64 instead of real numbers. With this simplification, sending one coordinate is equivalent to sending 32/64 bits. We acknowledge that addressing the errors arising from floating-point arithmetic is an important problem.\n\n__Questions__\n\n> The role of $L_B$ is not completely clear, as it does not prominently affect communication complexities compared to $L_A$. Is it that by isolating $L_B$ from $L_A$, one can effectively reduce $L_A$ and, consequently, the communication complexities as well? Moreover, the class of functions for which $L_B$ is known to be positive is quite restricted (Theorem 4.5). It would be beneficial to find more general examples.\n\nThank you for your comment. We agree that a more detailed discussion of this point (currently in the appendix), would benefit the paper, and we are happy to include it in the revised version. Let us clarify the results.\n\nTheorem 4.5 serves as an illustration of a case when $L_A=0$. However, please note that we do have much more general results with $L_B>0$ - see, for example, Theorem 4.8 (where we derive the constants $L_A$ and $L_B$ in terms of Hessians of the local functions $f_i$).\n\nIt is true that $L_B$ does not appear in the result from Theorem 4.6 and Corollary 4.7. However, this is not a disadvantage but rather a particular strength of MARINA-P with permutation compressors. To explain this, let us refer to a more general result in Theorem D.1. (along with Theorem D.2 and Corollary D.4). The upper bound on the stepsize depends on $L_B^2\\theta$, where $\\theta$ is a compression parameter from Definition A.3. The reason why this term does not appear in Theorem 4.6 and Corollary 4.7 is that for permutation compressors, we very conveniently obtain $\\theta=0$, which ultimately translates into a superior complexity bound.\n\nThe functional  $(L_A,L_B)$ inequality enables us to capture the intricate structure of the objective function and achieve superior complexity results for certain objective functions (particularly those satisfying the assumption with small $L_A$). This would not be possible without introducing both the $L_A$ and $L_B$ terms. While the second term on the right-hand side of (9) (the $L_B$ term) can be bounded by the first term using Jensen's inequality, reallocating mass from $L_B$ to $L_A$ results in worse theoretical guarantees. Therefore, keeping $L_A$ as small as possible is beneficial, as smaller values yield better complexity results, and hence the possibility that $L_B > 0$ is critical for obtaining the enhancements we present. Furthermore, in general $L_A\\neq0$, so requiring that the $(L_A,L_B)$ inequality holds with $L_A=0$ would limit the applicability of our results.\n\nLastly, both $L_A$ and $L_B$ appear in the complexity bounds of M3 (Theorem 5.1), making their introduction in the main part of the paper necessary.\n\nWe hope this clarifies the topic. Please let us know if there are any further questions.\n\n---\n\nWe appreciate your constructive feedback and trust that our responses have satisfactorily addressed the questions. Should any additional clarifications be required, we are happy to provide them.", "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": "KRK0VDA1xD", "reviewer": "Reviewer_r7n3", "summary": "This paper presents methods to improve communication efficiency in distributed optimization, particularly focusing on the server-to-worker (s2w) communication costs, which are often overlooked. The authors first present a lower bound on the required round of communication.  They used it to state that under no assumption between the individual functions stored at the distributed workers, the s2w communication loads can not be improved compared to the naive design. Then, the authors provide an algorithm and analysis showing that when the hessian of the individual functions are similar or aligned, improvements in communication complexity can be achieved.", "questions": "Is there any connection between $L_A$ and the Hessians of the individual functions, similar to the smoothness parameter $L$, which can be interpreted as the largest eigenvalue of the Hessian of f?", "limitations": "See weekness", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper introduces a formal quantification, called functional $(L_A, L_B)$ inequality, to measure the similarity in the smoothness of the individual functions available to the workers. Novel algorithms and analysis are provided to show that the similarity can be used to improve the s2w communication load. \n\nThe paper also includes an interesting theoretical analysis, providing lower bounds on the required rounds of communication in the worst case.", "weaknesses": "1. The authors use the lower bound on the rounds communication to claim a lower bound on the communication load. However, there is a gap in this argument: The authors state that since the rounds of communication are lower bounded by a certain function, the overall communication load is lower bounded by d times that function, given that the full gradient contains d entries. But if a compressor is used as assumed by the authors, where the server can deliver an unbiased function that has fewer entries, it is totally possible that the communication load is smaller than d times the rounds of communication, violating this claimed bound. \n\nTherefore, I have to suggest a weak rejection. I'm happy to raise my score if this issue can be appropriately fixed.\n\n2. The concept of functional $(L_A, L_B)$ inequality can be simplified since only L_A is used in the main results. It can be stated such as the functions satisfy an $L_A$ condition, if we can find $L_B$ such that ineq. (9) is satisfied.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and appreciating the strengths of our work. We would like to address your concerns and provide additional explanations.\n\n__Weaknesses__\n\n> The authors use the lower bound on the rounds communication to claim a lower bound on the communication load....\n\nAs far as we understand, the reviewer is pointing to a possible gap in our first contribution from Section 3. We believe that there may have been a misunderstanding, and there are no gaps in our argument.\n\nFirst of all, we are careful with our claims and only provide the lower bound $\\Omega\\left( \\frac{(\\omega + 1) L \\delta_0}{\\varepsilon} \\right)$ for the number of **iterations/rounds.** We have never provided _a lower bound on the communication load_, and never claimed that _the overall communication load is lower bounded by $d$ times that function, given that the full gradient contains $d$ entries_. Once again, we only proved the lower bound $\\Omega\\left( \\frac{(\\omega + 1) L \\delta_0}{\\varepsilon} \\right)$ for the number of iterations/rounds, where $\\omega$ is the variance from Definition 1.4.\n\nWe are on the same page with the reviewer that in order to determine the communication complexity, we have to multiply the number of iterations/rounds by the number of entries/coordinates of a compressor. For simplicity, let us consider the Rand$K$ compressor, which sends $K$ random coordinates and has variance $\\omega = \\frac{d}{K} - 1.$ Assuming that the server uses Rand$K$ in every iteration/round, the lower bound on the communication complexity is \n$$K \\times \\Omega\\left( \\frac{(\\omega + 1) L \\delta_0}{\\varepsilon} \\right) = K \\times \\Omega\\left( \\frac{d L \\delta_0}{K \\varepsilon} \\right) = \\Omega\\left( \\frac{d L \\delta_0}{\\varepsilon} \\right),$$\nbecause, as the reviewer noted, we have to multiply by $K$ (not $d,$ as both we and the paper agree upon). Hence, we get the communication complexity $\\Omega\\left( \\frac{d L \\delta_0}{\\varepsilon} \\right)$ of GD. This argument leaves us no hope to improve the $\\Omega\\left( \\frac{d L \\delta_0}{\\varepsilon} \\right)$ communication complexity without an extra assumption.\n\nIt is worth noting that we do not prove a lower bound for the communication complexity $\\Omega\\left( \\frac{d L \\delta_0}{\\varepsilon} \\right)$ in general. Instead, we establish a lower bound $\\Omega\\left( \\frac{(\\omega + 1) L \\delta_0}{\\varepsilon} \\right)$ for the number of iterations/rounds, and then, assuming that the server uses, for instance, Rand$K$ in every iteration, we get the $\\Omega\\left( \\frac{d L \\delta_0}{\\varepsilon} \\right)$ communication complexity. Even this result provides strong evidence that we need an extra assumption to get further theoretical improvement.\n\nWe believe that this clarification addresses the reviewer's concerns and explains that there are no mathematical gaps in our argument. We hope that the reviewer will reconsider the score. In case of any additional questions or if further clarification is needed, please let us know.\n\n> The concept of functional ($L_A, L_B$) inequality can be simplified since only $L_A$ is used in the main results. It can be stated such as the functions satisfy an $L_A$ condition, if we can find $L_B$ such that ineq. (9) is satisfied.\n\nIt is true that $L_B$ does not appear in the result from Theorem 4.6 and Corollary 4.7. This is a particular strength of MARINA-P with permutation compressors. \n\nLet us look at the general results in Theorem D.1. (plus Theorem D.2 and Corollary D.4). The upper bound on the stepsize depends on $L_B^2\\theta$, where $\\theta$ is a compression parameter from Definition A.3. The reason why this term does not appear in Theorem 4.6 and Corollary 4.7 is that for permutation compressors, very conveniently one obtains $\\theta=0$, which ultimately translates into superior complexity bound. However, the $L_B$ term is necessary for comparing this result with different compression schemes where $\\theta>0$. Moreover, both $L_A$ and $L_B$ appear in the complexity bounds of M3 (Theorem 5.1), so their introduction in the main part of the paper is necessary.\n\nOverall, the functional $(L_A,L_B)$ inequality enables us to capture the intricate structure of the objective function and obtain superior complexity results for certain objective functions (those satisfying the assumption with small $L_A$). This would not be possible without introducing both the $L_A$ and $L_B$ terms. While the second term on the right-hand side of (9) (the $L_B$ term) can be bounded by the first term using Jensen's inequality, reallocating mass from $L_B$ to $L_A$ results in worse theoretical guarantees. Therefore, keeping $L_A$ as small as possible is beneficial, as smaller values yield better complexity results. Hence, the possibility that $L_B > 0$ is critical for obtaining the enhancements we present. On the other hand, since in general $L_A\\neq0$, requiring that the $(L_A,L_B)$ holds with $L_A=0$ would limit the applicability of our results.\n\nWe hope this clarifies why both terms are needed. Please let us know if there are any further questions.\n\n__Questions__\n\n> Is there any connection between  and the Hessians of the individual functions, similar to the smoothness parameter $L$, which can be interpreted as the largest eigenvalue of the Hessian of $f$?\n\nYes, there is such a connection! In fact, this result is already included in the paper. Please, see Theorem 4.8, where we derive $L_A$ and $L_B$ based on the Hessians of the functions $f_i$.\n\n---\nWe hope that the explanations provided adequately address the reviewer's comments, and we kindly ask for a reconsideration of the score. Please let us know if more details or clarifications are needed.", "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": "K7hScBndVq", "reviewer": "Reviewer_K3Nf", "summary": "Differently from other papers in the field of federated learning, the authors consider the problem of uplink compression - from the server to the workers. The main contributions of the paper are MARINA-P and its variants. These optimization schemes leverage PermK sparsification to reduce the communication complexity in the uplink. When combined with momentum, MARINA-P achieves a total communication complexity that, in the case of $n>>1$ and for close-to-homogeneous clients, is smaller than competing state-of-the-art alternatives.", "questions": "- Related to my previous point, how many coordinates are sent into the uplink at each round from the server to all users? i.e. what is the support of $\\sum^n_{i=1} \\mathcal{C}_i(x)$?\n- Is MARINA-P compatible with client selection? Meaning, is it possible to apply MARINA-P if, at each round, the number of users varies or a different subset is chosen?\n- Would it be possible to compare MARINA-P to other state-of-the-art schemes that use masking to reduce communication (e.g., SPARSE RANDOM NETWORKS FOR COMMUNICATION-EFFICIENT FEDERATED LEARNING)?\"", "limitations": "Limitations are adequately discussed in the text.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper is original as it focuses on uplink compression, an aspect which is often overlooked in the federated learning community. The results are very interesting, as the authors not only show that under suitable conditions, MARINA-P has very low communication complexity, but they also demonstrate that without additional assumptions, there is an insurpassable lower bound to the communication complexity. The paper is very well-written; in fact, despite being very dense, it still introduces the problem and the proposed solution in a very clear manner.", "weaknesses": "- The main weakness of the paper is the assumption of data homogeneity. While I understand that this assumption is necessary, it would be interesting to include experimental evidence in the main text showing how MARINA-P performs with heterogeneous data.\n- The following might be erroneous, but to me seems like that the overall number of coordinates sent in the uplink is $d$. From the discussion in Section 4.5 it seems like that the parameter vector is permuted and divided into non-overlapping chunks, and each chunk is sent to a different client. As such, it looks like that the \\emph{overall} number of coordinates sent to the server is $d$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and for acknowledging the contributions of our research. We will now address each of your comments and provide clarifications.\n\n__Weaknesses__\n\n> The main weakness of the paper is the assumption of data homogeneity. While I understand that this assumption is necessary, it would be interesting to include experimental evidence in the main text showing how MARINA-P performs with heterogeneous data.\n\nThe assumption of data homogeneity is not necessary, and we do not assume it! While it is true that MARINA-P and M3 perform exceptionally well in the close-to-homogeneous regime, all our main results hold for arbitrarily heterogeneous clients. The only requirement is that the functional $(L_A,L_B)$ inequality holds. Importantly, for this to be true, the local functions do not need to be homogeneous. In fact, the functional $(L_A,L_B)$ inequality is weaker than the $L_i$-smoothness of the local functions $f_i$, which can clearly hold in heterogeneous scenarios.\n\n> The following might be erroneous, but to me seems like that the overall number of coordinates sent in the uplink is $d$. From the discussion in subsection 4.5 it seems like that the parameter vector is permuted and divided into non-overlapping chunks, and each chunk is sent to a different client. As such, it looks like that the _overall_ number of coordinates sent to the server is $d$.\n\nYes, it is true that each client receives $\\approx d/n$ coordinates, so the total number sent by the server is $d$ (as is the case for any sparsifier with the same sparsification level). Notice that without compression, the server would send $d$ coordinates to each worker, resulting in a total of $n \\times d$ instead of $d$ coordinates sent.\n\n__Questions__\n\n> Related to my previous point, how many coordinates are sent into the uplink at each round from the server to all users? i.e. what is the support of $\\sum \\mathcal{C}_i(x)$?\n\nAs mentioned previously, the server sends $K \\approx d/n$ (distinct) coordinates to each client in the case of the permutation compressors, and $\\sum \\mathcal{C}_i(x) = x$.\n\n> Is MARINA-P compatible with client selection? Meaning, is it possible to apply MARINA-P if, at each round, the number of users varies or a different subset is chosen?\n\nSuch behavior can be modeled using a specific compressor that satisfies Definition 1.4, and hence our theory applies. Specifically, let us define a compression operator $\\mathcal{C}$ via $\\mathcal{C}(x) = \\mathcal{\\bar{C}}(x)$ with probability $p$, and $0$ otherwise, where $\\mathcal{\\bar{C}} \\in \\mathbb{U}(\\bar{\\omega})$. It can easily be shown that $\\mathcal{C} \\in \\mathbb{U}(p\\bar{\\omega}+1-p)$. In this model, the case when $\\mathcal{C}(x) = 0$ can be interpreted as a worker not participating in this step.\n\n> Would it be possible to compare MARINA-P to other state-of-the-art schemes that use masking to reduce communication (e.g., SPARSE RANDOM NETWORKS FOR COMMUNICATION-EFFICIENT FEDERATED LEARNING)?\"\n\nFirst, [5] focuses on training sparse networks, whereas our objective is the optimization of a general objective function. More importantly, the method in [5] does not address communication reduction in the downlink direction. The primary goal of the proposed FedPM algorithm is to train a probability mask to find the optimal sparse random network within the original random one, aiming to reduce the uplink communication cost. In contrast, this paper targets both downlink and uplink communication directions. MARINA-P specifically targets the downlink communication direction. Since these two algorithms address different goals, a direct comparison is not evident.\n\n[5] Isik, B., Pase, F., Gunduz, D., Weissman, T., & Zorzi, M. (2022). Sparse random networks for communication-efficient federated learning. arXiv preprint arXiv:2209.15328.\n\n---\n\nWe hope that the explanations provided adequately address the reviewer’s comments. Should any additional clarifications be required, we are happy to provide them.", "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: Unlike most papers in federated learning/distributed optimization, this paper studies the downlink communication cost (server to users). The paper presents a theoretical analysis on the required number communication rounds and shows that, under no assumption on the functions stored at the distributed workers, the communication cost cannot be improved with respect to a naive approach. But, if the hessian of the individual functions are "aligned", improvements in communication complexity can be achieved. In particular, they propose a downlink compression scheme called MARINA-P, which uses the interesting idea of sending correlated compression versions to the users. The reviewers agree that the paper provides a meaningful contribution in a relatively unexplored aspect of distributed optimization.
Decision: Accept (spotlight)