EF21-P and Friends: Improved Theoretical Communication Complexity for Distributed Optimization with Bidirectional Compression
Authors: Kaja Gruntkowska
Alexander Tyurin
Peter Richtárik
Venue: Submitted to ICLR 2023 (2023)
Keywords: communication compression
bidirectional compression
error feedback
distributed optimization

Abstract: The starting point of this paper is the discovery of a novel and simple error-feedback mechanism, which we call EF21-P, for dealing with the error introduced by a contractive compressor. Unlike  all prior works on error feedback, where compression and correction operate in the dual space of gradients,  our mechanism operates in the primal space of models. While we believe that EF21-P may be of interest in many situations where it is often advantageous to perform model perturbation prior to the computation of the gradient (e.g., randomized smoothing and generalization), in this work we focus our attention on its use as a key building block in the design of communication-efficient distributed optimization methods supporting bidirectional compression. In particular, we employ EF21-P as the mechanism for compressing and subsequently error-correcting the model broadcast by the server to the workers. By combining EF21-P with suitable methods performing worker-to-server compression, we obtain novel methods supporting bidirectional compression and enjoying  new state-of-the-art theoretical communication complexity for convex and nonconvex problems. For example, our bounds are the first that manage to decouple the  variance/error coming from the workers-to-server and server-to-workers compression, transforming a multiplicative dependence to an additive one. In the convex regime, we obtain the first bounds that match the theoretical communication complexity of gradient descent. Even in this convex regime, our algorithms work with biased gradient estimators, which is non-standard and requires new proof techniques that may be of  independent interest. Finally, our theoretical results are corroborated through suitable experiments.

