2Direction: Theoretically Faster Distributed Training with Bidirectional Communication Compression
Authors: Alexander Tyurin
Peter Richtárik
Venue: NeurIPS 2023 poster (2023)
Keywords: convex optimization
accelerated method
communication compression
bidirectional compression
distributed optimization

Abstract: We consider distributed convex optimization problems in the regime when the communication between the server and the workers is expensive in both uplink and downlink directions. We develop a new and provably accelerated method, which we call 2Direction, based on fast bidirectional compressed communication and a new bespoke error-feedback mechanism which may be of independent interest. Indeed, we find that the EF and EF21-P mechanisms (Seide et al., 2014; Gruntkowska et al., 2023) that have considerable success in the design of efficient non-accelerated methods are not appropriate for accelerated methods. In particular, we prove that 2Direction improves the previous state-of-the-art communication complexity $\widetilde{\Theta}\left(K \times \left(\frac{L}{\alpha \mu} + \frac{L_{\max} \omega}{n \mu} + \omega\right)\right)$ (Gruntkowska et al., 2023) to $\widetilde{\Theta}(K \times (\sqrt{\frac{L (\omega + 1)}{\alpha \mu}} + \sqrt{\frac{L_{\max} \omega^2}{n \mu}} + \frac{1}{\alpha} + \omega))$ in the $\mu$--strongly-convex setting, where $L$ and $L_{\max}$ are smoothness constants, $n$ is \# of workers, $\omega$ and $\alpha$ are compression errors of the Rand$K$ and Top$K$ sparsifiers (as examples), $K$ is \# of coordinates/bits that the server and workers send to each other. Moreover, our method is the first that improves upon the communication complexity of the vanilla accelerated gradient descent method (AGD). We obtain similar improvements in the general convex regime as well. Finally, our theoretical findings are corroborated by experimental evidence.

