Error Feedback Reloaded: From Quadratic to Arithmetic Mean of Smoothness Constants
Authors: Peter Richtárik
Elnur Gasanov
Konstantin Pavlovich Burlachenko
Venue: ICLR 2024 poster (2024)
Keywords: error feedback
greedy sparsification
distributed optimization
communication complexity
machine cloning
weighted error feedback
quadratic mean
arithmetic mean
large stepsizes
Primary area: optimization

Abstract: Error feedback (EF) is a highly popular and immensely effective mechanism for fixing convergence issues which arise in distributed training methods (such as distributed GD or SGD) when these are enhanced with greedy communication compression techniques such as Top-k. While EF was proposed almost a decade ago (Seide et al, 2014), and despite concentrated effort by the community to advance the theoretical understanding of this mechanism, there is still a lot to explore. In this work we study a modern form of error feedback called EF21 (Richtárik et al, 2021) which offers the currently best-known theoretical guarantees, under the weakest assumptions, and also works well in practice. In particular, while the theoretical communication complexity of EF21 depends on the quadratic mean of certain smoothness parameters, we improve this dependence to their arithmetic mean, which is always smaller, and can be substantially smaller, especially in heterogeneous data regimes. We take the reader on a journey of our discovery process. Starting with the idea of applying EF21 to an equivalent reformulation of the underlying problem which (unfortunately) requires (often impractical) machine cloning, we continue to the discovery of a new weighted version of EF21 which can (fortunately) be executed without any cloning, and finally circle back to an improved analysis of the original EF21 method. While this development applies to the simplest form of EF21, our approach naturally extends to more elaborate variants involving stochastic gradients and partial participation. Further, our technique improves the best-known theory of EF21 in the rare features regime (Richtárik et al, 2023). Finally, we validate our theoretical findings with suitable experiments.

Published as a conference paper ICLR 2024
ERROR FEEDBACK RELOADED: FROM QUADRATIC TO ARITHMETIC MEAN OF SMOOTHNESS CONSTANTS
Peter Richtárik
Elnur Gasanov
Konstantin Burlachenko AI Initiative
AI Initiative
AI Initiative
KAUST; Saudi Arabia
KAUST, Saudi Arabia
KAUST, Saudi Arabia
ABSTRACT
Error Feedback (EF) is a highly popular and immensely effective mechanism for fixing convergence issues which arise in distributed training methods (such as distributed GD or SGD) when these are enhanced with greedy communication compression techniques such as TopK. While EF was proposed almost decade ago (Seide et al., 2014), and de- spite concentrated effort by the community to advance the theoretical understanding of this mechanism, there is still a lot to explore. In this work we study a modern form of error feedback called EF21 (Richtárik et al. (022)) which offers the currently best-known theoretical guarantees, under the weakest assumptions, and also works well in practice. In particular, while the theoretical communication complexity of EF21 depends the quadratic mean of certain smoothness parameters, we improve this dependence to their arithmetic mean, which is always smaller, and can be substantially smaller, especially in heterogeneous data regimes. We take the reader on a journey of our discovery process, Starting with the idea of applying EF21 to an equivalent reformulation of the underlying problem which (unfortunately) requires (often impractical) machine cloning. we continue to the discovery of a new weighted version of EF21 which can (fortunately) be executed without any cloning, and finally circle back to an improved analyvis of the original EF21 method. While this development applies to the simplest form of EF21, our approach naturally extends to more elaborate variants involving stochastic gradients and partial par- ticipation. Further, our technique improves the best-known theory of EF21 in the rare features regime (Richtárik et al. 2023). Finally, validate theoretical findings with suitable experiments.
1 INTRODUCTION
Due to their ability to harness the computational capabilities of modern devices and their capacity to extract value from the enormous data generated by organizations, individuals, and various digital devices and sen- sors, Machine Learning (ML) methods (Bishop) 2016; Shalev-Shwarte & Ben-Davee
2014) have become
indispensable in numerous practical applications (Krizheskyy et al.) 2012) Lin et al. 2022 Vaswani et al.,
2017
Onay & Öztürk 2018 Poplin al. 2017 Gavriluç et al. 2009: Sun et al. 2017).
The necessity to handle large datasets has driven application entities to store and process their data in power- ful computing centers (Yang et al. 2019: Dean al. 2012) Verbraeken et al.) 2020) via distributed training algorithms. Beside this industry-standard centralized approach, decentralized forms of distributed learning are becoming increasingly popular. For example, Federated Learning (FL) facilitates a collaborative learn- ing process in which various clients, such as hospitals or owners of edge devices, collectively train a model
KKing Abdullah University of Science and Technology

---

