EF21 with Bells & Whistles: Practical Algorithmic Extensions of Modern Error Feedback
Authors: Ilyas Fatkhullin
Igor Sokolov
Eduard Gorbunov
Zhize Li
Peter Richtárik
Venue: ICLR 2022 Submitted (2022)
Keywords: EF21
error feedback
bidirectional compression
regularization
variance reduction
heavy ball momentum
stochastic approximation

Abstract: First proposed by Seide et al (2014) as a heuristic, error feedback (EF) is a very popular mechanism for enforcing convergence of distributed gradient-based optimization methods enhanced with communication compression strategies based on the application of contractive compression operators. However, existing theory of EF relies on very strong assumptions (e.g., bounded gradients), and provides pessimistic convergence rates (e.g., while the best known rate for EF in the smooth nonconvex regime, and when full gradients are compressed, is $O(1/T^{2/3})$, the rate of gradient descent in the same regime is $O(1/T)$). Recently, Richt\'{a}rik et al (2021) proposed a new error feedback mechanism, EF21, based on the construction of a Markov compressor induced by a contractive compressor. EF21 removes the aforementioned theoretical deficiencies of EF and at the same time works better in practice. In this work we propose six practical extensions of EF21: partial participation, stochastic approximation, variance reduction, proximal setting, momentum and bidirectional compression. Our extensions are supported by strong convergence theory in the smooth nonconvex and also Polyak-Łojasiewicz regimes. Several of these techniques were never analyzed in conjunction with EF before, and in cases where they were (e.g., bidirectional compression), our rates are vastly superior.