Directioon: Theoretically Faster Distributed Training with Bidirectional Communication Compression
Alexander Tyurin
Peter Richtárik
KAUST Saudi Arabia
KAUST
Saudi Arabia
al elexaneertuurii@@malll...
richtarik0gmail.com
Abstract
We consider distributed convex optimization problems in the regime when the communication between the server and the workers is expensive both uplink and downlink directions. We develop which we call 2Direction, based on fast bidirectional compressed communication and new bespoke error-feedback mechanism which may be of independent in- terest. Indeed, we find that the EF and EF21-P mechanisms (Seide et al., 2014; Gruntkowska et al., 2023) that have considerable success in the design of efficient acc-lcceler methods are not appropriate for accelerated methods. In partic- ular, prove that 2Direction improves the previous state-of-the-at communica- tion complexity Ô (K x (4/ap Lmaass/nn + w)) (Gruntkowska al., 2023) O(K x (v [[[(+1)//w + v //maew//m /nu + 1/6 + w)) in the y-stroogly-connvxx set- ting, where L and Lixax are compression errors of the RandK and TopK sparsifiers (as examples), K is # of coordinates/bits that the server and workers send to each other. Moreover, our method is the first that improves upon the communication complexity of the vanilla accelerated gradient descent (AGD) method (Nesterov, 2018). We obtain similar improvements in the general convex regime as well. Finally, our theoreti- cal findings corroborated by experimental evidence.
and provably accelerated method,
smoothness constants, is # of workers, and
Introduction
We consider convex optimization problems in the centralized distributed setting. These types of problems appear in federated learning (Konečný et al., 2016; McMahan et al., 2017) and distributed optimization (Ramesh et al., 2021). In this setting, one of the main problems is the communication bottleneck: the connection link between the server and the workers can be very slow. We focus our attention on methods that aim to address this issue by applying lossy compression the communi- cated messages (Alistarh et al., 2017; Mishchenko et al., 2019; Gruntkowska et al., 2023).
1.1
The problem
Formally, consider the optimization problem
f(x) = = Amm)
min #ER'
(I)
where n is the number of workers and f; Rd TR are smooth convex functions for all i [n] =
(1...., n... We consider the centralized distributed optimization setting in which each 7th worker
contains the function ft. and all workers are directly connected to server (Kairouz et al., 2021). In
general, we want to find (possibly random) point & such that [ - f(x*) S e, where x"
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

an optimal point. In the strongly convex setup, we also want to guarantee that Bi - x 201 S for some point I.
Virtually all other theoretical works in this genre assume that, compared to the worker-to-server (w2s) communication cost, the server-to-workers (s2w) broadcast is fast that it can be ignored. We lift this limitation and instead associate a relative cost r E [0, 1] with the two directions of communication. If free, and i = 1/2, then the s2w and w2s costs are equal. All our theoretical results hold for any r E [0, 1]. We formalize and elaborate upon this setup in Section
then s2w communication is free, if
then w2s communication is
1.2 Assumptions
Throughout the paper we rely on several standard assumptions on the functions fa and f. Assumption 1.1. Functions fi are L--smooth, i.e., [V V f((i))l I Lş || - yll for all æ, E Rd, for all E [ni] We let Lumax max [x] I4. Further, let L be constant such that
1 E | (xx) Vf(li)ll < L || - y/l for all E R². Note that if the functions fo are smoohh for all i [n]. then İ Lmax.
Assumption 1.2. Function is L Lmooth,, i.e., [xv - Vf(v)l L || yil for all x, Rd. Assumption 1.3. Functions f. are convex for all i E [nd], and f is p-strongly convex with μ 2 0, attaining minimum at some point x² Rd
is known that the above smoothness constants are related the following way. Lemma 1.4 (Gruntkowska et al. (2023)). If Assumptions 1.2, 1.1 and 1.3 hold, then L S Lmax S aL and L < < V.maae.
Motivation: From Unidirectional to Bidirectional Compression
In this work, we distinguish between worker-to-server (w2s=uplink) and server-to- worker (s2w=downlink) communication cost, and define w2s and s2w communication complexities of methods in the following natural way.
Definition 2.1. For centralized distributed method M aiming solve problem (1), the commu- nication complexity m is the expected number of coordinates/floats that each worker sends to the server solve problem (1). The quantity m is the expected number of floats/coordinates the server broadcasts to the workers to solve problem (1). If m m then we use the simplified notation m := X m
Let us illustrate the above concepts on the simplest baseline: vanilla gradient descent (GD). It is well known (Nesterov, 2018) that for T-smooth, /--strongly convex problems, GD returns e- solution after O (4/p log 1/c) iterations. In each iteration, the workers and the server communicate all ((d) coordinates to each other (since compression is applied). Therefore, the communication complexity of GD is m.n = θ (dL/y- log 1/c) The same reasoning applies to the accelerated gradient method (AGD) (Nesterov, 2018), whose communication complexity is maco ((d / log 1/e).
2.1 Compression mappings
In the literature, researchers often use the following two families of compressors: Definition 2.2. A (possibly) stochastic mapping Rd
Rd biased compressor if there
exists E (0, 1] such that
E [I((()) xx|²] < (1 a) ||+|
Va EdR
(2)
Definition 2.3. A stochastic mapping C Rd - Rd is unbiased compressor if there exists such that
E [C(x)) = x E [[((s) = s w ||=1
Va Rd.
'Some works measure bits instead of coordinates. For computer systems, where coordinates are represented by 32 or 64 bits, these measures equivalent up to the constant factors 32 or 64.

---

Table I: Communication Rounds in the Strongly Convex Case. The number of communication rounds and rounds costs to get an e-solution (L3 -| I e) up to logarithmic factors. The table shows the most relevant bidirectional compressed methods that are ordered by the total communication complexity # Communication Rounds x Round Cost (see (4) for details).
i. The parameter weights the importancc/speed of uplink and downlink connections. When 1/2, it mcans that the uplink and downlink speeds are equal.
The parameters K and Ka are the expected densities Definition 2.5 of compressors CD E [ww)) and Cº B(a) )M) that operate in the workers and the server accordingly. Less formally, Kw and Ka are the number of coordinates/bits that the workers and the server send to each other in each communication round.
Method
# Communication Rounds
Round Cost
Dore, Artemis, MURANA
(Philippenko and Dieuleveur, 2020)
(Liu et al., 2020)
Xomax
(1 K) + Koo
(Condat and Richtárik, 2022)
(Philippenko and Dieuleveut, 2021)
MCM
3/5
myn
Zinaz (
(1 - r) + rka
GD (Nesterov, 2018)
d
(Graikowska al., 2023)
EF21-P DIANA
ay +
Lumnn w ui
(1 r) + rKa
AGD (Nesterov, 2018)
(Remark 5, (Theorem 5.2)
2Direction
1 + v Amaxu?
+ +
r) rK.
2Direction
mmao (1, L.ow+1] ap
12/3 1/3 +111 173p
(Remark S, (Theorem 5.4)
K) rka
(requires /max/L))
1//2 moma (w/+1)3/2
Lmagw
Vanp
(0) The Dore, Artemis, MURANA, and MCM methods do support bissed compressors for server- worker compression.
In these methods, the error a equals 1/sx+ +1), where the emorr w, is a parameter of an unbiased compressor that is used in server-towworker compression. For these methods, we define 1/(us 11 as to make comparison easy with EF21-P DIANA and 2Direction.
(h) table, we present simplified iteration complexity 2Direction assuming that S 1/2amd w +1 (4/kw) (13) and (14), In Section 6, we show that 2Drrection has worse total communication com-
The full complexities plexity than EF21-P DIANA for all r E [0, 1] and for any choice of compressors.
fel We define Round Cost of a method M as constant such that m J = Communication Rounds x Round Cost, where m is the total communication complexity (4).
2Direction can have even betler total communication complexity if the algorithm use the ratio Lmax/ i when selecting the parameters r and in Algorithm I. For instance, this is the case if we assume that Lima L. which was done by Li Richtárik (2021), for esample.
et (2020);
10 The notation 92 (-) meuns least up to logarithmic factoes."
We will make use of the following assumption. Assumption 2.4. The randomness in all compressors used in our method is drawn independently.
Let us denote the set of mappings satisfying Definition 2.2 and 2.3 by BB(a) and U(w), respectively. The family of biased compressors B is wider. Indeed, it well known e D(w), then 1/ww+1)-C e B (1/w+1)). The canonical sparsification operators belonging to these classes are Topk E (B()))) and RandK E U(d/K- 1). The former outputs the K largest values (in magnitude) of the input vector, while the latter outputs K random values of the input vector, scaled by d/K (Beznosikov et al., 2020). Following (Gorbunov et al., 2021; Tyurin and Richtárik, 2023), we now define the expected density of sparsifier as a way to formalize its compression performance.
Definition 2.5. The expected density of sparsifier C Rd + Rd is the quantity Ke sup E [[])())]lo,, where IIv/lo is the number of of non-zero components of y E Rdd.
Trivially, for the Rand and TopK sparsifiers we have Ke- K.
2.2 Unidirectional (i.e., w2s) compression
As mentioned in the introduction, virtually all theoretical works in the area of compressed communi- cation ignore s2w communication cost and instead aim minimize m Algorithmic work related
3

---

to methods that only perform w2s compression has long history, and this area is relatively well understood (Alistarh et al., 2017: Mishchenko et al., 2019; Richtárik al., 2021).
We refer to the work of Gruntkowska et al. (2023) for a detailed discussion of the communication complexities of non-accelerated methods in the convex and non-convex settings. For instance, ing RandK, the DIANA method of Mishchenko et al. (2019) provably improves* the communication complexity of GD to I ê (d + KL/u+ dLmux//pp) Accelerated methods focusing on w2s compression are also well investigated. For example, Li et al. (2020) and Li and Richtárik (2021) developed accelerated methods, which are based on (Mishchenko et al., 2019; Kovalev et al., 2020), and provably improve the w2s complexity of DIANA, Moreover, using Rand with K S d/n, ADI- ANA improves the communication complexity of AGD to m - Od + dv Imoz/fu)..
2.3 Bidirectional (i.e., w2s and s2w) compression
The methods mentioned in Section 2.2 do not perform server-to- workers (s2w) compression, and one can show that the server-to-workers (s2w) communication complexities these methods are worse than M.m = (dd L/v) For example, using the RandK, the s2w communication complexity of ADIANA is at least m ANANA S2(d x w) (K)/)), which be 4/K times larger than in GD or AGD. Instead of my methods performing bidirectional compression attempt to minimize the total communication complexity, which we define as a convex combination of the w2s and s2w communication complexities:
m = (1 r) + rm
The parameter [0, 1] weights the importance of uplink (w2s) and downlink (s2w) connections Methods from Section 2.2 assume that = 0, thus ignoring the s2w communication cost. On the other hand, when r 1/2, the uplink and downlink communication speeds are equal. By consid- ering any r E [0, 1]. our methods and findings are applicable to more situations arising in practice. Obviously, m Map and m mx for all E [0, 1]. Recently, Gruntkowska al. (2023) proposed the EF21-P + DIANA method. This is the first method supporting bidirectional compres- sion that provably improves both the w2s and s2w complexities of GD: M S moD for all r [0, 1]. Bidirectional methods designed before EF21-P DIANA, including (Tang et al., 2020; Liu et al., 2020; Philippenko and Dieuleveut, 2021), do not guarantee the total communication com- plexities better than that of GD. The EF21-P DIANA method is not an accelerated method and, in the worst case, can have communication complexities worse than AGD when the condition number I/f is large.
3 Contributions
Motivated by the above discussion, in this work we aim to address the following
Main Problem:
Is it possible to develop a method supporting bidirectional communication compression that improves the current best theoretical total communication complexity of EF21-P DIANA, and guarantees the total communication com- plexity to be no worse than the communication complexity m. = (L% of AGD, while improving on AGD in at least some regimes?
A) We develop a new fast method (2Direction; see Algorithm 1) supporting bidirectional commu- nication compression. Our analysis leads to new state-of-the-art complexity rates in the centralized distributed setting (see Table 1), and as a byproduct, we answer Main Problem in the affirmative.
B) Gruntkowska et al. (2023) proposed to use the EF21-P error-feedback mechanism (8) to im- prove the convergence rates of accelleredd methods supporting bidirectional communication compression. EF21-P is reparameterization of the celebrated EF mechanism (Seide et al., 2014). We tried to use EF21-P in our method as well, but failed. Our failures indicated that fundamentally
PIndeed, using Lemma 1.4, K S d, and I. 2 (t, one can easily show that + KLfp + dllmax/ngg = O(d1/)). "i " m where "h and RV are connection speeds, and 220 1200

---

new approach is needed, and this eventually led us to design new error-feedback mechanism (9) that is more appropriate for accelerated methods. We believe that this is contribution of indepen- dent interest that might motivate future growth in the area.
C) Unlike previous theoretical works (Li et al., 2020; Li and Richtárik, 2021) accelerated methods, we present unified analysis in both the u-strongly-come Moreover, in the general convex setting and low accuracy regimes, our analysis improves the rate O (1/2/3) of Li and Richtárik (2021) to O (log 1/e) (see details in Section R).
and general convex cases.
D) Even though central goal to obtain new SOTA theoretical communication complexities for centralized distributed optimization, we show that the newly developed algorithm enjoys faster communication complexities in practice as well (see details in Section Q).
Algorithm 1 2Direction: A Fast Gradient Method Supporting Bidirectional Compression
Lipschitz-like like parameter L > ctrong-convexity parameter μ. 2 O, probability E (0, 1], parameter To 2 1, momentum т E (0, 1], contraction parameter a E (0, 1] from (2), initial point x E IR" initial gradient shifts 1i, ........... ... 1g E R gradient shifts k2 E Re and o u Initialize 1/ w0 = n æ0 and At" = = E. do BaaalaaeeLLamminnRateeeeeee (. 5: for = 1,..., parallel do
I: Parameters:
3: for = 0, 1,.1,....
4: Tt-1, 01-1
Get learning rates using Algorithm 2
6:
n² 0++1w" + 0++1)=*
7: mi
(Vii(v'*) id))
Worker compresses shifled gradient the compressor CP.v U(w)
8:
4:9 Send compressed message m.
to the server
9:
end for
10:
g'+l ht + 1 Σ mfa
n++l_ arg min r+ ,x) +
L+Ta 1/ 2te41
11 1
gradient-like descent stop
12:
++ arg min (k
Lifie
| w²
11
27441
13:
pt Cº (1
Server compresses the shifted model vin the compressor C (B(a)
14:
w r+1 - gitl +p"
15:
x'+1 = O++1u*+ + (1 0ct1)2
16:
Send compressed message p to all n workers
17:
Flip coin c¹ Bemouuli(p)
g--1 v' 18:
and gtt
d'
ke.
c'
19:
if cf = then
20:
Broadcast non compresse messages th and 4+41 to all n workers
With small probability
21:
end if
22:
for L...., . n in parallel
23:
q² g++1 arg minzeRd (k'
ZtPTH || w/ 2011
24:
u+1 a (+1 +
p243
x x"_1,
==
25:
_+1
2
d==0
26:
m. 1.2 c. (Vf:(2+t))
h!)
Worker compresses shifted gradient the compressor C, c U(W)
27:
4. = 1 + 3m, A.#
28:
Send compressed message m. to the server end for
29:
30:
n/+1 (1 -)o'' + + 2
31:
h.41 = h²' + - Σe= m!:
32:
end for
4 New Method: 2Direction
In order to provide an answer to Main Problem, at beginning of our research journey we hoped that rather straightforward approach might bear fruit. In particular, we considered the current state- the-art methods ADIANA (Algorithm 3) (Li et al., 2020), CANITA (Li and Richtárik, 2021) and EF21- P + DIANA (Algorithm 4) (Gruntkowska et al., 2023), and tried to combine the EF21-P compression
5

---

Algorithm 2 CalculateLeaamingRaees
1: Parameters: element ry; parameter L > 0; strong-convexity parameter μ 2 0, probability contraction
parameter at momentum т. parameter 3
2: Find the largest root 0.+1 of the quadratic equation
pi.100441 + p( TepeBe41 (T. (T. U1.+Tuph T1pp) =0
3: 0mnn = 1 min { a
p p.:
} Be+1 minf0e+1, Omini:
Mot1
1-p8442"
T
Pe + Y441
mechanism on the server side with the ADIANA (accelerated DIANA) compression mechanism on the workers' side. In short, we were aiming develop "EF21-P ADIANA" method. Note that while EF21-P + DIANA provides the current SOTA communication complexity among all methods supporting bidirectional compression, the method is not "accelerated". On the other hand, while ADIANA (in the strongly convex regime) and CANITA (in the convex regime) are "accelerated", they support unidirectional (uplink) compression only.
In Sections and C we list the ADIANA and EF21-P + DIANA methods, respectively. One can see that in order calculate x141 1+1 and 24+1 in ADIANA (Algorithm 3), it is sufficient for the server to broadcast the point _i+1 At first sight, it seems that we might be able to develop a "EF21-P ADIANA" method by replacing Line 15 in Algorithm 3 with Lines 12, 13, 14, and 16 from Algorithm 4. With these changes, we can try to calculate gf+1 and y using the formulas
g² Oc+1"* + (1 0c+1)=',
(5)
+ 1 + (1 0(41)2
(6)
2+1 w' + CP (u²+1 w²),
(7)
instead of Lines 7 and 17 in Algorithm 3. Unfortunately. all our attempts of making this work failed, and we now believe that this "naive" approach will not lead to resolution of Main Problem. Let us briefly explain why we think so, and how we ultimately managed to resolve Main Problem.
The first issue arises from the fact that the point x'+1, and, consequently, the point 21+1 depend on w1+1 instead of u and thus the error from the primal (i.e., server) compressor Cº affects them. In our proofs, we do not know how to prove a good convergence rate with (6). Therefore, we decided to use the original update (Line 17 from Algorithm 3) instead. We can do this almost for free because in Algorithm 3 the point x'+1 is only used in Line 18 (Algorithm 3) with small probability In the final version of our algorithm 2Direction (see Algorithm 1), we broadcast a non-compressed messages x1+1 with probability p. In Section 6, we show that p is so small that these non-compressed rare messages do not affect the total communication complexity of Algorithm 3.
The second issue comes from the observation that we can not perform the same trick for point ++ since it is required in each iteration of Algorithm 3. We tried to use (5) and (7), but this still does not work. Deeper understanding of this can only be gained by detailed examination our proof and the proofs of (Li et al., 2020; Gruntkowska et al., 2023). One way to explain the difficulty is to observe that in non-accelerated methods (Gorbunov et al., 2020; Gruntkowska et al., 2023), the variance-reducing shifts h' converge to the fixed vector fxxx)) while in the accelerated methods (Li et al., 2020; Li and Richtárik, 2021), these shifts h' converge the non-fixed vectors V f2(") in the corresponding Lyapunov functions. Assume that μ = O. Then, instead of the EF21-F mechanism
wh = w² + CP (ut+1 - -w()
Alg. w + C. (u' 1++1 1 - w()
(8)
\=(=")=0 w² 7041 (f(x*) CCP (u' Tes1
w²)
propose to perform the step
'1111 w² Te+1
b V=((') + CP (u' - ( -(())) w²)
(9)
= =q'+1 + CP (u - ,(+1), where
n 1+1 arg min (g (1 x) + 27111 ||I=~ u11 g++l = arg min (V)(2
L
||
w
23111
dERd
=ERd
Unlike (8), step (9) resolves all our previous problems, and we were able to obtain new SOTA rates.

---

However, step (9) is not implementable since the server and the nodes need to know the vector f((²). The last crucial observation the same as with the points x' and 2": the vector fz(²") changes with probability p since the point 2 changes with probability p. Intuitively, this means that it easier to communicate V V=(=²) between the server and the workers. We do this using two auxiliary control vectors, v and k.. The former "learns" the value of f=") in Line 30 (Algorithm 1), and the latter is used in Line 14 (Algorithm 1) instead V ff(²),, Then, when the algorithm updates =+1 it also updates k in Line 18 (Algorithm 1) and the updated non-compressed vector ke is broadcast to the workers.
The described changes are highlighted in Lines 6, 12, 13, 14, 18, 20, 23, 24 and 30 of our new Algorithm in green color. Other steps of the algorithm correspond the original ADIANA method (Algorithm 3). Remarkably, all these new steps are only required to substitute single Line 15 of Algorithm 3!
Theoretical Communication Complexity of 2Direction
Having outlined our thought process when developing 2Direction (Algorithm 1), are now ready to present our theoretical iteration and communication complexity results. Note that 2Direction depends on two parameerra,,,,ss, probability p (used in Lines and 17) and momentum (used in Lines 4 and 30). Further, while Li et al. (2020); Li and Richtárik (2021) assume a strong relationship between and Lmax (L maxx), Gruntkowska et al. (2023) differentiate between L and Lmax and thus perform a more general and analysis of their method. In order to perform a fair comparison to the above results, we have decided to minimize the total communication complexity m as a function of the
and depending on whether the ratio Lmnx/L / is known or not.
Defining R² : || 2²I Theorems E. and E.14 state that 2Direction converges after
T= max
L
ATlema W avap
/. VW+IVWT
opp
arp
a/Pa/up
(10)
Lmari 1 1 (w + 1), (1) (
Amaa (w 17 Rj
app
Tg. = O
max
LR ope
LB aTE
VLmma 1w+1) ayne
V.llmae Vuu WWWT a/P/ne
(11)
(w 1)
Luanww w R2 npc
+
max a aT (w
iterations, in the μ-strooggl convex and general convex regimes, respectively. These complexities depend on two sypemtpprameters: p E (0, and E (0, 1). For simplicity, in what follows we con- sider the j-strooglyy convex case only*. While the iteration complexities (10) and (11) are clearly important, in the context of our paper, optimizing communication complexity (4) is more important. In the following simple theorem, we give expressions for the communication complexities of 2Direc- tion, taking into account both workers-to-sere
(w2s) and server-to-workers (s2w) communication.
Theorem 5.1. Assume that c.:. and C. have expected densities equal to K and Ka, respectively (see Definition 2.5). In view of Theorem E. 12, in expectation, the w2s and s2w communication complexities are equal to
m (KK xT+ d)
and m θ ((Ka + pd) T +
(12)
Proof. The first complexity in (12) follows because w2s communication involves c.-.(()) and
cP)(() only. The second complexity in (12) follows because s2w communication involves C.¹ ()), plus two non-compressed vectors x'+1 and g++ with the probability p. The term d comes from the fact that non compressed vectors are communicated in the initialization phase.
*One can always take μ = 5/22² to understand the dependencies in the general convex case.
7

---

5.1 The ratio L is not known
In the following theorem, we consider the regime when the exact value of fmax/L is not known. Hence, we seek to find and J that minimize the worst case m (see (4)) w.r.t Lmax E [L, Theorem 5.2. Choose E [0 and let Plaa trk. In view of Theorem 5.1, the rd
values p = min w+1 Mis - and r (w+1)a78 minimize max m This choice leads to the Lmax (L,
11/a
following number communication rounds:
Lmaoe max(u+1.5 (w+ 1), ): 1): (13)
Trealisii
max
max(w-11.t
ng
The total communication complexity thus equals m
+ (((1 ([(1-r)ksg + rkaa Tratine Soaaint-n d).
mulistic
Remark 5.3. To simplify the rate (13) and understand the quantity Mar,. let C. be the RandK sparsifier and consider the when the s2w communication is not slower than the w2s com- munication, i.e., r < 1/2. Then Trealistic = + max {v [(w+1)
ap VV V [mmxxwlw+1) 1 (w + 1) and upp
Mh, S w + 1. Indeed, this follows from r s 1/2 and the fact that w + = a/k_ for the Randk compressor: IWa (I-r)Ratrk.
nd
d S wwtt wwl..
5.2 The ratio Lma//L is known
We now consider the case when we have information about the ratio Lmsx/L.
rd Theorem 5.4. Choose E [0, 1], and let pw.a = [I-r)Kk+rK, In view of Theorem 5.1, the values p and T given by (63) and (58), respectively, minimize mi... from (10). This choice leads to the following number of communication rounds:
L mmax(1,,5... Pin
1,2/3 11/3 (ws 11)
1 T (w 1)3/2
1 pttiiiitic
au
an!/3p
Vanu
(14)
Timasit max + 1,
'a" (w + 1), platiaa 1)
nip.
The total communication complexity thus equals m"
H (((1 - Kw rraa) T Tominii +d).
Note that information about /umas/L / leads to a better rate that in Theorem 5.2.
Remark 5.5. To simplify the rate (14), let c. be the RandK sparsifier and consider the case when the s2w communication is not slower than the w2s communication, i.e., 1/2. Then r
(max(1,(uu1])
12/3 1.99,,..
Temasd 1imass (w+1)
1,//21 Laman (w+11)3/2
[mmax((w+1)) 1 (w + 11) In- nn
max
1/1
Vana
deed, this follows from r & 1/2 and the fact that w +1 = d/k, for the RandK compressor: rd 1h = (1-r)Kutrk, I 1-r x d K_
< 2r (w +
Theoretical Comparison with Previous State of the Art
We show that the communication complexity of 2Direction always worse than that of EF21 DIANA and AGD. Crucially, in some regimes, it can be substantially better. Furthermore, show that if the s2w communication cost is zero (i.e., if 0), the 2Direction obtains the same communication complexity as ADIANA (Li et al., 2020) (see Section S).
Comparison with EF21 DIANA, The EF21-P DIANA method has the communication complexi- ties that equal
ma DEANA
θ (Kn, DEPII--DANAA + d)
and
&ee m
= θ (Ka TERLLS DEANA + d):
BERr P DIANA
IIt is sufficient to assume that + 2 (1/[k_)) It is sufficient assume that 2 (4/K...
8

---

where K and Ka are the expected densities of C. and C' in Algorithm 4. The last term comes from the fact that EF21-P + DIANA sends non-compressed vectors the initialization phase. Let us define K" (1 K + r r.a. Therefore, the total communication complexity equals
m BP2L NANA
è (K ap
whmox + w +d)
(15)
mp
Theorem 5.2 ensures that the total communication complexity of 2Direction
Kuia (V" //maxfu + 1,
Iimaci fw + +1, M
1 + w + Mes
I. Medisic
+
app
np
a
(16)
One can see that (16) is an accelerated rate; it has much better dependence on the condition numbers 4/4 and 4max/p. In Section E.8. we prove the following simple theorem, which means that 2Direction is not worse than EF21-P DIANA.
Theorem 6.1. For all E [0, 1], m
Ô (m (rn.e. DeAN.)
Comparison with AGD. To compare the abstract complexity (16) with the non-abstract complexity ((d /1)),, take the RandK and TopK compressors in Algorithm 1.
Theorem 6.2. For all r E [0, 1] and for all K E [d], let us take the RandK and TopK compressors with the parameters (expected densifies) i) K. K and K, min([1-r/ps (,d], for E [0, 1/2),
ii) K_, = min[["//-n/ [ and Ko = K for (1/2, 1]. Then we have masiii O (muen).
Theorem 6.2 states that the total communication complexity of 2Direction is not worse than that of AGD, It can be strictly better in the regimes when a > K/d (for TopK), Lmax < nL, and 1.
Proof Sketch
After we settle on the final version of Algorithm 1, the proof technique is pretty standard at the be- ginning (Li et al., 2020; Tyurin and Richtárik, 2023; Gruntkowska al., 2023). We proved descent lemma (Lemma E.4) and lemmas that control the convergences of auxiliary sequences (Lemmas E.5, E.6, E.7, E.8). Using these lemmas, we construct the Lyapunov function (45) with the coefficients R, p, À and Pa 0 for all t 0.
One of the main problems was to find appropriate L, K, P. À and i: 0 such that we get a con- vergence. In more details, to get converge it is sufficient to find L, K, p, À and V/2 2 0 such that (46), (47) and (48) hold. Using the symbolic computation SymPy library (Meurer al., 2017), we found appropriate not all. To get convergence, we also found the bounds on the parameter L, which essentially describe the speed of the convergence. In raw form, using symbolic computations, we obtained huge number of bounds on (see Sections I, J, L, N). was clear that most of them are redundant and it was required to find the essential ones. After a close look at the bounds on L, we found out that it sufficient to require (44) to ensure that all inequalities from Sections I, J. and N hold (see Section O for details).
p. À and 2 0 ((90), (88), (82), (83)) such that the inequalities hold. But that
Theorem 6.1 (No worse than EF21-P DIANA)
Theorem 1, (μ-strongly convex)
Theorem F.9 (Lyapanov Function Convergence)
Theorems 5.1, 5.2
comm. compl. and optimal p and
Theorem (general convex)
Theorem 6.2 (No worse than AGD)
Figure 1: Roadmap to resolution of Main Problem.
8 Limitations and Future Work
In contrast to Algorithm (EF21+DIANA) in which the server always broadcasts compressed vec- tors, in our Algorithm I (2Direction) the server needs to broadcast non-compressed vectors with

---

probability p (see Line 20). While in Section 6 we explain that this does not have an adverse effect on the theoretical communication complexity since p small, one may wonder whether it might be possible to achieve the same (or better) bounds as ours without having to resort to intermittent non-compressed broadcasts. This remains an open problem; possibly a challenging one. Another limitation comes from the fact that 2Direction requires more iterations than AGD in general (this is the case of all methods that reduce communication complexity). While, indeed, (10) can be higher than ( L/),, the total communication complexity of 2Direction is not worse than that AGD.
Acknowledgements
This work of P. Richtárik and A. Tyurin was supported by the KAUST Baseline Research Scheme (KAUST BRF) and the KAUST Extreme Computing Research Center (KAUST ECRC), and the work of P. Richtárik was supported by the SDAIA-KAUST Center of Excellence in Data Science and Artificial Intelligence (SDAIA-KAUSTAA AI).
References
Alistarh, D., Grubic, D., Li, J., Tomioka, R., and Vojnovic, M. (2017). QSGD: Communication- efficient SGD via gradient quantization and encoding. In Advances in Neural Information Pro- cessing Systems (NIPS), pages 1720.
Beznosikov, A., Horváth, S., Richtárik, P., and Safaryan, M. (2020). On biased compression for distributed learning, arXiv preprint MXXi:2002..22411
Chang, C.-C. and Lin, C.-J. (2011). LIBSVM: a library for support vector machines. ACM Trans- actions on Intelligent Systems and Technology 2(3)1127.
Condat, L. and Richtárik, P. (2022). Murana: A generic framework for stochastic variance-reduced optimization. In Mathematical and Scientific Machine Learning, pages 81-96. PMLR.
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.
Gorbunov, E., Hanzely, F., and Richtárik, P. (2020). A unified theory of SGD: Variance reduction, sampling, quantization and coordinate descent. In International Conference on Artificial Intelli- gence and Statistics, pages 680-690 09-690. PMLR.
Gruntkowska, K., Tyurin, A., and Richtárik, (2023). EF21-P and friends: Improved theoreti- cal communication complexity for distributed optimization with bidirectional compression. In International Conference on Machine Learning.
Kairouz, P., McMahan, H. B., Avent, B., Bellet, A., Bennis, M., Bhagoji, A. N., Bonawitz, K., Charles, Z., Cormode, G., Cummings, R., et al. (2021). Advances and open problems in federated learning. Foundations and Trends@ Machine Learning, 14(1-2):1-210.
Konečný, J. McMahan, H. B., Yu, F. X., Richtárik, P., Suresh, A. T., and Bacon, D. (2016). Federated learning: Strategies for improving communication efficiency. arXiv preprint arX1v:1610.05492.
Kovalev, D., Horváth, S., and Richtárík, (2020). Don't 't jump through hoops and remove those loops: Svrg and katyusha are better without the outer loop. In Algorithmic Learning Theory, pages 451-467. PMLR.
Krizhevsky, A., Hinton, G., et al. (2009). Learning multiple layers of features from tiny images. Technical report, University of Toronto, Toronto.
Lan, G. (2020). First-order and stochastic optimization methods for machine learning. Springer.
Lan, G., Li, Z., and Zhou, Y. (2019). A unified variance-reduced accelerated gradient method for convex optimization. Advances in Neural Information Processing Systems, 32.
Li, 7.., Kovalev, D., Qian, X., and Richtárik, P. (2020). Acceleration for compressed gradient descent in distributed and federated optimization. In International Conference on Machine Learning.
10

---

Li, Z. and Richtárik, P. (2021). CANITA: Faster rates for distributed convex optimization with communication compression. Advances Neural Information Processing Systems, 34:13770- 13781.
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.
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.
Meurer, A., Smith, C. P., Paprocki, M., Čertík, O., Kirpichev, S. B., Rocklin, M., Kumar, A., Ivanov, S., Moore, K., Singh, S., Rathnayake, T., Vig, S., Granger, B. E., Muller, R. P. Bonazzi, F., Gupta, H., Vats, S., Johansson, F., Pedregosa, F,, Curry, M. J., Terrel, A. R., Roučka, v., Saboo, A., Fernando, I., Kulal, S., Cimrman, R., and Scopatz, A. (2017). Sympy: symbolic computing in python. PeerJ Computer Science, 3:e103.
Mishchenko, K., Gorbunov, E., Takáč, M., and Richtárik, P. (2019). Distributed learning with compressed gradient differences. arXiv preprint arXiv: 0ee.1191199000 09269.
Nesterov, Y. (2018). Lectures on convex optimization, volume 137. Springer.
Philippenko, C. and Dieuleveut, A. (2020). Artemis: tight convergence guarantees for bidirectional compression in federated learning. arXiv preprint arXiv:2006. /459/.
Philippenko, C. and Dieuleveut, (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. arXiv preprint arXiv:2102.12092.
Richtárik, P., Sokolov, I., and Fatkhullin, I. (2021). EF21: A new, simpler, theoretically better, and practically faster error feedback. In Neural Information Processing 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.
Stonyakin, F., Tyurin, A., Gasnikov, A., Dvurechensky, P., Agafonov, A.. Dvinskikh, D., Alkousa, M., Pasechnyuk, D., Artamonov, S.. and Piskunova, V. (2021). Inexact model: a framework for optimization and variational inequalities. Optimization Methods and Software, 36(6): 120-
Tang, H., Lian, X., Yu, C.,, Zhang, T., and Liu, J. (2020). DoubleSqueeze: Parallel stochastic gradient descent with double-pass ervor-compensated compression. In Proceedings of the 36th International Conference on Machine Learning (ICML).
Tyurin, A. and Richtárik, P. (2023). DASHA: Distributed nonconvex optimization with communi-
cation compression and optimal oracle complexity. International Conference on Learning Repre- sentations (ICLR).

---

Appendix
Contents
Introduction
1.1
The problem
1.2
Assumptions
2
Motivation: From Unidirectional to Bidirectional Compression
2.1
Compression mappings
2.2
Unidirectional (i.e., w2s) compression
2.3
Bidirectional (i.e., w2s and s2w) compression
3
Contributions
New Method: 2Direction
Theoretical Communication Complexity of 2Direction
5.1
The ratio Lmxx/L / is not known
5.2
The ratio L.ma//L is known
8
6 Theoretical Comparison with Previous State of the Art
7 Proof Sketch
8 Limitations and Future Work
A Table of Notations
14
B The Original ADIANA Algorithm
14
C The Original EF21-P DIANA Algorithm
15
Useful Identities and Inequalities
15
Proofs of Theorems
15
E.1 Analysis of learning rates
15
E,2 Generic lemmas
19
E,3
Construction the Lyapunov function
24
E,4
Main theorem
29
E.5
Strongly-convex case
34
E,6
General convex case
35
E.7
Choosing optimal parameters
36
E.8
Comparison with EF21 DIANA
40
12

---

E,9 Comparison with AGD
40
Auxillary Inequalities For L
G Proof of Lemma E.10 (First Symbolically Computed)
43
H Proof of Lemma E.11 (Second Symbolically Computed)
44
I Symbolically Computed Constraints for Such That The Term w.r.t is less equal 1/2 in (87)
45
J Symbolically Computed Constraints for L Such That The Term w.r.t is less equal 1/2 in (89)
46
K Symbolically Computed Expression (91)
46
Symbolically Computed Constraints for L Such That The Inequality from Section K Holds
49
M Symbolically Computed Expression (92)
54
N Symbolically Computed Constraints for L Such That The Inequality from Section M Holds
55
0 Symbolical Check That The Constraints from Sections I, J, L and N Follow From The Constraint (44)
57
P Jupyter Notebook for Symbolic Computations
63
P.1 File utils.py
68
Experiments
71
Q.1 Setup
Q.2 Results
R Convergence Rate of CANITA obtained by Li and Richtárik (2021)
72
Comparison with ADIANA
72
13

---

A Table of Notations
Notation
Meaning
9 O0)
Exist C such that g(z) C [(2] for all E 2
g = ((
Exist C such that g(z) 2 C x f(2) for all E Z
9 ((f)
-= (f) and = St())
9 = 0()
Exist C > such that g(²) S C [[z) x log(poly(z)) for all
9 = (()
Exist C > such that g(z) 2 C x f(=) x log(poly(z)) for all : E
9 = (
g = (f) and g = ft(f)
0, (a.....U)
Set (i E b)
(!.
B The Original ADIANA Algorithm
In this section, we present the ADIANA algorithm from (Li et al., 2020). In the following method, the notations, parameterization, and order of steps can be slightly different, but the general idea is the same.
Algorithm Accelerated DIANA (ADIANA) by Li et al. (2020)
1: Parameters: Lipschitz-like parameter > O, strong-convexity parameter 2 probability p. parameter To, initial point 2²" E IR initial gradient shifts h. ... bg R Initialize
1/w+1 and 20
=x
3: Initialize Ao - h
4: for t = 0, 1,..,., do
5: Tr-1, 7++1, 0,-1 CalculateOriginall .wa.ggaall..mmiinattts(.....)))
6: for -..-.,,, parallel do
y²+1 1441 + 0++1)=
8:
m -cP.v (Vfi k()
Worker compresses gradient compressor c U(W)
9:
Send compressed message mf*" to the server
10:
end for
n 1 n
m;
Server averages the messages
12:
g h''
+ m 1.
-5 E (hf + m.
13:
4 arg min
(g
41
x) + 2res1
|| - w/11 11 4112
Server does gradient like descent
step
14:
Flip a coin c' ~ Bernoulli(p)
15:
Broadcast non-compressed messages of to all workers
16:
for I,..., n in parallel do
17:
x² = 00+14" +
02+1)2
x x111
=1
18:
241
d=
19:
m. c. (V h9)
Worker compresses shifted gradient the compressor C U(w)
20:
h. = h 3m
Update the control variables
21:
Scnd compressed message m to the server
22:
end for
23: h++1 h' + 3 Σr m
Server averages the messages
24: end for
14

---

C The Original EF21-P + DIANA Algorithm
In this section, we present the EF21-P + DIANA algorithm from (Gruntkowska et al., 2023). In the following method, the notations, parameterization, and order of steps can be slightly different, but the general idea is the same.
Algorithm EF21-P DIANA by Gruntkowska et (2023)
1: Parameters: learning rates 7 > 0 and B > 0, initial model u² E R initial gradient shifts hi. ... 1% E R. average of the initial gradient shifts ht" Σi= M. initial model shift w" = u E R do for I...................... n parallel
2: for t 0, 0,
4:
m = C. (V Send compressed message m. to the server h h + Bm!
Worker compresses the shifted gradient via the dual compressor CPP C U(w)
5:
6:
Worker i updates local gradient shift with stepsize
7:
end for
mi' n
= m
Server averages the n messages received from workers Server updates the average gradient so A Eis Ag Server computes the gradient estimator
9:
h441 h' + 3m
g' h² + m
11:
u 4+ u' - 79
Server takes a gradient-type step with stepsize 7y Server compresses the shifted model via the primal compressor e B (a)
12:
pttl Cº (u"
w²)
13:
w = w² +p'+1
Server updates the model shift
14:
Broadcast compressed message p all n workers
15:
for i = L...,, in parallel do
16:
w0 w
Worker updates local copy model
17:
end for
18:
end for
D Useful Identities and Inequalities
For all x, y, 21....,
, In E RR > 0 and a E (0, 1]. we have:
| y1
(1 5) |== + (1+ 1 |121
(17)
|| + 2/1 < 2 ||x]| 2 + |
(18)
|
s slyl
(x.y)
(19)
2s
(1 a)
1 a
<
(20)
2
2
(1 (1-a) a)
1
$ -
(21)
a
1 [Iall + +|b|| ||a (|a-)
(a,
(22)
Variance decomposition:
For any random vector X E IR and any non-random c E Rd, we have
E ||x
<|1 E [IX-1 + [|[[x]-
E[X]]
(23)
Lemma D.1 (Nesterov (2018)). Let f Rd + be a function for which Assumptions 1.2 and 1.3 satisfied. Then for all x, y Ed we have:
Vf(x) - vf(m) < 2L(f(x) - f(v) - (V 3)).
(24)
E Proofs of Theorems
E.1 Analysis of learning rates
In this section, we establish inequalities for the sequences from Algorithm 2.
15

---

Lemma E.1. Suppose that parameter L > O, cooonnccyy parameter μ 2 0, probability E
(0,1), 2 μ. and To 2 Then the sequences generated by Algoritim have the following
properties:
The quantities O141; N41, and T 141 are well-defined and O1-1: 7+1 2 0 for all 2
2. 744 p0r+11 1 141 for all 2
3. 10 - (L + +,)) for all 2
4.
T1 2
To exp
2
mmin {
{V
4L
PH
p0
})
for all 1 O.
5.
Fe
exp (tpo min
t i
2
T; 2
p(e-F)
t 2 I.
Iprl
1.0]
where == max
log 2Topot
p9mm
min
6. {0++1)12 a non-increasing sequence.
Proof.
1. Note that Oe+1 the largest root of
pLr,0041 + p(L T.m)0+41 (1+)) O.
(25)
We fix t 0. Assume that r, > 0.
Then
pīr, 0 p(I +Tp) x (I 0.
Therefore, the largest root 0.+1 is well-defined and 0.+1 2 0, and 0c+1 min(Oc+1, mmin 2 O. Next, 7+11 is well-defined and
7+11 p - (1 20 0
since p0++1 E [0, 7/4. Finally, T++1 = I + 7++1 > O. We showed that, for all 2 0, P. 0, then O.+1, h+41 2 0 and 1'+1 O. Note that To O, thus Oz+1, 70+1 2 0 and
T(+1 > for all 2 0.
2. From the definition of 7+t and 1++1, we have
(1 (0++1))111 p0c+1l's,
which is equivalent to
7+1 = p0++1 (T + x+11) = p0
3. Recall again that 8e 0 is the largest root of
pLr,0 + p(L Te440.+1 + - (Ieu = O.
If 0(+1 S minn then
pLr + p[T + TTu)00+11 - (I. (I. TTp) = 0.
Otherwise, if 0.41
Omin since
pïr, x 0 P(L + Teps) x 0 (L + T(p) 0.
16

---

and B1t1 8min < <B4+1, then
pT.T,00 + p(T. + Te - (I. + T.uu) S O. In all cases, the inequality (26) holds. From this inequality, we can get
(26)
pLr,0 S (L P(x) (1-00++1)
and
poc+iTe
L8 (1 (1-pol (1-p)) - (T+t
Using the definition of 7 obtain
100417141 S (T. + Tep)
for all t 2 0.
4. Let us find the largest root of the quadratic equation (25):
0++1= == -p p(L + Tet) + V + Tim)² + 4pLI',(L + Tip)
(27)
2pI.r,
Let define p² (I+ and b b:= 4Lp (L + +Tp) Te. then
041 -Va + va+b
2TpT.
Since r 2 1 for all t t2 0, and L 2 n. we have
a a= p= p² [L m (L + r.p)² 2 (L [L+I (T,L+ +.p) s 2Lp
I,
b
2"
Using vI セ Z (Vz + vD) //2 for all x, y. 2 0. and vb 2 v2 we have
0.t1 = -va + Va+b b 2
- =va+ v2 V + 1 Vb
2Lp,, t
2Lpr, ;
(/22 - 1) Va + 1
1
vb
vb
vb
v2 v2
v2
v22
2Lpr
2Lpr;
4Lpr,
Therefore
ATy (1++
(L + (Tmm)
1
max {V 4pl'' V
4LpTe
4LpT,
4pT.
and
{VarTT V 4pT.
1 4pT,"
Omin )
O.11 > min max
(28)
Next, since p0++1 E 2/4), we have
7+41 p0,+ I', (1((1 p0++1) 2 -00+1I1e (1 +p00+1)
(29)
and
T := re+ 7+11 2 p1+p8
p01+ + -p20 Tt.
Using (28) and (29), we obtain
/
1)
{ PJ
p0min }) rr
Pe+1 2
1 + pmmmmi
Omin
1 [++min/
min
(V
4pL
(1
4L
{
Pp
6+1
> To
(v
PH
}).
2 To
1 + min
(V
4T. 4T, 1.,ppmmi.
p0
2
exp
(t min
4T."
p0mmu
(30)
where that 1 et /2 for all E [0, 1].
17

---

5. Using (28) and (29), we have
T'+1 2 (1+ pl++1 + +2202+2 L':
2 P. + pmin {V {V4D):
2
6 mmn
r. + p² min
Omin
rτ.
4pl's
4pl's
The sequence 1++41 is strongly increasing. Thus, exists the minimal (4p0)))) For all 0 E it holds that I' < (4pol
such that F3 2
minn and
V
Apt.
Tu
T441 2T pomin + p²0e mi 2 r - p0mi 2 To (1 + pdmin)) |-1
2 2
exp ((t + 1)pmmin).
(31)
Therefore, if 0, then
To
7-1 z
exp (ai 1)p0min).
4p02 min
2
Thus, we have the following bound for T:
T == max
log
.0
p0min
2r Topos min
For all t 2 f, we have
V
4pt. S mmin and
1
2 // 2.
2 le T
4pf l' + p
T. = le+
4pl'
Using mathematical induction, let us show that
p(t - 8)2
re
(32)
4p02 min
16
for all 2 E. For / = Fit it is true since 1; some 2 E, assume that (32) holds, then
Ap0
by the definition of ł. Next, for
Dp
T411 2 r
T
p(t - 2)2
VP
p(t - 7)2
p
+
4p62
16
4p82 min
16
4
p(t - 8)2
p(t
+
4p02 min
16
8
p(t 8 1)²
4p02 min
16
We proved the inequality using mathematical induction. Combining (31) and (32), we obtain the unified incquality for T.:
( To 2
p(t 7)2
D 2 min
exp (tp0min),
4p02 P
16
for all Also, if E, then the first term the minimum is less equal than the second one. Therefore,
Fe exp (1p0min),
<<> T
r. 2
min
Te exp (1p0min) , App2 + p(e-7)²
{ 1 T.
(33)
18

---

Let us bound the second term. Recall that f 2 E, thus, if 2 E, then (t- 2 (t - -)2. In (33), we can change to i and get
La exp (tplmin),
t t<t
T2
min
To exp (tp0 4y00 + p(c-0)
t2t. t.
Using the Taylor expansion of the exponent at the point t, we get
To
To
To p p20 min exp (tpo min)
(t ( f)2
exp (tp@min) 2 exp (tp0min)
2
2
2
p. (t [t2²
1
+
P
(t 8)?
4p02 min
4p02 min
16
for all t 2 f. Finally, we can conclude that
Ia exp (tpl min)
t i
T2
p(t-D)²
t 2
4p0 min
6. Let rewrite (27):
o++1 = -p(L + T(p) + vD2(L + rip)² + 4 Tass)
2pIrr
- 1 1 Ft L
1 r.
+ L 1
1
:)
+ V
Pe
Let us temporarily denote 0e = 1/2 + 7. for all t 2 0. Note that a is a non-increasing sequence, since T2+1 2 r' for all 2 Therefore,
1
0.+1 = 2 ag +
V 4 0 ac.
Let us take the derivative of the last term w.r.t. at and compare it to zero:
2 aa
+ p
1
1
+
20
a1
+
2
2
+
at
2
2 2
2 +
Las
4
P
+
2
20 0.
p
p
4
pa
Thus, 0e+1 is a non-decreasing sequence w.r.t. az. But the sequence or is non-increasing, therefore 0.41 is non-increasing sequence w.r.t. t. It left use that 02+1 the minimum of Oc+1 and the constant quantity.
E.2
Generic lemmas
First, we prove well-known lemma from the theory of accelerated methods (Lan, 2020; Stonyakin et al., 2021). Lemma E.2. Let us take vectors a, b, g E Rdd numerical quantities a, 0, and
u = arg min (g. x)
+ a || all + 2 || - -b12.
rgRd
2
Then
(g,4) + C || - all2 +
3 || b112 2 (g. u)
+ α
||u
al
2
+
||u
b11
+
( +
|
u
2
2
2
2
2
(34)
for all x E Rdd.
19

---

Proof. A function
f(x) = (g. x))
a
|| all² +
1 b1l
strongly-convex with the parameter a + 3. From the strong-convexity and the optimality of u, we
obtain
f(x) 2 f(u)+ (f(u), --)
a B || ull f(u)
ar +
|| ull
2
2
for all x E Rd. This inequality equivalent to (34).
We assume that the conditional expectation [2 [] is conditioned the randomness from the first iterations. Also, let us define Dy (x. = f(x) f(y) (V) y)-
Lemma E.3. Suppose that Assumptions 1.2, 1.1, 1.3 and 2.4 hold. For Algorithm 1, the following inequality holds:
E
[19
V fl f(y*+t)11
2w Vfi(=))
Aill2 +
4w Lmxx
- -
(35)
2
Proof.
Using the definition of gh+l, we have
||g r+
ffy ||]]
1t' +
c CD (V - 11) (
1=1
cD MD) (VS()(t)) n:) [|]
n²
where use the independence and the unbiasedness of the compressors (see Assumption 2.4).
Using Definition 2.3 and Assumption 1.1, we have
Eg
119 g
VS( /() 1-]
V +1 k?1?
(18) 2w
2w n n
$
f Vi((st))1?
n
L.D.1
2w
2w
Vf((2') 111l
2L((f(22) - - -1
n
Using that Liax maxie([] Li, we obtain (35).
Lemma E.4. Suppose that Assumptions 1.2, 1.1, 1.3 and 2.4 hold. For Algorithu 1, the following inequality holds:
E4 [ - [(x²)]
(1 p0c+1) (f(z') f(x)))
2pw
1
hhg V1((E)112)
nI
11 i=1
[
L + Tet1ll Es || 112]
+ +p0c+1
||ue 2¹112
27/41
27+11
20

---

4ww 4ww Bc41 - 1)
+ p
Dj (2' .
nL
pl Et |||att- - pb8 I
+
2 R2
2
Proof. Using Assumption 1.2, we have
((x)) -(0))) x: - - + L
- || - 11
2
Using the definition of xt+1, we obtain
-
-(x² S (1 0 (1 - (VI('++)) 1 + Oct1 ----)>>())))))
[(x)) +
(V/())t)), -
L ||alt|- - -1/t112
= -(1 0141) (1(1 - -1xx)) ) + (VS(s(t)) - ,)t11)
(36)
+ Oc+i (I(y' - -((x)) + (g , - ((t1))
Oct1 (v)()(+)) - gg net1 - - v(t1))
1 || - 1|
L
2
in the last inequality we add and subtract g gh+l Using the definition of u and Lemma E.2 with x = x², we have
L Tej4
(g' w0tl -1(t1) s (g x² -
| 12²12
11 =110" y 112
2
L + T'M |
w²12
1
uu¹ 42 112
L + I I1
11 2/1
2/++1
2
2
We use the fact that [++1= TT 7-1- Since 1lu'-y" -ytt2
2 0, we have
L Tipl
agtt,utt - t S (g xx - g(tl) + 271+1
1| - u²ll
+ 1
2 1| +12
L + Teft || - -ull?
L + l'ot1l
|| - -u(t1( 111
2
27441
By substituting this inequality to (36), we get
f(x(+1)- - f(xx)
5 (1--0+1) (1()/+1) + (VS(' - )/
+ +0++ (1() - -(x') + (g ,x' 1/ (1))
L [L+ 11 1
L + Tej1 I - ud1
L Pe+1lt 1x 1x-- 111)
ul11 + ~/2 1|0" - -
+ 0c+1
271+1
2
2
+ Mc+1
((V((y(+)
-g w - -
T,
|att1 - y 111
+ 2
Using p-strong convexity, we have
f(x)) (2)2$60 + 1
H 2 1100- 1
and
f(x - -f(x))
I (1 - 0c+1) (f(y+t)- )
- +1)))
21

---

+ +0++ ((g (f(((t1),2* -1(t1))
+ +0+1
L L++
2i+++1 1| -2²11= I+ Taft | v²12= 2=-
L+ + T T(+1 2-e-1
- x 112
27++1
+ 0c+1
(VV (z) -gg g²² ,utt1 - y
L
+ -1 112
Let us take the conditional expectation E2, [+] conditioned on the randomness from the first t itera- tions:
E. [f(x+1) [(x))]
$ (1 ((+1) -
f(x") + (VI(('+)), -1 -
+ 02t1
((E, [g [1(l)++)]] ,2" - g2t11)
T. Te
270+1 1| ||--
I T Es
[1/ - rd'11]]
+ Te+1ll
E, |||2* - n 1(+)
+ M++1
270+1
2
+ Oc+1
E.
[[V (+1) D +1 1t y y1t
L
|||a4t| 1 - -1² 11
+ 2
Et
(1 1(+1)
(f( f(x") + (V]()++)), -
L L+ - L+ I E, |1 wd'1?]
L + To+1/4 Ey
|| n - w(+)
Oc+1
27++1
270+1
2n+1
0z+1
R2,
[V +11 9 1+1 g -1 y 1
L,
|||att]
y/ 21(
Et
2
(37)
where use that E. [g ())+ We can find w analytically and obtain that
w++1 + Tef w' + p7++1 11
7e+1 g++l L ++ L+
L L+I4+1
Pe+1
Therefore, using that E2 [g+t]] (1( and u² and t are conditionally nonrandom, we obtain
E2 [V g at ++1 1-t1-yt11 [
7++ Eg [1g
v 1|
(38)
+ 141l
Combining (35) from Lemma E.3 with (37) and (38), get
E, [f())t1) f(x")]
$ (1 - l441) ( (( -
ff(x)))x)
TeN -u'l
L+ L+T E,
[| u9133]
L P Te+1l E, ||00 1100- -uat 111)
+ 0++1
27441
2
2
0c4176+1
12w Σ V -hil2 4w.mmxx (f(z*) ff(((t2) - - ((11))
+ L. + D 11
n2 1=1
L
E,
2
22

---

Using the notation (, = -lo (Vf(v). v), we get
E. [f f(x')]
(1 04+1) (f(z9) - f(xxx( ) -(("")
I -w'l L+ Es || w011²]
L + r 2
[| - -
+ 0c+1
27++1
27++1
27+
14417611
2w
n V -hil2 + AwLmax 12 (22,,y(t1)
+ L L+T++1
112 1=1
L Et ||
-
2
= (1 1c+1) (f(2') - f(xx))
04117411 2w n
|| [((('²²)) - nill?
+ L + T++H n
i=1
L L+
L+ Tet2l1 Es - 11))
+ +0+1
-wll"
270+1
27++1
04417441
AwImaax + +1++1 1c+1-11 -1
+
Dy(2'
L I+Te2
L Et (1la+t--/++100
Be+1 (L Tess)
Eg [||ott] u² -=]
2
27++1
In the last equality, we simply regrouped the terms. Using the definition of et+1, we get
E. [1(= - [(x))] plE,, [f(x(t]) - [(x))] + p) (s(=') [(xx))
I p(1 0(+1) -((5)-ffic (((=))-((x'))
1.+17 2w 1 n + P I + Te41/1 n
Σ V nall"
n
L+I
L+ Tetill E, [| - -
+ +
1|-- - u2ll²
270+1
274+1
04417441
AwTmmax + +ct1 -
+ P
L+I n
pL E,
(latt-y/tlp
poz+1
(L + [+1t)
Ee ||lutt--dd) -d'111] (1- p) (f(( f(x)))
2
270+1
(1 -00+11 (f(z')- - ff(x))
0st1 2w
V(((2') - -nll2)
P
L Te41H n
L+ Te+1ll E,
+ +p0++1
||-- w'l²"
wtt (1a=-)++11())
2//+1
270+1
04417+41 4wTmmxx + B1+1 - 1) Dy(at.8'11)
+ p
L + n
PL
[1]] pdr+1 (L + T(t4)
E1
|| ++
1E |||et1 n
2
270+1
In the last equality, we grouped the terms with ff()) In Algorithm 2, we choose the learning rates so that (see Lemma E.
10 I Tmp.
Since T 2 T, for all t E No, thus
0417741
0
<
<
L + 1-TT4P
L L+ Teu
L
23

---

and
E, [f(= - f(x))]
$ (1 p0(+1) ( -(x=)))(x=))))
2w + p TL
[ - -ntll?)
i=1
pd1+1
T. T.+Tall
||at ||-- -w'l1
T. + D T4+1l1
Er || w 11]]
23/+11
2441
Aw Lwwxmax 0c+1 -1) Dy(z", x2
p
nT.
pL +
Et
||
111
p0f I.
18
- -1.
||| -0-1--u111
2
2
E.3
Construction the Lyapunov function
In this section, we provide lemmas that will help to construct Lyapunov function.
Lemma E.5. Suppose that Assumptions 1.2, I.I, 1.3 and 2.4 hold. The parameter B I 1/w+1. Then, for Algorithm 1, the following inequality holds:
++ -
E,
(39)
T1
Sp
11 1+
T.max (3 (2t) 4p 1 P 1.7R,
[|
-121)
(1
B
M - VS((=')11
72 1=1
(40)
Proof. Using the definition of h [+1 we have
E
M ++
h$ + sc (V (.(((tttt) - -A - //
E,
| v yll
E,
23
-h3) h V/i(z C, -()))))))))))))))))))))))))))))) + 32 -
E,
Note that Eg (V):((((() nd)] V/((z(t1) h1 and
Ec
II - -nt))
(w (w (w 1 - - -
where Ee | is conditional expectation that is conditioned on =+1 and h4 Therefore,
| + (
n
< E,
| - v/1(=
24

---

2 (h)
f)( Vf((z!(1)= - hbt + 8l +1)
f -
T2
n
(1 233 +
E
| v
Since 3 s 1/ we have
- V <1 - 33TB, IR+
Σ | v
E
Next, we use the definition of 2 ++1 and obtain
E2
++
\)(
1=1
114- - \/( (11-B) 1 |
$ (1 - B) pE
n i=1
==1
(17)
S (1+ 2p)
- -
+ (1+ ( (1 - 3) 1 Σ
(1 - B) p
3
1
+ (1 - B) (1 - p)
|| v
- -(1+ 1+ 2p>
(1 B3 pE,
-
+(1 3) 1+ () 1 m
1 - | [)(
-
2 n
Using
1- 3 1, (18) and (20), we get
| (1(
E,
1=1
S 4p
1+
p
[a((*)) - (/(0011111 + 4p 1 P) E,
Σ
-
-
3) 1=1
3
9
| - V
2
n
From Assumptions 1.1 and 1.3 and Lemma D.I, we obtain
E2
M++1
p
Tumax (f(=')- (V/6tt))))) + +4p (1+
p 3
1. -|ttt1
Sp
1
++3
3
3
+
1
2
i=1
=8p
11
p
Lunax 0,(',,''+)) + 4p 1 p
i.E,, ||a2t1-
+ +11- =) n ΣΣ
| - ))
3
3
25

---

Lemma E.6. Suppose that Assumptions 1.2, 1.1, 1.3 and 2.4 hold. Then, for Algorithm 1, the following inequality holds:
2
Er ||
- s (1
2 1/00 - -u'12 a
②)
744
|1'-
L - 1(+1
2w 70+1
Vfi(2') ntll"
n++1
2 (AwLmax
8L a
Dy Dy(2',u
n
1++ 1++11
T T1+11u
(41)
Proof.
Using the definition of w and Definition 2.2, we get the following inequality
Eg
- E, ||ce (u - - (u - (1+) S S
a)
[| -0t1111 11]]
We can find the analytical formulas for u(t1 and gt+1, and obtain that
+ Tup u'
2++1_
pr++1 1+1 7+41
g 1+1
L L+ TTTH
L T+T4+
1+14+1
and
L + Tm
d+t
w + 17411
y/+1
7++1 kC
L T+41
L Pe+1m
L
Te+14
Therefore,
16, || 16-1-==" 111
+ Tije
(w- u²) L P4+1l
70+1 (k' g(+11)
L + I 1441
(23)
a)
+ Peje
(w
-w') -I
7++1 (k' (K-- -Vf(yt+))
7 P441k
2
+ (11-a) a)
7+1
E, |1|gtt| -ffl
(17)
2 (1 )
L + TiMe
2
1 -u11² +
I. + M+4
|| 1150- (
+ [+41
2
+(1 a.)
70+1
Er -1104H--/6(
L+Tr-14
(18)
(1 2)
T Tell
1 -w'll
w'll?
[L+T
4
7411
Σ + Tetil1
4
7411
2
|V/((=)) \)
a
L+ + T
2
(1 a)
7041
E,
-
||00
One can substitute (35) from Lemma E.3 to the last inequality and get
- -utt113 |1
E,
< (1 2) ( T. re+1pp)
T. Teje ) 11w'- - uu'l
+ a
4
741
2
-V(2))11
I + T(41//
26

---

4
7441
||V
+ a
L ++ 1++11+1P/
+ (1 a)
7+41
2w
[V((=*) n1ll? +
Lw Dy(e",
L+I U+1++111
n i=1
Using Lemma D.1 and 1- - a S 1, we obtain
E ||
- | =1
$ (1 1 2) 2)
a)
(
L LTH
2 1| - =u'l
T. T1+T++114
4
7++1
a
+ +T4111//
2
7t11
1 Vf((=*) -All²=
(L+T+ti) "
n+1
(AweLmax +
8L Dy 12(2'11tt)
L+I 1++++11
n
||ui - =21
4
n++1
1 -V(=))?
I+
0:
2w
7tt1
2
n
V -acc))-hhh n:ll + (
9+11
2 (Aw
8L. + a Dy Dy
+
(T.4
n
n
im1
where we use that T'+1 2 Pe for all t 2 0.
Lemma E.7. Suppose that Assumptions 1.2 and 1.3 hold. Then, for Algorithm the following inequality holds:
Eg | (1(=++))111)
< 2pEx [1ue - |/( + 8pLD, (=' 1) + E,L'E, [| - y + + +11- llke - ?)(
(42)
Proof. Note that 1.++1 and 1(+1 are coupled by the same random variable c¹. Therefore,
Ex || - -[[(
||(
PE [1|2* v)(x++1) >|>]
+ (1- -
(18)
- 2pTB2 [11e --s(=>)
4p ///=\) - V/ - 4pE, [|V -VS(att))
+ (1 - p) |1at {)()))
$ 2pE, ||0e - Vf(('))l |1* + SpLD, .....//) g- + 4pL |||55|| - - + (1 - p) 11 {
where we use Assumptions 1.2 and Lemma D.1.
Lemma E.8. Suppose that Assumptions 1.2, 1.1 and 1.3 hold. The momentum (0. 1] and the probability p E (0, 1]. Then, for Algorithm 1, the following inequality holds:
Es || -V 1²]
(1- )) -Vf(+)12++++ + 272w n
Σ
1 vi((2)))12
+ Ap 1+ (4p(1+
+<4p
2p) ) r. Spr
Dy(2*, y(1) +
2pp
(pp 2p 1+
I? +
4pr
Ey -11ltti-
-
n
n
(43)
27

---

Proof.
Using the definition of v'+1, we get
Be - E.
(a- 7)--)) T)O' + h2' IC :.= (V -ht) n1) v
Assumption 2.4, including the independence and the unbiasedness of the compressors, insures that
Es [|otti-v((*'
(23) (1 - Ze -V
E +
co. cP. (VSi(= -1) 13) -
-V -)))
(1 T) ||10 (V
n² Σ E+
72 m
cop. (V - n.) (V - -m311(]
< (1 - " [lbe - v [|]]
T"
[|V - -n!l
E,
n² 1=1
Using the definition of 2+1,, we have
Ee || - \/( ||"
(1 - () - p) 1|00 - vf('")| + +11-7)3pB [lle* 1 -
(1- p) Σ
|14 - vf((=b)1 + prpw
Σ We ||1n5 - v Sa [1
112
n12
1=1
(17) 1
(1 -1-77 --)))(1-1 (p1-pp][
p/ p))
p 1100 \)(())|| + (1- 7)2 (1+ 220) yad [[]()))) - v)(
+ (1 - 7)2
1 + 2p/
(1 2w
n
||0|- V)((
n²
2pr ww
Σ
n
Es [||1] V []
2
Σ
E. [[ - - |
n1
n²
1=1
(1 7)3 (1+ 2) 1 |)(=))) + (1 -7)2
1+
2p
pIz [|V)(= - v ||]
+ (1 + p)
Σ
||4 vf( + 2p
Ee [|V
n2
n²
1=1
Using 0 5 -1--51
S 1,pe E (0, 1] and (0 we get
E. 11 - ||a]
< (1- ;) 110- v((21)]++ + (1 1
2p) p., [| - v
2w
Σ || v<(>>\|> + 2p
B. || - vA(a+t1117]
+ ??
n²
1=1
(18)
S (1 (1- () |
+ 2p 1+ -
|| - [ + +2p
1+ ) E, || - -
28

---

2
|
2
t=1
4p w
4pT w n²
E
n
is left to use Assumptions 1.2 and with Lemma D.I to obtain
E.
T)
2) 10'- V
+ 2p
12) 2p 1 2p ) L L2 11 =2
+ 4p
LD,
7
| v)((=')1
2
8pr
wLLax
Dy (2x1,"tt)) + 4pr wI2
By -
272w
(1 )/
||'¹ v)(=t)|(
+
116 {
n²
+ 4p 1+ 2p"
L +
Spr Swr
Pr(k'.yeth) + 2p (1( 1+ 2p
2 +
4p up?
E, || y0+211]
E,4 Main theorem
Theorem E.9. Suppose that Assumptions 1.2, 1.1, 1.3, 2.4 hold. Let
L Lp a ar'
VII.maPP
VLLmax VDVUT
Imnaxlop
Lunazw
L 660508 x max
g. (44)
aB/n
a/3//n
B2n
w4I and Omnn = min 1,
8 p
For all t 0, Algoriithm 1 guarantees that
Pi+1
[ff(tt+)) - f(x")] RE
| - -
12+1112)
I + T2+1l1 E8
+pl 1 (((2++1)11
+ AE
1 -
|1 - -x-11 x11
2
< re
E [f(2)) - f(x²)] + <E
h V
+ +wE
I|we 20113]
PE |||. { AE [11'~</(>))f
+ T.ll B
|| - -0-1''11 ==1
+
2
(45)
for some R, p. X, vt 2 0.
Proof. We fix some constants K, 0, X, v4 2 0 for all / 2 O that we define later. By combining Lemma E.4 with (39) from Lemma E.5, V (41) from Lemma E.6, p (42) from Lemma E.7, and X x (43) from Lemma E.8, we get the following inequality:
n
E, [f( - f(x')] + K,,
1+42 111(2+1))11 + V. |1100 2 411
29

---

+ p ||6441 (1 AB [l04t [)(2+t))1²]
5 (1 -000+11)1 (f(z²) - -(x)))
2pu
m - V
+ nL
71
==1
L Tefe |1' - x112
L + Te+1ll Be -
- 1'])
+ +p0++1
270+1
270+1
4w
+ +0++1 -1) 1141-1)
P)(2'.y/t))
+
n2
pL
||al - |||/ -11+111
11]] DOZ+1L L Es [|12tt1 1ol1-2"
[|1==tt-==(] -22ll]]
2
P B
Timax Ds(5',y .ytt) + +4p
+ 1+
P. T.21,, -1=111))++111) + 21-2)
1 n
Σ 1 vA(Ee))))
+
8p
1
33
(1 (1-2) a)
4 1|w6 will
7o+1
|['-~V[(=')]
+ 14
2)
a
L L+
2w
7++1
1
70+1 ) [[V/((=))- -h(l" -LI
2 (
(AwTmmx 81. [a)
D D5(Et.y(tt)
n
T'+11
n
n
+ p 2p
|100 [)((')|1]] + SyLD (=" , + 4pL 2E, 1o)
+ (1 p) ||k ((((+))13)
(1- 2 -)(()))
2
+1
h Vf((=')11
n²
+ +
4pp +(1p|
++ 2p) π +
Spr w D)(t'rntt1)) +
22p 1+ 2p
4pr
- -
Ex
n
I
72
We regroup the terms and obtain
n |,t22 V/(ett2111?
E, [f())t])- - f(aa)] + K.E,
+ t. ||| - 111
1=1
+ pE, [||5t|- ||]"]]
||uct1 (oct1--8(e+t))))
+ AE
$ (1 -00+11) (f(z²) - -((x))
L+T || x=11|
L + le+1ll
+ p0c+1
Be [[
-x=
27+41
27/+1
+p
4wwmmxx
+ +18
1+ P
Lmax + 11
T.+ n++1
( (Aw
+ 8L
pa )
+ p8L+
nT.
3
pm
(1(1+
1+ 2p
L 8rma
4
+ +0++1 -1 Dy(=",1"')
+
PL
+
x4p
1
1.2 + pApL? +1
2p (20
1+ 2p
L + 4przwW22 E. [||aAt] -
2
po?
2+
E,
|| w²'1" 1²1
2
+ 14
11
a
|lue* - ut u1(2
2
7111 ) 2
+ p(1 p(1 p1) pp11-p)
||0 |
v)(>))112
+
V1
a
L+
30

---

+ p2p + X (1-22) -- (o'-vf((2')
2pw
nl. + 1t 2w
Yot1
+ 2
2T2
+ ki (1-
( Σ | - (
+
T T++14+111
n
n
Using x²*1 y/t11 B (ut - w²) we get (we mark the changes with color)
Ee [f( - f(x")] + klEL
1 | -
) + +nB. - 11
1=1
+p ||att] )|
AB,
$ (1 p01+1) (f(2*) ff(²))
I.+ Te |1' - xx11²
L + T
Be [1wet] 1o-t1-x"' x=11²) [19)
+ +d0++1
2
27++1
+p
4wLmmxx
nn
+ +18
|+
P 33)
Limxx + 11
I +++I Iett1)
Yet1
2
(
(AusLmaax
pm
+
par ) + +p8+
8L)
+ + (4 (4(1+ 1+ 2p)
+
+ +.++1-1 -1 Dy(et,ytt)
n
Apr )) E. 11-1--w11]
+ 82
pl.
+ KAp
p (1+²)) B)
(+
12 + pApI? +2
2p
1 2p 2 I2 +
1+1
2
T
n
p02 1+1
E,
-u''-=''1"" x²1²]]
2
(1
1 - u²'l 2²12
1/
2
4
N++1
)
2
+ p(1 +1(1-p)) p) ||-- -
11
L + P2+111
02p A (1-2)) 2)) (1'-v)((>))*
2pw
2w
7++1
2r2w + k (1 ( (+ ||4 |n-- -
+ Vt
nL
n
[+1441
n
The inequality (17) implics ||utt1
w²1l I 2 || - 2111² 2 l|ue w' || and
n h,tt1 - ( ||2
E, [f(x)+])- - -xxx*]] + KiEE
+ +u |||00tt 111
1=1
+ plz |1 -V(: 11²]
+ AE,
$ (1 1--000111 (f(z²) - f(z"))
I. Tep |u'- =112
İ. + Te+1ll
p10++1
Bs [1uctt -x-1=x11]
x²1) 11)
27++1
270+1
+
AwTmmax nL
+ ki8 +18
[1+ P.
Limx + ue
I I+ 7o41
(
(Aw +
8L
+ +8L+
pm
per
4 1+ (4(1+
2p)
87 W7axX
+ x
L
+ + -1
Di(et,9(t2)
n
2p I + 4pr2uut? )) E, [11-42 1 w01(]]
20 20
pI.
ndp
1 P.
Lt pApL? +2 2p (1
1+
8
p0z 00 L
E,
|||l-1 2²112
2
31

---

PL
(1+ P) 1² + pApL? +1 2p (1+ 22) 2 12 +2+
Apr 2
)) + (1-2) w'1?
20
kdp
[1 3)
2
n
4
1+41
2
+ t1 (1)1->)) -V(-v((>''''
14 a
L+ + P241111
+ p2p A (1-2) 2)) |100=
2pw
2w
7t+1
2
2
1
))
(2
m Σ
1In 1i4--vie v
nī.
+ 1t
n
i. T.+ T
n
+ K
n
Now, we want to find appropriate n. p. X, and Vy such that
20
pL + x4p
p (1+3)
1 11
1 AApl +1
2p
1+
2p
1 +
Apr )) + u (1- a¹
- 11
-
3
T
n
2
2
7tt1
+ -p) S (1 (1-?) 2)
-p)
I. + T1+1/1
7
p2p + X
1
S
2
2pw nL n
2w + Vt
+ x 2
3 S k (1 4)
3
+
(1- 2
L 1++++
(46)
We analyze inequalities (46) in the following lemma:
Lemma E.10 (First Symbolically Computed). Assume that for the parameter L, the inequalities
from Sections and J hold. Then, for all t 2 0, exists p in (90), K in (88), X in (82), and V. in (83) such that (46) holds.
We proof lemma separately in Section G. Using the lemma, we have
E. [[(==t))- - [(x')] + <,E,
1+ V/((=
+ +ul [llutt2 - -1ott1=w++11 =11]
+ plx [11441 - ()( ||]]]
+ AE, |10411 -
S (1 p0++1) (J(z') [(x)))
T+ |u"² ux-'
L + Te+ilI
+ +00+t1
x01
Be
-x11 -
27141
270+1
AwTmmax
(1+ p
2 ( (AwsTmmax
8L
+P
+ +18
Timax + Vt
I. L TTTill
+
par ) + p8T.+
nL
3
pm
(1(1+ 1+ 2p)
87 Wmax
+ 4
L
+ 00+1 1141-1
Dy(a',
n
pL
1.2 + pApT. + (220 (1+3) }
2p)
4pT wi )) B. [[|utt - w(1]
+ 202 1+1
+ =App
2p
1+
1,2 +
7
n
20p 1+1 L
- [²1]"]
E,
2
+ 1/ (1
1100 - u''l 211
4
+ (1
2 || 21
+1
11
+K ( a)
Σ | |
32

---

Let us separately analyze the terms w.r.t. D +1 and E. [| n' [1²]
Lemma E.11 (Second Symbolically Computed). Consider the parameters p. K, X, and vi from Lemma E.10. Assume that for the parameter L, the inequalities from Sections L and N hold, and the step size 1.+1 S f/r all t 2 0. Then, for all 2 O, the following inequalities are satisfied:
p
AwTmmxx nL
+ k8
(1
P [//
Imaa + (I+PetIN))
76+1
)
(Auetmme pm
+
8L.
+ +P8I+
pa
(47)
2p) T
87 wr2 ) + 1c+1 10+1-11
+ x 4 1+
L +
Dy 1 0
and
20/
PL
kAp
1+ p)
2.2 pApp? +1 2p (1+ 2p)
|+
I.² +
4pr
E,
| - -
3)
n
p T,
Es [1 - x²11² 5o.
2
(48)
We prove Lemma E.11 in Section H. Using the lemma, we get
E, [f(2)+)) - ff((((()) + R,E,
+ +rE [||oett-a(+111 a +11
+ pB, ||att1 - [ }|{]
+ XB (octi-vs(++t)))))
$ (1 - p01+1) (f(2") - f((²))
L + Teft 1 -u'--"' 1x11
L + T Ee || =011²))
+ p0
27141
2%/+11
4// 11
|| | u²1?
4
+p [1
P
||A^ {(()1)12
2
+1 (1 7)
||u0 - v)(>'))
* (1 4
3
1
| - VI(GT))))
1=1
Note that 0 < 1/41 S v4 for all t 2 0, since p.+1 is a non-increasing sequence (see Lemma E.1 and the definition of 242 in (83)). Using
1 min 1, p p
3
041 S
4
for all / 2 0, we obtain
E, [f(x(t]] f(xx)] + nE,
| 11 - - 111
+ B. [[ -utt1
+ +p [1,44] (5(2 + AlE -oant--vsea -
<(1 (00+1)) ((66)) - -f(=") +
n1 Σ |11 VA(G3)12)
11
+ ve 1 u11
+ - - v)(zt)|1 + (Db-v((>))??
33

---

+00++1
L+ Tzll
x²11 112
L+ + r Te+1ll
En [|| - -x01))
27++1
21
Let us multiply the inequality by pulet1
2011
7++1
Er [f(= f(x")] + kBBB
1
|10 V
+ 1 [| re+1 ||]
p0c+1
1=1
- + XB (ouft-v(((*t)))
+
1+41
m041) (((tt)-((e") f((²) +
(
1
| v((Et)1)) + 2 l/w0 ut 11
p8l+1
n
+ + Aallk--vfle v)(>'|// + -
L Tip 2
1 101|
L + Iitill
Es | x²' (12)
2
left to use that [++1 == r2 + 7441 and 7411 p0++1 1 (see Lemma E.1) and take the full expectation to obtain (45).
In the proof we require that, for the parameter L, the inequalities from Sections J, L and N hold. In Section O we show that these inequalities follow from (44).
E.5 Strongly-convex case
Theorem E.12. Suppose that Assumptions 1.2, 1.1, 1.3, 2.4 hold. Let
L Lp
VLLmaxPNWr
VT. VDVWT
Lmaxwp? Lmaxw
L 660508 x max
S: (49)
aT
aB
a/B/n
B2n
1 Omnn 1 min { 1, 1. p'''pp pJ hp v)((2") for all i E [n], w u. k0 vf(20),
w+I
0 vz(2²), and To 2 1. Then Algorithm guarantees that
E [[((=)) f(x*)] + " [| - x² =11"]
(-2) 22exp(-22)
$ 2eexp
(V(()))) (((")) + ( (T/
L
+1) 11 -
-0-1'=1 x²'1(
2
To
(50)
where
Q 2 x v V660508x
L
L
/L (w + 1)TTT an/1p
VLLmax Vw + W a a/D/np
LmaxW(w + 1)2p
Lmaxit
max
(V app
aTH
np
V
mpp
a' (w + 1), 1
Remark E. Up a constant factor of 2, one can see that the optimal To in (50) from Theo- rem E. equals lo = 4/p. But the dependence on To is under the logarithm, so if the dependence on the logarithm not critical, one can take any To 2 1.
Proof. All conditions from Theorem E.9 are satisfied. Let us sum the inequality (45) for t 0 to T 1:
Pr
E [[((=))-(aa')) + KE
1
|
+ E |1"0" u² |1]
1
+pB ||NT - -V((=>)11
+ XE
||eT - -((+T)19))
34

---

n
S To
E ([ - -(x")] + R.EE
n Σ
V
+ mo
11 - 2012
+ plR ||400 -v
+ AR
-
L [ 2
E |1 111u'=>'1''
x²11²]
I + TT
E ||u 1|---2"10 =1(]]
2
Using the initial conditions and the non-negativity of the terms, we get
TTM I 211' 2
I. + Tojl
(nE[((=")-(A2) - +
Ioo f(x*)) +
11 x²1
2
Using Lemma E. we have
I [J(=T) - [[xx)] + H
x911"]
2
S exp (-Tmin min {
pl 1..0mmmi
(2(1669))(05)) + (T/
+ 10 || x x1(
4L
To
It is left the definitions of L and Omin-
E.6 General convex case
Let us use Theorem E.9 to analyze the general convex case (μ can possibly be equal to zero):
Theorem E.14. Suppose that Assumptions 1.2, 1.1, 1.3, 2.4 hold. Let
L 660508 x max {T. T. Lp
VTllmasPWW VLl /
Tnnaxwp? I.naxw
(a at aB/n
S (51)
o/3/n
B2n
8 = w+I:
I mmin 1 min (1, a 1.g.p
''pp' ho = VV((=)) for all i E [n], w = u., 2D = V)((2),
00 fz²"), and To [1, l/L]. Then Algorithm returns e-solution, i.e., E [f((T)] - f(x²) Se. after
L =11²0=00 11=)
+
log
pllmi
Toc
pd min
(52)
Topp 0) QV 1
+
max
p0mmn
log
otherwise
iterations, where
L
L
VLL (w 1) a/n
VLIumax Vw 1WT avPVn
Limaet (w 1)2p
Lmuxel
Q -
max
ap
at
n
nip
Remark E.15. One can see that the optimal To in (52) from Theorem E. 14 equals Io = L/2. But the dependence on To is under the logarithm, if the dependence the logarithm is not critical, one can take any To E 1/T..
Proof. All conditions from Theorem E.9 satisfied. Let us sum the inequality (45) for 0 to T-1: 1:
Pr
E [[((=)) [(x)]] kE
ur |110" = 11
||AT [ + AE
||00 [|o-~v((+())))
+pB
n
<To
E -
- [(x))) + xE
1100 - vA((=')12 Σ
+ moE || - 00113]
=0113)
35

---

+ pll |1:00
v)(=
+ +E 11:00~1/0 -V<p=~>
||ue - x² x-11() [. _ TT
|1ue ='11
2
2
Using the initial conditions, the non-negativity of the terms, and T' S 1/L,, we get
TrE -(=")) Ioo <To (((12)-((()))))) ((x))) + +. Toj - {(x))) I. -
| xx" 1=
2
$
- =11=00 xz
Using the I-smoothness and u S S L, we have
Tr
TrB[ [](=)) - 1(x)) s L || - x111 + - x¹11 s 2t 1| - x²12
Using Lemma 1, we have
Lo exp (tp0 1E [ [[(==)] f(x))] s 22 x11
t <<t
2
p(t-D)" [f - f(x*){ s 2L |:0 x ||?
t t2t,
16
0) The last inequalities guarantees that Algorithm 1 re-
where 8 := max
p0mni log 2Tpp
turns e-solution after (52) iterations.
E.7 Choosing optimal parameters
Theorem 5.2. Choose E [0, 1] and let Plaa = (Irr)K_tkka" In view of Theorem 5.1, the values p = min
w+I Maan and 1/3
(w41)778
minimize max
m This choice leads the E[,xE(
following number of communication rounds:
Tmellssic
max
max 1,
Immaa we max (w+ (w+1,
1) (in
(13)
ng
The total communication complexity thus equals m
((((1 r) + rkaa Tratio + d).
malisic
Proof. We implicitly assume that p E (0, 1] and T E (0, 1]. Using (12) and (4), have
arg min p.r
max Lmax L.LL]
m = arg min
max Luax ELL,mL)
@ k + (Ka + pd) T).
p.7
Note that only T depends on Liax and We have
min
max
T
Lenax El [L,
(10)
L Coppe'
L atμ
LL (w + 1) avnp
min
max Imaee [[
max
LLmmax Vw + IVWT a a//p//4
Imnawo(w + 1)3p
Imaaws mpp
a - (w + +1), !1
L
L
L(w + 1)
Lvw IVWT
Lw(w + +1ppp
La pHi
min θ max (V
app"
atT
aj
/
1
1
(w + 1),
a'
36

---

The last term attains the minimum when
p2/s
(53)
w + 1' (w + 1)2/3
Therefore, we get
T' min max
T
Lmax E mL
pp a (w 1), )1)) (54)
= max (VaPi' L
I(w+11
Ilw + 1)2/3 apt/8p VV
Too(w + 132p
Las 1
V
'V
V
ap
where we use that
1
(w 1)2/33
- - e @ max { (w + 1) ,1, #
max w +
S max w +
(w ww+ll +1)
(ww+))
p2/3
3p
is left find
arg min P
min
max Temax [[
m"..
arg min 3 ((1-)) + (Ka + pd)
p
arg min θ (AxT' +
(55)
p
where A = (1 11-r) Kw + rKa 2 0 and B = rd 2 0. Note that A and B do not depend on p. If
p A/B, then ê (AT" BpT") θ (BpT"). The term pT" is non-decreasing function w.r.t. p.
For 2 A/B, it means that an optimal point = A/B. Thus the argmin (55) is equivalent to
arg min (A T B pT) arg min θ (T"), pēQu
PE
where Qu Q0== (1<ppp S $}- Thus, have
L
Llw + 1)
Mww + 1/2/3 ap1/3/4
Las(w + 1)2p
Ias V pp a (w 1), 1), })
arg min + max (V P
app
ap VV
1
The next observation is that this argmin is non-decreasing when p > 1/w41. It means that the min- imum attains at some point p E Q = {plp I 1/W+1,P E Qo)- Using this information, we
can eliminate the redundant terms (for instance, Av [(w+1) I Av OAK
I. for E Q1) and get an app
equivalent argmin
L
Las 1
arg min θ max pEQ,
(V app V
ppu
p
The last term attains the minimum at
1 A
p min
(56)
1++* B
Using (56) and (53), an optimal is
11/3
(57)
(w + 1)2/3"
We substitute (56) and (57) to (10) and obtain (13). We use Lemma 1.4 eliminate the redundant terms. Note that م'. := 13/A.
Using (12) and (56), have
m paisss
(1 - KT Traimn + r (Ka + pd) Traius + d
37

---

Ka (1- r) rd
()-r)Kk + traa d) T Tasis + d
I r) manin
2(1 K T + 22rKTTaaan d.
Note that
m lallakk
= -1--)) (o- + r (Ko + pd) Trstite + d
2 (1 r) -u + r + d.
rd Theorem 5.4. Choose r E [0, 1), and let plaa = [I-r) In view of Theorem 5. the values p and T given by (63) and (58), respectively, minimize m from (10). This choice leads to the following number of communication rounds:
L max L, pL ap
L L113 (w 1) am113pp
L 11/22 (w 1)3/2
Toplimiatc -
Vanu
(14)
Limasto max fw + 1, a.
(w + 1), Hlany }).
Tip.
The total communication complexity thus equals m Myuusss = (((1 - Ku rra)) ) T Tepimnn + d).
Proof. We implicitly assume that p E (0, and (0, 1]. We start the proof as in Theorem 5.2. Using (12) and (4), we have
arg min m = arg min θ (m) + (Ka + pd) T)
P/7
Unlike Theorem 5.2, we know the ratio Limas/L, thus
min T
(10)
L
L
VLLmaa (w + D)VT avT24
min θ
max
app
atH
LL V Vw
IVTT
Lumxw(ww 1)2p
Lmux
mpp aa (w + 1), :1
The last term attains the minimum when
Ln Linax
1/3
1/3
T min
1.
min
(58)
w + 1 (w + 1)2/3
Therefore, we get
T' = min T
L axpp'
L 1/3 (w + 1)
L (w + 1)2/3
Lmaxw + 1)2p
Lmaxw 1
w 1, - 1
(59)
= - max (V
a -,
an313p
13
71p1
mpp
It is left find
arg min
min Ininm".) arg min ((1 kw + (Ka + Dd)
arg min θ (A x T" BxpT",
(60)
P
where = (1 Kw +r, 2 and B = rd 2 0. Note that A and do not depend on p. p 2 A/B, then Ô (AT' + BpT") = (ByT") The term pT non-decreasing function w.r.t. p. For A/B, it means that an optimal point p A/B. Thus the argmin (60) is equivalent
arg min θ (Ax T B pT") arg min θ (T'). P
PēQo
38

---

where Qu:= : (p/pp> $).
Next, we have
arg min 3 (T*)
PEQu
arg min peQu
L app
1 1/3
(w + 1)
2 1/3 (w 1)2/3
Lmaxw + 1)2p
Lmaxx 1
(w + 1), 1
p )
max
V
am113p
an 13 mm11/3p1/8/ 1/11/31
np
npp aa
(61)
1/3
For
2
Lmax
Ln
w+1
using Lemma 1.4, we have 2 w+1
L2/3 L 1/3 (w + 1)
L app
13
L 11/3
(w + 1)2/3
L2/3 1/3 (w + 1)
on 1m1/331/314
an
Linaxw
Limaw((w + 1)2p
apH
1
Limax Ln
1/3
S
(w + (W (1)
p
1/3
means that for p 2
Lu Lmmax
the argmin (61) is equivalent to
w+1
L3/3 1/3 (w + 1)
Lmaxw(ww + 1)2p 1
(w (ww 1))+
arg min
max
PEQo
/33
12p4
a
Since all terms non-increasing functions of p, the minimum is attained point p
1/3
1/3
Ln
for all
Lm Txmax
Let us define
Fmax
w+1
w
Ln Linax
Q
p
p
w+1
The last observation means that the argmin (61) is equivalent to
arg min
pEQ1
1 1/3 (w + +)
12/3 1/3 (w + 1)2/3
Lmaxw(ww + 1)2p
Lmaxw 1
npp a. (w + 1), 1 1
max
V app
13
/3
nip4
L app'
Tmmax (w 132p
1 Imnax 1 " (w +1+
arg min θ
max
(V
p )
(62)
PEQI
1441
npp
where we eliminate the redundant terms using the additional information particular,
Ln Limax
1
In
w+1
1/3 (w + L2/3 133
L
L2/3 11/3
1/3 (w + 1)2/3
L
<
appi
and
V
an 23133p1
V app
39

---

2/3
for all p
Ln Tmmax
Without the condition p E Q1, the argmin (62) attains the minimum
w+1
a point
Ln Linax
1/2
max
1'
Va(w + 1)3/2
Considering the condition Q1 and yws == B/A, we have
Ln
1/3
Ln Lmaxx
1/2
1
min
ais,a
Linax
w w+1
max
+
Valw + 1)3/2 Ss.
(63)
is left carefully to substitute (63)
Luaxi
1 1): p aa" (w 10+11)
max
(V
app
npp
and obtain (14). The proof of m m = θ rem 5.2.
(((1 - -r) Ku + rraa) Tunee)) is the same as in Theo-
E.8 Comparison with EF21 DIANA
Theorem 6.1. For all E [0, 1], m malisii
Ô m ma
Proof. Using the inequality of arithmetic and geometric means, i.e., vay S 2ty for all x, 2 0, 2
and T. 2 ,, we have
L(w+1) +
L(w
Lmaxws(w + 1)
Lp
m
=
+
+V
+ w + tlar +
12/6
L
Linaxw
Tiphira ap
TrnaxwWhoo np
}dd.
=
Kr
+ tw+
+V
+ Hlws
app
From the definition of pu rd/K5... we get
((K K"
(L
Limaxw
(V
LK x rd
LmaxwWK
x rd
m realisio
+ tw
+ rdd +d)
Cxfs
ni
aep
Using the inequality of arithmetic and geometric means again and
< 1, we obtain
-ō(1o
Lmaax
[
Imaaiw
m Icalittc
aefe +
+
+w)
Ky,a
+ d td)
nu
af
my
The last equality means that m Ö (mom for all [0,1].
E.9
Comparison with AGD
Theorem 6.2. For all r E [0, 1] and for all K E [d], let us take the RandK and TopK compressors with the parameters (expected densities) i) K2, K and Ka min([1-r/7H]] d} for r E [0, 1/2),
ii) K., = min min([r/1-
and Ka = K for E (1/2, 1). Then we have m O (man)).
Proof. Consider that r E [0,1/2], then K = K, Kg = min [ d). Therefore, we have KT == (1 - Ka + rr, S r) r[2-r//K] $ 3(1 r
and
KT W, == (1 Kw + r > (1-r)k
40

---

Using this observation, we obtain Pusa == rd
I
(1-r)K I d [1-r)K rd 1 and I
rd
Note that 2 Ka/d and -
K2,a
K.
d/K., for TopK and RandK. Thus min
d
1. We substitute the
K
bounds to (16) and obtain
m -ō 6(1- (1-))
(V R
(
d
rL
+
d
Lmax niu
+
rd
+
d rd
(1 (1-r) r) + ta).
1
K
r)u
V K
(1- (1-r)K
K
Since
E [0, and K I d, one can easily show that
m
nellok
= =0(d)
d1 1
+ dg
dv
Lmax
-d)
np
is left to use Lemma 1.4, to get misiiin = =6 (2/? 1.) = Ō (mxoo) for all r E [0, 1/2].
Assume that r E (1/ then K min min([
and Ka K. Using the same reasoning.
we have
KT w,a = (1 - Km + rK, 1 (1 - r//r/1-1k +rk & 3rK, Ky == (1 - Kr + tra 2 rk,
1l = rd S
d
KW K
K
{ (1 (1-r)d r)d
and S max
rk ,1 1.
d
By substituting these inequalities to (16), we obtain
m sollitic
=
rk
d
L
d
(1 r) Lumaxi
d (1 - r1-r)d
+
+ d
td)
d
K
K
rnie
K
rK
K
5 (a/#t) = =ō Omm)) for all r E (1/2, 1].
Using Lemma 1.4, one can easily show that m
F Auxillary Inequalities For L
We now prove useful bounds for L.
Lemma F.1 (Auxillary Inequalities). Assume that the constraint (44) hold, and a constant 660508. Then
Imaxlpp
Tumaxpp
Immaxit
L 120
(64)
L 2
(65)
L 2
(66)
F2n
Bn
VLLmaxPW/T
VLLmax /LLmavVDVUT
VDVWT
v LL VPVWT
L >
(67)
2
(68)
Ż 2
(69)
aB/n
ayBym
ann
1> Ipt/UT
L /.VWT
L /.VTTT ayn
(70)
(7))
(72)
aB
a/3/T
L > c Tp
iwpV L>
(73)
(74)
Va
VavBVn
41

---

L2 Lpvw
pw
(75)
L 2
(76)
B/n
Bn
1> c-
L
(77)
L Lp
(78)
L 2 cL
(79)
a
1/3
1/3
LL wpp 02 1272
LL
L L26
(80)
L
(81)
823
Proof.
The inequalities (64) and (66) follow from (44). The inequality (65) follows from (64) and
(66):
Lmaxiup -maxw
3n S c
(5x
p²
x
12
c x 2
Lmaxiup In
Lmax S L.
82
2
The inequalities (67) and (68) follow from (44). The inequality (69) follows from (68) and B
(0, 1]:
L 2 W V...mux
a/3/vn
ayn
Using Lemma 1.4, (67), (68), and (69), the inequalities (70), (71), and (72) follow from
VLLmaxP
IpvwT
2 c
2 aByn
aByn
VLLmax
WVVWTT
L 2
aV3/V
aVB/n
LLLLax VP/
1,2
av
avn
Next, using Lemma 1.4, and
2tu 2
ry for all x, 2 0, the inequality (73) follows from
Lovw
VL
L x a 222 B2n S L.
Lmaxp² (44)
S
Va
vaByn
The inequality (74) follows from
//WV Va S VLLmuxvPVa C
Lmaxpx (44) L.
c
x
x
VayBVn
2
2
Bn
The inequalities (75) and (76) follow from (73), (74), and E (0.
ipvo
Tn
L c Va3yn
2 Byn
VayByn
VBVT
The inequalities (77) and (78) follow from (44), and (79) follows from (77) and E (0, 1]. Using
Lemma 1.4, and ztytz 2 1/ for all x, y, 2 0, the inequalities (80) and (81) follows from
c
1172
1/3
Sc
L Lmxxwwopp*
oZ 1212117
1/3
31
x
aT
Lp
3
x
Lp
aT
3
c
x
Lmaxwpp (44)
BBn
5 L,
L.
1/3
T?
1/3
Lp
Lp
(44). 5 L.
cc
+
5/
a² 3n072
a² BnT2
3
at
7r
3n
42

---

G Proof of Lemma E.10 (First Symbolically Computed)
We use the notations from the proof of Theorem E.9.
Lemma E,10 (First Symbolically Computed), Assume that for the parameter T., the inequalities from Sections and J hold. Then, for all 2 0, exists p in (90), k. in (88), x in (82), and vs in (83) such that (46) holds.
Proof. The inequalities (46) are equívalent to
80
pl: 2
+ xAp
1
1+
L - pApL2 +1
2p
1+
2p
L
+
4pr
)
S
Svc. v
7
n
8
7++1
2
Vt
P.p pr
op
L + 11+1/11
8p
p S X
8pw
8wi
7++1
87
+ 1s
+
I K.
nI.3
nB
L + T T1+1/1
n
Let us take
8p
À P
(82)
ensure that the third inequality holds. It left to find the parameters such that
80
pl.
x4p
p¹ 1+
1.2 + ApT.2 +p
8y
2p
1 +
2y
I.2
4prr
)
2
3)
7
7011
S.p
op
L Pe+1
Spw
8w
7+11
2
8p
8r
+ Vt
+
p
S K.
nL3
n3
L + 12+111
T
Let us take
;= 02 (k,,p,
(83)
where we additionally define
= (k. =
pL. 2
+ xAp
1
1) 1.2 + pApT? + B
8p
2p
1
2p 7
I
+
4pr
T.
n
(84)
ensure that the first inequality holds. It left to find the parameters and p such that
n1410++1
)
2
[(R, p) ap
S.p
L L+
8pw nL.3
8w
714100+1
2
8p 87
0( p)
+
S k.
n3
T. T
Using Lemma E. have 10-10-11
L+T+i1
<
10+10++1 L+Te
7.
it is sufficient show that stronger
inequalities hold:
8
(K. p)
S P.
(85)
apI?
8pw
8w
8p
8r?
+ (k.
p
<
(86)
nL.
n
nB
43

---

From this point all formulas in this lemma are generated by the script from Section P (see Section in Section P). We use the SymPy library (Meurer al., 2017).
Using the definition of D. the left hand side of (86) equals
2048L
+ 1024LPwp'p L2aBnT
256L2upp
32Lwp
+
L2a,3n72
L2aBB
L2a8n
(87)
25
256
64wppT
8up
2048 p'
+
12288n + I.20332
+ 3n
L,B
I.2aBB2
where we grouped the terms w.r.t. R. Let us take L such that the bracket is less or equal to 1/2. We define the constraints in Section I. Therefore, (86) holds if
4096T.2wp' I'aBnt2
2048TAwp²p L'aBnT
512TAupp 641aup LPann
128wppT
16wp LBn
40961.
+
L'a3n
Bn
L'a,n2
(88)
Using the definition of D and K, the left hand side of (85) equals
32L
16384LI2wp
16384Lf2up2
L²a²
L
L+a3
20'8LLp²
1024L2P
256L
104
524288LLL
T,20272
T2a2T
T.2
TAa3Bur2
131072L?
10485761
ww
524288L2 L'Wp"
(89)
LAa3Bn
32a332n72
La 3
2048i²wpr
32768
32768i2wpp²
TA038pn
1.202n
T2a2Bn
1.202332
1048576i'
4096i²up
4096
332
[Aa288222
L3228n
L2a283n
where we grouped the terms w.r.t. p. Let us take L such that the bracket is less or equal 1/2. We define the constraints in Section J. Therefore, (85) holds if
64L 32768LL2wp 32768LiPwp² 81921Bwp = La +
8192iPwp2
L +
(90)
L4a33n
L3a2Bn
L3a33'n
Finally, under the constraints from Sections and on L, the choices of parameters (90), (88), (83) and (82) insure that (46) holds.
H Proof of Lemma E.11 (Second Symbolically Computed)
We use the notations from the proof of Theorem E.9.
Lemma E.11 (Second Symbolically Computed). Consider the parameters p. K, X, and vt from Lemma E.10. Assume that for the parameter L, the inequalities from Sections and N hold, and the step size B.+1 I for all t. 2 0. Then, for all 2 0, the following inequalities are satisfied:
p
Aw Tmax nL
+ k8
1+
T.max + 14 (
(L+
76+1
2 (AAw (Autt Tymax +
81.
+ +8T.+
pn
pa
(47)
2p)
87 wT2x ) + 00+1-119 -1 Dj D3(2', 50
+
4
1+
L +
44

---

and
20
pL
20 +xpp (1+ 3 2 + ApL' + 2p 1+ +
L + 4pT
18,
|| | u²
2
p 2
Er |||""|-x'()
w'1l² 5..
(48)
Proof. Since p 2 and Dy(2', +1) 2 0 for all O, the inequality (47) is satisfied if
Awlmax nI.
1 p
Timax + us + T+41
[Aw
8L
+ x8
3
[1+T+4//)
pm
pa
+
p8I.+
+t ( (1
2p L Wrm
+ +0+11- 1441-155 1100
Note that Bc+1 S for all 2 0. Therefore, it is sufficient to show that
Aw Tmmx nL
1+ p
7++1
Aw [wwTmaxx
8T.
+
Imax 1t L (LTT44H/)
3)
pn
pa
+ x 4 11 2p
8r2
L
n
In the view of (83), we have to show that
4w nL
14110411
//w 8L
+ k8
1
T.max + 1
+
+ p&I.+
L P
pn
pa
2p)
8
3
+ 4 1+
L
n
4
Using Lemma E.I, we have J4410++1 L+T
30t10++11 L+TeK
I t. so is sufficient to show that
4wLmax nI.
D
[wwLmax
8L
+ k8
1+
Limax
pSL++
3
T2
pm
pa
(91)
2p
8
3
4
1+
L
T2
From this point all formulas this lemma are generated by the script from Section (see Section in Section P).
Let us substitute (90), (88), (82), and (84) to the last inequality and obtain the inequality from Section K. The conditions from Section I. insure that the inequality from Section K holds. It left to
prove (48). Since p 2 0, Eg || u w(ll]] > 0 and 07 2 0 for all 2 0, the inequality (48)
holds if
4 Σ
L
k4 1+ P 1 pAL? +
(2 (2(1+ 2p
47 wr2
L
1.
(92)
Let us substitute (90), (88) and (82) the last inequality and obtain the inequality from Section The inequality from Section M holds if L satisfy the inequalities from Section N.
I Symbolically Computed Constraints for L Such That The Term w.r.t. is less or equal 1/2 in (87)
256
256l
<
(93)
<
(94)
L2a3n
L2a
45

---

J Symbolically Computed Constraints for L Such That The Term w.r.t. p is less or equal 1/2 in (89)
256L2 1
1024L2P
2048L2p²
(95)
(96)
-
(97)
12a2 28
L2a
28
L2a
28
2048L2wpT
32768i2wpr
5 28
(98)
(99)
32768 32768i2wp27
T.202n
1.2023n
28
(100)
12202
28
13107212
1310721,2:?up'
1
1048576i/w²''
1
(101)
(102)
S
(103)
28
28
T.03Bn2
28
104857644w2p²
524288L
524288L2
(104)
(105)
S
(106)
320232n22
28
L 13R7
28
L²a883n
28
DA8576L2L'wwp
1
1
(107)
(108)
28
28
K Symbolically Computed Expression (91)
544L2
16384L
4Lmaxw Ln
+
12az
Laa
20481'P
40961222
65536L*p
I2a2T
I?a2?
L*aaT
131072L*p2
16LLmaxW
+ 128Lmaxup
+
LP4422
1ann
Lin
128Lmaxup
819213
Lmmxw + 512LLmaxup
L32n
Lta
L2a3n
512LLmaxwpp
1048Lmaxi?
2048 i.2
L2af2n
L30,3n2
L3a,32
4096LLmaxwpr
L
22768LLLmaxup Lmmaxupp
65536L*
Lmaxwpp?
I.202n
69632LL2wp
69
131072L2i2wpp
L
L3a232n
L+a
262144T mp
262144T3 upp
2785281.2 i.P
LAa33n
LA0382n
IA Bn
278528L
Lppp
20971521
2 +
20971521
LAa38p
L Bn
167772161
167772161 iippp
10737418241
L5a53n
L
L'a53tn2
107374182413144222
2147483648L314429
4294967296--i44pp
130382n2
L7 13
46

---

42949672961-
85899345921
8192L
IAa0
I8a0B8n2
8192LI 1?2upp
65536LLmasup
6
L 322
L3a23n
622
L222pr 65536LLmax
pr
wp
262144LL'wp
L4
L
524288LL'up
524
12x
524288
I Bn²
524288 i??upp²
1048576I
L mmp
1048576I 3 mpp
+ 2
122?
L*a0 3
104
1048576L'
W'
1048576L Lma
L?
L
Laa
2097152 Lmaxto''
2097152L Lmaxwo'
2097 2097152L2
T
TA003822n7
10775212(?2pp2
2097152T.
upp
109715212f2upp up
L+a3Bn7
8388608L2 WPpp
2388608L
8388608L3
Lmax w
Lf BTT
1
L4a23n2
$388608Lmaxt L'
8388608
8388608 L LA
L2
La Bnd
(27722661312ppp
167772161>
1677721611Aw2p'
LPu3Bn2
66777216LL=Wpp'
i2 16777216L
33554432L* L L i2p
n22
2 8
34603008L Liax L22
67108864L - L'
67108864L
L2
L
160555mm
671088641, max 12
134217728I i2p
134217728T i.2wp'
13
L 3112
L B
134217728 L L
T
184217728Lmas. L TPT
134217728I Lmax PP
3
3
BAn
134217728L'
134217728L LWW'p' p
1426063361 L L?W?p?
3Pa53n2
L
13
268435456LL 2 T
268435456Li
W22
268435456
3 T
3333
268435456Lmax LAWSDi
268435456L
L 1222p'3
276824064L
L p
3,3333
T. 3322
536870912L. 222 T
536870912Imas
5368709121.2
2 T 1
55at53n²
3333
5368709121 Lmax Wp2
1073741824L L 2
10737418241
1343331
Lo 3'n2
2147453648L Lmax L AAw
21474836481 Lmax L A 3
L80532n
2147483648121,A
4294967296
1. A
42949672967
i.9.
i.9 3
+
+
84
47

---

42949672961 Lmax Lmax LA
42919672961'1-w-pp
3 42949672961 LA
w22p"
+
333333m3
B"a
I222232n2
$68993499LLI
1589934592LL--*p
8589934592 L. w
32
8589934592 P
85899345921
85899345921
17179869184LD
17179869184L*-DW'p
17179869184L
L n3
222
L n2
1717986918411
343597383681, 2
34359738368I w. pO
L8a032n2
L
L
34359738368L - L
34359738368
wpp
34359738368L
B
32a232n272
68719476733L''1''p
687194767361-
1048576LLmax W PT
33
3n2
4194304LLmms i? p2T
4194304L.Lmax
1.
4194304T Tmmax T.2w21'
Bm2
3
8388608L L L t'ppp'
33554432LLmaxx
33554432L L L?'2p'
3n22 2
LAa33An2
Lo 3n²T
3460300SLLmax L P
67108564LLmox L.'WP'''
p
67108864LLmax L P2T
322
B3
671088641, I 2
1342177281, Tmmxx 1.2 Pwupp
13841203212 T max 1 1.?
Tn228m222
3
32
268435456L' Lmux ?
268435456L Liax 1222p' p
2768240644L* L L i?2
100333n27
536870912LLmax
536870912LL
LAW p
5368709121 Lixx 2222p
33
536870912T maxx
22222p
570425344T max T2
1073741824L
1. 1.
1073741824LL
L P
1073741824L 3 Lmax PP
1073741824L* L i
1 n322
1140556688LLm
1140850688 Linax L
2147483648LL L
13
32
2147483648L L 2p
2147483648L* Lmax L 3
2147483648L
3
2
42949672961 Lmax S
42949672961* L
L. T'
4294967296 L w'
37
85899345921,2 Tmmax 3
85899345921 T P.Aw3p'
85809345921 Limax 1 AA33
3
L TT
17179869184LLmma
17179869184LL
171798691841 L 1 W
344
3
171798691841" L i'wapa
17179569184 L LAwap
14359738368LLmm
A
T3
1 n2
34359738368I3 T TAw3pp
48

---

L
Symbolically Computed Constraints for L Such That The Inequality from Section K Holds
544L2
1
16384L4
1
Almax
(109)
S
(110)
(111)
L²a
326
L
326
Ln
326
2048L2P
1
409612p2
65536I*p
1
(112)
(113)
(114)
L2a2T
326
L2a272
326
326
131072L
16
128Lmaxipp
(115)
(116)
(117)
LAa
326
TPom
326
Lßn.
326
81921 Tmaxw
512L
(118)
(119)
(120)
LB2
326
LAa3n
326
L2a3n
326
mmp
2048L L.'Pp
2048 W44Lmman
1
(121)
(122)
(123)
12a.82n
326
L3a3n2
326
L3
326
4096 4096LLmaxwpr
32768L Lmaxwp LAa3nT
65536L Lmaxwpp
(124)
(125)
(126)
12a2n
326
326
326
69632LL?wp
69'
131072L2i?ump
(127)
(128)
(129)
1,3028n
326
1,922322
326
LAocnn
326
262144L* Lmaxwp
262144L*
LInewupp?
1
278528L2
(130)
(131)
(132)
T.038Bn
326
T.20332
326
I.a03,n
326
2785281121,upp
1
20971521, 8.?up
20971521,3 i??up?
(133)
(134)
(135)
L+a332n
326
326
326
i6777216L'
1
16777216L-2xup'
1
1073741824L$1442p
1
(136)
<
(137)
L5a5Bn Bn
326
L 3Bpn
326
L7a534n2
326
(138)
10737418241
3
<
326
326
18a03tn2
326
(139)
(140)
(141)
49

---

1994967296L-LA49
L
8192 DZWFp
-
(144)
B222
326 (142)
326
326
(143)
8192L max W??
1
65536L 65536L maxxWpT
65536L Lmnsswpp
L²a262n2
-
326
(145)
T2223nn
326
(146)
12225'n
326
(147)
65536L 22 PT TAQ2n2
162144LL2wpp
262144LL'wp²
(149)
(150)
326
1.a02 2.n
326
1.302 13223m 326
(148)
524288LiZwp'
524288LL w
524288 Lmxx w22
<
(151)
(152)
1B22B172
326
T.302 326
1. Bn2
326
(153)
924288Lmass
1
1048576I L Lmp
1
10485761 1
822
326
T.Ao3 3nnT
326
T.A03 1033pmn
326
(154)
(155)
(156)
104
1
10485761.2
1
1048576T, T.max i.2wpp
1
(157)
(158)
326
L+a33p
326
3 Sn?
326
(159)
2097152L L
1
2097152L L mpp
2097152L²
(162)
Bnn
326
L4a382nT2
326
L Bm
326
(160)
(161)
20971521>i2upp>
2097
1
2
(163)
(164)
-
(165)
T.2
326
TA TAa3,nn2 9nr
326
T. 332
326
8388608L'LPwp2
1
8388608L3
1
8388608L L L2
1
(166)
(167)
326
326
Le Bnn
326
(168)
8388608 in i2' 13
1
8388608 Lmax 2P²T
1
8388608 Lmx iA=3pp
1
<
<
<
326
326
326
(169)
(170)
(171)
50

---

167772161 LPwp'
167772161 1?2
1
16777216LL
(172)
(173)
326
1 B22
326
326
(174)
16777216L-~w>p>
1
16777216Lmax 1 L'= 133?
33554432L' Lmax W
3322
326
326
326
(175)
(176)
(177)
34603008T. Limax i?
67108864L i.?up?
1
67108864I i.P
1
(179)
(180)
T,0033p222
326
T.00BBn
326
T (3
326
(178)
67108864L Lmax ipp 88
134217728L
134217728L L
326
326
L 82
326
(181)
(182)
(183)
134217728 mmax m.a TA
134217728T Tmax
Imax ppA=Ap2T
1342177281 T.max i.2upp
326
L32383n2
326
(184)
(185)
(186)
B=4217728221-W1
134217728L'-A>>3''
1
142606336L* Limx L?W2pp
1,005,n22
326
1,00582m22
326
1,002,3922
326
(187)
(188)
(189)
268435156LL*'2p'
1
268435456LIA
1
268435456 2p=p
<
I
326
13
326
233
326
(190)
(191)
(192)
2684354561 1.
2684354561.3 T.maxx 1p
2768240641 Tm i.
33
326
326
3333
326
(193)
(194)
(195)
536870912Li+4270
1
536870912 L pp=
536870912L' Lmax LAWPpp
33
326
326
326
(196)
(197)
(198)
5368709121
Lmass L L2
1
1073741824I Lmnns 2p3
10737418241214"02p
132
326
L33483n3
326
L
326
(199)
(200)
(201)
51

---

1073741824121402pp
21474836481 Limax L
21474836481 Lmax LA
B22
326
280BBr22
326
L L8005,241
326
(202)
(203)
(204)
2147483648L2L-WPp
4294967296 w
4294967296 L p=
326
326
326
(205)
(206)
(207)
42949672961. Lmmxx T
12
42949672991--'-
1
326
130083n22
326
1J0533222
326
(208)
(209)
(210)
$589934592LL
8589934592L
8589934552 1owpppr
L
326
326
133
326
(211)
(212)
(213)
86809345991/$1A4Pp
85890345921/
1'
326
L'a583n2T
326
L'0582n27
326
(214)
(215)
(216)
17179869184L P'
171798691841
1
13
326
1 13
326
326
(217)
(218)
(219)
171798691841
34359738368L 2
4435
22
326
326
326
(220)
(221)
(222)
34359738368T.
1
34359738308T
34350738369T,
12a08'n272
326
180053n2T
326
130032n272
326
(223)
(224)
(225)
687194767361211m09
1048576LLmax
3
326 (226)
Laa 13n22
326
326
(227)
(228)
4194304LL i2w P2
1
4194304L 12 12
1
4194304L L w??
1
L 3n
326
142382
326
Toa38n2r
326
(229)
(230)
(231)
52

---

8388608 Lmax 123 L 7
33554432LLmas L2
335544321 Lmax 12 I
-
326
326
326
(232)
(233)
(234)
34603008LLmax P
6710886AL max L?2
67108864L Lmx L L
1
5223
326
L
326
L Bn3
326
(235)
(236)
(237)
671088641, Lmmax i?
134217728I Limaxx w?? 1.00381n27
138412032T. 1.2lmmas Lmax T. 1,503 3222
326
326
326
(238)
(239)
(240)
268435456L Lmax 2
2684354561. Liuax W
276824064L" L L L
S
326
326
326
(241)
(242)
(243)
536870912T.I mmax p' L LAn+
536870912T.I.
p
536870912T,2 T.max Tma 1.Pu2pp 333333n272
326
L
326
326
(244)
(245)
(246)
5368709121 Lmmx L2222ps 1.
570425344L LImax L?'Ppp
1073741824L Lmax LA 1''"
1
326
T.0 18223
326
I.00
326
(247)
(248)
(249)
1073741824LL Ln L
1073741824L Lmaxx ?p
1073741824L Lmax WP
13
326 (250)
L B4n22
326
L8a483n22
326
(251)
(252)
11 1140850688I.1 I.T 1.AW3p²
1140850688 T. ?
2147483648T iAwippr
1
326
326
g3
326
(253)
(254)
(255)
2147483648L Lmax 155
214748364812 Lmax L'
2147483648L* Limx L'p
326
326
326
(256)
(257)
(258)
42949672961. 2am49 2
42949672961 Lmaae 2
4294967296 L W
L L7
326
13
326
13
326
(259)
(260)
(261)
53

---

85899345921. Lmax LAWOpp
85899345921 Limax L' L
85899345921 133 Lmmxx LA
326
326
La Jan5p223
326
(262)
(263)
(264)
17179869184L ppT
17179869184LLmmax "p"
17179869184L Lma L 2
326
326
326
(265)
(266)
(267)
171798691841" Limase I'A T 33n
1
171798691841 I.
1
34359738368 L. T
326
326
326
(268)
(269)
(270)
34359738368L. L L 3
Lyaa L
326 (271)
M Symbolically Computed Expression (92)
2L +
1024L3
4096L2P
1
8192L
256l'up
256
T30272
123n
I.2,2pn
1024Li?wp
102
8192I.?2upr
+
+
1,3,8n
T300,2n
T.302n
131072L
131072L
2'' 10485761
L+a25n
38
DA85766L$L2.0 LP
1048576l4="p"
322
L Bn²
32a2
167772161 w2 P'T
167772167>w@pp'
335544321 p''
TAn2BAn2
[An232n2
2
6710886AL2i4
134217728L W
3322
L B3n
268435456L
268435456L
5368709121 W
33
536870912/2w3pp2
5368709121
1073741824
3
33,3,3,
181072Li'upT
131072Li?up²
524288L2 iPwp?
I3a28nn
LAa2BnT
524288I2
1048576I2
1048576L2
L+a2BPn
Lta2Bnt
L n272
41943041
4194304L3
3 i?
8388608L3 wpp
L 82
Bn72
54

---

8388608L* L'
$388608LL=22P3
8385608LLAW'p'
+
3'
B302,322
67108864LLAWppp1
67108864LL w
134217728LI
L 34m
622
268435456L
268435456L
5368709121'-1>'ppp
536870912L-L-wPpp
536870912L
1073741824120433p
I9o353n'
T.023pn2222
33
107374182A1 2
107374182A13
2147483648L w
L"a
L"a=52nLT
2147483648L
2147483648L & Wpppp'
2147483648/"14422
4294967296L1
12949672961214499
13
1'
N
Symbolically Computed Constraints for L Such That The Inequality from Section M Holds
2L
1024L
1
4096L2P
1
<
(272)
(273)
(274)
L
114
L
114
L3
114
p
256l2up
256l2wp²
1
(275)
(276)
(277)
L3a272
114
123n
114
122,2n
114
1024Li?wp
<
(278)
1024T.iPup2
1
81921.12up
L3a3n
114
(279)
(280)
L300222
114
1302n
114
131072I
13107213 wp
1
1048576L
(281)
(282)
(283)
2An2Bn
114
L4a232n
114
L
114
3
1048576 2p2T
1048576i*=2''>
1
<
(284)
(285)
5
(286)
132
114
[4a2Bn²
114
L422,32
114
1677721614
167772161-
1
(287)
(288) 114
(289)
T.a22 24
114
TA0223212
TA222,3312
114
67.
1
1342177281.
1
<
114
1oa382n2
114
L3o3,3n2
114
(290)
(291)
(292)
55

---

268435456L31A499
1
5368709121"
1
BA
114
13
114
L
114
(293)
(294)
(295)
536870912l'''''>
5368709121"-->9pp 33
1
10737418241"'>''
1
33
114
114
L30253n22
114
(296)
(297)
(298)
131072Li2upr
131072Li2up
5242881.
(299)
(300)
(301)
114
T.023pn
114
TAa2BnuT
114
524288L2 L
1
1048576L2 L?up
1
10485761. L'
(302)
(303)
(304)
114
L BnT?
114
IAa232nT2
114
1
4194304L
1
8388608 L2
(305)
(306)
(307)
19033mm
114
L 33
114
I 1 1
114
$3886081:(2wD)
1
8388608
1
L38
1
(308)
(309)
(310)
114
114
1332,,2n22
114
6710
1
6710856AT.iA42222.
1
134217728L..
1
114
114
13333nn2
114 (313)
(311)
(312)
2684354466Lii4w9p
26843545612
1
5368709122214
1 114 (316)
T0038in22
114
T.0088222
114 (315)
n
(314)
5368709121214
536870912L-1*'00
1
10T3741824L-1
1 114 (319)
23
114
Loa352n2
114
1 330333
(317)
(318)
10737418241
10737418241. 3,
2147483648./9133pp
<
114
L3o2t2n22
114
L7
114
(320)
(321)
(322)
56

---

2147483648L1"">pp>
1147483448111499
2147483648L
1
B22
114
114 (324)
114 (325)
(323)
2147483648L*
229967296LL'u'p
1
42949672961*
114
33
114 (327)
L'a230n2
114 (328)
(326)
O Symbolical Check That The Constraints from Sections I, J, L and N Follow From The Constraint (44)
Note that the inequalities from Lemma F.1 follow from (44). Therefore, the inequalities from Sec- tions I, J. L and N follow from (44), if they follow from the inequalities from Lemma F.1. We now present it', These results are checked and generated using the script in Section P (see Section 6 in Section P)
(93) follows from (74),
(94) follows from (73),
(95) follows from (77), (77).
(96) follows from (77).
(97) follows from (78),
998) follows from (72),
(99) follows from (71), (71).
(100) follows from (70),
(101) follows from
(74).
(102) follows from (77), (73),
(103) follows from (74), (74), (72), (72).
(104) follows from (73),(73) (72), (72).
(105) follows from (78), (77), (74).
(106) follows from (78), (77), (73).
(107) follows from (78), (78), (74), (74).
(108) follows from (78), (78), (73).
(109) follows from (77), (77).
(110) follows from (77) (77),(77)
(111) follows from (66).
(112) follows from (78), (77).
(113) follows from (78), (78).
(114) follows from (78), (77), (77), (77).
(115) follows from (78), (78), (77), (77).
(116) follows from (77), (66).
(117) follows from (65).
(118) follows from (64).
(119) follows from (77), (7),
Ta(a) follows from (b),c)) means that one should use (b) and (c) to get (a). It possible that thus should apply & (= two times.
57

---

(120) follows from (77), (65).
(121) follows from (77), (64).
(122) follows from (74), (66).
(123) follows from (74), (74),
(124) follows from (69), (69).
(125) follows from (78), (77), (66).
(126) follows from (78), (78), (77), (66).
(127) follows from (77), (74), (74).
(128) follows from (77), (73),
(129) follows from (77), (72), (72).
(130) follows from (77), (77)
(131) follows from (77), (64).
(132) follows from (77), (74).
(133) follows from (77)
(134) follows from (77)
(135) follows from (77))(77))77)))))))))))
(136) follows from (77)
(137) follows from (77), (73),
(138) follows from (77) (73), (73), (73),
(139) follows from
(140) follows from (7)) (74).
(73).
(141) follows from (7)) (73), (73).
(142) follows from (7)))))) (74), (74).
(143) follows from (7)) (7))
(144) follows from (77),
(145) follows from (74),
(146) follows from (68), (68).
(147) follows from (67), (67).
(148) follows from (77), (72), (66).
(149) follows from (78), (74), (74).
(150) follows from (78), (73), (73).
(151) follows from (81), (81).
(152) follows from (80), (80).
(153) follows from (72), (65).
(154) follows from (72), (72), (64).
(155) follows from (78), (77), (77), (65).
(156) follows from (78), (77), (77), (64).
(157) follows from (78), (77), (74), (74).
(158) follows from (78), (77), (73),
(159) follows from (77), (74), (74),
(160) follows from (78), (78), (77) (65).
(161) follows from (78), (78), (77), (64).
(162) follows from (77), (77), (71), (71).
(163) follows from (77), (70), (70).
(164) follows from (78), (74),
(165) follows from (78), (78), (73).
58

---

(166) follows from (77) (74) (74).
(167) follows from (77), ((77))(3))))))) (73).
(168) follows from (77), (74).
(169) follows from (70), (64),
(170) follows from (7))
(171) follows from (74), (74), (72), (72), (66).
(172) follows from (78), (78), (74), (74).
(173) follows from (78), (78), (77), (73), (73).
(174) follows from (77), (74), (72), (72).
(175) follows from (77), (73), (72).
(176) follows from (7)),
(177) follows from (77), (73), (64).
(178) follows from (77,, (74), (65).
(179) follows from (77), (77), (74), (74).
(180) follows from (77), (73),
(181) follows from (77), (77), (74), (64).
(182) follows from (78),
(74), (74).
(183) follows from (78), (77), (77), (73).
(184) follows from (7)), (64).
(185) follows from (74))
(186) follows from (77) (73), (64).
(187) follows from (7)) (72),
(188) follows from
(189) follows from (7))
(190) follows from (7)) (70),
(191) follows from (77), (7)) (71),
(192) follows from (73), (72), (64).
(193) follows from (7)) (71), (65).
(194) follows from (7)) (74)) (74), (64).
(195) follows from (74), (72), (65).
(196) follows from (74), (74), (70), (70).
(197) follows from (74), (72), (64).
(198) follows from (77,, (74), (74), (74), (64).
(199) follows from (77),
(74), (74), (66).
(200) follows from (77), (74), (74), (74), (74),(6))
(201) follows from (73), (70).
(202) follows from (77), (74), (7I),,
(203) follows from (77), (74), (74), (74), (74)
(204) follows from
(77)) (74), (66).
(205) follows from
(206) follows from (74),
(72), (64).
(207) follows from (74), (74)) (72), (72), (66).
(208) follows from (77), (77), (74), (74), (74), (74), (65).
(209) follows from (77), (73), (73), (73), (73).
(210) follows from
(74), (74), (74).
(211) follows from (78), (7)) (70).
59

---

(212) follows from (7)),
(72).
(213) follows from (74), (74), (74), (74), (72), (72), (65).
(214) follows from (78), (78), (73), (73), (73), (73).
(215) follows from (77), (74), (74), (73), (73).
(216) follows from (78), (77) (74), (74), (74).
(217) follows from (78), (7))
(218) follows from (78), (7)) (73).
(219) follows from (78), (77),,
(220) follows from (78), (7)) (74), (74).
(221) follows from (79), (78), (74), (7I),, (70), (70).
(222) follows from
(72), (72).
(223) follows from (78), (7)) (73).
(224) follows from (78),
(225) follows from (78), (7))
(226) follows from (79), (T),)))))))
(227) follows from (78), (T))
(228) follows from (77), (71),
(229) follows from (77), (72) (72), (65).
(230) follows from (77), (72), (64).
(231) follows from (78), (74), (74), (66).
(232) follows from (78), (78), (74), (66).
(233) follows from (77), (70), (70), (64).
(234) follows from (77), (77), (74), (64).
(235) follows from (77), (65).
(236) follows from (7)) (64).
(237) follows from (77), (72), (72), (66).
(238) follows from (78), (74), (74), (66).
(239) follows from (77, (73), (64).
(240) follows from (78), (77), (74), (65).
(241) follows from (78), (78), (73), (73), (64).
(242) follows from (78), (77), (74), (74), (64).
(243) follows from (78, (74), (65).
(244) follows from
(245) follows from (77), (74), (74), (7I), (66).
(246) follows from (78), (74,, (74),
(247) follows from (78), (77) (7)), (73), (64).
(248) follows from (78), (77),(7)) (74), (74), (65).
(249) follows from (77), (73), (72), (72), (64).
(250) follows from (77), (7)), (74), (71), (71), (65).
(251) follows from (78), (73), (73), (64).
(252) follows from (78), (77), (74), (74), (64).
(253) follows from (77), (74), (74), (72), (72), (65).
(254) follows from (78), (78), (77), (74), (74), (65).
(255) follows from (77), (74), (74), (72), (72), (64).
(256) follows from (78), (78), (74), (74), (64).
(257) follows from (78), (77), (74), (74), (74), (64).
60

---

(258) follows from
(74), (66).
(259) follows from (78), (78), (74), (74), (74), (64).
(260) follows from (78), (77), (74), (74), (74), (65).
(261) follows from
(74), (74), (66).
(262) follows from
(74), (74), (65).
(263) follows from (77), (74), (74),
(264) follows from (77) (74), (74), (66).
(72), (72), (266) follows from (77), (74),
(265) follows from (77),
(66).
(267) follows from (78), (78), (7)) (74), (74), (74),
(268) follows from (78), (77), (74)) (74), (74), (74), (65).
(269) follows from (78), (7))
(66).
(270) follows from (77), (74), (72),)))
(271) follows from (78),
(74),
(272) follows from (79).
(273) follows from (79), (77)
(274) follows from (79), (78),
(275) follows from (79), (78),
(276) follows from (76), (76).
(277) follows from (75), (75).
(278) follows from (79), (74), (74).
(279) follows from (79), (73),
(280) follows from (79), (72),
(281) follows from (79), (777),(7), (74).
(282) follows from (79), (77),(()) (73).
(283) follows from (79), (77), (77),
(284) follows from (79), (77) (73),
(285) follows from (76), (72), (72).
(286) follows from (75), (75), (72).
(287) follows from (75), (75), (70).
(288) follows from (76), (76), (71),
(289) follows from (76), (76), (70).
(290) follows from (79), (73), (73), (73), (73).
(291) follows from (79), (77), (74), (74), (74), (74).
(292) follows from (79), (77), (74), (74), (73), (73),
(293) follows from (79), (77), (73), (73)) (73).
(294) follows from (79), (77), (74), (74),
(295) follows from (75), (75), (73), (73), (72), (72).
(296) follows from (76), (76), (74), (74), (72), (72).
(297) follows from (79), (77) (74), (74), (73), (73).
(298) follows from (76), (73), (72), (72).
(299) follows from (79), (71).
(300) follows from (79), (70), (70).
(301) follows from (79), (74), (74).
(302) follows from (79), (78), (73), (73).
(303) follows from (78), (76), (76).
61

---

(304) follows from (7))
(305) follows from (79), (78), (77), (74), (74).
(306) follows from (79), (78), (77), (73), (73).
(307) follows from (78), (74), (74).
(308) follows from (79), (78), (78), (73), (73).
(309) follows from (79), (74), (74), (72), (72).
(310) follows from (79), (73), (72), (72).
(311) follows from (79), (73), (70), (70).
(312) follows from (79), (74), (71),
(313) follows from (79), (74), (74), (70), (70).
(314) follows from (79), (78), (73), (73), (73).
(315) follows from (79), (78), (74), (74), (74), (74).
(316) follows from (78), (78), (75), (75), (73),77))
(317) follows from (79), (78), (74), (74), (73), (73).
(318) follows from (78), (76), (76), (74), (74).
(319) follows from (78), (76), (76), (73),
(320) follows from (79), (77) (73), (73), (73),
(321) follows from (79), (78), (74), (74), (74), (74).
(322) follows from (79), (73), (73), (73), (72).
(323) follows from (79), (74), (74), (72),
(324) follows from (79), (78), (78), (73), (73)))
(325) follows from (79), (78), (77), (74), (74), (73),
(326) follows from (79), (78), (78), (74), (74), (74),(74)
(327) follows from (79), (74), (74), (73), (72),
(328) follows from (79), (78), (78), (74), (73),
62

---

Jupyter Notebook for Symbolic Computations
1 Import Necessary Libraries
]:
import os
from IPython IPython.display display import display
import sympy
from sympy import Symbol
from utils import FileWriter, Constraintellgreeaatorr from utils import get_factors, get_term, search_factors,, oftpee__pprrs____neeeeeiee
2 Initialize a File for Results
[]: file_pathe h../paper/resullt.cm txt!
if os aa.path.eom exists (fieep((ile_a
os remove (file_path)
fw FileWriter (file_path))
3 Initialize Symbols From the Paper
[ []: rho Symbol ( ('rho', nomeegttiv--True
kappa Symbol ( kappa', nomnegative-True)
Imbda = Symbol ( ('lambda', nomnogativ=-True)
omega = Symbol ( omega', nomnegative-True)
p Symbol ('p', positive=True)
tau Symbol ( ('tau', positive-True)
beta = Symbol ( ('beta', positive-True)
alpha = Symbol ('alpha', positive-True)
n Symbol (y'', positive-True)
L Symbol
L'L', ('L', positive-True)
L hat = Symbol (r (L)', positive=True)
63

---

L b_max Symbol (r L
positive-True)
L_bar
Symbol (r (L)r
positive-True)
4 Assistant for "First Symbolically Computed" Lemma
4.1
Calculate Expressions
[
nu hat_exp (8 / alpha)
(p L /
+ kappa
4 * (1 P beta)
* L_hat**2
rho * * p L**2
rho (8 p tau)
(2 p (1 / tau) *u
++++2
4 tau**2
omega *u
-L_hat**2 / n))
nu nu_hat Symbol (r' \hat(lnu3', nonnegative-True)
# The left hand sides of the inequalities
rho_lhs mu_hat (8 / (alpha p L_bar 2))
sappa_lhs ((8 * p omega) / (n * L_bar beta)
mu_hat * (8 * omega) (n beta L_bar**2)
rho (8 p) / tau (8 tau omega) / (n beta))
4.2 Display Them
[]:
display (taplay(nuhhat_exx hat_exp)
1hs)
display (kappa_lkkaaaaaaaa lhs)
4.3
Symbolically Calculate The Steps From The Proof
[ ]: constraints_age = ConstraintsAggregatorr
rho_lhe rho_lhs. subs (nu_hat, nu nu_hat_exp) kappa_ lhs kappa_ 1hs subs (nu_hat, mu_hat_exp)
# Grroup Terms w. w.r.t t. kappa kappa_lhs_poly sympy poly (kappa_lhs, kappa) kappa_coef happa_lhs_pont all_coefffs kappa_lhs = kappa_ expand () collect (kappa)
fw wwite(sympp latex (kappa_lhs)
# Find Conditions When The Coefficients Near Kappa <= 1/2
terms sympy expand(aappa_coef [0]) args
latex_string = constraints_agg add_ www.soonntttttttttrtttt
fw. write (latex_string)
64

---

Define kappa kappa_solution (2 kappa_coef [1]) expand
fw ww..rite(""kapp 'eqdef sympy. latex (kappo]soluutoo) + " \labelfeq:
"kappa_sol)")
# Group Terms w.r. t. rho
rho lhs rho_1hs subs (kappa, kappa_solution) rho_lhs rho_lhs expand () collect (rho)
fw. write(sympy latex (rho_ _rhh_ + ", [label ratgrrrooo_e_ppd"_e___
# Find Condition tions When The Coefficients Near rho <= 1/2 rho seto_lhs_pae poloy = sympy poly (rho_lhs, rho)
rho_coef rho r wtl.lhhsooll.llllloooo...o terms = sympy erpo args latex_ constraints_age add_ (to
args
fw. write (allllxx_strinn
# Define Tho rho_solution (2 rho_ [1]) (1x).expand
fw. wr.write \eqdef sympy latex (rho_solltion) (aboslfe
5
Assistant for "Second Symbolically Computed" Lemma
5.1 First Inequality
[]:
bregman_coef ((4 omega L_max) (n L_bar)
+ kappa 8 * (1 + p / beta) * L_max
+ hat
L bar+*)2)
(4 omega L_max (p n) * /u
(p * alpha))
rho * L
+ Imbda * (4 * (1 + (2 * p) / tau) * L + 8 tau**2 * omega *u
LL_max_ n)) display (bregman_coef)
Imbda_solution rho 8 * p /
tau
Substitue all known expressions to the term bregman_coef = \
bregman_ coef subs (nu_hat, nu_hat_exp) exp) subs (1mbda, coldaa_soltion)
-suus (kappa, kappa_solution) subs (rho, rho_ rho_solution)
bregman_coef bregman_coef expand () latex_string = latex_repres inequality (bregmancotbe fw. ww..riteelaex__srring
# Find Conditions When tregman_coef is Less or Equal <= 1/2
terms bregman_coet args
65

---

latex_string constraints_agg add_connsraints (terms) fw.write (latex_stringg
5.2 Second Inequality
[ J: dist_coef = (4 / L_bar) * / 2
kappa rho 4 ***2
(1 p beta) L_hat **
1mbda * (2 * (1 + 2 p / tau) L**2 + 4 tau**2 *u
-oega L_hat**2 n))
cisplay(dist_coef)
dist_coef
dist_coef subs (Imbda, Imbda_solution) subs (kappa, kappa_solution) subs (rho,u
soho_solution)
dist_coef dist _ost_coefft expand simpliiyy expand
latex_string latex_repres___ hates.rrpppsssoo...nnaallitlitte heeeuualltyddisscctttt rhs="1")
fw. wwitrite aaatttelaxex__stteete
terms diet_coef args
latex_string = constraints_age add_constrainte (terms)
fw. w.iwrit (aatte_laex_string
6 Check That The Constraints Follow From The Inequalities from The "Auxillary Inequalities" Lemma.
6.1 The Inequalities from The "Auxillary Inequalities" Lemma:
[]: from collections import OrderedDict
.contstant =
proposals OrderedDict
("eq:1ipt:max_2"
(L_max omega * p**2) / (beta**2 n)),
("eq:lipt:max.1)
(L_max omega * p) / (beta n)),
("eq:lipt:max",
(L_max omega) / (n)),
("eq:1ipt:1_1_mxx 2",
(sympy.sqrt (L * L_max) p * sympy sqrt (omega
taau) (alpha beta sympy. serpy..srttnm (n))),
("eq:11pt:11__mx_11
(sympy sqrt (L L_max) sympy. sqrt(p * omega *u
-tau)) (alpha compy.sque (beta n))),
("eq:1ipt:111_mxxpp))
(sympy Soympy.sqrt.ee (L L_max) sympy sqrt omega *u
tau)) (alpha * sympy sqrt (n))),
('eq:lipt:
hat p sympy sqrt (omega tau)) (alpha tu
beta sympy sqrt (n))),
("eq:lipt:hat_11
hat sympy sp omega tau)) / (alpha *u
sympy sqrr (beta n))),
("eq:lipt:hat..) :hatpp,
(L hat sympy sqrt (p omega tau)) / (alpha *u
sdmsy sqrt (n))),
66

---

("eg:lipt:hat_ellhhaa (L_hat p sympy. sqrt (omega)) / (beta sympy. sqrt n))),
(L_hat sympy sqrt (p omega)) / (sympy sqrt (betau
alpha * n))),
no 2", hat p sympy. sqrt (omega)) / (beta sympy.
sqrr(n))),
htcp:pp:haattt_____peep no (L_hat sympy sqrt (p * omega)) / (sympy sqrt (beta.
n))),
("eq:lipt:plain",
(L) / (alpha)),
("eg:llipt.plain.._.alaa" (L p) (alpha tau)),
L'eg:Lipttpplann__o_alpaaa (L)),
("ag:llip::doublellipp22 sympy cbrt * L_hat*#2 * onega * p*+4) /u (alpha**2 beta**2 tau*+2))),
:'eq:lipt:douuble "imble_lipt_i", sympy.cbrr cbrt ((L L_hat**2 * omega * p**3) /u
(alpha**2 beta n tau**2))),
])
const 660508
for k, proposal in proposals.. t):ms():
proposals [k] (const proposal L_bar) expand
proposals_facton factorss [get_factors (proposal) for proposal in proposals. items ())
6.2 Search The Right Inequalities for Each Constraint
[]: # Takes "1 hour on a laptop
import tqdm constraints constraints_age - ()
cestrriints_iequalitet
[]
for i, factor in enumerate (tqdm tqdm (cdn(sooostaaintts))
num_of haa__bass_fcctorrreeeeeeeeeeeeee wtw.ffrstttotuseeeeeeeeeeoeeeeee -int (factor [L_b)r])
path search_ (factor,
factors,
pos_hints [L, L_max, L_hat, omega, pl, neg_hints= [alpha, n])
cntrraintsiinqqaaittiin append (path)
assert path is not None
text = constraints_ags []:
(proposals,u
connstraints_inoqualitteee)) fw. ww..rite(eext
67

---

Args: P.1 File utils.py
import o8
from collections import defaultdict from copy import copy
import sympy
class defaallcicciittcoosttteddddddddd
def ..init_. *args, **wargg))
10
super (ddfannddttttitteonss solf)...iiit.... (*arge, **kwargs) self. const None
11
12
def cop
obj super (ddaauttiiiiittttsssssss self) _opyy...ooy..... O) obj.t self. const return obj
15
16
19
def get_factors (term)
20
Converts sympy expression with the sympy Mul type to dictionary with factors.
Ex: 2 B (1/2) {A: 2, B: -1/2)
22
Args:
23
parami: sympy expression (sympy. Mul)
24
factors deffuulddcctiithonsss (int)
factors. const
27
const_assigned False
28
assert isinstance sympy.Mul
29
for el in term.args:
free_symbols lest free_ symbols) if (on(or)e_symbols) assert not const_assigned
32
33
const_assignes True
cecoors.onns = int (el) continue
36
assert len sfrre__)yybbl)ss)
37
power al. () [free_symbol] [0]] assert isinstance (power, sympy Rational) factors sysbollllebolsleeee___eee__eella [o]] power
38
return factors 40
41
42
def get term (factors):
The inverse function to the get_factors function: converts factors to term (A: 2, -1/2} A (1/2)
45
16
47
parami: dictionary with factors
reault factors. const
50
for k, in factors items (); result = result k **
return result 51
55
def search_factor (factors, num_ buw.o__beeefactorsstto.o. base_factors. pos_hintss pos_hints-(], neg_hints=:]):
Checks if it possible to decompose 'factors' using num_of of cun_ee_base__eee
factors from 'base_factors'
57
Args:
58
parami: dictionary with factors
param2: number of base factors to use
param3: list of dictionaries with factors
68

---

param4 and param5: hints to the algorithm that helps to improve performance Returns:
A list with indices (with repetitions) of "base_factors" that compose 63
factors'
64
If it not possible, then the function returns None.
def _check, for in pos_hints:
_check_hints hints (factors_):
67
68
assert factors, [k] >=
for k in neg_hints:
factors [k] <= 0
21
check__innss (factors)
72
for base in factors:
73
-check_hints
def
num_of_base tor__aae_factorsstoouuss path, base faceoract 0:
if bum.of.baee_facttrrtttoo.
26
return factors const 1 all ([factors [k] for factors]) for index, choice in enumerate (base_factors):
77
78
factor_choice copy (factors)
factor_choice connttc...cnsstt......oocccii.ie factor_choice const / choice. const for k, v choice. items factor_ [k] factor chotor_choicelle [k]
82
skip False
for in pos_hints: if factor_choiced skip True break for k in neg meg_hints:
85
86
87
if factor_choices [k] > 0:
skip True break if not skip and www.rrccaactttooo (fatrr chocc,r,chhice, 1, path, base :as_ffctors): path append
90
91
93
return True
94
return False
95
path = []
if
(factors, nustos__aseffactrss...o to_ path, base_ factors) return path
98
else: return None
99
class PileWriter(bbjeet))
103
def __init__ (self, file_path): self._file_pat assert not os path. exists (file_path)
104
file_path
107
write text):
108
with open (self. (wtesseeeffeeeeeeeeee_eeeeeeeeee fath, "a") as fd: write (" format (text))
format
112
class Conetrainteaggrrgttr( (objectt):
113
def __init__(self). (self): self constraints = []
116
get get.conntreinnt((eel):: return self._constraing
117
def add_constraints (self, terms):
denom_constang self denos_constant (terms)
121
terme_global_inder []
122
for term in terms:
terms-global. index. append (len (self constraints))
69

---

self constraiits append (get_factore (term * denom_.constant))
(terms, self prrparreeeeeeeeeee (temms corms_llobllindes
126
127
def prepare_ text__tex___t
# assert len pro_..rroo.rropsssssssstt proposals, constraints text = proposala_ labels liat (proposala (eyp keys
=- len constraints)
131
for global_index, ineq in enumerate (tt.onstrrtttttiinnniiiiieeeeeee constraint_labe
132
self a text += "& ((Qr) format (constraint__abbll
index)
\Itextnormal
follows from for i, index_proposal text "(eqref((O)) format (proposals labels [index_ (indxx_proposal)) if i == (ineg) 1:
enumerate (ineq)
135
136
text += "."
else:
139
text ","
140
text += "M1M"" return text
def __ddddd_eonstaaeeeee constant terms): return len (terms)
145
def ggtt_llbelll (self, global_index):
return eeq: sympy: constraints: format (0rta
149
def --epppreeeexttt (self, terms, terms_global_indes)) text denom_constant self delos_ constant (terms)
150
cam_per_colume for i, (global_inder, term) in enumerate (eirratttxippptes___pee (taitttessgllobllindde terms)): if num_per_colum == 0:
153
154
text += text +- ""\begin(equation"" text sympy latex
\leq (Vrrac((1))(()))) format (
denom_ constant)
158
text += "Niabel((0))"".frrr formatt (self. (sell..get..aabeel [elobal_index]/
text += r"\enndfequatonn]"
if num_per_coluue
(num_per_com column 1):
161
text ==r ('Nendttabulars)
162
else:
text += "&"
def ceildiv (a, b):
return ((a // -b)
166
for 1 in range (len (terms), ceildiv (len (terms), num_per_column) num ham_pee__clumnn
if X num_per_coluue == faum_per_colume 1):
text r" (Veed(tabularr)
169
else: text "&"
170
return text
174
def ratex_repres... of www.ooouualittaaaaeeeeeoreaaaaee (conu,,,ttccof,, rhs=" (h== latex_string "&" for i, term in enumerate args): latex_string latex_string sympy latex (term) if len (coef args)
175
178
179
latex_string
\leq rhs
else:
if 1 % 2: fatex_string
W
183
else: latex_string +=
184
return latex_string
70

---

Experiments
Q.1
Setup
We now conduct experiments on the practical logistic regression task with LIBSVM datasets (Chang and Lin, 2011) (under the 3-clause BSD license). The experiments were implemented in Python 3.7.9. The distributed environment was emulated on machines with Intel(R) Xeon(R) Gold 6248 CPU 2.50GHz. In each plot we show the relations between the total number of coordinates transmitted from and to the server and function values. The parameters of the algorithms are taken as suggested by the corresponding theory, except for the stepsizes that we fine-tune from a set [2' i E [-20, 20 For 2Direction, we use parameters from Theorem 5.2 and finetune the step size L.
We solve the logistic regression problem:
m log
exp (al, Σy= exp (a.,
Rt) = m j=1
where T1, Ti,...,22 E Rdd is the number of unique labels, oij E Rd is a feature of a sample on the 7th worker, Yij is a corresponding label and m the number of samples located on the 7 worker. The RandK compressor is used to compress information from the workers to the server, the TopK compressor used to compress information from the server to workers. The performance of algorithms is compared CIFARIO (Krizhevsky et al., 2009) (# of features 3072, # of samples equals 50,000), and real-sim (# of features 20958, of samples equals 72,309) datasets.
Q.2 Results
In Figure 2, 3 and we provide empirical communication complexities of our experiments. For each algorithm, we show the three best experiments. The experiments are collaborative with our theory. 2Direction enjoys faster convergence rates than EF21-P DIANA and AGD.
J0
280 IN Gaorresd CA
0111
10-3
1011
(n (workers-to sorver))rrr
168
/ [server.towwokkrs)
Figure 2: Logistic Regression with real-sim dataset. # workers n 100. = 1000 in all compressors.
17x 109
17x 10
165x
10
16x109
1.6x19'
15x
1.5
10F
C22LP CAMAL sow 0.012S
10
Sug 02012
14x 12
231907 ar Sep 106241144422
144x19
201902 230244 80035
x35 18
0.5
13 (workers server)
2.5
135x188
13
2.5
#bits (server workers)
1c10
Figure Logistic Regression with CIFARIO dataset. of workers n 10. compressors.
1000 in all
71

---

10x19
145x 18
194
16x
18x189
135 10f
135
15x
155
20 Dee ri0 10075005
22herke 00024226222
1 1000
135x1
#bis (workers to server)
le10
#bits h [sserverrtowworrerss
1e10
Figure 4: Logistic Regression with CIFARIO dataset. # of workers n 100. K 1000 in all compressors.
R Convergence Rate of CANITA obtained by Li and Richtárik (2021)
In their Equation (54), Li and Richtárik (2021) derive the following bound for their CANITA method:
+ w)3 (1 (3 3/2)
E [T+ <
max
73
T2
In the regime when w 2 n, choosing b = w and B = + (z) in their Equation (10) gives
(1 w)
(1 + () + 3/2)L })
max
T3
T2
(1 w)
w(w/n n 3/2)2 1)
0
max
T33
T
(1 w)
W²LL
1)
O
max
T3
nT²
This means that the correct convergence rate of the CANITA method (Li and Richtárik, 2021)
+
1/a
vn
n,
T
(329)
w <n n.
Comparing this result with our Theorem E.14 describing the convergence of our method 2Direction, w one can see that in the low accuracy regimes (in particular, when ş17अ dominates in (329)), our result improves θ |// to at least @ (log !) However, the dependence θ (log !) should not be overly surprising as was observed by Lan et al. (2019) already, albeit in somewhat different context.
Comparison with ADIANA
We to check that rate (14) restores the from (Li al., 2020). Since ADIANA only compresses from the workers to the server, let us take r = 0, the identity compressor operator c (x) x for all dd which does not perform compression, and, as (Li et al.. 2020), consider the optimistic case, when Lmxx L. For this compressor, we have = 1 in (2). Note that مú. = 0.
Thus the iteration complexity (14) equals
L
L(w+1) 11)
L(w + 1)3/2 Vnu
Lar(w + 1) ni
(w + 11
poptimistic
max
L
L(w + 1)3/2
Lwllw + 1)
(w (1++1//))
max
(330)
Vnju
7if1
where we use Young's incquality: to-worker compression, Algorithm has the same iteration (330) and communication complexity as (Li et al., 2020).
1w
Without the server-
V
Vn
72


Reviews:
[{"review_id": "4OHym29shm", "reviewer": "Reviewer_gU3b", "summary": "The authors considered a distributed convex optimization setting where both uplink and downlink communications should be considered. In this setting, the authors proposed an accelerated method called 2Direction which generalizes AGD into the bidirectional compressed communication setting and prove its convergence rate and communication complexity. Finally, empirical results are provided. ", "questions": "See Weaknesses", "limitations": "No", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "For this new setting, the authors propose new strategies to make the adaption of AGD possible, which is nontrivial. Meanwhile, the bounds seem OK to me and can be applicable in the smooth transition from uplink to downlink. ", "weaknesses": "Such a generalization for the bidirectional case fills an important gap, but it lacks enough motivational examples for why such settings deserve study. \n\nThe algorithm name 2Direction is confusing as we don't really know what it means. It is better to follow the tradition and use the abbreviation of the full algorithm name. \n\nThe authors show the motivation of the new strategy is the existing approaches failed in the bidirectional case but don't show the concrete reason why failed. Is the failure superficial or essential? \n\nThe experiments should be included in the main body. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review!\n\n> For this **new setting**, the authors propose new strategies to make the adaption of AGD possible, which is nontrivial. Meanwhile, the bounds seem OK to me and can be applicable in the smooth transition from uplink to downlink.\n\n> Such a generalization for the bidirectional case fills an important gap, but it lacks enough motivational examples for why such settings deserve study.\n\nThe bidirectional setting is not a new setting. The first methods that consider this setting can be traced back to at least in 2019 \\[3, 10, 11\\]. This topic is increasingly popular in the community \\[6\\] (ICML 2023), \\[7]\\ (ICML 2023) , \\[8\\] (NeurIPS 2021). See also the recent paper \\[9\\] (ICML 2023) on fine-tuning large language models, where bidirectional compression was essential to obtain the strong empirical results (btw: their theoretical communication complexity is worse than that of vanilla gradient descent; our results point to *better* rates than vanilla accelerated gradient descent). In short, this is a very important setting.\n\nThe bidirectional compression is often overlooked because the analysis of unidirectional methods is much easier and by the assumption that the broadcasting from a server to the workers **is free.** Clearly, the assumption that your phone/laptop can receive data from the server for free is an oversimplification. The communication speeds in both directions have some limited speed in reality. Please try to visit speedtest(dot)net and check download and upload speeds. These speeds will be equal in most locations, and it is quite unlikely that the download speed will equal $\\infty.$\n\n> The algorithm name 2Direction is confusing as we don't really know what it means. It is better to follow the tradition and use the abbreviation of the full algorithm name.\n\n2Direction = TwoDirection $\\approx$ Bidirectional. It is just a game of words. One can think that 2Direction is an abbreviation of a \"Bidirectional Method.\" \n\nAs authors, we have the right to choose a name for our method. Some authors use abbreviations of full algorithm names (when such abbreviations lead to \"good\" names), some choose playful names (e.g., Hogwild! - a test of time award winner; CocktailSGD \\[9\\]; or DoubleSqueeze \\[10\\] - our name is in some sense similar to this one), some authors choose female/male names (e.g., consider the celebrated Katyusha method \\[1\\], celebrated Adam method, or Diana / Marina \\[2\\]), and so on. \n\nThis is clearly not a weakness of our paper; we see it at best as a minor recommendation based on personal preference of the reviewer. We happen to have a different preference in this particular case. As such, we believe that our choice of the algorithm name should not affect accept / reject recommendations.\n\n> The authors show the motivation of the new strategy is the existing approaches failed in the bidirectional case but don't show the concrete reason why failed. Is the failure superficial or essential?\n\nThe failure of preceding methods seems essential - neither the authors nor us know how to prove that these methods have better communication complexity than vanilla GD (with the exception of \\[6\\]), let alone accelerated GD. This is not a proof of impossibility, but we believe the preceding methods and simply not designed well, and a major redesign of the algorithms was needed.\n\nIn other words, we believe that our new strategy is essential. In Lines 167-176, we explain why. It is clear from the proof that the designed modification is required to obtain the convergence of a Lyapunov function in our method. If you compare the Lyapunov functions of non-accelerated \\[4\\] and accelerated methods \\[5\\], you will see that the control variables \"converge\" to the non-fixed vectors (please see explanation in Lines 167-176).\n\n> The experiments should be included in the main body.\n\nOur work is theoretical, we believe that the theoretical insights are by an order of magnitude more important than the experimental section. Having said that, if the paper gets accepted, we expect to get an extra page and we plan to do as you advise. \n\nIf you have any additional questions, then let us know please.\n\n\\[1\\] Z Allen-Zhu et al Katyusha: The first direct acceleration of stochastic gradient methods\n\n\\[2\\] Gorbunov et al. MARINA: Faster non-convex distributed learning with compression\n\n\\[3\\] Liu et al A double residual compression algorithm for efficient distributed learning, 2019\n\n\\[4\\] Gorbunov et al. A unified theory of SGD: Variance reduction, sampling, quantization and coordinate descent.\n\n\\[5\\] Z. Li et al Acceleration for compressed gradient descent in distributed and federated optimization\n\n\\[6\\] Gruntkowska K. EF21-P and Friends: Improved Theoretical Communication Complexity for Distributed Optimization with Bidirectional Compression\n\n\\[7\\] Dorfman R. DoCoFL: Downlink Compression for Cross-Device Federated Learning\n\n\\[8\\] Philippenko C. Preserved central model for faster bidirectional compres335 sion in distributed settings.\n\n\\[9\\] Jue Wang, Yucheng Lu, Binhang Yuan, Beidi Chen, Percy Liang, Christopher De Sa, Christopher Re, Ce Zhang. CocktailSGD: Fine-tuning Foundation Models over 500Mbps Networks, 2023\n\n\\[10\\] Hanlin Tang, Xiangru Lian, Chen Yu, Tong Zhang, Ji Liu. DoubleSqueeze: Parallel Stochastic Gradient Descent with Double-Pass Error-Compensated Compression, 2019\n\n\\[11\\] Horvath et al, Natural Compression for Distributed Deep Learning, 2019\n"}, {"review_id": "V9HwX9xuzl", "reviewer": "Reviewer_M4eW", "summary": "This paper studies 2Direction, a new method for compressed communications for the centralized distributed convex optimization problem, in the case where both worker-to-server and server-to-worker communications are compressed. Compared to previous work EF21-P+DIANA, it  guarantees a total communication complexity no worse than Nesterov's accelerated gradient methods.", "questions": "* line 130 claims a *\"new error feedback mechanism\"* but only compares it to the EF21-P method. What is the difference between equation 9 and other mechanisms such as MEM-SGD [1] ?\n* In the experiments part (appendix Q), why use a single value of $K$ ? Would it be possible to display the evolution of the convergence rate at different degrees of compression ?\n* line 1033, the stepsize $\\bar L$ is said to be finetuned. However, if we assume $L = L_{\\max}$ (which we can find for logistic regression), wouldn't equation 44 give a closed form expression of $\\bar L$ ?\n\n**Typos :**\n* The order of Equations 6 and 7 seems to have been reversed.\n* line 195: a *\"and\"* seems to have been left between *\"general analysis\"*.\n\n\n**References :**\n\n[1] Sebastian U Stich, Jean-Baptiste Cordonnier, and Martin Jaggi. *Sparsified SGD with memory*. In NeurIPS, 2018.", "limitations": "*", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The paper introduces a new objective of minimizing the *total communication complexity*, which is well defined through equation 4 and clearly explained with the problematic lines 118-122.\n* To alleviate some of the burden of understanding the seemingly cumbersome algorithm and proof, efforts were made to describe some of the steps of the research/thought process that led to the final method in Section 4, and to provide a sketch of the proof in Section 7.\n* For reproducibility purposes, I appreciated the presence of the SymPy code used for the symbolic computation part of the proof.\n* The final result is original, seems to have required more than a *\"small tinkering\"* of previous methods (Section 4), and displays both theoretical and practical improvements over previous state of the art algorithms.", "weaknesses": "* While efforts were made to ease the understanding of the general ideas behind the algorithm and proof, they seem so cluttered that it deters from delving into the technical details.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the positive evaluation and comments!\n\n> While efforts were made to ease the understanding of the general ideas behind the algorithm and proof, they seem so cluttered that it deters from delving into the technical details.\n\nUnfortunately, this is the nature of all accelerated methods. In our method, everything is overcomplicated by the fact that we have bidirectional compression. This is the first method that has better communication guarantees than the vanilla accelerated method. We tried to explain the proof idea in Section 7.\n\n> line 130 claims a \"new error feedback mechanism\" but only compares it to the EF21-P method. What is the difference between equation 9 and other mechanisms such as MEM-SGD [1] ?\n\nIf we understood their work correctly, MEM-SGD is simply the EF mechanism from (Seide et al. (2014)). Their contribution seems to be not on the algorithmic part, but in theory (Seide et al (2014) did not provide any theory). In the abstract and in Lines 127-128, we explain that EF21-P is a reparameterization of the celebrated EF mechanism (see details in \\[1, Section 2\\]). So the difference between (9) and EF (MEM-SGD) is the same as the difference between (9) and EF21-P (under re-parameterization of variables). Note, however, that we had to use a new and modified version of the EF21-P mechanism (see Lines 167-176 where we explain the difference), and that unlike in [1], where classical EF is used on the workers' side, we use our new EF mechanism at the server side. \n\n> In the experiments part (appendix Q), why use a single value of $K$? Would it be possible to display the evolution of the convergence rate at different degrees of compression?\n\nThere are many parameters, including $K,$ # of workers $n,$ dataset type... It is practically infeasible to experiment all possible parameters. In our experiments, we took several key parameters to check that the dependences from the theory holds in practice as well (it does). Note that the acceleration nature of the method is independent of the chosen $K.$ But we can easily also add experiments where we study the choice of $K$. We do not think though that such experiments would add much value.\n\n> line 1033, the stepsize $bar{L}$ is said to be fine-tuned...\n\nIn general, for logistic regression, we can only find an *upper bound* for $L_{\\max}.$ Thus, it is still not tight. Moreover, the reviewer can see that (44) is proportional to the large constant which is just an artifact of the proof. It is possible to get a better constant, but the proof will be even much larger. Note that the step size in EF21-P + DIANA is also finetuned, so the comparison is fair.\n\n\\[1\\] Gruntkowska K. et al EF21-P and Friends: Improved Theoretical Communication Complexity for Distributed Optimization with Bidirectional Compression\n"}, {"review_id": "I246Y1SCgi", "reviewer": "Reviewer_EaSZ", "summary": "This paper proposes a new distributed convex optimization problems with bidirectional compression. This algorithm, named as 2Direction, is claimed to be the first that improves upon the communication complexity of the vanilla accelerated gradient descent.", "questions": "See above", "limitations": "N/A", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The 2Direction method seems novel\n2. The studied problem is well-motivated", "weaknesses": "1. The proof of the algorithm is rather complicated. I cannot verify the solidness of the established theorem given the very tight review timeline. The appendix I, J, K, L and O are very scary given the symbolically computed expressions. It is basically a computer-aided proof. I will discuss with other reviewers and chairs on how to check this proof.\n\n2. In table 2, some terms are associated with $\\Omega$ while the others are not. Please clarify the reason.\n\n3. 2Direction uses a unbiased compressor and a contractive compressor in algorithm design. Can 2Direction use unbiaed compressors for both w2s and s2w compression? Can 2Direction use contractive compressors for both w2s and s2w compression?\n\n4. Does 2Direction have the smallest communication complexity when r = 0 compared with existing uni-directional compression algorithms?\n\nSince I cannot verify the correctness of the established theorem, I would recommend borderline reject at this stage.  ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the comments!\n\n> The proof of the algorithm is rather complicated. I cannot verify the solidness of the established theorem given the very tight review timeline. The appendix I, J, K, L and O are very scary given the symbolically computed expressions. It is basically a computer-aided proof. I will discuss with other reviewers and chairs on how to check this proof.\n\n> Since I cannot verify the correctness of the established theorem, I would recommend borderline reject at this stage.\n\nWe really appreciate your time and effort, thank you! **But it is not fair to leave us with the comment saying you would recommend rejection because you \"cannot verify the correctness of the established theorem.\" We know the proofs and results are correct.** **Please ask us questions regarding the proof. We will be happy to answer them.** The computer-aided part is only listed starting from page 45. Before that, do you have any concerns regarding our proofs? Note that we give a brief overview of our proof in Section 7.\n\n * We are not asking to check the generated formulas. It is sufficient to check that we generated the formulas correctly. So it is sufficient to check and understand the code on pages 64-71. The formulas are only listed for reproducibility purposes.\n\n* **The computer-aided proofs are very popular and becoming an essential instrument in modern optimization methods. Recent breakthroughs weren't possible without them. See, for instance, the celebrated SAG paper \\[2\\] (the authors were awarded the Lagrange prize in optimization for this work)! The modern era of variance-reduced methods (SVRG, Katyusha, SAGA, ...) would not be possible without this paper; as this work started this subfield.** We can list many more papers: \\[3,4\\]. Besides this, formal theorem provers are becoming popular as well, e.g., the Lean theorem prover developed by Leonardo de Moura.\n\n* Let us briefly give additional details why we need symbolic computation in a part of the proof. The first time we use this is on Line 704 (formula (87)). We need it there to substitute $\\nu$ in (86). In this place, we agree that the computation assistant is not necessary. But it is becoming clear that it is necessary when we get (89). In order to get (89), we have to multiply a large number of fractions. The situation with the number of fractions, when we substitute the parameters to (91), is even worse, and the number of fractions that we have to multiply is even bigger. The symbolic computations are simply used to multiply brackets for us. Note that we could do it without the assistant, but the probability of making mistakes is much higher. Another place where we use symbolic comutations is when we check assertions in Section O. There, we also could it do it by hand, but it would be more difficult without a computation assistant.\n \n* It is clear that the method *requires* a computation assistant, and there is nothing that we can do here. **We could write the proof without the computer assistant, but it would make the proof even larger and less reader-friendly. The probability of making a mistake would be higher without the assistant.**\n\n> In table 2, some terms are associated with $\\Omega$ while the others are not. Please clarify the reason.\n\nBecause in some papers, the *full* convergence rate is not transparent. For instance, take a look at Theorem 1 from \\[1\\]. Just to be on the safe side, for all the methods with $\\Omega$, we say that the complexity is not better than $\\Omega(...).$ We agree that we should leave a footnote to explain that.\n\n> 2Direction uses a unbiased compressor and a contractive compressor in algorithm design. Can 2Direction use unbiaed compressors for both w2s and s2w compression? \n\nYes, it can! Because one can get the biased compressor from an unbiased one using the following transformation: $\\frac{1}{\n\\omega + 1} \\times C$ (see Lines 75-76)\n\n> Can 2Direction use contractive compressors for both w2s and s2w compression?\n\nNo, it can't. In the proofs, it is important that clients use an unbiassed compressor. The use of contractive compressors for both w2s and s2w compression is a very challenging task. The known methods that work with contractive compressors in both directions cannot even match the communication complexity guarantees of the vanilla GD method (e.g., see the EF21-BC method and its complexity \\[5\\]). The obtained communication complexities of such methods are much worse than the same methods but using the identity compressor (i.e., variants that do not compress anything). Before our work, even with unbiased compressors an improvement over baselines not performing any compression was not achieved, and the vanilla AGD method had the best communication complexity in the convex setting. \n\n> Does 2Direction have the smallest communication complexity when r = 0 compared with existing uni-directional compression algorithms?\n\nYes, it is! We explain it Lines 240-241 and proof in Section S. we show that the communication complexity of 2Direction is not worse than the communication complexity of ADIANA which is the current SOTA method in the uni-directional (w2s) setting!\n\n**If you have any additional questions, please ask us. We believe that we addressed all questions. We kindly ask the reviewer to reconsider the score.**\n\n\\[1\\] Liu X. A Double Residual Compression Algorithm for Efficient Distributed Learning\n\n\\[2\\] Schmidt M. et al Minimizing Finite Sums with the Stochastic Average Gradient\n\n\\[3\\] Drori Y.  et al Performance of first-order methods for smooth convex minimization: a novel approach.\n\n\\[4\\] Grimmer B. Provably Faster Gradient Descent via Long Steps\n\n\\[5\\] Fatkhullin I. et al. EF21 with bells & whistles: practical algorithmic extensions of modern error feedback\n"}, {"review_id": "pDjtei18y7", "reviewer": "Reviewer_AqDA", "summary": "This paper proposes 2Direction, a new GD-based distributed training algorithm for convex optimization problems. The improvement of 2Direction over previous works that target communication complexity in the convex case is that 2Direction is both accelerated and allows for bi-directional compression. 2Direction is proven to offer better communication complexity than previous works in certain regimes and not being worse otherwise.", "questions": "1.\tCan the authors comment on weaknesses (1)(2)(3)?\n2.\tCan the authors shed more light on why with small probability exact values must be sent? Clearly the proof requires this, but more intuition on whether this is inherent or just an artifact of the proof technique would be helpful. \n3.\tThe comparison/analysis is done with TopK (downlink) and RandK (uplink) as example compressors. However, these compressors have weaker worst-case MSE guarantees in comparison to SOTA compression techniques that provide asymptotically better worst-case tradeoffs between communication and MSE. Can the authors shed light on that? In particular, if compressors with stronger guarantees are used, can that affect the communication complexity analysis? E.g., since line 10 in algorithm 1 can be viewed as an instance of the distributed mean estimation problem, can the usage of techniques such as [1]-[3] lead to better communication complexity or alter the conclusions? (this also relates to weakness (1))\n4.\tAssumption 2.4 – while the independence between the workers in the uplink direction is indeed desired, why independence with the downlink direction is important?  \n\n[1] Suresh, Ananda Theertha, et al. \"Distributed mean estimation with limited communication.\" International conference on machine learning. PMLR, 2017.\n\n[2] Davies, Peter, et al. \"New Bounds For Distributed Mean Estimation and Variance Reduction.\" International Conference on Learning Representations, 2021.\n\n[3] Vargaftik, Shay, et al. \"Eden: Communication-efficient and robust distributed mean estimation for federated learning.\" International Conference on Machine Learning. PMLR, 2022.", "limitations": "The authors clearly stated a limitation of their work in Section 8. I do have few additional suggestions about the memory/computational efficiency aspect. Moreover, since federated learning (FL) is mentioned as motivation, it worth discussing whether 2Direction can be potentially extended to common FL scenarios with partial participation and stochastic gradients.\n\nI did not recognized potential negative broader impact.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1.\tThe scope of the paper and the main problem are well-defined and clear. \n2.    The paper considers bi-directional compression. SO far, bi-directional compression received less attention in the literature that mostly considers only compressing uplink communication. \n2.\tThe paper’s theoretical analysis and results are mostly clear and solid. The paper theoretically compares 2Direction to several SOTA alternatives.\n3.\tThe design choices of 2Direction are well articulated.", "weaknesses": "1.\tThe communication complexity analysis and its optimization are not fully clear. Specifically, there is dependency between the round cost and the number of communication rounds (i.e., via K and w). \n2.\t2Direction (Algorithm 1) requires more memory and compute resources in comparison to some previous methods such as DG, AGD and EF21-P + DIANA  (e.g., 2Direction requires arrays for storing h, v and solving (11)-(12)-(23)). This overhead and its consequences, especially in federated learning contexts, are not discussed.\n3.\tThe experimental part is somewhat weak (appears in the supplementary material and contains a single logistic regression problem with two datasets).\n4. The presentation can be improved. In particular, the paper is not self contained and relies on the supplementary material to convey main ideas. Notably: (i) Section 4 points to Sections B and C to articulate design choices; (ii) Section 5.2 points to equations 58 and 63", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review!\n\n> The communication complexity analysis and its optimization are not fully clear. Specifically, there is dependency between the round cost and the number of communication rounds (i.e., via K and w).\n\n* The rounds costs and the number of communication rounds depend on $K$ ($K_{\\omega}$ and $K_{\\alpha}$) and $\\omega$ in all methods (see Table 1). The parameters $K$ and $\\omega$ are defined by a chosen compressor. For instance, in the case of Rand$K$, $K_{\\omega} = K$ and $\\omega = \\frac{d}{K} - 1.$ In the case of Top$K$, $K_{\\alpha} = K$ and $\\alpha = \\frac{K}{d}.$\n* One can find the communication complexities in (16) or in Table 1 (Comm. Compl = # Communication Rounds × Round Cost) as functions of $\\omega,$ $\\alpha$ and $K.$ For the Rand$K$ and Top$K$ compressors, we can substitute the parameters to Table 1 [2Direction] or (16) and obtain the communication complexity  \nRound Cost × \\# Communication Rounds = $K \\times \\left(\\sqrt{\\frac{L}{\\mu}} \\frac{d}{K} + \\sqrt{\\frac{L_{\\max}}{n \\mu}} \\frac{d}{K} + \\frac{d}{K}\\right) = d \\sqrt{\\frac{L}{\\mu}} + d \\sqrt{\\frac{L_{\\max}}{n \\mu}} + d.$  \nNote that this communication complexity is never worse than the communication complexity of AGD. At the same it is very pessimistic because when we were deriving it we used that $\\alpha = \\frac{K}{d}$ in Top$K.$ However, in practice, $\\alpha \\gg \\frac{K}{d}.$ \n\n* Let us illustrate that. For simplicity, let us take Top$K$ with $K = 1.$ Then, one can show that  $||C(x) - x||^{2} = ||x||^2_2 -||x||^2_{\\infty}.$ One can see that the \"effective\" $\\alpha = ||x||^2_{\\infty} / ||x||^2_2.$ It depends on the distribution of coordinates $x$. Yes, we can be unlucky, and in the case when all coordinates are equal, we get the worst case $\\alpha = 1 / d.$ But in practice \\[6, 7\\], the distribution of coordinates is very non-equal to each other.\n\n> 2Direction (Algorithm 1) requires more memory and compute resources in comparison to some previous methods such as DG, AGD and EF21-P + DIANA.\n\n* The vanilla AGD method also requires additional memory compared to the vanilla GD method due to the fact that AGD uses the acceleration momentum technique. For instance, look at the implementation of AGD in \\[1, p.64\\]. It also has additional variables compared to GD.\n* The same reasoning applies to 2Direction and EF21-P + DIANA. Indeed, 2Direction requires more memory. However, it requires more memory by a **multiplicative constant factor**. In other words, the memory complexity of 2Direction, EF21-P + DIANA, AGD, and GD is $O(d),$ where the $d$ is the dimension of the problem. All methods have the same  $O(d)$ memory complexity. But we agree that the constant factors that the Big-O notation hides are different. \n\n> The experimental part is somewhat weak...\n\nOur work is theoretical, and we wish our work to be judged as such. We agree that the experiments are important to test the theoretical bounds. One can see that the behavior of methods in experiments in Section Q supports the theory. We analyze the logistic regression problem, which is the most popular convex optimization task in machine learning. Our method is designed only for convex problems, so we do not provide experiments with neural networks. Note that we provide the new theoretical SOTA communication complexities in the bidirectional convex setting. \n\n> Can the authors shed more light on why with small probability exact values must be sent? ...\n\nWe believe that this is the nature of all *variance-reduced accelerated* methods. If you look at all other methods \\[1, 2, 3, 4\\] that accelerate variance-reduced methods, they all require intermittent computations via double loop or probabilistic switching (as it was done in our paper)\n\n> The comparison/analysis is done with TopK (downlink) and RandK (uplink) as example compressors. ...\n\nOne can use any compressor in line 7 of Alg. 1 if it is unbiased (see Def 2.3). Also, one can use any compressor in line 13 of Alg. 1 if it is *biased* (see Def 2.2). The theory will hold for any choice of them. One can take his/her favorite compressor and use it our method. It is only necessary to find $K$ and $\\omega.$ The parameters $K$ is the number of bits/coordinates that a compressor preserve. The parameters $\\omega$ and $\\alpha$ usually can be also easily estimated. For instance, Rand$K$ has $\\omega = \\frac{d}{K} - 1.$ Note that there are many more compressors \\[5\\]. The choice of TopK and RandK (as examples) is motivated by the fact that these compressors are the most popular in the literature, and they can be easily explained to a reader who is not from the community of distributed compressed methods.\n\n> Assumption 2.4 – while the independence between the workers in the uplink direction is indeed desired, why independence with the downlink direction is important?\n\nThe independence of the uplink and the downlink directions is important. Also, it is important that the compression operators are independent across different iterations. Otherwise, we can not use the conditional expectation trick in the proofs. For instance, we use independence in Lines 528 and 519.\n\n**We believe that we addressed all questions. We kindly ask the reviewer to reconsider the score.**\n\n\\[1\\]: Lan G. First-order and stochastic optimization methods for machine learning\n\n\\[2\\] Lan G. et al  A unified variance-reduced accelerated gradient method for convex optimization\n\n\\[3\\] Zeyuan A. Katyusha: The First Direct Acceleration of Stochastic Gradient Methods\n\n\\[4\\] Kovalev D et al Don’t Jump Through Hoops and Remove Those Loops: SVRG and Katyusha are Better Without the Outer Loop\n\n\\[5\\] Xu H. GRACE: A Compressed Communication Framework for Distributed Machine Learning\n\n\\[6\\]: Beznosikov, A., Horvath, S., Richtarik, P., and Safaryan, M. On biased compression for distributed learning\n\n\\[7\\]: PowerSGD: Practical Low-Rank Gradient Compression for Distributed Optimization Thijs Vogels, Sai Praneeth Karimireddy, Martin Jaggi\n"}]

Author rebuttal:
Dear AC and Reviewers,

Thank you for your work and effort. In this comment, we quickly clarify our main contribution to the community.

The field of optimization methods with compressed communication methods is very popular, rapidly growing, and will only increase in importance (e.g., see Jue Wang, Yucheng Lu, Binhang Yuan, Beidi Chen, Percy Liang, Christopher De Sa, Christopher Re, Ce Zhang. CocktailSGD: Fine-tuning Foundation Models over 500Mbps Networks, ICML 2023 where the authors fine-tune a large language model in  distributed manner, and bidirectional compression was essential). 

There are hundreds, and maybe even thousands of papers that design optimization methods to reduce communication overhead. 

**However, as far as we know, none of the previous papers provided theoretical communication guarantees that would be no worse than the communication guarantees of the vanilla accelerated Nesterov's method (AGD), let alone guarantees that can in some regimes be substantially better. In short, we believe that our work is an important theoretical breakthrough in an important subfield of ML.**

Before our paper, the best theoretical guarantees were obtained by AGD that **does not compress**. The communication complexity of AGD is $d \times \sqrt{\frac{L}{\mu}} \ln \frac{1}{\varepsilon}$ (= # of send bits/coordinates $\times$ # of iterations/rounds). **Our paper is the first one that broke this fundamental baseline in the bidirectional setting.** 

**We believe that the low scores given to us by some reviewers do not reflect the quality and import of our work.**

Thank you again, we really appreciate your reviews and comments! Please ask us any questions!

authors

Meta-review: This paper focuses on how to reduce the communication cost for accelerated gradient algorithms in the distributed setting. The proposed bi-directional compression accelerated gradient algorithm improves the communication cost of non-accelerated gradient algorithm. The theoretical result looks promising. The theoretical proof is nontrivial and uses many symbiotic computations.

The reviewers had a long discussion about the decision about this paper and did not achieve a consensus. Consider that this is the first work to explore how to optimize the communication cost for Nesterov's accelerated gradient algorithms in distributed setting (which is non trivial and challenging), we decided to accept this paper. In the meantime, we want to point out the readability and the clarity need to be improved. In particular,

It is a tough work to verify the correctness of the current proof. The theoretical proof needs to be simplified, although some portion of complexity is by nature of the (Nesterov's) accelerated gradient algorithm. For example, authors can compare the proof for AGD and use the key results in proving AGD as the reference. Symbolic computations are not encouraged to use in the proof, since it buries the proof insights and makes the proof look over of construction. Some symbolic computations can be replaced by choosing the learning rate appropriately to achieve the same purpose.

The algorithm can be more of structure. The current algorithm description is too fragmented and too long. The assumed background for readers can be with AGD. The comparison to other existing bi-directional compression algorithms such as [3, 9, 10] need to be discussed too. Provide the explanation why the biased compression operator can only be applied to one side, unlike [10].

Empirical study: although we treat this paper as a theoretical work, it does not mean the empirical study is not important. The most important result is still expected to be included in the main body of this paper.
Decision: Accept (poster)