Published as a conference paper ICLR 2024
on their devices while retaining their data locally, without uploading it to a centralized location (Konečný
et al. 2016b a McMahan et al.
2017 Li et al. 2020a Kairouz et al. 2021 Wang et al. 2021)
Distributed training problems are typically formulated as optimization problems of the form
min #ER
f(x) = 1 f(()) ((()
where n is the number of clients/workers/noddss vector x E IR represents the d trainable parameters, and fz(z) is the loss of the model parameterized by the training data stored on client i E [m]] -= {1...., nn. One of the key issues in distributed training in general, and FL in particular, is the communication bottle- neck (Konečný et al. 2016b Kairouz al.) (021). The overall efficiency of distributed algorithm for solving (1) can be characterized by multiplying the number of communication rounds needed to find a solu- tion of acceptable accuracy by the cost of each communication round:
communication complexity
communication rounds x cost of I communication round. (2)
This simple formula clarifies the rationale behind two orthogonal approaches to alleviating the communica- tion bottleneck. i) The first approach aims minimize the first factor in 2 This is done by carefully de- ciding on what work should be done on the clients in each communication round in order for to reduce the total number of communication rounds needed, and includes methods based on local training (Stich 2018 Lin et al. 2018 Mishchenko et al. 2022; Condat et al. [023 Li et al., (019) and momentum (Nesterov 1983 2004; d' Aspremont et al. 2021). Methods in this class communicate dense d-dimensional vectors. ii The second approach aims to minimize the second factor in (2). Methods in this category compress the
information (typically d-dimensional vectors) transmitted between the clients and the server (Alistarh et al.,
2017
Khirirat et al., 2018 Bernstein et al. 2018 Safaryan et al. 2021).
1.1
COMMUNICATION COMPRESSION
Vector compression can be achieved through the application of compression operator. Below, we outline two primary classes of these operators: unbiased (with conically bounded variance) and contractive.
Definition (Compressors). A randomized mapping C Rd + Rd is called i) an unbiased compressor if for some 0 it satisfies
E [[([)]] =x, E [[[C(x) - x1 =13]] S W|| Vz e
(3)
and ii) a contractive compressor if for some E (0, 1] it satisfies
||[((=) - -|| S (1 (1--00 [=)[=== Vo E
is well known that whenever a compressor C satisfies ( then the scaled compressor C/(w + 1) satisfies 4 with a = (w + 1) In this sense, the class of contractive compressors includes all unbiased compressors as well. However, it is also strictly larger. For example, the Topk compressor, which retains the K largest elements in absolute value of the vector it is applied and replaces the rest by zeros, and happens to be very powerful in practice (Alistarh et al. 20188. satisfies 4 with a = K. but does not satisfy 3.. From now on, we write C(a) denote the class of compressors satisfying (4).
d
It will be convenient to define the following functions of the contraction parameter
0 - ((a)
vI a; = =[a) トー E <
1+v1=a 1. (5) ((a)
Bla)
a
Note that 0 < E(a) < - 1. The behavior of distributed algorithms utilizing unbiased compressors for solving (T is relatively well-understood from a theoretical standpoint (Khirirat et al., 2018, Mishchenko ct al. 2019 Li et al. [220bb] Gorbunov et al. 2021] Tyurin & Richtárik] 2023). By now, the community possesses a robust theoretical understanding of the advantages such methods can offer and the mechanisms behind their efficacy (Gorbunovv al. 2020 Khaled et al. 2023 Tyurin & Richtárik] 2023). However, it is well known that the class of contractive compressors includes udes some practically very powerful operators, such the greedy sparsifier TopK (Stich et al. 2018 Alistarh al. 2018) and the low-rank approximator Rank K
2

---

Published as a conference paper ICLR 2024
Algorithm 1 EF21: Error Feedback 2021
1: Input: initial model xº R2; initial gradient estimates g.. .2........ .........0...................... g..
R stored at the server and the
clients; stepsize ?. > 0; number of iterations T
2: Initialize: g" Σ - o.¹ on the server
3: for f 0, 1,2..... T do
4: Server computes x'+1 x²' 7g and broadcasts x+11 to all clients
5: io 1,...... n on the clients in parallel do
6:
Compute uf = (V (+ gf) and update 9i o/+1 96 + ut
7: Send the compressed message u, to the server
8: end for
9: Server updates of = of + ut for all i E [n)] and computes g =E=19
10: end for
11:
Output: Point aT chosen from the set (x ..... .........--.. TT uniformly at random
2022), which are biased, and hence their behavior not explainable by the above developments. These compressors have demonstrated surprisingly effective performance in practice (Seide et al. 2014; Alistarh et al. 2018), even when compared to the best results we can get with unbiased compressors (Szlendak et al. 2022). and are indispensable difficult tasks such the fine-tuning of foundation models in geographically distributed manner over slow networks (Wang et al. 2023).
Vogels et al.; 2019; Safaryan et al.
However, our theoretical understanding of algorithms based on contractive compressors in general, and these powerful biased compressors in particular, is very weak. Indeed, while the SOTA theory involving unbi- ased compressors offers significant and often several- wfggees--of-aaniiee
improvements over the baseline
methods that do not use compression (Mishchenko et al. 2019 Horváth et al. (019b] Li et al.) [020b] Gor- bunov et al. 2020; 2021 Tyurii & [ the best theory we currently have for methods that can provably work with contractive compressors, i.e., the theory behind the error feedback method called EF21 developed by |Richtárik et al. (02T) (see Algorithm [ and its variants (Fatkhullin et al. 2022 Condat et al., 2022 Fatkhullin et al. 2023). merely matches the communication complexity of the underlying methods that do not use any compression (Szlendak et al., 2022).
To the best of our knowledge, the only exception to this is the very recent work of Richtárik et al. (0223) showing that in a rare features regime, the EF21 method (Richtárik et al. 2021) outperforms gradient descent (which is special case of EF21 when (z) x for all E [m]] and f 2 in theory. However, Richtárik ct al. (2023) obtain no improvements upon the current best theoretical result for vanilla EF21 (Richtárik
2021 in the general smooth nonconvex regime, outlined in Section 1.2 we investigate in this work. et
1.2
ASSUMPTIONS
We adopt the same very weak assumptions as those used by Richtárik et al. (2021) in their analysis of EF21. Assumption 1. The function f is L-smooth, i.e., there exists > such that
[[) f(y)) & L. || - yll, Vx, E TRd Assumption 2. The functions fr are L.-sohoth, i.e., for all i E [n]] there exists Lg >> 0 such that
(6)
(()) fv(ill < L, || yll Va, y Rdd.
(7)
L, So, Assumption I does not further limit the class of functions already covered by Assumption Indeed, it merely provides a new parameter better characterizing the smoothness of than the estimate TAA obtainable from Assumption 2 could.
Note that if (7) holds, then 6 holds, and L < LAM
2
Since our goal in T is to minimize f. the below assumption is necessary for the problem to be meaningful.
Assumption 3. There exists f E R such that inf f 2 f"
3

---

Published as a conference paper ICLR 2024
1.3 SUMMARY OF CONTRIBUTIONS
our work we improve the current SOTA theoretical communication complexity guarantees for distributed algorithms that work with contractive compressors in general, and empirically powerful biased compressors such as Top and RankK particular (Richtárik et al. 2021 Fatkhullin al. 2021).
In particular, under Assumptions the best known guarantees were obtained by Richtárik et al. (022)
for the EF21 method: to find (random) vector s" satisfying E [|*)()))|) - E. Algorithm requires
T O (QM((a)e==)
iterations, where LQM = + L3 is the Quadratic Mean of the smoothness constants L Li...., Ln- Our main finding is improvement of this result to
T= O ((T. + LAME(a))e="),
(8)
where LAM = 1 Ei= Li is the Arithmetic Mean of the smoothness constants Lı,..., Inn. We obtain this improvement in three different ways:
i) by client cloning (see Sections 2.1 and 2.2 and Theorem 2
ii) by proposing new smoolneex--wigghted variant of EF21 which we call EF21-W (see Section and Theorem 3), and
iii by new smoothness- analysis of classical EF21 (see Section 2.4 and Theorem
We obtain refined linear convergence results cases under the Volyak-Lojasiewir condition. Further, analysis technique extends to many variants of EF21, including EF21-S which uses stochastic gradients instead of gradients (Section[E) E.. and EF21-PP which enables partial participation of clients (Section(G). Our analysis also improves upon the results of Richtárik et al. (2023) who study EF21 in the rare featuress regime (Section H). Finally, validate our theory with suitable computational experiments (Sections) and
2 EF21 RELOADED: OUR DISCOVERY STORY
We now take the reader along on a ride of our discovery process.
2.1
STEP 1: CLONING THE CLIENT WITH THE WORSE SMOOTHNESS CONSTANT
The starting point of our journey is simple observation described in the following example.
Example Let n = and f(x) = (f) + f2(x) + fa(x) + f4(r)). Assume the smoothness constants L,, L2, Ls of fI, f2, are equal to I, and La equal 100. In this case,EF21 needs run for
Ti = ((I. T-quE(a))==t)) = ((T+ + (2501.5E(a)) -5(a)))-1)
iterations. Now, envision the existence of an additional machine capable of downloading the data from the fourth "problematic" machine. By rescaling local loss functions, we maintain the overall loss function as:
f(x)
f((=) = (ff1(x) ff((z) + 2 ff(()) fa())) ffa(z)) = f(x).
Rescaling of the functions modifies the smoothness constants L; Lor 1,2,3, and L. 3 for i = 4, EF21, launched on this setting of five nodes, requires
To ===0 O (LL((a)()))
~ (=64)(()))=
iterations, where LoM is the quadratic mean of the smoothness constants i,,..., L.g.
4

---

Published as conference paper ICLR 2024
This simple observation highlights that the addition of just one more client significantly enhances the con- vergence rate. Indeed, EF21 requires approximately {( (V2501.5 v1564) z 10 fewer iterations. We will generalize this client cloning idea in the next section.
2.2 STEP 2: GENERALIZING THE CLONING IDRA
We will now take the above motivating example further, allowing each client i to be cloned arbitrarily many (N;) times. Let us see where this gets us. For each [n], let N; denote a positive integer. We define
N = Ei=1 N₂ (the total number of clients after cloning), and observe that f can be equivalently written
[(x)
Σ - E M(x))
N
N W..
[(=)
ΣΣ So(r),
N.
(9)
where f1z(2) nN, f(()) for all [n]
and j [N:]. Notice that we scaled the functions before, and N
that fiy is Ly-smmothh, where Lij- = n.N. Li
Analysis of the convergence rate. The performance of EF21, when applied to the problem p clients, depends on the quadratic mean of the new smoothness constants:
involving N
M(N, N.) =
N
12
Σ
R 1
1. N.NN
(10)
Note that if N; 1 for all [ni], then .I,...., 1) LQM-
Optimal choice of cloning frequencies. Our goal is to find integer values N1 E E E,..., N₂ E minimizing defined in (1O). While we do not have closed-form formula for the global
.....,,,
the function M (NN..... M,) minimizer, we are able explicitly find solution that is most /2 times worse than the optimal one in terms of the objective value. In particular, if we let N = [</Laaa] for all i E [Tt], then
LAM S min
( N.. S (N NW S V2LAM N₁ NN.EN....N..C N.
and moreover, n. & N = Σ, N < 2n. That is, we need at most double the number of clients in our client cloning construction. See Lemma 2 in the Appendix for details.
By directly applying EF21 theory from Richtárik et al. 2021 to problem obtain the advertised improvement from LQM LAM-
p involving N clients, we
Theorem (Convergence of EF21 applied to problem
with N machines). Consider Algorithm ? (9) the the distributed optimization problem ( where N
(EF21) applied to the "cloning reformulation"
L./T.w for all i E [n]. Let Assumptions hold, assume that C₁2y E C((i) for all i E [m), E [N:] and 0, sei
Gt
9 (lag(xt))1
and let the stepsize satisfy 0 <7 S L+V2LAME(a)
If for T 2 we define if element of the set fx x ..... ....,IT-II TT1 chosen uniformly at random, then
|
2(f(2 )- 5*)
72
D(TTT
When choose the largest allowed stepsize and of (iz((.)) for all i,j, this leads to the complexity 8); that is, by cloning client machines, we can replace LQM in the standard rate with V2LAM- similar result can be obtained even if we do not ignore the integrality constraint, but we do not include it for brevity
5

---

Published as a conference paper ICLR 2024
reasons. However, is important note that the cloning approach has several straightforward shortcomings, which we will address in the next section
2.3 STEP 3: FROM CLIENT CLONING TO UPDATE WEIGHTING
is evident that employing client cloning improves the convergence rate. Nevertheless, there are obvious drawbacks associated with this approach. Firstly, it necessitates larger number of computational devices, rendering its implementation less appealing from a resource allocation perspective. Secondly, the utiliza- tion of EF21 with cloned machines results in departure from the principles of Federated Learning, it inherently compromises user privacy- transferring data from one device to another is prohibited FI..
However, simpler approach implementing the cloning idea emerges when assume the compressors used to be deterministic. To illustrate this, let us initially examine how we would typically implement EF21 with cloned machines: x = r¹ 7
(11)
S = -ie + C V fi fzy - Kiy), iE [n], jE [Na].
(12)
We will now rewrite the same method in a different way. Assume we choose Ii = oe for all j E [N:]- We show by induction that زig is the same for all j [N:]. We have just seen that this holds for = 0. Assume this holds for some f. Then since (ay nN. (1 for all [N,] combined with the induction hypothesis, (12) and the determinism of Cij. we see that 1+1 is the same for all j E [Ni]] Let us define of = gig for all t. This is valid definition since we have shown that giy does not depend on j. Because of all of the above, iterations
12) can be equivalently written in the form
x1
w.gt
(13)
9; = of + C (/( of), i i (n),
++1
(14)
L. where w; = E, 4," This transformation effectively enables us to operate the method on the original n clients, climinating the need for N clients! This refinement has led to the creation of new algorithm that outperforms EF21 in terms of convergence rate, which we call EF21-W (Algorithm [ While we relied on assuming that the compressors are deterministic in order motivate the transition from N to clients, it turns out that EF21-W converges without the need to invoke this assumption. Theorem (Theory for EF) Consider Algorithm (EF21 applied to the distributed optimization problem ①
Let Assumptions 73 hold, assume that C₁ E C(a) for all i E [ni] and 2 O, set
G¹ =
w
TEM f((x
'In our work, we address an optimization problem of the form min,, 20 resent certain constants. This formulation bears a resemblance to the meta problem in the importance sampling strategy discussed in (Zhao & Zhang 2015). Despite the apparent similarities in the abstract formulation, our approach and the one in the referenced work diverge significantly in both motivation and implementation. While & Zhang (2015) ap- plies importance sampling reduce the variance of stochastic gradient estimator by adjusting sampling probabilities, our method involves adjusting client cloning weights without sampling. Furthermore, our gradient estimator is biased, unlike the unbiased estimator in the referenced paper, and we aim to minimize the quadratic mean of the smoothness constants, which is inherently different from the objectives in Zhao & Zhang (2015). Although both approaches can be expressed through similar mathematical framework, they are employed in vastly different contexts, and any parallelism may be coincidental rather than indicative of direct connection.
w0.=1 Er wi where a, rep-
6

---

Published as conference paper ICLR 2024
Algorithm 2 EF21-W: Weighted Error Feedback 2021
1: Input: initial model parameters x E R2; initial gradient estimates g .2.92. 92.................... ..... 9h E stored the server and the clients; weights Wi; = Ix/E, Ly; stepsize y > 0; number iterations
2: Initialize: g6 - = w.g. on the server
3: for t 0, 1,
T T-
do
4: Server computes x²+1 = x 77" and broadcasts x 1 to all n clients
the clients in parallel do 6: Compute u = C [s('+++) o.) and update of = of - uf
5: for .....,.
7: Send the compressed message u to the server
8: end for
9: Server updates of 9f + uf for all i [n], and computes g Ei= wig, ++1
10: end for
11:
Output: Point g² chosen from the (x² ...., ........---y -T uniformly random
where w,
L. E for all E [n], and let the stepsize satisfy 0 < S L-Lams(aa) ffr T we define
it as an element of the set {a x x..., chosen uniformly at random, then
E [
2(f(x)) G 7T
(15)
D(aTT
2.4 STEP 4: FROM WEIGHTS IN THE ALGORITHM TO WEIGHTS IN THE ANALYSIS
the preceding section, we introduced novel algorithm: EF21-W. While it bears some resemblance to the vanilla EF21 algorithm (Richtárik al. [021] (we recover it for uniform weights), the reliance on particular non-uniform weights enables it to achieve a faster convergence rate. However, this is not the end the story another insight reveals yet another surprise.
Let us consider the scenario when the compressors in Algorithm are positively homogeneous Introducing the variable hę nw.g. we can reformulate the gradient update in Algorithm to
h [+1 nogg
TWW;; gf + C₁
[((la*)) st) = a + CV(V)(('') - ht),
indicating that h adheres to the update rule of the vanilla EF21 method! Furthermore, the iterates x' also follow the same rule as EF21:
w = x²
w -
So, what does this mean? One interpretation suggests that for positively homogeneous contractive compres- sors, the vanilla EF21 algorithm is equivalent to EF21-W, and hence inherits its faster convergence rate that depends on LAM rather than on LQM- However, it turns out that we can establish the same result with- out having to resort to positive homogeneity altogether. For example, the "natural compression" quantizer, which rounds to one of the two nearest powers of two, is not positively homogeneous (Horváth et al. 2019a). Theorem 4 (New theory for EF21). Consider Algorithm (EF21) applied the distributed optimization problem Let Assumptions
hold. assume that C E ((a) for all i E [n]] and 2 0, set
G :==a
llo - Vf((>'11
AA compressor C: Rdd Bdd is positively homogeneous if C(tx) (C(xr) for all > 0 and Rd
7

---

Published as conference paper ICLR 2024
where wi = - for all E [n], and let the stepsize satisfy 0 y I T-TAME(a)) If T 1 we define
Ie as an element of the set {a x.....,'"" x""-1} chosen uniformly at random, then
E V (
|| = 2(f(a))
77 +
B(a)T
G
(16)
This last result effectively pushes the weights from the algorithm in EF21-W to the proof, which enabled us show that the original EF21 method also enjoys the same improvement: from LQm LAM-
3 EXPERIMENTS
3.1 NON-CONVEX LOGISTIC REGRESSION ON BENCIIARK DATASETS
our first experiment, we employed logistic regression model with non-convex regularizer, i.e.,
fi(x) = + Σ log (1 exp(-wo a.f=)) +
where (asj. yeg) Ed x [-1,1] represents the j-th data point out from a set of n, data points stored client i, and X > denotes a regularization coefficient. We utilized six datasets from LIBSVM (Chang &
Lin T01T). The dataset shuffling strategy, detailed Appendix [.5], was employed to emulate heterogeneous
data distribution. Each client was assigned the same number of data points. Figure I providee comparison
between EF21 employing the original stepsize (Richtárik et al. 202 and EF21-W with the better stepsize. The initial gradient estimators were chosen g.¹ (zizz") for all E [n]] As evidenced empirically, the EF21-W algorithm emerges as a practical choice when utilized situations characterized by high variance in smoothness constants. As evident from the plots, the algorithm employing the new step size exhibits superior performance compared to its predecessor.
Next, conducted comparative analysis of the performance of EF21-W-PP and EF21-W-SGD, elu- cidated in the appendix, compared to their non-weighted counterparts. In the AF21-PPPEFF1-W- algo- rithms, each client participated independently in each round with probability P: 0.5. Moreover, in the case of EF21-SGD/EF21 -W-GG algorithms, a single data point was stochastically sampled from a uniform distribution each client during each iteration of the algorithm. As observed in Figure 2 the algorithms employing the new learning rates demonstrate faster convergence. Notably, Figure (c) depicts more pro- nounced oscillations with updated step sizes, as the new analysis permits larger step sizes, which can induce oscillations in stochastic methods.
3.2 NON-CONVEX LINEAR MODEL ON SYNTHETIC DATASETS
our second set of experiments, we trained a linear regression model with a non-convex regularizer. The function f. for the linear regression problem is defined as follows: f((x) = n; |A, b +> 2 - 3
x²
Here, A, E xd and b; E RT represent the feature matrix and labels stored on client i encompassing ny data points. The data employed in four experiments, as illustrated in Figure R] was generated in such manner that the smoothness constant L remained fixed, while L, varied so that the difference between two crucial analysis terms LQM and LAM changed from relatively large value negligible. As evident from Figure 3] the performance of EF21-W consistently matches or surpasses that of the original EF21, particularly in scenarios characterized by significant variations the smoothness constants. For additional details and supplementary experiments, we refer the reader to Sections [ [
8

---

Published as conference paper ICLR 2024
Viaii
aide
1600
(a) AUSTRALI AN, Tryar 10'6
(b) w1 A, Tvar
3.28
(c) W..., Traa 2 2.04
1001
1180
2200
2008
(e) MUSHRCOMS, Lear R 5 10 (1) PHISHING, Lyar = 9 x 10
(d) W3A, Lyar Rs 1.58
Figure 1: Comparison of EF21 versus
EF21-W with the Top1 compressor the non-convex logistic regression
problem. The number of clients is 1, 000. The step size for EF21 set according to (Richtárik al. (20T), and the step size EF21-W set according to Theorem 3 The coefficient À for (f)- is set 0.001, and for (a) set 000 for numerical stability. We Livar
LaM
LAM
EE
( Em L.)
H921 WHE
10
0721-820
0F23-F
2044
40003
20830
(a) W1A SGD
(b) WIA PP
(c) AUSTRALIAN, SGD
(d) AUSTRALIAN, PP
Figure 2: Comparison EF21-W with partial partial participation (EF21-W-PP) or stochastic gradients (EF21-W-SGD)
versus EF21 with partial partial participation (EF21-PP) or stochastic gradients (EF21-SGD) (Fatkhullin et al. 202T). The Top1 compressor was employed in all experiments. The number of clients 1, 000. All stepsizes are theoretical. The coefficient À was to 0.001 for (a). (b) and to 1, 0000 for (c), (d).
U.C.
12:51
3008
2000
1800
A003
10l0
2500
(a) Lvar R3 1.4 x 10 LoM R 2126, LAM Ru 252
(b) Lear 1.9 x 105
(c) Lovas R 1.0 x 10 Lou R 433, LAM P 280
(d) Lear R 5.4 10a Lou R 294, TAX R2 285
LQM Rs 1431, FAM Rs 263
Figure 3: Comparison of EF21 vs. EF21-W with the Topl compressor on the non-convex linear problem. The number of clients is 2, 000. The coefficient À has been 100. The step size for EF21 is according (Richtárik et al. 202T), and the step size for EF21-W set according to Theorem all cases, smoothness constant equals 50.
9

---

Published as conference paper ICLR 2024
ACKNOWLEDGEMENTS
This work of all authors was supported by the KAUST Baseline Research Scheme (KAUST BRF). The work Peter Richtárik and Konstantin Burlachenko was also supported by the SDAIA-KAUST Center of Excellencee in Data Science and Artificial Intelligence (SUAIA-KAUST AI). We wish to thank Babis Kostopoulos- VSRP intern at KAUST who spent some time working on this project in Summer 2023 helping with some parts of the project. We offered Babis co-authorship, but he declined.
REFERENCES
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. QSGD: Communication efficient SGD via gradient quantization and encoding. In Advances in Neural Information Processing Systems, 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, 2018.
Jeremy Bernstein, Yu-Xiang Wang, Kamyar Azizzadenesheli, and Animashree Anandkumar. signsgd: Com- pressed optimisation for non-convex problems. In International Conference on Machine Learning, pp- 560-569. PMLR, 2018.
C.M. Bishop. Pattern Recognition and Machine Learning. Information Science and Statistics. Springer New York, 2016. ISBN 9781493938438. URL htttps://books..... wow.oooooooooe.....ooooooooooooe com sa/dooks?id
kOXDLAFACAAJ
Konstantin Burlachenko, Samuel Horváth, and Peter Richtárik. Fl pytorch: optimization research simulator for federated learning. In Proceedings of the 2nd ACM International Workshop on Distributed Machine Learning, pp. 1-7, 2021.
Chih-Chung Chang and Chih-Jen Lin. LIBSVM: a library for support vector machines. ACM Transactions on Intelligent Systems and Technology (TIST), 2(3):1-27, 2011.
Laurent Condat, Kai Yi, and Peter Richtárik. EF-BV: unified theory of error feedback and variance reduction mechanisms for biased and unbiased compression in distributed optimization. In Advances in Neural Information Processing Systems, volume 35, 2022.
Laurent Condat, Grigory Malinovsky, and Peter Richtárik. Tamuna: Accelerated federated learning with local training and partial participation. arXiv preprint arXiv:2302.09832. 2023.
Alexandre d' Aspremont, Damien Scieur, and Adrien Taylor. Acceleration methods. Foundation and Trends in Optimization, 5(1-2):1-245 2021.
Jeffrey Dean, Greg Corrado, Rajat Monga, Kai Chen, Matthieu Devin, Mark Mao, Mare' aurelio Ranzato, Andrew Senior, Paul Tucker, Ke Yang, et al. Large scale distributed deep networks. Advances in Neural Information Processing Systems, 25, 2012.
Ilyas Fatkhullin, Igor Sokolov, Eduard Gorbunov, Zhize Li, and Peter Richtárik. EF21 with bells & whistles: Practical algorithmic extensions of modern error feedback. arXiv preprint 10.02:21 2021.
Ilyas Fatkhullin, Alexander Tyurin, and Peter Richtárik. Momentum provably improves emror feedback! In Advances in Neural Information Processing Systems, volume 36, 2023.
10

---

Published as a conference paper ICLR 2024
Dragoş Gavrilut, Mihai Cimpoeşu. Dan Anton, and Liviu Ciortuz. Malware detection using machine learn- ing. In 2009 International Multiconference on Computer Science and Information Technology, pp. 735- 741. IEEE, 2009.
Eduard Gorbunov, Filip Hanzely, and Peter Richtárik. A unified theory of SGD: Variance reduction, sam- pling, quantization and coordinate descent. In The 23rd International Conference on Artificial Intelligence and Statistics, 2020.
Eduard Gorbunov, Konstantin Burlachenko, Zhize Li, and Peter Richtárik. MARINA: Faster non-convex distributed learning with compression. In 38th International Conference on Machine Learning, 2021.
Samuel Horváth, Chen-Yu Yu Ho, Ludovít Horváth, Atal Narayan Sahu, Marco Canini, and Peter Richtárik. Natural compression for distributed deep learning. arXiv preprint 1905: 2019a.
Samuel Horváth, Dmitry Kovalev, Konstantin Mishchenko, Sehastian Stich, and Peter Richtárik. Stochastic distributed learning with gradient quantization and variance reduction. arXiv preprint arXiv:1904.05115, 2019b.
Samuel Horváth, Chen-Yu Ho, Ludovit Horvath, Atal Narayan Sahu, Marco Canini, and Peter Richtárik. Natural compression for distributed deep learning. In Mathematical and Scientific Machine Learning, pp- 141, PMLR, 2022.
IEEE Computer Society. IEEE Standard for Floating-Point Arithmetic. Technical report, IEEE, 2008. URL https://eeexplocee.c ieee. wwt. www.ddcccmeeennnncceeeee IEEE Std 754-2008.
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjum Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Advances and open problems in federated learning. Foundations and Trends@ in Machine Learning, 14(1-2):1-210, 2021.
Ahmed Khaled and Peter Richtárik. Better theory for SGD in the nonconvex world. Transactions on Machine Learning Research, 2022.
Ahmed Khaled, Othmane Sebbouh, Nicolas Loizou, Robert M. Gower, and Peter Richtárik. Unified analysis of stochastic gradient methods for composite convex and smooth optimization. Journal of Optimization Theory and Applications, 2023.
Sarit Khirirat, Hamid Reza Feyzmahdavian, and Mikacl Johansson. Distributed learning with compressed gradients. arXiv preprint 1rXiv:1806.06573. 2018
Jakub Konečný, H. Brendan McMahan, Daniel Ramage, and Peter Richtárik. Federated optimization: dis- tributed machine learning for on-device intelligence. arXiv:1610.02527, 2016a.
Jakub Konečný, H. Brendan McMahan, Felix Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Ba- con. Federated learning: strategies for improving communication efficiency. In NIPS Private Multi-Party Machine Learning Workshop, 2016b.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolutional neural networks. In Advances in Neural Information Processing Systems, volume 25, 2012.
Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learning: Challenges, methods, and future directions. IEEE Signal Processing Magazine, 37:50-60 2020a.
Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang. On the convergence of FedAvg on non-iid data. arXiv preprint arxiv: 2019.

---

Published as a conference paper ICLR 2024
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, 2020b.
Zhize Li, Hongyan Bao, Xiangliang Zhang, and Peter Richtárik. PAGE: A simple and optimal probabilis- tic gradient estimator for nonconvex optimization. In International Conference on Machine Learning (ICML), 2021.
Stephanie Lin, Jacob Hilton, and Owain Evans. TruthfulQA: Measuring how models mimic human false- hoods. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 3214-3252, Dublin, Ireland, May 2022. Association for Computational Linguistics. doi: acl-long 229
URL
Tao Lin, Sebastian Stich, Kumar Kshitij Patel, and Martin Jaggi. Don't use large mini-batches, use local SGD. arXiv preprint arXiv: 07000, 2018.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-efficiii learning of deep networks from decentralized data. In Artificial intelligence and statistics, pp. 1273-1282. PMLR, 2017.
Konstantin Mishchenko, Eduard Gorbunov, Martin Takáč, and Peter Richtárik. Distributed learning with compressed gradient differences. arXiv preprint arXiv: 2019.
Konstantin Mishchenko, Grigory Malinovsky, Sebastian Stich, and Peter Richtárik. Proxskip: Yes! Local gradient steps provably lead to communication acceleration! Finally! In International Conference on Machine Learning. pp. 15750-15769, PMLR, 2022.
Yurii Nesterov. A method for unconstrained convex minimization problem with the rate of convergence o (I/k" 2), 1983.
Yurii Nesterov. Introductory lectures on convex optimization: a basic course (Applied Optimization). Kluwer Academic Publishers, 2004.
Ceylan Onay and Elif Öztürk. A review of credit scoring research in the age of big data. Journal of Financial Regulation and Compliance, 305)):382-00, 2018.
Ryan Poplin, Avinash V. Varadarajan, Katy Blumer, Yun Liu, Michael V. McConnell, Gregory S. Corrado, Lily Peng, and Dale R. Webster. Predicting cardiovascular risk factors from retinal fundus photographs using deep learning. arXiv preprint arXiv: /70Xv 09843, 2017.
Peter Richtárik, Igor Sokolov, and Iyas Fatkhullin. EF21: new, simpler, theoretically better, and practi- cally faster error feedback. In Advances in Neural Information Processing Systems, volume 34, 2021.
Peter Richtárik, Elnur Gasanov, and Konstantin Burlachenko. Error feedback shines when features are rare. arXiv preprint 2rXhv:2305.15264 2023.
Mher Safaryan, Egor Shulgin, and Peter Richtárik. Uncertainty principle for communication compression in distributed and federated learning and the search for optimal compressor. Information and Inference: A Journal of the IMA, 11(2):557-58) 04 2021. ISSN 2049-8772. doi: 10.1093/maiia/raab006 URL
hnttps://dol http://tto....g/..///// 10931 htt.://///......//aaaaaaaaa/aaa /
Mher Safaryan, Rustem Islamov, Xun Qian, and Peter Richtárik. FedNL: Making Newton-type methods applicable to federated learning. In Internatioanl Conference Machine Learning. 2022.
12

---

Published as a conference paper ICLR 2024
Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu. 1-bit stochastic gradient descent and its application to data-paratl distributed training of speech DNNs. In Fifteenth Annual Conference of the International Speech Communication Association, 2014.
S. Shalev-Shwartz and S. Ben-David. Understanding Machine Learning: From Theory to Algorithms. Un- derstanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014, ISBN 9781107057132 httthtts:
google. com. sa/books LanooosssdddtttAAAAAOAO
Sebastian U Stich. Local SGD converges fast and communicates little. arXiv preprint arXiv:1805.0976) 2018.
Sehastian U. Stich, J.-B. Cordonnier, and Martin Jaggi. Sparsified SGD with memory. In Advances in Neural Information Processing Systems, 2018.
Yu Sun, Yuan Liu, Guan Wang, Haiyan Zhang, al. Deep learning for plant identification in natural environment. Computational Intelligence and Neuroscience, 2017.
Rafal Szlendak, Alexander Tyurin, and Peter Richtárik. Permutation compressors for provably faster dis-
tributed nonconvex optimization. In International Conference on Learning Representations, 2022.
Alexander Tyurin and Peter Richtárik. DASHA: Distributed nonconvex optimization with communication compression and optimal oracle complexity. In International Conference on Learning Representations, 2023.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Information Processing Systems, volume 30, 2017.
Joost Verbraeken, Matthijs Wolting, Jonathan Katzy, Jeroen Kloppenburg, Tim Verbelen, and Jan S Reller- meyer. A survey on distributed machine learning. ACM Computing Surveys, 1333) 2020.
Thijs Vogels, Sai Praneeth Karimireddy, and Martin Jaggi. PowerSGI: Practical low-rank gradient com- pression for distributed optimization. In Advances in Neural Information Processing Systems, 2019.
Jianyu Wang, Zachary Charles, Zheng Xu, Gauri Joshi, H. Brendan McMahan, Blaise Aguera Arcas, Maruan Al-Shedivat, Galen Andrew, Salman Avestimehr, Katharine Daly, Deepesh Data, Suhas Dig- gavi, Hubert Eichner, Advait Gadhikar, Zachary Garrett, Antonious M. Girgis, Filip Hanzely, Andrew Hard, Chaoyang He, Samuel Horvath, Zhouyuan Huo, Alex Ingerman, Martin Jaggi, Tara Javidi, Pe- ter Kairouz, Satyen Kale, Sai Praneeth Karimireddy, Jakub Konecny, Sanmi Koyejo, Tian Li, Luyang Liu, Mehryar Mohri, Hang Qi, Sashank J. Reddi, Peter Richtarik, Karan Singhal, Virginia Smith, Mahdi Soltanolkotabi, Weikang Song, Ananda Theertha Suresh, Sebastian U. Stich, Ameet Talwalkar, Hongyi Wang, Blake Woodworth, Shanshan Wu, Felix X. Yu, Honglin Yuan, Manzil Zaheer, Mi Zhang, Tong Zhang, Chunxiang Zheng, Chen Zhu, and Wennan Zhu. A field guide federated optimization. arXiv preprint arXiv:2107.066 /7,66677777667 2021.
Jue Wang, Yucheng Lu. Binhang Yuan, Beidi Chen, Perey Liang, Christopher De Sa, Christopher Re, and Ce Zhang. Cocktailsgd: Fine-tuning foundation models over 500mbps networks. In International Con- ference Machine Learming, pp.
PMLR, 2023.
Tao Yang, Xinlei Yi, Junfeng Wu, Ye Yuan, Di Wu, Ziyang Meng. Yiguang Hong, Hong Wang, Zongli Lin, and Karl H. Johansson. A survey of distributed optimization. Annual Reviews in Control, 47: 775, 2019. ISSN 1367-5788, doi:
URL https:
13

---

Published as a conference paper ICLR 2024
Peilin Zhao and Tong Zhang. Stochastic optimization with importance sampling for regularized loss min- imization. In Francis Bach and David Blei (eds.). Proceedings of the 32nd International Conference on Machine Learning, volume 37 of Proceedings of Machine Learning Research, pp. 1-9, Lille, France, html
07-09 Jul 2015. PMLR. URL https: httpss:/procceedngg. www.nnsssm.....l.mmmmmmm..m...mm press http://nw..m......e//eese...ee/e
14

---

Published as conference paper ICLR 2024
A BASIC RESULTS AND LEMMAS
In this section, we offer few results that serve essential prerequisites for establishing the main findings the paper.
A.1
OPTIMAL CLIENT CLONING FREQUENCIES
Lemma (Optimal weights). Lel 0z 0.fori E [n]]. Then
2
n
Σ
(17)
uy Ma E w;=1
Wy
which is achieved when w E, aj This means that
min =0==1
(18)
f=1
We now show that the cloning frequencies given by N mization problem of finding the optimal integer client frequencies. Lemma (V2-approximation) we ler N
form V-aaprrxximation for the opti-
LaM
L.
for all E [n], then
LAM
LAM S
M (NN,....,NN N.) & M NN) S V2LAM. NIEN....N.ENN
min
Proof. Recall that
M(NI,... No.
N:/N
The first inequality in the claim follows by relaxing the integrality constraints, which gives us the bound
L?
1
L?
min M.EN.....EENN
20
N
N/NN
and subsequently applying Lemma 17
Next, we argue that the quantity N Σ, No is at most 2n. Indeed,
n
N
Σ
N Σ
+1] = 2n.
(19)
LAM
LAM
i=1
i=1
We will now this to bound M (NV. ...., N#) from above:
L?
2
L
V2
M(NI NO
LAM
Li LAM-
N
N
i=1
Since LAM < 1 for all i [n), the proof is finished follows:
V2 f
Σ L,LAM = V2
M(N N <
v LAM
Σ L. = VLLAM-
In
15

---

Published as conference paper ICLR 2024
A.2 DESCENT LEMMA
Lemma 3 (Li al. (2221). Let Assumption 1 hold and # x² -'''. where g Id is any vector, and
Y > 0 is any scalar. Then, we have
(1 2
L
f(xtt1) S f(x'((()))))))))))) 2 f[V((=))1
| - 2²11 + I - vf(xx))
(20)
2
2
A.3 YOUNG'S INEQUALITY
Lemma (Young's s inequality). For any a, b E R2 and any positive scalar s > 0 holds that
||a + blb s (1 8) |||l + (1+
(21)
A.4 2-SUBOPTIMAL, BUT SIMPLE STEPSIZE RULE
Lemma (Lemma 5, Richtárik et al. (021 Let a, the bound is light up to the Jactor of since
If0 < 9 Vaug then + S Moreover,
1 5 Va
2
va+b S min
bj
v
A.5 OPTIMAL COEFFICIENT YOUNG'S INEQUALITY
Lemma 6 (Lemma 3, Richtárik et al. (021)), ). Let < S 1 and s > 0, let = =1-
and B(,,, 8) = (1 - a) (1 + 8 1). Then, the solution of the optimization problem
min B(a,s)
:0 8 T-a
(22)
((0,8)
is given by s* VI-a 1. Furthermore, 8(a vT a, and ((a,
1-a
I-vI-a
16

---

Published as a conference paper ICLR 2024
B CLONING REFORMULATION FOR POLYAK-LOIASCHEWITZ FUNTIONN
For completeness, we also provide series of convergence results under Polyak-L.ojsiewiic condition. We commence our exposition with the subsequent definition. Assumption 4 (Polyak-Lojssewwiez, There exists a positive scalar the following inequality is satisfied:
0 such that for all points R
1 -IV[(1)) 2p
[(x) ((x))
(23)
where x=" = argmin fa)).
Theorem 5. Let Assumptions
and hold. Assume that C C(a) for all i E [n]] and & 2 Consider
Algorithm 7 (EF21) applied to the "cloning" reformulation 9 of the distributed optimization problem
where N LAM for all E [n]. Let the stepsize be set as
I
{
28 0
0
0 0S min
2/
where 0 -- vI and 3
1-a Let
1-VI-a"
we' = f(x") f(=") 3
0
Then, for any 2 0, we have
E [ < 7/1 y
Proof. This theorem is corollary of Theorem 2 in (Richtárik et al. 2021 and Lemma 2
17

---

Published as a conference paper ICLR 2024
C PROOF OF THEOREM 3
(THEORY FOR EF21-W)
In this section, we present proof for Theorem tion lemma. We define the following quantities:
To start this proof, we establish corresponding contrac-
V(((a')
G
9
G¹
W,G
(24)
nwW;
where the weights wi are defined as specified in Algorithm
2 that is,
L;
We Σラ Li
(25)
C.1 A LEMMA
With these definitions in place, we are now prepared to proceed to the lemma.
Lemma 7. Let C; E C(a) for all i E [n] and t 2 O. Let W = .o.... I x², x²,x''1 ++1,, Then, for iterates
of Algorithm 2 we have
G
W < (1 0(a, 8)) + B(a, 8) n²w?
/ -//(='))1
(26)
and
| S(1 8(a, s)) E G') + 3(a, 5) L
|1"tt-=='13
(27)
where > 0 is arbitrary positive scalar, and ((, s) = 1 - (1 (1 + 8),
and
(1-))(+++)
(28)
Proof. The proof is straightforward and bears resemblance to similar proof found in a prior work (Richtárik et
2021
(x
E
1
W
24
E
W
nu
V fi(att))
2
E
9 + c
g
W
new
new
V Vi((t++1
(1 a)
mills
Vi((++1)
fx((''
Vf((x')
(1 a)
96
nww;
new
Vi(( gf
(1- (1+
1
+(1-a) (1 + 1 n²w?
(f((o(t)) - -
with the final inequality holding for any positive scalar s > Consequently, we have successfully estab- lished the first part of the lemma.
18

---

Published as conference paper ICLR 2024
By employing (24) and the preceding inequality, we can derive the subsequent bound for the conditional expectation of G
B G
W
E
We
G
W
24
W;E
9g
W
nw;;
Vii(z*) 2
(1 0(0,8) 8))
0
new
i=1
+B(a, 8)
Wi
[
Vs((+')
(29)
wfn²
Applying Assumption 2 and 25 we further proceed to:
E [
W
(1- (1-0(a,8)) 8))
93
Vfi(=*)
+ (a,,)) 8)
wFn?
Wi
Vs((x++1) -
new;
24
(1 0(a, 8)) G³ + 3(a, 8)
Vf((tt1)
win
L?
(1 8(a, s)) G¹ + ((),s)
|| - =z'1l
x²1
wine
i=1
L?
25
(1 - 0(a, s)) G¹ + B(a,s) s)
- -2'1?
Σ L
n?
1=
1= 1.3
Li Σ j=1
= (1 - l(a, 8)) G¹ + 8),
|| _ =111
n2
1=1
= (1- (1-0(a, 3)) G + 3(a, L)M
|| x
(30)
Using the tower property, we get
E [ = E E | w']l
(1 8() + B(a, 8) [|aft1-x=|1?] ==11]]]
and this finalizes the proof.
C.2 MAIN RESULT
We are now prepared to establish the proof for Theorem 3
Proof. Note that, according to 13 the gradient estimate for Algorithm gets the following form:
wag
(31)
1=
19

---

Published as a conference paper at ICLR 2024
Using Lemma 3 and Jensen's inequality applied to the function x + || (since Ei=1 wi 1), we obtain the following bound:
f(
f(x') - 2 1 [('()))|
L
|
|
x²
-12
+ 2
g'
V
fi
(x*)
2>
2
1=1
2
31
f(xt) - 2/2 || [
4
||
x² $12
2
Σ Wi
vif((a))
2
g
2
2
< [(x)) - 3/2 |()(a>))|
L
| -x²11 112 2
Σ W/
0/
22
2
f(x)) 7 2 |()('')|
L
|
-2'1--011 112
(32)
2
2
Subtracting f from both sides and taking expectation, we get
B [[ [*] < E [s(x")
- -
E
||
2
1 L
|| 1 2+1 x' [17]
+ 3 |G
E
(33)
2
2
Let 8' = [[f((*)) -- o = [["] and r² = EE
||
Subsequently, by adding 27 with a
7
multiplier, we obtain
20(0),))
84+1, + 20(a,s) s) st+1
8¹ - 7 Vf(2')) )12
L
r¹
2 s¹
+ s1+1
2
27
2
20
8' 7 |f(('') 112
1
L
st
2
27
2
2
+
7
(B(a, 3)
(1 - 0(, 8))8*)
20(a, 8)
= 8' + 7
L
3(a, 3(a, 3)L pd
20
2
2y
2
20 8)
8' + 20
|V
2
The last inequality is result of the bound 7 Bla,s) ((,,))
+ Ln S 1, which is satisfied for the stepsize
1
S L LAME(a,s)
where E(a, 5)= the final stepsize. By summing up incqualities for = o....,T T - 1, we get
((a.s)
((r,a)- Maximizing the stepsize bound over the choice of using Lemma 6 we obtain
0 0
7 ST 80
20 00
E
||
20
1=
2 Multiplying both sides by 57, after rearranging we get
Σ
28 5
TT
OT
20

---

Published as conference paper ICLR 2024
It remains to notice that the left hand side can be interpreted as E [|V where 8² is chosen from uniformly at random.
{2 xx _T
C.3 MAIN RESULT FOR POLYAK-LOIASIEWICC FUNCTIONS
The main result is presented next.
Theorem 6. Let Assumptions
2 and 4 hold. Assume that C E C(a) for all [n]] and 0. Let the
stepsize in Algorithm 2 be sel as
0(a)
0 7 S min
+ V2LAME(a)
2/1
Let
v === - f(x") (ar")+ 7 7²
0
Then, for any > the the following inequality holds: S (1 - 711) v0.
(34)
Proof. We proceed as in the previous proof, starting from the descent lemma with the same vector but using the PL inequality and subtracting f (xx) from both sides:
IE [f( f(x))]
E [ 2 [V((t))12-
1 L)
1
-2/1/+ +77 10
27
2)
2
(1-74)E [ [(x))| 27
L
| - 12112 Gr (35)
2
2
Let 8¹ = =f(((x) - f(x²() } s = E [G]] and x² y²;= =E
|xt+1 - x² ='I Thus,
ge+l + 2 st1
44
(1 74000
L
r + 7 x¹ + 7 /
27
2
(1 71000"
L
r
+
+ ?
(1-0)
+B
n Ls
xet
27
2
2
72
L
3IAaM?
(1
70)
+
rr
0
2
27
2
0
where and 33 are set as in Lemma 1 7/p and
6
Note that our extra assumption on the stepsize implies that 1
- S
1
3L 2 0.
27
2
2,2812n
The last inequality follows from the bound
+ + < 1. Thus.
8++1 + ++1
7
< (1 714) (8 + 0 )s
0
It remains to unroll the recurrence.
21

---

Published as conference paper ICLR 2024
D PROOF OF THEOREM 4 (IMPROVED THEORY FOR EF21)
We commence by redefining gradient distortion as follows:
1 [VL((') of W
G
(36)
We recall that the gradient update step for standard EF21 (Algorithm) 1
takes the following form:
9: g + (V -g.).
(37)
g 1
91
(38)
i=1
D.1 TWO LEMMAS
Once more, we start our proof with the contraction lemma.
Lemma 8. Let C E C(a) for all
[n] and t O. Define W = 1gl. 92. .., I xt, s.t11. Let
Assumption 2 hold. Then
E [ w S (1 A(a G)) + B(a, A - x²11?
(39)
where = s) (1
a1 (1+ + s) and B(a, s) = (1 - a1 + ") for any s > 0.
Proof. The proof of this lemma starts as the similar lemma in the standard analysis of EF21:
E [G
w
[IV - W
n2
[alb +
CV 9.)) V/( [
[V -
Wi
+ - 9f'
n
i=1
((1
- (1 vf(('')) (1+ s) vf(('()12
n²
(40)
22

---

Published as a conference paper at ICLR 2024
for all > 0. We proceed the proof as follows:
40
n
E [ w
(1++5
V.((+1)11 + ,وااgء v(((z()113
11a
Wi
1
1
[e(('')1 + s)
1 | (
(1 0(a,8) 8))
1lo
n2
Wi
n²
m
i=1
(1 - 0(a, 8) s)) + B(a,s) s)
36
V fi +1 - f(('))1
n²
Wi
B(a, s)
"
(1- O(, 8)
|| ++
x 111
(41)
n²
Wi
Note that this is the exact place where the current analysis differs from the standard one. It fully coincides with it when wy +. i.e., when we assign the same weight for each individual gradient distortion llo f. However, applying weights according to "importance" of each function, we proceed as follows:
(1 8)) + 8(a,
L
E [ [
1
++
1²112
n²
W/
faa,
L3
n
(1 f(a,s)) G)
L
|
112
n²
L
(1 (aa,s)) + 8(a,s)
Σ Tij
Σ
T4
||x
x²11
n²
1=1
(1 (((a,))) ((,
x0 2011?
what finishes the proof.
To prove the main convergence theorem, we also need the following lemma. Lemma 9, For the variable g from Algorithm ! the following inequality holds:
11gl V f((('))) 12² Gt.
(42)
Proof. The proof is straightforward:
l - 2²²)))
(o - v)((at))
(g) V)((a*))
W/ win
(of
v(((x'))
Wi
Win
Ilg
{2(
G¹,
w.n
where the only inequality in this series of equations is derived using Jensen's 's inequality.
23

---

Published as a conference paper ICLR 2024
D.2 MAIN RESULT
We are now equipped with all the necessary tools to establish the convergence theorem.
Proof. Let define the Lyapunov function
Φ¹ = --xx-- - 20( 8)
G
Let us also define W = fgi.9. g2. ................................ I x², +1 We start as follows:
[+++1
E [f((tt)) -- W +
7
E
[ W"]
20(a, s)
f(x²) - - - [[ |1
1
2
- - 2100 - vf(('))]'
27
7 E. [G W
20(a, 8)
f(x²) - [ (
1
1.
||att1-211122 7 G" 2
2
7 E |G wc]
20(a, 8)
f(x²) 8r 2 (((
1
L
|| - -x'112 I
27 2
2
28(a, 8) ((1 f(a, 8))G² + ((, s)
7
AM -x
- 1²)
f(x²) - 5*+ + 20(a,s)
7 G 1[
(1 1 L
7,3 8)
L
| x'112
2n
20(a, s)
20
f(x²) - -r+ 7 G v {2
(0 s)
4' - 12
The inequality in the last but line is valid if
1
L + LAM Bla.s)
By optimizing the stepsize bound through the selection of s in accordance with Lemmaf6) we derive the final stepsize and establish the optimal value for in defining the Lyapunov function. Applying the tower property and unrolling the recurrence, we finish the proof.
according to Lemma 5
D.3 MAIN RESULT FOR POLYAK-LOJASIEWIIZ FUNCTIONS
For completeness, we also provide a convergence result under Polyak-Loojasiewicz.co condition (Assumption The main result is presented next.
24

---

Published as a conference paper at ICLR 2024
Theorem 7. Let Assumptions ! 2 and 4 hold. Assume that C E C(a) for all E [n]] and 2 0. Let the
stepsize in Algorithm 2 be set as
1
0(a,8) 8)
0 0< S min
L V2LAME(a)
24
Let
v² f(x))x - f(x²) + 0(a,s)
7 G².
Then, for any T > the the following inequality holds:
E S (11-)1))0 y0.
(43)
Proaf. We proceed as in the previous proof, starting from the descent lemma with the same vector but using the PL inequality and subtracting f(xx) from both sides:
IE [ - f(x)]]
E - 2 [V((t))
1
2 | 1--1-2111 -2- l
2y
2
(1 (1-r))BB[ [)(=) [xx')]
1
L 2
| - xt 12+ 2 or (44)
27
Let 8" = =B(f(x') - f(xx)),
s² = E [G'] and x² == E
| - x² x'(l?]] Thus,
81+1 ? 2
(1 72)6
L
, + 5² + 7 1t1
8(a, s)
27
2
2 f(a,s)
39
L
(1 71)88*
1
+
27
2
2
2
+ 7
0(a,s)
+B (1- (())(a,)))++
11
-
1
Li
re
i=1
= -1-711 71) +
7
(1-0aa 0(a,)) 8)
8t
L
3L
r².
B(a,s) s)
2
2n
2
0(a, s)
Note that our extra assumption on the stepsize implies that 1
8(),))
I 1
7/ and
2
1
3LAMD
2 0.
27
2 0(1x8) 8)
The last inequality follows from the bound 722
2 ((a,))
+ 7 S 1. Thus.
51+1
+1 S (1 - 71)
8² B(a,s) s) 50)
0(a,s)
It remains to unroll the recurrence which finishes the prove.
25

---

Published as conference paper ICLR 2024
E EF21- WEIGHTED ERROR FEEDBACK 2021 WITH STOCHASTIC SUBSAMPLED GRADIENTS
The EF21-W algorithm assumes that all clients can compute the exact gradient in each round. In some scenarios, the exact gradients may be unavailable too costly to compute, and only approximate gradient estimators can be obtained. In this section, we present the convergence result for EF21-W in the setting where the gradient computation on the clients, (xx is replaced by specific stochastic gradient estimator. For a variation of EF21-W-SGD which working under a more general setting please see Appendix
E. ALGORITHM
this section, we extend EF21-W to handle stochastic gradients, and we call the resulting algorithm EF21-
Our analysis of this extension follows similar approach as the used by Farkhullin et al. 2021 for studying the stochastic gradient version of the vanilla EF21 algorithm, which
W-SGD (Algorithm 3
they called EF21 SGD. Analysis of EF21-W-SGD has important differences with vanilla EF21-SGD:
(L (
1. Vanilla EF21-SGD provides maximum theoretically possible 7 (L+LOM LQM 4
where
EF21-W-SGD has
L. LAM
2. Vanilla EF21-SGD and EF21-W-SGD formally differs in a way how it reports iterate x² which min-
imizes E. V ||]] due to slightly different definition Á. The EF21-W-SGD (Algorithm
requires output iterate a" randomly according to the probability mass function described by (49)
Algorithm 3 EF21-W-SGD Weighted Error Feedback 2021 with Stochastic Gradients
1: Input: initial model xº e IR;; initial gradient estimates gf ......... ... Rd stored at the server and the clients; stepsize 7 0; number of iterations T 0; weights w. Σ, T for E [n]]
Initialize: = T
w on the server
3: for f. = 0.
do
4: Server computes , _² - 7 and broadcasts (+1 to all m clients
5: i= 1,.... on the clients in parallel do
6:
Compute stochastic estimator 9. (x(x+1))
Σズ Veet (x*+ of the gradient (a((+)))
j=
7: Compute uf = C rewey (a(tt)) gf and update 9 of ut
8: Send the compressed message ut to the server
9: end for
10: Server updates gf = of + ut for all [n]. and computes gl+1 E w.g, 1+1
11: end for
Output: Point a chosen from the (x ........."" T randomly according the law 49
Assumption 5 (General assumption for stochastic gradient estimators). We assume that for all i E [n] there exist parameters A,, C, 0, B, 2 such that
E
V fee (x)]l
< 2A, (fi(x) f!a!) + (=) + C.,
(45)
26

---

Published as conference paper ICLR 2024
holds for all 1R where si inf f((x) -00.
We study EF21-W-SGD under the same assumption as was used for analyzing Vanilla EF21-SGD, which we denote as Assumption []] To the best of our knowledge, this assumption, which was originally presented Assumption 2 by Khaled & Richtárik (2022), is the most general assumption for stochastic gradient estimator in a non-convex setting.
Next, to be aligned with original Vanilla EF21-SGD (Fatkhullin et al. 2021 we have considered specific form of gradient estimator. This specific form of gradient estimator from Vanilla EF21-SGD presented in Section 4.1.2. Fatkhuliin et al. (2021) where the stochastic gradient 9. has been computed as follows:
d:
Veet (1(+1),
Here Ti is minibatch size of sampled datapoint indexed by <t of client i in iteration And E are independent random variables. For version of EF21-W-SGD which working under a more general setting please see Appendix F
E.2 LEMMA
The contraction lemma in this case gets the following form:
Lemma 10. Let C E C(a) for all i E [n]] and 2 0. Define
(((('')
G
G Σ G.G.t.
n&W;
Let Assumptions
2 and hold. Then, for any 8, 0 we have
E
E
S (1
0) |
B L
|1
1'l 10]
A32 ((att1)-f")) + +.
(46)
where
Li
wz =
E3 Lg
0 = 1 - (1 (1 s) +v),
6 2(1 a ()++)(++++))
B2 2(1 - a) 5) (1+++++)))) s
2(A; L,(B, 1))
Ā
max i=
T
TAW
C 1
Č
max
Ti nww
'When A, 0 one ignore the first term in the right-hand side of 45 i.c., assumption inf f((x) -00 is not required in this case.
27

---

Published as a conference paper ICLR 2024
Proof.
Define W = (9f......
gh x², 12t11.
The proof starts as follows:
1+1 Vii(a*t1)
E
G
W
E
W
man;
(1(x(tt)
line
E
g +
C²
W
nowl
nww;
Gi(x (i(att1)
g. (2*+1)
Di (
2
E
ci
+
W
new
news
1ow
nu
||o
(((xtt1)
ge (1(x+11)
| 1
(1 + كااد
9f
9
gi (1(tt1)
Vii(atti)
+(1 + +
W
naw;
(x(xx=1)
vf((x')
Vf((x*))
(1 (1-a)(1 +s)E
9
W
nww,
nw;
(((x(t1)
+(1 + +
W
nuw
new;
Vfi(z*))
a1= +3) +1+
9:"
nw',
fi('')
9. (x++1)
+(1 (1-a)(11 s)(1 11 1)
news
((x+t))
+(1 +11+8-1BB
W
nw;
rew
Vi((tt) 2
(1 - a) s)(1 D)B
93'
nw;;
V Vi((=++1)
ge (x+++11
+2(1 a1 + s) + vー y
W
new
nw
V Vi(zz+1)
{)(()")
-2(1-a)(1+ s) --
TWW
(((x+t1)
vf(x*++)
2
+(1+5-1)B
W
nw;
now;
To further bound the last term, which contains multiple (1+ ++1s factors, we leverage the property that de( (e(x+1) is a random variable serving as unbiased estimator of V v taking the form
1
(
Tee, (I*
28

---

Published as a conference paper at ICLR 2024
where fi are independent random variables. Next, we can continue as follows:
E [ 1 wy] 1 (1-
B) [
w
+ 31 u
[ - V f(("))1 |
B2
E
v
Sei (x 11) -
Vfi(
1m1)
(news) )2
j=1
(1 0) [G]
w"]
+
Si n²
(z V vf((2))1
{)(((tt) 12 |
B2
E Σ
Vieg
(nw;)2
= (1 - 0) [G] WM]
+
1
(i((ott1) - {s((t\)
n2 ?
B2
V (att1)) / | - I [ies (attt) (
(mww)) ) J2
$ (1- 0) [G wi] + $t nسu?
/fi(e't)) - -f((i))
B2 Σ 2A,
Ball +|
(2w
O) [ w +
31 n????
1 -
24,
(f((z - ) + 2(B, - 2[B3-1)88 1)82
Cr33 (ne,) )2,,
(nw:) 127
(nwm)) 2
< (1 0}E [ W
+
31
1
V [(( - [s(((') ?
n²u?
2A
(f((o - llal) + 2(B: - 1)82,
2
L. (fi(ott)- - f:al) + CrB²
(nu
(nw,)2TT
(nw,))2T,
1 [[/((t(t))- - ((x()))
(1 0}E [0|| w + 81 nzn?
2(A, + I. (B; 12)
Cr
(f((z - -!an)= +
(nw,)?T
(nw:)
Furthermore, as a result of leveraging Assumption 2, we can derive the subsequent bound:
E [ W'] < (1 (1- + 11
n n² |1a4t1 - 201
2(A, + (B, - 12
CrS2 (nvu:)2rt
(fi(a(t1)- -s!nt)- +
(now;)2T
29

---

Published as a conference paper ICLR 2024
Applying the tower property and subsequently taking the expectation, we obtain: |||ett] - =011]]
E [[ < (1 - O)E [G]] 31 n² 1))
LE
(47)
2(A; + (B; (nT
Cr
+
E [fi(x(tt) Jial + (nzw))2T
Regarding the expectation of G we derive the subsequent bound:
E [[
= E
1=1
Σ W,E [G]
(1
w;lE [G]] Σ
w n²w??
Lg EE || - 2211?]
2(A; + Li(Be 1))83
CrBB
.R [fi(s - siau] +
W/i
Wi (nws) )
)T;
1=1
= (1 E [G]]
+ Σ
81 n2w,
L E |1 - =21
||
i=1
n 2(A, + Li (B. 1))B2
C,5²
E [f(()( fuml] +
n n2w,
ne n
Employing quantities A and C, the final bound can be reformulated as follows:
11
E [[ s
(1 0) G7
+
Lē EE
|| 1 - 1-1
n2w;
1 Σ
A32-
E [f((z+1)
s:me| + C.
i=1
$
(1 83 [G]]
+ Σ
B1
Li E || - 1=1
n²w;
1=1
+
Σ
A3n- E [f(
- pinf]] + +B,32
S 0)B |a]| + Σ
3 1 1 EE ||02t11 - =01
m
+ +A8 [ - | + C
30

---

Published as conference paper ICLR 2024
L, Given that w; Eg Ti"
we have:
E [ z (1-0)E(G") + 1 Σ 31
En L
L,B |1 x² |19
==1
+A [f(x)1] - pint] + 0
{ Li E || 10-4+112111 =001
(1
(1- G²| +
i=1
+A3,B [ pinl] + C.
what completes the proof.
E.3 MAIN RESULT
Now we are ready to prove the main convergence theorem.
Theorem 8. Let C C(a) for all E [n]] and 2 in Algorithm
3
Set the following quantities:
0 1 (1 a) (1 +) u),,
3 2(1 -x) (1 + 8) (1+)
f2
2(1 a1 - s) + +11++++))+)
Li
wx
2(A; + Li(B; 1)) 1
Ā
max im
n000
C2 1
Č
max i
Ti nww
Under Assumptions
2 and and selection of 8 > 0, 1 > 0 such that (1 + 8)(1 + +1) < I-a set the
1
stepsize in the following way:
1
(48)
L+ LAMY
Choose an iterate a from t2 x
with probability
Prob(# = =x²)=
1/2
(49)
Vr¹
where
7A32
T
Ut
;
Vr
Σ
11.
20
Then,
E |()(">) 12]
2( ((f(20) find
Go
832
<
(50)
I
(1-
2.
0T
20
where GO := Ei ii 10 Vf(
31

---

Published as a conference paper at ICLR 2024
Proof. In the derivation below, we use Lemma
g²
wag.
(51)
We start as follows:
f(
f(x') - 2/2 2
1.
|
x²
1
+
2
g²
v
fi fz
27
2
2
2
51
f(at) - 2/2 [f((''))'
4)
| x²1
x²11²+
2
vi(((a))
Wi
9
2
2
2
S f(x)) 7
2 |-)(a')|
I
||/0 x²'1" 22112
7
Σ
1
9
V(((2')
2g 2
2
now;
f(x)) 7
2 ||
L
||a
- x²
112
7 2 G²
(52)
2y
2
Subtracting f" from both sides and taking expectation, we get
E [[ ["] s [[
1-1
[*] -
7 E
V [V |19]
27 E
1 L
|1
2²y1²] + F [
(53)
Let 8t = Eff(x') f")
f"), s = E |C** and p+ = E
|| -x-- -|1001-=2111
Then by adding Tे8 s² + and employing
46). we obtain:
81+1, + 7
1+
S 8¹_
2
/f(ao)))
1 I
r²
7 0e
20
27
2
2
+ 7
+11- 0)ss² + AB28841 + -(3²z
20
5t +
| [1²] - 1
L
2
AM
r² +
7A32
81+1
+
2 82
2
20
2
2
20
20
20
S 8 + I 2 28 2
[V
019 +
2,A,32
81+1
+ 7
32.
20
29
2 Ly 1, which holds due to Lemma 5 for y Subsequently, we will reconfigure the final inequality and perform algebraic manipulations,
The last inequality follows from the bound 72 8
L+LAMY taking into account that 2 > O. In the final step of these algebraic transformations, we will leverage the fact that st 2 0:
7A3
G 32.
81+1
+
8+1
11
8t +
-s
- I
8++1 +
20
20
2
20
20
Therefore,
2 g1+1
+
2 y 1+1
<
2 _x¹ +
2 22
5'
E
|
27AB2 g++1
2 2 82.
7 20
7
20
7 20
7: 20
32

---

Published as a conference paper at ICLR 2024
Further,
E
[[V
2 _280+1
2 2
g
2 8'
2
s
2 2
gr+1
2n
B2
7
20
7
7 28
7 20
7 28
2 80t1
2 2 1+1
2 8
+ yA 8
CB2
8'
20
20
20
2
8' +
y
8
7A33
8
y
8
+
C
28
28
28
2
8
γ
st
7A,32
88+1
?
s4+1
+
C02
?
20
20
20
We sum up inequalities above with weights u2 /V, where uy == (1
~A&
28
) and VT ==
- 08:
T
T
E
E
VT
t=
1
E.
| (x')
(xt) || [|]]
VT
t=
7A32
CB2
1t
8'
+
Y
s'
[u41
+
8 1+1
+ θ
VT
20
20
20
VVT
2
W
8
20
Y s
1
AB3
29
84+1
2
7 1+1
+
Σ
T
WT
Wr
CB
θ
1=0
2
W1
8t
se
1
AA32
8t+1
+
1+1
)
+
8
TVT
20
20
28
0
2
u1
8t
?
8
w++1
55-1 + 7 st+1
))
C33
VIT
20
20
0
1=
28
C
+
TVr
0V
0
Finally, we notice that VT = Σ
T
(1
A
y 2 T (1
146 yT, what concludes the proof.
20
t=1
33

---

Published as conference paper ICLR 2024
F EF21-W-SGD: WEIGHTED ERROR FEEDBACK 2021 WITH STOCHASTIC GRADIENTS UNDER THE ABC ASSUMPTION
this section, we present the convergence result for Weighted EF21 in the setting where the gradient com- putation on the clients is replaced with pretty general unbiased stochastic gradient estimator.
F.1 ALGORITHM
The EF21-W algorithm assumes that all clients can compute the exact gradient in each round. In some scenarios, the exact gradients may be unavailable too costly compute, and only approximate gradient estimators can be obtained. To have the ability for EF21-W to work in such circumstances we extended EF21-W to handle stochastic gradients. We called the resulting algorithm EF21-W-SGD (Algorithm
Algorithm 4 EF21-W-SGD: Weighted EF-21 with Stochastic Gradients under ABC assumption
1: Input: initial model xº E IRU; initial gradient estimates g .2...., 9 E R stored at the server and the clients; stepsize > 0; number of iterations T >> O; weights Σ, bj
for i E [n]]
2: Initialize: 9" - - 1= w.gl the server
3: for I. 0, 1,2. T do
4: Server computes r²+1 = x² 77g² and broadcasts =:++1 to all n clients
5: for = I.....,1 n on the clients in parallel do
6: Compute stochastic gradient 9. (x(x=1) estimator of the gradient (z
7: Compute u³ = C Rew ( of and update o gt + m/
8: Send the compressed message u² to the server
9: end for
10: Server updates of = of + ut for all i E [n], and computes g²+l En wig
11: end for
12: Output: Point x² chosen from the set xx" x" 11
} randomly according the law 59
Our analysis of this extension follows similar approach as the one used by Fatkhullin al. 2021 for study- ing the stochastic gradient version under the name EF21-SGD. However, EF21-W-SGD has four important differences with vanilla EF21-SGD:
1. Vanilla EF21-SGD algorithm analyzed by Fatkhullin al. (2021) worked under specific pling schema for stochastic gradient estimator. Our analysis works under a more general ABC Assumption 6
2. Vanilla EF21-SGD provides maximum theoretically possible 7 = LQM V
where
EF21-W-SGD has 7 L+ LAM
3. In contrast to the original analysis Vanilla EF21-SGI our analysis provides more aggressive 31 parameter which is smaller by a factor of 2.
4. Vanilla EF21-SGD and EF21-W-SGD formally differs in way how it reports iterate x" which minimizes V f( due to a slightly different definition of Ā. The EF21-W-SGD (Algo-
rithm requires output iterate #T randomly according to the probability mass function described by Equation (59).
34

---

Published as conference paper ICLR 2024
Assumption 6 (General assumption for stochastic gradient estimators). We assume that for all [n] there exist parameters A,, C 2 0, B; 2 such that
E [ s 2A, (f(()) + B. ( + C..
(54)
holds for all TRd where A inf ZER" fi(x)) > -00.
Assumption (Unbiased assumption for stochastic gradient estimators). We assuaee that for all E [x] there following holds for all x R
E [1) = = V.())).
We study EF21-W-SGU under Assumptionn(aama Assumption To the best of our knowledge, this Assump- tion [ which was originally presented as Assumption by Khaled & Richtárik (2022). is the most general assumption for stochastic gradient estimator in non-convex setting. For detailed explanation of the generality of this assumption see Figure of Khaled & Richtárik (2022).
F.2 A LEMMA
The contraction lemma in this case gets the following form:
Lemma 11. Let C E C(a) for all i [n] and 2 0. Define
V((('')
G
g
G² G'= W.
nww
Let Assumptions
o 7 hold. Then, for any > 0, > 0 during execution of the Algorithm the following
holds:
E
E(G
<
8 T ['] + Pr 12 A
||ott =²1p] A [f( finl] CB2
(55)
where
W/s = Li
Σ₁4j'
0 = 1 - (1-
9 = (1 (1+
82 (1 a) + 8) (11+
1
Ā
max
2(4: + L,(B: 1))
I.....
nww;
C _,1
1
max
Loon
Tew;
"When A, 0 one ignore the first term in the right-hand side of 54 i.c., assumption inf f((x) -00 is not required in this case.
35

---

Published as conference paper ICLR 2024
Proof. Define W = (9f......
Ih x², 12t11.
The proof starts follows:
1+1 V(i(x*+1)
E
G
W
E
W
man;
(1(a(t1)
line
E
9 + C²
W
nowls
nww;
Gi(a (i(aat1)
g. (x*+1)
ge (x(
f
(1(
2
E
ci
+
new
news
1ow
nu m
||o
(i(xtt1)
ge (1(x+t1
| 1
(1 + ك)
g (1(t1)
Vii(att1)
+(1 + =
nwi
(1 11-a)(1 + +SJE
(((att1)
ff((tt))
|| W
gf
nus s
+(1 + 1)B
new
new
11.1 1 +
|1.0"
1)
V f
+(1 -1-a)/ a)(1+ s)LE
kma mr
new
(1(xt1))
411 14
= 11--0
1 + +))R
(1
+
V
+(1 aa) aa
nuy
kma
2
36

---

Published as conference paper ICLR 2024
Further, we continue as follows
Vii(a()
|2
G W
(1-a)(1++ s) + E)
gi¹
nww,
V[i(z(+1)
V[i(=') |2
+(1-a) + 5) +
(1
now
new;
gi(x*+!) (z(
+(1+ + a) s))
W
nww
To further bound the last term, which contains multiple (1+ s- factors, we leverage the property that (x(x+1) is a random variable serving as unbiased estimator of V (i(xtt1). Our approach is as follows:
E [ W (1
S
E
[ W
9 n
( VA(=")]|
(n )2
Now due to the requirement of unbiasedness of gradient estimators expressed in the form of Assumption we have the following:
[ \](
| [ = E
||
w*]
[[(
(56)
Using this variance decomposition, we can proceed follows.
37

---

Published as a conference paper ICLR 2024
E [G
W
(1 Q)E [G]]] w + n²
1 [ii(tlt)) - {)(
B2
E [1
| - -|
+ (nxw))) )2
(1 E) G
w + B1 n Vf((2'+1) - -
B2
(2A:
- fimift ((t B.IIV
+ - -
(1 D)E |G W/
+ 31 n2w,
[[i(+*+))) - v/(("')/
24
2(BB 1)182 ('I(AA(attt))))) + Gr82
(fi(a(t))-))
(nw;)2
(nwn))
(nzo))2
1
(1 B) G w +11 n²
[l(x {f((2')1
24 (fi( - f + BB, 1),32
Li (Ji(z(t1) s!at) + Grfi2
(nw;)) )2
(nw;)2
(new;)
1 [ -V((a")
(1 ول [G wr] + 31 n²u?
((4 L, (B: 1))82
C2
(1i - p!ult + (new;)²
(nw;)²
Next leveraging Assumption 2 we replace the second term in the last expression, and we can derive the subsequent bound:
8,L7
E
[
W
(1 11-0) - +
| 10211xx()) 1²11
n²u?
2A4 L.(B: - 1))832
CaB2
(fi( - f(al) +
(nw:)²
(new;)²²
Applying the tower property and subsequently taking the expectation, we obtain:
E [ s (1 θ) [G:] + 31 nu
1
|| [|att]-2*1]
1--1-xx1] ==1²]]
(57)
+ 2(A; + La - 1))
C2
E [f((x(t]) - slau] + (nw:) )2
(nw;)2
38

---

Published as a conference paper at ICLR 2024
Next for the expectation of the main quantity of our interest G++1, we derive the subsequent bound:
E [++1| = E
G
W [
w:lE |G]] + n i=1
(1 0)
w n² n²
L3 . EE || - x211"]]
2(A; + Li (B; - 1))822
Cr
IE [[((ctttt - s +
+
W
(nw;)² )2
w
(nw,))
1=1
= (1 - و} [G'] + Σ
n
31
1
L EE =211
n²w;
f=1
2(A, + LB - 12)
C₂3²
E [( - sam0]
(n)2w
n nww:
Employing quantities À and Õ, the final bound can be reformulated follows:
E B[G s (1 mOE [o]]
B
1
L3
E | - =01]"]]
n?ws
1
T E [f((ttt]]
- -Saui] + C
1=1
12
I (1 (1-60 E G + >
B1 n
L. E | -
-x(1²² 2010²]
im
1 T
+
-
Ag E [f((x(t1)
(octt))fuu plnnj + T
π
72
S (1 و} | +
31
L3 BE
EE |1oet1 - 21]l]]
n2w,
1=1
+ A
1
- -ini + CB2
Given that w; = J. Σ, L,
we have:
E [ S (1- - ÔEE [G'] +
1
31
Σg Lj
LE |1 =011"]]
im1
+ A [[(x+1]] - - + T.32
2
1 Σ Tu
(1 - UΙT [G*] + B,
. [1o04t1- [1]
n2 1=1
+ A [f(x+1]] - pint] + C..
what completes the proof.
39

---

Published as a conference paper ICLR 2024
F.3 MAIN RESULT
Now we are ready to prove the main convergence theorem.
Theorem 9. Let C C(a) all E [n] and 2 in Algorithm 4 set the following quantities:
0
a)) (1 +v);
3 (1 - (1 5) (s+
= (1 - a) s) + (1+ )
L
Wi
Σj= bij'
2(A, + L;(B, - 1))
Ä
max
=I.....
TOW;
C2
max
i TEW;
Under Assumptions i
and selection of 8 > 0, > small enough such that (1 - 8)(1 +V) < T-a
holds, set the stepsize in the jollowing way:
(58)
L LAMV? /
Choose an iterate a² from t2 x.
x² } with probability
Prob(*" =x') 112
(59)
VT
where
7A32
VT = Σ ut
1/.
20 ;
Then,
E [V) 11
< 2(ʃ(x9) f
Go
C
(60)
(1
2A 29
0T (1 xA
where G = =E= w/|
|00p
V)((o)) ?
nww
Proof. In the derivation below, we use Lemma 3 for
wag
(61)
1=1
40

---

Published as a conference paper at ICLR 2024
We start as follows:
1(
f(a²) 7 2
/f((t)))
L.
|
11 +
Y 2
g¹
V
fi(('))
27 2
1=1
f(x²) - 2 /
I
||/0|
x²1 $11 ?
1 Σ
Vii(("))
W/
9
27
2
< f(x)) 2 [>(("'))1
L
||_
x² 112 + 2
Σ
n
9
Vi((x')
W/
'2
2
now;
1=1
((6)) 2/ |>)'))||
L
||,
xz
112
2
2
2
Subtracting f from both sides and taking expectation. we get
E [[(xt+1)- - [*] < [s(())) r - E [|>
1
E
||
x [11]] + M [G'].
2
27
2
Let 8r =E[((x²) - 1", = E [G'] and yr = E |||--t1-=000 ==']"]
Then by adding 20 s and employing
inequality (46). we obtain:
8r+1 7 st 5
||
27 -) r¹ 2
1 L
2
2
20
7
+(1 0)s² + +A8g8tt1 (.22)
20
5t + 7
E
[1( - ( L.
1_7
7
B1 L'aM
r² +
7A32 8t
+ 70 20
82
20
2
27
2
20
20
S 8' + 1 5'
E
[|V
+ 2A82
8++1
70 32.
2
20
20
20
The last inequality follows from the bound 722 26b6 + In < 1, which holds due to Lemma for
1
31 0
L L+ILAMY
Subsequently, we will reconfigure the final inequality and perform algebraic manipulations, taking into account that
> O. In the final step of these algebraic transformations, we will leverage the fact that st 2 0:
7A3 g+ + 70 32.
80+1 + g4141 +1
8² + 7 s²
2
I [|V
+ 20
28
20
28
Therefore,
2 8t41
+
2 1+1
<
2 8¹
2 7
5 E
|V
V
2
A73
2 G 82. ge+1
7 26
7
7 28
7 20
? 20
41

---

Published as a conference paper at ICLR 2024
Further,
E
[[V
2 -280+1
2 2
g+1
2 8'
2
s
2 2
gr+1
2n
B2
7
20
7
7 28
7 20
7 28
2 80t1
2 2 1+1
2 8
+ yA 8
CB2
8'
20
20
20
2
8' +
y
8
7A33
8
y
8
+
C
28
28
28
0
2
8
γ
st
7A,32
88+1
?
s4+1
+
C02
?
20
20
20
We sum up inequalities above with weights u2 /Vr where uy == (1
~A&
28
y and VT ==
- 08:
T
T
E
E
VT
t=
1
E.
| (x')
(xt) || [|]]
VT
t=
7A32
CB2
1t
8'
+
Y
s'
[u41
+
8 1+11
+ θ
VT
20
20
20
VVT
2
W
8
20
Y s
1
AB3
29
85+1
2
7 1+1
+
Σ
T
WT
Wr
CB
θ
1=0
2
W1
8t
se
1
AA32
8t+1
+
1+1
)
+
8
TVT
20
20
28
0
2
u1
8t
?
8
W++1
55-1 + 7 st+1
))
C33
VIT
20
20
0
1=
28
C
+
TVr
0V
0
Finally, we notice that VT = Σ
T
(1
A
y 2 T (1
146 yT, what concludes the proof.
20
t=1
42

---

Published as conference paper ICLR 2024
G EF21-W-PP: WEIGHTED ERROR FEEDBACK 2021 WITH PARTIAL PARTICIPATION
In this section, present another extension of eπror feedback. Again, to maintain brevity, show results for EF21-W, however, we believe getting an enhanced rate for standard EF21 should be straightfor ward.
G.1 ALGORITIM
Building upon the delineation of EF21-W in Algorithm we our attention its partial participation variant, EF21-W-PP, and seek to highlight the primary distinctions between them. One salient difference is the introduction of a distribution, denoted
across the clients. For clarity, consider the power set P of the set [n] {1, 112..... .....,,. n., representing all possible subsets of [n]. Then, the distribution 'D serves as a discrete distribution over
While EF21-W-PP rums, at the start of each communication round t, the master, having computed descent step as = x² - 79" samples a client subset 5 from distribution Contrasting with Algorithm where the new iteration rt+1 is sent to all clients, in this variant, it is sent exclusively to those in St.
Any client E S adheres to procedures akin EF21-W: compresses the quantity was Vf((x') of and
transmits this to the master. Conversely, client j omitted in St, i.e., $ S is excluded from the training for that iteration. Concluding the round, the master updates g by integrating the averaged compressed variances received from clients in the set S
Algorithm 5 EF21-W-PP: Weighted Error Feedback 2021 with Partial Participation
1: Input: initial model parameters Nº E R initial gradient estimates gi .2.99.... Lh Rd stored at the clients; weights W/ L./E, Ly; stepsize y > O; number of iterations T > 0; distribution D over clients
2: Initialize: 9d Σ = w. the server
3: for t- 0, 1,2. 1.2...., 7 do
4: Server computes x1+1 _² -7g'
5: Server samples a subset St ~ D of clients
6: Server broadcasts x²+1 to clients in S
7: for i = l....... n on the clients in parallel do
if then ) gf) and update of = o6 + m/
9: Compute of = vww,
Send the compressed message ut to the server end if
11:
12:
if $ St then
13:
Set uf = for the client and the server
14:
Do not change local state g. ++1 = g end if
15:
16:
end for
17: Server updates of 1+1 = 9t + uf for E [n]] and computes g Em wigh 6+1
18:
end for
19:
Output: Point 3t chosen from the set (x.,....,e Tf -1 uniformly at random
Assume S is drawn from the distribution D. Let denote
P; Prob(i S*).
(62)
43

---

Published as conference paper ICLR 2024
other words, pt represents the probability of client being selected in any iteration. For given parameters such that pi (0, 1] for [n], we introduce the notations Puuin = min; and Pmax = max; Pi. respectively.
G.2 A LEMMA
Having established the necessary definitions, we can now proceed to formulate lemma. Lemma 12. Let C E C(aa) for all [n] and t 2 0. Let Assumption 2
hoold. Define
9 Vf((")
G
G²
W.G.
(63)
nw;;
For any 8 and p > 0, let us define the following quantities:
((o, 8) = 1 - (1 (:((1 +))
B(a, s) = B(a, s) = (1
0p
Punnf O(a, 3) P (Prax Puiin)
B (B(a, 8) (1 Pmiin (1 p p=1)) LaM-
Additionally, assume that
1 p(1 Pmin) + (pmax Pmnin)
2 Ma, 8) p(1 Pmiin ) + (pmax Pmin)
Pmax
Pmax
Then, we have
[ S(1 (1-0p)E [G*]
BE | 2² 2012]-
(64)
Proof.
Let us define W {gf....
Ih. x² ++ }. client participates in the training at iteration t, then
v
(2
E [G
E
W e St
nw;
line of Algorithm
E
of C
V.i(att11
v (i((((11
W E
nw;;
Vi((x((1)
(1 11-00 ax)
g
nwa
fi(xt+t)
vf((x*)
(1 ())
9
na
nww
Vs((x*)
(1-a)(1 s)
nww;
+(1 a) (1+
V
-
?2w? 2
Vf((2*)
(1 (1++))
g
L2
+(1 - ai) (1+
|| 1+1 _ x
n
44

---

Published as a conference paper ICLR 2024
Utilizing the tower property and taking the expectation with respect W
we derive:
L 2
E G i s*] - (1 l(a, 8)) [ + 3(a, s)
E
x ++
x²
(65)
u
where ((a, 8) - - a1 + s), and B(a, = (1 a) + 8 s-)).
We now aim to bound the quantity
E [G i 5*] starting with an application of the tower property:
E
G i st)
E E
G
Wt, i & s*]l
(i((t+t)
E
E
9.
W & St
nw;
v
fi(
fi(z²)
Vf((z')
E
E
g
[ . st
nww
new
Vfi(tt)
1 + +(
Vf((z*)
Vfi(att)
E
E
p)
W i St
new
new
now;
(1 p1+ n²w?? ?
(1 p)B G.
E
Given that Assumption is satisfied, by applying
( to the second term, we obtain:
L1 + p
p=))
E [ l q s*] s (1 + p)B [c]] +
E
|| || 2²
-2'11=)-11)) 2²11
(66)
n²w?
We combine the two preceding bounds:
E
[G
Prob(i S [ | 5t
+ Prob(i $ SS) [G 1 gig st
P.E
G S + (1 P:) |.
i s*1
66
Pi
(1 - (1-6(a, s) E G + B(a, 8)
I
E
1u't1=2'12
n2us
+(1 p.) (1 (1+ [
L3 +
E
-1
x² [1]
n²u?
((1 (1--0a 0(a s))pi (1 - (1-p:)( + p)) E [G]]
L
+((aa.))p s)p: +(1 (1- p 1)
E
||
||
-2011²)
n n
45

---

Published as a conference paper at ICLR 2024
Consequently, for E [G+ we derive the subsequent bound:
E
G
E
G
well [G:
<
Wi ((1 - 0(a, s))p; + (1-p:)(1 + p)) E [G:]
i=1
wi (B(a, s);; + (1 P1) + +
1 n²w?
I
|ottl x4 =1²]
where we applied the preceding inequality. Remembering the definitions pmin = min; ps and pmax = max; Pi, we subsequently obtain:
E B S
wi ((1 - 0(a, 8) Pmax + (1 PPmin + p)) E
[
L. n?w;
(3(a, s)pmaxx + (1 - Pmmia + 1)
TE
|| - -
n
((1 (ax Pmaxx + (1 Pmii) (1 + 0)) Σ w,B [G]]
L3 n2ws
(8(a, Praxe + (1 Pinin) (1 p
E
-
n
i=
Applying 63
and
we obtain:
+1
(a, Pmax + (1 - Pmiin + P)) [
n
L
(3(x, Pmaax + (1 Pmiu) ) p 1) Σ
E
x 11]]
n2
L:
21=
((1 ((x, 8m)x + (1 Pmmii (1 + p)) E [G*]
+ (3(a, s)Pa + (1 Pmin (1+
+ ))) Σ
Σ 1=1
E
|
x- 113]
n
j=l
((1 0(, Pmax (1 Pmii (1 p)) EE |c*
+ (3(a, smmxx + (1 Pmmin) (1 + p -)) L E
| x² |1]]
Subsequently, in order to simplify the last inequality, we introduce the variables - Op and B:
- 0p == (1 8(a, 8) P + (1 Pruin) (1 + p)
Pmax Pmax la, s) + 1 Pmnin + P PruinP
= (-Pmax + Pmax ((a 8) + Punin - P + Pmiinp) = 1 (Pmiup + Pmuxx A A( 8) p (Pmax Punin)
46

---

Published as conference paper ICLR 2024
Therefore,
0p (amaxO(ax 8) p(1 Pmin) (Pmax Pmmin))
B = (3(xr 8) 8mpax + (1 Pmin)) (1 + p p))) LAM-
Expressed in terms of these variables, the final inequality can be reformulated as:
E [ (1 - 1p [G'] BE
|| x²
Since we need the contraction property over the gradient distortion E [G++]] we require 0 < <Bp S 1. We rewrite these conditions as follows:
1 p(1 Puiin) + (Pmax Punin)
2 0(1 8) > p(1 Puin)) ) + (Pimax Pmiia
Pmax
Pmax
G.3 MAIN RESULT
We are ready to prove the main convergence theorem.
Theorem 10. Consider Algorithm (EF21-WPPP) applied the distributed optimization problem 1
Let
Assumptions 7 2
3 hold, assume that C C(a) for all E [n]] and t 0, set
G G'=
w1 9
vf((2')
nu,,
where wi
L. Σ, r, for all i [n), and let the stepsize satisfy
B
0<75
1++11 1 8p
L
(67)
where 8 > 0, 50,p> p> O, and
((x, 8)
= - - a) (1 +s)
B(a, s)
= (1 (1-a) a1=a)(++55)
0p
Punmp A(a, 8) P)max - p (Prax -Puni) (1 Pmmin (1 p p-1)) LAM
B (3(a, P
Additionally, assume that
+ p(1 Pmii)= (Pmax Pmmin) 2 M(a,))
p(1 Pmmin) + (pmax Pmin)
Pmax
Pmax
for T >> 1 define aff element of the 100,20 xt
,..., wf chosen uniformly random, then
[[V < 2(f(x0) -8¹)
Go
E
7 +
(68)
0
Proof. Following the same approach employed in the proof for the SGD case, we obtain
E 12( f*1 < [[f(x')
f*1
1
L
E
| - $13 + 2
[
27
2
47

---

Published as a conference paper ICLR 2024
Let 8' E[fxx²) - f*), st = B and n" = E
-
Applying the previous lemma, we
obtain:
8++
? st+1
s 6' - 2 | [7]
1
L
r¹
7 S'
+
Br + (1 (1-8,)s²
20p
27
2
28p
8¹
8'+ 28
E
1
L
yd
2
27
28p
20
8 + 7 5¹ E
V f(x
||]
20p
By summing up inequalities for = 0, ...,, T 1, we get
T Σ ==
0 O 6 7 T
S 60
5"
2
R
||
28p
20
2
Finally, via multiplying both sides by
2 77
after rearranging we get:
T-1
E
[
25
+ s
7T
OpT
It remains to notice that the left-hand side can be interpreted as E [| where a" is chosen from the set fx= xx .........""""".................. T-1} uniformly at random.
Our analysis of this extension follows a similar approach as the one used by Fatkhullin et al. (202I), for algorithm they called EF21-PP. Presented analysis of EF21-W-PP has better provides better multiplicative factor in definition of B x L where in vanilla EF21-PP had B LoM- This fact improves upper bound on allowable step size in (67) ).
48

---

Published as conference paper ICLR 2024
H IMPROVED THEORY FOR EF21 IN THE RARE FEATURES REGIME
In this section, we adapt our new results to the rare features regime proposed and studied by Richtärik al.
2023
H.1 ALGORITHM
this section, we focus on Algorithm 6 which is an adaptation EF21 (as delineated in Algorithm [ that specifically employs TopK operators. This variant is tailored for the rare features scenario, enhancing the convergence rate by shifting from the average squared Lipschitz constants to the square of their average. The modifications introduced in Algorithm compared the standard EF21, are twofold and significant.
Primarily, the algorithm exclusively engages TopK compressors, leveraging the inherent sparsity present in the data. Additionally, the initial gradient estimates of are confined to the respective subspaces R as characterized by equation (71). With the exception of these distinct aspects, the algorithm's execution parallels that of the original EF21.
Algorithm EF21: Error Feedback 2021 with Topk compressors
1: Input: initial model x² Rd, initial gradient estimates of E .i......g Ih [R (as defined in equa-
tion (7I) stored at the server and the clients; stepsize y > 0; sparsification levels Ki,..., Kn. E [d];
number of iterations T > 0
2: Initialize: g" -. o on the server
3: for 0, 1, T-2....TT-11 do
4: Server computes x²+1 =x 779 and broadcasts x:++1 to all n clients
5: for f= 1, ...., n on the clients in parallel do
6: Compute uf TopK, f gf) and update ++1 gf + un.
7: Send the compressed message uf to the server
8: end for
9: Server updates gf = gf + uf for all i E [n]. and computes g"+l E gf
10: end for
11:
Output: Point x² chosen from the set {x", x..,, uniformly at random
H.2 NEW SPARSITY MEASURE
To extend our results the rare features regime, we need to slightly change the definition of the parameter e in the original paper. The way we do it is unrolled as follows. First, we recall the following definitions from (Richtárik al. 2023): z= ((i,)) e [n] x [d] [V)(
Vr e Rd).
(69)
and
I= fie in] (i.j) 2),
J= (j E [d] (1,5) 2).
(70)
We also need the following definition of TRy:
RC = {u- = (ui....,uu) E Rd uj = 0 whenever (i.j) E Z}.
(71)
Now we are ready for new definition of the sparsity parameter
n max
Wi
(72)
jE
49

---

Published as conference paper ICLR 2024
where wi is defined as in (25). We note that e recovers the standard definition from (Richtárik al. 2023 when for all i [n/]
H.3 LEMMAS
We will proceed through several lemmas. Lemma 13. Let ut E RR for all i [n]. Then, the following inequality holds:
m
12
Willg
(73)
72
Proof. Initially, we observe that
w. W,Uij
(74)
j=1
1=1
We note that for any j E
[d] it holds that
Σ wruls
Σ
willi
1EZ,
2
2
2
(75)
Wi Wi V'I,
Σ
W wp iez,
wi
Uij
wi
uig
iE
iEI,
iEI,
YEZ,
where on the last line we used the Jensen's inequality. Subsequent arithmetic manipulations and the incor- poration of definition 772) yield:
2
Σ
75
Σ
Walli
wi
Willi ij
iEZ,
Σ
2
Wi
iET,
i=1
max jEld
Σ wt iET,
wiul
1=1
Wi
2
(76)
T2
Substituting Equation (76) into Equation
74
completes the proof.
Lemma 14. Assume that of Rd for all E [m). Then, it holds for all > 0 that
l|g* fx < e G
(77)
n
50

---

Published as a conference paper ICLR 2024
Proof. By Lemma in Richtárik et al. 2023). for EF21 the update of stays in R& if of E Ry We then
proceed as follows:
llgs - vf((")))
of v((('')
Σ w
(of - V vi((z9))
(78)
Since of E R as was noted, and Vf((²") E Ry by the definition of R, then (of fa(())) also belongs to R... By Lemma 13. we further proceed:
llg 2
10
(g)
nuw;
(of v(i(z')))
im
Vs(e(())12
= G
n?w;
which completes the proof.
For the convenience of the reader, we briefly revisit Lemma from (Richtárik et al.
2023 Lemma 15 (Lemma 6 from Richtárik et al. (2023), ). If Assumption 2 holds, then for E [rl,, have
Σ ((V)()))) (V))))))) L
Σ (x. y²)²
Vx, Rd.
(79)
j:(iJ)EZ
Now, we proceed to the following lemma, which aims to provide tighter bound for the quantity E 1 [Vf((x)) (v)) 1.
L;
Lemma 16. !f Assumption holds, then
s cLAM - -y1
(80)
Proof. The proof commences as follows:
Vf(()) 2
Σn Li H(Ls)Ez
Σ ((f(()))) (Vf(())),)
Σ (zz-
Σ
Σ
21))
Σ Σ
(I - [
Σ Li (81)
J=1 R(.jeez
==
8(1,))
51

---

Published as conference paper ICLR 2024
To advance our derivations, we consider the maximum value over
Σ LE:
(:(1,))2
(f((x) V
(2) - 81)² Σ L,
==1
kli.d)E2
(xj - yi)² max
Σ Li x(f,j)ez
jEId
2
d Σ j=1
max
Σ Li
(Cg - -11)
SEId]
max jEId
Σ
|| y/1
max jEId]
Σ Li
||x yll
72
CLAM | y11
IET
what completes the proof.
For clarity and easy reference, we recapitulate Lemma 10 from Richtárik et 2023
Lemma 17 (Lemma 10 from Richtárik et al. (003)). The iterates of Algorithm method satisfy
||at
< (1 0(a)) | V/((')|1 + ((a))(() (())) - -V
(82)
where a min
min ve(m)
Lemma 18. Under Assumption
iteates of Algorithm ssatisfies
c++ < (1 ((a)) + +(aa) 22all - y112.
(83)
52

---

Published as a conference paper ICLR 2024
Proof. The proof a combination of Lemmas 16 and 17
1
G++1
36
||9
+1
Wi
1
O(a))llst
+ ((W)IVV((att)) v
Wi
(1 (1- (aa) +
3(a)
1
[ -
n²
t=1
(1 - O(a))*+ + 3(a)
25
Σ وا
\ - -Vi('')
n²
j=l
2
B(a) (1 (aa)
Σ فاj
11?
n² n
(1-8(a))G + 8(aa) LaMll - y11?
H.4 MAIN RESULT
And now we are ready to formulate the main result.
Theorem 11. Let Assumptions 7
and
hold. Let g E RR. for all i E [n].
1
min
min i
0<75 L+ LLMM((a)
Under these conditions, the iterates of Algorithm satisfy
|V < 2(f(x²) - -f)
Go + (a)T
(84)
7T
Proof. Let us define the Lyapunov function:
V' =
f(x)) - f + J0 G
(85)
20n
53

---

Published as conference paper ICLR 2024
We start the proof follows:
4+++11
83
f(x!+1) - fr + YC G++l
20n
f(x') - -
- 2/2
1
|| - x²112+ + 211 [f(x2)]1 +
70 G++1
2
2 2
2
20n
f(x') /
| S (=))
1 L
|| 21112
Y _
7e g
2
2y
2
2
20n
1 L
f(x') / 2
V / (=*)11²
||,
x212
2
+ - + NC
(1 0)G*
+ B
1x xx/13
2 n
20n
AM
f(z') fr + yc
G
7
f
L
3 c²
|1
x'11
20n
2
27
2
n²
V' f
1
7
8 e²
L
|
x²11
2/
20 n
20
V' (
Unrolling the inequality above, we get
T-1 Σ 1=0
0 o< < < -T 2
2
Vf('')1
from what the main result follows.
54

---

Published as conference paper ICLR 2024
I EXPERIMENTS: FURTHER DETAILS
2cr
Txd
13
1./9
1s-03
7z
5e
23
Dimension
Figure 4: The factor vB/0 as function of optimization variable dimension for several Topk compressors. The behavior is independent of properties of (.) and (z).
1.1 COMPUTING AND SOFTWARE ENVIRONMENT
We used the Python software suite FL.PyTorch (Burlachenko et al. 2021 to simulate the distributed en- vironment for training. We carried out experiments on compute node with Ubuntu 18.04 LTS, 256 GBytes DRAM DDR4 memory at 2.9GHz, and 48 cores (2 sockets with cores per socket) of In- tel(R) Xeon(R) Gold 6246 CPU at 3.3GHz. We used double-precision arithmetic during computing gradient oracles. All our computations were carried on CPU.
1.2
COMMENTS ON THE IMPROVEMENT
The standard EF21 analysis (Richtárik et al. 2021) allows utilize EF21 with maximum allowable step size y equal to:
3(a))
1-
== T.+ TQN
((a) =1 v1 a, ((a)
((a)
&
Our analysis allows replace the quantity LQM with LAM. This improvement has important con- sequence. The replaced quantity affects the step size by a factor of E(a) V P( This factor can be arbitrarily large d increases, shown in Figure 4 If d is increasing and the parameter k of TopK com- pressor fixed, then even a small improvement in the constant term can have a significant impact in an absolute sense to the computed step size if {(a) >> L.
B(a)
1.3 WHEN IMPROVED ANALYSIS LEADS TO MORE AGGRESSIVE STEPS
The quantity LQM V Σ L? plays essential role in EF21 analysis. As we saw with special consider- ation this quantity for EF21 and its extensions is improvable. The improved analysis allows us to replace it with LAM E L, Clearly, by the arithmetic-quadraie mean inequality,
L
L2M L 2 0.
55

---

Published as conference paper ICLR 2024
The difference LQM LAM can be expressed follows:
LaM + LAM
LQM LAM =
(LOM LAM)
[QM + LAM
Lom
LAM
1
L
LQM + LAM
LQM + LAM
12
The coefficient LAm in the last equation can be bounded from below and above as follows:
2LQ 2 max( LAM) S LQM + LAM S 2 min(Lin,, LAM) S 2LAM
As consequence, difference LQm LAM is bound above the estimated variance of L; divided by the mean of L;. also known as Index of Dispersion statistics. From this consideration, we can more easily observe that EF21-W can have arbitrarily better stepsize than vanilla EF21 if the variance of L; is increasing faster than the mean of L,
1.4 DATASET GENERATION FOR SYNTHETIC EXPERIMENT
First, we assume that the user provides two parameters: l R4 and I. R,. These parameters define the construction of strongly convex function fi(x), which are modified by meta-parameters E [-1, and z > 0, described next.
1. Each client initially has
1 - |A,r bull2, fi(x)
where A, is initialized in such way that fo is L, smooth and μy, strongly convex. Parameters defined in the following way:
L, - 1)) +. As.
2. The scalar value y E [-1, +1] informally plays the role of meta parameter to change the distribution of L; and make values of Li close to one of the following: (i) μı; (ii) L; (iii) (L n)/2. The exact modification of L; depends on the sign of meta parameter q.
Case E [0, 1]. In this case for first n/2 (i.e., i E [0, n/)) compute the value Li,- terp(Ts,/) 11 q). where lerp(a, b, b,(): Rd x Rd x [0, 1] + Rd standard linear interpolation lerp(a, b, t) = a(1
b bt.
The last n/2 (i e [n/2+1,n) nl) compute the value Li,g lerp(L;, q). For example, q = then Li, = L,, vi E [n]. and if = 1 then Lig- = for first n//2 clients and Li,9 L for last n/2 clients.
Case q [-. In this for all clients the new value Ligg lerp (L p2/2. -Q). In this case for example if q 0 then Li,g = T., and if q -1 then Ligg = (T. 12/2.
The process firstly fills the A, in such form that L, forms a uniform spectrum in [M, L] with the center of this spectrum equal to
2- And then as q - 1, the variance of Li is increasing. We use these new values Ligg for all e [n]] clients as a final target L.ow values. Due to numerical issues, found that it's worthwhile for the first and last client add extra scaling. First client scales Lı,g by factor 1/2, and last n-th client scales Lngg by factor 2. Here 2 2 0 is an additional meta-parameter.
3.
56

---

Published as conference paper ICLR 2024
4. Next obtained values are used to generate A, in such way that 42 (x) has uniform spectrum in (f..g.z Li,
5. As a last step the objective function fxx is scaled in such a way that it is L smooth with constant A Isolution where Isolution fixed solution.
value L. The b; for each client initialized
I.5 DATASET SHUFFLING STRATEGY FOR LIBSVM DATASET
Our dataset shuffling strategy heuristically splits data points so that Twar is maximized. It consists of the following steps:
1. Sort data points from the whole dataset according L constants. Sort all data points according to the smoothness constants of the loss function for each single data point.
2. Assign a single data point to each client Assume that there are total m data points in the datasets, and the total number of clients is At the beginning each client holds single data point [(
+ 1/2) 122
3. Pass through all points. Initialize set F= assigned from the previous step. For each point we find the best client i' E [n]]FF to assign the point in a way that assignment of point to client maximize L = L2M L Once the client already has m data points assigned to it, the client is added to the set
= O- Next, we pass through points except those
The set in the last step guarantees each client will have data points. general, this is heuristic greedy strategy that approximately maximizes Lvar under the constraint that each client has the same amount of data points equal to % Due to its heuristic nature, the Algorithm does not provide deep guarantees, but was good enough for our experiments.
57

---

Published as conference paper ICLR 2024
299
00
BP22-W
0F22
6202
10000
4000
20683
(a) var 20 4.45 x 10
(b) Lyar 2 1.97 x 106
FPZL
30-
10
20
20
CF2248
1971
(c) Lvar 2 1.08 X 10
(d) Lvar RJ 5.42 103
Figure 5: Convex smooth optimization. EF21 and FF21-W with Topt client compressor, n = 2 2000, = 10. The
where A = 0.01. Theoretical objective function is constitute of fx()) defined in Eq. 86. Regularization term x ||ا|| 2
step size. Full participation. Extra details in Table
J ADDITIONAL EXPERIMENTS
In this section, we present additional experiments for comparison EF21-W, EF21-W-PP, EF21-W-SGD with their vanilla versions. We applied these algorithms in a series of synthetically generated convex and non- convex optimization problems and for training logistic regression with non-convex regularized with using several LIBSVM datasets (Chang & Lin (011)). While carrying out additional experiments we will use three quantities. These quantities have already been mentioned in the main part, but we will repeat them here:
LQM =
LP LAM = 1=1
Lis
Lyar = LGM LAM =
4 Σ 1=1
The relationship between these quantities was discussed in Appendix L.3 In our experiments we used Topk compressor. The TopK compressor returns sparse vectors filled with zeros, except K positions, which cor- respond to K maximum values in absolute value and which are unchanged by the compressor. Even if this compressor breaks ties arbitrarily, it is possible to show that a 7 The compressor parameter is defined 9
without considering properties of ft. The quantities B, 0, are derived from a, and they do not depend on L.
J.1 ADDITIONAL EXPERIMENTS FOR EF21
Convex case with synthetic datasets. We aim to solve optimization problem ( in the case when the functions fi,..., fn are strongly convex. particular, we work with
X b + 2 |,:1
f((x) = |A,
(86)
where À 0.01. can be shown that L; ni linear regression model with convex regularized is presented in Figure 5] The total number of rounds for
Amax (A, T A.) A. The result of experiments for training
58

---

Published as conference paper ICLR 2024
23"1
(P21
10
1g-4
10
10:0
2000
1332
6383
E000
16000
2000
40.00
Reunds
2000
0000
10000
(a) Laa 23 4.45 x 106
(b) Lyar 2 1.97 x 10
EFRL
101
6732-
nie F921
-M- 1921
1p-n
2032
5030
00000
2000
6000
0003
30000
(c) Lyar R 1.08 x 10
(d) Lvar 5.42 10
Figure 6: Non-Convex smooth optimization. EF21 and EF21-W with Topt client compressor, n 2,000 d 10. The objective function constitute of fi()) defined in Eq. 887. Regularization term A Æ + with 100. Theoretical step size. Full client participation. Extra details in Table 2
simulation is 10, 000. Instances of optimization problems were generated for values L, == 50, / with several values of 2 with using the dataset generation schema described in Appendix [.4] The summary presented in Table I We present several optimization problems demonstrate
of derived quantities the possible different relationships between LQM and LAM- As we see from experiments, the EF21-W is superior as the variance of L; tends increase. The plots in Figure [5] (a)-(d) correspond decreasing variance of Li As we see, the variance of L; decreases, the difference between EF21-W and EF21 also tends to decrease. Finally, EF21-W is always at least as best as EF21.
Table 1: Convex Optimization experiment in Figure
Quantities which define theoretical step size.
Tag
L
z
Lvar
{= v
Lqm
LAM
NEF21
NEF21
50
10a
4.45
10"
18.486
2111.90
52.04
2.55
10-5
9.87 x 10-2
(b)
50
103
1.97 x 106
18.486
1408.49
63.56
3.83 X 10
8.16 X 10-
(c)
50
102
1.08 x 10a
18.486
339.34
80.97
1.58 x 10-4
6.46 x 10-4
(d)
50
0.8
5.42 x 103
18.486
112.51
85.03
4.69 x 10 6.16 x 10 4
Non-convex case with synthetic datasets. We aim to solve optimization problem 1 in the case when the functions fi...., are non-convex. In particular, we work with
f((x) = ||, bull
(87)
1=1 +1
The result of experiments for training linear regression model with non-convex regularization is presented Figure 6 The regularization coefficient À 100. Instances of optimization problems were generated for
values L 50, μ 1 and several values of 4, z for employed dataset generation schema from Appendix [.4]
59

---

Published as a conference paper ICLR 2024
The summary of derived quantities is presented in Table 2 We present various instances of optimization problems to demonstrate the different relationships between Lom and LAM- As we see in the case of small variance of L, algorithm EF21-W is least as best as standard EF21.
Table 2: Non-convex optimization experiment in Figure 6
Quantities which define theoretical step size.
Tag
q
z
Lar
{
8
LQM
LAM
7EF21
7EF21-W
(a)
50
1
10
4.45 x 10'
18.486
2126.25
252.035
2.52 x 10-5
2.03 x 10
(b)
50
1
10a
1.97 X 106
18.486
1431.53
263.55 55
3.74 X 10-5
1.95 X 10
(c)
1
10a
1.08 x 10s
18.486
433.05
280.958
1.21 10
1.83 10-4
(d)
50
0.8
1
5.42 X 10
18.486
294.39
285.022
1.17 10
1.81 10
Non-convex logistic regression on benchmark datasets. We aim to solve optimization problem | in the case when the functions fn. are non-convex. In particular, we work with logistic regression with a non-convex robustifying regularization term:
1
fx(z) = n4 Σ
log (1 + exp(p Viy a))z))
(88)
where (aij. Viy) Rdd 1-1,
We used several LIBSVM datasets Chang & Lin 2011) for our benchmarking purposes. The results are presented in Figure 7 and Figure The important quantities for these instances of optimization problems are summarized in Table From Figures (a). (b), (c), we can observe that for these datasets, the EF21-W is better, and this effect observable in practice. For example, from these examples, we can observe that 12.5K rounds of EF21-W corresponds to only 10K rounds of EF21. This improvement is essential for Federated Learning, which both communication rounds and communicate information during a round represent the main bottlenecks and are the subject of optimization. Figures / (d), (e). (f) demonstrate that sometimes the EF21-W can have practical behavior close to EF21, even if there is an improvement in step-size (For exact values of step size see Table 3). The experiment on AUSTRAL IAN datasets are presented in Figure g This example demonstrates that in this LIBSVM benchmark datasets, the relative improvement in the number of rounds for EF21-W compared to EF21 is considerable. For example 40K rounds of EF21 corresponds to 5K rounds of EF21-W in terms of attainable [['
Table 3: Non-convex optimization experiments in Figures 7
Derived quantities which define theoretical step size.
Tag
Lvar
LoM
LAM
7EF22
"EEF21 w
(A) WZA
0.781
3.283
692.49
2.921
2.291
5.678 x
7.237
0.784
2.041
6902.49
2.402
1.981
10
8.689 10
(c) W3A.
0.801
1.579
6022
2.147
1.741
7.772 x 10
9.523 x 10
(d) MUSHROOMS
2.913
5,05 x
226.
3.771
3.704
1.166 x 10
1.187 x 10
SPLICE
96.082
2.25 10"
122.497
113.46
10
7.14
(b PHISHING
0.412
9.2 10
198.498
0.422
0.428
1.670 x 10
1.674 x 10
(g) AUSTRALIAN
3.98 x
1.1 10
18.488
3.35 x 107
3.96 10
9.733
10
8.007 x 10
Non-convex logistic regression with non-homogeneous compressor. In this supplementary experiment,
we leveraged the AUSTRALIAN LIBSVM datasets (Chang & Lin 2011) train logistic regression, incorpo-
60

---

Published as conference paper ICLR 2024
DF21.W
C72:4
LP21
1721
6743
12-1
10-1
5030
10036
15003
20303
5000
70060
15032
23000
10
5003
12003
15200
70000
(a) WIA
(b) N2A
(c) W3A
2F21.W
EF21-W
10
1921
10-1
12a4
5000
15500
13000
20002
35070
27000
15300
2000
(d) MUSHROOMS
(c) SPLICK
PHI INIG
Figure 7: Non-Convex Logistic Regression: comparison of EF21 and EF21-W. The used compressor is Topt. The
number clients L, 000. Regularization term À Σ #f+1" with 0.001. Theoretical step size. Full client
participation. The objective function is constitute of fx) defined in Eq. 88 Extra details are in Table
4x10
1002
20020
30200
42000
(g) AUSTRALIAN
Figure 8: Non-Convex Logistic Regression: comparison the performance standard EF21 and EF21-W. The used =7 compressor Top1. The number of clients n 200. Regularization term X a +1' with À 1,000. Thcoretical step size. The objective function constitute of f(() defined in Eq. 88
Extra details are in Table
rating a non-convex sparsity-enhancet regularization term defined in Eg. 88). The experiment featured the utilization of -onooooggeneuus compressor known as Natural by Horvááth et al. (2022), belonging the family of unbiased compressors and adhering to Definition] 3 with w 1/8. This compressor, in random- ized manner, rounds the exponential part and zeros out the transferred mantissa part when employing the standard IEEE 754 Standard for Floating-Point Arithmetic TEEE Computer Society (2008) representation for floating-pott numbers. Consequently, when using a single float-point format (FP32) during communi- cation, only 9 bits of payload per scalar need to be sent the master, and the remaining 23 bits of mantissa can be entirely dropped.
The experiment results depicted in Figure 9 In this experiment, fine-tuned the theoretical step size by multiplying it with a specific constant. As we can see the EF21-W consistently outperforms EF21 across all corresponding step-size multipliers. As EF21-W operates effectively by utilizing unbiased non-
61

---

Published as conference paper ICLR 2024
10a
101
EF21 x5
EF21 Nat: x6
EF21-W
10
10-10
EF21-W W Nat: x40
10-2
EF21 W Nat: x40
-5
EF21 Nat: x6
10-14
EF21 Nat: x6
10 -0
EF21 Nat: x40
10-15
EF21 Nat: x40
10000
200
(a)
(b)
Figure 9: Non-Convex Logistic Regression: comparison the performance of standard EF21 and EF21-W. The used compressor for EF21 EF21-W is Natural Humpressor/Horváthh et al. (2022). number clients n 200. The objec- with À 1, 100.. Multipliers tive function is constitute of fx) defined in Eq. (88). Regularization term A E 2341
=f
thcoretical step size. Full participation. Computation format single precision (FP32), Datasct: AUSTRALIAN.
homogeneous compressors, and the advantages over EF21 extend beyond the scope of applying EF21-W solely to homogeneous compressors. Finally, it is worth noting that the increased theoretical step size in EF21-W does not entirely capture the practical scenario of potentially enhancing the step size by signifi- cantly large multiplicative factor (c.g., x40), which remains a subject for future research.
62

---

Published as conference paper ICLR 2024
10
ER21
EF21-01P
10
12
12.
101
104
15003
20000
5500
5000
15000
Rounds
Rounds
Rounds
(a) L var = 4.45 X 106
(b) Var 1.97 X 10
(c) Var 1.08 10S
Figure 10: Convex smooth optimization. EF21-PP and EF21-W-PP with Topt client compressor, = 2000, == 10.
The objective function is constiute of (+( defined in Eq. (89). Regularization term X ||=||" 0.01. Theoretical
step size. The objective function constitute of f((x) defined Eq. (9.). Each client participates in each round with probability p. = 0.5. Extra details are Table
J.2 ADDITIONAL EXPERIMENTS FOR EF21-W-PP
Convex case with synthetic datasets.
Table 4: Convex optimization experiment in Figure 10
Derived quantities which define thcoretical step size.
Tag
L
q
Lyar
Lqu
LAM
NEF21-PP PP
NEF21-W-PP
(a)
50
10a
4.45 x 10"
18.486
2111.90
52.04
2.55 x 10
9.87 x 10
(b)
10a
1.97 x 106
18.486
1408 49
63.56
3.83 x 10-5
8.16 10
(c)
1
10a
1.08
10"
18.486
339.34
80.97
1.58
10
6.46
10
We aim to solve optimization problem (T) in the case when the functions f1,..., In are strongly convex. In particular, we choose:
A |
f((x) = | ball
(89)
this synthetic experiment, we have used the maximum allowable step size suggested by the theory of EF21-PP and for the proposed EF21-W-PP algorithm. The initial gradient estimators have been initialized as . = Vf((=") for all i. The number of clients in simulation
2000, dimension of optimization problem d 10, number of samples per client n, 10, and number of communication rounds is 10, 000. For both EF21-PP and EF21-W-PP clients we used Top1 biased contractile compressor. In our experiment, each client's participation
each communication round is governed by an independent Bernoulli trial which takes p; = 0.5. The result of experiments for training linear regression model with a convex regularizer is presented in Figure 10 The regularization constant was chosen to be À 0.01. Instances of optimization problems were generated for values L 50,u 1 with several values of q and The summary of derived quantities is presented Table 4 We present several optimization problems to demonstrate the possible different relationships between LQM and LAM. As see from experiments, the EF21-W-PP is superior as the variance of L, tends to increase. As we can observe EF21-W-PP always at least as best as EF21-PP.
Non-convex logistic regression benchmark datasets. We provide additional numerical experiments which we compare EF21-PP and EF21-W-PP for solving (I. We address the problem of training a binary classifier via logistic model on several LIBSVM datasets (Chang & Lin 2011) with non-convex
63

---

Published as conference paper ICLR 2024
EF21-449P
DF21-PP
EF21
10-1
10-2
10-2
20000
(a) WIA
(b) W2A
EF21-W-PP
10-2
EF21-W-99
EF21-PP
EF21-PP
10-1
10-4
10"
10000
20000 Rounds
30000
40000
10000
20000 Rounds
30000
40000
(c) W3A
(d) PHISHING
Figure 11: Non-Convex Logistic Regression: comparison of EF21-PP and EF21-W-PP. The used compressor Top1.
2 The number clients 000. Regularization term A AE= +I 0.001. Thcoretical step size. Each client
participates in each round with probability p; 0.5. The objective function is constitute of f((x) defined in Eq. 990 Extra details are in Table
regularization. We consider the case when the functions fI...., fn are non-convex; in particular, we set fxx follows:
fxxx) = n; y=1
1
Σ
log (1 exp(- Vig a.Jz)) X Σ +1
(90)
where (aij, Viy) Rdd 1-1,
We conducted distributed training of logistic regression model on W1A, W2A, W3A, PHISHING, and AUSTRALIAN datasets with non-convex regularization. The initial gradient estimators set of ff(²²) for all i E [ni]. For comparison of EF21-PP and EF21-W-PP, we used the largest step size allowed by theory.
We used the dataset shuffling strategy described in Appendix [.5 The results presented in Figure IT and
Figure 12
The important quantities for these instances of optimization problems are summarized in Table 5
Table 5: Non-Convex optimization experiments in Figures 11
12
Quantities which define thcoretical step size.
Tag
Lyaar
LQM
LAM
"EF21 -PP
?EF21 WP
(a WIA
0.781
3.283
2.921
2.291
2.315 x 10
2.95
10
0.784
2.041
2.402
1.931
2.816 x 10-4
3.503 10 10-1
0.801
1.579
2.147
1.741
3.149 x 10
3.884
10
(d) PHISHING
0.412
9.2 x 10
0.429
0.428
6.806 x 10-3
6.823 x 10 10-3
(6) AUSTRALIAN
3.96 x 10"
1.1 x 1026
3.35 10"
3.96 x 10
3.876 10 10-10
3.243
10
64

---

Published as conference paper ICLR 2024
10
10a
EF21-W-PP
EF21-PP
20000
40000
60000
80000
Rounds
AUSTRALIAN
Figure 12: Non-Convex Logistic Regression: comparison of EF21-PP and EF21-W-PP. The used compressor is Topl. The number of clients = 200. Regularization term X X #/+1' with À 1, 000.. Theoretical step size. Each client
participates each round with probability p; = 0.5. The objective function is constitute ft(x) defined in 90 Extra details are in Table
From Figure 11 (a), (b), (c), can observe that for these datasets, the EF21-W-PP better, and this effect observable in practice and is not negligible. Figure (d), demonstrate that sometimes EF21-W-PP terms of the full gradient at last iterate can have slightly worse behavior compared to EF21-PP, even though theory allow more aggressive step-size (For exact values of step size see Table 5 The experiment on AUSTRALIAN dataset is presented in Figure 12] This example demonstrates that this LIBSVM benchmark datasets, the relative improvement in the number of rounds for EF21-W-PP compared to EF21-PP is considerable. The EF21-W-PP exhibits more oscillation behavior in terms of [=* for AUSTRALIAN dataset, however can observe in expectation (x*)) tends decrease faster compare EF21-PP.
J.3 ADDITIONAL EXPERIMENTS FOR
The standard EF21-SGD with the analysis described in Corollary 4 (Fatkhullin 2021] allows perform- ing the optimization procedure with maximum allowable step size up to the factor of equal to:
-1
B
TEF2 = L.
V
LQM
last expression quantities 9 = 1- (1- +1 (1+11) +2), v), and B1 = 2(1 a11-a) (1+ 8) -- Improved
analysis for EF21-W-SGD allows to apply step size:
B
TEFZ1-WASGD
L
LAM
Therefore in terms of step size
NeF21-WSGD
TeF21-8GD
65

---

Published as conference paper ICLR 2024
and EF21-W-SGD exhibits a more aggressive step-size.
We conducted distributed training of logistic regression model on W1A, W2A, W3A, PHISHING, AUSTRALIAN datasets with non-convex regularization. For datasets, we consider the optimization prob- lem where
n2 log (1 + exp(-xp Vi a.))))
f((z)
Σ +1
(91)
and (ay, Biy) Rd x (-1,1}.
The initial gradient estimators are set to of EF21-W-SGD, we used the largest step size allowed by theory. The dataset shuffling strategy repeats the strategy that we have used for EF21-W-PP and EF21-W and it described in Appendix [.5 The algorithms EF21-SGD and /EF21-W-SGD employed an unbiased gradient estimator, which was estimated by sampling a single training point uniformly at random and independently at each client.
(x())) for all [n]. For comparison of EF21-SGD and
Table Non- Convex optimization experiments Figures
13
14 Quantities which define theoretical step size.
Tag
L
Lyur
Lom
LAM
7EF21 SGD
"YFF2 SGDD
0.781
3.283
2.921
2.291
4.014 x 10
5.118
10
0.784
2.041
2.402
1.931
4.882 x 10-4
6.072 10"
W3A
0,801
1.579
2.147
1.741
5.460 x 10
6.733 X 10
(1 PHISHING
0,412
9.2 x 10
0.429
0.428
1.183 x 10
1.186 x 10
( AUSTRALIAN
3.96 10"
1.1 10
3.35 10'
3.96 10"
3.876
10
3.243
10
The results are presented in Figure 13 and Figure 14 The important quantities for these instances of op- timization problems summarized in Table In all Figures 13 (a), (b), (c), (d) for these datasets, the EF21-W-SGD is better, and this effect is observable in practice. The experiment on AUSTRALIAN datasets are presented Figure [4] This example demonstrates that in this LIBSVM bench- mark datasets, the relative improvement in the number of rounds for EF21-W-SGD compared to EF21-SGD is considerable. Finally, we address oscillation behavior to the fact that employed step size for EF21-SGD too pessimistic, and its employed step size removes oscillation of || fx"))"
observe that
K REPRODUCIBILITY STATEMENT
To ensure reproducibility, we use the following FL.P PL.oorh simulator features: (i) random seeds were fixed for data synthesis; (ii) random seeds were fixed for the runtime pseudo-random generators involved EF21-PP and EF21-SGD across clients and the server; (iii) the thread pool size was turned off to avoid the non-deterministic order of client updates in the server.
If you are interested in the source code for all experiments, please contact the authors.
66

---

Published as conference paper ICLR 2024
2F21-5G0
EF21-SGD
10-1
10
10-4
10-2
5000
10000
15000
20000
5000
10000
35000
20000
Rounds
Rounds
(a) W1A
(b) W2A
B221-N-5G
10"
BF21-W-SGD
U221-500
EF21-560
10-2
10-3
10000
20000
PHISHING
comparison of EF21-SGD and EF21-W-SGD. The used compressor is Top1. The SGD gradient estimator SGD-US, = 1. The number of clients 1, 000. The objective function constitute of Non-Convex logistic regression:
Figure 13:
23
À 0.001. Thcoretical step size. See also 6 fi fx) defined in Eq 91). Regularization term A E a341*
10a
10a
EF21-W-SGD
EF21-SGD
20000
80000
Rounds
AUSTRALIAN
Figure 14: Non-Convex logistic regression:
comparison of EF21-SGD and EF21-W-SGD. used compressor is Top1.
The SGD gradient estimator is SGD-US, r = 1. The number clients n 200. The objective function is constitute
fx)) defined in Eq. (T). Regularization term À An x? Extra details are in Table
with 000. Theoretical step size. Full participation.
2
67


Reviews:
[{"review_id": "D1TFIIHuna", "reviewer": "Reviewer_JbXd", "summary": "Error Feedback (EF) uses contractive compressors to improve distributed training methods. EF has been around for almost a decade(Siede et al 2014), and suitable theory had been developed for its variant EF21 (Richtárik et al 2021). In this work, the authors improve the analysis of EF21 by allowing for larger step sizes through a refined analysis of varying smoothness constants of the different client loss, leading to an improvement from the quadratic mean to the arithmetic mean of the respective constants.\nThey describe how they came up with this idea, and by doing this they propose a variant of EF21 called EF21-W which weights the different client gradient inversely proportional to their smoothness constant. They also provide n improved analysis of EF21 is achieved by extending an analogous analysis of EF21-W.\nIn the supplementary material they extend the algorithm to more advanced versions like EF21 SGD which uses stochastic gradients instead of gradients and EF21 PP which requires partial participation of clients. The authors also provide experimental results for logistic regression with non-convex regularization. They show significant improvement for largely varying smoothness constants and very limited improvements for more balanced cases.", "questions": "- Can you provide experiments that clarify whether the improvement of the results in the setting of largely varying smoothness constants is coming from larger admissible step size or from the different weighting of the clients?\n- Please include a discussion of the connection between the idea underlying EF21-W and importance sampling.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper is very well written, in particular, the narrative that led the authors to the results is instructive and plausible. The claimed convergence theory is rather exhaustive and applies under quite general assumptions (Assumptions 1-3 only require bounds on the smoothness constants and a lower bound on the optimal function value; a version of the results that leads to linear convergence uses Assumption 4, Polyak-Lojasiewicz inequality, which is a rather weak condition for linear convergence). The improvement in the admissible stepsize for EF21 will be potentially relevant for distributed optimization with largely varying smoothness constants. Furthermore, the authors also provide versions of their algorithms in the stochastic setting (EF21-SGD) and a setting of partial participation (EF-21PP).", "weaknesses": "From their theory and experiments, it remains unclear whether the Improvement of the results are coming from the provably larger admissible step size or from different weighting of the clients (as in EF21-W) -- the experiments only seem to compare EF21 with the original stepsize to EF21-W with the improved stepsize (similarly, EF21-W-SGD vs. EF21-SGD).\nFurthermore, the novelty of the underlying ideas is not sufficiently discussed. In particular, the usage of differently weighted clients’ gradients based on Lipschitz constants seems to be very related to similar ideas used in importance sampling fro stochastic optimization. (e.g., Zhao, P., & Zhang, T., \"Stochastic optimization with importance sampling for regularized loss minimization\", ICML 2015). Ideally, a discussion of the connection of their work with this body of literature should be part of the paper.", "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": "", "extra_scores": {}}, {"review_id": "xYXtEagZXa", "reviewer": "Reviewer_uTDX", "summary": "This paper proposes a new weighted version of EF21 with better theoretical guarantees. Experiments show that the proposed EF21-W outperforms the baselines.", "questions": "1. If we simply re-weight the gradients with $w_i$ in the gradient averaging without using communication compression or EF21, would we obtain the same improvement in the theoretical results (from quadratic mean to arithmetic mean of the smoothness constants)?\n\n2. For the more complicated models or tasks, such as neural networks, how to obtain the smoothness constants and apply EF21-W?", "limitations": "", "rating": 3, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "1. This paper proposes a new weighted version of EF21 with better theoretical guarantees. \n\n2. Experiments show that the proposed EF21-W outperforms the baselines.", "weaknesses": "1. It seems that the proposed EF21-W is simply a method that uses the local smoothness constants to obtain a weighted average of the local gradients sent by the workers, which actually has nothing to do with EF21. I mean, if we totally remove the communication compression and EF21 parts, we could still obtain a distributed gradient descent algorithms with weighted average of gradients on the server side and the same improvement in the theoretical results (from quadratic mean to arithmetic mean of the smoothness constants). Adding communication compression and EF21 seems too deliberate to me and prevents the paper from presenting the core idea in a clean and crispy manner.\n\n2. The experiments seem too simple and small to me. I mean, the linear/logistic regression models on libsvm datasets could be easily trained in a short time on some modern and cheap hardware such as a normal laptop, which doesn't require distributed training or communication at all. I understand these experiments are meant to verify the theoretical results, but the experiment settings are just too simple and synthetic, which makes the experiments seem meaningless to me.\n\n3. The proposed algorithm, EF21-W is far from practical, since in real-world complicated models and training tasks, typically it is very difficult to obtain the smoothness constants, while the smoothness constants are essential for EF21-W.", "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": "", "extra_scores": {}}, {"review_id": "7OqscCq0Y4", "reviewer": "Reviewer_ZKKe", "summary": "This paper presents with a weighted version of EF21, a modern form of error feedback, which previously offers the best theoretical guarantees under the weakest assumptions. And the proposed weighted version of EF21 improved the dependence on the quadratic mean of certain smoothness parameters to their arithmetic mean. \n\nIn addition to the detailed description of the weighted error feedback algorithms, this paper introduces the steps took to discover the weighted EF21, starting from adding one more client node to enhance the convergence rate in EF21, to generalizing the cloning idea, replacing the quadratic mean of the smoothness parameters to their arithmetic mean, improving convergence rate, to overcoming the shortcomings with cloning clients with weighted version of EF21. \n\nFinally, the paper conducted experiments on non-convex logistic regression on benchmark datasets and non-convex linear regression on synthetic datasets, showing a faster convergence rate in situations of high variance in smoothness constants.", "questions": "Why is top1 compressor chosen to be employed in all experiments? If the algorithm is designed for a specific setting, can that be clearly described in the paper?\n\nWhy is the number of clients set to be 1000 in the logistic regression experiments, and set to be 2000 in the linear regression experiments? Is it chosen for a specific problem setting? Will the algorithm behave differently with different number of clients?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper proposed an intuitive algorithm based on EF21, improving the convergence rate in cases of high variance in smoothness constants, taking the readers through the journey of discovering the algorithm. The process of discovery is clearly described in the paper with simple and effective examples. The math presented in the main paper is enough to clarify the core idea behind the algorithm, and more detailed explanations can be found in the appendix. After taking the readers through the discovery process, the paper presents with 2 sets of experiments conducted on the new algorithm, accompanied by clear figures illustrating the improvement of the algorithm over the original EF21.", "weaknesses": "This paper did not discuss the choices of compressor used in the experiments, as in the original paper of EF21. In the EF21 paper, experiments were conducted on fine-tuning k and the step sizes, which is overlooked in this paper. \n\nThis paper conducted experiments under specific settings with limited explanation for the parameters chosen, such as the number of clients in each experiment.", "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": "", "extra_scores": {}}, {"review_id": "VsWrJrlsrG", "reviewer": "Reviewer_XNZi", "summary": "The authors offers a refined analysis of the popular EF21 algorithm to show that this algorithm actually depends on the arithmetic mean of Lipschitz constants instead of the quadratic mean. In the process the authors also proposed new versions of EF21, and showed that this analysis can be extended to a wide variety of EF21 variants.", "questions": "N/A", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. Improves theoretical understanding of existing popular approach.\n2. Presentation is very clear, and easy to follow\n3. Contribution is meaningful, because it further promotes the use of EF21 under certain cases.", "weaknesses": "1. Did not propose a newer version of EF21 that outperforms the original one (probably not a weakness, but more of a hope)", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)