Under review as a conference paper at ICLR 2022
EF21 WITH BELLS & WHISTLES: PRACTICAL ALGO- RITHMIC EXTENSIONS OF MODERN ERROR FEEDBACK
Anonymous authors Paper under double-blind review
ABSTRACT
First proposed by [Seide et al. (2014) as heuristic, error feedback (EF) is a very popular mechanism for enforcing convergence of distributed gradient-based optimization methods enhanced with communication compression strategies based on the application of contractive compression operators. However, existing theory of EF relies on very strong assumptions (c.g., bounded gradients), and provides pessimistic convergence rates (e-g., while the best known rate for EF in the smooth nonconvex regime, and when full gradients are compressed, (3/33333) the of gradient descent in the same regime is O(/TT), Recently, Richtárik et al. (2021) (2021) proposed a new eтror feedback mechanism, EF21, based on the construction of a Markov compressor induced by contractive compressor. EF21 removes the aforementioned theoretical deficiencies of EF and the same time works better practice. In this work we propose six practical extensions of EF21, all supported by strong convergence theory: partial participation, stochastic approximation, variance reduction, proximal setting, momentum and bidirectional compression. Several of these techniques were never analyzed in conjunction with EF before, and in cases where they were (e.g., bidirectional compression), rates vastly superior.
INTRODUCTION
In this paper, we consider the nonconvex distributted/federraed optimization problem of the form
f(x)
n +
min aER
(I)
where n denotes the number of clietssworkers/eeiiss//dds connected with server/master and client has an access to the local loss function fi only. The local loss of each client is allowed to have the online/expectation form
fa(z) = EG [fc.
or the finite-sum form
m Mxx) = m Σ (z)(x).
Problems of this structure appear in federated learning (Konečný et al. 2016 Kairouz 2019), where training is performed directly on the clients' devices. In quest for state-of-the-at performance, machine learning practitioners develop elaborate model architectures and train their models on enormous data sets. Naturally, for training this scale be possible, one needs rely on distributed computing (Goyal et al., 2017 You et al. 2020). Since in recent years remarkable empirical successes were obtained with massively over-parameterized models (Arora al. 2018). which puts an extra strain on the communication links during training. recent research activity and practice focuses on developing distributed optimization methods and systems capitalizing on (deterministic or randomized) lossy communication compression techniques to reduce the amount of communication traffic.
A compression mechanism is typically formalized as operator C. dRd Rd mapping hard-to- communicate (e.g., dense) input messages into easy-to-come commmumimcmm (e.g.. sparse) output messages. The operator is allowed to be randomized, and typically operates models Khaled & Richtárik

---

Under review as a conference paper at ICLR 2022
(2019) or on gradients AAlistarh al. (2017); Beznosikov et al. (2020). both of which can be
described as vectors in IR Besides sparsification (Alistarh et al. 2018). typical examples of useful
compression mechanisms include quantization (Alistarh et al.] 2017 Horväth et al. 2019a) and
low-rank approximation (Vogels et al. 2019 Safaryan et al. 2021
There are two large classes of compression operators often studied in the literature: i) unbiased compression operators C, meaning that there exists w 2 0 such that
E [C(=)) x;,
Vo R.: E [[[((=) ==[]] - =||
(4)
and ii) biased compression operators C, meaning that there exists 0 < a S such that
E [[[((x) - x |²] - (1 - a) ||=]| Vo E RRd
(5)
Note that the latter "biased" class contains the former one, i.e., C satisfies 4 with w. then a scaled
version (1 + -) satisfies (5) with a = 1/(++w). While distributed optimization methods with
unbiased compressors 4 are well understood (Alistarh et al. 2017] Khirirat et al. 2018 Mishchenko
ct al. 2019 Horváth et al.) 2019b; Li et al. 2020 Li & Richtárik, 202 Li & Richtárik 20200
Islamov et al. 2021 Gorbunov et al. 2, biased compressors (5) are significantly harder to analyze.
One of the main reasons behind this is rooted in the observation that when deployed within distributed gradient descent in naive way, biased compresors may lead to (even exponential) divergence
(Karimrredy et al. 2019 Beznosikov et al. (020). Error Feedback (EF) (or Error Compensation (EC)) technique originally proposed by (Seide et al. (2014)- emerged as empirical fix of this problem. However, this technique remained poorly understood until very recently.
Although several theoretical results were obtained supporting the EF framework in recent years (Stich cet al. 2018 Alistarh et al.] 2018 Beznosikov et al.) 2020 Gorbunov et al.] 2020 Qian et al. 2020 Tang et al. 2020; Koloskova al. 2020), they use strong assumptions (e.g., convexity, bounded gradients, bounded dissimilarity). and do not get (1/oT) convergence rates in the smooth nonconvex regime. Very recently, Richhááik et al. (202I) proposed a new EF mechanism called EF21, which uses standard smoothness assumptions only, and also enjoys the desirable ((1/ar) convergence rate for the nonconvex case (in terms of number of communication rounds T this matches the best-known rate ((1++)))a)/ obtained by Gorbunov et al. (2021) using unbiased compressors) improving the previous (1/(TT)))/3) rate of the standard EF mechanism (Koloskova et al. 2020).
2
OUR CONTRIBUTIONS
While Richtárik et al. (2021) provide new theoretical SOTA for enror feedback based methods, the authors only study their EF21 mechanism in a pure form, without any additional "bells and whistles" which are of importance in practice. In this paper, we aim to push the EF21 framework beyond its pure form by extending it in several directions of high theoretical and practical importance. In particular, we further enhance the EF21 mechanism with the following six useful and practical algo- rithmic extensions: stochastic approximation, variance reduction, partial participation, bidirectional compression, momentum, and proximal (regularization). We do not stop at merely proposing these algorithmic enhancements: we derive strong convergence results for all of these extensions. Several of these techniques were never analyzed in conjunction with the original EF mechanism before, and in cases where they were, our new results with EF21 are vastly superior. See Table [T for an overview of our results. summary, our results constitute the new algorithmic and theoretical state-of-the. in the area of error feedback.
We now briefly comment on each extension proposed in this paper:
Stochastic approximation. The vanilla EF21 method requires all clients to compute the exact/full gradient in each round. While Richtárik al. (222)) do consider stochastic extension of EF21, they do not formalize their result, and only consider the simplistic scenario of uniformly bounded variance, which does not in general hold for stochasticity coming from subsampling (Khaled & Richtárik 2020). However, exact gradients are not available in the stochastic/online setting (2). and in the finite-sum setting (3) it is more efficient in practice to use subsampling and work with stochastic gradients instead. In our paper, we extend EF21 more general stochastic approximation framework than the simplistic framework considered in the original paper. Our method is called EF21-SGD (Algorithm 2 see Appendix for more details.
2

---

Under review as a conference paper at ICLR 2022
Setup
Method
Citation
Compl. (NC)
Compl. (PC)
Comment
Full graus
EF21
Richtärik et al.
2202
Choco-SGD
Koloskova
2020
NIA
Stoch. grads
EF21-SGD
Richtárik et al.
2021
UBV (Es.
EF21-SGD
NEW
1+- Inf
(Es.
EF21-PAGE
NEW
V/ m
+ m
fi(x)
Su (t))
PP
EF21-PP
NEW
grads
pac
pap
ap
DoubleSqueeze
Tang al.
2020
NIA
[I(((a)
=IIl & A
BC
EF21-BC
NEW
Fall grads
Pwo ard
Mom.
M-CSER
Xie
2020
(1 m)ac3
NIA
IV G
EF21-HB
NEW
N/A
Full grads
Prox
EF21-Prox
NEW
Full grads
@ Red term number of communication rounds, tern expected number gradient compatations per client.
2 Xie al. 2020) consider Nesterov's momentum. Morcover, they analyzed the version with stochastic gradients, bidirectional compression
and local steps However, the derived result is not hetter than state-of sute-of-the-nt the-art ones with either stochastic gradients or hidirectional compression. include the results Xfe (020) the other parts of the table
Therefore, maintain table compact,
This result is obtained under the generalized PL Pt.-coddiion for composite opumization problems (see Assumption from Appendix L2
Table I: Summary of the statc-of-the-art complexity results for finding an E-stationary point, i.c., such a point & that E [+)]I+ < E², for generally non-convex functions and an E-solution, i.c., such point è that B [f()) [(x")] S for functions satisfying PÊ-condition using error-feedback type methods. By (computation) complexity we mean the average number of (stochastic) first-order oracle calls needed to find an e-stationary point ("Compl. (NC)") or s-solution ("Compl. (PE))"). Removing the terms colored in blue from the complexity bounds shown in the table, one can get communication complexity bounds, i.c., the total number of communication rounds needed to find e-stationary point ("Compl. (NC)") e-solution ("Compl. (PL)"). Dependences on the numerical constants, "quality" of the starting point, and smoothness constants are omitted the complexity bounds. Moreover, dependencies on log(?/e) are also omitted in the column "Compl. (PI.)". Abbreviations: "BC"" = bidirectional compression, "Pp"= = partial participation; "Mom." momentum; T the
number communications rounds needed to find an e-stationary point; #grads = number of (stochastic) first-order oracle calls needed to find an s-stationary point. Notation: a = the compression parameter, Oge and aM = the compression parameters of worker and master nodes respectively for EF21-BC, x² +/2 E. of (see Example inf = fiul - - E mi En= fig/ (see Example 2 p probability of sampling the client EF21-PP, v/ = momentum parameter. To the best of our knowledge, combinations of error feedback with partial participation (EF21-PP) and proximal versions of ertor feedback (EF21-Prox) were never analyzed in the literature.
Variance reduction. As mentioned above, EF21 relies on full gradient computations at all clients. This incurs a high or unaffordable computation cost, especially when local clients hold large training sets, i.e., if m is very large in (3). In the finite-sum setting (3). we enhance EF21 with variance reduction technique to reduce the computational complexity. In particular, we adopt the simple and
efficient mariueee-reduced method PAGE (Li et al. 2021 2021b) (which is optimal for solving
problems (3) into EF21, and call the resulting method PAGE (Algorithm 3)
See Appendix
for more details.
Partial participation. The EF21 method proposed by Richtárik et al. 2202)) requires full partici- pation of clients for solving problem (T. i.e., in each round, the server needs to communicate with all clients. However, full participation is usually impractical or very hard to achieve in massively distributed (c.g., federated) learning problems (Konečný al., 2016 Cho et al., 2020 Kairouz 2019) 2
Li& Richtárik 2021b Zhao et al. 2021). To remedy this situation, we propose partial participation (PP) variant of EF21, which we call EF21-PP (Algorithm
4 See Appendix for more details.
Bidirectional compression. The vanilla EF21 method only considers upstream compression of the messages sent by the clients to the server. However, in some situations, downstream communication is also costly (Horváth et al.) 2019a Tang et al. 2020 Philippenko & Dieuleveut 2020). In order to cater to these situations, we modify EF so that the server can also optionally compresses messages before communication. Our master compression is intelligent in that it employs the Markov compressor proposed in EF21 to be used at the devices. The proposed method, based on bidirectional compression, is EF21-BC (Algorithm 5). See Appendix for more details.
3

---

Under review as a conference paper at ICLR 2022
Update
Method
Comment
EF21
Alg.
CiV 9.)
EF21-SGD
Alg. 2
((g 999)
Bel satisties As. 2
Be(p).
Vfi(a if
of + (aylatti)
9¹ 1
Σ0 9:
EF21-PAGE
Ale. B
C(u)t) -9
Jel
9
92 of
Σ (fy(a"), = serg 1. minibatch, 7
EF21-PP
Alg
CIV
i dig
0
x ++1
79
9 111 g" 11
Master broadcasts b'
8441
Ca +-1
EF21-BC
Alg.
C.. on the workers'
g'+1
Σn 0. cf
Car is used on the master's 's side
0.
= x² - yv
1 E1=1 9i
noº + g
EF21-HB
Alp
C(V
E [0,1] momentum parameter
9. 9i + cf
yr
7g').
For problem C (c'+t( - 9 prox (a) is defined
EF21-Prox
Alg. 7
Table 2: Description of the methods developed and analyzed in the paper. For ease of comparison, we also provide a description of EF21. In all methods only compressed vectors d are transmitted from workers to the master and the master broadcasts noncoompeessed iterates x [+1 (except EF21-BC where the master broadcasts compressed vector b b(+1). Initialization of oi, i .,..., can be arbitrary (possibly randomized). One possible choice is of CCV (x²)). The pseudocodes for each method are given in the appendix.
Momentum. A very successful and popular technique for enhancing both optimization and generalization momentum/acceelratioon (Polyak) 1964 Nesterov [983] Lan & Zhou| 2015: |
Zhu 2017 Lan et al. 2019 Li 2021a). For instance, momentum is key building block behind the
widely-used Adam method (Kingma & Ba 2014). In this paper, we add the well-known (Polyak)
heavy ball momentum (Polyak 1964 Loizou & Richtárik, 2020) to EF21, and call the resulting
method EF21-HB (Algorithm 6). See Appendix for more details.
Proximal setting. It is common practice to solve regularized versions of empirical risk minimiza- tion problems instead of their vanilla variants (Shalev-Shwartz & Ben-David 2014). We thus consider the conpoosite/regullrized///e
problem
del'
f1(() +
min ZER
where r(x): Rd RU is regularizer, e.g., l regularizer ||æ]|| or & regularizer ||=|| To broaden the applicability of EF21 such problems, we propose a proximal variant of EF21 solve
the more general composite problems (6). We call this new method EF21-Prox (Algorithm 7 See Appendix for more details.
Our theoretical complexity results are summarized in Table In addition, we also analyze EF 1-
SGD, EF21-PAGE, EF21-PP, EF21-BC under Polyak-Lojasiewice (PL) condition (Polykk 1963
Lojasiewicz 1963) and EF21-Prox under the generalized PÉ-condition (Li & Li| 2018) for composite optimization problems. Due to space limitations, we defer all the details about the analysis under the PE-condition to the appendix and provide only simplified rates in Table [1] We comment on some
preliminary experimental results in Section More experiments including deep learning experiments are presented in Appendix A
METHODS
Since methods modifications of EF21, they share many features, and are presented in unified way in Table [] At each iteration of the proposed methods, worker i computes the compressed vector of and sends it to the master. The methods differ in the way of computing but have similar (in case
4

---

Under review as a conference paper at ICLR 2022
of EF21-SGD EF21-PAGE, EF21-PP -eee-PP-exactly the same) update rules to the one of EF21:
x++1 x²= - 7'",
9 g d
++1
g g++l= =
The pseudocodes of the methods are given in the appendix. Below we briefly describe each method.
EF21-SGD: Error feedback and SGD. EF21-SGD is essentially EF21 but instead of the full gradients ()(x++)), workers compute the stochastic gradients 9. (z and use them to compute cf = C(ā -))). Despite the seeming simplicity of this extension, it is highly important for
various applications of machine learning and statistics where exact gradients are either unavailable prohibitively expensive to compute.
EF21-PAGE:
Error feedback and variance reduction. In the finite-sum regime (3) variance
reduced methods usually perform better than vanilla SGD in many situations (Gower et al. 2020).
Therefore, for this setup We modify EF21 and combine it with variance reduction. In particular, this
time we replace V fi ff(xxt)) in the formula for ef with the PAGE estimator (Li et al. 2021) 1 of --1 With
(lypically small) probability p this estimator equals the full gradient of V.((x ) and with probability 1 p it is set
of
1+1
0
+ 1 Σ AE1;
where I is minibatch of size Ti Typically, the number of data points owned by each client is large, and p S 1/m when T; = 1. As a result, computation of full gradients rarely happens during the optimization procedure: on average, once in every m iterations only. Although it is possible to use other variance-reduced estimators like in SVRG or SAGA, we use the PAGE-estimator: unlike SVRG or SAGA, PAGE is optimal for smooth nonconvex optimization, and therefore gives the best theoretical guarantees (we have obtained results for both SVRG and SAGA and indeed, they are worse, and hence we do not include them).
Notice that unlike VR-MARINA (Gorbunov et al., 202I), which a state-of-the-ar distributed optimization method designed specifically for unbiased compressors and which also uses the PAGE- estimator, EF21-PAGE does not require the communication of full (non-compressed) vectors at all. This is an important property the algorithm since, in some distributed networks, and especially when d is very large, as is the case in modern peramearmmteri deep learning, full vector communication is prohibitive. However, unlike the rate of VR-MARINA, the rate of EF21-PAGE does not improve with increasing n. This is not flaw of our method, but rather an inevitable drawback of distributed methods that rely on biased compressors such as Top-k:
EF21-PP: Error feedback and partial participation. The extension of EF21 to the case of partial participation of the clients is mathematically identical to EF21 up to the following change: cf = 0 for all clients & S, S {l.....n] nn. that are not selected for communication at iteration t. In practice, &f = means that client does not take part the (-th communication round. Here the set S, C (1, (1, (1,....77 ] is formed randomly such that Prob(i- E S,) p: > 0 for all i 1,....74.
EF21-BC: Error feedback and bidirectional compression. The simplicity of the EF21 mecha- nism allows to naturally extend it to the case when it is desirable to have efficient/comppessedd communication between the clients and the server in both directions. At each iteration of EF21-BC. clients compute and send to the master node ci C.. (x**++))) g and update g, + g + of in the usual way. i.e., workers apply the EF21 mechanism. The key difference between EF21 and EF21-BC is that the master node in EF21-BC also uses this mechanism: computes and broadcasts to the workers the compressed vector b = Ca (g g¹) and updates g = g + b(+1, where g²+1 = Σm= J Vector g is maintained by the master and workers. Therefore, the clients are able to update it via using g'+1 = g" + bt+1 and compute x ,+1 = x' - -i once they receive b(+1
EF21-HB: Error feedback with momentum. We consider classical Heavy-ball method (Polyak 1964) with EF21 estimator g":
x x² you" ++1 n70 + gh+1,
-:-1 of + + ge+1
The resulting method is not better than EF21 in terms of the complexity of finding E-stationary point, ie., momentum does not improve the theoretical convergence rate. Unfortunately, this is common
5

---

Under review as a conference paper at ICLR 2022
issue for a wide range of results for momentum methods Loizou & Richtárik (2020). However, is important to theoretically analyze momentum-extenninnn such as EF21-HB due to their importance in practice and generalization behaviour.
EF21-Prox: Error feedback for composite problems. Finally, we make EF21 applicable to the composite optimization problems (6) by simply taking the prox-operator from the right-hand side of the x update rule 7 x=+1 prox, (x" ?g") = arg min ffr(x) + +111//)''1///// This
trick is simple, but, surprisingly, EF21-Prox is the first distributed method with error-feedback that provably converges for composite problems (6).
4 THEORETICAL CONVERGENCE RESULTS
In this section, we formulate a single corollary derived from the main convergence theorems for our six enhancements of EF21, and formulate the assumptions that use in the analysis. The complete statements of the theorems and their proofs are provided in the appendices. In Table T we compare new results with existing results.
4.1
ASSUMPTIONS
In this subsection, we list and discuss the assumptions that we use in the analysis.
4.1.1
GENERAL ASSUMPTIONS
To derive our convergence results, we invoke the following standard smoothness assumption. Assumption 1 (Smoothness and lower boundedness). Every fo has Li-Liscchitz gradient, i.e. [+) Vf)ll) < L || for all i [ma] x, Rd, and fint def inf f(x) > -00.
We also assume that the compression operators used by all algorithms satisfy the following property. Definition (Contractive compressors). We say that (possibly randomized) map C RR Rd is contractive compression operator, simply contractive compressor, if there exists constant a such that
E [[[[(z) x 12] < a1 |1=1,
Vr E Rd
(8)
We emphasize that do not assume C to be unbiased. Hence, theory works with the Top-k (Alistarh et al. 2018) and the Rank-r (Safaryan et al. 2021) compressors, for example.
4.1.2 ADDTIONAL ASSUMPTIONS FOR EF21-SGD
We analyze EF21-SGD under the assumption that local stochastic gradients VSet, (x²) satisfy following inequality (see Assumption of Khaled & Richtárik (2020)).
Assumption (General assumption for stochastic gradients). assume that for all 1,... there exist parameters A,, C 2 0, B 2 1 such that
Sey (a (1 x² 2A, (fi(')) - -inf) ) [[[[ C..
where pinf inf f((x) -0.
Below provide two examples of stochastic gradients fitting this assumption (for more detail,
(Kaaled & Richtárik] 2020)).
Example Consider fee, (x*) such that
vf((a') and E Vie, (x9) Vf((a*) /|² 1x" < oo²
EE v fee (x') x
for some a; 2 0. Then, due to variance decomposition, 9 holds with A; = 0, B, = 0, C2 = of
When A; O one can ignore the first term in the right-hand side of (9) i.c., assumption inf f((z) > not required in this case.

---

Under review as a conference paper at ICLR 2022
Example 2.
Let f((x) En fız(z), fig be Lmo-shooth and fig inf fiy(x) > -00.
Following Gower et al. (2099) we consider a stochastic reformulation
fi(z) B.,DD (f = BugnDD
Σ Frig (x)
(10)
where Eu,-D, [wis] = 1. One can show (see Proposition 2 of Khaled & Richtárik (2020) that under
the assumption that BRADD [ug]] is finite for all j stochastic gradient Vfet (x') =V (x') with
of sampled Dj satisfies ( with A; = maxj LiyBEr,D [v]]] B; 1, C, 24,A inf where
A Th 2j=1 (fial sigt) ). In particular, (robb[Vees Veet, (x²) Vig((()) Σ then
A L, Ei Lig, B = 1, and C. = 2A.
Stochastic gradient (x(x") is computed using mini-batch of independent samples satisfying 9):
Ds (xx) def
Vle (x').
4.1.3 ADDITIONAL. ASSUMPTIONS FOR EF21-PAGE
In the analysis of EF21-PAGE, rely the following assumption. Assumption (Average L-smoothness). Let every f. have the form (3. Assume that for all t 2
0, i = I,...,n, n, and batch 11 (of size Ti). the minibatch stochastic gradients difference / def
1 EE (Vfi((z*+)) fii((z")) computed on the node i, satisfies E
A x² xx,x(++]] = A and
E A
4. 7. 11 - 1²12 <
(11)
with some C, 2 0, where A def Vfi(att))- Vf((x'). We also define C def E (1-pa)
This assumption is satisfied for many standard//popular sampling strategies. For example, if 1 is a full batch, then L, Another example is uniform sampling on (1.....m) and each fig is smooth. In this regime, one may verify that L; I maxisism Lij-
4.2
MAIN RESULTS
Below we formulate the corollary establishing the complexities for each method. The complete version of this result is formulated and rigorously derived for each method in the appendix.
Corollary 1. Suppose that Assumption holds. Then, there exist appropriate choices of parameters for EF21-PP, EF21-BC, EF21-HB, EF21-Prox such that the number of communication rounds and the (expected) number of gradient computations at each node 4 grad for these methods to find an E-stationary point, i.e., a point a" such that [[ < for EF21-PP, EF21-BC, EF21-HB and ( < e2 for EF21-Prox, where Gx(x) = 1/7 (x prox, (x >V]()))) are
EF21-PP:
= O
Lso p
#grad O
La ng
EF21-BC:
T #grad = 0
L8
awrrrer
EF21-HB:
T #grud 0
I-
Lgu
EF21-Prox:
T #grad O
ac
where T. def V - def {(1)) (for EF21-Prox = - ), p is the probability of sampling the client in EF21-PP. aw and am are contraction factors for compressors applied on the workers' and the master's 's sides respectively in EF21-BC, and 17 E [0,1) is the momentum parameter in EF21-HB.
7

---

Under review as a conference paper at ICLR 2022
If Assumptions 7 ann in the setup from Example 1 hold, then there exist appropriate choices of parameters for EF21-SGD such that the corresponding T and the averaged number of gradient computations at each node # grad are
EF21-SGD:
T T=
L8 ac
#grad O
L5" as a²
+
L5"0² 2
where - -
If Assumptions and and hold, then there exist appropriate choices of parameters for EF21 such that the corresponding T and #grad are
EF21-PAGE:
T=
(T+ Ei8"
VmL
#grad = O (m +
(T. Z)0 as
y C6.
a6
5²
where C = V
LR Ei
C3 T3 TT-L
Remark:
We highlight some points for our results in Corollary 1 as follows:
For EF21-PP and EF21-Prox: none of previous error feedback methods work these settings (partial participation and proximal/composit case). Thus, we provide the first convergence results show that the gradient (computation) complexity for both EF21-PP and
for them. Moreover, EF21-Prox is (()ae), matching the original vanilla EF21. It means that we extend EF21 to both settings for free.
For EF21-BC, we show O complexity result. In particular, if one uses constant ratio of compression (e.g., 10%), then z 0.1. Then the result will be O(122). However, previous result of DoubleSqueeze is (()e²)) and it also uses more strict assumption for the compressors (E []][(x) - xlI] A). Even if we ignore this, our results for EF21-BC is better than the one for DoubleSqueeze by large factor 1/s.
Similarly, our result for EF21-HB is roughly 0(122) (note that the momentum parameter v) usually constant such as 0.2, 0.4, 0.9 used in our experiments). However, previous result of M-CSER is roughly O(G/=)) and it proven under an additional bounded gradient assumption. Similarly, our EF21-HB is better by a large factor 1/e.
For EF21-SGD and EF21-PAGE, we want to reduce the gradient complexity by using (variance- reduced) stochastic gradients instead of full gradient in the vanilla EF21. Note that o² and A inf in EF21-SGD could be much smaller than G in Choco-SGD since G' always depends on the dimension (and can be infinite), while x² and A inf are very small the functions/data samples are similar/close). Thus, for high dimensional problems (e.g., deep neural networks), EF21-SGD can be better than Choco-SGD. Besides, in the finite-sum case (3), especially if the number of data samples m on each client is not very large, then EF21-PAGE much better since its complexity is roughly O(ym/s2) while EF21-SGD ones is roughly O(7)
mostly dimension-free parameters (particularly, they
EXPERIMENTS
In this section, we consider a logistic regression problem with non-convex regularizer
min FER
f(x) = Σ log (1 exp (-b,a,
(12)
where E Idd, b; {-1,)) are the training data, and À > 0 is the regularization parameter, which set to = 0.1 all experiments. For all methods the stepsizes are initially chosen as the largest stepsize predicted by theory for EF21 (see Theorem TT. then they are tuned individually for each parameter setting. We provide more details on the datasets, hardware, experimental setups, and additional experiments, including deep learning experiments in Appendix
Fast convergence with variance reduction. In our first experiment, we showcase the computation and communication superiority of EF21-PAGE (Alg. over EF21-SGD.
Experiment 1:
Figure & illustrates that, in all cases, EF21-PAGE perfectly reduces the accumulated variance and converges the desired tolerance, whereas EF21-SGD is stuck at accuracy level. Moreover,
8

---

Under review as a conference paper at ICLR 2022
EF21-PAGE turns out to be surprisingly efficient with small bathsizes (eg, 1.5% of the local data both in terms of the number of epochs and the # bits sent to the server per client. Interestingly, for most datasets, a further increase of bathsize does not considerably improve the convergence.
mus troo Mt., Top
wdb, Top
390, Top
shishing. Top-)
10--
10-1
10
10
E/21 SOt P72 12.5%
12
CF236644
0216000
1.5%
CF2l-dde Loe
10"4
CF234h2l sanc
12.0%
10
D'2LAAEE 125%
Ce:
10
E'2I0NNE und
10
27%
2444AA 1D%
C'2iiia 120e 2.2%
EF2ieNat: 35%
250
400
105
250
40
20
45
E0
(a) Convergence in epochs.
TOOOTTA, Tep-
wif Top-2
Tops?
hi-shing, Top-3
P073 AiRk 20d6, 29t
10
10
(F2)-A00 Mi 12
30-4
10
10
Fiel and
end and (ic 9%
10-1
10-4
E/2EPAEE dec 13.8%
10-
0121-022 2 dec
25%
10
EP22 Mide 12.5%
120
OPSL-NNE: 135
100000
200000
302000
100000 200000
300000
50000
100000
20003
40000
(b) Convergence in terms of total number of bits sent from Clients to the Server divided by n.
Figure I: Comparison of EF21-PAGE and EF21 with tuned parameters. By 1x,2x, 2x, 4x (and so on) we indicate that the stepsize was set to a multiple of the largest stepsize predicted by theory for EF21. By 25%, 12.5% and 1.5% we refer batchsizes equal [0.25NNJ.. [0.125N,] and [0.015.N for all clients i = 1, I,, where N, denotes the size of local dataset.
Experiment 2: On the effect of partial participation of clients. This experiment shows that EF21-PP (Alg. 4 can reduce communication costs and can be more practical than EF21. For this 100 and, therefore, apply a different data partitioning, see Table from Appendix A for more details.
comparison, we consider
is predicted by our theory (Corollary that, in terms of the number of iterations/communicattooo rounds, partial participation slows down the convergence of EF21 by a fraction of participating clients. We observe this behavior practice as well (see Figure 2a However, since for EF21-PP
the communications are considerably cheaper it outperforms EF2 in terms of # number of bits sent to the server per client on average (see Figure
mushrooms, Top Librs sit
wBa, Top-2
250. Tos-2
stisting Tos-1
10t
10f
10a
16f
10-2
16-2
10-1
01211100
E/21 Laf
s/20-r J0c 2ory
1022 en Jis J5h
proiiw ea Boa
M925 en Bu Kir
ar2 la 6.
5000
15600
T5000
1903
2505
1050
250
503
255
530
750
commurication munds
commin cnlon munds
communication munnds
communcction mounds
(a) Convergence in communication rounds.
7100 Top
Top.2
Top
shishingTTop
3.2
C/2 Libre
C/2 132h
21- 190 12.2%
-0
PRTL 1he
ext the 29c. P82 a2
eol You
PR73 oc
BQLAE Acc
2923.09
454
100000 4bisa C1
203000
$0000 100000
15050 20203
30000
5000 #bism (C+5)
30505
plisi 31
(b) Convergence in terms of total number of bits sent from Clients to the Server divided by
Figure 2: Comparison of EF21-PP and EF21 with tuned parameters. By 1x, 2x, 4x (and so on) we indicate that the stepsize set to a multiple of the largest stepsize predicted by theory for EF21. By 50%, 25% 12.5% and 6.5% we refer to a number of participating clients equal to [0.5m], [0.25n]. |0.125m and (0.065n].

---

Under review as a conference paper at ICLR 2022
REFERENCES
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovie. QSGD: Communication- efficient SGD via gradient quantization and encoding. In Advances Neural Information Process- ing Systems (NIPS), pp. 1709-1720, 2017.
Dan Alistarh, Torsten Hoefler, Mikael Johansson, Sarit Khirirat, Nikola Konstantinov, and Cédric Renggli. The convergence of sparsified gradient methods. In Advances in Neural Information Processing Systems (NeurIPS), 2018.
Zeyuan Allen-Zhu. Katyusha: The first direct acceleration of stochastic gradient methods. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Compuling, pp. 1200- 1205. ACM, 2017.
Yossi Arjevani, Yair Carmon, John C Duchi, Dylan J Foster, Nathan Srebro, and Blake Woodworth. Lower bounds for non-convex stochastic optimization. arXiv preprint arXiv: 2019.
Sanjeev Arora, Nadav Cohen, and Elad Hazan. On the optimization of deep networks: Implicit acceleration by overparameterization. In Proceedings of the 35th International Conference on Machine Learning (ICML), 2018.
Amir Beck. First-Order Methods Optimization. Society for Industrial and Applied Mathematics, 2017.
Aleksandr Beznosikov, Samuel Horváth, Peter Richtárik, and Mher Safaryan. On biased compression for distributed learning. arXiv preprint arXiv: 124400 2020.
Léon Bottou. Curiously fast convergence of some stochastic gradient descent algorithms. In Proceedings of the symposium learning and data science, Paris, volume 8, pp. 2624-2633, 2009.
Léon Bottou. Stochastic gradient descent tricks. In Neural networks: Tricks of the trade, pp. 421-436. Springer, 2012.
Chih-CCung Chang and Chih-Jen Lin. LIBSVM: a library for support vector machines. ACM
Transactions Intelligent Systems and Technology (TIST), 2(3):1-27, 2011.
Yae Jee Cho, Jianyu Wang, and Gauri Joshi. Client selection in federated learning: Convergence analysis and power-of-choice selection strategies. arXiv preprint arXiv:2010.01243v1, 2020.
Eduard Gorbunov, Dmitry Kovalev, Dmitry Makarenko, and Peter Richtárik. Lincarly converging error compensated SGD. In 34th Conference Neural Information Processing Systems (NeurIPS), 2020.
Eduard Gorbunov, Konstantin Burlachenko, Zhize Li, and Peter Richtárik. MARINA: Faster non- convex distributed learning with compression. In International Conference on Machine Learning, pp. 3788-3798. PMLR, 2021. arXiv:2102.07845.
Robert M Gower, Mark Schmidt, Francis Bach, and Peter Richtárik. Variance-reduced methods for machine learning. Proceedings of the IEEE, 108(11):1988-1))) 2020.
Robert Mansel Gower, Nicolas Loizou, Xun Qian, Alibek Sailanbayev, Egor Shulgin, and Peter Richtárik. SGD: General analysis and improved rates. In International Conference on Machine Learning, pp. 5200-5209. PMLR, 2019.
Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, Andrew Tulloch, Yangqing Jia, and Kaiming He. Accurate, large minibatch sgd: Training imagenet in hour. arXiv preprint 1rXiv:1706.02677 2017.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 770-778, 2016.
10

---

Under review as a conference paper at ICLR 2022
Samuel Horváth and Peter Richtárik. A better alternative to error feedback for communication efficient distributed learning. In 9th Interaational Conference on Learning Representations (ICLR), 2021.
Samuel Horváth, Chen- Yu Ho, L'udovít Horváth, Atal Narayan Sahu, Marco Canini, and Peter Richtárik. Natural compression for distributed deep learning. arXiv preprint 19X.v 2019a.
Samuel Horváth, Dmitry Kovalev, Konstantin Mishchenko, Sebastian Stich, and Peter Richtárik. Stochastic distributed learning with gradient quantization and variance reduction. arXiv preprint arXiv:1904.051/ 05100. 2019b.
Rustem Islamov, Xun Qian, and Peter Richtárik. Distributed second order methods with fast rates and compressed communication. arXiv preprint arXiv:2/02.07/55 2021.
Peter et al Kairouz. Advances and open problems in federated learning. arXiv preprint 1912v47912.04977, 2019.
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.
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. SCAFFOLD: Stochastic controlled averaging for federated learning. In Proceedings of the 37th International Conference on Machine Learning, 2020.
Ahmed Khaled and Peter Richtárik. Gradient descent with compressed iterates. In NewrlPS Workshop on Federated Learning for Data Privacy and Confidentiality, 2019.
Ahmed Khaled and Peter Richtárik. Better theory for SGD in the nonconvex world. arXiv preprint arXiv:2002.005 033329 2020.
Sarit Khirirat, Hamid Reza Feyzmahdavian, and Mikael Johansson. Distributed learning with compressed gradients. arXiv preprint 1 2018.
Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint arXiv:1412.6988) 2014.
Anastasia Koloskova, Tao Lin, S. Stich, and Martin Jaggi. Decentralized deep learning with arbitrary communication compression. International Conference on Learning Representations (ICLR), 2020.
Jakub Konečný, H. Brendan McMahan, Felix Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: strategies for improving communication efficiency. In NIPS Private Multi-Party Machine Learning Workshop, 2016.
Alex Krizhevsky, Geoffrey Hinton, al. Learning multiple layers of features from tiny images. Technical report, University of Toronto, Toronto, 2009.
Guanghui Lan and Yi Zhou. An optimal randomized incremental gradient method. arXiv preprint arXin:1507.02000. 2015.
Guanghui Lan, Zhize Li, and Yi Zhou. unified variance-reduced accelerated gradient method for convex optimization. In Advances in Neural Information Processing Systems, pp. 10462-10472, 2019.
Zhize Li. ANITA: An optimal loopless accelerated variance-reduced gradient method. arXiv preprint IIXiv22103.11333 2021a.
Zhize Li. A short note of page: Optimal convergence rates for nonconvex optimization. arXiv preprint arXiv:2 106.000900 09663, 2021b.
Zhize Li and Jian Li. A simple proximal stochastic gradient method for nonsmooth nonconvex optimization. In Advances in Neural Information Processing Systems (NeurIPS), pp. 5569-5579, 2018.
11

---

Under review as a conference paper at ICLR 2022
Zhize Li and Peter Richtárik. A unified analysis of stochastic gradient methods for nonconvex federated optimization. arXiv preprint arXiv:2006.07013, 2020.
Zhize Li and Peter Richtárik. CANITA: Faster rates for distributed convex optimization with communication compression. arXiv preprint arXiv:2107.09461, 2021a.
Zhize Li and Peter Richtárik. ZeroSARAH: Efficient nonconvex finite- sum optimization with zero full gradient computation. arXiv preprint arXiv:2103.01447) 2021b.
Zhize Li, Dmitry Kovalev, Xun Qian, and Peter Richtárik. Acceleration for compressed gradient
descent in distributed and federated optimization. In International Conference on Machine Learning (ICML), pp. 5895-5904. PMLR, 2020.
Zhize Li, Hongyan Bao, Xiangliang Zhang, and Peter Richtárik. PAGE: A simple and optimal probabilistic gradient estimator for nonconvex optimization. In International Conference on Machine Learning (ICML), pp. 6286-6295, PMLR, 2021. arXiv:2008. 10898.
Nicolas Loizou and Peter Richtárik. Momentum and stochastic momentum for stochastic gradi- ent, Newton, proximal point and subspace descent methods. Computational Optimization and Applications, 77:653-710, 2020.
Stanislaw Lojasiewicz. A topological property of real analytic subsets. Coll. du CNRS, Les équations aux dérivées partielles, 117(87-89):2, 1963.
Konstantin Mishchenko, Eduard Gorbunov, Martin Takáč, and Peter Richtárik. Distributed learning 2019.
with compressed gradient differences. arXiv preprint
Konstantin Mishchenko, Ahmed Khaled, and Peter Richtarik. Random reshuffling: Simple analysis with vast improvements. In Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 17320 Curran As- sociates, Inc., 2020.
nwwrineuip...e pptp://rroooeeenncen.u.or.pppppp / pdd.
Yurii Nesterov. method for unconstrained convex minimization problem with the rate of conver- gence (1/K* 2). In Doklady AN USSR, volume 269, pp. 543-547, 1983.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, pegforeerfrmeece deep learning library. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
Constantin Philippenko and Aymeric Dieuleveut. Bidirectional compression in heterogeneous settings for distributed or federated learning with partial participation: tight convergence guarantees. arXiv preprint arXiv:2006. 14591, 2020.
Boris T Polyak. Gradient methods for the minimisation of functionals. USSR Computational
Mathematics and Mathematical Physics, 3(4):864-9)) 1744,4878817 1963.
Boris T Polyak. Some methods of speeding up the convergence of iteration methods. Ussr computa- tional mathematics and mathematical physics, 4(5):1-17, 1964.
Xun Qian, Peter Richtárik, and Tong Zhang. Error compensated distributed SGD can accelerated. arXiv preprint arXiv:2010.00091 2020.
Zheng Qu and Peter Richtárik. Coordinate descent with arbitrary sampling ii: Expected separable overapproximation. arXiv preprint arXiv:1412.8063 2014.
Peter Richtárik, Igor Sokolov, and Ilyas Fatkhullin. EF21: A new, simpler, theoretically better, and practically faster emor feedback. arXiv preprint arXiv:2 2021.
Mher Safaryan. Rustem Islamov, Xun Qian, and Peter Richtárik. FedNL: Making Newton-type methods applicable to federated learning. arXiv preprint 1rX.v92/00.00969, 2021.
12

---

Under review as a conference paper at ICLR 2022
Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu. 1-bit stochastic gradient descent and its application to data-pan aata-parallel distributed training of speech DNNs. In Fifteenth Annual Conference of the International Speech Communication Association, 2014.
Shai Shalev-Shwarz and Shai Ben-David. Understanding machine learning: from theory to algo- rithms. Cambridge University Press, 2014.
Sebastian U. Stich, J.-B. Cordonnier, and Martin Jaggi. Sparsified SGD with memory. In Advances in Neural Information Processing Systems (NeurlPS), 2018.
Hanlin Tang, Xiangru Lian, Chen Yu, Tong Zhang, and Ji Liu. DoubleSqueeze: Parallel stochastic gradient descent with double-past croo--comennsted compression. In Proceedings of the 36th International Conference on Machine Learning (ICML), 2020.
Thijs Vogels, Sai Praneeth Karimireddy, and Martin Jaggi. PowerSGD: Practical low-rank gradient compression for distributed optimization. In Neural Information Processing Systems, 2019.
Zhe Wang, Kaiyi Ji, Yi Zhou, Yingbin Liang, and Vahid Tarokh. Spiderboost and momentum: Faster stochastic variance reduction algorithms. arXiv preprint arXiv: 10690, 2018
Cong Xie, Shuai Zheng, Oluwasanmi Koyejo, Indranil Gupta, Mu Li, and Haibin Lin. CSER: Communication efficieet SGD with error reset. Advances in Neural Information Processing Systems (NeurIPS), pp. 12593- 12603, 2020.
Haibo Yang, Minghong Fang, and Jia Liu. Achieving linear speedup with partial worker participation in non-iid federated learning. arXiv preprini arXiv:2101./1203.0 2021.
Tianbao Yang, Qihang Lin, and Zhe Li. Unified convergence analysis of stochastic momentum methods for convex and non-convex optimization. arXiv preprint wiXiv:164.003577 2016.
Yang You, Jing Li, Sashank Reddi, Jonathan Hseu, Sanjiv Kumar, Srinadh Bhojanapalli, Xiaodan Song. James Demmel, Kurt Keutzer, and Cho-Jui Hsieh. Large batch optimization for deep learning: Training bert in 76 minutes. In International Conference on Learning Representations, 2020.
wwt. wtt.://ttee.oormr...d........mr.
Haoyu Zhao, Zhize Li, and Peter Richtárik. FedPAGE: A fast local stochastic gradient method for coammunicatiooneffiicce federated learning, arXiv preprint 200.0210..
13

---

Under review as a conference paper at ICLR 2022
TABLE OF CONTENTS
Introduction
2
Our Contributions
Methods
4
Theoretical Convergence Results
4.1
Assumptions
4.1.1
General Assumptions
4.1.2
Addtional Assumptions for EF 21 SGD
4.1.3
Additional Assumptions for 2F21-PAGE
Main Results
5
Experiments
Extra Experiments
15
Non-Convex Logistic Regression: Additional Experiments and Details
15
A.2
Experiments with Least Squares
20
A.3 Deep Learning Experiments
20
Notations and Assumptions
22
EF21
23
Convergence for General Non-Convex Functions
23
Convergence under Polyek-L.ojaseewicz Condition
25
Stochastic Gradients)
27
D.1 Convergence for General Non-Convex Functions Convergence under Polyak-L.ojasiewie Condition
28
D.2
32
Variance Reduction
35
E.
Convergence for General Non-Convex Functions
37
E.2
Convergence under Polyak-Lojasiiwwizz Condition
41
Partial Participation
44
FI
Convergence for General Non-Convex Functions
47
F2
Convergence under Polyak-t.ojasiewicz Condition
48
Bidirectional Compression
49
G.T
Convergence for General Non-Convex Functions
51
G.2
Convergence under Polyak-Lojasiewiez Condition
53
H Heavy Ball Momentum
55
H.1
Convergence for General Non-Convex Functions
57
Composite Case
63
Convergence for General Non-Convex Functions
65
1.2
Convergence under Polyak-Lojasiewiczz Condition
67
J
Useful Auxiliary Results
70
Basic Facts
70
2 Useful Lemmas
70
14

---

Under review as a conference paper at ICLR 2022
A EXTRA EXPERIMENTS
In this section, we give missing details on the experiments from Section and provide additional experiments.
A.1 NON-CONVEX LOGISTIC REGRESSION: ADDITIONAL. EXPERIMENTS AND DETAILS
Datasets, hardware and implementation. We use standard LibSVM datasets (Chang & Lin 2011 and split each dataset among n clients. For experiments 3, 4 and 5, we chose n. 20 whereas for the experiment 2 we consider = 100. The first n clients own equal parts, and the remaining part,
of size .N- n |M/n|, is assigned to the last client. We consider the heterogeneous data distribution regime (i.e. we do not make any additional assumptions summary of datasets and details of splitting data among workers can be found in Tables [ and [5]
data similarity between workers). A
The algorithms implemented in Python 3.8; use 3 different CPU cluster node rypes in all
experiments: 1) AMD EPYC 7702 64-Core; 2) Intel(R) Xcon(R) Gold 6148 CPU @ 2,40GHz; CPU 2.50GHz. In all algorithms involving compression, we use Top-k (Alistarh et al. 2017) as canonical example of contractive compressor C, and fix the compression ratio */d = 0.01, where d the number of features in the dataset. For all algorithms, at each iteration we compute the squared norm of the exact/full gradient for comparison of the methods performance. We terminate our algorithms either if they reach the certain number of iterations or the following stopping criterion is satisfied: || f="))"" s 10-7.
3) Inte Xeon(R) Gold 6248
In all experiments, the stepsize is set to the largest stepsize predicted by theory for EF21 multiplied by some constant multiplier which was individually tuned in all cases.
Dataset
N (total # of datapoints)
d (# of features)
k
N₃
mushrooms
20
8,120
112
2
406
w
20
49,749
300
2,487
a9a
20
32,560
123
2
1,628
phishing
20
11,055
68
552
real- 1ell--imm isim
20
72,309
20,958
210
3615
Table 3: Summary of the datasets and splitting of the data among clients for Experiments 1, 4, and
Here N; denotes the number of datapoints per client.
Experiment 1: Fast convergence with variance reductions (extra details). The parameters pa of the PAGE estimator are set to P; def E N; where тÚ is the batchsize for clients i i= 1,... .n (see Table for details). In our experiments, we assume that the sampling of Bernoulli random variable is performed on server side (which means that at each iteration for all clients = or by 0). And if by = O, then in line 5 of Algorithm 3 f is sampled without replacement uniformly random. Table shows the selection of parameter p for each experiment.
For each batchsize from the se
(95%, 50%, 12.5%, 6.5%,3%),
we tune the stepsize multiplier for EF21-PAGE within the set {0.25, 0.5, 1,2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048).
The best pair (batchsize, stepsize multiplier) is chosen in such a way that it gives the best convergence in terms of #bits/n(CC - 5). In the rest of the experiments, fine tuning is performed in similar fashion.
By 50%, 25% (and on) we refer to a hatchsize, which is equals to [0.5N.., [0.25N,] (and so on) for all clients 1.
15

---

Under review as a conference paper at ICLR 2022
Dataset
25%
12.5%
1.5%
mushrooms
0.1992
0.1097
0.0146
wBa
0.1998
0.1108
0.0147
a9a
0.2
0.1109
0,0145
phishing
0.2
0.1111
0.0143
real-sim
0.1999
0.1109
0.0147
Table Summary of the parameter choice of p.
Experiment 2: On the effect of partial participation of clients (extra details) In this experiment, we consider 100 and, therefore, a different data partitioning, see Table 5 for the summary.
Dataset
N (total # of datapoints)
of features)
k
N;
mushrooms
100
8,120
112
2
w
100
49,749
300
2
497
a 9a
100
32,560
123
2
325
phishing 100
11,055
68
1
110
Table Summary of the datasets and splitting of the data among clients for Experiment Here N; denotes the number of datapoints per client.
We tune the stepsize multiplier for EF21-PP within the following set:
(0.125,0.25, 0.5, 1,2,4,8, 1,,,,,,,,8 16, 64, 128, 256, 512, 1024, 2048, 4096).
On the advantages of bidirectional biased compression. Our next experiment demonstrates that the application of the Server - Clients compression in EF21-BC (Alg. 5 does not significantly slow down the convergence terms of the communication rounds but requires much less bits to be transmitted. Indeed, Figure 3a illustrates that that it is sufficient to communicate only 5% 15% of data to perform similarly EF21 (Alg. Note that EF21 communicates full vectors from the Server + Clients, and, therefore, may have slower communication at each round. In Figure 3b we take into account only the number of bits sent from clients to the server, and therefore we observe the same behavior as in Figure 3al However, if we care about the total number of bits (see Figure 3c), then EF21-BC considerably outperforms EF21 in all cases.
Experiment 3:
'The range 5% 15% from the fractions k/4 for each dataset.
16

---

Under review as a conference paper at ICLR 2022
TIOOTT,, Top-2
rdla Top-2
Top-2
shahing Top-3
1.0
#EA 2884
101
107
uEa 244
WED Toudts COLIT
erties Tardh
was mordss
10
-0
Eraaac 10 dec
hopiei- J0x
10
10
10
10
1000
2003
3000
10:0
2005
3009
500
1000
208
400
cadon
Communcation
(a) Convergence in communication rounds.
trooms, 2
wda, Top-2
a2a, Top
phahting Top-2
2.0
di LaB
10
1iza Co
101
uiz ans
10
012-40 tapets cu
axzzeci rapett
01:44: tapets
1014.
[pari
10
10
10
10
T00000 #beat +51
2000000
1001036
200000
20000
20000
100015
5205
15000
#bism
#btiann (2
#bttm (C
(b) Convergence in terms total number of bits sent from Clients to Server divided by zt.
Topel
100
No har
10
grot aclll ao eot an ae tie
10e
ertt entt the
10
evnt an
to has mowe
12
#bitch 10 S----15--00
106
#bttat 1C -115-55- -C)
105
#bilam IC CS----1---
#bism (C-54S--6 -1
(c) Convergence in terms of total number of bits from Clients the Server plus the total number of bits broadeasted from Server to Clients divided by n.
Figure 3: Comparison of EF21-BC and EF21 with tuned stepsizes By 1x, 2x, 4x (and so on) we indicate that the stepsize was set to a multiple of the largest stepsize predicted by theory for EF21 (see the Theorem T
For each parameter k in Server-Client compression, tune the stepsize multiplier for EF21-BC within the following set:
{0. 10.125,0.25,, 0.5, 4,8,
4,8, 16, 32, 64, 128, 256, 512, 1024, 2048).
Experiment 4:
On the cheaper computations via EF21-SGD. The fourth experiment (see Fig- ure 4aj illustrates that EF21-SGD (Alg. ( is the more preferable choice than EF21 for the cases when full gradient computations are costly.
For each batchsize from the se
(95%, 50%,55%%,,7,,,, 25%,12.5% 6.5%,3%)
we tune the stepsize multiplier for EF21-SGD within the following set:
(0.25, 0.5, 1,2, 4, 16, 32, 64, 128, 256, 512, 1024, 2048).
Figure 4a illustrates that EF21-SGD able to reach a moderate tolerance in - 10 epochs.
'By 50%, 25% (and so on) we refer to a hatchsize, which is equals to [0.5N.J, [0.25N,] (and so on) for all clients 1.
17

---

Under review as a conference paper at ICLR 2022
mus TIOOTT, Top2
odo Top-2
69.. Top-2
2h Top-3
1.0
104
100
10"
10
100
end unth FMtt 906
1912 sith
R/gEAES 27u
1933 ko0 hos
10
wny with pittic 13
10
e991 with colice 12
10
10
1913 sitt
20
23
40
20
40
40
(a) Convergence in epochs.
Top-2
wda, Top-2
a9a, Top-2
phating, Top-3
3.00
1122420-2240
10
101
107
arzioo 1as 20%
andt-at 34u 1.5%
100
FF1--02 772-400.3 3bc 59%
1014
20
E72--48 2010 12
10
E/1/000 dnc 0.55
10
103030
50:05
150003
20050
20000
40003
103003
20005
30000
(C-+5)
#btaan (2
#bitam
(b) Convergence in terms the number bits sent from Clients to the Server by each client.
Figure 4: Comparison of EF21-SGD and EF21 with tuned stepsizes. By 1x, 2x, 4x (and on)
indicate that the stepsize was set to a multiple of the largest stepsize predicted by theory for EF21. By 50%, 25% (and so on) we refer to a batchsize, which is equals to [0.5N. [0.25N.] (and so on) for all clients i 1 ...
However, due to the accumulated variance introduced by SGD, estimator EF21-SGD is stuck at some accuracy level (see Figure 4b showing the usual behavior of the SGD observed in practice.
Experiment 5: On the effect of heavy ball momentum. In this experiment (see Figure 5) we show that for the majority of the considered datasets heavy ball acceleration used in EF21-HB (Alg. (6) improves the convergence of EF21 method. For every dataset (and correspondingly chosen parameter k) we tune momentum parameter 17 in EF21-HB by making grid search over all possible parameter values from 0.05 to 0.99 with the step 0.05. Finally, for our plots we pick r) E (0.05, 0.2, 0.25, 0.4, 0.9) since the first four values shows the best performance and r) = 0.9 is popular choice in practice.
For each parameter 7/ from the set
we perform a grid search of stepsize multiplier within the powers of 2:
{0.125, 0.5, 1, 2, 4, 16, 32, 64, 128, 256, 512, 1024, 2048).
Top-2
phieting,
164
10f
16P
16a
Craeel Hols q-
BE24IGIK OAG
Crasel Sal AG
10
10
1923 H8 Min
10
20:4
P921
1923 H8: Mrc
20:4
172 dr 8-13
072 48 Al gn0
100305
200000
10505 105050
20503 40300
10000
200m
trch
#hergh 15
#SRAN (C
Figure 5: Comparison of EF21-HB and EF21 with tuned parameters in terms of total number of bits sent from Clients to the Server divided by n. By 1 1x, 2x, 4x (and so on) we indicate that the stepsize was set to multiple of the largest stepsize predicted by theory for EF21 (see the Theorem
Experiments on a larger dataset. In these additional experiments, we test our methods on larger problem and dataset. The dimension of the dataset used in these experiments is d 20958. Each method is run for 500 epochs. In this case, we observe a similar behavior as in our previous experiments.
18

---

Under review as a conference paper at ICLR 2022
10a
real-sim, Top-210
10a
real-sim, Top-210
10
10
[[ff(x*)]
10
10-2
FF21..GD 25%
*
EF21-SGD: 64x: 25%
EF21-SGD:
10-4
10-4
EF21-SGD; 128k: 1.5%
EF21-SGD; 128x; 1.5%
EF2I-PAGE; 32x: 25%
EF21-PAGE; 32x: 25%
10-6
EF21-PAGE; 8x: 12.5%
10-6 6
EF21-PAGE; Bk: 12.5%
EF21-PAGE; 8k; 1.5%
EF21-PAGE; 8x: 1k:1.5. 1.5%
0
200
400
bits/n (C+5) 2
epochs
1e7
(a) Convergence in epochs.
(b) Convergence in terms of total number of bits sent from Clients to the Server divided by n.
Figure 6: Comparison of EF21-PAGE and EF21-SGI with tuned parameters. By 1x, , 2x, 4x (and so on) indicate that the stepsize set to a multiple of the largest stepsize predicted by theory for EF21. By 25%, 12.5% and 1.5% we refer to batchsizes equal [0.25NN]. [0.125N,] and [0.015N, for all clients 1, 21, where N; denotes the size of local dataset.
107
real-im, 1pp-100
10P
real-sim, 2pp-210
10a
realsim, Top-210
101
107
10a
[19100111
2722 d4
E723:
1721 S6x
10-1
1:22 Tepuitis ARR
1122 BC. 1ep-2
Tep-36655- CL
1/2200
120-22235
1121-6
10-2
2722 BO Tep555815--0 -D:
10'4
1/2166
120-5253p---0 -C) 32x
10"4
6521 dc 1ep-022005
communication rounds
1000
Maitsin (C-5))
1eb
abitimn 50-5-5-11
107
(a) Convergence in communica- (b) Convergence in terms total (c) Convergence terms of total numher of bits sent from Clients number of bits sent from Clients to the Server divided by n. of bits broadcasted from Server Clients divided by n..
tion rounds.
the Server plus the total number
Figure 7: Comparison of EF21-BC and EF21 with tuned stepsizes By 1x, 2x, 4x (and so on) we indicate that the stepsize was set to a multiple of the largest stepsize predicted by theory for EF21 (see the Theorem TT.
Comparison non-compressed methods. In addition, we compare EF21- and EF21-SGD to the baseline methods without compression: PAGE (Figure Bab and SGD (Figure 9a In these experiments, we observe that EF21-PAGE and EF21-SGD require much less information to transmit in order to achieve the same accuracy of the solution as the methods without compression (PAGE, SGD).
110071, Top
w8o, Top
190. To
shisingg Top
CF23-N6G Sibe 20% CFSIMAAC LOMS
CTA--MEE (nc 230 C2L446E PNGL
10a
10
133%
20
10-4
e17) nena 17.5%
10
NEE ax9ie 120%
1000000
200000
300003
100000 200620
330260
50000
100000
20000
40000
4bishh (C+S1
#bish
(C-+5)
(a) Convergence in terms of total number of bits sent from Clients to the Server divided by nt
Figure 8: Comparison of EF21-PAGE and PAGE with tuned parameters. By xx, 2x, 4x (and so on) we indicate that the stepsize was set to multiple of the largest stepsize predicted by theory for EF21. By 25% 12.5% and 1.5% we refer to batchsizes equal [0.25N.J. [0.125N.. and [0.015N,] for all clients 1, .n, where N, denotes the size of local dataset.
19

---

Under review as a conference paper at ICLR 2022
matroorm, Tpp2
Tap-2
a7a. Tep2
pluntigg Tpp-
100
10%
100
10
10
0723568 2008 20%
E726602 Jeteo 25h
0725566 LIBC 6%
E73600 10:25h
10-4
10
RER JOMA 25N.
10
NET ML
10
18200
20003
52000 4ERAN 5
100203
15050 DREEA (C.55)
20000
abisin S1
(a) Convergence in terms total number of bits sent from Clients to the Server divided by n.
Figure 9: Comparison of EF21-SGD and SGD with tuned parameters. By 1x, 2x, 4x (and so on) we indicate that the stepsize was set to a multiple the largest stepsize predicted by theory for EF21. By 25%, 12.5% and 1.5% we refer to batchsizes equal [0.25.N.J [0.125N:] and [0.015N:] for all clients = .,, where Nj denotes the size local dataset.
A.2 EXPERIMENTS WITH LEAST SQUARES
In this section, we conduct the experiments on a function satisfying the PL-condition (see Assump- tion 4). In particular, we consider the least squares problem:
min
f(z)
1 Σ
(a. 6.)2
ZER"
where a, R by E {-1,1} the training data. We the same datasets for the logistic regression problem.
Experiment: On the effect of heavy ball momentum in PL-setting, For PL-setting, EF21-HB also improves the convergence over EF21 for the majority of the datasets (see Figure Stepsize and momentum parameter 7) chosen using the same strategy for the logistic regression experiments (see section A.I.
mathesoms, Top-2
wfa, Top2
sña Tops2
thishing, Top-1
wrth dhe
eRTS 1844
entt diee eetl and came
erti wn zeipe park
erzi wel EVAAL go-
s/zontt ss. on ass
6/12-48 Jox 111.6
112246 Lik, or
E10
10:4
33
#bissi
0%
8.5
0.5
1.0
21,0000 1apasa
750000
5000
10005
15000
mus 1100 Top
W8b, Top
193, Tep
shiching, Top
20
072
E2iea SEIC
OF Lapee
1.0
30P
C22e end)
10R
10
10
10-1
10
10
0.5
255
0.0
1.5
250050 500003
750000
5000
10035
15000
obsigh (C+51
1e5
#bitu (C+5)
#atuin (C
#bibbh (C-+5
Figure 10: Comparison of EF21-HB and EF21 with tuned parameters in terms of total number of bits sent from Clients to the Server divided by n. By 1 1x, 2x, 4x (and so on) we indicate that the stepsize was set to multiple of the largest stepsize predicted by theory for EF21 (see the Theorem 2
A.3 DEEP LEARNING EXPERIMENTS
In this experiment, the exact/full gradient (2*+11) in the algorithm EF21-HB is replaced by its stochastic estimator (we later refer to this method as EF21-SGD-HD). We compare the resulting method with some existing baselines on a deep learning multi-class image classification task. In particular, compare EF21-SGD-HD method to SGD EF-SGD-HET EF21-SGD
SEF21+SGDD-HB is the method obtained from EF21-SGD-HB via replacing EF21 by EF21 + compressor "EF-SGD-HB is the method obtained from EF21-SGD FFB1-SGD-HB via replacing EF21 by EF compressor
20

---

Under review as a conference paper at ICLR 2022
and EF-SGD on the problem of training R8 (He al. 2016) model CIFAR-10 Krizhevsky
ct al. 2009) dataset. For more details about the EF21+ and EF type methods and their applications in deep learning we refer reader to (Richtárik et al. 2021). We implement the algorithms in PyTorch (Paszke et al. 2019) and run the experiments on a single GPU NVIDIA GeForce RTX 2080 Ti. The dataset split into 8 equal parts. Total train set size for CIFAR-10 is 50,000. The test set for evaluation has 10,000 data points. The train set is split into batches of size = 32. The first seven workers own an equal number of batches of data, while the last worker gets the rest. In our experiments, we fix k R 0.05d, = 32 and momentum parameter = 0.9 As it is usually done in deep learning applications, stochastic gradients are generated via so-called "shuffle once" strategy, i.e., workers randomly shuffle their datasets and then select minibatches using the obtained order (Bottou 2009; 2012, Mishchenko al., 2020). tune the stepsize 7 within range (0.0625, 0. 125, 0.25, 0.5, } and for each method we individually chose the one giving the highest accuracy score on test. For momentum methods, the best stepsize was 0.5, whereas for the non-momentum ones it was 0.125.
The experiments show (see Figure M that the train loss for momentum methods decreases slower than for the non-momentum ones, whereas for the test loss situation is the opposite. Finally, momentum methods show a considerable improvement in the accuracy score on the test set over the existing EF21-SGD and EF-SGD.
EP FF-33
Talk
10"
oxteorccainn mesds
commariatiio neEds
Figure 11: Comparison of EF-SGD and EF21-SGD with EF-SGD-HB, EF21-SGD-HB, and EF21+- SGD-HB with tuned stepsizes applied train ResNet18 CIFARIO.
'Here, is the number of model parameters, For ResNet18, d 11,511,784.
21

---

Under review as a conference paper at ICLR 2022
EF21
EF21-SGD
R ||_| 11² 8 = =((a)) finf
EF21-PP
R | x¹ 2| 8º (x²) finf
EF21-PAGE
P [V)((²)) - v/ll" V1
||0 - 9/ 1
EF21-BC
Pt 10 Vfi(2') || Rt
x x¹
, f(xt)( finf
EF21-HB
R' (1 11-1) 11)2 ge+1 xd 8 = f(x))
fint
R² | 11-1-x'
x² || (xx) = f(x) (z), 8¹ (xxx)) -
EF21-Prox
(z) 1 (x prox (x ( vVf()))
Table 6: Summary of frequently used notations in the proofs.
B NOTATIONS AND ASSUMPTIONS
We now introduce an additional assumption, which enables us to obtain faster linear convergence result different settings.
Assumption 4 (ollykk-oojsiewiizz) There exists μ > 0 such that f(x) f(x*) S 1 2p [+()] for all x E R2,, where x arg min f.
Table summarizes the most frequently used notations in our analysis. Additionally, we comment
the main quantities here. We define 5' f(x²) f R del || - =²1| In the analysis of EF21- HB, it is useful to adapt this notation to Re (1 1)) ||++] - ==11|= where {= (=")220 is the sequence
of virtual iterates introduced in Section H We denote G del [[Vf('z') Il G def
1 E G
following Richtárik et al. (0021), where g is EF21 estimator node i. Throughout the paper 2 Di=1 I.J where L; is smoothness constant for fa()), i = 1.....7 (see Assumption
Iff additionally, Assumption holds, then ginl can he replaced by f(x") for xt arg min gg3d f(x).
22

---

Under review as a conference paper at ICLR 2022
C
EF21
For completeness, we provide here the detailed proofs for EF21 (Richtárik et al. 2021).
Algorithm 1 EF21
1: Input: starting point x0 R gf E R for = 1....,n (known by nodes); gd = 1 -i== 9
(known by master); learning rate Y
2: for = 0,1,2.....
do
3:
Master computes x = x' gg and broadcasts s1+1 all nodes
4: for all nodes i = 1, 1,..., in parallel do
5:
Compress & - C(V (xx g and send of to the master
6: Update local state of +1 93
7: end for
1 8: Master computes = n Li=1
Σ
+1 via g g' + of
9:
end for
Lemma 1. Let be a contractive compressor, then for all 1,....
E G S (1 8)
G
3L || x²11²] and
(13)
E + - (1 - O)L [ 3 |||(41-= ==1]]
(14)
where 0 dd (1 s),
B def (1 a) (1 (1+
for any >> 0.
Proof. Define W del (oi.....
x² x +1+ then
IP [G
E
E
G+++1 W|]]
E
E
11 +1 - [ [
E
E
|lot
+ +C(( - - v)(( [w]]]
(1 a)
/ - s211"]
(1 ()-a) B) [((('') s011
+(1-a)
| f. fx(
(15)
(4)
(1- B3 [/(''' 2119
+(1 a) (1 - 17 |||00t1 - =0'133
(i81) (1 (1- B)B || - el| + BLŞE || x² [13]]
where (i) follows by Young's inequality (18). (ii holds by Assumption D and (iei) we apply the
definition of 0 and 3. Averaging the above incqualities over I,..., n, obtain (14.
C.1 CONVERGENCE FOR GENERAL NON-CONVEX FUNCTIONS
Theorem 1. Let Assumption ! hold, and let the stepsize in Algorithm 7 be set as
0<75 L+ 1
(16)
Fix 2 1. and let T be chosen from the iterates ,0,x',...,2"
T- uniformly at random. Then
E [[| 2 (f(x2)
find
[
(17)
IT
0T
23

---

Under review as a conference paper at ICLR 2022
where L = / 13 - 1 (1- ss. B (1- for any s > O.
Proof.
According to our notation, for Algorithm
Rt = | x² | By Lemma have
E [
(1-0)E[G")
LL [R']
(18)
Next, using Lemma and Jensen's inequality (19).
we obtain the bound
1
f(x S f(z') - 2/ 2
[f(('')1
L
Rd
+
(of - Vfi(z'))
27
2
2
==1
S f(x²) - 2 [f((")))
L
R² + 7
E
n
11
vi(xt\)1
22
2
n
= s(x') - |(({)))|
R² +
c
(19)
27
2
Subtracting finl from both sides of the above inequality, taking expectation and using the notation 8' = f(x") fint, we get
E [ <
[
E
IE [[
- ( 27
1/2 2
E
R
+ 2
[G
(20)
2
Then by adding (20
with a 7
multiple of 18 we obtain
28
E [8+
+ 7 10 [++
20
E [0']
E
|
11]]
2
1
L
E
[
+
2B
2
[G')
+
7
(BL [R'] + (1 B)L [G7]]
20
= E [o']
+ 2
[G']
- - 3E ||| ff ||
20
1
L
7 3ī?
E [R'
22
2
28
< E
50
+
E
[V[()')]
20
The last inequality follows from the bound 722 9 Ly < 1, which holds because of Lemma 15 and our assumption on the stepsize. By summing up incqualities for t = O..... T - 1, we get
0 < E
8T
GT
S 50
7 E
G
7 2 L=0
E
[[
20
20
Multiplying both sides by
2 7T
after rearranging we get
Σ B [1 t=
280 TT
E [
+
8T
It remains to notice that the left hand side can be interpreted as E from r x1 ,..., -1 uniformly random.
where &7 is chosen
Corollary 2. Let assumptions of Theorem holdd
df V)i(z"),
,,... n
= (L+ L.
24

---

Under review as a conference paper at ICLR 2022
Then, after T Vterations/coommniictttonn rounds of EF21 we have E
[f((")) S It requires
L
T # O
aE²
iterations/commnnicaiions rounds/gradint computations at each node, where i / E L3
8 f(x)) - f
Proof. Since of vi(x'),, ,,..., we have G 0 and by Theorem
(3)
28
(6i)
28
3
(18))
20
L _ -1))
#grad
T
-
L
L
L +
7E2
22
8
E²
a
25
2L
(1n)
25
L
21
6L6
L +
E²
E²
a
aE
where in (i) is due to the rate (17) given by Theorem ! In two (ii) we plug in the stepsize, in (tis)
we use Lemma 17 and (iv) follows by the inequalities a - 1, and L < L.
C.2 CONVERGENCE UNDER SHLYAK-LOIASIEWIEE CONDITION
Theorem 2. Let Assumptions I and hold, and let the stepsize in Algorithm be set as
0 S min {
23
(21)
2jz
Let tf def f(x²) - f(x²) )+ + / G² Then for any
2 0, we have
E 1 2 1 (1 - - E [w]]]
(22)
where L = / Σn L3 0= 1 a1 + s). B = -
(1-aa a) (1+ for any s >> 0.
Proof. We proceed as in the previous proof, but use the PL inequality, subtract f(x*) from both sides of (19) and utilize the notation 5' fxx') f(x))
8++1 S 8 2 [
1
L
R¹
G²
2r
2
S 8¹ 7 (f(x*) - -((x))
1
L
R²
2 G 2
27
2
(1 (1-74)8
(
1
L
R¹
G 2
2y
2
Take expectation on both sides of the above inequality and add it with 3/2 multiple of (88) then
E 1 + g < (1 (1-7w4 =E) [8]]
R'
3
[
27
+ (1 (1- 8) [G'] + BiPE [RT]
= (1 - >4)1E |04| + 3/2 (1 1
E |G]
2
L 3i29
E [e'|
27
2
0
25

---

Under review as a conference paper at ICLR 2022
Note that our assumption on the stepsize implies that S 7/ and 27
2 0. The
70 22002 0 yI. - 1, which holds because of Lemma 15 and
last inequality follows from the bound our assumption on the stepsize. Thus,
8 2 G
(1 wu) 8a c²)
0
S
remains to unroll the recurrence.
Corollary 3. Let assumptions of Theorem hold,
Le Vfi(z),
i= ,
-1
23
= min
( Tv
2/z
Then, after T iterationscommuunictttonn rounds EF21 we have E ((("))_((**)) Se. It requires
T
80
{))
T= #grad =
log ap
(23)
ferratios/communictiooss rounds/gradint compulations at each node, where T, = V - 1
80 = -=x=))x--- fin...
Proof. Notice that
min { 1
(112))
28
-1
0
2
-1
4
min
L +
LV2
0
2/
a
-1
2v2L
min
p
L
4
a
(1 + 202)L
min
a
4
opp
min
(1+ 2
app
min
4L 4
4L
where in (i) apply Lemma 17 and plug in 0 = 1 /1 according to Lemma 17
(ii) follows
by / a 0/2, (1i1) follows by the inequalities a < 1, and T. T..
Let o Vft(x"), i 1....,n n, then G = 0. Thus using
22 and the above computations, we
arrive at
log 80
1
80
4T.
5
#grad
T<
log
log
log (1 7/4)
7/44
E
at
E
where (i) due to 122
26

---

Under review as a conference paper at ICLR 2022
D STOCHASTIC GRADIENTS
In this section, we study the extension of EF21 to the case when stochastic gradients are used instead of full gradients.
Algorithm 2 EF21-SGD
1: Input: starting point 20 E RR; o E Rd (known by nodes); g 1 Σ 1==1 of (known by master); learning rate 7 > 0
2:
for 0,1,
- do
3:
Master computes x++1 = x' - ng and broadcasts x1+1 to all nodes
4:
for all nodes i 1. ,,..., in parallel do
5:
Compute a stochastic gradient 9: (x(+1)= = + Σj= Vee (x*+1)
6:
Compress & = C(p (1++)) gt) and send of to the master
7: Update local state +1 g + c
8: end for
9: Master computes g n Ei= gi 1+1 via viag*th gt g6 1
10:
end for
Lemma 2. Let Assumptions 7 and 2 hold. Then for all t 2 0 and all constants P.v > 0 EF21-SGD
satisfies
E [+++]] S (1- (1-0)E [ + T.21. || - =011"]]
+ABBE [
piml| + C.32
(24)
where 0
1 - (1 - (1 + p) + v).
31
ddf 2 - a) + p) (1+
82
def
211 a) (1 + p) (1+ + (1+ À max:=1....
L
C Č= 2(B,+L,(B,-I) (fint - f Ci
T,
Proof. For all p.v > 0 we have
E [
E
9
++1 ( |?]
||| (0)(x -96 (0)(='t)) - [3 -
(1+ + p)E
+ 1 2)
E [1o((a(t2) - (5((a(t2)11
p
|1ot - [11 ||-]]
(1 a) (1 +
+ (1+ 1) E [10g(art2) - (s((a(t))1
p
$ (1 (1+ (1 + F)E |lot - v
- a1 p)
(1+ 1
/fi(ct++)) - (a
//
-) p)
[ -
) ||V
1+ E
- - |/]
<
(1 B) G
+ 81 L |1 - ==]""]
+
[10:(0
- V (1((o
27

---

Under review as a conference paper at ICLR 2022
where we introduced 0 def 1 (1 -0-
(1 (1 + p)(1 + v). 31 def 2(1 a1 + p) (1+
B2 _ (1 a) (1 + p) (1 + ;) + (.) Next we use independence of VSeg, (2"), variance
decomposition, and (9) estimate the last term:
|| E [ = (1- ور [ + B 1
2-11"]
B2 Tr E
Sey, (1'+1)- /
= (1- 1)ル [ + B من || 12 - 20'1"]]
+ - E V (a ( ||]]
- E || |
(1 (1- C + L |||AA|-11111 =-11²]
-
82 [f((l=tt)
--an + Ba(B:
E [|
C.B2
T
T2
Ti
(1 0) E G + L || - -11001-2001 x2(1[]]
2(A: + L. - 1)),32 E [ - paal] +
C₂
Averaging the obtained inequality for i 1,... ,11 get
E G
(1 (1E [G]] + | T. || - x6 [1²]]
2(A, + I,(B, - -1)) E [f(( [pau] +
C,3²
TB
TB
S (1 وز [a] + L [||2t1] 1 =3/11"]
2(A, + L.(B, - 1))822 [f((xt+1)) - ppine)
T2.
82
2(AA + Li - 1)) (sinf - ((art) + Ci
Ti
To
t=1
(1
|
+ 3 [| - (g01)=x01(+] A32 [f(x - -lnt]] + C
D.1 CONVERGENCE FOR GENERAL NON-CONVER FUNCTIONS
Theorem 3. Let Assumptions I Aadd] 2 hold, and let the stepsize in Algorithm 2 be set as
31 0
0 OC7S
T T T
(25)
where L = V L2, 0 del 1 (1 - a) (1 + p) + v). B, del 2 a1 (1 p1 b), and
P.v > 0 are some positive numbers. Assume that batchsizes ,I,-..,7e are such that 2u,ez
1, where
2#
Ā max;= L(A,+L,(B,DD) and 322 def 2 - a:) (1 p) (1 :) + (1+ )
:)) Fix T > 1 and
T; let f be chosen from the iterates x. x1 _T with followinn probabilities:
AAB2
T
Prob {3"==""=""
= x'}
W W
Wi
(1
1
WT
Wt-
20
t=
28

---

Under review as a conference paper at ICLR 2022
Then
[l }19] 3 2(f(x") -fint)
E G
C
E
+
+
(26)
7T - 20 (122d/²2
1
20
20
where Ö = 2(ActL((B,-I)) ( s + Ci
Proof. We notice that inequality 20 holds for EF21-SGD as well, i.c., we have
E [
<
E
[8
E 2
|
L
E
[e"
+
E
[
2
Summing up the above inequality with
20 multiple of 24p. derive
E +
2 0
E
8
L
RC
7 R
[
20
2
27
2
2/ (1 -)E [G'] + 3, [R']
28
2A
? A [5+
+ 7 C
20
20
7A32 2
E
[8++1]
+ +
8"
G
||[
2.8
20
20
2
20
1
L
73,1²
E [R']
27
2
20
25
7AB3g
[
+
8
+
G
|V
+ TB2
20
20
2
20
where 1 def (1 a) (1 p)(1 v),
31 del 2(1-a) (1 p) (1 +) B2 def 2 a1
p) (1+ (1 + ) and p.v are some positive numbers. Next, we rearrange the terms
[|(
2
E
8 +
G² - 1 __223
E [
- -- [G+t]]
7
20
20
20
θ
2
E
8
Gt
1
7AB22
E 8c-1
2 E [
7
20
20
20
C32
+
θ
sum up the obtained inequalities for = 0.1...... T with weights wi/Wr, and use the definition of T
W.
WR
K
2
7 ct
g1+1 + - [G-+i]
W.E
8
+
w E
WT
20
20
t=0
0
E [G)]
W
9Wr
θ
29

---

Under review as a conference paper at ICLR 2022
Finally, notice
T WT =
7A32
T
W 2 (T++)
min (=0......,
Wi > T 1
20
0=0
that finishes the proof.
Corollary 4. Let assumptions of Theorem
hold, p = 0/2, v = 4/4,
1
7
L L+LV
4
2T (Ar + L.(B, - 1)) (A, L,(B, 1)) 32 0ime
40,,2
}
T
max
1,
0
δe2
De2
168
8E (
T
max
YE²
E²
where 6inf
pinl
fial 80 f(x") fial, Then, after T iterations of EF21-SGD have
E
S =2. It requires
Lo + +E Go)
T=
ax
iteratinsscommmnniications rounds,
#grad;
T;T
(I.0 + + [GO]
(A,(00 + 5pme) + Ci
L5 + E Go]
o
as²
[L8 - E ) [G
a² + L)
stochastic oracle calls for worker i, and
n
#grad
T
n
1.80
E
L88 + B [G
(A. + giul) + C.
0
as
adgl
==1
(L80 [GO] (G,A), [G0]
a²(aL L)ea
stochastic oracle calls per worker on average, where A, = A; Li(B:-1)
Proof. The given choice of T; ensures that (1-
7432 26
T = (1) and ÖB S 5/2. Next, the choice
of T ensures that the right-hand side of 26) is smaller than Finally, after simple computation get the expression for T:P.
Corollary 5. Consider the setting described in Example P 0/2, V a/4,
Let assumptions of Theorem hold,
4 82
166
8IE
[G9]
L + I
T
max
2
T
max
762
0g
30

---

Under review as a conference paper at ICLR 2022
where = f(x))((()))))))) - fint. Then, after T iterations of EF21-SGD we have E [|] S requires
Lo c
T=0
iterationscoommenicattoss rounds,
L80 + (")
(iD +B (o o3
# #grad, T;
aE²
a²
stochastic oracle calls for worker i, and
7.80 + +
[
+ F 0² a²
#grad
TT=
aE
stochastic oracle calls per worker average, where o² Corollary 6. Consider the setting described in Example p= 0/2, 0/4,
Li=1 oZ.
Let assumptions of Theorem 3
hold,
7
L
L
B
2T
L
8I,
SL, B2
}]
max
1.
8imt.
0e2
0=
166
[
T
max
762
0g2
where 5iul finl
finl 8 -x(x)) pint I
mi Σ/=1 Lzg. A
1
Σド (s sial)
mi
Then, after T iterations of EF21-SGD we have E
||>s(>>))*
S 82. It requires
== L6
+ G
ag²
iteration/communicatiions rounds,
#grad, T.T
(I80 + +E(Go) (I,(0" + d:nf) + L,A)"()
o L8 + +E Go)
(100 a
aget
(T.0 + E [ L [O)]
a? + L)
stochastic oracle calls for worker i, and
#grad
T
i=1
i80
+ E
[.50
+ [GO]
(I,(60) dinf) T,A
0
aEa
1
3
[.80 E [
I,E Go)
n
a²
L)ea
stochastic oracle calls per worker average.
31

---

Under review as a conference paper at ICLR 2022
D.2 CONVERGENCE UNDER POLYAK- EOJASIEWICZ CONDITION
Theorem 4. Let Assumptions 7
2 and
hold, and let the stepsize in Algorithm 2 be set as
2
0
0 O<YS min
minm L I 0
(27)
2p
where T, = V - 122 0 def 1 (1 o:) (1 + p) + 1). B def 2 - oi) + p) p) (1+ + b), and
P.v > 0 are some positive numbers. Assume that batchsizes Ti.....TT are such that 2A3²
0 - y
where À = max 2(A,+,,(B-1)) and B2 def 2(1 a) (1 p) (1+ () + (1 2). Then for all T F21
E
8T + 7 1
S (1
7u T E
80
G
4 CB
(28)
2
μu
where ==
2
2(B,+L,(B,-II)
(flut= f!ul)
Ci 7z
+
n1
To
Proof. We notice that inequality (20) holds for EF21-SGD as well, i.e., we have
E [
S E [oa E [|V
1
E
[2']
+ 2
E[[
27
2
(1 - MF [o*] - 27
L
[
+ 3 [G]]
2
Summing up the above inequality with a 3 multiple of (24).
we derive
E g++1 + [
< (1 - X4) 600
1
L
E
R2
+ 2
27
2
21 0)E [G]] + 7
- [R*]
+ 0
0
2 AB [0+ + 2
0
AA3
0
E [0+ + (1 - 7/ E [0']
+
1 1
E
7
G
+
7 7
2
0
L 3 7.2
E [R']
27
2 θ
7A3
E [04+1]
+ (1 - 11)
8"
+ 2 cd
+ 1..3..
0
0
where θ def (1 a)) (1 + p)(1 + v). def 2 - a) (1 + p) (1 + 1). B2 def 2(1
p) (1+ + (1+ + ) and p,v > are some positive numbers. Next, we rearrange the terms
TA32
AA32 θ
E g++1 + c
ge+1 + I c
0
5
(1 - YHIIE
8º +
Gd
+
and divide both sides of the inequality by
1
E g1-1 + 7 c
1 7/4
E
8²
+
7 Gt
CB
θ
7,00
θ
0
1
Adde
0
A,8
(1 74)
1 +
E
8t
+
c
+
+1
18.2.
0
0
0
32

---

Under review as a conference paper at ICLR 2022
Since
240² < and 7 S A. we have 0
E 80 2 g
(1 7p1) (1 (1+
7/4
8
2 G¹
2y 03
2
0
0
(1 7/
8 2 c
27 73.
0
Unrolling the recurrence, get
T-1
E 8 7 GT
$ (1-
7/4 T
E
8 + 6
OB
Σ
(1
)
2
(1-
7/
E
8 + Go
+ 27 0
Σ
1
7/
2
2
t=
(1-
7/
E
8 + 0o
+ 10
83
2
that finishes the proof.
Corollary 7. Let assumptions of Theorem 4 hold, p 0/2, v 0/4
0
min
L T 81 24
8 (A + L,(B,
1)) 32 64 64 L,(B, 1)) B2 siml
32C,,3
T
max
1,
Ōep
dep
28
27
θE 1
=
ln
+
where 8inf
fint
fint 8
f(x²) -fnnt Then, after T iterations of EF21-SGD have
E
[f(x²)
< fin[]
It requires
Σ
80
2G
T=0
In
E
LE
teeratons/communicctiinss rounds,
#grad, T.T
((T.
[AAlE + Simt) + +c:))
T.
50
2G
O
In
pao
1RadE
Tee
stochastic oracle calls for worker i, and
1
#grad
T
n 1=1
[
Σ
i Aslle + )/n))+0,
80
2G
0
In
+ E
pace
12a3E
I.c
stochastic oracle calls per worker on average, where A, = A, + Li - 11)
Proof. The given choice of т; ensures that 3 2
2 <
P and 48/2/200 < f/2. Next, the choice of T
ensures that the right-hand side of (28) is smaller than E. Finally, after simple computation we get the expression for T..
33

---

Under review as a conference paper at ICLR 2022
Corollary 8. Consider the setting described in Example 7 = 2/2, V 8/4,
Let assumptions of Theorem hold,
0
32
2
25
)
min
max 1,
T =
In
+ EF
L L
21
deu
7
0E
where 50 = f(x²) - fint. Then, after T iterations of EF21-SGD we have E [f(xt) (((x))=a pint] S c. It requires
T.
10
[2G
T=0
In
E
uaa
Le
iteraiion/communicationn rounds,
#
TiT
o
((1L
L
Lo,
8"
2G
In
jia
12:08e
Le
stochastic oracle calls for worker and
#grad
nf
i=1
o
((1
E
Loo pra3z
8
2G
In
E
Ha
Le
stochastic oracle calls per worker on average, where o² Corollary 9. Consider the setting described in Example 8/2, v = 4/4,
>
Let assumptions of Theorem hold,
1
θ
7 min
2p
+
SL, 32
64L,
64L; inf 32 θep
gint
max
11
280
G2
1)
T
+
E
7/44
OE
where 8inf = fint
fint 8
f(x))
fint, L;
1.
En= Lij, A
1 E (finf finf).
mi
mi
Then, after T iterations of EF21-SGD we have E
[f(x²)
finl] S E. It requires
L
80
[2G
T= 0
ln
E
-
Le
iernatins/communicttionn rounds,
#grad; = T.
((L+
I
LL (E +
8imt + Ainf)
80
2G
o
In
E
pa
1RO3E
E
Te
stochastic oracle calls for worker and
1
#grad
T
n
1
LT
(8
+
ginf + Inf)
/ 80
2G
o
In
E
p.ac
n
3203E
Le
stochastic oracle calls per worker average.
34

---

Under review as a conference paper at ICLR 2022
E VARIANCE REDUCTION
In this part, we modify the EF21 framework to better handle finite-sum problems with smooth summands. Unlike the online/streaming case where SGD has the optimal complexity (without additional assumption on the smoothness of stochastic trajectories) (Arjevani et al. 2019), in the finite sum regime, it is well-known that one hope for convergence the exact stationary point rather than its neighborhood. To achieve this, variance reduction techniques are instrumental. One approach apply PAGE-estimator (Li al., (021) instead of random minibatch applied in SGD. Note that PAGE has optimal complexity for nonconvex problems of the form 3 With Corollary 10 we illustrate that this O (m + vm/e²) complexity is recovered for our Algorithm when no compression
is applied and n2 =
We show how to combine PAGE estimator with EF21 mechanism and call the new method EF21- PAGE. At each step of EF21-PAGE, clients (nodes) either compute (with probability p) full gradients or use recursive estimator i + 7: jeer fy - fiy (z")) (with probability 1 - p). Then each client applics a Markov compressor/EF21 1atsssor//EE1-stmmattoooo -estimator and sends the result to the master node. Typically the number of data points m is large, and p l/m. As a result, computation of full gradients rarely happens during optimization procedure, on average, only once in every m iterations.
Notice that unlike VR-MARINA (Gorbunov al. 2021), which is state-of-the-an distributed optimization method designed specifically for unbiased compressors and which also uses PAGE- estimator, EF21-PAGE does not require the communication of full (not compressed) vectors at all. This an important property of the algorithm since, in some distributed networks, and especially when very large, as is the case in modern over- per--arameterized deep learning. full vector communication is prohibitive. However, unlike the rate of VR-MARINA, the rate of EF21-PAGE does not improve with the growth of n. This not a flaw of our method, but rather an inevitable drawback of the distributed methods that use biased compressions only.
Notations for this section. In this section, we use the following additional notations P der (x") - =f1?, p def E P.. V def ||o - gfll V def n Σ Vt, where of PAGE n
estimator. Recall that Gt def + G. o def [Vf((=)) - Ifll
The main idea of the analysis in this section to split the error two parts G 2P 2V, and bound them separetely.
Algorithm 3 EF21-PAGE
1: Input: starting point 2 E R::; g. of E Rd for 1,..., (known by nodes); g" = > 9f
(known by master); learning rate y > 0: probabilities pt E (0,1]; batch-sizes S T S m
2: for t = 0,1, T 1 do
3: Master computes x ++1 = gg
4: for all nodes i 1, , in parallel do
5:
Sample by ~ Be(p,)
6:
If b sample minibatch of data samples I with [7]] T if bj = 1, if by =
(x(+1) U
7:
[+1
1 Σ (z)((x
- fig()"))
jEī
8: Compress oi C(e
g and send et to the master c
9: Update local state g of
10: end for
Master computes g 1 g 4+1 via gag = o6 + E
12:
end for
Output: दर chosen uniformly from {a* hee(T)
Lemma 3. Let Assumption
hold, and let o/+1 be PAGE estimator; i. e. for bj ~ Be(pi)
(11 Σ (Viig -
if
b 1,
11
if
b = 0,
(29)
jen
35

---

Under review as a conference paper at ICLR 2022
for all i 1,...,,... n, t. 2 0. Then
E [
S (1
Pmin )L [
+ C
||
(30)
where -= -i=1
(1-4)) "
Pmin m Pa.
Proof.
E
p
=
E [1 41
= (1- P.)
of
+
1
- -
(
- (
Ti JEI;
= (1 PA)
0/ - v/((=') + A Vfi(z(t1)= [
0f v + A - 1
(1 PA)
(1 P.)
[10| Vf(('') }|]] (11- - PB)
|| A $11
(8))
(1 P:) [P]]]
(1-pi) p:)
(1-
E - 2²
-114441=0'13 101
Ti
< Pmin E [P:]] + (1 - p.)
||| - x ==]]]]]
(31)
where equality (i) holds because E A A " x11 ug = 0, and (ii) holds by Assumption
It remains average the above inequality over i ,,...,
Lemma 4. Let Assumptions and hold, let o/+1 be a PAGE estimator, i. e. for bf Be(p;) and for all i = 1...., 120 0
(1( of Σ -
if b 1,
[+1
if by 0,
(32)
JELf
and let g, g be EF21 estimator; i.
g: [+1 of + C(u ++ gi), 9f = C (v?)
(33)
for all i -L,...,n,. n, n,, 22 Then
E [vtt]]] (1 OOE V*] 23 E [P*] + (2T2 8 + E²) E
(34)
where ī 1 In Em=
(1-p:)
7 Paaxx = max;=1 Pi. Pr. 1- 1-11- B = (1-a) (1+
for any 8 >
Proof. Following the steps in proof of Lemma I but with ((((++11) and V Vf((t) being substituted
by their estimators of and of. we end up with an analogue of (15)
E 11 41 - of 411 < (1 - 0)E loa o
+ 3E
10
++ - -
(35)
36

---

Under review as a conference paper at ICLR 2022
where A == 1 (1 a1 + s), 8 = (1- a) (1 + 1 for any 0. Then
E [
E ||of
11
(1 O
|| - [
+ 3I
|| ++1 - -ill
0)E
| 1
+ JI
E || - 2/l1 1
10 x² =
(1 0)
[v]] + 3p,
[|o| -
[((
+ - -P.)EE 7h
Σ -
JEZŞ
(1 R) [V]] + 3p,1E [|ug - [ |1] + +13 -P:)RE ||
(1 0)R [V]
2.3p B |111 - V/(aa")1
31:(1 pz) || 2
+23 E
||
(1 0) [
2 E [P:] + 2 |||:1|
+ BB1 PE)
||=:|]]]
(188)
8) [V]]]
2,3p.E [P:] + 8(pp; + PP:)E |,:1
+ pt) F | |
((v)
(1- O)E [V. + +33p.B
[P:] + 3(1 + pt) [| ---1--x-
x²" =011²]
+.3 (1 - pi)C3
|| (
E
T
(1 - (1-Pi)
< (1-0)E [V] + 2.3
[P]] + + 2L, +
EE
| - 2²113]
where in (i) use the definition of PAGE estimator (32) (ti) applies
[19) with s 1, (zii) is due to bias-variance decomposition (23). (iv) makes use of Assumptions and 3 and the last step is due to p; I 1, Pi S Pmax
It remains to average the above inequality over i = 1...., n.
E. CONVERGENCE FOR GENERAL
FUNCTIONS
Theorem 5. Let Assumptions 7 and
3 hold, and let the stepsize in Algorithm 3 be set as
48 12 L
33 Pinax
0<7S L+
2
T2
(36)
Punin
Punn
Fix T 2 and let aff be chosen from the iterates x0 s
,..., T- uniformly random. Then
2
E
(37)
"
where ye def f(x²) - -fint + zVve
7 1
28panin B
pt, Pmax m1Xx I..... Pi. Pmii
Pmin
min;=1..... Ps, L. = / V L3 0 = 1 - (1
a1 + 5), B = (1 - a) (1+5-1) for any
> 0.
37

---

Under review as a conference paper at ICLR 2022
Proof. We apply Lemma and split the error llof
V=((=')|l in two parts
f(att1) $ f(x²) ạ 2 (
L
R ? 119
11-0--VV60 -Vf(2')11
27
2
s ((x) 2/4 |V[x'1]1
1 L
R²
27
2
+7|19* - 1'1 + >BB
[ll0t
V
(a>)))1
s f(x²) - 2 V f(x ||
(2 2
Rt
+y 1 Σ l1o 11
+ Σ ||0 \s(()')11
s(x) - "((
(
L
R² + 7 + 7p
(38)
27
2
where we used notation R² |1:g011 = || - x² and applied 118) and (19
Subtracting finl from both sides of the above inequality, taking expectation and using the notation 5r fxx pint we get
[
E [89
I [[V][>)))] 2
L
[RR
+ + [V] + yE [P'] (39)
27
2
Further, Lemma and
provide the recursive bounds for the last two terms of (39
E [ptt]]
(1 Punin )E [Pe] + [Ra)
(40)
[v+t]] <
(1 O)E V* + 3 2T. + E2) E [Re] + 2.3 E [pt)
(2T.2
(41)
Adding 39) with a 3 multiple of (41
we obtain
E [8++]] [vett] s
E 1001 J (39)
1
2
E
[ + > [ve]
27
+E [M]] 2 ((1 (1- 0) E
V
+ Ar + (C((P))
S
8' + 3 [Vo] - 3E ||
1
L
7A
[2]]
27
2
0
+y g E [P
where we denote A def 3 (2ī² + (2)
C def 2,3pmaxx
Then adding the above inequality with Panin
(1 + 4)
multiple of 44
get
38

---

Under review as a conference paper at ICLR 2022
B [
E [
?
(1+g))
C'
E [P**]
0
Pmin
s
8" + B [y - w
V (+')))
L
74
R²a
2
27
2
0
1+ C E Pd
7
1+ 8) (
(1- Pmin (1- [Pi]
2 (R')
Pmin
s
E
8
?
E
['
+
1
C
E
pd
- - [
Pwin
0
1
L
74
C
[1
L
E [R*]
2y
Puin
0
E
[6
?
E
Vf
(z9)
L
74
(1+
22 E R2
(42)
27
Puni
The coefficient in front of [R** simplifies after substitution by A and C'
24
(1+ -
2 (
23 0
1
33
Pmax
+
Pmin
0
Pmin
Pmin
Thus by Lemma 15 and the stepsize choice
-1
48 0
38 Pmax
1
0 Oc7s L+
12
+2
C2
(43)
Pmin
Pmin
the last term
42 is not positive. By summing up inequalities for t= O....., 1, we get
[[V
E
2 Multiplying both sides by क and rearranging we get
T-1
[+
2E [T0]
7T
||V)())) [?]. where 47 is chosen
remains to notice that the left hand side can be interpreted as E from z ,..,, x -1 uniformly at random.
Corollary 10. Let assumptions of Theorem 5 hold.
of 9f
vV((1'),
I,...; n,,
4,3
3,3 Pmaxx
γ L+
V 0
ī2 +
Az
Puin
Punin
i= 1 1,...,n.
T, m
Then, after T iieratios/coommuiicationn rounds of EF21-PAGE we have E requires
Vs(
|||
$ <
39

---

Under review as a conference paper at ICLR 2022
[ E)00 age2
Mimase E80 8
T=0
Pmax
Pmin
iteration/commmnicationss rounds,
ggrad = o 0mm +
Ti(L + Z)8"
Ti my C80
Pmax Pmin
ac
62
stochastic oracle calls for worker i, and
T(L + E)80
T M E80
#grad O
Pmaxx
aE2
Pinin
stochastic oracle calls per worker average. where E To max4=1..... ma Pmax = max Pt. Pmin = mill==1..... Pr.
1 1 my Mmax
Proof. Notice that by Lemma 17 we have
++
43 1
0
+
33 Pmax
Pmin
1 Pmin
C
L+
V
a²
16
2 +2
Pmax a²
12
Pmin
Pmin
C
24
Pmnax
2
L +
I +
C
a²
Puin
Puin
L + a
L
24
a V Pmiu
Pmix
C+
V2
E
v
Punin
5 L
224
V
|Puax C
+
v2.
C
Pmii
VPmin
IA
5
Piax
[I++ C +
V2 Σ
Punin
Pumiu
5
Pmax
[T+ + 2 M.maa C,
Puii
where we used L. Pminn S Pmax. and the fact that va va+bs Vo+ vor a a. 0. Then the number of communication rounds
280
T
<
7
n8
5
Pmax
i 2) + 2 Mmaxx
<
c²
a
Pmin
[
+ D)00
Praxx
Mmaax E80 6²
ac2
Pmin
At each worker, have
# #grad,
m, T (pmm (1 p()T.)
2m4 T
m + T; mi
S m, + 2T.T.
Averaging over 1, 1,....P. .n, get
40

---

Under review as a conference paper at ICLR 2022
#grad
Σ + 2TT
T(T. L)80
T Mimax L80
Pmax
= 0 m +
ac
Pmin
E²
E.2 CONVERGENCE UNDER POLYAK-E.OIASEEWIC CONDITION
Theorem 6. Let Assumptions 1 and hold, and let the stepsize in Algorithm 3 be set as
0
Pmin
0 min
7o: 2p
(44)
2p
where 70 def 0 < 5 L +
72 + ( Pmax
2
L
V Σ
03.0
0
11
Puiia
1 1 (1- -1 +), 3 = (1 - a) (1 + 11 for any 8 > O.
Let Tf def f(x')= - f(x*) v + 27 (1 + 48pmaxx
Pt. Then for any T 2 0, we have
Paii
T $ - (1) [TO]]
(45)
Proof. Similarly to the proof of Theorem the inequalities (39) f(**).
440).
41 hold with 8 f(x²)
Adding 39 with
2x # multiple of (11
we obtain
[8 + 0
27 E [vet1]
E [
Y
E
11
1
E [ + YE [v']
2n
27 8
+
[Pd]
((1 (1-0)
0) [V']
A
+CE (P
2 E [v']
(1
8
8 +
2
(xr
[1
1
L 2
[R]]
27
20
+y
E
P']
0
where A def 3 (2ī²
(213+22).c C del 2.3m
Then adding the above inequality with
27 Panin (1
2C 2()
multiple of 40
get
41

---

Under review as a conference paper at ICLR 2022
27
+ 24 (+
20
B
[
E 1J +
[[++]]+
E [p
0
Pmin
0
S 8
2 [v] (1-
(1-2) 2
0
V [1'((z))11
- 1
L
27A
E R2'
2
27
2
20'
ty
1 +
E P"
27
1
20
(1
Pmin
E [P]] + L [R9)
Pinin
E
1
+
27 E ['
(1
+
27
1
20
E [P') (1
Pmin
0
2
Puin
0
2
E
Vf
x 1|]
1
L
27A
2y
1+
2C
2
E R*
22
2
Pmin
(46)
PL incquality implies that 8 - 3 fx')(
< (1 7p)6
In view of the above inequality and our
assumption on the stepsize ( S 2/² v
Pmim 2p
), we get
L 2
27
20
E [ < (1 7n [w']
1
E
[R]]
2
0
Pinin
0
The coefficient in front of EE [ simplifies after substitution by and C
A
+
27 Pinin
1
20
43 I2 +
23 +
2
+
8,
Pmax
2
0
0
0
Punin
0
Pmni
48
T.2 +2
5,3
Pmax
1
C
0
Punin
Punin
Thus by Lemma 15 and the stepsize choice
88 1 +
5,9 Pmax
0 O<>S
L+
A2
(47)
Pmin
Pmin
the last term in 46 is not positive.
E
[1]t]] < (1 - B [v'].
It remains unroll the recurrence.
Corollary 11. Let assumptions of Theorem hoold,
0 = 5. V)i(1"),
== 1......,7 n,
0 Puii
183 12
153 Pmax
7. min
y0. 2j²²
To ++ V 0
-+++ +
[2
2μ
Pmiin
Pmiin
Pi
I.....n. n.
T4 + m,
Then, after T iterations of EF21-PAGE we have E.. [f(xT) pint] S c. It requires
Punax + Vmlmax In
80
T=
Pinin
42

---

Under review as a conference paper at ICLR 2022
iterationsccommnniicaatnss rounds,
L I
80
# #grad;
my +
Ti
Pmax
v Mmmaxh C
1
Pmni
stochastic oracle calls for worker i, and
T. T
80
#grad O
T
Pmaxx
+ mm In
1
a
Pmin
stochastic oracle calls per worker on average, where T 1 Ei To m max mi Pinax max Pi Pmin min;=1,.... Pi-
Th
ma, max
43

---

Under review as a conference paper at ICLR 2022
F PARTIAL PARTICIPATION
In this section, we provide an option for partial participation of the clients a feature important in federated learning. Most of the works in compressed distributed optimization deal with full worker participation, i.c., the case when all clients are involved in computation and communication at every iteration. However, in the practice of federated learning, only a subset of clients allowed to participate at each training round. This limitation comes mainly due to the following two reasons. First, clients (e.g.. mobile devices) may wish to join leave the network randomly. Second, it is often prohibitive to wait for all available clients since stragglers can significantly slow down the training process. Although many existing works (Gorbunov al. [202]] Horváth & Richtárik 202T Philippenko & Dieuleveut 2020; Karimireddy et al. 2020; Yang et al. ] Cho et al. (2020) allow for partial participation, they assume either unbiased compressors no compression at all. We
provide a simple analysis of partial participation, which works with biased compressors and builds upon the EF21 mechanism.
The modified method (Algorithm 4 is called EF21-PP. At each iteration of EF21-PP, the master samples a subset S: of clients (nodes), which are required to perform computation. Note, that all other clients (nodes) & St participate neither in the computation nor in communication at iteration I.
We allow for an arbitrary sampling strategy of a subset St the master node, The only requirement is that Prob (i E St) p; O for all i = I,... n2, which is often referred to as proper arbitrary sampling P Clearly, many poplular sampling procedures fell into this setting, for instance, independent sampling with/without replacement, 7-nice sampling. We do not discuss particular sampling strategies here, more on samplings can be found in (Qu & Richtárik 2014).
Algorithm 4 EF21-PP (EF21 with partial participation)
1: Input: starting point x0 Rdd gf E Rd for = I,..., n (known by nodes); g" = E1= 9 (known by master); learning rate y 0 do
2: for = 0,1, T
3:
Master computes 'x11 x² 7g
4: Master samples a subset S, of nodes (I.s.) S n) such that Prob (i St)
5:
Master broadcasts xz+1 to the nodes with e St
6:
for all nodes i = ,,..., in parallel do i S, then Compress cf = c(Vf((x'+) - g.) and send di to the master
7:
8:
9:
Update local state 9) 1+1 of + cf end if if i
10:
11:
$ Sy then
Do not change local state gf +1 = 9
13: end if
14:
end for
15:
Master updates gf*1 4+1==/ -6: cf 0 for i $ S.
16:
Master computes g0+1 - i+1 via go+l = 9¹ + + of
17:
end for
Lemma 5. Then for Algorithm f holds
E [[ < -1 [G*] + -BE || ||,t11 - x01]3]
(48)
with 8p dgf PPmin + Opmax (Pmar Pmin), B def Σ" (3p: + +(1+ p-1) (1 p-)) L. def Pmaz= mmxxiiiga Pi, Pmiin min 0= (1 s) a)), (1 !) (1 a:) and
def
small enough p.
Proof. By 13 in Lemma we have for all E St
E [G
| S.] < (1 - O}R [G]] + BI [1 - 1² s.]
(49)
It is natural to focus proper samplings only since otherwise there is node i, which never communicaties. This would be critical issue when trying minimize (T) we do not assume any similarity hetween f((-)
44

---

Under review as a conference paper at ICLR 2022
with 0 = 1 (1 + s) - 8=
= (1+ !) (1 a) and arbitrary s >> 0.
Define W def
x², { and let i of S₁, then
E [ | i $ Si]
= E E |
W i c st]
= E E |1 - Vf (z /|2 wh] l si]
E |1ot v /)((z')] )|² 1
l s.]
S (1+ p)E
+ +(+
E E [f(( - [ l St)
S (1 + [
(1 + p p- IF V vf((2')] 1 $ Si)
G + (1 + p p11) LE ||00 - x2'1²]]
S (1 eb
(50)
Combining 449 and 50
we get
E [[G+t]]
[
n
P.E G
| E Si]
+ 12
Σe
(1 pc) E [G 1 lig Sil
n
19
(1 0) 1 n
P [G]] + 3
n Σ
|
P=I.
E || =011
n
1 Σ (1 - p;) E [G]]]
+ +11 (1+p) p)
n
n
+ (1+p 1-)
Σ (1 p.)
E |||ott2 -=011² 20(1]]]
n
(1 0) Pmnax
E
[G]]] + 3
Σ
ps 1i
E $[laftt - [8]
n
7
+ (1 + p) (1 Pmin)
1
Σ
E [G:]]
1=1
R ||actl-a*"] p-)
+
(1
1=1
(1 Pmaaa + (1+p)(1 pmmnn) )E [
p.)) (Ops + (1+p=1) (1- (p-))) L3 E ||aat1- - [=]
1 (ppiin + 0pmax - p (Pmax -Pmin)) E [a]]
(pp: + p-) (1 p.)) L3 E ||a041- - 22 2-11
(1 0,) E [G*] BE || 1p]
45

---

Under review as a conference paper at ICLR 2022
Lemma 6. [To simplify the rates for partial participation) Let B and By be defined as in Theorems and Theorems 8 and let Pt = p > 0 for all = ,,..., n. Then there exist p. 8 >> O such that
pa
0₂ 2
(51)
2
2
B
4L
0
(52)
8p
pa
Proof. Under the assumption that p; = p for all = I,...; the constants simplify to
Bp ppp+ 8p-pp p:
B (Bp + (1+p
122
Pmas = Pmnn = p.
Case 1: let a = 1,p 1, then the result holds trivially.
Case 11: let 0 < < 1, p 1, then B = 3ī. 0p = = v1 - -a 2 2 and 52
follows by
Lemma
Case III: let = 1. and < < 1, then 0 = 1, = 0, B = (1+ p- (1- (1-p) p- (11-)).
Then the choice
pex ~(-ツ) simplifies
0, 2'
B (1+ p)
2(1 p)
2
4
1 1
0p 0-p(1-1
n2
Case IV: 0 < a < l,and < < 1.Then the choice of constants = (1 ()) (1 (1+1) 8).
(1 a) (1 1), p 41-p) T[-oa yields
pe
pp + 0p - 0p-p
= (1-)))))) -
pa pa- aas - p1-
pa.
(53)
Also
14 4 30
4
1
4(1 p) + op
4 - p(4 - a)
4
<
1+
p
po
pa
pa
Thus
B p8 (1 -p)
(1
p(1 a)) (1+ +1+11 +1 p) (1+ 7.2
7,2
0 p(p
+ 0)
1 pc
p(1 - a) + (1 p)
pex I
pa
pa i
P0
1.2
BPa
167
(54)
pºa²
46

---

Under review as a conference paper at ICLR 2022
F.1 CONVERGENCE FOR GENERAL NON-CONVEX FUNCTIONS
Theorem 7. Lel Assumption 7 hold, and let the stepsize in Algorithm be set as
-1
B
0<75 1
(55)
10
Fix T 2 and let 8 be chosen from the iterates x0,x0!_ 3-..,
x T- uniformly random. Then
2 (f(x)) - )
E G
V |1 v
E
(56)
77
0₂T
with 9p = PPmin + Ppma - p- (Pmax Pmmm)) B -
(Sp; p1+ (1 (1-p.)) L.
Pmaz maxIiiiH Po Pmin = mini Ph, 1 (1 + 8)
a), = (1+ b) (1 a) and
P. > 0.
Proof. By (20 we have
[z(()))1 - (1 I
115++1 I
E [
E 2
RR + 2 B
(57)
27 2
Lemma that
E [ S (1 0p) [G]] + BE [RC
(58)
with P,- PPmin + 0pmas p (Pmas Pmin). B Σ
(sp: (1 p- (1 p:)) L7
Pmaz n Pis Pmnin minigign Ps. 1 (1 ()+ (1)1-)), a), gign
a) and
small enough 8.8 > O.
Adding 57 with a 20,
7
multiple of (58) and rearranging terms the right hand side, we have
E [1+
+
E [G
E [8']
E
[G]]
20p
20,
F
[[
12]
L
BBB E [R*]
27
2
20
E
8d
7 E [G']
20,
The last inequality follows from the bound 2 + Ly - 1, which holds because of Lemma 15 and assumption the stepsize. By summing up inequalities for t = 0...., T 1, we get
8,
2 T-1
8
7 G
< 8
2 E
[G
-2
IE ||
20
20
Multiplying both sides by - after rearranging get
T
28
E [
0T
t=0
It remains to notice that the left hand side can be interpreted as E uniformly random.
||>) [|]]
where &T is chosen
from 0 of
Corollary 12. Let assumptions of Theorem 7 hold.
vf((x"),
1 == 1,.... n,
B
L+
0p
Pr
P,
n1
47

---

Under review as a conference paper at ICLR 2022
where B and Bg are given in Theorem 7
Then, after T iterations/coommaniccttionn rounds of EF21-PP
have E [/("") 6 requires
||]]
L
T= #grad O
(59)
pas?
teeraions/communicatonns rounds/grudint computations at each node.
Proof. Let ge fi((x)), I,...,
, n, then Go and by Theorem
(1)
20
(6)
28
B
(1it)
26
4L
#grad
T
S
L
L
L
+
7E2
g2
Op
E²
pa
280
4T.
(dv)
25
L
4T.
5T.0
L
+
+
g2
po
g2
pa
po
poe
where (i) is due to the rate (56) given by Theorem 7 In two (ti) we use the largest possible stepsize
(55) in (iii) we utilize Lemma and (iv) follows by the inequalities S 1, p and T. T. n1
F.2
CONVERGENCE UNDER POLYAK-LOIASIEN
CONDITION
Theorem 8. Ler Assumptions 7 and hold, and let the stepsize in Algorithm be set as
0 0<>5 S min {(++
2B
(60)
0p
2p
Let ti def f(x²) - f(x²) 2 G¹. Then for any 2 0, we have
E 1 < - 74)= EE [v]]]
(61)
with 0p = PPinin + 0pmas (Pmar Pminn), ) B Σm (3p; + p-1 (1 p:)) T.3.
Pmaz maxisign Po Pmin minigisn Ps, 1 (1 s) a). B (1 b) a) and
0,8 O.
Proof. Following the same steps as the proof of Theorem 2 but using 588. and assumption on the stepsize (60), we obtain the result.
Corollary 13. Let assumptions of Theorem hold,
d
vf((2))
1 ... n,
2B
0p
min
L
0g
2/
Pe p.
1, 1....,
where B and Op are given in Theorem
& Then, after T iterationscoommnnccation rounds of EF21-PP
have E [f(xT) f(x))] < It requires
(
T #graa o
log
(62)
pap
ternatons/commmnications rounds/grudint computations at each node.
Proof. The proof is the same for Corollary 3 upper bound the quantities 1/e, and B/e,, which appear in Theorem
The only difference is that Lemma is needed to
48

---

Under review as a conference paper at ICLR 2022
G BIDIRECTIONAL COMPRESSION
In the majority of applications, the uplink (Client + Server) communication is the bottleneck. However, some settings the downlink (Server + Client) communication can also slowdown training. Tang et al. (2020) construct a mechanism which allows bidirectional biased compression.
Their method builds upon the original EF meachanism and they prove nonconvex objectives. However, the main defficiency of this approach is that it requires additional
T rate for general
assumption of bounded magnitude of error (there exists A > O such that E ||C(z) =1|² < A for all 2). In this section, we lift this limitation and propose a new method EF21-BC (Algorithm which enjoys the desirable O (+). and does not rely on additional assumptions.
5
Algorithm 5 EF21-BC (EF21 with bidirectional biased compression)
1: Input: starting point xº E R g", 6", T. E Rd for = ..... n (known by nodes); g
E> T. (known by master): learning rate 7 > 0
2:
for 0,1,2.... T 1 do
3: Master updates x = x² - ~g
4: for all nodes l...., . in parallel do
5:
Update x g++1 = r' ?g' rg"..0 9 g++ g' + b'.
6:
compress c C., (V f 1) g.). ). send ot to the master, and
7:
update local state g end for
g + +
8:
9: Master computes g 1 n 7+1 via - + di
- g.
+ g²), broadcast bl+1 to workers,
n
10: compreses 1++ = Cm (1g +1
11: and updates g++1 = g" + b1+1
12:
end for
Note that CM and C.r stand for contractive compressors of the type Of of master and workers respec- tively. In general, different aM and ar are accepted.
Notations for this section: P del |l V[((z*)] p del E P..
Lemma 7. Let Assumption hold, C.v be contractive compressor, and g.+1 be an EF21 estimator of ( i.
g = T + Co. (V Φt) for arbitrary ge and all all i I,..., n,, t 0. Then
(63)
E |t+1] s (1 0.. E pt] + Bug B. 1.P
R*)
(64)
where a def 1- 11 -1 s), B def (1 aw) (1 s-1) for any > 0.
Proof. The proof is the same as for Lemmal
Lemma 8. Let Assumption I hold, CMr Cu be contractive compressors. Let g. be an EF21
estimator of vf(aat))) e.e.
g - + C. (VF g.),
(65)
and let gi+1 be an EF21 estimator
of En 1 g* 11 = gو + Cm (g++1 -g))
(66)
for arbitrary g. 9d and all 1,..., ......,n. n, 2 0. Then
E -1 g 11 < (1 8 E ||9* 3-1²"
+ 88 E PP* + 88 i2F |R').
(67)
where g" 1 Σ 9/. 3" 1 Σ H. Am = -1--a +()) p). 3M = -1-aaw) (1 11
for any p
49

---

Under review as a conference paper at ICLR 2022
Proof. Similarly to the proof of Lemma
define W def fof...., .......,,e. Ihs 2h, xlt,) and
E | ++1 -9
E E ||1s 1- 9 11+ wo]
E E [11s* + Cas S5x(tt+1 - -g') - 11- w
(1 aas) B || - -9-1l"]
(1 als + p)lE ||0x - -01²²
+(1 - al1-am) (1 p-1) l - 3-
(1 (1-00 (1-0as)3 FF.
[||0* - 111 + Bas | -
(68)
where (i) follows by Young's inequality (188), and in (ii) we use the definition of Uss and 8M-
Further we bound the last term in 668 Recall that
(69)
71
where of = Cr (Vf((t+)))
Φ and g'
> n Zim1
g
Then
|| - 3-1"
6
1
g"
11
1=1
E
1=1
E
[||4 - (V.((t - -. + (V. - 37)
E
7=1
18
|| (Vf((t(t)) - 3.) (v)( - 31 wi]l
2 71
1=1
+2 1
n
E [[ - 11
71
2(1 aw)
E ||V -717
+ 2
E [ -
2(2 aww)
Σ E || - 11
(18)
|| -1
4
71
4 n
Σ
[|VAA
vsi(x')- - (Ø) [)(()))))1
8
- vf((2'))
|11 + 8 Σ E \f - -
1=1
8
Σ
E
|: - vイ(
si || 1|a-+1=0011 20|1"]
71
SE
P
87 E
R
(70)
50

---

Under review as a conference paper at ICLR 2022
where in (i) we use (119.
(ti) is due to awe 0, (iti) holds by Assumption In the last step
apply the definition of p 1
Ei= l
Vf(("'>||' and R² x x
Finally, plugging
70
into
68
we conclude the proof.
G.1 CONVERGENCE FOR GENERAL NON-CONVEX FUNCTIONS
Theorem 9. Let Assumption 7 hold, and let the stepsize in Algorithm
be set
163M
28
8,3M
0<7s L+ I
1
(71)
0M
0w
MM
Fix T 2 and let at be chosen from the iterates x.
uniformly at random. Then
2E m
E
f(
(72)
7/
where vi def 1(x)) - fiint + TM 11ge + -
+
83.r
pt. L
V - L. Ow def (1-
U3s
(1+((+)) Bw def (1- aw) (1 + 1) On
def
1 (1 aM) (1 p). BM del
(1 (1-ax) (1 (1+ p
for any p.s >
Proof. We apply Lemma 16 and split the error 1lg
V)(x')]] in two parts
f(x(t1) S f(x') 2 [=())
1
RR + 2 2 119 - -V((')l
2
27 2
s f(x') 7 |
1 L
R²
2
27 2
+7|19¹ - -/12 +> 11 - -V'-Vf(0")) vf(x')]] ||
S f(x') - 2 4 (z )1
(1 2x 2) R.
2
+ Σ |1gs - 71'
+ + Σ
| V/i(a')]1
1=1
= f(x') - 2 ( -
-(1
Rd + >11g* - =311 + tpp',
(73)
2g
2
where we used notation R2d = |l 122 = || - x11 pe === 1 Σ 10 {)(('()] and applied
118) and (19
Subtracting finl from both sides of the above inequality, taking expectation and using the notation f(x fint we get
1 (1 [ + +E
E [8
E [51]
E [[V
E
[1o*
[|2]
+ TE [P*]
2y
(74)
Further, Lemma and & provide the recursive bounds for the last two terms of 77
E pt+1] I (1 (1- DE) [P*) + 3 L'E (R),
(75)
E [1 - -211113]] < (1 - IE [19s - -3-1 + 83 i. 8. [R.] + 83 [P'] (76)
51

---

Under review as a conference paper at ICLR 2022
Summing up
744 with TM
multiple of 76
we obtain
E 1
7 E |11 -
[88 E V (x*) [1]]
1
L
EE [R]]
0M
27
[|0 3-11"] {
+
+ 0M
7
(1-
(1-0w)
IE |100 - 3 11²))
7
8,331
[RC] + 8 [P()
8M
s
E
[6]]]
+
|||0* 11o"'-o11 3タ
|Vf |ff (z') (z') [|]
0M
2
L
873M L2
IE [ne*]
27
2
8,3M
+7
1 +
[P']]
0m
Then adding the above inequality with o/ (1+
88M Pst
multiple of 75). we get
E [1 = E [0
+
"E
E
[|1 - 1111
7 ( 1 1
85M
E
[[ptt]]
Oar
Ow
0M
s E [59] + 2 E ||1ot - 5²1""] - IZ | (I-) [1]
1
87B I2
[
2ny
8,3M
+y
1 +
E [P*]
0M
7
8,3M
(1--ww) O. Pd] + Bm,. T [P(T)
(11
+
+
0.
ON
<
E [5*]
+
E
||19* - 3-11"]
+
1
8BM
[Pi]
- 1
V (z)))
AM
0ur
2
L
8y
T.2
7
1 +
8,3M
B.T
[[R²]
27
2
8M
E
[v']
||
(1))
2
L
8yB
12
2B I?
883M
11
E
[RR]]
(77)
27
2
OM
0n
0M
Thus by Lemma 15 and the stepsize choice
-1
163
2.5w
8,3M
0 0<7s
L
L
+
1 +
(78)
0M
O..
0M
the last term in is not positive. By summing up inequalities for 0,..., T 1, get
0 < E V
EE
Σ
[
Multiplying both sides by z and rearranging get
21E [10]
Σ
<
TT
52

---

Under review as a conference paper at ICLR 2022
remains to notice that the left hand side can be interpreted as V f+²))
||]
where x" is chosen
from x0 T-1 uniformly at random.
Corollary 14. Let assumption of Theorem
9 hold,
go = Vf(x"),
T. = Vfi(2'),
I,
I. [.+ IV
163M
23w
(1 (1+
8BM
+ 8w
Bss
0
Then, after T iteration/coommunicationn rounds of EF21-BC we have [f())) requires
$ E..
T = #grad = O L
(79)
iterationscoommuiiattin rounds/grudint compulations at each node.
Proof. Note that by Lemma 17
and CMM, Ohw 1, have
1633M
20e
88M
4
4
0
+
0w
[+
0M
16
OM
2
+
2
0
1
8
a
64
33
+
2
2
0'
O'M
64 + --3
a 03
remains apply the steps similar those in the proof of Corollary
G.2 CONVERGENCE UNDER POLYAK LOJASIEWICZ CONDITION
Theorem 10. Let Assumptions 7 and 4 hold, and let the stepsize in Algorithm be set
0M
Ow
0< S min
70.
(80)
2p.
2/1
-1
where 7o
def
L V
328M +
48,, 12 (1
163
ī. = V / I?? G.. def =1- 1- (1-11p (1-aw)((1
9,,
0xi
s), Bw def
(1 aww
+ s-1), 8m
def 1 (1 aas) (1 + p). BM def (1 1--ap aaa (1 + p-1) for any
P.S >6>0
Let ye def f(z')= çint + 2 l1g*
8/3M + Pu
v
1
pt. Then for any T 2 we have
6M
E
V
s (1 - 7H) T E [vo).
(81)
Proof. Similarly to the proof of Theorem the inequalities f(**).
74).
75 76) hold with 8² = f (x:!)
It remains apply the steps similar to those in the proof of Theorem
Corollary 15. Let assumption of Theorem 10 hold,
()())),
g
(a
1,...,n, n.
8M 8.
3283
43
16,3MM
= min
Yo.
2p
2p
=
L + L OM
+
0..
1
0M
53

---

Under review as a conference paper at ICLR 2022
Then, after T iterations of EF21-PAGE we have IE - S It requires [f(x*))
I.
100
#grad 0
In HawaN
iteratiosscoommnniiaatons rounds/gradint computations at each node.
54

---

Under review as a conference paper at ICLR 2022
H HEAVY BALL MOMENTUM
Notations for this section: R |1r = (1 -)>1||=++] ==11
In this section, we study the momentum version of EF21. In particular, we focus on Polyak style momentum (Polyak) 1964 Yang et al. 20166). Let g be gradient estimator iteration t, then the
update rule of heavy bull (HB) is given by
x x = x' 799 n (x' (x'-x"'1) )
where x- .r. 17 E [0. 1) called the momentum parameter, and y > is the stepsize. The above update rule can be viewed as a combination of the classical gradient step
y' x² 79
followed by additional momentum step
x -++1 = v' + (x'
Here the momentum term is added to accelerate the convergence and make the trajectory look like smooth descent the bottom of the ravine, rather than zigzag.
Equivalently, the update of HB can be implemented by the following two steps (Yang et al. 2016
x++1 x² yu'
y(+1 n7 + gttt1
We are now ready to present the distributed variant of heavy ball method enhanced with a contractive compressor C, and EF21 mechanism, which we call EF21-HB (Algorithm 60. We present the complexity results in Theorem I1 and Corollary
Algorithm 6 EF21-HB
Input: starting point x E Rd. of Fd for I,..., n (known by nodes); v0 9o
Σ" 2i=13 o (known by master); learning rate y 0; momentum parameter 0 17 do Master computes =++ xt yo and broadcasts w1+1 all nodes for all nodes i = 1,... in parallel do
2: for t = 0,1,,,....
3:
4:
5:
Compress c C(V ft t
gf) and send of to the master
6: Update local state g g
7: end for
8: Master computes g++1 Σl of via gh+l =9¹ + El= d. and w mp² + g
9:
end for
In the analysis of EF21-HB, assume by default that w-! O. Lemma 9, Let sequences (x*) (z')r20- and {u') Je20 be generated by Algorithm 6 and let the sequence
{2r) h2o be defined as 111 dof 1+1
77 v² with 0 S 17 < 1. Then all 2 0
1-
2 ++1
7 17
Proof.
c-1
17
1
?1
(8)
2 +
79
7
1
/'
7
(0'
1
1]
55

---

Under review as a conference paper at ICLR 2022
where in (t) and (iti' we use the definition of 2 and 2², in (2i) the step x x² yv
(line 3 of Algorithm 6). Finally, the last equality follows by the update y r7 + g (line 8 of Algorithm 6).
Lemma 10. Let the sequence {u' J120 be defined as vf+1 n/o gg with n Then
Σ
7)
1=
Proof. Unrolling the given recurrence and noticing that v O, we have of Ei 'g' Define
H 2i n² S T Then by Jensen's ' inequality
def
2
H
g
H
1=
t=
1=0
s
H
1|
T-1
||
=
1
1=0
T-1
Σ |1''11
r
1 1-
Σ ||
Lemma 11, Let the sequence (z (z')12 be defined as t0+1 def 111
- v² with S < 1. Then
T-1 E (1 - 0)
T-1
T-1
G + 23 + 4n7²)
Σ E [1 - 20[1]]
1=
1=0
where 0 = - (1- + 8),
8= (1-a) (1 (1+ for any > O.
Proof. Summing up the inequality in Lemma (for EF21 estimator) for t = O,..., 1, we have
T-1
T-1
Σ E |
<1 - 0)
Σ [G]] + 3ī.
| 1 =0913]]
(82)
1=0
It remains to bound ΣT-1 E |||2t|1 - 2-11
Notice that by definition of {2r Fe2o we have
x. ++1 x² = 2tt 1+1
2¹ +
717 (v' 11-1).
1 m
56

---

Under review as a conference paper at ICLR 2022
Thus
T-1 Σ
17 T-1
Σ
-
|| || - 2²12
+ (1 - 17)
|| 10t - -1-
0
1=0
T-1
2
2
Σ
E
|| ++1 - 201²]
+ (1 1)
E ||00* - (1 - m))
1=0
T-1 Σ E
47211 2-1
||:
2
-
E [1]
+ (1- n7)
1=0
472112
T-1
+ (1 - n)3
Σ
17) R [1|0"
2 1m0
T-1
|| 2" ||3]
+
47
T-1
Σ
E [10011]]]
(1-m)²
0
17227
T-1
+
Σ
E [|]
(1 1-) 1=0
T-1 Σ
141 21 $11
87221
Σ E [|
E
+ (1 n) 1=
1=
T-1
T-1
(2)
Σ
||: - 2 ||²
+ 81p 2 Σ
E -1
- =010²]
T-1
2(1 + 477")
2 |
2113]
2=0
where in (i) we apply Lemma 10 and in (ii) Lemma 9 is utilized.
It remains plug in the above inequality into
Lemma 12. Let the sequence (z']12 be generated as in Lemma for all t 2
iee, ge+1 20 12 g" then
| < 26 + 2(1 -1)²
72 || 1 _ =91
with G = -
-
Proof. Notice that for > 0 we have (f(x') = Vs(ao)) - -g-- 7
(2 2¹). Then
{| < 2||vS(x')-)) - 1²1 +2 (1 (1-1)² 11)
|| - =11
72
2 n
Vf((a') 0.11 2(1 1)
- -121
n
72
where the inequalities hold due to
118) with s 1, and 119
H.1 CONVERGENCE FOR GENERAL NON-CONVEX FUNCTIONS
Theorem 11. Let Assumption 7 hoold and let the stepsize in Algorithm 6 be set
0<><<
(1+ n)
I
23
(1 (1+47²)
def 70
(83)
2(1 -1 )
0
57

---

Under review as a conference paper at ICLR 2022
(1-- and >> 0. Fix T 2 and let ae be chosen from the iterates x0, x
where 0 S <
y..., x
T
uniformly at random. Then
T-1 E
38 -17) 11)
E [
1 3(1 - 17)
2
(84)
Ty 1
7
OT
2X1 y
1 7.
%0
where A1 def T
x 29 (1 + 4np)). If the stepsize is set to 0 <
S 20/2, then
E [|[
61
11)
E |o|
3(1 - 11)
2
(85)
7T
T0
0 (1 + 4n7²) 7L4
23
Proof. Consider the sequence 21+1 def x1+1 - -- ot with 0 0 n < 1. Then Lemma states that
gt1l = =2 g". By L-smoothness of f(.)
2((1)) - 2/+++ + L || 1 1-:11=1+ 211
((: - -1x²) S (VI(="), 241
2
(VI(=') - g/' 241 - -2-) + (gg' 2 -2
2 ||=441- 1101-==1p 111
L
(V1(2') - g6 24 - 24) - 1 - " || - 211 + I
2 || - =21
?
(VS(=)) 36 2 21) -
1 [-1 17 L
|| - 211
7. 2
(Vf(z') gg',, 2 2111_ - 2²) + (Vf(z') - vf(z'), 2 2²)
(1 1 11 L
|| - =21
7
2
(1))
1
d1
=2y1²+ + 1 |V((') (
Vf(x²)
0²1?²=
+
-|
2\1
2
222
d2
|| - 2/1
( 1- 17 I
2 || - 21
+ 2
7.
Vf(z9) - 00'1 +
|ff(z V\((a')11
2A1
2
-(1-")
1 (1-1
L
\1
X2
||
211
2
(in)
1
Vf(2')
0'11²
+
xt |1?
2\1
2\₂
1 (1-1 17
L
A1
X2
|| 1112
7
2
(iw)
2, 2 T,2
Vf(z') - --'11==
+
2\₂ (1 - -)) 1100-112
2\1
1 17
L
X1 Aa
|| 11 211
2
where in (1) Lemma 9 is applied, in (ii) the inequality (15) is applied twice for X1 A2 > 0, (Mi)
holds due to Assumption 1 and (ir) holds by definition of z x²
111
9
58

---

Under review as a conference paper at ICLR 2022
Summing up the above inequalities for t O.....T T (assuming 8 0),, we have
T
2²
T
f(z") & f(z") +
| - -0'l² + 2A2(1 - -
|1
2X1
1=U
t=0
(1-8
L
A1
12
|| - x11
7
2
2
2
1=0
f(0%)
+
1
Σ
[V
-
2212222
Σ
||0/112
2
2A2(1 -1)a 1=0
1=0
1 T-1
11
L
A1
Σ || - 21
7
2
2
2
T-1
222
T-1
(1 n))
(
f(z2)
+
Σ
V - 9011²
+
Σ
2 1 - =/1
2X1
222(1 - -1)4 1=0
72
1=u
1
L
A1
A2
|| | - 2112
7
2
2
2
1
f(29) +
Σ
V\(('') g/1l²
2
1=0
1 1-1 1
L
\1
22
n7213
|| 12 1-41-22 =21
7
2
2
2
2\₂ (1 17)2
(ii1)
T-1
I f(z")= +
Σ G
2
1=U
1 1
L
01
A2
2,21
T-1
Σ
|| - 2/13
7
2
2
2
2x₂
(1
1))
1=
1 T-1
f(29) +
Σ
G²
2
1=0
T-1
(1-
L
X1
n
2¹13
7
2
2
(1 17)
= f((0) +
Σ
T-1
G
1 17
L
A1
nn.
1
T-1
Σ
R
2
2
2
(1 7)
(1 - 17) 1=0
1=0
where (i) holds due to Lemma
10
in (ii) Lemma is applied, in (iii) we apply [VV.(x=)) - g²1 S
G Finally, in the last two steps choose X22 1-
aL. and recall the definition R. = 1hg'11?
(1 (1-n)² -2 || 2
Subtracting finf from both sides of the above inequality, taking expectation and using the notation
8' f(=') finf, we get
1 T-1
1 1- 1
L
A1
(1 - -n) )
nL
1 T-1
E [eT
<
E
8
[[
B
2
2 2
(1 m)
1=0
(86)
By Lemma
we have
T-1 [[ < (1-0)
28 + 4n²))
T-1
E
Σ
E
[ +
Σ t=
EE [xe*]
(87)
(1 (1-1)
0
t=
59

---

Under review as a conference paper at ICLR 2022
Next, going to add (86) with 20 multiple of (87). First, let us "forget", for moment, about all the terms involving R' and denote their sum appearing on the right hand side by R. then
T-1 E
1
E |
E G
E
E G
0) 2
| R
20
2
E
E
G
+R.
20X1
Canceling out the same terms in both sides of the above inequality, we get
1
E [5"]
E
[G"]
E
+
E
[GJ]] R,
20
2AA1
where R def
|--
L 11
2n
8i+(4++)7))
E
2
1-
0A1
(1-1)²
Now choosing d = T.v #
(1 + 4n72) and using the definition of To given by
83 i.e., 70
def
(1+n)& 2(1-a)2
+
I 1-
V
23
(1 + (1+4))))
we have
1 11
2n
3I 4n7²)
+
2
1
1- 77
2
0y1
(1 1,)
17
L
1+
27
- I
23
(1+ + 4n72)
1
2
1 -
0
(1 1))
1+ 1
23
(1 + 4n12)
+4122)
2 (1
7)
0
1-
--
Then
0 < E
[T
E
8
G
20
E
8
1
6O)
(1
1
E
[R9]
20\1
7
70
1
E
TT
E
R
70
1
After rearranging, we get
E [T (1 11) 7 7(1
E R*
S
To
Summing the result of Lemma 12 lover O,..., T and applying expectation, we get
< T-1
T-1
E
G + 7
Σ E R
1=0
Due to Lemma 11 the conditions of Lemma 18 hold with C def
2,T.2 1447² (1-7)2,
8¹ = E -E(G* r
[R')., thus
60

---

Under review as a conference paper at ICLR 2022
7-1
E
T-1
[
Σ
E
[R]]
Combining the above inequalities, we can continue with
T-1
T-1
[|>
s 2
Σ
E
G
+
2
[*]
72 1=0
1=0
2 G
2+ 1²
E
[2*]
0
0
1=0
2EE
|
1²C
E T
(1 - 11)
2
0
0
1
70
11+T)
Note that for 7 < 70
we have
1]
C²
C
0
S1 1.
(88)
(1+m)L 2(1-1)²
+
0
Thus
2E [G0]
3E [
(1 - 17)
Σ
E [[V
?
1
X
70
31 11)
E [G0]
3(1 - 11)
2 2
7 7 70
2
where d T 20 (1 2n
Corollary 16. Let assumptions of Theorem hold,
df vf((2,,,
I.....n. n,
(L (1+n)
23
=
2(1 2)
0
(1 + 4np2)
Then, after T itenation/coommuiication rounds of EF21-HB have E requires
[|
$ S.. Ir
L880 22
-+1-11)
1
#grad O
+
(89)
iterationsccommuiccationn rounds/gradint computations at each node.
Proof. Notice that by using L < L, 1 < 1 and Lemma 17 have
[)+ i
23
L
10,3
V
(1 + 4m7)
<
2(1 - m)
77
0
1)
- 17
2
10
<
1-1
1-
61

---

Under review as a conference paper at ICLR 2022
Using the above inequality, 88 and 83 get
68% (1 77)
60
71)
L
2/10
#grad
Ts
7e?
6²
-
1
2010 10
+
E²
1 11-1
17
62

---

Under review as a conference paper at ICLR 2022
1
COMPOSITE CASE
Now focus solving composite optimization problem
(z) ZERd
min
def
Σ -x())+(x)) 1=1
(90)
where each fi(-) is L--smooth (possibly non-convex), r(+) is convex, and Φinnt inf ((x) > -o0. This is a standard and important generalization of setting (I.. Namely, it includes three special cases.
Smooth unconstrained optimization. Set r 0. then we recover the initially stated problem formulation T.
Smooth optimization over convex set. Let de (indicator function of the set Q), where
Q a nonempty closed convex Then (90) reduces to the problem of minimizing finite sum of smooth (possibly non-convex) functions over nonempty closed convex set
{ 1 I f((z)
min ZEQ
i=1
l reeullaarized optimization. Choose r(x) \||z||1 with A > 0, then 90) amounts to the
I regularized (also known LASSO) problem
min wERd
Σ f((x) A|l=lla
n
For any 7 0, x E Rd, define a proximal mapping of function r(-) (prox- pprxx-operator) as
1 11
prox (x) arg min ((())
+ 24
(91)
yERU
Throughout this section, we assume that the master node can efficiently compute prox- at every iteration. This is reasonable assumption, and in many cases (choices of r(-)) appearing in applications, there exists an analytical solution of (91), or its computation is cheap compared to the aggregation step.
To evaluate convergence in composite case, we define the generalized gradient mapping at a point Rd with parameter ?
(x) def (x ( -Vf(())
(92)
One can verify that the above quantity is well-defined evaluation metric (Beck 2017). Namely, for
any x² E Rd it holds that (x) 0 if and only if xt is a stationary point of (90), and in special
case when r = O, we have (x) = V fz))
Notations for this section: in this section we re-define 8 del (x²) - Linl
Lemma 13 (Gradient mapping bound). Let 1+1 def
prox,, (x' -oot), then
E || (1=)
2 ||att [1ttt_x'111 x1()
2B || (s(xt))1
(93)
63

---

Under review as a conference paper at ICLR 2022
Proof.
E
||
(x')
1
E
xx
prox (1' -7V (1)
72
| xz [1²]
2
|| prox,, (2' - {>\)(='))
+
72
g2
2
E
1+1
x² [1]]
7
2
pI (xl - -p0))= px' - [Vf(x')) |
+
E
72
<
2
1 ++
x0'1 [1]]
7/2
2
E [I(00* -ru") - -(x" ( (1])
+ 73
2
| x² [1d] + 21 |||ut V
(94)
72
where in the last inequality we apply non-expansiveness of prox-operator.
Lemma 14. Let +1 def
prox,,, (x' qu'), then for any X > O.
o (x') 2X 1100 | (2
L A) 2 (1altl-zt
+ (z)+1)
(95)
Proof. Define f(x) del r(x)+ + 27 || - x' + 700112 and note that rl+1 = arg min {f(x)). Since
F(.) is 1/7 strongly convex, we have
1 | -
F(x') 2 F(a't1)
+
27
r(x')+ + 27
1
1//o/112 2 r(xtt()
|| 1 x² + x00' + 27
1 || - 2211?
27
Thus
r(alt1) - r((²)) 5 - 1att1_
1
- x01
- 1 xz))
(0+,
(96)
By L smoothness of f(-).
1 2141 - x21
f (V) x111 xx²) +
(97)
2
Summing up 977 with (6) we obtain
① (1) 2 (x') z (Vf(z') 0i +11 =z²)
-11-
L
| - 20/13
7
2
< 21 |V(x') - 09112
(
L X
|| =01
7
2
We are now ready to present EF21-Prox and provide its convergence guarantees in general non- convex case.
64

---

Under review as a conference paper at ICLR 2022
1.1 CONVERGENCE FOR GENERAL NON-CONVEX FUNCTIONS
Algorithm 7 EF21-Prox
1: Input: starting point æ R gf E F for = 1,..., n (known by nodes); 9" = n/ -:1=1 9 (known by master); learning rate y
2: for t = 0,1,2...., T - do
3:
Master computes x++1
prox,, y. (x' 79"))
4: for all nodes i = 1, ...., in parallel do
5:
Compress oi = C(V fi (x
g and send of to the master
6: Update local state gf ++ = 9 + c
7: end for
8: Master computes gf = n/ -m g. +1 via gta = g¹ g'+ Eisi
9: end for
10:
Output: Dr chosen uniformly from (e')e(T))
Theorem 12. Let Assumption 7 hold, r(-) be convex and iint infaers ((x) -00. Set the
stepsize in Algorithm 7 as
L L
B
0<9<
70:
(98)
01 a1 s). B = (1 - a) (1 (1+ for any s > O.
where L 12,00,,,-11111
Fix T and let 5² be chosen from the iterates x², ,, ,..., x uniformly random. Then
E [+15((+5)11]
4 4( piul)
2E [GO]
0
1+
(99)
Ty 70
OT
7
(1-
7
3
70
If the stepsize is set to 0 < < S 70/2, then
E
9 [6, (4
||] )
8 8(50 - piul)
2E [G
1
0
(100)
#T
7T. V 3
Proof. First, let us apply Lemma 14 with vf = === ,0,
2X 11 - vf (x') _
A
4 (x+tl) s Φ (z")
2 2 1| - x1122 1
(101)
Subtract Hint from both sides, take expectation, and define d² = $ (x²) -iiuf
G¹
Dim loot V)(("))) Re || - =01 then
-
E [6'] - [ L A E [
E [
-
+
2X E [G*]
(102)
Note that the proof of Lemma does not rely on the update rule for 1++ but only on the way the estimator gf is constructed. Therefore, [14p also holds for the composite case
[
(1 8)E [G*] + si [R*].
(103)
Adding
102 with 28A
multiple of 100 obtain
E
[8++1]
+
1
E [G++]]
<
E
5t
+
1
E
[G*]
+
1 - 0
B [G]]
1
L
A
E
[R*]
28A
2X
20X
7
2
2
+
R
20
E
[5]
+ 28X
E [
(1
X
3
7.2
E
[*]
2
2
2AA
65

---

Under review as a conference paper at ICLR 2022
By summing up inequalities for t- O,.... T 1, arrive at
1 E
1
1
L
8 I
0 H B +
[
S 80
+
E [
Σ
[
E
29X
29A
7
2
20A
Thus
T Σ E
[RR]
x
80
[G"]]
1
L
B 1.2
-1
20A
2
2
20X
(
1
0
1
L
8 +
E [G
1
20
V
BIZ
7
1 B.
(104)
where in the first equality we choose
v V and in the second we detine gor def
80
9
[G] B (7-
L3² 2 v
T22
= =(1
20
DL
7a
By Lemma
13 with ef = g" we have
E
||o,, (s²)
1
Σ
E
[119,
(2t)
T
2
Σ
E
[R-]
+
2
Σ
R
[G]]
PT
T
1=
E Go
2 BL T-1
IE
[1c]]
+
+
Σ E [n¹]
7.2
0
(18)
2F B
2 E [G"]
2 3T2 F B
T
T
T 0
2F B
BL2
2 E Go
T
2F
2 3T
2 E Go
1
Ty
(1
2
0
T
7o
where in (1) we apply Lemma 18 with C def
Bī2, s
def
E
[
r. def
E [R (ti) is due to 104).
Note that for 7
1/4 +
we have
x2
TT.
T
2 S
(105)
0
1 +
Thus
4F
[G9]
E
(1(,(()7)1?
<
T 0
Tn
70
480
2E [G
2E
[G"]
1
0
(106)
2 Ty
OT
Thy
2
0
70
Set 7 S 70/2, then the bound simplifies to
E
(
<
8
2 [G
1+ 7
2
0
7T
OT
3
66

---

Under review as a conference paper at ICLR 2022
Corollary 17. Let assumptions of Theorem 12 hold,
g. V(i("")
i= 1=
(I. 21+2IN10/
-
7
Then, after T iterationsccommunication rounds of EF21-Prox we have [| s
requires
L80
g O
ore2
where T. = / Ei=1 L2, 80 (xx0)
Tinss
Proof.
The proof is the same as for Corollary
1.2 CONVERGENCE UNDER POLYAK-LOJASIEWIIZ CONDITION
In order to extend the analysis of Polyak- Lojakk--ojssiiiizzz functions to composite optimization, we use the following Assumption S from (Li & Li 2018 Wang et al. 2018
Assumption 5
There exists μ 0 such that
[,)]1 2 2/ (T(x) +xx"))
for all x. E Rdd, where x= = arg min, (2x).
Theorem 13. Let Assumptions and 5 hold, r(.) be convex and iiuf = inf 2(x)) > -oo. Ser the stepsize in Algorithm 7 as
{ L 2I,
23
7 S min
(107)
J + OL
Let yt def ((x²) 2(x*) + G² with x = / L. Then for any T 2 0, we have
E [ < (1 ) E E[V"],
(108)
where L / -. L7 0 1 1- (1 a1 s). B (1- a) (1+ for any s 0.
Proof. We start as in the previous proof, but subtract (xx*) from both sides of 101 and define
def Tb (x') 1 (x*). Recall that G Ei l1 v v R² = 1
Then
E [0t+2]
E [8']
L
E
R*
+ - E [G]]
(109)
2
2X
By Lemma we have
E G
(1 0)E
G*
B
[e'|
(110)
Then by adding (109) with Φx multiple of 110 we obtain
67

---

Under review as a conference paper at ICLR 2022
1 E. [Gt+]] E [8t+1] +
0 2
L
A
E [8']
0 +
E
R'
0X
2
1
+
BT.2B RR]
1
1
L
X
3 8N
E
[87]
1
E
G
T
E
R2
AA
7
2
1
0
L
23
E
[8']
1
[[
E
L
E
R*
0A
2)
2
0
(88)
E [88]
E [
E
[
(111)
8X
27
where in (i) we choose À
29
L2, (ii) is due the stepsize choice (the first term in minimum).
Next, combining Assumption with Lemma
we have
2p0 = 2p ($(x²) 2(x²)) = [,,()
72 n + 2G",
and
-R' S -1720' - +
(112)
Thus can be further bounded as
1
E [
= E
g++
+
G++1
01
1
1
s
E
[o"]
1
E
[G"]
-
E [R*]]
0X
27 7/44
E
[00]
1
1
E
|G"
E
+
2
[
0X
2
[1
7/
E
[5t]
+
1
1
0
70X
E
[G*]
0X
2
2
E
8
G
(113)
0X
where the last inequality follows by our assumption on the stepsize (the second term in minimum). It remains to unroll the recurrence.
Corollary 18. Let assumptions of Theorem 13 hold,
g
f(((x))
1, I,..., n,
2B L 2 0
0
7 min
L
+ OL,
28
Then, after T iteratons/commmniccttionn rounds of EF21-Prox have L [f(x*) f(x))] S It requires
T = # O |1 |+ L log osp
80
(114)
tieration/coommuicatiions rounds/gradint computations at each node, where T. V Σ" //E 12.
80 "))>>>"-- -hins_
68

---

Under review as a conference paper at ICLR 2022
Proof. Note that by Lemma 17 we have
1 + L
23
4u +
T, 2/2
S
B
4 | I.
a
The remainder the proof is the same as for Corollary
3
69

---

Under review as a conference paper at ICLR 2022
J USEFUL AUXILIARY RESULTS
J.1 BASIC FACTS
For all a, b, 11.... In R s and p E (0.1) the following inequalities hold
||a|²
s a|1612
(a, b)
2s +
(115)
2
(a b, + b)
||a|?
|1b11
(116)
|al1
|1b11
||a + b11?
(117)
2
||a+
B11?
(1
s][[a[| + (1 1/8)
(118)
2
Σ T2
R
K
1
(119)
12
(1-2) 2
2)
$ 1 1+p. p.
(120)
(1
P 2)
p)
< p 2'
(121)
log (1 p)
S -p.
(122)
Bias-variance decomposition For a random vector & E Id and any deterministic vector æ E R4 the variance of & can be decomposed as
E
[ILE
[[ = E [[]S]]]] ||[[]]]
(123)
Tower property of mathematical expectation. For random variables E, Rd we have
E[E] = B|E[< vl
(124)
under assumption that all expectations in the expression above well-defined.
J.2 USEFUL. LEMMAS
Lemma 15 (Lemma 5 of (Richtárik et al. 2021 If0 S S Votb.
then ar² + by S 1. Moreover,
the bound is tight up to the factor of since Va-b S min { Vo :
1
Vo+b
Lemma 16 (Lemma 2 of (Li et al. 2021). Suppose that function f is T-smooth and let r++1 def
x' - "g' where g" E Rdd is any vector, and 7 > O any scalar. Then we have
f(att)) S s(x') T |
4
=11 ||alt2 -
V
(125)
27
2
Lemma 17 (Lemma 3 of Richtárik et al. 2021 ). Let 0 < < 1 and for > 0 let 0(s) and 3(s) be defined as
B(s) de (1 a)
((s) 1- a) + s),
Then the solution of the optimization problem
((s) 0(s)
a
min
0 < 1-
(126)
is given by s*
1. Furthermore, A(s*) = v1 -1-a B(s*) = 1-a
I-VI-a and
VI-a
B(x*)
v1 a
-
1 < 1.
(127)
((*)
In the trivial case
1. we have 8(o) 8(s)
foror any 0, and 127 is satisfied.
70

---

Under review as a conference paper at ICLR 2022
Lemma 18. Let (arbitrary scalar) non-negative sequences (2'. and fr" satisfy
T-1
T-1
T-1
E
(1
Σ
for some parameters (0, 1]. C
Then for all T
20
0
0
T
p.
(128)
Proof. We have
T-1
T-1
T
8
s/41
0
S
C
1=
T-1
Σ
Dividing both sides by 0 > 0 and rearranging the terms, we get
T-1
0
C T-1
Σ
S
Σ
71


Reviews:
[{"review_id": "gDsSJZnmlez", "reviewer": "Reviewer_DvwK", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "I appreciate the authors' efforts for analyzing EF21 for various settings and provide their convergence results as well as the experimental results. However, it is not clear to me what challenge the paper addresses and novelty the paper presents. All the six variants including stochastic gradient, variance reduction, heavy momentum, partial participation, bidirectional compression, and proximal gradient have been extensively studied in the literature. Merely combining them with EF21 and providing theoretical analyses do not seems novel to me.\n\nEF has worse error bound than the full-precision counterpart when the full gradient is used. However, it has the same asymptotic bound with stochastic gradient. How does EF21-SGD compare to EF-SGD? Does EF21 still yield better bound when stochastic gradient is adopted?\n\nThe aforementioned question is from theoretical side. From empirical side, Figure 7 in the appendix shows that both EF-SGD and EF-SGD-HB converge faster than EF21-SGD and EF21-SGD-HB, respectively. Only the hybrid method EF21+-SGD-HB obtains higher testing accuracy. These seems to contradict the claim that EF21 is better than EF for the stochastic setting. How do we explain these findings?\n\nSome minor comments:\n1. It is clearer to split the updates in Table 2 to worker's and server's, which I think are more friendly to the readers.\n2. $L_j$ in Example 2 should be $L_{ij}$? ", "summary_of_the_paper": "Error feedback (EF) is a technique for ensuring convergence of biased contractive compressor. However, it achieves suboptimal convergence rate when full gradient is used. Recently, EF21 was introduced to mitigate the theoretical deficiencies of EF. This paper studies several extensions of EF21 including EF21 with stochastic gradient, variance reduction, heavy momentum, partial participation, bidirectional compression, and proximal gradient. The paper establishes the convergence results for the six variants and conducts experiments on several small datasets.", "summary_of_the_review": "This paper provides solid theoretical analysis for several EF21 variants. But the novelty is limited.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made 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": "bDVphbUzHaM", "reviewer": "Reviewer_yZfa", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "While the authors definitely did a lot of works, as this is a 70 page paper, the novelty of this work seems to largely depend on EF21. And the main results are obtained by combining the key results in of EF21 with existing analytical techniques such as PAGE and momentum. It is not clear from the main context what are the new analytical breakthrough introduced specifically in this work.\n\nMore experiments are needed to support the theoretical findings. In particular,\n\na) Comparison with other benchmarks is needed since tighter bounds in theory does not necessarily imply better empirical performance.\n\nb) More large-scale experiments should be added. Currently, many logistic regression problems have dimension less than 300.\n\nc) In the ResNet18 experiment, have the authors decreased the step sizes? Typically it is not hard for resnet18 to get a test accuracy more than 90%.\n\nd) One of the goals of communication efficient methods is to make training faster. Communication rounds does not necessarily mean fast in runtime since there are also implementation overhead for (de)compression. Hence, the runtime vs accuracy is also needed in numerical results.", "summary_of_the_paper": "This work studies communication efficient methods by extending EF21 to six more practical settings including momentum, variance reduction, etc. The main results are the convergence rates under these settings. ", "summary_of_the_review": "More discussions are needed to clarify the theoretical novelty, and numerical results should be extended.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made 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": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "aiFr5S3S19v", "reviewer": "Reviewer_2qZ7", "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": "The paper is well-written. The convergence analysis and experiments shows that the proposed algorithms work well in both theory and practice. \nHowever, I have the following concerns:\n1. All the proposed algorithms are extensions of EF21, the overall modification seems minor to me, which weakens the contribution of this paper.\n2. Most importantly, I hardly find the experiment results convincing due to the experiment settings. Most of the datasets and models are small and simple, which typically does not require distributed training (even being trained on CPUs), not to mention communication compression. The results on such simple and small learning problems can barely show the significance of any distributed training algorithm with communication compression. \n3. Even for the largest problems: Resnet on cifar10, is usually considered the smallest one in the distributed scenarios.  On cifar10, although the proposed algorithms shows better test accuracy than the baselines, the baselines have better training loss. Thus, it is hard to justify which algorithm is actually better. Such phenomena is also not explained in the paper.  \n4. A very important baseline is missing in the experiments: SGD without communication compression, which could be compared to the proposed algorithms in the number of epochs. Without such a baseline, it is hard to justify the performance of the proposed algorithms.", "summary_of_the_paper": "In this paper, the authors propose six practical extensions of EF21, with convergence analysis and good experiment results.", "summary_of_the_review": "The paper is well-written, and good in theory and practice. \nHowever, I have some concerns in the contribution and the experiment settings.", "strength_and_weaknesses": "", "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": "Cfi2UxDu7hA", "reviewer": "Reviewer_YjdL", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "This paper studies extended versions of an existing algorithm called EF21, and show its convergence complexity when combined with other techniques, such as momentum, variance reduction, etc. The theoretical analysis is detailed and given for each variant. The analysis on partial participation and proximal settings are new for error-feedback type algorithms.\n\nOverall I have two concerns:\n\n- The paper provides convergence proof for each variant, which is good, however, it's still unclear to me what role EF21 plays on these techniques. More specifically, to me this paper seems to focus on the fundamental question: how would the convergence rate of any existing algorithm adapt if an EF21 gradient oracle is used? For instance, if we want to use both stochastic approximation and momentum (which is usually the case in practice), can we obtain a rate from your analysis without additional proof? \n\n- The experiments seem a little thin. The main experiments are conducted on small scale linear regression problems (where communication is not really an issue). The appendix provides additional results for Resnet18 on CIFAR10. However, only the first few epochs are shown and it's unclear what hypothesis is verified there (Resnet18 should reach 93% test accuracy on CIFAR10). \n\nSome other minor concerns:\n\n- In the abstract (and also in the paper), it's claimed that EF21-BC is better than a previous result from (Tang et al., 2020). But note that in (Tang et al., 2020), stochastic gradient is used while in  EF21-BC, full gradient is still used. So it's not clear whether EF21-BC can really improve the rate if they are compared in the same setting.\n\n- In the comparison to ChocoSGD on page 8, the authors states $G$ usually depends on dimension while $\\sigma^2$ and $\\Delta$ are dimension free, which seems a little off to me. As they are all bounded on the norm, the statements on their orders are unjustified.", "summary_of_the_paper": "This paper studies the extended versions of a previously proposed algorithm called EF21. The paper includes several variants of EF21 such as stochastic optimization, partial participation, variance reduction, momentum, etc. The theoretical analysis for each extension is given and experiments on real world datasets are conducted.", "summary_of_the_review": "Please refer to the main review for the details.\n\nI recommend the authors to update the manuscript to make these points clearer.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made 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": {}}]

Author rebuttal:

Meta-review: This paper presents several variants and extensions (including stochastic and proximal) of the error-feedback method EF21 and provides convergence rates for each of them and shows that they improve upon previous state of the arts. Despite the much broadened application scenarios and SOTA  in convergence rates/complexity, the main and common concern from the reviewers is the novelty of the paper beyond the original EF21 work. There are also concerns on the empirical evaluations that do not fully support the theoretical promises. I agree with the reviewers and regrettably have to recommend rejection for ICLR.
Decision: Reject