Under review as a conference paper at ICLR 2023
EF21-P AND FRIENDS: IMPROVED THEORETICAL COMMUNICATION COMPLEXITY FOR DISTRIBUTED OPTIMIZATION WITH BIDIRECTIONAL COMPRESSION
Anonymous authors Paper under double-blind review
ABSTRACT
The starting point of this paper is the discovery of a novel and simple emror- feedback mechanism, which we call EF21-P, for dealing with the error introduced by a contractive compressor. Unlike all prior works on error feedback, where compression and correction operate in the dual space of gradients, our mecha- nism operates in the primal space of models. While we believe that EF21-P may be of interest in many situations where it is often advantageous perform model perturbation prior to the computation of the gradient (e.g., randomized smoothing key building
and generalization), in this work we focus our attention its block in the design of communiiation--ffiiien distributed optimization methods supporting bidirectional compression. In particular, we employ EF21-P as the mechanism for compressing and subsequently coror-corretting the model broad- cast by the server the workers. By combining EF21-P with suitable methods performing worker-tooserrvee compression, we obtain novel methods supporting bidirectional compression and enjoying new state-of-the-art theoretical communi- cation complexity for convex and nonconvex problems. For example, our bounds are the first that manage to decouple the variance/error coming from the workers- to-server and server-to- socer-to-oood to-workess compression, transforming multiplicative de- pendence to an additive one. In the convex regime, we obtain the first bounds that match the theoretical communication complexity of gradient descent. Even in this convex regime, our algorithms work with biased gradient estimators, which is non- standard and requires new proof techniques that may be of independent interest. Finally, our theoretical results are corroborated through suitable experiments.
INTRODUCTION: ERROR FEEDBACK IN THE PRIMAL SPACE
The key moment which ultimately enabled the main results of this paper was our discovery of new and simple crror-feedback technique, which we call EF21-P, that operates in the primal space of the iterates/models instead of the prevalent approach to error-feedback (Stich & Karimireddy, 2019; Karimireddy et al., 2019; Gorbunov et al., 2020b; Beznosikov et al., 2020; Richtárik et al., 2021) which operates in the dual space of gradients To describe EF21-P, consider solving the optimization problem
min f(x): xER2
where f dRdd_ - a smooth but not necessarily convex function. Given a contractive compression operator C RRd + Rd i.e.. a (possibly) randomized mapping satisfying the inequality
E
[[(x) =0| < (1 - a) ||~||
Ve
Rd
for some constant a E (0, 1]. our EF21-P method aims to solve (1) via the iterative process
r+ = VV(("") +++ = v0 + + (2 cz ---1-- w'),
!Our method is inspired by the recently proposed emror feedback mechanism, EF21, of Richtárik et al. (2021), which compresses the dual vectors, i.e. the gradients. EF21 is currently the state-of ofth--of error feed- back mechanism in terms of its theoretical properties and practical performance (Fatkhullin et al., 2021). If we wish explicitly highlight its dual nature, we could instead meaningfully call their method EF21-D.

---

Under review as a conference paper at ICLR 2023
where Y 0 is stepsize, 20 IR is the initial iterate, w 20 R is the initial iterate shift, and C is an instantiation of a randomized contractive compressor satisfying (2) sampled at time t. Note that when C is the identity mapping (a 1), then w' = z' for all and hence EF21-P reduces to vanilla gradient descent (GD). Otherwise, EF21-P is a new optimization method. Note that (x") iteration of EF21-P can be equivalently written in the form of perturbed gradient descent
++1
VV + (*),
c'= w w'²) (x' -w²-))
Note that the model perturbation Ç is not a zero mean random variable", and that in view of (2), the size of the perturbation can be bounded via
E [I | (0","""] w s ao1-a)lo 1 w 11
(4)
From now on, will write C E B(a) to mean that C is compressor satisfying (2).
1.1 EF21-P THEORY
If is L-smooth and p-strongly convex, we prove that both æ' and w converge to to = arg min f at a linear rate, in ((*/au)) log 1/)) iterations in expectation (see Section D). Intuitively speaking, this happens because the frror-feedback mechanism embedded in EF21-P makes sure that the quantity on the right-hand side of (4) converges to zero, which forces the size of the error C' caused by the perturbation to converge zero as well. However, EF21-P can be analyzed in the smooth nonconvex regime as well, in which case it finds an E-approximate stationary point. The precise convergence result, proof, as well as extension that allows to replace V f((w) with stochastic gradient under the general ABC inequality introduced by Khaled & Richtárik (2020) (which provably holds for various sources of stochasticity, including subsampling and gradient compression) be found in Section E.
1.2 SUMMARY OF CONTRIBUTIONS
We believe that EF21-P and its analysis could be useful in various optimization and machine learning contexts in which some kind of iterate perturbation plays an important role, including randomized smoothing (Duchi al., 2012), perturbed SGD (Vardhan & Stich, 2022), and generalization (Orvieto et al., 2022). In this work we do not venture into these potential application areas and instead focus all our attention on a single and important use case where, as we found out, EF21-P leads to new tatte-of-the-aee art methods and theory: the design of communication -effetiinnn distributed optimization methods supporting bidirectional (i.e., workers-to-sere to-server and server-to- worker)s compression.
In particular, we use EF21-P as the mechanism for compressing and subsequently curorccorg the model broadcast by the server to the workers. By combining EF21-P with suitable methods ("friends" in the title of the paper) performing worker-to-server compression, in particular, DIANA (Mishchenko et al., 2019; Horváth et al., 2022) or DCGD (Alistarh et al., 2017: Khirirat et al., 2018), we obtain novel methods, suggestively named EF21-P DIANA (Algorithm 1) and EF21-P DCGD (A (Algorithm 2), both supporting bidirectional compression, and both enjoying new state-of- the-art theoretical communication complexity for convex and nonconvex problems. While DIANA and DCGD were not designed to work with compressors from B(a) to compress the workers-to- -to server communication, and can in principle diverge if used that way, they work well with the smaller class of randomized compression mappings C: I2d Ied characterized by
E [[((x)) = x.
E [|(())) x0|? - w 1|
Vo E RRd
(5)
where w 2 0 is constant. We will write C E U(w) to mean that C satisfies (5). It is well known that if E U(w), then c/(++) E (1/(-1)), which means that the class U(w) indeed more narrow.
Convex setting. EF21-P DIANA provides new sate-of-the-ate convergence rates for distributed optimization tasks in the strongly convex (see Table and general convex regimes. This is the first method enabling bidirectional compression that has the server-to-workers and workers-to-server communication complexity better than vanilla GD. When the workers calculate stochastic gradi- ents (see Section 3.1), we prove that EF21-P DIANA improves the rates of the existing methods.
II fact, this only happens in the non-interesting case when C²-1 is identity with probability 1.
2

---

Under review as a conference paper at ICLR 2023
We prove that EF21-P DCGD has an better convergence rate than EF21-P + DIANA in the interpolation regime (see Section 3.2).
Nonconvex setting, In the nonconvex setting (see Section 4), EF21-P DCGD is the first method using bidirectional compression whose convergence rate decouples the noises coming from the workers-to-server and server-to-workers compression from multiplicative (see Table 2). Moreover, EF21-P + DCGD provides the new state-of-the-art convergence rate in the low accuracy regimes (E is small the of workers n is large). Further, we provide examples of optimization problems where EF21-P + DCGD outperforms previous state-of-the-art methods even in the high accuracy regime.
additive dependence
Unified SGD analysis framework with the EF21-P mechanism. Khaled & Richtárik (2020) provide unified framework for the analysis of SGD-type methods for smooth nonconvex problems. Their framework helps to analyze SGD and DCGD under various assumptions, including i) strong and weak growth, ii) samplings strategies, e.g., importance sampling. Unfortunately, the theory relies heavily on the unbiasedness of stochastic gradients, as result of which it is not applicable to our methods (in EF21-P DCGD, E [gg'] = Vf(w") + V=(=")). Therefore, we decided to rebuild the theory from scratch. Our results inherit all previous achievements of (Khaled & Richtárik, 2020), and further generalize the unified framework to make it suitable for optimization methods where the iterates are perturbed using the EF21-P mechanism. We believe that this is contribution with potential applications beyond the focus of this work (distributed optimization with bidirectional compression). This development is presented in Section E; our main results from Section 4.1-4.3 which cater to the nonconvex setting are simple corollaries of our general theory.
2 DISTRIBUTED OPTIMIZATION AND BIDIRECTIONAL COMPRESSION
In this paper, we consider distributed optimization problems in strongly convex, convex and non- convex settings. Such problems arise in federated learning (Konečný et al., 2016; McMahan et al., 2017) and in deep learning (Ramesh al., 2021). In federated learning, a large number of work- ers/devices/nodes contain local data and communicate with parameter-server that performs opti- mization of a function a distributed fashion (Ramaswamy et al., 2019). Due to privacy concerns and the potentially large number of workers, the communication between the workers and the server a bottleneck and requires specialized al algorithms capable of reducing the communication overhead. Popular algorithms dealing with these kinds of problems are based on communication compression (Mishchenko et al., 2019; Richtárik et al., 2021; Tang et al., 2019). We consider the distributed optimization problem of the form
min = xERd
(6)
where n is the number of workers and ft Rd + R smooth (possibly nonconvex) functions for
all i E [n] = (I..... n.. We assume that the functions fi are stored on n workers. Each of them directly connected to server that orchestrates the work of the devices (Kairouz et al., 2021), i.e., the workers perform some calculations and send the results to the server, after which the server does calculations and sends the results back to the workers and the whole process repeats.
Throughput the work we will refer to a subset of these assumptions:
Assumption 2.1. The function is L-smooth, i.c., [z) ff(y)) S L || vll Vz, Rd.
Assumption 2.2. The functions f smoohh for all i E [m]. Ī is constant such that EE= V f(x) V < i || 2/l² for all x, y E IRd and Lmax == maxie[n] Li-
Assumption 2.3. The functions fi are convex and the function f is j-strongly convex with μ 2 0 and attains a minimum at some point x E Rdd.
To avoid ambiguity, the constants L, L, and L; are the smallest such numbers.
Lemma 2.4. Assumptions 2.1, 2.2 and 2.3 hold, then Î. S Timax nL and I. < ī. S VnL.
2.1 COMMUNICATION COMPLEXITY OF VANILLA GRADIENT DESCENT
Solving the aforementioned optimization problem involves two key steps: i) the workers send results to the server Seerver-to-worker communication), ii) the server sends results to the workers (workers-
3

---

Under review as a conference paper at ICLR 2023
to-server communication). Let us first consider how this procedure works in the case of GD:
x =
fi(x').
It is well known that if the function f is L-smooth and μ-strongly convex (see Assumptions 2.1 and 2.3), then GD with stepsize ? = l/z. returns an E-solution after O (4/4 log 1/)) steps. In dis- tributed setting, GD would require i) the workers to send Vfi(=') to the server ii) the server to send rt+1 to the workers or, alternatively, ii) the server to send A n - Vfi(=') to the workers, depending on whether the iterates x' are updated on the server or on the workers. Assuming that the communication complexity is proportional to the number of coordinates, the server-to-worken and workers-to-servee communication complexities are equal O lo)
2.2
WORKERS-TO-SERVE (=UPLINK) COMPRESSION
We now move on to more advanced algorithms that aim to improve the workers-to- to-serv communi- cation complexity. These algorithms assume that the server-to- server-to-workers communication complexity negligible and focus exclusively on sending the message from devices to the server. Such an approach can be justified by the fact that broadcast operation may in some systems be much faster than gather operation (Mishchenko et al., 2019; Kairouz et al., 2021). Moreover, the server can be considered to be just an abstraction representing "all other nodes", in which case server-to-worker communication does not exist at all.
The primary tools that help reduce communication cost are compression operators, such as vector sparsification and quantization (Beznosikov et al., 2020). However, compression injects error/noise into the process, formalized in (2) and (5). Two canonical examples of compressors belonging to these two classes are the TopK E B(+/a) and Rand E U(4/k 1) sparsifiers. The former retains the K largest values of the input vector, while the latter takes K random values of this vector scaled by d/s (Beznosikov et al., 2020). Further examples of compressors belonging to BB(a) and U(w) can be found in (Beznosikov et al., 2020).
The theory of methods supporting workers-to- to-serv compression is reasonably well developed. In the convex and strongly convex setting, the current state-of-the-arr methods are DIANA (Mishchenko et al., 2019), ADIANA (Li et al., 2020), and CANITA (Li & Richtárik, 2021). In the nonconvex setting, the current state-of-the-eee regime) and MARINA, DASHA, FRECON, and EF21 (Gorbunov al., 2021; Tyurin & Richtárik, 2022b;a; Zhao et al., 2021; Richtárik et al., 2021) (in the high accuracy regime).
methods are DCGD (Khaled & Richtárik, 2020) (in the low accuracy
To see that these types of algorithms can achieve workers-to-sene is no worse than that of GD, let us consider the DIANA method. In the strongly convex case, DIANA (Khaled et al., 2020) has the convergence rate O (((1 4/n) Amax// + w) log 1/e) Using the RandK compression operator with K = d/n, the workers-to-servee complexity is not greater than
communication complexity that
0 (1 #) Lmax + w) log 1 O ((dlaga + log t)
-(((
meaning that DIANA's complexity is better than GD's complexity O (dL// log 1/8) (recall that Imax S L..). The same reasoning applies to other algorithms in the convex and nonconvex worlds.
2.3 BIDIRECTIONAL COMPRESSION
In the previous section, we showed that is possible to improve workers-tor -ookerre-t communication complexity of GD. But what about the server-to-ue server-to-workers compression? Does there exist a method that would also compress the information sent from the server to the workers and obtain the workers- to-server and server-to-we toookers communication complexities at least good with the vanilla GD method? As far as we know, the current answer to the question is NO!
Bidirectional compression has been considered in many papers, including (Horváth al., 2019; Tang et al., 2019; Liu et al., 2020; Philippenko Dieuleveut, 2020; 2021; Fatkhullin et al., 2021). In Table 1, provide comparison of methods applying this type of compression in the strongly convex setting. Let us now take a closer look at the MCM method of Philippenko & Dieuleveut (2021). For simplicity, we assume that the server and the workers RandK compressors with
4

---

Under review as a conference paper at ICLR 2023
Algorithm EF21-P DIANA
1: Parameters: learning rates > (for learning the model) and / > 0 (for learning the gradient shifts); initial model æ" E _t (stored on the server and the workers); initial gradient shifts .i...., ......,,g, Ag IRd
(stored on the workers); average of the initial gradient shifts h = 2 hg (stored the server); initial model shift w = _² e IRd (stored on the server and the workers) do 1.............. n parallel
2: for L 0.
4:
m. C. (V
Worker i compresses the shifted gradient vin the dual compressor CP E U(w)
5:
Send compressed message m. to the server
6:
h,+1 h + Bm!
Worker é updates local gradicut shift with stepsize
end
m' > m
Server averages the messages received from the workers Server updates the average gradient shift so that = Disr K
h h' + 3m'
10:
ge h' +m²
Server computes the gradient estimator
11:
x 24 = r
Server takes a gradient type with stepsize "y Server compresses the shifted model via the primal compressor C (a)
12:
ptt c (x
w²
13:
w+ = w² + +pt+1
Server updates the model shift
14:
Broadcast compressed message p² pt+ to all workers
15: for 1, 1....,, n in parallel do
16: 4 w +
Worker updates its local capy the model shift
17:
end for
18:
end for
parameters K, and Kw, respectively. The server-to-workers communication complexity of MCM is not less than
3/2 maat Ω (Kss (1 (1+ w/
Lannx log Ω
(20 K.
8/2
Lunna log !
Jn
Thus, for any K, E [1, d], the server-to-worker communication complexity is worse than the GD's complexity O ( AL log l/e) by a factor of d3/3 /2/// The same reasoning applies to Dore (Liu et al., 2020) and Artemis (Philippenko & Dieuleveut, 2020):
K, x Widie
Liaax log 1 S
d2 Limax log
R.n
It turns out that find an example of problem (6) with Lmax n.L. Therefore, in the worst case scenario, the server-to-we workers communication complexity can be up to d/K, times worse than the GD's complexity for any K E [1.
2.4 NEW METHODS
We are now ready to present our main method EF21-P DIANA (see Algorithm 1), which is combination of our EF21-P mechanism described in Section (and analyzed Sections and E)
and the DIANA method of Mishchenko et al. (2019); Horváth et al. (2022); Gorbunov et al. (2020a). The pseudocode of Algorithm should be self-explamatory. If the gradient shifts {ht} employed by DIANA are initialized to zeros, and we choose 3 = 0, then DIANA reduces to DCGD, and EF21-P DIANA thus reduces to EF21-P DCGD (see Algorithm 2). If we further choose the Auaa/eg compressors C.P to be identity mappings, then EF21-P DCGD further reduces EF21-P.
3 ANALYSIS IN THE CONVEX SETTING
Let us first state the convergence theorem.
Theorem 3.1. Suppose that Assumptions 2.1, 2.2 and 2.3 hold, B w+I: set a w and let < min
Vna 20
}. Then Algorithm I returns x! such that
160m
10O0. (w+1))
|| x 1| +E [f(x") f(x*)] 5 (1- mp)² vo.
27
where Vu:- :-
2- ||000 x" |1]] + (f(22) - f(x²)) + STw(w+1) Σn |A1 - V/((>')1??
5

---

Under review as a conference paper at ICLR 2023
Table 1: Strongly Convex Case. The number of communication rounds to get an E-solution [Ell -- I21 S E) up to logarithmic factors. To make comparison easier, if a method works with biased compressor, we assume that the biased compressor is formed from the unbiased compressors and the following relations hold: wi + 1/o. and w, + 1/,,, where ww and w, are parameters of workers-to-servee -eeervr and server-to-worknn compressors, accordingly.
Method
Communication Rounds
Limitations
DIANA
Faana
No servertto-worker compression.
(Mishchenko al.,
Dore,
(Liu et al., 2020)
diyii Aauax
(Philippenko & Dieuleveut, 2020)
MOM
(( 2/2
weewer 1/2 VR
Lmax
(Philippenko & Dieuleveut, 2021)
w.) & + v (went
EF21-P DIANA (new)
(Thoorem 3.1)
presented bit less accurately: + wxx Aama +
(1 + wi) + (utee DJor + Tmaax or presented bit less accurately: (I we + wh Limax
EF21-P DCGD (new) (Theorem G.3)
Interpolation regime: vf(==)= =
The above result means that EF21-P DIANA guarantees E-solution after
TNEW 0
((1N +
/ w
L w Lmax + +w) log
+
om
steps. Noting that s i. S L Timax and
v
2x an
We 2n
this gives
2a
TNEW = =0 (((1
Lox + +w) log !
Comparing this rate with rates achieved by the existing algorithms (see Table 1), our method is the first one to guarantee the decoupling of noises and w coming from the server-to-workers and the workers-to-servee compressors. Moreover, it is more general, the server-to- workers compression can use biased compressors, including TopK and RankK (Safaryan et al., 2021). These can in practice perform better than the unbiassed ones (Beznosikov et al., 2020; Vogels et al., 2019).
As promised, let us now show that EF21-P DIANA has the communication complexity better than GD. For simplicity, we assume that the server and the workers use TopK and RandK compressors respectively. Since under this assumption = d/k - and K/a, the gerver-to-worken and the workers-to-server communication complexities equal
o (K
x
( ap
+
L w Lmax + log :) =0 ((at) +
Vor
d Lmnx
log
Note that T.max nL and < Vnl. so this complexity is no worse than the GD's complexity for any K E [1, The general convex case is discussed in Section F.I.
3.1 STOCHASTIC GRADIENTS
In this section, we assume that the workers in EF21-P + DIANA calculate stochastic gradients instead of exact gradients:
Assumption 3.2 (Stochastic gradients). For all x e Rd, stochastic gradients f((()) are unbiased and have bounded variance, i.e., E[Vf((x)] = ff(),, and [(())((() (z) 12] < o² for all
i [n], where o² > O.
We now provide generalization of Theorem 3.1:
Theorem 3.3, Let us consider Algorithu using stochastic gradients V instead of exact gradients St for all i E [n). Let Assumptions 2, 2.2, 2.3 and 3.2 hold, 3 w+I: 20 w. and
S

---

Under review as a conference paper at ICLR 2023
min
7
Vnec
αx 100L
Then Algorithm 1 returns x² such that
1max
20V@L
(w+1)
F. || - 11² + + [F())) - [(xx)] s ) V 24( 1)o²
24
pm
where 0 == 24
E ||-00 x 13] + (f(z9) - f((²)) + 8TW(Wt1)
Di=1 11g vf(("*)]]*
n
For general convex case, refer Theorem F.4. Note that Theorem 3.3 has the same convergence rate as Theorem 3.1, except for the statistical term O (wo+1)="/un) that is the same as in DIANA (Gorbunov al., 2020a; Khaled et al., 2020) and does not depend
3.2 EF21-P DCGD AND INTERPOLATION REGIME
We also analyze second method, EF21-P DCGD, which is based on DCGD (Khaled & Richtárik, 2020; Alistarh et al., 2017). One can think of DCGD as DIANA with parameter / 0. On one hand, the convergence of EF21-P DCGD is faster (see Theorem G.3) comparing to EF21- P + DIANA (see Theorem 3.1). On the other hand, we can guarantee the convergence only to a 0(%) >i= [ "neighborhood" of the solution. However, this "neighborhood" disap- pears in the interpolation regime, i.e., when V.f((=)) for all E [n]. The interpolation regime is very common in modern deep learning tasks (Brown et al., 2020; Bubeck & Sellke, 2021).
3.3 WHY DO BIDIRECTIONAL METHODS WORK MUCH BETTER THAN GD?
Our analysis of EF21-P + DIANA covers the worst case scenario for the values of Lymax and a. Although Lmax be equal to nL, in practice it tends to be much smaller. Similarly, the assumed bound on the parameter a equal to */d for the TopK compressor is also very conservative and the "effeettve" a is much larger (Beznosikov et al., 2020; Vogels et al., 2019; Xu et al., 2021). Note that Algorithm does not depend on ad Our claims are also supported by experiments from Section 5.
4 ANALYSIS IN THE NONCONVEX SETTING
In the nonconvex case, existing bidirectional methods suffer from the same problem as those used in the convex case (see Section 2.3): they either do not provide -orversso-workers compression at all, or the compressor errors/noises are coupled in a multiplicative fashion (see ww and wi in Table 2).
Instead of the convexity (see Assumption 2.3), we will need the following assumption:
Assumption 4.1 (Lower boundedness). There exist fo E IR and fi ....... E R such that f(x) 2 f and f(( 2 f for all x E Rd and for all i E [n]].
As in the convex setting, the theory of methods that only use workers-to-serve compression is well examined. In the high accuracy regimes, the current state-of-the-art methods are MARINA and DASHA (Gorbunov et al., 2021; Tyurin & Richtárik, 2022b); both return an E-stationary point after O (AOL AnwL) Vne
iterations, where Ao f(x") f In the low accuracy regimes, the
current state-of-the of-e--of-he-eee oof-the-art art method is DCGD (Khaled & Richtárik, 2020), with an iteration complexity where A := f - Σm fr. Note that DCGD has worse dependence on E, but scales much better with the number of workers
AaL AolAs "1)11"
We now investigate how EF21-P can help us in the general nonconvex case. Let us recall that in the convex case, decoupling of the noises coming from compression schemes can be achieved by combining EF21-P with DIANA. In the nonconvex setting, we successfully combine EF21-P and DCGD. Moreover, we provide analysis of some particular cases where EF21-P + DCGD can be the method of choice in the high accuracy regimes.
Whether or not it is possible achieve the decoupling by combining our method with MARINA or DASHA is not yet known and we leave it to future work".
We did not to get the convergence rate of EF21-P DIANA in the nonconvex regime because it is well known that DIANA suboptimal method in the nonconvex case (Gorbunov et al., 2021).
7

---

Under review as a conference paper at ICLR 2023
Table 2: General nonconvex Case. The # of communication rounds to get an e-stationary point (Ell f S E). For simplicity, we assume that fü f for all i [n] and only the terms with respect to and ws are shown. The parameters w/ and have the same meaning as in Table 1.
Communication
Limitations
Aowe & ned
DCGD (Khaled Richtárik, 2020)
server-to compression.
MARINA, DASHA
(Gorbunoy et al., 2021)
Aguul vRlc
No server-to-worker compression.
(Tyurin & Richtárik, 2022b)
MCM (Philippenko & Dieuleveur, 2021)
Ap
3/2
1/2
Lmnx
Only bomogenenus case. ft for all E [x).
CD CD-Adam (Wang al., 2022)
f
V mazi (ueeww)) 6
Bounded gradient assumption.
EF21 (Fatkhullin et al., 2021)
Agwnwrr
NEOLITHIC (Huang 2022)
Ag funax
Does not compress vectors! Bounded gradient assuraption.
EF21-P DCGD (new)
uny I. Lomax
AguaL
EF21-P DCGD (new)
Dagl
Strong-growth assumption with parameter D.
6 each sommunication round, NEOLITHIC sends the number of compressed vectors proportional where parameter of biased compressor, For Top or RandK, it means that NEOLITHIC sends @(4/x) sparsilied vectors with K nonzero elements, meaning in lotal, (dd values are in communication
4.1 EF21-P + DCGD IN THE GENERAL NONCONVEX CASE
Without any restrictive assumptions, we can prove the following convergence result:
Theorem 4.2. Consider Algorithm 2 and let Assumptions 2. 2.2 and 4.1 hold, x00 = wo, and 7 min
VT.
ne
}
Then
T 324" SL ViwLbaax
T 18A,L max
8 Lman 32A" Lmax
min DSAST-L
E
[ SE.
(The follows from Theorem E.3 and Proposition E.4 (Part 1)).
We get the rate of DCGD (Khaled & Richtárik, 2020) plus an additional O ( taining the first method with bidirectional compression where the noises from og factor, thus ob- decoupled. Moreover, as noted before, this method provides the sate-off-the-ae rates when e is small or the number of workers n is large.
(اام)
compressors are
4.2 STRONG GROWTH CONDITION
Here analyze EF21-P DCGD under the strong strong-growth condition (Schmidt & Roux, 2013).
Assumption 4.3. There exists D 0 such that 1 E > [[))() for all x Rdd
While this assumption is restrictive and does not even hold for quadratic optimization problems, there exist numerous practical applications when it is reasonable. These include, for example, deep learning, where the number of parameters is so huge that the model can interpolate the training dataset (Schmidt & Roux, 2013; Vaswani et al., 2019; Meng et al., 2020). To train such models, en- gineers use distributed environments, which case communication becomes the main a bottleneck (Ramesh et al., 2021). For these problems, method is suitable and can be successfully applied. Theorem 4.4. Consider Algorithm 2, let Assumptions 2.1, 2.2, 4.1 and 4.3 hold, and choose x. n and 7 min { S7. 4DDL. Then
T 484.L max
18 1D
min E [[IVF(='))] Se.
0S1ST-1
(The proof from Theorem E.3 and Proposition E.4 (Part 2)).
Comparing to Section 4.1, the above result shows an improved dependence on E under the strong growth assumption.
8

---

Under review as a conference paper at ICLR 2023
1T21-7 SCGD: 35.0
1122 DCED: stwe: 16.0
1721-7 3AM,
2221-7 DIAMA Stpp
1011
1011
#bits /n tworkers-to-server
le7
Witts /n (server-to-worker
Figure I: Logistic Regression with real-sim dataset. Number of workers n 100. Sparsification level was set to K 100 for all compressors.
4.3 HOMOGENEOUS FUNCTIONS
Another important problem where our method can be useful is distributed optimization with ho- mogeneous (identical) functions and stochastic gradients. particular, we consider the case when fi = f for all [n] and instead of exact gradients, stochastic gradients are used. This assump- tion holds, for instance, for distributed machine learning problems where every worker samples mini-batches from large shared dataset (Recht et al., 201 I; Goyal et al., 2017).
Theorem 4.5. Let us consider Algorithm with the stochastic gradients V instead of the exact gradients V. Suppose that Assumptions 2.1, 2.2, 3.2 and 4.1 hold and f: for all i E [n]. Set x = w and let 7 -min
a SL
(
16(
me
Then
T> 48DoL max
{ {a (H +1),
16(w+1)0 ne
min E
[V(())) sc.
OStST-1
(The follows from Theorem E.3 and Proposition E.4 (Part 4)).
Under exactly the same assumptions, MCM method by (Philippenko & Diculeveut, 2020) with bidirectional compression guarantees the convergence rate + AoL max { + +1) ,wss 3/2 w/r!/ (wu+1)o })- Comparing this with our result, the last statistical term (c++1)=²/ns ns is the same in both cases, but we significantly improve the other communication terms (take w ww and a = (w, + 1)-1
1 in Theorem 4.5).
EXPERIMENTAL HIGHLIGHTS
We now provide a few highlights from our experiments. For more details and experiments, we refer to Section A, where we compare our algorithms with the previous state-of-the-ar method MCM and solve a nonconvex task. We consider the logistic regression task with real-sim (# of features 20,958, # of samples equals 72,309) from LIBSVM dataset (Chang & Lin, 2011). Each plot represents the relations between function values and the total number of coordinates transmitted from and the server. In all algorithms, the RandK compressor is used to compress information from the workers to the server. In the case of EF21-P + DIANA and EF21-P + DCGD, we take TopK compressor compress from the server the workers. The results are presented in Figure 1. The main conclusion from these experiments is that EF21-P DIANA and EF21-P DCGD converge to solution not slower than DIANA, even though DIANA does not compress vectors sent from the server to the workers! This means that EF21-P DIANA and EF21-P + DCGD can send x400 less values from the server to the workers for free! Moreover, we see that EF21-P + DCGD converges faster than its competitors.
REFERENCES
Dan Alistarh, Demjan Grubic, Jerry Li. Ryota Tomioka, and Milan Vojnovie. QSGD: Communication-effcccett SGD via gradient quantization and encoding. In Advances in Neural Information Processing Systems (NIPS), pp. 1709-1720, 2017.

---

Under review as a conference paper at ICLR 2023
Aleksandr Beznosikov, Samuel Horváth, Peter Richtárik, and Mher Safaryan. On biased compres- sion for distributed learning. arXiv preprint arXiv:2002.12410, 2020..
Tom B Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. arXiv preprint arXiv:2005. 14165, 2020.
Sébastien Bubeck and Mark Sellke. A universal law of robustness via isoperimetry. arXiv preprint arXiv:2105. 12806, 2021.
Chih-Chung Chang and Chih-Jen Lin. LIBSVM: a library for support vector machines. ACM Transactions on Intelligent Systems and Technology (TIST), 2(3): 2011.
Laurent Condat, Kai Yi, and Peter Richtárik. EF-BV: A unified theory of eπror feedback and variance reduction mechanisms for biased and unbiased compression in distributed optimization. arXiv preprint arXiv:2205.0411m 2022.
John C Duchi, Peter L Bartlett, and Martin J Wainwright. Randomized smoothing for stochastic optimization. SIAM Journal on Optimization, 22(2):674-701, 2012.
Ilyas Fatkhullin, Igor Sokolov, Eduard Gorbunov, Zhize Li, and Peter Richtárik. EF21 with bells & whistles: Practical algorithmic extensions of modern error feedback. arXiv preprint arXiv:2/ 10.03244, 2021.
Eduard Gorbunov, Filip Hanzely, and Peter Richtárik. A unified theory of SGD: Variance reduc- tion, sampling, quantization and coordinate descent. In International Conference on Artificial Intelligence and Statistics, pp. 680-690. PMLR, 2020a.
Eduard Gorbunov, Dmitry Kovalev, Dmitry Makarenko, and Peter Richtárik. Linearly converging error compensated SGD. In 34th Conference on Neural Information Processing Systems (NeurIPS 2020), 2020b.
Eduard Gorbunov, Konstantin Burlachenko, Zhize Li, and Peter Richtárik. MARINA: Faster non- convex distributed learning with compression. In 38th International Conference on Machine Learning. 2021.
Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, An- drew Tulloch, Yangqing Jia, and Kaiming He. Accurate, large minibatch SGD: Training imagenet in hour. arXiv preprint urXiv:/706.02600 2017.
Samuel Horváth, Chen-Yu Yu Ho, Ludovít Horváth, Atal Narayan Sahu, Marco Canini, and Peter Richtárik. Natural compression for distributed deep learning. arXiv preprint 2019.
Samuel Horváth, Dmitry Kovalev, Konstantin Mishchenko, Sebastian Stich, and Peter Richtárik. Stochastic distributed learning with gradient quantization and variance reduction. Optimization Methods and Softwrre, 2022.
Xinmeng Huang, Yiming Chen, Wotao Yin, and Kun Yuan. Lower bounds and nearly op- timal algorithms distributed learning with communication compression. arXiv preprint arXiv:2206.. 20n.226666.3665... 2022.
Peter Kairouz, Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Ad- vances and open problems in federated learning. Foundations and Trends@ in Machine Learning, 14(1-2):1-210, 2021.
Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian Stich, and Martin Jaggi. Error feedback fixes SignSGD and other gradient compression schemes. In 36th International Conference on Machine Learning (ICML), 2019.
Ahmed Khaled and Peter Richtárik. Better theory for SGD in the nonconvex world. arXiv preprint 232332000..03329, 2020.
10

---

Under review as a conference paper at ICLR 2023
Ahmed Khaled, Othmane Sebbouh, Nicolas Loizou, Robert M Gower, and Peter Richtárik. Unified analysis of stochastic gradient methods for composite convex and smooth optimization. arXiv preprint 7xXi::2006.1157. 2020.
Sarit Khirirat, Hamid Reza Feyzmahdavian, and Mikael Johansson. Distributed learning with com- pressed gradients. arXiv preprint arXiv:/806.0653 2018.
Anastasia Koloskova, Sebastian U Stich, and Martin Jaggi. Sharper convergence guarantees for asynchronous SGD for distributed and federated learning. arXiv preprint #rXiv:2206.08077 2022.
Jakub Konečný, H Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. arXiv preprint arXiv:1610.05492 2016.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. Technical report, University of Toronto, Toronto, 2009.
Zhize Li and Peter Richtárik. CANITA: Faster rates for distributed convex optimization with com- munication compression. Advances in Neural Information Processing Systems, 34: 13770-117777 2021.
Zhize Li, Dmitry Kovalev, Xun Qian, and Peter Richtárik. Acceleration for compressed gradi- ent descent in distributed and federated optimization. In International Conference on Machine Learning, 2020.
Xiaorui Liu, Yao Li, Jiliang Tang, and Ming Yan. A double residual compression algorithm for efficient distributed learning. In International Conference on Artificial Intelligence and Statistics, pp. 133-143. PMLR, 2020.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. learning of deep networks from decentralized data. In Artificial intelli- gence and statistics, pp. 1273-1282. PMLR, 2017.
Communication-efien
Si Yi Meng, Sharan Vaswani, Issam Hadj Laradji, Mark Schmidt, and Simon Lacoste-Julien. Fast and furious convergence: Stochastic second order methods under interpolation. In The 23rd International Conference Artificial Intelligence and Statistics, pp. 1375-1386. PMLR, 2020.
Konstantin Mishchenko, Eduard Gorbunov, Martin Takáč, and Peter Richtárik. Distributed learning with compressed gradient differences. arXiv preprint arXiv:1901.09260 2019.
Tomoya Murata and Taiji Suzuki. Bias-variance reduced local SGD for less heterogeneous federated learning. arXiv preprint 102.v:2102.03/99 2021.
Yurii Nesterov. Introductory lectures on convex optimization; A basic course, volume 87, Springer Science & Business Media, 2003.
Yurii Nesterov. Lectures on convex optimization, volume 137. Springer, 2018.
Antonio Orvieto, Hans Kersting, Frank Proske, Francis Bach, and Aurelien Lucchi. Anticorrelated noise injection for improved generalization. arXiv preprint arXiv:2202.02833 2022.
Constantin Philippenko and Aymeric Dieuleveut. Artemis: tight convergence guarantees for bidi- rectional compression in federated learning. arXiv preprint arXiv: 14591, 2020.
Constantin Philippenko and Aymeric Dieuleveut. Preserved central model for faster bidirectional compression distributed settings. Advances in Neural Information Processing Systems, 34: 2387-2399, 2021.
Swaroop Ramaswamy, Rajiv Mathews, Kanishka Rao, and Françoise Beaufays. Federated learning for emoji prediction a mobile keyboard. arXiv preprint 1xXiv:1906.04322 2019.
Aditya Ramesh, Mikhail Pavlov, Gabriel Goh, Scott Gray, Chelsea Voss, Alee Radford, Mark Chen, and Ilya Sutskever. Zero-shot text-to-image generation. arXiv preprint a02.v:2 /2092, 2021.
11

---

Under review as a conference paper at ICLR 2023
Benjamin Recht, Christopher Re, Stephen Wright, and Feng Niu. Hogwild!: A lock-free approach to parallelizing stochastic gradient descent. Advances Neural Information Processing Systems, 24, 2011.
Peter Richtárik, Igor Sokolov, and Ilyas Fatkhullin. EF21: A new, simpler, theoretically better, and practically faster error feedback. arXiv preprini 1..Xix::106.05200000 2021.
Peter Richtárik, Igor Sokolov, Ilyas Fatkhullin, Elnur Gasanov, Zhize Li, and Eduard Gorbunov. distributed training and better theory
3PC: Three point compressors for communication-effieeeecc distibrii for lazy aggregation. PMLR, 2022.
Mher Safaryan, Rustem Islamov, Xun Qian, and Peter Richtárik. Fednl: Making newton-type meth- ods applicable to federated learning. arXiv preprint arXiv:2106.0296) 2021.
Mark Schmidt and Nicolas Le Roux. Fast convergence of stochastic gradient descent under a strong growth condition. arXiv preprint 1008. 2013.
Sebastian Stich and Sai Praneeth Karimireddy, The error-feedback framework: Better rates for SGD with delayed gradients and compressed communication. arXiv preprint arXiv: arXiv::909.000 1909.0535,, 2019.
Rafat Szlendak, Alexander Tyurin, and Peter Richtárik. Permutation compressors for provably faster distributed nonconvex optimization. arXiv preprint arXiv:2110.03300, 2021.
Hanlin Tang, Chen Yu, Xiangru Lian, Tong Zhang, and Ji Liu. Doublesquezze: Parallel stochastic gradient descent with double-pass error-compensated compression. In International Conference on Machine Learning, pp. 6155-6165. PMLR, 2019.
Alexander Tyurin and Peter Richtárik. A computation and communication efficient method for dis- tributed nonconvex problems the partial participation setting. arXiv preprint arXiv:2205.1552 2022a.
Alexander Tyurin and Peter Richtárik. DASHA: Distributed nonconvex optimization with commu- nication compression, optimal oracle complexity, and no client synchronization. arXiv preprint arXiv:2202.01268, 2022b.
Harsh Vardhan and Sebastian U. Stich. Tackling benign nonconvexity with smoothing and stochastic gradients, 2022.
Sharan Vaswani, Francis Bach, and Mark Schmidt. Fast and faster convergence of SGD for over- parameterized models and an accelerated perceptron. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 1195-1204. PMLR, 2019.
Thijs Vogels, Sai Praneeth Karimireddy, and Martin Jaggi. PowerSGD: Practical low-rank gradient compression for distributed optimization. In Neural Information Processing Systems, 2019.
Yujia Wang, Lu Lin, and Jinghui Chen. distributed nonconvex optimization. In International Conference on Artificial Intelligence and Statistics, pp.
cetpuniccatio-compesssss adaptive gradient method for
PMLR, 2022.
Hang Xu, Kelly Kostopoulou, Aritra Dutta, Xin Li, Alexandros Ntoulas, and Panos Kalnis. Deepre- duce: A sparse-tensor communication framework for federated deep learning. Advances in Neural Information Processing Systems, 34:21150-2111 2021.
Haoyu Zhao, Konstantin Burlachenko, Zhize Li, and Peter Richtárik. Faster rates for compressed federated learning with client-variance reduction. arXiv preprint 11X1v:2112.13097, 2021.
12

---

Under review as a conference paper at ICLR 2023
CONTENTS
Introduction: Error Feedback in the Primal Space
1.1
EF21-P theory
1.2
Summary of contributions
2
Distributed Optimization and Bidirectional Compression
2.1
Communication complexity of vanilla gradient descent
2.2
Workers-to-server (=uplink) compression
2.3
Bidirectional compression
2.4
New methods
3
Analysis in the Convex Setting
3.1
Stochastic gradients
3.2 EF21-P + DCGD and interpolation regime
3.3
Why do bidirectional methods work much better than GD?
4
Analysis in the Nonconvex Setting
4.1
EF21-P + DCGD the general nonconvex case
4.2
Strong growth condition
8
4.3
Homogeneous functions
5
Experimental Highlights
A Further Experiments
14
Useful Identities and Inequalities
16
C Proof of Lemma 2.4
17
D Convergence of EF21-P in the Strongly Convex Regime
18
Convergence of EF21-P in the Smooth Nonconvex Regime
20
E.1 General convergence theory
20
E.2 Proof of the convergence result
E.3 Proof of Proposition E.4
25
Proofs for EF21-P + DIANA in the Convex Case
27
F1
Communication Complexities in the General Convex Case
34
F.2 Proofs for EF21-P + DIANA with Stochastic Gradients
35
Proofs for EF21-P DCGD in the Convex Case
41
H Future Work and Possible Extensions
46
13

---

Under review as a conference paper at ICLR 2023
A FURTHER EXPERIMENTS
We now provide the results of our experiments on practical machine learning tasks with LIBSVM datasets (Chang & Lin, 2011) (under the 3-clause BSD license). Each plot represents the relations between function values and the total number of coordinates transmitted from and to the server. The parameters of the algorithms are suggested by the theory, except for the stepsizes y that finetune from set {2' [-10, 10
We solve the logistic regression problem:
exp (aT Σ y=1 exp (a.)ar)
[(1 ..) =
log
where 21,..., Te E Rd is the number of unique labels, o. E R is a feature of sample on the 2t worker, Viy is a corresponding label and m is the number of samples located on the jth worker. In all algorithms, the Rand compressor is used to compress information from the workers to the server. In the case EF21-P + DIANA and EF21-P + DCGD, we take TopK compressor to compress from the server to the workers. The performance of algorithms is compared on w&a (# of features 300, # of samples equals 49, 49,749) 749), 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.
The results are presented in Figures 1, 2 and 3. The conclusions are the same as in Section 5. One can see that EF21-P + DIANA and EF21-P + DCGD converge to a solution not slower than DIANA, even though DIANA does not compress vectors sent from the server to the workers! EF21-P + DIANA and EF21-P + DCGD send x100 x1000 less values from the server to the workers!
10
SF21 DCGD Srag 16.0
EF2) SAMA SIIS COR
-0-
5721 BANA Stop dis &.
66x11-
6x
#bits/ (Warkers to server]
106
#bitsin worreett
Figure 2: Logistic Regression with w8a dataset. # of workers n 10. K = 10 in all compressors.
2444
2 10
21222 D72L-P CUNK: V.o. E3325
ANA 003125
2x:22
12x
1.4x
#bits/ (workers server)
33
10
10
(servento
13
Figure 3: Logistic Regression with CIFARIO dataset. of workers 10. K 1000 in all compressors.
We also compare our algorithm to MCM. Since MCM does not support contractive compressors defined in 2, we use RandK instead of the TopK compressor in the server-to-workers compression. Figure 4 shows that our new algorithms converge faster.
Finally, we provide experiments for the nonconvex setting and compare EF21-P + DCGD against EF21-BC (Fatkhullin et al., 2021) and DASHA (Tyurin & Richtárik, 2022b). We consider the logistic regression with nonconvex regularizer
r(z Ie)
14

---

Under review as a conference paper at ICLR 2023
C'aLe POGD: SNE 8
ErRLP PCCe: 2.3 DANA
10-1
(perventoowwriens
Figure 4: Logistic Regression with real-sim dataset. of workers 100. The parameters of workers-to server and server-to- torkkess-workers compressors are Kw = 100 and K, 2000.
where Fl is an indexing operation of a vector and À 0.001. We use RandK and TopK com- pressors for the workers-to-server and server-to-workers compressions, respectively. Note that in these experiments, the server-to-workers compression is only supported by EF21-P + DCGD and EF21-BC. In Figure 5, one that EF21-P DCGD converges faster than other algorithms and outperforms DASHA, which does not compress vectors when transmitting them from the server to the workers.
DANIL Sho <be
Ne.iid EF21 BC Stop ebe. 0.5 BOAD sne dae.
(F21 ic Ste 4th 6.5
Dc.5 Step 2.6
3:
30.00
#btt /n (Warkers to-server]
167
Poks (servanto (orkwrs))s)
Figure 5: Logistic Regression with the nonconvex regularizer and real-sim dataset. of workers 100. K 100 in all compressors.
15

---

Under review as a conference paper at ICLR 2023
B USEFUL IDENTITIES AND INEQUALITIES
For all x, U; ....,,,......................... E RR, 8 > 0 and a E (0, 1]. we have:
| vll (1 8) |== + (1 + s + llll?
| + y11 s 2 || 2 + 1 2
(8)
|
8 +|yl1
(x.1)
2s
(1 a)
(10)
2
2
(1 a)
1+ $ -
(11)
a
(a,
[|a|l + |1b|| - ||a [ll²)
(12)
Tower property: For any random variables X and Y, we have
E E Y] = E [X]
(13)
Variance decomposition: For any random vector X Ie and any non-random Rd,, we have
E ||X -IIx- - =11 E || [1 + [|B[
E[X]1]
cl
(14)
Lemma B.1 (Nesterov (2018)). Let f : Rd - R be a function for which Assumptions 2./ and 2.3 satisfied. Then for all x, y Rdd we have:
-
& 2L(f(z) - f(v) - (V 4)).
(15)
Lemma B.2 (Khaled & Richtárik (2020)). Let S be a function for which Assumptions 2.1 and 4.1 are satisfied. Then for all x, y E Fd we have:
ff())] s 2L(((x) f)))
(16)
16

---

Under review as a conference paper at ICLR 2023
C PROOF OF LEMMA 2.4
Lemma 2.4. If Assumptions 2.1, 2.2 and 2.3 hold, then I. & Timax S nL and I. L. L.S S VnL.
Proof. One can show (see (Nesterov, 2003)) that a convex function I is L-smooth if and only either of the two conditions below holds:
0 S (Vf(x) - (D00--/(())... V
- D) S -|r-- -ll", Vx,yE R. [V/(=) < L(V](>) Vf(x), 9), V Rd.
For any fixed i E [n). we have
(Vf(()) Vf(()), - v) $ Σ
- Vf(U), y)
i=1
(V(((a) Vf((),, v)
n
n (Vf(z) Vf(y), x v)
< n f(x)) - V f( vl
en 7n -11
Thus L, S nL and Lmax S nL. Next,
Vf((z)
<
Li (V/(x)) V((()xx--) v\
t=1
S Lmma
(V((()) V)(()) x v)
1=1
Lmax (Vf(x) Vf(v), x - 3)
Lmax
Vf(x) V of(iil | vll
(21)
Lmxx L | y11
I nL2 | - y|1
and hence i S VnL. Using Jensen's 's inequality, have
[Vf(()) - VV(()) 2 || - -y1??
Thus L <. L. Finally, I Lmax follows from
n
[f(() -
Σ
I ||
v11 2 1| y
7
n
17

---

Under review as a conference paper at ICLR 2023
D CONVERGENCE OF EF21-P IN THE STRONGLY CONVEX REGIME
We now provide the convergence rate of EF21-P from Section 1 in the strongly convex case.
Theorem D.1. Let Assumptions 2.1 and 2.3 hold, set wD x and choose Y S a
Then EF21-P
10L
returns x² such that
E || x01 +E[[(=") - f(x²)] $ 74 T 1 1000 x012] + (f(29) 24
2)
27
Moreover, F. [lw0- - x²1 x²1]"]] - as 1 xo. 00.
Theorem D.1 states that EF21-P will return an e-solution after O (d log log1/s steps. Comparing to 1oe
GD's rate O (+ log B/e)
one can see that EF21-P converges 1/a times slower.
Proof. First, let us note that
|| x² 2=1
| 1e+11 - x² 1=11²= | - x012
(2² - x 1+1 x² - -2x" + x xt11) - (2 - x², x
t+1 x4))
2 (x' xt11 x x²)
2y f x 11 x²)) )
(17)
Using L-smoothness of f (Assumption 2.1), we obtain
1(x s s(u²) + (Vf(w'), x=+1 - =0²) )-
| - r0'12
2
conv-ty I f(x*) + (Vf(w') ), xt+11 - -x*)
/
| - x=1
+ L
|1 w²|
2
(1)
f(x')
1
|0' x x=1
1
|| x²1
1
|| 1--1-211
22' 11
27
24
|w' xx" 1
++
w01
2
2
Using (8), we have
-
||, - w0'l s T.11 1- - ==112+1,0
+ I.
I/ - 2²112
2
and
|=' x²
11
Iw' x² 1|2
11
I|w' - 201
1
1w' - x= 112 L 1|' =11?
4
2
2
2
where we used the fact that S L. Hence
5(xlt1) S f(x*) +
x=
$12
||
11
- xz"
x011²-
|| - xz 11
27
24
24
11
Ilu't x² x²1
L
||,0-11
+
2
2
fz(²") +
1
1|00 - -x*11
1
1|
xx11
1
|| | 1+1 - =211
27
2n
+ L 11|2²* - 2=112
/
|| - 1=1
-x-11²
+ L
|| - x² 2011
+ L || |u=" - 201?
4
=f(x*) + 2n
(1
7/14
10" x² ||2- 1
1 x01
2
27
1
1) ||0
- 101 2L
|w' - x11
27
$ <s(x") + 27
(1
7/K
1|00 xz
11
1
|
x=
11 + 2L I|w 22112
2
2y
18

---

Under review as a conference paper at ICLR 2023
where the last inequality follows from the fact that y S 2T.
Let us denote by Es41 [-] the expectation
conditioned on previous iterations {O..... tJ. Then
E411 [f(x f(x))
27 (1 (1- 214 || x²1²
2
Es+1 |||0-1 -200--011 x=113]] + 21 22/1|u²² x²12
(18)
2y
|| z0+1 |2]
remains to bound E
Es+1
|||o*t! 221111
Ex+1
||w0" + CC - w') - x²+1 11a]
11 WV
(1 E || w0(l3]
(1 a) 1 vf(w") w²1l
IV9
[1 ||00 z²112 + 2-2
vf(w")/1
| x² 211 4
(1 2
[V(wm') -
+ 47
[V {)(x))11
(.D.....))
a
4221,3
| |Iu'-x"" xx'1? + 8 (s(x²) s(x)))
_ +
2
|| o'1 8721. (f(x')
1
0)
- f(x'))
4
where the last step we assume that (18), obtain
I a
Adding a 161, multiple of the above inequality to
E [[(x+t)]] +
16L
Ex+1
|1 - -1/ - f(x")
1 +
(1
7/41
| - x112
2
2
27 Ex+1
[11-41
x²
[1"]
16L (1
a
| - x'
+
128
(f(x²) - f(x)))
a²
Thus, taking full expectation over both sides of the inequality and considering ? S 161. S a 4y
gives
E f(x))] +
1 E [||a x² ==11]]
16T. E
||
27
$ (1 7H)
E [f(x*) f(x')] + 2n
I1a' x² 2²1]]] + 16L E |||u - 1131
Applying this inequality iteratively and using the assumption w = x proves the result.
19

---

Under review as a conference paper at ICLR 2023
E CONVERGENCE OF EF21-P IN THE SMOOTH NONCONVEX REGIME
E GENERAL CONVERGENCE THEORY
We now move on study how the EF21-P method can be used in the nonconvex regime. The analysis relies on the expected smoothness assumption introduced by Khaled & Richtárik (2020). In their work, they study SGD methods, performing iterations of the form
x. x' - 779',
where g6 is unbiased estimator of the true gradient ff(²²) Following Khaled & Richtárik (2020), we shall assume that E [g[[)]] = f(x). However, in our case, gradients will be evaluated at perturbed points, thus resulting in biased stochastic gradient estimators. In particular, we consider the following general update rule, where the stochastic gradients are calculated at points evolving according to the EF21-P mechanism, rather than at the current iterate:
x++1 = x² "g("") w ++1 = w² + (att1
(19)
Our result covers wide range of sources of stochasticity that may be present in g. For detailed discussion of the topic, refer the reader to the original paper (Khaled & Richtárik, 2020).
Throughout this section, we will rely on the following assumptions:
Assumption E.1. The stochastic gradient g(x) is an unbiased estimator of the true gradient ffr,,
i.c.
[g())] (x)
for all x Rd. Assumption E.2 (From Khaled & Richtárik (2020)). There exist constants A, B,C 2 0 such that:
[19())) < 2A(f(=) f") +
for all x E Rdd
We are ready to state the main theorem:
Theorem E.3. Let Assumptions 2.1, 4.1, E.1 and E.2 hold and w x0. Fix >> O and choose the stepsize
7 = min {
1
1
8T. ABT'
V2ALT' 16CT.
Then
48 max
8 4B,
96A.A 16C
T
min E 0S
Se.
(20)
Note that by taking A = C = 0 and B = 1, one recovers the convergence of EF21-P in the
nonconvex setting, Namely, under Assumptions 2.1 and 4.1, for d0 w and S 8T. we have
minogesr-1 [IVf(=))])
as soon as T 384A,L ace
We now apply the above result to the combination of EF21-P perturbation of the model and DCGD (Khaled & Richtárik, 2020) (EF21-P + DCGD). Suppose that the iterates follow the update (19) (see also Algorithm 2), where
g(x) = - Σ (a()))
(21)
and each stochastic gradient (z) is an unbiased estimator of the true gradient f.( (i.e., E. [2)(())) = (f(())).
Proposition E.4. Suppose that the gradient estimator g(x) is constructed via (21) and that Assump- tion 2.2 holds. Let A" == E S(). Then:
20

---

Under review as a conference paper at ICLR 2023
1. For 9,(2) f(()), Assumption E.2 is satisfied with A Lw B and C 2AA
2. In the same setting as in part 1, assuming additionally that Assumption 4.3 holds, Assump- tion E.2 is satisfied with A C 0 and B
D2 + 1.
3. Assume that each
stochastic gradient 9: has bounded variance, (i.e.
E (l)(()) {=((=))l S 0²). Then Assumption E.2 is satisfied with A AWLmax
B and C 2AA
4. Suppose that E [11x((x)) {((=)) S 0² and Si I for all i E [n]. Then Assumption
E.2 is satisfied with A 0. B _ + 1 and C w+1 o². a
In Section 4, we apply Proposition E.4 and state the corresponding theorems.
E.2 PROOF OF THE CONVERGENCE RESULT
We will need the following two lemmas:
Lemma E.5, Consider sequences (8'),, (r*)e and (s*), such that 8', r' 2 0 for all 2 and
8 0. Suppose that
g (+1 S bōt + as' cr + d.
(22)
where a, b, G, are non-negative constants and b 2 1.
Then for any T 2
br
d
min 0S1ST-1 cT
50
Proof. The proof follows similar steps as the proof of Lemma of Khaled Richtárik (2020) and provide it for completeness. Let us fix w-1 > O and define w, Wh-1 Multiplying (22) by wy gives
w +1 at +1 S bwy awyss cwer dw,
I 11-18' + aw;-1s' ewit" + dwr.
Summing both sides of the inequality for O,..., 1, we obtain
T-1
T-1
WT WT-18" +awr-11 S 1= + aa 11 - Σ
wor + d
Σ
Wt.
t=
t=0
Rearranging and using the assumption that S = 0 and neg-niiativity of s' gives
wor" + 1T < 1 + aw
awT- +
Wt
1=
t=0
S w 1 80 + d
Wt.
Next, using the non-negativity of 5 and wi, we have
T-1
T-1 < Σ wor + WT-18" S w +
T-1
Σ
wor'
Wr.
t=
t=0
1=0
Letting WT == ET- We and dividing both sides of the inequality by Wr. we obtain
min pd
wor <
W- Wr
8 d.
0S1ST-1
WI t=ul
21

---

Under review as a conference paper at ICLR 2023
Using the fact that
T-1
T
Tw
Wr
Wy
min
W. = Twr-1 63
0StST-1
1=
we can finish the proof.
Lemma E.6. Let Assumptions 2.1, 4.1, E.I and E.2 hold, set w = x² and choose
1
Q
S min
4A 4BL
8L
Then
8 81 + 2
min E [ 0S1ST-1
<
Do + 8CL,.
(23)
7T
Proof. First, L-smoothness of f implies that
f(w') - f(x') + (Vf(x', w² - -z²) + T.
2 1| - x011
2 f(("') + 2L
1
v vf(x')) + L 1||u²= x011
(24)
and
L
S f(x²) f(xtt1)
+ (V 1+1 - -2²) -
|| x011
2
L
= ~\(('))
+
2 11((
Using the fact that g(x) an unbiased estimator of the true gradient, subtracting I from both sides of the latter inequality and taking expectation given iterations {0..... we obtain
I^²
Es41 [f(*++)) 1*1
S f(x²) - f - (Vf((=) V(((")) +
Es+1 [|<(w())1
2
(22)
f(x") 5 - 2 -1I ||2
_ |
)1
+
|V vs(W')|
2
Tn²2 (2Al((w)) - (3) + B | (w 1|2 c))
+ 2
2)
S f(x') 8r -(15(0011- - 2IV((( + TT2
2 1|='-w'11
(fL*)( - +1²) BIn²
CT^²
vf(w>)) + 2
2
+ L3
1(x*) 8r - 1/4 (( (1 BLA) Vf )| ||1
|| - ww112
2
+AL')(f(w') ++) CL22
2
24)
2 f(x²) - 8r - -V11((²') (z)x )12 2 (1 - BLT) [f(ww()1 + 12g
|100 1
2
+AL?? (f(a') + 21
1 vf('')| ||( + 1 -0 - fr)
2- = + 2
CIA²
= (1+ Al72) (f(z") 5*)
--) -
2 (1 Av) \<(x))= - (1 Bln)
||//('')|
2
+L² + + || = + CL?²
1
2
Hence, taking full expectation, for 7 5 4 we have
1
E [f - f"1 s (1 AL f(xx)
-1-
7 [V
(25)
22

---

Under review as a conference paper at ICLR 2023
? (1 - BLy) E | [| + L2nyE [|1-t =010]]= + Ct2²
2
2
Next, variance decomposition and Assumption E.2 gives
E "oodd""">((((")" (44) E [ll((ee) [P] - || -|
(B.2)
I 2A(f(w") - ff) + (B (B-1) +C
(4)
I 2A [((²)) 1
2L
+(B-1) - ([B-1)][[/(w")) -
A
= 2A - T. | + 2AL 1|w0 - x²11
+(B - 1) [[==)\\v((']]] +
(26)
Therefore, using the unbiasedness of g(x), we can bound the expected distance between +1+ and
x² as
E |/w0t1 - 111
= E 10 + Cp - -w") - 11]
2 (1 a)E
|| |x - ww()
(1 a) E
|100 - ,gk - -w"ll 1²]
=
(4)
(1 - a) 2
|||9* vf(w(') [1
+ (1 11-aa a) E ||at F(((') - -oo =0011]]
MMC00D S
(1-a) E
|10* v)(ww)
1|
+ +11 2
( E ||aa w0'l(]]
2x E [|]f(w9))*)
a
(2) x
21 - a)>² (f(x²) - -r) + A - a² \
L
+2AL (1 a I|w6 - x11 2
+ +B - 11 - a)²² Vf(w'))'
+ (1
_
a
E
||0t ||'' w² w01 + 27² E || |'
2
Hence, taking expectation, for 7
8AT((1-o]
A(1 -a)
E w +1 - -11
22 - a)
+
E
| [4]
L
2
+ +7²
+ +B (B-1)(1 ()(1-0)) F [w]("())l" ||?
a
+ (1- + +2L (1 (1-o) E |100 - w/ [13)
C( 7
A a) > E ||V |=]
S 21 - a) 2 [s(x)) - -1] +
L
+9² 2 + (B- 1) (1) E || |19
+ (1 - 4) E
+ C1
(27)
Adding AL's
multiple of (27) to (25), we obtain
2
E [f(x+))- - f*1
E
w +1
2 ++
a
23

---

Under review as a conference paper at ICLR 2023
1 1 + ALy² + (1-2(1-0)))
E [[((x') -
a
7
16AL (1 10--01 a²
E ||V
4
BLy 8L272 2
+ (B - 1) (3(1-a)) -a))) E
( [|V
1
2
4L 7
CL
4CL -a
E || - 2²
2
a
Then, provided that
a
a
a V 32AL a)
S min
4BL 8L" V 32(B - 1) 1)62*
a
a
-min
(BLL' 8L V 32AL(1 a)
(where we used min(a, b) S ab for all a. E Rt), this gives
E [f((x(1) - [ +
41.2 E || |||
- x 11 ||] $ (1+2AL7)) E [f((t)
4L'7E ||w0 x' 11] CIA².
2 | 2
a
Denoting a== 4L'7 b= + 2AL c== 3 and = CL??, this equivalent to
8 ++ - 1ott + as' or + d.
(28)
where 8' = -*)
r² = E [IVS(=)1 and st
E |110" 211²]. Hence, using
Lemma E.5, for any T N
d
min
051ST-1
cT
which proves (23). In the proof, we have the following constraints on ry:
1
1
7 S min
4A
4BL
8L' 32AL(1 a a)
Using the inequality min(a, b} S Vab for all a, b E Rt, this can be simplified to
1
min
4A
4BL
SL
Theorem E.3. Let Assumptions 2.1, 4.1, E.1 and E.2 hold and set w 20, Fix 8 > 0 and choose the stepsize
7 = min
8L' 4BL
2ALT 16C J
Then
T
4 max
4B,
96A.A A
16C
min
[f(xx)]1 [f(a"))}{
Se. (20)
8
8
0S1ST-1
Proof. By Lemma E.6, we have
8 811 (1+22))7)
[|]
min 0stsT
<
Ao 8CLy
TT
24

---

Under review as a conference paper at ICLR 2023
provided that y I min { 4. 4BL } Now, using the fact that 1 + cx and the assumption y - V2ALT obtain
(1 (1+2AL72)* z exp (2ALT^²) s exp(1) <.
Hence
min 0S1ST-1
E [|V
24 - 7T
Ao + 8CL,
In order to obtain equivalent to
24 77 Ao + 8CIY S we require that both terms are no larger than 2. which is
484g
(29)
7
? 16CL
(30)
We thus require that:
7 min
4A 4BL' 8T, /2ALT 16CL
which, combined with (29) gives:
48 max 4A, 4A,4BL,
8L A6 16CL
T2
It remains to notice that the term 4A can be dropped, thus simplifying the constraints to
1 a 1
< min
4BT. ST,
V2ALT 16CT.
and
48Ao
8L 964gAL 16CL
T 2 max 4BL,
Indeed, if [> < then (20) holds for any y O. Let us now assume that f/ > e.
The above constraints imply that V2ALT I 96A.AE. Moreover, from Lemma B.2, we know that
8 |+ < 2T Thus V2ALT S 48A Similarly, we see that 96ApAL 484.
E.3
PROOF PROPOSITION E.4
Proof.
1. Using independence of CI...., Cn. we have
E ||({))11] = E
C.
(4) (C. (V)(())
E
+ +*]f(z)]|
+ |))()))
(B.2)
w
Σ
2L ft) + [+)
n i=1
25

---

Under review as a conference paper at ICLR 2023
2i Lmaa
n²
where A =
whmaz
2. Starting in part of the proof, we obtain
(43) 3 (Dw +1) [V
E [1(0))1|] S
3. First let us note that
E [[la(0)11]] - E [la((x) - v(( [VA())) [V)(())
Following steps similar to the proof of Proposition 4 of Khaled & Richtárik (2020), unbi- asedness of the stochastic gradients gives
|| (ia(e)..... (a(c)).....a.. In (x(
E
[[
(1)
E
E
n Σ
c, (arcos)
n
(14)
E
E
(C, (g((x)) - 2((2)) ():(x)))
19 (x). (z(
+
1
g
x
11
n
(14)
|Ic. (9:(x)) - (x))) (01(4)...., ]n(oo]
E
E
n
(g)(()) v((()) -/
+ +[[l/())1
+E
(g((z) V /7 + +[[lf(0)1
1
E
+E
n2
71
1=1
(IVA(())(* +
+
1
Σ
E
[laa(o) - VA(O))] + [V)(1))
n2
n
1=1
(B.2)
(2L, (f((z) - f() + 0²)
n +[{(())]
n2
2A
+C,
where A = TTaa and C == 2AA* - 02
4. Starting as in part and using the assumption fi f, we have:
Vf(x) /7
E [|
E
[1((())11 +E
9((x)) -o(()
+ +[(
(14) W
[10a((x)
- [ +|
n
1=1
F. [11)((r)) - v + +|V
+ n
w
+ 8 + +1) ||
26

---

Under review as a conference paper at ICLR 2023
F PROOFS FOR EF21-P DIANA IN THE CONVEX CASE
First, we prove an auxiliary theorem:
Theorem F.1. Lel us assume that Assumptions 2.1, 2.2 and 2.3 hold, 8 E
[0.
1
and
w+1
Vna
a B
S min
(31)
160w
20 / 100L 1
Then Algorithm 1 guarantees that
1
++
x²
+ [f(x - f(x))]
2yy
+
Kー
E
|1att1 Vsi((*)
|||] [|(
NB -1100t1-
10--11=-1111 121
-
i= 1
7/11
||a| - 011 + 2 [[(xx)) -f(x*))
Σ 27
2
7p
1
Σ E | vf(("")11 + +w(1= 7/
E || Ioo - 2² 2²1
+
(32)
where K S
Sye nB
and
192.y=
32L
na
Proof. From L-smoothness (Assumption 2.1) of the function f. we have
L
f(x+t1) 1 f(w²) + (Vf(w"), x - -
-w) ) +
|
1
w01
2
conv-ty
I f(x*)= + (Vf(w"), x +++ - x=+1-==")
-x*) - /
uu² - x²11 111 L || -
- w0l
2
2
f(x)) + (0', ++1 x²) + <Vi(ww) gt x1a x²)
1/4 | w¹ 1| bリ 1 - x² x¹1
We reprove well-known equality from the convex world. Noting that ++1 x² 796
obtain
||-- - x²112 - || - x²11" 1 -1111++111 - x011
-
(x" - 111 x²' - 2x" + +xtt1 (0 - -x", x0, - x²))
2 (x² - x 1111 x - -x")
27 (9), xtt1 x²))
(33)
Substituting (33) in the inequality gives
f(**+1) - f(x + ( (2((2")
g¹, x r+] x²))
|,- - x=1 =01
|| - x." 11?
|| ++ - x21
+
27
27
2
L
++ w² 112
1
|| - xz 20112
+
2
2
Next, by (8), we have
L
||
|
- w0l
- L
1| - x² 1 + L I1llu²= 2911
2
and
P |="
1²1
1 2
|| - =1=
w - 1/
P I xx11 L Illw² =11
4
2
2
27

---

Under review as a conference paper at ICLR 2023
where we used L 2/2 μs. Thus
[at S f(x' + (VS(wo)
g, x xx))
1
|x x²
1
| - xx" 11
1
1 ++ x² ||
+ 27
27
2n
+ L || 1- - 2¹1 _/ + I E110²² - =2'11
1
1|00
x² 11 + L 1|w0 - x21
4
= f(x") + (Vf(w²) g¹, +41 x²)
+ 27
1
(1
7/44
|| - x01 1|?
1
||_ - x²11 ( 1 -11)
|,. - x²112 + 2T |/ee* =011
2%
27
S {(x")) + (Vo( - -g¹, -g' xt11 - x²)
1
(1 - ||=" - -x" 11
+
27
1 ||_ - x² 211 + 2L 1|w0 - x=11
2y
where we used the fact that 5 2I.
1. Then, taking expectation conditioned on previous iterations
(0.... (0.....(), we obtain
Ex41 (((x(t)) S f(x") + Es+1 [(Vf(w") - -g¹, ,²,x²' +t1 - x²)]
27 (1 7p 2 ||a" |=aa-x" 2y
+2L 1 Eet1 [114411-2"10
==011² + 2L || |w* - x²11?
From the unbiasedness of the compressors CP,, we have
Es+1 [g"] = vf(w')
and
E [(V](w')) - - 1+1 x²)] Es+1 [( fl f(w'(()))))))))))) - gg' - - ->>}]
-7Ee+1 < (V](w") g' g')
7Fe+1 ||o013 > / (w")l ||
( EEtz [|o--1+(w>))1]
Therefore
E(41 [f(x
S fxx) + +Ee+11 [|00 - -Vf(w"))
+ 2y
1 (1
1|00 - x:" x011
E1+1
||
11] + 2T. 11 - =x/
2
2y
(34)
Now, we separately consider Es+1 [100* - v(("")1
From the independence of compressors, we
have
Ex+1
[110 - vV((()))
1 Σ cP CV((Vi((w) - -h0 - v)(we)
E44
h²
n iml
1
E [[CP(V - 12) (V m,)1l
n²
W
Vii(w*) - m!ll
2
1=1
<
2w
Σ
||n - v)((=-)11= + 2w
Vf((w") vf((21)12
n
n²
i=1
28

---

Under review as a conference paper at ICLR 2023
2w
4w
4w
h
VSi(w")
V Vfi("')]
n
where in the last three inequalities, we used (5) and (8). Next, using Assumption 2.2 and Lemma B.1, we obtain
Fx+1
|1o0 - V
2w
M [[(("))] + 4wI² l 22112+ 1 Σi= ||
SwLmax
S
(35)
n
n
n
To construct a Lyapunov function, it remains to bound
vf((t')]] and
|wet1
20+1|p?
12
E(+1
||n5 vf((a*))1)
71
E(41 |||n + SC, - -1) - [((""))1
:=1
1
| vf((z)) || +
23
Σ (M vfi(='), Ex+1 (C - A1)1>> ==1
1=1
8
Ex+1 [|C nD)la
11
(5)
1
|| []((+))|1 + 28 n
Σ (M V((('), V.('')) -M)
11
n i=1
B
1 - -
8 Σ [V/(w()) - -
3)
1/4 [/(2"))' 21
n
1 (3(w 11) [3((+1))-) 1) n
Σ V/((w)) - =n'l?
n
< (1 - 9)
1
h
V )|
8 n Σ
Σ -
n
(0,
where we use that B
E
Thus, using (8), Assumption 2.2 and Lemma B. we have
w+1
1 n n
||1 Ex11
vf(()>)))
< (1 - 3) 1 Σ
11 - (1( 23 1|-'t
- x012 + 48Lmax (f(x*) f(x")) (36)
n
| pet2 1222 12]
It remains bound E
-0+1110 13] Es41 [110t11 -1
Ex-1 |1|u" + c² -w) 2+1
12)
I (1 - Ex44 |||act1 - 133
(1 - Ex+1
|||0 - -6 - - 109
29

---

Under review as a conference paper at ICLR 2023
- 0 (1 - F [lo5 - [s(w))]( - (1
-1- - a) || "VS(w") - w'1 1
$ E ||g* vf(w())l + -1-
2 2 || - z²12² + 22²
[f(("()]
(8)
2 7 B |19' vs(wo') |1
+ +11- ? | - =x11?
2
22
| \/(>)|] + 22² [V[(x²) - -V/(x')
Using Assumption 2.1 and Lemma B.I, we obtain
Es+1
1
++
- x
S E ||00
4221.2
1| - r'11?= + 8
+
1
a
a (f(x") - f(x"))
2
(35)
2w
+ 4w
Iw²= - x21? + Sw (f(2')-((x"))
72
|
(f(("")11
12 i=1
422L2
| = + 872L
+
a
(f(x') -f(x"))
2
a
a
a
4/
42PWL2
11/0 -
- 201 +
272w
Σ | (f((2')11
1
2
a
n²
88 w Lmxx L72L)
(f(x') -s(x))
+
11
a
I (1 a) |!w2 - 1211 +
27
||n5- - -V/(2=11
n²
+ 88 8yPWTmmax 87²1.)
(((t)-f(x'))
where we assume that 7 S v32L and y S
Van V32wL
Let us fix some constants K 2 and v 2 O. We now combine the above inequality with (34), (35) and (36) to obtain
Es41 [f(x
+
- Σ
1
E
| - vf((a')]1) + +vEe+1 ||ulti-x=+1 xlt111
n 1=1
2w Σ
|M vf(x"')11 + 4.2 | - =0 + Sw (f(at) -((e))((x)))
I <f(z") +
n² 1=1
(1- 7H
||0" - ==1
Ex+1 |1|0 -
-2"11 2"11]] + 22 1|e - x211
+ 27
2
2x
n
+K
(1 (1- B)
Σ | Vf(("'))' +/32+23i 111111= 1|00-2"'1 2²12" + 43 (f(x')
- f(x)))
n
(1 4) - 211
2w n²
| vfi(=*)11+ + (87PuImuxx
8,2L1) (000)-((x)) (f(at)-((')) s(0'))
+v
n2 a
Rearranging the last inequality, one can get
1 Ex+1
||a-t|
- x1]]]] Er-1
[ [(x))]
27
+ xx n
Es41
||15t1
Vsi(a*)1? + WE+t1 -1
30

---

Under review as a conference paper at ICLR 2023
1
7/
12-- - =x112
27
8yw-mmxx
(8yWwlmux + - )) (1(29) - (f(=9)
+ x44,3 +
-sxx))
n
+
27W
+ v 27pw
+ 15 16(11 (1-1))
1
|ng - Vfa((=))'' )|2
n1 1=1
+ 2T + n28T. + v (1-
4 (1-4) 14)
| - x'12
+
(37)
Our final goal is to find i. and v such that
27w
27
+ k (1 - 3] = 1 .<1- =x(===x11))) B
+
n
n
2
and
4
+ 2L + x2BL +v (1-4)
a
S 1 1 (1- g)
4
The last inequality is equivalent to
32
16L
163I
+ K
< v.
(38)
na
a
a
From the first equality we get nB
K
4yw
1,2w ng
Thus
32ywi
16L
1632²
32ywL²
16L +
( 4ww
472W)
163I
+
+
R
+ 1
nB
nB
96ywI²
16L
6
96
16L
+
2'
na
a
na
no
a
where we used that 7 S holds. Thus
Vnn V128wL
It means that we can take v
192
+
321. to ensure that (38)
4yw nB
192
32L
4y2w
4rw
768- n2aB
128
+
na
a
nB
n1
n13cx
Let us now substitute these values of and in inequality (37):
Ex+1
|
10] + Fe+1 [1(x - [(x")]
27
1
Es+1 || - Vf((z=)) /|3] + +Ee++1 ||utt1 -
- [2]
+ K
im1
1
[
2/4)
1| |-=-="") xx11|= + k (1
1
9
Σ
- vf(xx)) + (1- 2 || - 2012
2y
2
2
Lyw
47w n3
w 2 1.2
1
+
4,
n1
n²ai3
n18a
192
32L
2
8y2L
+
na
a
1
1
7/
x011 211
+ K 1
Σ
I
v/((t')11 + 1011111 (1-
a) "|1l(t - xy1
2-
2
2
24yxx
< L2 Lmax
? LL
256 WL na²
(1(49) f(x*))
n
n²a
na
a²
31

---

Under review as a conference paper at ICLR 2023
Using the assumptions on y, we have
24x
10"
4608 2w 2 TT2L Limax
20.
1
a²a
na
10"
14
1
1
S
na
10'
1536"
40
S
na²
na.
10'
256
a²
10"
Finally, considering
8 S ,
and S gives
1 29
Es+1 |||at1-- =01
+ Es+1
f(x)))
Σ Ex+1 || v(((==))1 + +E+++1 |1 - 11
+ Kー
1=1
1 (1
7/4
3/4 - n 2 1| - =011 + (1 -
Σ - (
5
2
27
+ (1 (1- - 2 | 201 (5(x') f(x'))
Note that x
47w ng
708 w0"" na
+
1287 n3a
8yw n2
We now prove theorem for the general convex case:
Theorem F.2. Let us assume that Assumptions 2.1, 2.2 and 2.3 hold, the strong convexity parameter
satisfies = 0, B = w+1 x = w and
na
7 S min
160 Lmax
20 20L
100L
Then Algorithm 1 guarantees convergence rate
1
Σ
x f(x')
1 S
1 ||00 x²1 1ax Vs(xx) 7
167w(w +1)
1 11
vf(("'))
T
T
Tn
(39)
Proof. Let bound (32):
E
|| - x= 2013]
+ + [f(x f(x*)]
27
1 12
E |11 v)((=')] [|²]] + DE -
- 11]
+
71
1
(1
7/44
F.
||
--
x ||] 2 F - - [(xx))
2
2
(1
7/4
Σ E
[|M ( >/1} + (1- (1-11774 7/44
E |||et x011
+
2
n
1
E
||اا - x= [2]
+ 1
E [f(x')) -
[(x')]
1 n
Σ
E.
| v)((==>)1
VE
100 - -o'1=
27
n
i=1
32

---

Under review as a conference paper at ICLR 2023
We now sum the inequality for t E {O...., T 1} and obtain
E
1|
=1 + 2 [f(x") - -(xx)] )} +
+ 1
Σ E [f(xt) - [(x))
27
+
1
E
||nt - vfi(2')
\|((=")11] }|1] + V [1100 - =01
n
1
x =²2
1
(f(x0) - -(x")) + - Σ
| -V-((') +vll + =001
+ 2
24
1=1
(f(x9) - -f(x)) + 1/0 - x >11 + 2 $ 27
1
1
81
Σ
|| - Vf(2"))??
n² 8
where we used the assumption 20 w and the bound on K. Using nonnegativity of the terms and convexity, we then have
1
T
- 7T 1100 =x11²= + f(x") - -QV-->((>>)
16
((x))
|
V[((**)]
T
-
T
Tn 3
We now prove theorem for the strongly convex case:
Theorem 3.1. Suppose that Assumptions 2.1, 2.2 and 2.3 hold, B w+I set x0 w and let
y S min 160
Vna 20/
J Then Algorithm I returns x.' such that
1000 (w+1)
|| xt 11 + +E +f(((²") f(x*)] S (1- 7 T vo,
E
where Vo: ;- 24
LE E || - [1] + -(x))) + STw(wt1)
Di=1 /119 vi((t*)1?
n
Proof. Using 7 S 1OOT. S j let us bound (32):
E
||
- x²
+ E [|( -(xx)]
27
1
E |11 vf((z") {|²] + DE || - 11]
+ k
71 1=1
1
(1
7/44
F. ||0''
- x=1 [1] + (
2
2
(1- 7/01
1
ΣΣ [||n vf(("'))? 11²} + + ((1-73 7/14
E |||w" - =0(13]
2
n
1 (1 7/44
E' || 1 [|] + (1 2 E [ -s(x")]
27 2
+ (1
7/8
7
1 n
Σ F. [|M- - V/i(2' >13 + - (1- 1--24 F. [||w* - =013]
7M
n
= (1 7H)
- | - x² x11 |2] + E - -(xx)} + ベニ n
n
| V.((a*) [1] + +E - =219]
E
27
Recursively applying the last inequality and using x0 = w one can get that
E ||o" - x01'
+ +E(f(=") - f(x*)] + 1 E
Σ
|
+ +vE ||=0-~1'11" - 131 VS(()))1
27
n 1=1
33

---

Under review as a conference paper at ICLR 2023
- (1
7p T
|| - =-119 ( +
Σ
1
V (((())))))
2
27
n
Using the nonnegativity of the terms and the bound on we obtain
1
||"" - x= || + E. [T(x)) - -(aa)]
2
(1 11-22
2
F. ||00 x-11"] + (F(x9)
87 2
Σ A
27
F.1 COMMUNICATION COMPLEXITIES IN THE GENERAL CONVEX CASE
We now derive the communication complexities for the general convex case. From Theorem F.2, we know that EF21-P DIANA has the following convergence rate:
f(x)
1 7/
1000 x²1 (xx)) Vs(x')
167w(w +1)
Σ 1 V/(("")]
T
Tn²
Let us take No Vf(())) for all i E [m]. Using Assumptions 2.1 and 2.2, we have
f
1 T
f(x") -
7T 1 =²1
1
T. 1.1120 - =x*1'
T
2T
1=1
16 +1)
n
f((")) Vf(("')]'
+
T'n
1000
x11
+
L
1|200
x*1 112
16/w(w
1) 120 x011"
7T
27
Tn
Using the bound on 7, we obtain that EF21-P DIANA returns an E-solution after
w.rmux
voi.
L +
7wlw +)L2
VnaE
ne
steps. For simplicity, we assume that the server and the workers TopK and Rand compressors, respectively. Thus the server-to-workers and the workers-to-server communication complexities equal
Wbmax
VWD
L
sw(w + 1)2²
x
+
+
+ +
nE
VnaE
aE
ne
dl dImax
dī.
dl.
KL
d
118
NE
8 118
Note that 7 <
y mm
Thus
20/wL
20 wot/ww+11Z
WLmax
VWL
L
L
wwlw
+ 1)i²
1
K
NE
Vnae
a6
E
ne
dLmax
dL
dL
KL
dl
0
11
Vns
nE
ddImax
dī
dL
0
ne
Vne
Since Lmax I nL and L S VnL, this complexity not worse than the GD's complexity O (LL) for any K [1,
34

---

Under review as a conference paper at ICLR 2023
F.2 PROOFS FOR EF21-P DIANA WITH STOCHASTIC GRADIENTS
First, we prove the following auxiliary theorem:
Theorem F33. Let us consider Algorithm 1 using the stochastic gradients Vi instead of the exact
gradients ft for all E [n]. Assume that Assumptions 2.1, 2.2, 2.3 and 3.2 hold, 3 E 0, w+1 and
Vna
8
N min
160w 20
100L
Then Algorithm guarantees that
1
E
[
x²
11²]
+ E f((=tt
2
1
E ++ | Vii(2)) 11] + +vB [||00t1 -
+
ベー
71 i=1
1
(1 7/
E ||0| - x=1 |2]
+ 1 [f((t)) [f(x)]
2
2y
+ (1
7/14
1 -
E || ((( + (1- -/14
E || 1=90=1991 =9]]]] + 127(w + 1)o²
2
2
(40)
where K S
8oe and S nB
192ywI 32L
Proof.
First, we bound E++1 [lg' - vf(w"))
1 E Es+1 ||a|t1- v.((2=))1 and
Using the independence of compressors, we have 11t+1 x [1]
Ex+1
Ex+1
||9* - V ff(w"))l ||3]
1
EE41
hr
cP (P(VVi(w') - -1) Vs(w"))
n i=1
n
(()(t((()))) - m1) (v.r(w0)) - -n: n3)]["]
E1+1
n²
(14)
n
[C(( (2t (Vf((w") - -nt) nnt)(²) /1] + +E++1 - -V(())))(((())))
Ex+1
n
[[((w')) h3 |
[.(0o') - V(((w>))1' |1]
Ex41
E++1
nz
E
f((()²) - h2ll2 + w w+1 1
- -
E
n²
1=1
Vi((w') 1Ell? + (w + 1)o²
n
2w
|| - V/(=1))
2w
VVi(ww') v[((=')]?
(w+ 1)o2 1)o²
22
2w
4w
||
- -/(+>>]
+
VVi(w' - {)((2')11
22 1=1
n
4w
Vif((())) - -
(w + 1102
+
n
n
1=1
35

---

Under review as a conference paper at ICLR 2023
where in the last three inequalities, we used (5) and (8). Using Assumption 2.2 and Lemma B.I, we obtain
E++1
[110
V of
f(w"))
2w
1 V[i(x")]1 + 4w 1 - x21 +
SwLmaxx (f(x") + (w + 1)o²
n
n
Next, we bound
1 n
-i= ||a -fi(z")) )|² to construct a Lyapunov function:
|| 1+ - [10
E
1
|i + | (ff((()( - -h) - V/((2>)
Ex+1
n
1
||
vif((=*)|
+ 2,
n Σ (h: v,((")), E141 (
11
82
| - n2) []]
Ex+1
1 1
23 Σ (44 - V/((a'), Vh(ww) - -n1)
2
1 v1(
71
1=1
1=1
8 +
|| - nill
+
Ex+1
n
(14) 1
||n V[((>'))''
2,3
n Σ (4- - Vii(""), VB((wo)) - -nt)
11
8 w + 1)
[| -n] pl + 1) Σ Ex+1
[ - {/(wm)]'
+
Ex+1
n
1=1
1
2,3 Σ(n - Vf((a'), Vfi(w()) -12) -k
|| - Vf((("))1
+
12
1=1
8 + 1)
a
Σ Es41 || - -191"]] + + + 1)0²
+
n
12)
(1 - 3)
1 n
h4 || ||( + 8 Σ
Vf(ww' V)((21)
1
n2 1=1
B (3(w +1) -1) 1)
Vf((w") - 111l2 + 3:((2w + +1)0²
+
1=1
< s 3) Σ | - v+((')) ||²
1 n
B
(w'' vf((t))] + +B + 1102,
n2
[o.
where we use the assumption 3 E
Using (8), Assumption 2.2 and Lemma B.1, we have
w+1
[I14 - -V((x-)) [|]
< (1 B) و
Σ n
| v)(('))|
1=1
+ +28 || | - 20122 + 4.8mmx ( -
+ 8 + 1)02.
It remains to bound E |10 - -1+1 12]
E+41 [|lott] - 11 = Ees1
I|u' + - -
36

---

Under review as a conference paper at ICLR 2023
1 (1 (1-00) (1-o) Bx+1 | - -wol' 109
= (1 - a) E1+1
|||a - -g- - w0' w0113]
19 (1 - 2 |||s - vf(w())] - (1-a) =
~Vf(w") - -wwl w²12
||0' VS(w')] >|² + (1- / || - x'y? + 27
||
2 2 |||*
(8)
vf(ww)) )1 + (1 | -u'-xx0 =212
+ 47
v(at)] 4
a [Vf(z') vf(2')]??
a
Using Assumption 2.1 and Lemma B.1, we obtain
Es+1
|| - -x"+11" 1|a] S > [|g'
vf(w()]]
47
1 - rd/12+ + 872L
+
1
a
a (f(z') - s(x)))
2
a
2w
4wD² | - r2112+ + Bwimmx (J(x') [(xx)) (w + 1)o²
2
|
-
n 1=1
n
4101²2
=2? + 872L
1
(f(x)) -s(=))
2
a
a
2waw
| - vf((0*)12 + 1 +1--7
+ 472
4r2
1|00 1 2011
a
n
88 Wmxx
872L)
(f(x²) - -f(x)) + ?(w 1)0²
+
n +
a
n
(1
3)
||wi ||'''='')) -1011++
2
|1n - \1(
4
n²
+ 88 W
87²L) (1(x") s(x)) 7(w + 1)o²
a
where we assume that 7 S
Yon Let us fix some constants k 2 0 and v 2 0. In V32T. and y S Va2wI.
the proof of (34) in Theorem F.I, we do not use the structure of g². Hence we can reuse (34) here and combine it with the above inequalities to obtain
Es41 [f
+
K
1
Ec+1
|
Vf((=")1'* + +vee+1 ||w ||w - =11111
n
1=1
2w
vf(("))12+ + 4.
|w* - =0/1/= SwImax
+ (w + 1)0²
$ ff(x") +
- ((('))5(z1))
n
n
1=1
1
(
7H
| -x11|
1 Er+1 |1 || + +2 lle 1lu't=2'111 x112
27
2
27
+
(1- B)
Σ | - vf((z'))' )11² + +,32²
1/'0 - 2011² + 4 ((at)-f(xz") + 82(
(w + 1)0²
2 (1 4 | 2²1
Σ || vf((=')/1 + (872wImax 8,2L) (f(e*) - f(x²)) + 22(w + 1)02
+v
n²
n a
n
==1
Rearranging the last inequality, one can get
1 E,41
||a-t| x x11]] + F [f(x--]-
- -((+)))
2y
37

---

Under review as a conference paper at ICLR 2023
|| V/i((')]
+ Fb+t [| - -x 22421 [19]
+
K
E
11
i=1
1
[1
7/
122 - |a'-x"11
2y
2
Lyw
(8yWwmmax +
))/21 (1(2t) - 1(x2))
(r((t))((0))
+
+ 14,33 + v
n
n
+
2yw
+ 1/
27tw
+ +x(11-))
=
1
n1
| Vf(("')11
71
n
n 5=1
AywL2
+2L + k2Bf.² + v (1 4))
| -u'=x""1 x21
+
n
+ 7ww + 1)0²
x,32 (w + 1)0² + v 2 + 1)02
"
Using the same reasoning as in the proof of Theorem F.I, we have
1
Es+1
||alt|
- x" [1]] + E [ - [xx")]
2y
1
|11$42 - ([(00"))" + uFuti [Iw't]--'' -
+
ki
Ex+1
n i=1
1 (1 ) ||0² -0-11² + (1 - 7/
Σ
h vf((2")]' 1|( + v/ +u(1- )n1) 11100 - =221?
2y
2
i=1
1
(f(x²) - f(x")) + 7(w + 1)0²
+ K. (w + 1)0² + +x 7 + 1)0²
+ 2
n
for some
S nz
mr and v/ S 19
+ 324, Thus
1
E1+1
||
- x² [10] + Ec+1 [ - [xx))]
24
+
1
Ee+1 |11$ - Vii(a'>)\ ||(] + WB++1 [1 [|wut]-='' [1]]
-
n1 i=1
<
1
(1
) ||0² - =0112 + n (1 - 7/4
- Σ | Vi((=")]| + +u +0(1- 7/0)
llv0" - ==²1
2y
2
2
+ 1 (f(x9)
- f(z")) + 7/w + +102
2
n
8x3w(w + 1)0²
+ 1927> + 1)
3272(w + 1)
+
n
n²a
na
1 (1 - 7/4) 1|00 - 1x-1|² + K (1
7/
n
|| - V\(('))] + +0(1- 1| - 222
<
27
2
n1 i=1
+ 2 (((a))((())) + 127(w + 1)o²
where used the bounds on 7 and B.
Theorem 3.3. Let us consider Algorithm using stochastic gradients f instead of exact gradients
wTT: Vt for all i E [n]. Let Assumptions 2.1 2.2, 2.3 and 3.2 hold, 8 = 1 x0 = wo, and S
min|
Vna /
Then Algorithm 1 returns xt such that
160
TOOT:
[w+1)
-T - x² 2=13]] +E [f(xT) - -f(=")] s (1- 2 y + 24(
pm
1 E || - x² ||]] + (S(aO) - -s(x*)) + 8Tw(W+1) n1 Dn 114@ - v/((>>)11
where Vo := 2-
38

---

Under review as a conference paper at ICLR 2023
Proof.
Using y 1001 I je we can bound (40) follows:
E
||
- -
x011"
E [| - -(x=))
27
+ R:
1
E
||1
V }|1] + wE - 111
-
xt
17 i=1
1
(1
7/41
||- 11] + E ((f(())(((())
$
E
2y
2
(1
7/1
1 Σ E
|| - v/((2')1
+ +u(1-1 )-244
[||w* -
+ 12y(w (w + 1)o²
+
E
2
2
1
(1
7/4
E
||
x [9] + (1 2 E [[f(x')-
- -x(x)]]
2
2
+
(1
7/1
1
Σ
F.
[| v<i(('))))))))>)) |13} [1]] + v/ (1 (1-214 7/1
E. [||u* -x91]] + 127(w + 1)o²
2
n
2
= =(1
7/41
1 E
- x² 110] +E E((()() [(x*)] + -x=
ΣE E [Inns - -V)((+)) +oE || - ==1p]]
2
27
+ 12 + 1)0²
Recursively applying the last inequality and using the assumption æ. w one can get that
E
|| - x² 11]]
+ + [f(
f(x*)]
1 - + k
Σ B [1AT - ()(("))1 |1]] + t [||0 - =-11")
27
$
(1
7/4 T
1
E
||"ا xx +²]
+ - f(x"))
+ ー 1=1
aa -
2
2%
+ Σ
(1
7/ )
12 + 1)o²
n
1=
$ (1
7/ T
1 F. || x01²)) + (f(x0) ((x"))
+ +((x9))((00))
1 n
Σ
| - V/(
2%
n
1=1
24( + 1)0²
n4p
Using the nonnegativity of the terms and the bound on K, we obtain
1
E ||a""
x² 11]
+ +E(((²") f(x²)]
27
5 (1
Au T
1 F. |1-00 - x² 201]] + (((69)-((())
- ((x)))
+
8yw
a - v((cor))?)
2
27
n 0
24(w + 1)02
1441
Theorem F.4. Let us consider Algorithm I using stochastic gradients & instead of the exact gradients V for all i [n). Let us assume that Assumptions 2. 2.2, 2.3 and 3.2 hold, the strong convexity parameter satisfies 0, B
x0 w and
Vna
7 S min
160x 20 100L
39

---

Under review as a conference paper at ICLR 2023
Then Algorithm 1 guarantees the following convergence rate:
f T Σ x
f(x)) -
1
1000
2²12
[( Vi(x*)
7T
T
16mw(w +1)
Σ || - Vf((2')] 247(w + 1)0²
+
Tnz
8=1
Proof. Let us bound (40):
1
E
|
x=
19]
E (
27
12
+
F.
||n Vf((2') )[+] + WF
1 -
i=1
7/4
E |||a-
1 _ [f(=')-
- -[(x)]
27
2
+ K (1 - mp
[|M V)'("')]1 + (1 11-241 -/4 E Ilvet - 2-1(²] +
12-(ww + 1)o²
E
2
n
"
E ||aa* - x= 11]] F. [=((aa)-)60 - [(x))] + nー
Σ E | V1((0>))1
S 27
[|w'' - 211"]] 127(w + 1)o²
vF
n
Summing the inequality for E :o,..... T 1} gives
E
|| -
x
2111]
1 E [f(xt) f(x')] 1 Σ
[f(()) - f(x*)]
27
1=1
1
Σ
E' |1455 - vfi(x*)) [|] + +nE +
-z-1? -1
+
-
1
1000 x11? +
1 2 -
(f(a9)-((x)) -x(x)) + Kー Σ 11 V\((2')1
2
+
+wllw0 - 101 +
12T + 1)o²
n
< |/ 2000001 2²12² 11-0-211'- 27
1
+ 1 (f(29) - f(x))) + 87m
Σ 11 - [f(("))| + 12T + 1)0²
2
n²
where we used the fact that x = wD and the bound on k. Using nonnegativity of the terms and convexity, we have
T
- 1
7T 1100 - -x²12== + f(29) vf(x*)
f
x -
-f(x*)
T
T
1=1
167w
247(w + 1)o²
Σ 1145 <)((=*)]1
Tn2.3
40

---

Under review as a conference paper at ICLR 2023
G PROOFS FOR EF21-P DCGD IN THE CONVEX CASE
As mentioned before, EF21-P + DCGD arises a special case of EF21-P + DIANA if we do not attempt learn any local gradient shifts h and instead them to throughout. This can be achieved by setting 3 = 0.
Algorithm 2 EF21-P DCGD
1: Parameters: learning iterate shift w z0 R (stored on the server and the workers)
O; initial iterate xº R (stored the server and the workers); initial
3: for ...,,,..... n in parallel do g. = C. (Vfi(w))
for f. = 0.
do
4:
Compress gradient CP U(w)
5:
Send message of to the server end for
7:
g' = Σi gf
Compute gradient estimator
x441 x "g
Take gradient-type stop
9:
pet1 = C² (0 w²)
Compress shifted model on the server via C B (a))
10:
u01 w² +p" (+1
Update model shift
11:
Broadcast p² to all workers
12:
for i = L,..,,
n in parallet do
13:
w " w² + 11
Update model shift
14:
end for
15:
end for
The proofs in this section almost repeat the proofs from Section F.
Theorem G.1. Let assume that Assumptions 2.1, 2.2 and 2.3 hold and choose
n
Vna a
S min
160
20 100L
Then Algorithm guarantees that
x0
++]
x=11
x
+E [f(x -f -f(x")] +E [| 111
27
1 (1 (1- 7/11
|||0-=0*11 x²113] 113] + [f(xt)) - f(x))]
$ 2/
E
2
+ (1 7/4
+ 47w
Σ ((A(CT)))))
n
E.
(41)
2
n
where v <
32
16L
Proof. Note that EF21-P DCGD is EF21-P + DIANA with , = 0 and h = 0 for all i E [m]] and t 2 O. Up to (37), we can reuse the proof of Theorem F.I and obtain
1
E
||
- x x11
+ Ex+1
[f(*+1]= - [(x*)]
27
1
D
n
Ex+1 ||12422
Vf((a'))] - + vE [1 x
+ ki 11.
7/1
|-'--2"1 xx²12
2y
8rw + KABLmaas +
872wLmax 8/2L )) (J(x') 5(x)))
n
2yw
272w + x (1 -B)
l vf((2')11 Σ
+ v
n
n
1=1
41

---

Under review as a conference paper at ICLR 2023
42wi2
+ + - +0 +1(111111 4)) 1 - 101/
n
Due to 3 = 0, we have
1
Ex+1
||
||
xz1 1+-1-x*110
+ Es+1 [f(x - f(x*)]
27
Ec+1 [|1st1 v + +E+41 -
+
Kー
1=1
1
7/
2
1|x5 x²1
2y
8yw
/81
)
+v
+ a
-((e))
72
71
2yw
27²w +
1
1 - -V((2'11
+
i=1
2L + (1 (1-4)
- 11:0-- -2011
+
Taking x = 0 and
y
32qwi/²
+ 164 we obtain
om
Es+1 27
|| | - x² |2]
+ Es+1 [f(x(+1) f(x*)] + vB++1 [l -
1
(1-
7H
1|-0-20" -
101 1|
(1 (1- a) 8) I x
2n
Brw
327wB?
16L +
(8rPwLmax 8322) (J(a') -s(x")
+
n
27ww
272w
+
+
|
[f(("')1*
1
(1
7/4
|| x= 1|
( || fu'-xx' x211
27
Lyw
256- w 2
Lmax n²a
w
1
1287 L2
(J (f('")
na²
na:
a²
127 + 272w
+
| - V1((")11
Using the assumptions on 7, we have
8ywLmax
10*
3,, 2 T
20
<
n²a
na
10'
128 2
2 17
<
10'
2
1
<
na?
na
10'
128-2112
5
a²
10
Considering 7 5 n. we obtain
E,41 [| - x² [1] + E [f(x - + vEe+1
- 111
27
42

---

Under review as a conference paper at ICLR 2023
1
1 2/
1| x²11
2 (f(x') - f(x*)) +v (1
7/44
2)
1|
x²1
27
27w + 2w
Σ | vf(("))1
+
From the assumptions on 7, we have
2:w + 2
27w +
327WT?
167.
27,2w
4yw
+
on
and hence
Ex+1
xz - Ex+1
- (
+ rBeet1 [||utt] - =1t
27
1
(1- ) ||--->²|| (f(x') - f(x))) v (1- 24) ||w0 - =2'1?
$
24
4yw Σ -
n
1=1
Taking the full expectation, we obtain
B | ++ - x² 21]
+ E [s(attt) - f(x'(( }] + wE -
1 -11
27
1
(1
7/11
||=" x² [1²] ! [[(() f(x")] + v +u(1- 7/14
E ||w 1w'--aa 2'11²]
$
E
2y
4yw
1
n
+
E
| - vf(())))1
n
71
remains use (36) with 3 finish the proof of the theorem.
Theorem G.2. Lel us assume that Assumptions 2. 2.2 and 2.3 hold, the strong convexity parameter
satisfies 0, x= w and
nO
a
7 S min
160w
20 /wL 100L
Then Algorithm 2 guarantees that
T
1 11 - -2"1|+ f(x0) Vf(xa)
87
(1 n Σ (VTA(
f
x
f(x))
- 7T
+
T
T
n
Proof. Let us bound (41):
E
|||2t11
- x² x01
27
+ E [f(x - f(x))] + vE -
27
1
(1
7/
E' || - x² |P] + [ - f(x))| + v/ v/11 (1- 7 E | - |I'' =01
2
2
4,w
Σ
| [f((=t))1
+
1=1
1
E
||'** - x [²]
+ 2 E (f(x)))((2)) -
+ vE Iu' - x² 2113]
+ 4yw
(1 Σ (V
11
2n
We now sum the inequality for E (0....,T- 1} and obtain
T
1
|| -
-
- [[(['))
+ 1 2
Σ E [[(x)) [(x))] + +vE ||w= - x 1-'1
27
43

---

Under review as a conference paper at ICLR 2023
S 27
1
|100 x²11²+ 2 (J(=9)- - [((x)) + + 1111000 -> +
=201
T
1yw
1
n
n
1|-00 - x²112 2 (S(x9) - -(x")) + +T 4YW (1 2 (+*)))
1
=
27
n
where we used the assumption x" = wo. Non-negativity of the terms and convexity gives
T
S 77 11 - x²1 + f(x)) - vf(x*)
1
Syw
1
x
-s(x))
+
T
T
Theorem G.3. Let us assume that Assumptions 2.1, 2.2 and 2.3 hold, x = w. and
n
Vn
a
7 S min
160
wL 100L.
Then Algorithm 2 guarantees that
E || x 119] + [f(=t)
- [(x))
27
T $ [1 -1- ) 27
|1 (01]]+(((6)) +(((a))
+ &w ( n
( (
Proof. Using S 1000. S n let us bound (41):
E
|| - -x01 ||]] + E [f(x [(x"]] vF -
27
1
(1 (1-
7/11 2
E || - x² [1]
+ 1 + [F(()")) - [ + (1- = E |u -
27
47w
a
n
71
1
1
7/14
E
|| x 11] + (1
3/1
2
E [[((')] - [(x))] + (1-
2/44
E 11 -x001
24
2
2
4ww
Σ
1=1
(1
7/41
E
|| x x-1
+E - + +vE 1| 1||""=''""
x²11 =113))
27
4mw
Σ
+
==1
Recursively applying the last inequality and using x² = w. one obtains
E
||0" - x 11]
E
[f((=*) - f(x*)] + wE |||00 - xF1 |²]
27
(1
7/ T
1 F.
1000
=011"] + (((=0)- -
27
+ Σ
T-1
(1
7/0
4yw
1 ( (
2
n 1=1
1=
$ (11-241 )
T
1 F.
|000
=01 + -((o))
44

---

Under review as a conference paper at ICLR 2023
00
Mp
4hw
Σ (((()))))
+
2
n
n
1=0
(1 -1-
)
T
1 E
1000
x² x1] + (
+ 80 1 "
[V
27
mp
Non-negativity of E || | - =2]]"] gives
E. 10" x [1=]] + +E [f(x²) - [(x")]
2
S s(1
)
7u T
1
|100 x²11²] +
+ 8w 1 n
Σ
[V(((>)))))
27
45

---

Under review as a conference paper at ICLR 2023
H FUTURE WORK AND POSSIBLE EXTENSIONS
In this paper, many important features of distributed and federated learning were not investigated in detail. These include variance reduction of stochastic gradients (Horváth et al., 2022; Tyurin & Richtárik, 2022b), acceleration (Li & Richtárik, 2021; Li et al., 2020), local steps (Murata & Suzuki, 2021), partial participation (McMahan et al., 2017: Tyurin & Richtárik, 2022a) and asynchronous SGD (Koloskova et al., 2022). While some are simple exercises and can be easily added to our methods, many of them deserve further investigation and separate work. Further, note that several authors, including Szlendak et al. (2021); Richtárik et al. (2022); Condat et al. (2022), considered somewhat different families compressors than those we consider here. We believe that the results and discussion from our paper can be adapted to these families.
46


Reviews:
[{"review_id": "tqY0M3DQiw", "reviewer": "Reviewer_Vk1R", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes a new error-feedback based gradient compression algorithm for distributed machine learning. The key difference with prior work is that the compression is bidirectional i.e. data sent by both the workers and the server is compressed unlike most prior works which only focus on compressing data sent by the workers. The authors show that a novel application of error feedback at both the server and the workers enables them to improve over the communication complexity of several prior methods and converge at the same rate as gradient descent despite sending significantly lesser data in each direction at each communication round.", "summary_of_the_review": "The paper proposes a new application of error feedback to bidirectional gradient compression. The application is novel and the theoretical results show improvement over prior work. However the evaluation is somewhat limited and the overall gains of the approach for different machine learning models and as compared to methods using error feedback and biased gradient compression at workers aren't clear yet.", "strength_and_weaknesses": "Strengths:\n\n1. To the best of my understanding, this is a novel application of error feedback for server-to-worker compression in distributed machine learning. The fact that it can be used to augment any unbiased worker-to-server compression method also broadens its scope.\n\n2. The theoretical and empirical results presented show improvements over prior work.\n\nWeaknesses:\n\n1. My main concern with the paper is that the overall gain with this approach is not entirely clear. As the authors themselves acknowledge, the received wisdom in this space is that downloading data is faster/cheaper than uploading it which reduces the need for compressing data being sent by the server. Moreover, the proposed approach appears to require the workers to a) maintain local state/memory and b) use an unbiased compressor. While the requirement of maintaining local state is a bit restrictive, that is not a big issue since there are scenarios where such state can be maintained. However, as far as I know, if a worker maintains state, it can use a biased compressor with error feedback to improve significantly over unbiased compressors. As the authors don't compare against any such method, it is unclear if their approach leads to any significant improvement over these approaches, especially when the need for server-side compression may not be that acute to begin with.\n\n2. A second minor concern is the limited empirical evaluation. The authors only consider logistic regression on a few datasets. I would like to see evaluation on some other machine learning models to see if the gains are as apparent in other models as well. Also please clarify why results with the baseline approaches (DIANA, MCM, DASHA) are not presented for all datasets (some have DIANA as the baseline, some have DASHA, some have MCM).", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "gO6MAOHb1vL", "reviewer": "Reviewer_HQee", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors propose EF21-P in eq(3), which is an interesting and novel variant of error feedback. Theoretical analysis is comprehensive and solid. Empirical results on logistic regression task show the benefits of EF21-P.", "summary_of_the_review": "The author proposes a novel variant of error feedback, and it seems very interesting compared with most of the existing error feedback variants. The theoretical analysis looks comprehensive and solid. The only concern is how this method works in practice with larger-scale datasets and more complicated models.", "strength_and_weaknesses": "Strength:\n1. The proposed EF21-P is an interesting way to look at error feedback. The compression error seem to be modeled as the difference between $x$ and $w$, so the optimization objective seem to be make $x$ and $w$ more coherent, which is novel.\n2. The theoretical results are comprehensive, including both the convex and non-convex cases, and the combination with DIANA/DCGD to achieve the best results.\n\nWeaknesses:\n1. The experimental settings are small-scale. #features is 20k and #samples is 72k. A single worker should be sufficient to train logistic regression on this dataset.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "gDDwNC3nmb", "reviewer": "Reviewer_7QTA", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper suggests a new compression method based on the recent EF21 scheme and then used this compression method in the bidirectional distributed SGD method. Authors provide convergence rates for strongly convex, convex, and non-convex objectives. The theory is verified using logistic regression experiments.\n", "summary_of_the_review": "Please see the comments above! \n", "strength_and_weaknesses": "Strength:\n\nI think the most interesting part of this paper is the proposed compression technique and the section “Unified SGD analysis framework with EF21-P mechanism” which is placed in appendix. \n\nWeakness:\n\nWhile there is theoretical value in bidirectional distributed SGD, I  do not think there is much practical gain in using bidirectional compression as there is a number of references that claim that Broadcasting one message to n users is much cheaper than n poin-to-point communication. Therefore, my main criticism is the motivation for bidirectional compression.\n\nAnother question is how do you compare the additional storage cost of distributed algorithm?\n\nAdditionally, I do not think the Assumption on $\\hat{L}$ is standard. Can author provide any justification for that?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "8bMWpRLhit", "reviewer": "Reviewer_m3XR", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a simple error-feedback mechanism called EF21-P, and some variants such as EF21-P + DCGD and EF21-P + DIANA. This paper focuses on the theoretical analysis of EF21-P. The empirical shows good performance.", "summary_of_the_review": "Although this paper may provide some new insights in the theoretical analysis of distributed SGD with error feedback, the experiments are too simple, and more importantly there are some issues in the novelty of EF21-P.", "strength_and_weaknesses": "Strength:\n1. This paper focuses on the theoretical analysis of EF21-P, which provides thorough theories for both convex and non-convex cases.\n2. The empirical shows good performance.\n\nWeakness:\n1. For the empirical analysis, the model (logistic regression) and the datasets (libsvm datasets and cifar-10) are both too small and simple for distributed training. Typically, for such simple and small tasks, a single computer is enough for fast training.\n2. I believe that the main algorithm proposed in this paper, EF21-P, is actually not novel and is equivalent to the original error feedback. See my discussion below for more details. However, I'm not 100% sure about this. So please make clarification and correct me if I'm wrong about this.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject