Momentum Provably Improves Error Feedback!
Authors: Ilyas Fatkhullin
Alexander Tyurin
Peter Richtárik
Venue: NeurIPS 2023 poster (2023)
Keywords: Heavy-ball momentum
Polyak momentum
Error feedback
Federated Learning
Distributed Optimization
Stochastic optimization
Nonconvex optimization

Abstract: Due to the high communication overhead when training machine learning models in a distributed environment, modern algorithms invariably rely on lossy communication compression. However, when untreated, the errors caused by compression propagate, and can lead to severely unstable behavior, including exponential divergence. Almost a decade ago, Seide et al. [2014] proposed an error feedback (EF) mechanism, which we refer to as EF14, as an immensely effective heuristic for mitigating this issue. However, despite steady algorithmic and theoretical  advances in the EF field in the last decade, our understanding is far from complete. In this work we address one of the most pressing issues. In particular, in the canonical nonconvex setting, all known variants of EF rely on very large batch sizes to converge, which can be prohibitive in practice. We propose a surprisingly simple fix which removes this issue both theoretically, and in practice: the application of Polyak's momentum to the latest incarnation of EF due to Richtárik et al. [2021] known as EF21. Our algorithm, for which we coin the name EF21-SGDM, improves the communication and sample complexities of previous error feedback algorithms under standard smoothness and bounded variance assumptions, and does not require any further strong assumptions such as bounded gradient dissimilarity. Moreover, we propose a double momentum version of our method that improves the complexities even further. Our proof seems to be novel even when compression is removed form the method, and as such, our proof technique is of independent interest in the study of nonconvex stochastic optimization enriched with Polyak's momentum.

Momentum Provably Improves Error Feedback!
Iyas Fatkhullin ETH AI Center ETH Zurich
Alexander Tyurin KAUST
Peter Richtárik KAUST
Abstract
Due the high communication overhead when training machine learning models in a distributed environment, modern algorithms invariably rely on lossy communi- cation compression. However, when untreated, the errors caused by compression propagate, and can lead to severely unstable behavior, including exponential diver- gence. Almost decade ago, Seide al. [2014] proposed an error feedback (EF) mechanism, which we refer to EF14, as immensely effective heuristic for mitigating this issue. However, despite steady algorithmic and theoretical advances in the EF field in the last decade, our understanding is far from complete. In this work we address one of the most pressing issues. particular, in the canonical non- convex setting, all known variants of EF rely very large batch sizes to converge, which can prohibitive in practice. We propose a surprisingly simple fix which removes this issue both theoretically, and in practice: the application of Polyak's momentum to the latest incarnation of EF due to Richtárik et al. [2021] known as EF21. Our algorithm, for which we coin the name EF21-SGDMA improves the com- munication and sample complexities of previous error feedback algorithms under standard smoothness and bounded variance assumptions, and does require any further strong assumptions such as bounded gradient dissimilarity. Moreover, we propose double momentum version of our method that improves the complexities even further. Our proof seems to be novel even when compression is removed from the method, and such, our proof technique of independent interest in the study of nonconvex stochastic optimization enriched with Polyak's 's momentum.
Introduction
Since the practical utility of modern machine learning models crucially depends on our ability to train them on large quantities of training data, imperative to perform the training distributed storage and compute environment. In federated learning (FL) [Konečný et al., 2016, Kairouz, 2019], for example, data is naturally stored distributed fashion across a large number of clients (who capture and own the data in the first place), and the goal is to train single machine learning model from wealth of all this distributed data, in a private fashion, directly on their devices.
1.1 Formalism. We consider the problem of collaborative training of single model by several clients in data- paralll fashion. In particular, we aim to solve the distributed nonconvex stochastic optimization problem
min MERI
f(x) 1
fa(x) == EENND [f((z. E:),
== n,
where n is the number of clients, E Rd represents the parameters of the model we wish to train, and (x) is the (typically nonconvex) loss model parameterized by the vector æ on the data D; owned by client Unlike most works in federated learning, we do not assume the datasets to be similar, i.e., we allow the distributions .,,...,22 D, to be arbitrarily different.
King Abdullah University of Science and Technology, Thuwal, Saudi Arabia.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

We interested in the fundamental problem of finding an approximately stationary point of f in expectation, i.e., we wish to find a (possibly random) vector & E R such that E [[]][ S e. In order solve this problem, we assume that the n clients communicate via an orchestrating server. Typically, the role of the server is to first perform aggregation of the messages obtained from the workers, and to subsequently broadcast the aggregated information back to the workers. Following an implicit assumption made in virtually all theoretically-focee -occusee papers on communication-effice training. we also assume that the speed of client-to- to-workers broadcast is so fast (compared to speed of workers-to- to--toieeeett communication) that the cost associated with broadcast can be neglected?.
1.2 Aiming for communication and computation efficiency at the same time. In our work, we pay attention to two key aspects of efficient distributed training- communication cost and computation cost for finding an approximate stationary point 4. The former refers the number of bits that need to be communicated by the workers to the server, and the latter refers to the number of stochastic gradients that need be sampled by each client. The rest of the paper can be summarized as follows: We pick one of the most popular commuiicatio--efiiiee
gradient-type methods (the EF21 method of Richtárik al. [2021]- the latest variant of error feedback pioneered by Seide al. [2014]) and modify it in a way which provably preserves its communication complexity, but massively improves its computation/sample complexity, both theoretically and in practice.
2 Communication Compression, Error Feedback, and Sample Complexity
Communication compression techniques such as quantization [Alistarh et al., 2017, Horváth et al., 2019a] and sparsification [Seide et al.. 2014, Beznosikov et al., 2020] are known to be immensely powerful for reducing the communication footprint of gradient-type' methods. Arguably the most studied, versatile and practically useful class of compression mappings are contractive compressors.
Definition 1 (Contractive compressors). We say that (possibly randomized) mupping C Rd - Rd is a contructive compression operator if there exists a constant 0 < a S 1 such that
Vo TR... E [[[((t) [2] s (1 a)) ||=
(2)
Inequality (2) is satisfied by a vast array of compressors considered in the literature, including numerous variants of sparsification operators [Alistarh et al., 2018, Stich et al., 2018], quantization operators [Alistarh et al., 2017, Horváth et al., 2019a], and low-rank approximation [VVggels et al., 2019, Safaryan et al., 2022] and more [Beznosikov et al., 2020, Safaryan et al., 2021J. The canonical examples are i) the TopK sparsifier, which preserves the K largest components of in magnitude and sets all remaining coordinates to zero [Stich et al., 2018], and ii) the (scaled) Rand sparsifier, which preserves a subset of K components of x chosen uniformly random and sets all remaining coordinates to zero [Beznosikov et al., 2020]. In both cases, (2) is satisfied with a = K/a.
2.1 Brief history of error-feedback
When greedy contractive compressors, such TopK, are used in direct way compress the local gradients in distributed gradient descent (GD), the resulting method may diverge exponentially, even on strongly convex quadratics [Beznosikov et al., 2020]. Empirically, instability caused by such a naive application of greedy compressors was observed much earlier, and a fix was proposed in the form of the error feedback (EF) mechanism by Seide et al. [2014], which we henceforth call EF14 or EF14-SGD (in the stochastic case).* 4 To the best of our knowledge, the best sample complexity of EF14-SGD for finding a stationary point in the distributed nonconvex setting given by Koloskova et al. [2020]: after
+ oan -1g -4) samples EF14-SGD finds point x such that E||| f II] < E, where a is the contraction parameter (see Definition 1). However, such
*Wiile this is a reasonahle assumption in many practical situations [Mishchenko et al., 2019, Kairouz, 2019], some works consider the regime when the server-to- workers broadcast cannot be neglected [Horváth et al., 2019a, Tang et al., 2020, Philippenko and Dieuleveut, 2020, Kovalev et al., 2021, Fatkhullin et al., 2021, Gruntkowska al., 2022].
FFor Newton- typon methods, see [Islamov et al., 2022] and references therein. "In Appendix A. we provide more detailed discussion on theoretical develepments for this method.
'Here o² is the bound on the variance of stochastic gradients at each node, see Assumption 2. When referring the sample complexity we count the number of stochastic gradients used only at one of the n nodes rather than by all nodes in total. This is meaningful notion because the computations are done in parallel.

---

EF21-SGD-Kren
3.0
#F21-3GD
2.5
0b/o23re voleo
2.0
1.5
EF21 5GD (n= 500)
2F21-SGD (n 5000)
10000)
2000
4000
6.00
8000
10000
2000
4000
6000
8000
10000
Meration.
Rutution,
(a) Divergence for TI = 1.
(b) No improvement with ya.
Figure 1: Divergence of EF21-SGD the quadratic function f()) 2 | E IR, using the Top1 compressor. See the proof of Theorem I for details on the construction of the noise &: starting point x (0, 0.01) Unlike EF21-SGD, our method EF21-SGDM does not suffer from divergence and is stable near optimum. Figure lb shows that when increasing the number of nodes n, EF21-SGD applied with B = does not improve, and, moreover, diverges from the optimum even faster. All experiments use constant parameters 77 0.1 0.1/v7 10 see Figure for diminishing parameters. Each method is run 10 times and the plot shows the median performance alongside the 25% and 75% quantiles.
= L. 1. The
an analysis has two important deficiencies. First, the deterministic case (when exact gradients are computable by each node), the analysis only gives the suboptimal 3(=-²) iteration complexity, which is suboptimal compared to vanilla (i.e., non-compressed) gradient descent, whose iteration complexity is 3).-2). Second, their analysis relies heavily additional strong assumptions, such as the bounded gradient (BG) assumption, Ej]l V & 3 G2 for all x E Rd i [n]. E D., or the bounded gradient similarity (BGS) assumption, > [V ff < G for all Rdd, Such assumptions are restrictive and sometimes even unrealistic. and BGS might not hold even in the case of convex quadratic functions." Moreover, it was recently shown that nonconvex analysis of stochastic gradient methods using a BG assumption may hide an exponential dependence on the smoothness constant in the complexity [Yang et al., 2023].
particular, both BG
In 2021, these issues were partially resolved by Richtárik al. [2021], who propose modification of the EF mechanism, which they call EF21. They address both deficiencies of the original EF14 method: they removed the BG/BGS assumptions, and improved the iteration complexity O( in the full gradient regime. Subsequently. the EF21 method was modified in several directions, e.g.. extended bidirectional compression, variance reduction and proximal setup [Fatkhullin et al., 2021], generalized from contractive to three-point compressors [Richtárik et al., 2022] and adaptive compressors [Makarenko et al., 2022], modified from dual (gradient) to primal (model) compression [Gruntkowska et al., 2022] and from centralized to decentralized setting [Zhaa et al., 2022]. For further work, we refer to [Wang et al., 2022, Dorfman et al., 2023, Islamov et al., 2022].
2.2 Key issue: error feedback has an unhealthy appetite for samples!
Unfortunately, the current theory of EF21 with stochastic gradients has weak sample complexity guarantees. In particular, Fatkhullin et al. [2021] extended the EF21-GD method, which is the basic variant of EF21 using full gradient the clients, to EF21-SGD, which uses a "large minibatch" of
stochastic gradients instead. They obtained O ag + - sample complexity for their method.
Later, Zhao al. [2022] improved this result slightly" to O + _ shaving off one a in the stochastic term. However, it is easy to notice several issues in these results, which generally feature the fundamental challenge of combining biased gradient methods with stochastic gradients.
Mega-batches. These works require all clients to sample "mega-bate batches" of stochastic gradi- ents/datapoints in each iteration, of order (ee-2), in order control the variance coming from stochastic gradients. In Figure 1, we find that, in fact, a batch-free (i.e., with mini-hatch size =
'For example, one can consider f((x) T A.x with A, gdxd, for which BG or BGS assumptions hold only in the trivial cases: matrices A, are all zero or all equal to each other (homogeneous data regime). The result was obtained under more general setting of decentralized optimization network.

---

version of EF21-SGD diverges even on very simple quadratic function. We also observe a similar behavior when a small batch B >> 1 is applied. This implies that there is a fundamental flaw in the EF21-SGD method itself, rather "just" problem of the theoretical analysis. While mega-batch methods are common in optimization literature, smaller batches are often preferred whenever they "work". For example, the time/cost required obtain such large number of samples each iteration might be unreasonably large compared to the communication time, which is already reduced using compression. Moreover, when dealing with medical data, large batches might simply be unavail- able [Rieke et al., 2020]. In certain applications, such as federated reinforcement learning (RL) or multi-agent RL, is often intractable to sample more than one trajectory of the environment in order to form a gradient estimator [Mitra et al., 2023, Doan et al., 2019, Jin et al., 2022, Khodadadian et al., 2022]. Further, a method using a mega-batch at each iteration effectively follows the gradient descent (GD) dynamics instead of the dynamics of (mini-hatch) SGD, which may hinder the training and generalization performance of such algorithms since it is both empirically [Keskar et al., 2017, Kleinberg et al., 2018] and theoretically [Kale et al., 2021] observed that mini-batch SGD is superior to mega-batch SGD or GD in a number of machine learning tasks.
Dependence on a. The total sample complexity results derived by Fatkhullin et al. [2021]. Zhao et al. [2022] suffer from poor dependence on the contraction parameter a. Typically, EF methods are used with the TopK sparsifier, which only communicates K largest entries in magnitude. In this case, a= k/a, and the stochastic part of sample complexity scales quadratically with dimension.
No improvement with n. The stochastic term in the sample complexity of EF21-SGD does not improve when increasing the number of nodes. However, the opposite behavior is typically desired, and is present in several latest non-EF methods based on unbiased compressors, such as MARINA [Gorbunov et al., 2021] and DASHA [Tyurin and Richtárik, 2022]. We are not aware of any distributed algorithms utilizing the Top compressor achieving linear speedup in n in the stochastic term without relying on restrictive BG or BGS assumptions.
These observations motivate our work with the following central questions:
Can we design a batch-free distributed SGD method utilizing contractive communication compression (such as ')oK)) without relying on restrictive BG/BGS assumptions? Is it possible to improve over the current state-of-the- art O (a-tg-2 + and bounded variance assumptions?
- o2aa-2=
sample complexity under the standard smoothness
We answer both questions in the affirmative by incorporating momentum update into EF21-SGD.
2.3 Mysterious effectiveness of momentum in nonconvex optimization
An immensely popular modification of SGD (and its distributed variants) is the use of momentum. This technique, initially inspired by the developments in convex optimization [Polyak, 1964], is often applied in machine learning for stabilizing convergence and speeding up the training. In particular, momentum is an important part of an immensely popular and empirically successful line of adaptive methods for deep learning, including ADAM [Kingma and Ba, 2015] and a plethora of variants. The classical SGD method with Polyak (i.e., heavy ball) momentum (SGDM) reads:
++1 x² -70,
++1 (1 (1-n)) n) V ct+1),
where 7 >> 0 is learning rate and 17 > O is the momentum parameter.
We provide a concise walk through the key theoretical developments in the analysis of SGDM in stochastic nonconvex optimization in Appendix A; and only mention the most relevant works here. The most closely related works to ours are [Mishchenko et al., 2019], [Xie et al., 2020J, and [Fatkhullin et al.. 2021], which analyze momentum together with communication compression. The analysis in [Mishchenko al., 2019, Xie et al., 2020] requires BG/BGS assumption, and does not provide any theoretical improvement over the variants without momentum. Finally, the analysis of Fatkhullin et al. [2021] is only established for deterministic case, and it is unclear its extension to stochastic case can bring any convergence improvement over EF21-SGD. Recently, several other works attempt to explain the benefit of momentum [Plattner, 2022]; some consider structured nonconvex problems [Wang and Abernethy, 2021], and others focus on generalization [Jelassi and Li, 2022].

---

Method
Communication complexity
Asymptotic sample complexity
Batch-free?
No extra asumpption?
[Koloskova et ol., 2020)
EFT4-SGD
KG
X
[Huang et al., 2022]
NEOLITHIC
log (3)
00
ne4
2²
X
EF21-SGD
[Farkhullin et 2021]
BEER
14)
[2hao et 2022]
EF21-SGDM
Corollary 2
oe?
of stochastic gradicnts, i... E (a. 6.Il" G2 for all Rt. e0 This complexity achieved by using large mini batch communicating [K/a] coordinates per iteration, see Appendix e Analysis requires a bounded gradient disimilarity assumption, ie., Σi= (.)) f & GP for Rd
Analysis roquires bound of the second
Analysis requires a batch-size least B .,.7 for EF21-SGD and B
22 n
for BEER.
Table I: Summary of related works distributed emrrr compensated SGD methods using a TopK compressor under Assumptions 1 and 2. The goal find e-stationary point of smooth nonconvex function of the form (1), i.c., a point æ such that E [|| [z)]]] < E. "Communication complexity": the total # of communicated bits if the method is applied with sufficiently large batch-size; see Table 2 for batch-size. "Asymptotic sample complexity": the total # of samples required at each node to find an e-stationary point for batch-size B = in the regime O. "No extra assumptions": v'means that additional assumption is required.
Summary of contributions. Despite the vast amount of work trying explain the benefits of momentum, there is no work obtaining any theoretical improvement over vanilla SGD in the smooth nonconvex setting under the standard assumptions of smoothness and bounded variance.
First, we establish a negative result for simplifiedfidealized version of EF21-SGD, which shows that this algorithm does not converge with constant batch-size, and that mega-batch of order 2 is required. This provides a strong indication that EF21-SGD method inherently sensitive to stochastic gradients, which is also confirmed by our numerical simulations.
We propose simple fix for this problem by incorporating momentum step into EF21-SGD, which leads to our one-batch EF21-SGDM algorithm. By leveraging our new Lyapunov function construction and new analysis, we establish O (a --- + 1) sample complexity in the single node case.
o
We extend our algorithm to the distributed setting and derive an improved sample complexity result compared to other methods using the TopK compressor without resorting to the BG/BGS assumptions. In particular, EF21 #FD1- achieves asymptotically optimal O (a-n- sample complexity. Moreover, when EF21-SGDM is applied with large enough batch size, we prove that it reaches the optimal communication complexity O - see Tables & for more details.
Finally, propose double momentum variant of EF21-SGDM, and find that it further improves the sample complexity of EF21-SGDM the non-asymptotic regime.
We highlight that, interestingly, we prove that momentum helps: EF21-SGDM is theoretically better compared to non momentum variant large-batch EF21-SGD. We believe that our new technique can be extended in many ways, e.g., to dealing with other biased compressors and other (biased) com- munication saving techniques such as lazy aggregation of gradients, model compression, bidirectional compression, partial participation, decentralized training. adaptive compression; other important optimization techniques involving biased updates such as proximal SGD with momentum, gradient clipping and adaptive step-size schedules. We also hope that our proof techniques can be useful to establish linear speedup for other classes distributed methods, e.g, algorithms based on local training ProxSkip/Scaffnew [Mishchenko et al., 2022].
Additionally, extend our results to the class of absolute compressors in Appendix H and study the variance reduced variant of error feedback in Appendix I.
3 Main Results
Throughout the paper we work under the following standard assumptions.
Assumption (Smoothness and lower boundedness). We assume that I has L--Lipschitz gradient, i.e., [x) - v.(y))l < L || yll for all x, y R& and each fa has L Li-Liscchitz gradient,
5

---

ie., [V V S L, Ta||= Moreover, we assume that is lower bounded, Le., == inf f(x) > -00.
Ealx=-vll for all i [m], x. E RR.. We denote ==
E 1.2.
Assumption (Bounded variance (BV)). There exists a > such that
-
S
Vo E R2,
Ei [n],
(4)
where & ~ Di are ii.dd random samples for each i E [n].
3.1 A deeper dive into the issues EF21 has with stochastic gradients
As remarked before, the current analysis of EF21 in the stochastic setting requires each client to sample a mega-batch in each iteration, and it is not clear how to avoid this. In order to understand this phenomenon, we propose step back and examine an "idealized" version of EF21-SGD, which we call EF21-SGD-ideal, defined by the update rules (5a) + (5aa):
+1 x² 'g'
g' Σ of
(5a)
BF21-SGD-ideal
9: 1+1 = Vi((ttt))
+ C Vf +1 -542)- Vf((att)),
(5aa)
EF21-SGD: ++1
gf
+ C (V (1)))))))))))-
gi)
(5ab)
Compared to EF21-SGD, given by (5a) (5ab), we replace the previous state of by the exact gradient at the current iteration. Since EF21-SGD heavily relies on the approximation of A (x ) and according to the proof of convergence of EF21-SGD such discrepancy tends to change can only improve the method. While we admit this is a conceptual algorithm only (it does not lead to any communication sample complexity reduction in practice)", it serves well to illustrate the drawbacks of EF21-SGD. We now establish the following negative result for 1721-SGD-ideal.
co, this
Theorem Let L, 0, 0 < S 1/L and n 1. There exists a convex, L-smooth function R2 R. contractive compressor C(-) satisfying Definition 1, and unbiased stochastic gradient with bounded variance o² such that if the method EF21-SGD-ideal ((Sa) + (5aa)) is run with 0}, we have
step-size ", then for all T 2 0 and for all x {(0, x(2)))
E R2 222)) <
60 min f0² [+(>>)>>
E
Fix < E 4/v60 and x = T Additionally assume that n 2 1 and the variance of unbiased stochastic gradient is controlled by o²/B for some B 2 1. If B < 00gz. then we have E [|[[ for all T 0.
g²
The above theorem implies that the method (5a). (5aa), does not converge with small batch-size (e.g., equal one) for any fixed step-size choice." 9 Moreover, in distributed setting with nodes, a mini-batch of order B = Ω (a*)+²) is required for convergence. Notice that this batch-size is independent of n, which further implies that linear speedup in the number of nodes n cannot be achieved for this method. While we only prove these negative results for an "idealized" version of EF21-SGD rather than for the method itself, in Figures la and 4a, we empirically verify that EF21-SGD also suffers from a similar divergence on the same problem instance provided in the proof of Theorem Additionally, Figures lb and 4b illustrate that the situation does not improve for EF21-SGD when increasing
3.2 Momentum for avoiding mega-batches
Let us now focus on the single node setting" 10 and try to fix the divergence issue shown above. As we can learn from Theorem 1, the key reason for non-convergence of EF21-SGD is that even if the state vector g¹ sufficiently approximates the current gradient, i.e., g² (((++)) the design of
'This is because full gradients would need to be computed and communicated for its implementation. Notice also that if a 0, this method becomes the exact distributed gradient descent.
In fact, the example can easily extended to the case of polynomially decaying step-size. In this case, drop index everywhere and write of g'. ç E² for all 2 0.

---

this method cannot guarantee that the quantity lig' V)(>))| -/
small enough. Indeed, the last term above can be bounded by 2(2 -a)a² in expectation, but is not sufficient as formally illustrated in Theorem To fix this problem, we propose modify our "idealized" EF21-SGD-ideal method so that the compressed difference can be controlled and made arbitrarily small, which leads us to another (more advanced) conceptual algorithm.
+++1 V)(((tt) + nVV _ett) vf(x
4F21-SGDM-ideal
(6)
g g++1 - V/((*+)) + +C
v)(x(t)))
In this method, instead of using uz+ = vf(x**), ) as in EF21-SGD-ideal, we introduce a correction, which allows to control variance of the difference V - c(-1) (1((t)) This
allows us to derive the following convergence result. Let dn == -(x))
Proposition 1. Let Assumptions 1, 2 hold, and let C satisfy Definition Let go = and the step-size in method (5a), (6) be set as r S 1/2. Let t" be sampled uniformly at random from the iterates of the method. Then for any > 0 after T iterations, we have EE
260 T + A1j²0²
Notice that if 1 = 1, then algorithm EF21-SGDM-ideal (5a), (6) reduces to EF21-SGD-ided method (5a). (5aa), and this result shows that the lower bound for the batch-size established in Theorem is tight, i... B = (==*/=) is necessary and sufficient" for convergence. For 1j < 1, the above theorem suggests that using a small enough parameter v,, the variance term can be completely climinated. This observation motivates to design practical variant of this method. Similarly to the design of EF21 mechanism (from EF21- FF1--SGD-ideal, we propose to do this by replacing the exact gradients V Vf !) by state vectors vt and g' as follows:
0+1 = + n (VS(tt , (/-1))++1))) -'));
EF21-SGDM:
(7)
g + -0 9¹)
Theorem 2. Let Assumptions 1, hold, and let C satisfy Definition Let method (5a), (7) be run with gd = 00 = fz())). and at be sampled uniformly at random from the iterates of the method.
Then for all E (0, 1] with 7 S 70 -min
a 20
a TE
we have E
|| s(a2))
S 50(5 + no²²).
The choice 17 = min { 1, (L 1/2 7 To results in E [| |P]] - (.hr + (4 Vr)
Compared to Proposition 1, where 77 can be made arbitrarily small, Theorem 2 suggests that there is trade-off for the choice of v) E (0, 1] in algorithm (5a), (7). The above theorem implies that in single node setting EF21-SGDM has O L
Lo²) sample complexity. For a 1, this result matches with the sample complexity of SGD and is known to be unimprovable under Assumptions and 2 [Arjevani et al., 2019]. Moreover, when = 1, our sample complexity matches with previous analysis of momentum methods in [Liu et al., 2020] and [Defazio, 2021]. However, even in this single node (n 1), uncompressed (ar = 1) setting our analysis is different from the previous work, in partieular, our choice of momentum parameter and the Lyapunov function are different, see Appendix and J. For a 1, the above result matches with sample complexity of EF14-SGD (single node setting) [Stich and Karimireddy, 2019], which was recently shown to be optimal [Huang et al., 2022] for biased compressors satisfying Definition However, notice that the extension of the analysis by Stich and Karimireddy [2019] for EF14-SGD to distributed setting meets additional challenges and it is unclear whether is possible without imposing additional BG or BGS assumptions as in [Koloskova et al., 2020]. We revisit this analysis in Appendix K to showcase the difficulty of removing BG/BGS. In the following we will demonstrate the benefit of our EF21-SGDM method by extending it to distributed setting without imposing any additional assumptions.
3.3 Distributed stochastic error feedback with momentum
Now we are ready to present distributed variant of EF21-SGDM see Algorithm 1. Letting 5, = f(x')=ff - f", our convergence analysis of this method relies on the monotonicity of the following Lyapunov function:
A, == o, + - -
wf
2
Σ
ff((
+ Eot
{ -
(8)
"This follows by replacing o² in the batch free algorithm by /²/D p if the batch-size of size B > 1 is used.
7

---

Algorithm EF21-SGDM (Error Feedback 2021 Enhanced with Polyak Momentum)
1: Input: starting point _0, step-size O, momentum 7j E (0, 11, initial batch size Binit
2: Initialize of 9. Bm 2; Bui j=1 (z (i,)) for ......n; g Ei 9
3: for /. 0,1, ... T do
4: Master computes x x+1 xf 7g and broadcasts af+1 to all nodes
5: for all nodes 1, ,...,, parallel do
6:
Compute momentum estimator of (1 n)ef + vyV f( <t11
7: Compress e++ Cl +1 9t) and send et+1 to the master
8: Update local state g. 1 9 ++
9: end for
10: Master computes g = Di=1 o via g = g6 + ! Ei=
11: end for
Convergence of EF21-SGDM with contractive compressors. We obtain the following result: Theorem 3. Let Assumptions and 2 hold. Let aT be sampled uniformly at random from the T iterates of the method. Let EF21-SGDM (Algorithm be with contractive compressor. For all E (0, 1] and Binit 2 1, with S. min 201. 7T.
we have
| - 5
Ae
n" az
+
+
no²
(9)
77
where Ag given by (8). Choosing the batch size Bini and momentum 1j = min
o²
and stepsize 7 min
" 202 71.
}
Lho
{ 1.
Lóna? o
1/4
(L
1/a
Lópz
1/2
av Luo
we gel
E [|
0
Lδo
Lógg a2/3T
3/4
Lóng voT
2/3
+
L
1/2
of
nT
Remark 1. Note that using large initial batch size Buit 1 is not necessary for convergence of EF21-SGDM. If we set Bina = 1, the above theorem still holds by replacing ōg with No-
Remark the single node setting (n 1), the above result recovers the statement of Theorem 2 (with the same choice of parameters) since by Young's 's inequality (Lógg 8/4
(2//5T
Lon
Ligga 7-)
1/2 Lodue VaT
2/3
Lda
(LS,0")" 1/2 .add L L.
Recovering previous rates case of full gradients. Compared to the iteration complexity of EF14 [Koloskova et al., 2020], our result, summarized in
Lama G
089
Corollary 1. If = 0, then E V &
& ) []]
after =
iterations.
ac
better by order of magnitude, and does not require the BG assumption. The result of Corollary I the same as for EF21 method [Richtárik et al., 2021], and EF21-HB method [Fatkhullin et al., 2021]. Notice, however, that even in this deterministic setting (o 0) EF21-SGDM method is different from EF21 and EF21-HB: while the original EF21 does not use momentum, EF21-HB method incorporates momentum on the server side to update z', which is different from our Algorithm 1, where momentum applied by each node. This iteration complexity O o222 is optimal in both a and e. The matching lower bound was recently established by Huang et al. [2022] for smooth nonconvex optimization in the class of centralized, zero-respecting algorithms with contractive compressors.
Comparison to previous work. Our sample complexity in
Corollary 2. E [+>))))))
II] < after T = az?
Lo2/3 a2/3g575
La 12gs
+
La² net
iterations.
IIn Appendix J. show how to deal with time varying to and me-
13 Note that the initial batch size contributes to the sample complexity only an additive constant independent of e. Moreover, Bun 2 the following, we ignore the dependece Bun for fair comparison with other works.
Lóo < 2 since, otherwise. |v<(=>)| < 2L& o² and s is solution. In

---

strictly improves over the complexity Of Clan + Amnd") of EF14-SGD by Koloskova al. [2020], even in case when G < +oo. Notice that it always holds that o I G. If we assume that G x a, our three first terms in the complexity improve the first term from Koloskova al. [2020] by the factor of c/a, (rm/a)1/3 )1/3 a Compared to the BEER algorithm of Zhao et al. [2022], with sample complexity O Lum + Layg")) ), the result of Corollary 2 is strictly better in terms a, n, and oe
the smoothness constants." 14 In addition, we remove the large batch requirement for convergence compared [Fatkhullin et al., 2021, Zhao et al., 2022]. Moreover, notice that Corollary 2 implies that EF21-SGDM achieves asymptotically optimal sample complexity O Lo in the regime - ng
3.4 Further improvement using double momentum!
Unfortunately, in the -on-asyppooiic regime, sample complexity does not match with the lower bound in all problem parameters simultanuously due to the middle term a2/3g5/3 + Lga/s
Lo 2222 which can
Lo² potentially dominate over neT term for large enough n and e, and small enough a and a. We propose double-momentumm method, which can further improve the middle term in the sample complexity of EF21-SGDM. We replace the momentum estimator of in line 6 of Algorithm 1 by the following two-step momentum update
EF21-SGD2M: 1 ++ = (1 (1- n) + V J st+),,
u ++ 1+=1= (1 n)uf + tyu + (10)
We formally present this method in Algorithm 3 in Appendix G. Compared EF21- SGDM (Algo- rithm 1), the only change is that instead of compressing Dy g. in EF21-SGD2M, we compress uf - gf. where u, is two step (double) momentum estimator. The intuition behind this modification is that a double momentum estimator of has richer "memory" of the past gradients compared to v/. Notice that for each node, EF21-SGD22 requires save vectors (v), uf, gf) instead of 2 in EF21-SGDM (u/. g¹) and EF14-SGD (ef, o.). 15 When interacting with biased compression operator C()) such effect becomes crucial in improving the sample complexity. For EF21 SGD2M, we derive
Corollary 3. Let of in Algorithm I be replaced by ut given by (10) (Algorithm 3 in Appendix G). Then with appropriate choice of and n) (given in Theorem 5), we have [(")][ I after iterations.
T=
Ldg 05
L8a
L
13/5/5
4 Experiments
We
consider
a nonconvex logistic regression problem: [( =
m Dj=1 log log(exp(aJ xv,)) // exp(a.T=y) with nonconvex regularizer h(x1,...,
E Ek [T, + [z with X 10-3, where Ii...., Te E R², Hl is an indexing operation of a vector, e 2 2 is the number of classes, / is the number of features, m is the size of dataset, dij R' and Yij
(l....,c) c) features and labels. The datasets used are MNIST (with/ / = 784, m = 60 000, c = 10) and real-sim (with = 20 958, m = 72309, et al., 2010, Chang and Lin, 2011]. The dimension of the problem d (1+ 1)c, i.c., = 7500 for MNIST and d = 41 918 for real-sim. In each experiment, we show relations between the total number of transmitted coordinates and gradient/function values. The stochastic gradients in each algorithm are replaced by a mini-batch estimator 1/2 Σ Ei() with the same B 2 each plot. Notice that all methods (except for NEOLITHIC) calculate the same number of samples at each communication round, thus the dependence on the number of samples used will be qualitatively the same. In all algorithms, the step sizes are fine-tuned from a set (2 k 2-, 20 and the TopK compressor is used to compress information from the nodes to the master. For EF21-SGDM. we fix momentum parameter 7) 0.1 in all experiments. Prior to that, independent dataset w&a (with / = 300, m = 49 749, c = 2). We omit BEER method from the plots since it showed worse performance than EF21-SGD in all runs.
2) [LeCun
tuned 77 {0.01, 0.1} on the
Limax maX Li Notice that L < L < Lmxx and the inequalities are strict in heterogeneous setting. See Appendix K for details on EF14-SGD. contrast, EF21-SGD needs to save only one vector (gf). "orr NEOLITHIC, we use the parameter Rt [d/ K following the requirement in their Theorem 3. Experiments in Huang al. [2022] use heuristic choice R = 4, and thus can show faster convergence.

---

4.1 Experiment 1: increasing batch-size
In this experiment, we use MNIST dataset and fix the number of transmitted coordinates to = 10 (thus K/d = 10- and set 10. Figure 2 shows convergence plots for B E (1,32,128). EF21-SGDM and its double momentum version EF21-SGD2M have fast convergence and show a significant improvement when increasing batch-size compared to EF14-SGD. In contrast, EF21-SGD suffers from poor performance for small B, which confirms our observations in previous sections. NEOLITHIC has order times slower convergence rate due to the fact that it sends [d/x]] compressed vectors in each itcration, while other methods send only one.
127
ETLA-SR: SARD Iun 0,0025
CTU4660: ZAB KINC
OF C734-500 SHE AANCE 25
E72L-GEEMM 0.00355
C723-6G02N, 00025
B921 wite May S1IRIES
1921 NOOM Wes 19923
0921 NAOM
1e6
*biis
07
#itts
1e6
(a) B
(b) B 32
(c) B 128
Figure 2: Experiment on MNIST dataset with n = 10, and Top10 compressor.
4.2 Experiment 2: improving convergence with n
This experiment uses real-sim dataset, K = 100 (thus 2 K/2 = 2-10-3), and with B = 128 < m. We vary the number of nodes within n E {1, 10, 100), see Figure In this case, EF21-SGDM and EF21-SGD2M have much faster convergence compared to other methods for all n. Moreover, the proposed algorithms show significant improvement when n increases. We also observe that on this task, EF21-SGD2M performs slightly worse than EF21-SGDM for 10, 100. but it is still much faster than other other methods.
GFUA-GGD: SHOP 5'24-500: Seap KUN B.G.
GF34-000 2286
LF---00 SHE 120D
0F22-6004 Sup dis $1.0
EF2L-500 SHE JUN: LOBD
Sice
10-1
5/2L-SGOM
2020-000M $128
LF2L-G0M $120
#0t5/n
167
107
167
(a) n
(b) y 10
(c) n 100
Figure 3: Experiment on real-sim dataset with batch-size = 128, and Top100 compressor.
In Section C, present extra simulations with different parameters for above experiments. Addi- tionally, we inlclude experiemnts on simple quadratic problems and perform training of larger image recognition models. In all cases, EF21-SGDM and EF21-SGD2M outperform other algorithms.
Acknowledgments and Disclosure of Funding
This work of I. Fatkhullin was supported by ETH AI Center doctoral fellowship. The work of Richtárik and A. Tyurin was supported by the KAUST Baseline Research Scheme (KAUST BRF) and the KAUST Extreme Computing Research Center (KAUST ECRC); P. Richtárik was also supported by the (SDAIA-KAUSE AI).
Center of Excellence in Data Science and Artificial Intelligence
10

---

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 Process- ing Systems, pages 1709-1700 2017.
Dan Alistarh, Torsten Hoefler, Mikael Johansson, Sarit Khirirat, Nikola Konstantinov, and Cédric Renggli. The convergence of sparsified gradient methods. Advances Neural Information Processing Systems, 2018.
Yossi Arjevani, Yair Carmon, John C Duchi, Dylan J Foster, Nathan Srebro, and Blake Woodworth. Lower bounds for non-convex stochastic optimization. arXiv preprint arXiv:1912.02365. 2019.
Aleksandr Beznosikov, Samuel Horváth, Peter Richtárik, and Mher Safaryan. On biased compression for distributed learning. arXiv preprint arXiv:2002.
/24/0, /24/0002...41., 2020.
Chih-Chuna Chang and Chih-Jen Lin. LIBSVM: a library for support vector machines. ACM Transactions on Intelligent Systems and Technology (TIST), 2()): 2011.
Xin Chen, Niao He, Yifan Hu, and Zikun Ye. Efficient algorithms for minimizing compositions of convex functions and random functions and its applications in network revenue management. arXiv preprint 2tt.:22205017744 2022.
Ashok Cutkosky and Harsh Mehta. Momentum improves normalized SGD. In International Conference on Machine Learning, page 2260-2262222222 2660-2268. PMLR, 2020.
Ashok Cutkosky and Harsh Mchta. High-probability bounds for non-convex stochastic optimization with heavy tails. pages 4883-4895, 2021.
Ashok Cutkosky and Francesco Orahona. Momentum-based variance reduction in non-convex SGD. In Advances in Neural Information Processing Systems, 2019.
Aaron Defazio. Momentum via primal averaging: Theoretical insights and learning rate schedules for non-convex optimization. arXiv preprint 0xXix:2010000406, 2021.
Thinh Doan, Siva Maguluri, and Justin Romberg. Finite-time time analysis of distributed TD(0) with linear function approximation on multi-agent reinforcement learning. In International Conference on Machine Learning, pages 1626-1635. PMLR, 2019.
Ron Dorfman, Shay Vargaftik, Yaniv Ben-ltzhak, and Kfir Y. Levy. DcCoFL: Downlink compression for cross-device federated learning. arXiv preprint arXiv:2302.00543, 2023.
llyas Fatkhullin, Igor Sokolov, Eduard Gorbunov, Zhize Li, and Peter Richtárik. EF21 with bells & whistles: Practical algorithmic extensions of modern error feedback. arXiv preprint arXiv:2110.03294. 2021.
Juan Gao, Xin- Wei Liu, Yu-Hong Dai, Yakui Huang, and Junhua Gu. Distributed stochastic gradient tracking methods with momentum acceleration for non-convex optimization. Computational Optimization and Applications, 84(2):531-577 2023.
Euhanna Ghadimi, Hamid Reza Feyzmahdavian, and Mikael Johansson. Global convergence of the heavy-ball method for convex optimization. In 2015 European control conference (ECC), pages 310-315, IEEE, 2015.
Eduard Gorbunov, Dmitry Kovalev, Dmitry Makarenko, and Peter Richtárik. Linearly converging стrоr compensated SGD. In 34th Conference on Neural Information Processing Systems, 2020,
Eduard Gorbunov, Konstantin Burlachenko, Zhize Li, and Peter Richtárik. MARINA: Faster non- convex distributed learning with compression. In International Conference on Machine Learning, pages 3788-379099 PMLR, 2021.
Kaja Gruntkowska, Alexander Tyurin, and Peter Richtárik. Ef21-p -p and friends: Improved theoretical communication complexity for distributed optimization with bidirectional compression. arXiv preprint
Sep 2022.

---

Suyog Gupta, Ankur Agrawal, Kailash Gopalakrishnan, and Pritish Narayanan. Deep learning with limited numerical precision. In International Conference on Machine Learning, page 1737-1746, Feb 2015.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 770-778, 2016.
Samuel Horváth, Chen- Yu Ho, L'udovít Horváth, Atal Narayan Sahu, Marco Canini, and Peter Richtárik. Natural compression for distributed deep learning. arXiv preprint 2019a.
10988.
Samuel Horváth, Dmitry Kovalev, Konstantin Mishchenko, Sebastian Stich, and Peter Richtárik. Stochastic distributed learning with gradient quantization and variance reduction. arXiv preprint arXiv:/904.055 2019b.
Xinmeng Huang, Yiming Chen, Wotao Yin, and Kun Yuan. Lower bounds and nearly optimal algorithms in distributed learning with communication compression. In Advances in Neural Information Processing Systems, 2022.
Rustem Islamov, Xun Qian, Slavomír Hanzely, Mher Safaryan, and Peter Richtárik. Distributed newton-type methods with communication compression and bernoulli aggregation. arXiv preprint arXiv:2206.03588 2022.
Samy Jelassi and Yuanzhi Li. Towards understanding how momentum improves generalization in deep learning. In International Conference on Machine Learning, pages 9965-10040. PMLR, 2022.
Hao Jin, Yang Peng. Wenhao Yang, Shusen Wang. and Zhihua Zhang. Federated reinforcement learning with environment heterogeneity. In International Conference on Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pages 18-37. PMLR, 28-30 Mar 2022.
Peter et al Kairouz. Advances and open problems in federated learning. arXiv preprint 2019.
Satyen Kale, Ayush Sekhari, and Karthik Sridharan. Sgd: The role of implicit regularization, batch-size and multiple-epochs. arXiv preprint arXiv:2107.05074 2021.
Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian Stich, and Martin Jaggi. Error feedback fixes SignSGD and other gradient compression schemes. In International Conference on Machine
Learning, 2019.
Sai Praneeth Karimireddy, Martin Jaggi. Satyen Kale, Mehryar Mohri, Sashank J. Reddi, Sebastian U. Stich, and Ananda Theertha Suresh. Mime: Mimicking centralized stochastic algorithms in federated learning. arXiv preprint arXiv:2008.0366 2021.
Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Peter Tang. On latge-batch training for deep learning: Generalization gap and sharp minima. In International Conference on Learning Representations, 2017.
Sajad Khodadadian, Pranay Sharma, Gauri Joshi, and Siva Theja Maguluri. Federated reinforcement learning: Linear speedup under markovian sampling. In International Conference Machine Learning, page 10997-11055 11057. PMLR, Jun 2022.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In ICLR (Poster), 2015.
Bobby Kleinherg, Yuanzhi Li, and Yang Yuan. An alternative view: When does sgd escape local minima? In International Conference on Machine Learning, page 2698-22222 (707-2707. PMLR, 2018.
Anastasia Koloskova, Tao Lin, S. Stich, and Martin Jaggi. Decentralized deep learning with arbitrary communication compression. In International Conference Learning Representations, 2020.
12

---

Jakub Konečný, H. Brendan McMahan, Felix Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: strategies for improving communication efficiency. In NIPS Private Multi-Party Machine Learning Workshop. 2016.
Dmitry Kovalev, Anastasia Koloskova, Martin Jaggi, Peter Richtárik, and Sehastian Stich, A linearly convergent algorithm for decentralized optimization: Sending less bits for free! In The 24th International Conference Artificial Intelligence and Statistics (AISTATS 2021), 2021.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. Technical report, University of Toronto, Toronto, 2009.
Yann LeCun, Corinna Cortes, and CJ Burges. Mnist handwritten digit database. ATT Labs [Online]. Available: http://yann. http://yan..ecuu.comm http:/yannn..uu.cooooooo wwtpp/..co//ee///iiiiittooo 2, 2010.
Xiaoyu Li and Francesco Orabona. A high probability analysis of adaptive SGD with momentum.
arXiv preprini arXiv:2007. 14294, 2020.
Xiaoyu Li, Mingrui Liu, and Francesco Orabona. On the last iterate convergence of momentum methods. In International Conference on Algorithmic Learning Theory, pages 699-717. PMLR, 2022a.
Xiaoyun Li, Belhal Karimi, and Ping Li. On distributed adaptive optimization with gradient compres- sion. In International Conference on Learning Representations, 2022h.
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, pages 5895-5904. PMLR, 2020.
Zhize Li, Hongyan Bao, Xiangliang Zhang, and Peter Richtárik. PAGE: simple and optimal probabilistic gradient estimator for nonconvex optimization. In International Conference on Machine Learning, pages 6286-6295. PMLR, 2021.
Yujun Lin, Song Han, Huizi Mao, Yu Wang, and Bill Dally. Deep gradient compression: Reducing the communication bandwidth for distributed training. International Conference on Learning Representations, 2018
Yanli Liu, Yuan Gao, and Wotao Yin. An improved analysis of stochastic gradient descent with momentum. In Advances Neural Information Processing Systems, 2020.
Maksim Makarenko, Elnur Gasanov, Rustem Islamov, Abdurakhmon Sadiev, and Peter Richtarik. Adaptive compression for communictionn-fffiicntt distributed training. arXiv preprint arXiv:2211.00188 Oct 2022.
Konstantin Mishchenko, Eduard Gorbunov, Martin Takáč, and Peter Richtárik. Distributed learning with compressed gradient differences. arXiv preprint 1tt1::990100999 2019.
Konstantin Mishchenko, Grigory Malinovsky, Sebastian Stich, and Peter Richtarik. ProxSkip: Yes! Local gradient steps provably lead to communication acceleration! Finally! In International Conference on Machine Learning, pages 15750-15769, PMLR, 2022.
Aritra Mitra, George J. Pappas, and Hamed Hassani. Temporal difference learning with compressed updates: Error-feedback meets reinforcement learning. arXiv preprint arX1v:2301.00944, 2023.
Constantin Philippenko and Aymeric Dieuleveut. Bidirectional compression in heterogeneous settings for distributed or federated learning with partial participation: tight convergence guarantees. arXiv preprint arXiv:2006. 14591, 2020.
Maximilian Plattner. On SGD with momentum. Master's Thesis, 2022.
Boris T Polyak. Some methods of speeding up the convergence of iteration methods. Ussr computa- tional mathematics and mathematical physics, 4(5):1-17, 1964.
13

---

Xun Qian, Peter Richtárik, and Tong Zhang. Error compensated distributed SGD can be accelerated. arXiv preprint arXiv:2010.0009) 2020.
Peter Richtárik, Igor Sokolov, and Ilyas Fatkhullin. EF21: A new, simpler, theoretically better, and practically faster error feedback. In Advances in Neural Information Processing Systems, 2021.
Peter Richtárik, Igor Sokolov, llyas Fatkhullin, Elnur Gasanov, Zhize Li, and Eduard Gorbunov. 3PC: Three point compressors for communication cittuunccaaion-fffiiettt distributed training and a better theory for lazy aggregation. arXiv preprint arXiv: wtt::22220099999 2022.
Nicola Rieke, Jonny Hancox, Wenqi Li, Fausto Milletari, Holger R. Roth, Shadi Albarqouni, Spyridon Bakas, Mathicu N. Galtier, Bennett A. Landman, Klaus Maier-Hein Sébastien Ourselin, Micah Sheller, Ronald M. Summers, Andrew Trask, Daguang Xu, Maximilian Baust, and M. Jorge Cardoso. The future of digital health with federated learning. npj Digital Medicine, 3(11):1-7, 2020.
Mher Safaryan, Egor Shulgin, and Peter Richtárik. Uncertainty principle for communication compres- sion distributed and federated learning and the search for an optimal compressor. Information and Inference A Journal of the IMA, 2021.
Mher Safaryan, Rustem Islamov, Xun Qian, and Peter Richtárik. FedNL: Making Newton-type methods applicable federated learning. Internatiounl Conference on Muchine Learning, 2022.
Atal Sahu, Aritra Dutta, Ahmed M. Abdelmoniem, Trambak Banerjee, Marco Canini, and Panos Kalnis. Rethinking gradient sparsification as total error minimization. In Advances in Neural Information Processing Systems, page 9133-8146, 2021.
Amedeo Sapio, Marco Canini, Chen- Ho, Jacob Nelson, Panos Kalnis, Changhoon Kim, Arvind Krishnamurthy, and Masoud Moshref. Scaling distributed machine learning with in-network aggregation. In 18th USENIX Symposium on Networked Systems Design and Implementation, page 785-88888 808, 2021.
Othmane Sebbouh, Charles Dossal, and Aude Rondepierre. Nesterov's 's acceleration and Polyak's heavy ball method in continuous time: convergence rate analysis under geometric conditions and perturbations. arXiv preprint
2019.
Othmane Sebbouh, Robert M Gower, and Aaron Defazio. Almost sure convergence rates for stochastic gradient descent and stochastic heavy ball. In Conference on Learning Theory, pages 3935-3971. PMLR, 2021.
Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu. 1-bit stochastic gradient descent and its application data-parallel distributed training of speech DNNs. In Fifteenth Annual Conference of the International Speech Communication Association, 2014.
Navjot Singh, Deepesh Data, Jemin George, and Suhas Diggavi. Squarm-sgd: Communication- efficient momentum sgd for decentralized optimization. IEEE Journal Selected Areas in Information Theory, 2(3)) 969, 2021.
Sebastian Stich and Sai Praneeth Karimireddy. The error-feedback framework: Better rates for SGD with delayed gradients and compressed communication. arXiv preprint 1a0::099900550 2019.
Sebastian U. Stich and Sai Praneeth Karimireddy. The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Communication. arXiv preprint arXiv:1909.05350, 2021.
Sebastian U. Stich, J.-B. Cordonnier, and Martin Jaggi. Sparsified SGD with memory. In Advances in Neural Information Processing Systems, 2018.
Rafal Szlendak, Alexander Tyurin, and Peter Richtárik. Permutation compressors for provably faster distributed nonconvex optimization. arXiv preprint arXiv:2110.033000 2021.
14

---

Yuki Takezawa, Han Bao, Kenta Niwa, Ryoma Sato, and Makoto Yamada. Momentum tracking: Momentum acceleration for decentralized deep learning on heterogeneous data. arXiv preprint arXiv:2209.15505 2022.
Hanlin Tang, Xiangru Lian, Chen Yu, Tong Zhang, and Ji Liu. DoubleSqueeze: Parallel stochastic gradient descent with double-pass error-compensated compression. In International Conference on Machine Learning. 2020.
Alexander Tyurin and Peter Richtárik. Dasha: Distributed nonconvex optimization with commu- nication compression, optimal oracle complexity, and no client synchronization. arXiv preprint arXiv:2202.01268, 2022.
Thijs Vogels, Sai Pranceth Karimireddy, and Martin Jaggi. Powersgd: Practical low-rank gradient compression for distributed optimization. Advances in Neural Information Processing Systems, 2019.
Jun-Kun Wang and Jacob Abernethy. Quickly finding benign region via heavy ball momentum in non-convex optimization. arXiv preprint arXiv:2010.01449 2021.
Yujia Wang, Lu Lin, and Jinghui Chen. Communication-comprssss adaptive gradient method for distributed nonconvex optimization. In International Conference on Artificial Intelligence and Statistics, pages 6292-6320. PMLR, 2022.
Tiannan Xiao and Guoguo Yang. A convergence study of sgd-tgtt syd-type methods for stochastic optimization. arXiv preprint arXiv:2211.06197, 2022.
Cong Xie, Shuai Zheng, Oluwasanmi Koyejo, Indranil Gupta, Mu Li, and Haibin Lin. CSER: Communication-effiiceee SGD with error reset. In Advances in Neural Information Processing Systems, pages 12593-12603, 2020.
An Xu and Heng Huang. Detached error feedback for distributed sgd with random sparsification. In International Conference on Machine Learning, pages
PMLR, 2022.
Junchi Yang, Xiang Li, Ilyas Fatkhullin, and Niao He. Two sides of one coin: the limits of untuned SGD and the power of adaptive methods. In Advances Neural Information Processing Systems, 2023.
Tianbao Yang, Qihang Lin, and Zhe Li. Unified convergence analysis of stochastic momentum methods for convex and non-convex optimization. arXiv preprint arXiv:1604.033: 032557, 2016.
Chung-Yin Yiu Yau and Hoi-To Wai. DoCoM-SGT: Doubly compressed momentum-assisted stochastic gradient tracking algorithm for communication efficient decentralized learning. arXiv preprint 2Xiv:2202.00255. 2022.
Hao Yu, Rong Jin, and Sen Yang. On the linear speedup analysis of communication efficient momentum sgd for distributed non-convex optimization. In International Conference on Machine Learning, page 7184-7193, PMLR, 2019.
SK Zavriev and FV Kostyuk. Heavy-ball method in nonconvex optimization problems. Computational Mathematics and Modeling, 4(4):336-341, 1993.
Haoyu Zhao, Boyue Li, Zhize Li, Peter Richtárik, and Yuejie Chi. BEER: Fast O(1/T) rate for decentralized nonconvex optimization with communication compression. In Advances in Neural Information Processing Systems, 2022.
Shuai Zheng, Ziyue Huang, and James Kwok. Communication-effcceee distributed blockwise momentum SGD with error-feebbak.. In Advances in Neural Information Processing Systems, 2019.
15

---

Contents
1
Introduction
2
Communication Compression, Error Feedback, and Sample Complexity
2.1 Brief history of error-feedback
2.2 Key issue: error feedback has an unhealthy appetite for samples!
2.3
Mysterious effectiveness of momentum in nonconvex optimization
3
Main Results
3.1
A deeper dive into the issues EF21 has with stochastic gradients
6
3.2
Momentum for avoiding mega-batches... ....bbaicche....................
3.3 Distributed stochastic error feedback with momentum
3.4
Further improvement using double momentum!
4
Experiments
4.1 Experiment 1: increasing batch-size
10
4.2
Experiment 2: improving convergence with
10
More on Contractive Compressors, Error Feedback and Momentum
18
Variance Reduction Effect SGDM and Comparison STORM
21
C Additional Experiments and Details of Experimental Setup
22
C.1 Extra plots for experiments and
22
C.2 Experiment 3: stochastic quadratic optimization
22
C.3 Experiment 4: training neural network
24
D Descent Lemma
25
E EF21-SGDM-ideal (Proof of Theorem 1 and Proposition 1)
25
EF21-SGDM (Proof' of Theorems and 3)
28
F.1 Controlling the error of momentum estimator
30
F22 Controlling the error contractive compression and momentum estimator
Further Improvement Using Double Momentum (Proof of Corollary 3)
33
G.1
Controlling the error second momentum estimator
36
G.2 Controlling the error of contractive compression and double momentum estimator
38
H EF21-SGDM with Absolute Compressor
40
H.1 Controlling the error of absolute compression
42
I EF2L-STORMMMR
43
16

---

L11 Controlling the variance of STORM/MVR estimator
46
1.2 Controlling the variance of contractive compression and STORM/MVR estimator
47
J Simplified Proof of SGDM: Time Varying Parameters and No Tuning for Momentum Sequence
49
K Revisiting EF14-SGD Analysis under BG and BGS Assumptions
51
17

---

Asymp. sample compl.
Comm. compl.
Batch-size for comm. compl.
Batch free?
No extra assump.?
Method
EF14-SGD [Koloskova et al., 2020]
KGLu ac
ao (*) REQ
Lmsa net
v
x
NEOLITHIC
Loy log (
2² ne²
log ())
L 2 net
X
X
[Huang et al., 2022]
a
EF21-SGD [Fatkhullin ct al., 2021]
KT. ae?
Lg2 (d) a²gg
x
BEER [Zhao ct al., 2022]
Klaya
? ac?
Lugaa a²
x
V
EF21-SGDM
Kī
a. o2
V
a. o²
Lea
Corollary
ac2
ne²
L2
22
net
EF21-SGD2M
2L. 01 23
Laa
Corollary 3
ag2
L
Analysis requires a bound of the second moment of the stochastic gradients, i..., E V ft(,, &.II" S G² for all x E R².
This complexity is achieved by using a large mini-barch and commanicating [K/a] R d coordinates per iteration.
Analysis requires a bounded gradient disimilarity assumption, ie., a Ei= [r(x)) - [f())]? & G for z é Rt.
Analysis requires a batch-size al leust B 2 -,5Z for EF21-SGD and 2 or? for BEER.
For fair comparisen, take the (minniml)) batch-size for these methods which guaraniees the reported communication complexity. Table Extended summary related works on distributed error compensated SGD methods using a Top compressor under Assumptions and 2. The goal is to find an e-stationary point of a smooth nonconvex function of the form (I), i.e. point such that E [[]][())]] [I] < e. "Comm. compl." reports the total number of communicated bits if the method is applied with batch-size equal "Batch-size" at each node. When Top compressor is applied, then 2 K/ and the comm. compl. of error compensated methods can be reduced by a factor of ad/ K. "Batch-size for comm. compl." means the batch-size for achicving the reported "Comm. compl.". " "Asymp. sample compl." reports the asymptotic sample complexity of the algorithm with batch-size B = in the regime
O, i.c., the total number of samples required at each node to achieve e-stationary point. "Batch free" marks with v if the analysis ensures convergence with batch-size equal to 1. "No extra assump." marks with / no additional assumption beyond Assumptions and is required for analysis. We denote Lmn ma] L4 Notice that it always holds L S L S Lem and these inequalities only become equalities in the homogeneous case. It could be that T.. T. < making the batch-size of EF21-SGDD and EF21-SGD2M much smaller than those of EF21-SGD and BEER. Symbol denotes the maximum of two scalars.
A More on Contractive Compressors, Error Feedback and Momentum
Greedy vs uniform. In our work, we specifically focus on the class of contractive compressors satisfying Definition I, which contains a greedy TopK compressor as a special case. Note that TopK is greedy in that it minimizes the error (x) x1|² subject to the sparsity constraint [[((z)llo I K, where ||ullo counts the number of nonzero entries in u. In practice, greediness is almost always!7 17 very useful, translating into excellent empirical performance, especially when compared to the performance of the RandK sparsifier. On the other hand, it appears to be very hard to formalize these practical gains theoretically In fact, while greedy compressors such as TopK outperform their randomized cousins such as RandK in practice, and often by huge margins [Lin al., 2018], the theoretical picture is exactly reversed, and the theoretical communication complexity of gradient-type methods based on randomized compressors [Alistarh et al., 2017, Mishchenko et al., 2019, Horváth et al., 2019b, Li et al., 2020, Gorbunov et al., 2021] is much better than of those based on greedy compressors [Koloskova et al., 2020, Richtárik et al., 2021, Fatkhullin et al., 2021, Richtárik al., 2022]. The key reason behind this is the fact that popular randomized compressors such RandK become unbiased mappings after appropriate scaling (e.g.. g.. E[ K RRadd(()))) (x)] = xt), and that the inherent randomness is typically drawn independently by all clients. This leads to several key simplifications in the analysis, and consequently, to theoretical gains over methods that do not compress, and over methods that compress greedily. Further improvements are possible when the randomness is correlated in appropriate way [Szlendak et al., 2021].
Due to the superior empirical properties of greedy contractive compressors, and our desire to push this very potent line of work further, in this paper work with the general class of compressors
"Grredinesss is not useful, for example, when D, D, for all i.j and when Topk applied the full-batch gradient f (a) by each client, However, situations of this type arise rarely in practice. No theoretical results of this type exist for n 1.
18

---

satisfying Definition 1, and do not invoke any additional restrictive assumptions. For example, we do not assume C can be made unbiased after scaling.
Error Feedback. The first theoretical analysis of EF14 was presented in the works of Stich et al. [2018], Alistarh et al. [2018] and further revisited in convex case in [Karimireddy et al., 2019, Beznosikov et al., 2020, Gorbunov et al., 2020, Qian al.. 2020] and analysis was extended to nonconvex setting in [Stich and Karimireddy, 2019]. Later, in nonconvex case, various extensions and combinations of EF14 with other optimization techniques were considered and analyzed, which include bidirectional compression [Tang et al., 2020], decentralized training [Koloskova et al., 2020, Singh et al., 2021], server level momentum [Xie et al., 2020], client level momentum [Zheng et al., 2019], combination with adaptive methods [Li et al., 2022b]. To our knowledge, the best sample complexity for finding a stationary point for this method (including its momentum and adaptive variants) in the distributed nonconvex setting is given by Koloskova et al. [2020], which is More recently, Huang al. [2022] propose a modification of EF14 method achieving ng
o²
log( ( ne*
sample complexity by using the BGS assumption. When applied with Top
compressor, this method requires to communicate Ô (K/a) coordinates at every iteration. This makes it impractical since when the effective a is unknown and is set to a = K/ / it means that their method communicates all d coordinates at every iteration, mimicking vanilla (S)GD method. Moreover, their algorithm uses an additional subroutine and applies updates with a large batch-size of samples of order O L log ())). making the algorithm less practical and difficult to implement. It is worth to mention, that error feedback was also analyzed for other classes of compressors such as absolute (see
Definition 2) additive compressors (i.e., C(x y) C(x) + Cly) for all x; y IRd)) [TTang et al., 2020, Xu and Huang, 2022], which do not include Top sparsifier.
Momentum. The first convergence analysis of gradient descent with momentum was proposed by B.T. Polyak in his seminal work [Polyak, 1964] studying the benefit of multi-step methods. The proof technique proposed in this work based on the analysis of the spectral norm of a certain matrix arising from the dynamics of a multi-step process on a quadratic function.. Unfortunately, such technique restricted the case of strongly convex quadratic objective and the setting of full gradients. Later Zavriev and Kostyuk [1993] prove an asymptotic convergence of this method in nonconvex deterministic case without specifying the rate of convergence.
To our knowledge, the first non-asymptotic analysis of SGDM in the smooth nonconvex setting is due to Yu et al. [2019]. Their analysis, however, heavily relies on BG assumption. Later, Liu et al. [2020] provide a refined analysis of SGDM, removing the BG assumption and improving the dependence on the momentum parameter 17. Notice that the analysis of Liu et al. [2020] and the majority of other works relies on some variant of the following Lyapunov function:
A, = f(=) -(
Cr |
(11)
T=0
where {2") Tr20 is some auxiliary sequence (often) different from the iterates {a" Jr and {cr 3 is diminishing non-negative sequence. This approach is motivated by the dynamical system point of view at Polyak's 's heavy ball momentum, where the two terms in (11) are interpreted as the potential and kinetic energy of the system [Sebbouh al., 2019]. In contrast, the Lyapunov function used in this work is conceptually different even in the single node (n = 1), uncompressed (a 1) setting. Later, Defazio [2021] revisit the analysis in [Liu al., 2020] through the lens of primal averaging and provide insights on why momentum helps in practice. The momentum is also used for stabilizing adaptive algorithms such as normalized SGD [Cutkosky and Mehta, 2020]. In particular, it was shown that by using momentum, one can ensure convergence without large batches for normalized SGD (while keeping the same sample complexity as a large batch normalized SGD). However, their analysis is specific to the normalized method, which allows using the function value as a Lyapunov function. High probability analysis of momentum methods was investigated in [Cutkosky and Mehta, 2021, Li and Orabona, 2020]. In the distributed setting, [Yu et al.. 2019, Karimireddy et al., 2021] extend the analysis of SGDM under BGS assumption. Later [Takezawa et al., 2022, Gao et al., 2023] remove this assumption providing refined analysis based on the techniques developed in [Liu et al., 2020). However, the algorithms in these works do not apply any bandwidth reduction technique such as communication compression.
19

---

We would like to mention that understanding the behavior of SGDM in convex case also remains active area of research [Ghadimi et al., 2015, Yang et al., 2016, Sehbouh et al., 2021, Li et al., 2022a, Xiao and Yang, 2022].
20

---

B Variance Reduction Effect of SGDM and Comparison to STORM
Notice that the choice of our Lyapunov function A, (8), which is used in the analysis of EF21-SGDM implies that the gradient estimators of and vi improve over the iterations, i.e.,
df fz('),
of V
for t + oc.
This comes in contrast with the behavior of SGD, for which the gradient estimator of fi < does not necessarily tend to zero over iterations. Such effect of asymptotic improvement of the estimation error of the gradient estimator is reminiscent to the analogous effect known in the literature on variance reduction (VR) methods. In particular, the classical momentum step 6 of Algorithm may be contrasted with STORM variance reduced estimator proposed by Cutkosky and Orabona [2019], which updates the gradient estimator via
u ++1 Vf(xx't
- + (1 - () - Vf (f((,s)))))) ()) = = VV-
(12)
known that the class of VR methods (and STORM, in particular) can show faster asymptotic convergence in terms of T (or compared SGD and SGDM under some additional assump- tions. However, we would like to point out the important differences (and limitations) of (12) compared the classical Polyak's momentum used on line 6 of Algorithm 1. First, the estimator wi+] is different from the momentum update rule of+1 in that it is unbiased for any / 2 0, i.e., 0 which greatly facilitates the analysis of this method. Notice that, in particular, in the deterministic case (a = 0, a = 1), the method with estimator (12) reduces to vanilla gradient descent with w +1 (x+ Second, the computation of w + requires access to two stochastic gradients [I((,*+1, + and Vai("', ( under the same realization of noise St at each iteration, and requires the additional storage of control variate x². This a serious limitation, which can make the method impractical such as federated RL [Mitra et al., 2023], multi-agent RL [Doan et al., 2019] or operations research problems [Chen et al., 2022]. Third, the analysis of variance reduced methods such STORM requires an additional assumptions such as individual smoothness of stochastic functions (or its averaged variants) (Assumption 3), i.e., | (v,,)) Vi EI & || yl for all z.y E Rd & ~ D;, i E [n]), while our 2F21-GGDM only needs smoothness of (deterministic) local functions f((x). While this assumption is satisfied for some loss functions in supervised learning, it also be very limiting. Even if Assumption satisfied, the constant & (which always satisfies ? 2 T.) can be much larger than canceling the speed-up in terms of T (or E). For completeness, we provide the sample complexity analysis of error compensated method combined with estimator (12), which is deferred to Appendix I.
E [w V (ix*tt))
not implementable for certain applications
Notice that E [w] - v[([=))] Let E [ vf((=()] hold, then
[w]tt V.f((z*))) = (1 - 7) [uf (xf o!+)) = 0.
21

---

ISD EF21-SCD
EF21-SGOM
Osjectiv 5
2.5
EF21:500 (n- 50)
1.0
EF21 5F20:300 (n- 5000
EF21 10000)
2000
4000
6,000
8000 10000
2000
4000
6000
1000
10000
Iteration,
Iteration,
(a) Divergence in single node setting,
(b) No improvement with
Figure 4: Divergence of EF21-SGD on a quadratic function ||=|| with Top1 compressor. See the proof of Therem 1 for details the construction of noise &, for all methods is x² = (0, 0.01) Unlike Figure I, these experiments use time varying step-sizes and momentum parameters "/ T vt-1"
1, B 1. The starting point
0.1 Each method is run 10 times and the plot shows the
median performance alongside the 25% and 75% quantiles.
C Additional Experiments and Details of Experimental Setup
Divergence of EF21-SGD with time-varying step-sizes. We complement Figure in the main part of the paper, which shows divergence of EF21-SGD [Fatkhullin et al., 2021] with small (constant) step-size. Here, Figure 4, we see that the similar divergence is observed when using time varying step-sizes "/- = 0.1 V Also, EF21-SGD with time-varying step-size does not improve convergence when n is increased.
Implementation Details. The experiments were implemented in Python 3.7.9. The distributed environment was emulated machines with Intel(R) Xeon(R) Gold 6248 CPU @ 2.50GHz. In all experiments with MNIST, we split the dataset across nodes by labels to simulate the heterogencous setting.
C.1 Extra plots for experiments and 2
In Figures 5 and we provide extra experiments for the setup from Section 4.
EPSA-SCD:5EE DC 0.5 SADM 0.20125
D'L4SGD Suppake 1.0 Sarind
EF34-CD: Supp soc SODM
10- W
ebis//n
1ec
#bit /n
160
#bits:m
18
(a) B
(b) B
B 128
Figure 5: Performance of algorithms on MNIST dataset with 100, and Top10 compressor,
C.2 Experiment 3: stochastic quadratic optimization
We now consider synthetic X strongly convex quadratic function problem f(x) fi)x
where the functions fi(x) _ Q x TTb, are (not necessarily convex) quadratic functions for all [rx] and E Rdd The matrices Q Q.. vectors b,, .... bn, and a starting point 100, dimension d = 1000,
r are generated by Algorithm 2 with the number of nodes For all E [n] and x E Rd we consider stochastic gradients f( V fx) + &,, where & are iid. samples from (N0 a)) with {0.001, 0.01]. In
regularizer 0.01, and scale
22

---

2121
6723 SoEM srop ste 100-
101
#bts/nn
#b m
#bits n
n
(b) 10
(c) 100
Figure 6: Performance of algorithms real-sim dataset with batch-size B 1, and Top100 compressor.
Figure 7, we present the comparison of EF21- FFD1 and EF14-SGD with three different step sizes. The behavior of methods for other step sizes from the set (2* l E [-20, 20) follows a similar trend. For every step size, we observe that at the beginning, the methods have almost the same linear rates, but then EF14-SGD gets stuck at high accuracies, while EF21-SGDM continues converging to the lower accuracies.
10
10
EF14-5GD Step stre: 0.0625
EF1 4-5GD: Step size: 0.0625
BFL4-5GD: Step size: 0.125
EFL4-5GD: Step size: 0.125
EFL4-5D:: Siep
10
EFL4-50D:
10-1
BF23-SGDM: Step size: 0.0625
BF2]-SGDM: Step size: 0.0625
FP2 FPG.M. Step size 0.125
EP2 F-500D Step size ni125
EFg SCDN Step 025
10
EF27 SGB-: Step
10-
10-2
100000
10
#bits / n
# bits n
Figure 7: Stochastic Quadratic Optimization Problem with 0.001 (left figure) and a 0.01 (right figure)
Algorithm 2 Quadratic Optimization Task Generation Procedure
1: Parameters: number nodes n, dimension d, regularizer X, and scale s.
2: for = I,...,n do
3: Calculate Guassian noises μ 1 sEt and μ sEh iid. E, 100,
4: b, (-1 ni O.... 0) E _d
5: Scale the predefined tridiagonal matrix
2
-1
0
-1
gdxd
4
-1
2
6:
end for
7: Find the mean of matrices Q - >n x-= Q
8: Find the minimum eigenvalue Amin ( Q))
9: for i I,..,, do
10: Normalize matrix Q Q. + Amiu (Q))I
11: end for
12: Find a starting point d0 (Vd.0, 0........... ... .)
13: Output new problem: matrices Q1, Qn: vectors by ... by. starting point 0
procedure to generate stochastic quadratic optimization problems. In this section, we present an algorithm that generates quadratic optimization tasks. The formal description is provided in Algorithm 2. The idea is take a predefined tridiagonal matrix and add noises to simulate the heterogeneous setting, Algorithm 2 returns matrices Qı. Qn. vectors bi. b,, and starting
23

---

Vanila 5GD (ne compression:: Step size: 0.05
+ Vanila 5GD (ho compressieni: Step size: 0.05
SCDM:
SCDM: Stop 0:05
560: Step
EF14-50p: Step size: 0.05
EF14.SCD: Stap size: 0.05
(a) B
(b)
Figure ResNet- 18 on CIFARIO dataset with n
Algorithm
Test Accuracy
SGD
81.5 %
EF21-SGD
82.5 %
EF14-SGD
83.1 %
EF21-SGDM
83.3 %
Figure 9: Accuracy on the CIFARIO test split.
point z such that the matrix Q Н Q has the minimum eigenvalue Amin (Q) = X, where A is parameter. Next, define the functions fa and stochastic gradients in the following way:
f((x) = 2
-02 x T be
and
Vf((x,)) Vf((2)) Es
for all x E Rd and E [n]. The noises & are i.idd samples from (0, where a is parameter,
C.3 Experiment 4: training neural network
We test algorithms
image recognition task, CIFARIO [Krizhevsky al., 2009], with the ResNet- 18 [He et al., 2016] deep neural network (the number of parameters ze 10?). We split CIFARIO among 5 nodes, and take K 2 106 in TopK.. In all methods finetune the step sizes. One see that our findings the low-scale experiments translate into large-scale experiments in Figure With different batch sizes, EF21-SGD converges slower than EF21-SGDM and EF14-SGD, and new method EF21-SGDM improves over EF14-SGD in Figure 8b. We checked the accuracies on the test dataset (see Table 9) and observed the same relations between algorithms (note that accuracies are far from the real SOTA because we turned off all augmentations and regularizations in training).
24

---

D Descent Lemma
Let us state the following lemma that is used in the analysis of nonconvex optimization methods.
Lemma 1 ([Li al., 2021D. Let the function f()) be L-smooth and let x x² -rgg for some vector 9¹ E Bd and a step-size O. Then we have
f(xlt1) S f(x') 2 2 ||
L (2) 27 2
| - x² +212+
+ 11 - (13)
E EF21-SGDM-ideal (Proof of Theorem 1 and Proposition 1)
We now state slighly more general result than Theorem 1, which holds for EF21-SGDM-idel method with any v E (0, The statement of Theorem follows by setting 7 1, since in that case EF21-SGDM-idea coincides with EF21-SGD-ideal (5a), (5aa). Recall that EF21-SGDM-iden (distributed variant) has the following update rule:
x 1+ = x 79';
g¹ =
gi
(14)
==1
8 ++1 Vf((ztt1) VV 15 _ vf((ttt)),
EF21-SGDM-ideal:
(15)
9, ++ Vf((=tt) (c, - -Vf((x++)))
L,L, n S and 1. There exists convex, L-smooth function f(), a contractive compressor C(.) satisfying Definition 1, and an unbiased stochastic
Theorem 4. Let 0,0
<
gradient with bounded variance o² such that the method (14), (15) run with step-size 7, then for all T 2 0 and all x E ((0,)))) E R2 120 < <0}, we have
E [[Ivf(=>11'
min ((
60
Fix < L/V60 and 20 (o, To. Additionally assume that 2 and the variance of
unbiased stochastic gradient is controlled by o some B 2 1. Bf < x²0² then we have E [ for all T 2 0.
002
Proof of Theorem I. Part Consider fxx 1 |>||
RR.. For each iteration 0, let the random vector g++1 be sampled uniformly at random from the set of vectors:
2 20
302
(i) V 10
30
(=1
2
30
=
10
10
Define the stochastic gradient as Vf(x', = Vf(x*) + 5 = Lx + +
Notice that
E [V = (s('), and [V - |/(29)1 = 0²_
The update rule of method
(14), (15) with such estimator
7g' = x' - Lyx' - -c (n'*).
where we choose C(-) as Topl compressor. Notice that E [g'] (0, 0)
but
302
E [[((E))] =
(0, 1/3) T * T.
10
By setting the initial iterate to x0 (0, x0, T for any z
0, derive
300
= -11 -1 1
7
(1 -7)²
10
1=0
= -11
+
17
(1 (1- (1-Im) 1-I))))+
(0)
(16)
L
30
-1
25

---

for any 0 S Y 1/L, and any =(2; < 0. The inequality in (16) is because the first vector has strictly negative component <(2)- and the second vector has non-positive second component when ? >> 0 and x² > 0. Therefore, since |V](()]] = Lx|l" we have
E [V]({")]
= E Ia 2 |1]]
= B LL [La"]]" + LL - -E [[<
B [Laa [
2
18
(1 (1-1a)² | + 17
02
(1 ((1)))
30
IV3
(1 1y) [f((>)]1 n²00
(1 (1 11)
30
V (z)) 1 11"02
IV
30 Vf 12 + 17202
for all T 2 1, where in (i) we used the form of vector E x
T in (16), in (it) we drop a non-
negative cross term, and use Vf(x") = Lx The last inequality follows by lower bounding a univariate quadratic function with respect to (1 I>)" for 0 S = S 1, where optimal choice is
= 1/"0²/ (30 V |1 + +))o)). It is left to note that my 2 min y} for all x, y > 0.
rty
Part II. Fix n 2 1 and B 2 1. Let at each node i = 1...., the random vectors ş be sampled independently and uniformly form the set of vectors:
30
30
-2 30
0
10B'
22
V
10B'
23
-1) V
10B"
Define random matrix é (fi...., of the method (14), (15) on the same function instance will take the form
( Then E
|IV 5*) ( vf(zt))
o/ The update
1 Σ ((
x 141 x²
91 x¹ Lyx
Notice that in this case, we still have
302
c(n
Σ
[(( = =n 10 (0, 1/3) * (0,0)
n
which is independent (!) of n. Therefore, by similar derivations, we can conclude that
E [|V
1
1"a02
|| > 2
min
60
n?o² 60c2 S L/v60, and T0 (0, T.
where we that B
Proof of Proposition I. By smoothness (Assumption 1) f(-) it follows from Lemma that for
S I/L we have
|[ { 7
llo 2
(17)
Now it remains to control the last term, which due to the error introduced by a contractive compressor and stochastic gradients. We have
E [|oo
E
[||c (u' ( v((E)) (1) " (
2E (1 - - -
26

---

+21 E (-) {l(
S 2(2 - a)
VVs('', [
S 4nfo²
where (1) and (it) use the update rule (6). (ièi) holds by Young's inequality, and the last two steps hold by Definition and Assumption 2.
Subtracting f" from both sides of (17), taking expectation and defining ò. == [f(((=)) -"'). derive
E
[1]
200 [I
41f²
77
27

---

F EF21-SGDM (Proof of Theorems 2 and 3)
The statement of Theorem 2 follows directly from Theorem 3 and Remark 2. Let us prove Theorem 3.
Proof of Theorem 3. In order to control the error between g' and Vf(x'), we decompose it into two terms
l1o' - V)())( s 22|1g' - o' 2 2
v/('")|| S 2 11 ut + 2 -V
and develop recursion for each term above separately.
Part I (a). Controlling the error of momentum estimator for each uy. Recall that by Lemma 2-(24),
we have for each =1...., nI, and any 0 < 1 S 1 and f. 2
E || -
(i( [|] < (1 1) [I - v fi ||
+ 3 EE' ||0 - =²|l²]] + +1²02. (18)
Averaging inequalities (18) over i = l...., n and denoting P. == a Em= E [[lut -Vf((*))1
R₁ = E || x
[1] we have
31.
P (1 (1 (1-11) (1 +
R4 + 17²0²
Summing up the above inequality for O,..., T 1, we derive
J 4 T
T-1
3 1/2
Σ Rs
2 + Po + no
1
(19)
T/
1=0
1=0
Part I (b). Controlling the error of momentum estimator for of (on average). Similarly by Lemma 2-(25), we have for any 0 < n 1 and t 2 0
3L ( S (1- T) [10'' -/('') + E -
|10t) + 1/02
E
"
where vi
1 Σi= of is an auxiliary sequence.
Summing up the above inequality for f .,..., T 1, and denoting P. = E we derive
v {(
T-1 Σ
3L
T T-1 R +
no²
P.S
Po.
(20)
T I=U
1
T
nT
1=
Part II. Controlling the error of contractive compressor and momentum estimator. By Lemma we have for each = I,.... n, and any 0 < 1 < 1 and / 2 0
E 1 - 1/t111]] < (1
11 =1|[]]
4n²
E -
)
a
4L3n2 E |||0t1 - x 20113]
+ +17202
(21)
a
Averaging inequalities (21) over i = 1.... n, denoting V. == 1 Σn E [1oo mp|p]] and summing up the resulting inequality for t = 0,...,T T - 1, we obtain
ΣΣ v
<
8n1² 1
T
P: +
SLan T-1
Rs +
2n"²02
+ aT
Vo.
(22)
a
T
a²
T
t=0
1=0
28

---

Part III. Combining steps I and II with descent lemma. By smoothness (Assumption of f()) it
follows from Lemma that for any 7 S 1/(2L) we have
f(alt)) 1 f(xt) - 2 |/
1
10tt1
x²
112 + 2 2
19'- ff((==
(23)
2
47
S ((xt) 2 |
1
|
x² 112 , - Σ lla1 - 12 + +7 1 \/(a")/?
4n
Subtracting f from both sides of (23), taking expectation and defining 5, == Ef((=') ff we derive
+ Σ E
260
T-1
T-1
+ T
Σ
1/2 + 2
Σ
P
Σ
R
7T 1=0
T
24 T
1=0
t=0
280
16n² 1 T-1
1 T-1
4n/0²²
Pr +
Σ
P
7/
a² T
1=0
1=0
16-21'n2
T-1 Σ
R
7/2
T
(1)
26
16n 0²
41/²0 0²
2no 2
4
+
Vi
7T
a²
aT
16- 16-2
L 2
2
T-1
a
"1"
a²
Rg
+
2
Po
Q2T Po
16m
72
T
1/T
(181)
250
161802
41j00 0²
2nj02 2
6- 2
64-2I 0²
T-1 Σ t=
9²
Re
>T
a²
a
n
T
16
4
+
Po
+
Po
+
Vo
n/
2T
aT
26
161302
4nj² 0²
2np² 2
16n
4
+
+
+
Po
+
P.
+
Vo.
YT
a²
a
n
nT
2T
aT
where (1) holds due to (22), (ii) utilizes (0 and (mi) follows by S 1, and the last step holds due to the assumption the step-size. We proved (9).
We now find the particular values of parameters. Since 9, us for all i [n]. we have Vo 0. Using <Bn) for all i 1........ n. we have
of Bun
Σ Bus
fx
1=1
2
σ²
Po E 11000
V vf(a
and Po E
1o - vf(
<
BB
Binit
i=1
We can substitute the choice of y and obtain
(
T.50 aT
Lδo
17022
1700
n
2
no² a² BuiiT
E
= o
+
+
+
n/
a
a
mm Buin? T
Since Binit 2 Lown
we have
[[V = o
Lóo
Lgp
17
2
0202
110
1/a2 a Bini T
E
+
oT
rTT
a
a
Notice that the choice of the momentum parameter such that
<
Ldna² r
1/4
1) <
Ldaa
1/3
7 5 ( Ldnn 1/2 [TT
and 1 < Bao ensures that
Lóg
Ldg
no
Ldg
and
1/1
7/7
29

---

11aa 0- Bin
Ldo. 19
Therefore, have
Lòu
[ a2/3T
8/4
Lógor Va'T
3/8
Lóg0z nT
1/2
ov Lóu av Bini T
E
o
+
aT
Using Bint 2 min
LZL 1.280
02/3
n
we obtain
an T.
(1/314/3(660)
T
L
[.doo2/3)
9/4
Tddoa VaT
2/8
+(1
(Tngo2 1/2
E
[|
S o
aT 02/3T
+
+
nT
remains to notice that [max {
min
oZL L
2/3
x² Loori
a²
LouT a (16))7)
T
Lō
F.1 Controlling the error of momentum estimator
Lemma 2. Let Assumption I be satisfied, and suppose O < S 1. For every i = .,...,n, n, let the sequence {v()e2o be updated via
1 = 0i of- + 7j (V.f((z' - "
Define the sequence o² = 1/2 Ei= n/. Then for every i = -...., n and 2 0 it holds
3L3 E
E ||0t V[((+'))1 < (1- || - Va(("" ">]]
|1 - x² 1
n2003 (24)
(|oo-~((((t)) (1 1) 111-11 +
3L
E
|| - x0- 113
+ 1²0²
(25)
17
Proof. By the update rule of of, we have
||0t - V[(()))) = E
of - 111
+ n
= E Ees [1 - - V
v.(((()))
v(((="))| [|]]
= (1 2 ||05- V/((0') >| + . Viiaa' (0) V/((+)))
S (1 ?)
(1+ " E 10 (
(1+ 2
/ E
||V Vf(('') /|? 21
+ 11202
s (1 n)E || Vf((2' |P]
3L?
E
||at 11]
+ n²003
n
where the first inequality holds by Young's inequality, and the last step uses smoothness of fa(-) (Assumption 1), which concludes the proof of (24).
For each & = D....TT_ - 1, define a random vector gt = ($...., < and denote by (x 5 : n ii= (.r( Note that the entries of the random vector ç are indepen-
-
dent and Eg: [V 5t) fz(z". then we have
x² 1i + 17 (V) o'
where wi : Ei of is an auxiliary sequence. Therefore, we can similarly derive
E D[ll''vV/ vf( = E -|100 Vf(at) + n (Vf(=',,) 112
E Bgr [1(] - ()(6-1 V + (VS(=*, ( -V(((,))VV((())())
30

---

(1 2 [100-1 [|1o-1--f(aat
- vf(2"))] [|] + t -
(1 7)2 (1 " ") E -11--1--1(a' V/(aa 11
S
(1+ 2
E ||V - vf(zt)]] ||"] + n¹0²
+
7
n
3L2 E
1P0²
s (1- 1)
)| -
x-' x 1 [|]
n
where the last step uses smoothness of f(+) (Assumption 1), which concludes the proof of (25).
F.2 Controlling the error of contractive compression and momentum estimator
Lemma 3. Let Assumption I be satisfied, and suppose C is a contractive compressor with S 1 For every i = 1,...,9, ,,, let the sequences {u()12 and {91 be updated via
o = = 1 + 1 (V.i(i',, 44) - -0;00,;-)) 1
9 = of + C (ut 91¹ 1)
Then for every = 1, 1,...,, n and 1 2 0 it holds
4n² 2
E
o 0/119] $ (1 2
l - uf 11]
+
E |og
a
12,17² E ||ue - - 11]
+ 111000
(26)
Proof.
By the update rules of of and vti we derive
E
|lst
E ||0 - of + C(uj -9t |1
E Ee [|CCo] - of - (of g6 - |]]
(1 a IE
|ff - 96 =11
(12
a E
[|0] 96 + n Si -
(1 E
Eet |10 1 96 -
(1 a E
[|05
-6 + (V
-x)
+(1 - aa)n"B
(8))
||0| of - 111] (1 (1 [105 ||0--1 ff f((xx))]
(1- (1 +1+ P)
+(1 - (1-a))n20* a))200
(1 faE
|10 1-1
0 -1-=1|]] + 3 [| - v Ti(('') ||²] + - a))
|10 - of |1| 2,3 E
||0| vfila' 11]
(1 O)E
+2,87
[V//((²)) Vf. 1|
+ 12202
||o! -1 of 111 2 |10| viiaa' 1|] 2]
S (1 O)E
+2BLi,²B [| ||aa"x"'
-0--=1111 ||]] +
where (i) is due to the definition of a contractive compressor (Definition 1), (1i) follows by the update rule of of. (iti) and (v) hold by Young's 's inequality for any p > 0. In (iv), we introduced the notation
31

---

0 = 1 (1 - (1 + p), and 3 (1 a1 +- The last step follows by smoothness of 5i(-)
(Assumption 1). The proof is complete by the choice = oz/2, which guarantees 0 s 1 0/2 and 23 < 4/a.
32

---

G Further Improvement Using Double Momentum (Proof of Corollary 3)
Algorithm 3 EF21-SGD2M (Error Feedback 2021 Enhanced with Double Momentum) 1: Input: starting point x², step-size y >> O, parameter 1) E (0, 1), initial batch size Buii
2: Initialize uf = og = S. Bui Σ Bui j=1 ff((2", (22) for = 1,.... n; g" #/4 - 9
3: for = 0,1, T - do
4: Master computes xz
x² g and broadcasts x++1 to all nodes
5: for all nodes i = ...... n in parallel do
6:
Compute the first momentum estimator o/ (1 - n)u V (t
7:
Compute the second momentum estimator ui Compress e C(u, C(ut+) gf)) and send cf the master
(1 n)ut + nott!
8:
9: Update local state of+ g + +. 2+1
10: end for
11: Master computes g0+l 1
Σi= 91 1+1 via gaght = g'+ 4+1
n
12: end for
In this section, we state the detailed version of Corollary 3 Theorem 5, followed by its formal proof. Notice that the key reason for the sample complexity improvement of the double momentum variant compared EF21-SGDM (Theorem 3) is that in (27), one of the terms has better dependence on 7) compared to (9) in Theorem 3, i.e., 1)²0² /aa instead of 1f² /a. As a result, this term is dominated by other terms and vanishes in Corollary 3.
Theorem 5. Let Assumptions I and 2 hold. Let ST be sampled uniformly at random from the iterates of the method. Let Algorithm 3 run with a contractive compressor. For all n E (0, 1] and Bin 2 1,
with y S min { 60L
we have
16L
Vg
0/02
11002
17
E
V
0
+
(27)
TT
a
n
where Vo = 60 + 2
|| 1o0
- vf(29))
E
1lof vf((0)) [²]
Setting initial batch
size Binit =
o²
step-size and momentum parameters
Lbo
11
= min (
(L o2T
3/4
Ldgn o2T
1/2
a Lop Bunn
7 = min
(28)
160%. 16L
get
Ldo
2/3
8/4
4/2
Σ E [[V[(>))]]
s o
aT +
(
+
22/3T
nT
t=
Proof. order to control the error between gr and Vz(x"). we decompose into three terms
11g - v/(a2)]
s 3 I|g' - w²11 + 3 uu v² || + 3 3110* V)(aa)]|
3 n
1 Σ l1 utl?
+ - -lll'-o'11 +3 3| v
where we define the sequences vf a recursion for each term above separately.
1 Σm - of and vt = Σ of. In the following, we develop
Part I. Controlling the error of momentum estimator for each of and on average for vf. De-
note P, := E [|0' - (=(")) P. == 1/j E. E [|o vf(a'))) R. == E || ++ ||]
Similarly Part I of the proof of Theorem 3, have
3 T-1 1 Σ P
T-1
-
2
T
Σ
Rs +
n1o²
+
T/
Po.
(29)
1=0
1=0
33

---

T-11 3L2 3Lي ト
[-1 Σ R
no² n
+
+ n/
Po.
(30)
Part II (a). Controlling the error of the second momentum estimator for each ut. Recall that by Lemma 4-(37), we have for each i = ,,..., n, and any 0 < S and t 2 0
E
[| u
++
of
+
[1] I (1 1) [|ut - =f'] + 6n
|| [((())
+ [| - x²6 11] + +n²0²²
(31)
Averaging inequalities (31) over i = 1.....7. n and denoting Qi == ; Ei= E |lu - 2/1"]
we have
0. I (1 (1-1)0 Qt + 6n + 6T.2 + 17202
Summing up the above inequalities for t O..... T - 1, we derive
ΣΦ.
6
1
1
Pr + 6π
R₁ + 110 +
Q0
T A=
T
T t=0
1/T
t=
6 3L
1
1
6 1/T
+ 6Z.
Re + Tnjo" 2
Q0 + Po
1/2
T
1/T
19î² 1 T-1
Σ
Rs + 7njo" + n/
6
Po:
(32)
1/2
T
1=0
where we used (29), the bound 17 S 1, and ug = v. for i = 1,..., n.
Part II (b). Controlling the error of the second momentum estimator u² (on average). Similarly by Lemma 4-(38,, we have for any 0 < <1 5 and 2 0
E || - -2(
S (1 (1-1)) -- [| - v' [1]]
[|ue I [((+')1
+ 61ylE
1²02
+6L mE |||att| 22 [|]]
n
Summing up the above inequalities for t = O, O,...., T 1, and denoting Q2 == E |1 - 2-12 we derive
T e
6 T-1
T-1
Qr
&
Σ
P. + 6L
Σ
Rs + no² + Qo
T 1=0
T
T
'T
t=0
1=0
6 (6-312
T-1 1
7no
<
+ 61.
R4 +
+ T/
Qu + Po
1/2
n/T
(=0
19L² 1 T-1
Tno²
6
R₂
Po.
(33)
2/2 T
n/
where we used (30), the bound 17 S 1, and u = v0.
Part III. Controlling the error of contractive compressor and the double momentum estimator. By Lemma 5 we have for each i = 1..... n. and any 0 < 1
< 1 and 2 0
E [1 - uf "I]
(1- 2
| - ui1 [²]]] + 6x7 E [|ut - of
<
E
(34)
2
+ 617*
E
||u| Vf.l'' 1|]
+ 67,'"²
E
|1-- - x
141
2
+ nj
a
Averaging inequalities (34) over i = 1, ..... .n, denoting V.. = 1 Σ E
[19]
ut
and summing
up the resulting inequality for / = 0,..., T 1, we obtain
1
T
v 12
T-1 1
12n 4
T-1 1
12L2np
T-1
2n1²0²
Q. +
P
R₁ +
7
a
T
T
a²
T 0=
0=0
0=0
0=
34

---

12mp
1912 1
T-1
12n
332 T-1
Rs Tnjo²
Σ t=0
Rr + n70?
a²
112
T
a²
112 T
t=0
12L²'1 ạ
1
T-1
24
121 4
Re +
a²7 Po
a²
T
1=0
12. 19
T-1
12 o1
12- 12-3L 12
T-1
127
R1 +
R +
a²
T 1=0
a²
a²
T
a²
1=0
12 1 T
T-1 Σ
2n'002
12n
Rs
a²T Po
a²
a
276ī² T-1
12n20² 84
20
121 a²T
Rs +
+
Po
a²
a²
a²
a
(35)
Part IV. Combining steps I, II and III with descent lemma. By smoothness (Assumption 1) of f() it follows from Lemma 1 that for any y S 1/L2)) we have
(( s [(x²) 2 (=>))
1
|
x²
$11
+ 2 llgs +
(36)
47
2
s f(at) 7 \/
1
|| =0²11
2
47
+ Σ |1o
3r 1
+
37
||u² - -v1112+
+ 1100 {)((")11
3y 2
2
Subtracting f" from both sides of (36), taking expectation and defining 6, = ([f(x(()) [*]. we derive
E
200
T-1
1
1 T-1
1
Σ
V/ + 3
Σ t=0
Q: + 3
Σ
P.
Σ Re
7T
T
T
27 T
1=
t=
1=0
(9)
260
3 276
T-1
3 82
3 1277 0²
3 27 02
Rs
+
7T
a²
a²
a²
a
1=0
3. 19L2
T-1
3 3-700
R4 +
1/2
n
t=0
3L 1
T-1
1102 2
1
T-1
R +
Rr
1/2 T
2- T
1=0
1=0
361
18
3 Po
Po +
Po +
2T
T/
260
3. 841 30 0²
3. 12 5 0²
3. 2n 4 0²
22n10 2
'
a²
a²
600
3. 2.677
1
T-1 1
+
R
1/2
a²
27
T
1=
361
21
Po +
Po
2TT
1/'
260
2887 0²
6n) 4 02
22mp²
361d
21
+
+
+
Po +
Po
T
2
n
2T
nT
35

---

where (i) holds due to (30), (35) and (33), the last steps hold because of the assumption on the step-size, and S 1, which completes the proof of the first part of Theorem.
Notice that it suffices to take the same initial batch-size as in the proof of the Theorem 3 in order to "remove" Po and Po terms, since the power of 1 in front of Po is larger here compared to the proof of Theorem 3. The choice of the momentum parameter such that 17 -
[Laga²
<
Ldun
ensures that n²0² T
a= S
Ldia and Do²
Therefore, we can guarantee that the 77" ensures that
Laba
choice 1) min
L T
1/4
LAnn oT
1/2
Ldd aT
Lón02/3
8/4
[Lógo² 1/2
E
|
o
+
+
2//3T
ni
G.1 Controlling the error of second momentum estimator
Lemma 4. Let Assumption be satisfied, and suppose 0 < <n <nS1. For every i 1,..., n, let the
sequences {ef) 1:0 and {ufh20 be updated via
of = ot + 1 (Vi((1', , - 1)
t = पt 1-1 + 1j (u} - u 1
Define the sequences n² holds
= - ot and xt := 1/2 Σi=1 ut Then for every = I,..., and t 2 0
E
Iu - 0/
11 S (1-n)E || of || + Bn
||0 Vff(
+6I,21B
|1st - x." 11= 113]] + 17? o²
(37)
E
1| -1 s (1 - B) || 0 11
+ 6.
||11 |11-111 7f(x"~1111
+ + || -. ||]] 11²02
(38)
Proof. By the update rule of of. we have
E ||u| =[]["]
E
u of + (uu -
(1 1) 2
|||| - u [|a]
(1 M
(1-- - m) + fi ( -uf-111 113]
(1 7)) P
[ 1 ( V.((at ((((+==))) [7]
(1 1)) 2E
[ o/ 1 + n v.((2()) V/((=()) +
(1 7 PE
EE
[1]
(1 7) 2 EE
1u---1--00 of n( Vf((='))]
+ + (
S (1 1)) 2E
n60 Vl((z'))
+1200
(1 2
(1+)) [1 of
) पं
1+
+ 1220
36

---

S (1 3
4 - "1] + 3 [10
Vif((=')] 1|] +n7022
S (1 7))
1 - -1] + Bn |10f-1 Vsi(ot-)) [1]
B [|V/;(x') - V)i((='))) 1)| + +1/²0
$ (1 n) |u4
-f 119 + Bn || - vfi(a'-1)1 19]
+6T,,1 [1|2* -||=-~=--11 |1r] + 1/²0²
where the first inequality holds Assumption 2, the second incquality holds by Young's 's inequality, and the last step uses smoothness of f((-) (Assumption 1), which concludes the proof of (37).
For each t = O.....T T - 1, define a random vector ę := (Ci...., ...) and denote by ff (( == - 1 fi("', <(). Note that the entries of the random vector g are independent and Ege [V ,5) = Vf(a") ) then we have
0' =' (Vf(x' - -1)=='==)-="" r)-,),
it 1-1 + 17 (uf -u u
where of = n Ei= uf. ut == derive
1
n Ei= tt are auxiliary sequences. Therefore, we can similarly
E [|I't 0-][]]
= E || |
8¹ + nt(²" n² |1? [1]]
2)² E
|u' u 11]
(1 7)) '
(11 - m) 1 + // - -
(1 "E
[( )1 + 1 "
(1 17) Z
2 + 1700 - Vf(z')) + -
(1 17) 2
7 - ()(2')) - ) - |
-1 17( -- Vf(z'))] + +oFE - -
(1 ))
1202
(1 7) 2
+ m/2001 [[(x9))11
n
N (1 n)?
(1
? (2) E 1 1- 1111
1+ ?) n² [|| - v)(=a))( 17002
n
1f0²
(1 3llk a
1----- 111 3y |1001 - Vs(x')) [(a)))]]]
n
S (1 E)
1 1 -1- 119] En
|10011 vf(x 211
+ 1200
+69E
[ - v |"
n
< (1 1)
11--1- 11 + 6n
||| |110111 (
16L2nE ||-0-2²" - |13] 1/002
where the first inequality holds Assumption 2, the second inequality holds by Young" 's inequality, and the last step uses smoothness of f() (Assumption 1), which concludes the proof of (38).
37

---

G.2 Controlling the error of contractive compression and double momentum estimator
Lemma 5. Let Assumption be satisfied, and suppose C is a contractive compressor. For every
i 1, ..... nl let the sequences [v( {u]Jezor and (gl be updated via
of uf- +n (V < (t)-o(-1) o)
u = u, 1-1 + (o} - u! "/1))
g = 9.
1-1 + (ut g. ):
Then for every i = 1,..., n and 1. 2 0 it holds
llst u²119] s (1
E
u -
1|]
+
6n/ E || -
(39)
a
6n/² E
||u| Vii(='11, ||
+ 66.n
E
||
-|
+ t
a
Proof. By the update rules of of. us and v/. we derive
E |lot ud(l²]
E 9
1--1__ ut + C(u) - o 111
11-00 (1-a)B
|uu - 9 1/-]
(1 aB |1u, 1-1 9 1-1
+ tn(
- + [1
- 1
a) OB [|| 9/ + +n( 1(0t-1-44-1 (V/((=(( "
(V/((( () [[((+())
= (1 a) a) [ll - -.-1 + -
+
- -2f-
+n²² (V (35 [((('(
(1 B) ||0| 96 + +n - - +
+(1 - (1-a))n' a)n'' 'E V 5 |A(ッ)\|
(1 a) + p)B || of 11
=(1-a)(1 + >ロ )E -
+1j²02
|| 1-1 1 - اي 111 ||] + +1²0²
(1 0)E
+8E
mlme - un 1 n² (V (1---) o (V)('()) -
(1 - 0) E
[| 11ul-i-g(-11 11"] + 3,8 2 |11--1 mf 11]
+3,87 'E
||0 Vf (x-"--1))1 111²
+3,87" 'E
|| v fi(a'~1)]1
+ 11²02
< (1 - 0) [|u, 6-1 - ot [1² + 3 [10| mn 1 11]
+3881²T |||0 - V/ 111"
+38L?11E [|:0* 111a"-==-10 1 12] +12022
where (i) is due to definition of a contractive compressor (Definition 1), (ii) follows by the update
rule of of and uf; (zit) and (v) hold by Young's inequality for any p >> 0. In (iv), we introduced
38

---

the notation 0 = 1
(1 (1 p), and (1 a1 + pー The last step follows by
smoothness of /+(.) (Assumption 1). The proof is complete by the choice 0x22, which guarantees 1 1- 0 S a/2, and 33 S 6/a.
39

---

H EF21-SGDM with Absolute Compressor
In this section, we complement our theory by analyzing EF21-SGDM under a different class of widely used biased compressors, namely, absolute compressors, which are defined as follows.
Definition 2 (Absolute compressors). We say that (possibly randomized) map C. : IRd - R is an absolute compression operator there exists a constant A such that
E [1]((z)
|2] - A
Vx R
(40)
This class includes important examples of compressors such hard-threshold sparsifier [Sahu et al., 2021], (stochatsic) rounding schemes with bounded error [Gupta et al., 2015] and scaled integer rounding [Sapio al., 2021].
Algorithm EF21-SGDM (abs)
1: Input: starting point x0, step-size 7 > O, momentum 17 E (0, 1], initial batch size Bin
2: Initialize of 9. B Bui fz 41.3) for i = 1..... m; g Ei=13 9e
3: for t = 0,1, 2........ T
do
4: Master computes x+1
rg and broadcasts x1 all nodes
5: for all nodes i = 1, ,,..., in parallel do
6:
Compute momentum estimator of (1 n)uf + f/ tt
Compress o +1 = [o and send et+1 to the master
7:
8: Update local state sf 1+1 = o 70t
9:
end for
10: Master computes g 1 Ei=1 gi +1 via vi g = g" + E 74 ++1
end for
To accomodate absolute compressors into our EF21-SGDM method, we need to make a slight modification our algorithm, see Algorithm 4. At each iteration, before compressing the difference of L. divide it by the step-size 7.. Later, multiply the compressed vector of by y, i... have
1+1
9
9. ++1 +
Such modification is necessary for absolute compressors because by Definition the compression error is not proportional to ||=]1² but merely an absolute constant A In fact, Algorithm 4 is somewhat more universal the sense that it can be also applied for contractive compressors. 20 We derive the following result for EF21-SGDM (abs).
Theorem Let Assumptions and hold. Let a sampled uniformly at random from the iterates of the method. Let Algorithm 4 run with an absolute compressor (Definition 2). For all E (0, 1] and Bu 2 with 7 S 1. 4
we have
Vo TT +
11²2
E
& SO
(41)
where Vo = 50 + 3R momentum parameter, and initial batch size
[ is a Lyapunov function. With the following step-size,
La 2TT
Löon 2T
1/2
σ²
min
1,
B
(42)
4L
Lóon
have
Lgg
60
2/3
1/2
E |
12]
<
O
+
T
T
nT
2I is straightforward to modify the proof of our Theorem 3 for the case when Algorithm 4 is applied with contractive compressor.
40

---

Corollary 4. Under the setting of Theorem we have B ([(
after T
O Lbu 5 +
LL ne*
iterations.
Remark The sample complexity result in Corollary 4 matches the one derived for DoubleSqueeze algorithm ['Tnng et al., 2020], which is different from Algorithm 4.
Proof. Similarly to the proof of Theorem 3, we control the error between ge and Vf(x²) by decom- posing it into two terms
1g0 - s2llo"" v' +1/+2/10 -V(())]
S 2- 71 Σ 11 -
||
Again, for the second term above we can use the recursion developed for momentum estimator Lemma 2. However, since we use a different compressor here, we need to bound ||g - of term differently, thus invoke Lemma 6 for absolute compressor.
Part I. Controlling the error of momentum estimator on average for vf. Denote P. := E ||ue Vf(x')] R.
E
||
x 2
[1]]-
Similarly to Part of the proof of Theorem
we have by Lemma 2
T-1 P.
3L 1 S
no² +
Σ
Rs
Po.
(43)
T x=0
7
n/
Part IL Controlling the error of absolute compressor and momentum estimator, By Lemma have for any 1) 1 and & >
1
V =
EE 99
- S م
(44)
Part III. Combining steps I and II with descent lemma. By smoothness (Assumption 1) of f(-) it follows from Lemma that for any 7 S 1/(2T, we have
f(x+11) I f(x') 2 |f(x')]|
- 1
| - x0112 + 2 ||gs VV0-Vf(aa v((''|]
(45)
2
4
S f(x0) ? 2 [f(x")]| 1
||att1 =111? + + ypc.
4y
Subtracting fr from both sides of (45), taking expectation and defining = E [f -f"}. we derive
E
|
+
Σ E
280
T-1 Σ
T-1 Σ
1 T-1 2₂ T
+
P
R
7
T
(=0
1=0
(=0
280
+
272 + 2
1 T-1
Σ
P
1
T-1
Σ
R
TT
T
2₂ T
1=0
1=
260
(6L
1
2n1a
1
2
Σ
Rs
Po
7T
272
7
n
1/
260
2no
2,22
+
Po
7/T
n
T/
(46)
where in (1) and (ii) we apply (43), (44), and in the last step we use the assumption on the step-size 7 (4L).
41

---

Setting 7
_1. and taking v
L'de A
1/8
we can ensure that
1²4² 1/
Lóa
since 1l
Ldin 1/2
47.
77
o²
have d² Lóo 7/
ga² Ldy 57
Finally, by setting the initial batch-size to Binit Therefore, derive
o²
have 7 Po
Loan
200
2no
Σ E Vf
+
27
2²²
+ 11
Po
TT
8T60
1
2nj02
a²
+
nT
8L2
n
rJ Binst
Lóo
o (L80)
0
T
T/3
(nT)
(47)
H.1 Controlling the error of absolute compression
Lemma 6. Les be an absolute compressor and g;" ++1 be updated according to Algorithm 4, then for t 12 O, we have Di= |lot = S A
Proof. By the update rule for of ++1 in Algorithm 4 and Definition 2, we can bound
E
|19. ++1
2 1
E
|nc
0
+++
g
(uf+)
c+1
9
7
||e
(
c+1
96
1+1
o
27
S
59²A2.
42

---

I EF21-STORM/MVR
Algorithm 5 EF21-STORMMVR
1: Input: æ0, step-size 0, parameter (0, Binit
2: Initialize u = 9 Bm 2j Vfi(2) c0 for 1..... ni g" E. of
3: for -= 0,1,
do
4: Master computes xz = xt ng and broadcasts af+1 to all nodes
5: for all nodes 1, ..... parallel do
6:
Draw et+1 and compute two (stochastic) gradients V f( , and vf((""11.4"""
7:
Compute variance reduced STORM/MVR estimator
8:
Vf(x'*11 - [ + (1-11)1)) (w fi''', (e,,<(+)) Compress o C(w
w
9:
g and send e++1 to the master ++1
10: Update local state g ++1 = g + 9
11: end for
12: Master computes g 1 Ei= 9i 1+ via g = g6 + + c
13:
end for
Assumption (Individual smoothness?)), For each = 1,..., n, every realization o ~ Di, the stochastic gradient fe(a,g)) l. Lipischit for all x, Rd
[Vf(((.))) (.)l s vl1
We denote 72 = +E
Theorem 7. Let Assumptions 1, 2 and hold. Let a. be sampled uniformly at random from the iterates of the method. Let Algorithm 5 run with a contractive compressor. For all E (0, 1] and Bini 2 with 7 I min { a
va
vnn
we have
88
68
E
)
11]
0
T
00022
11a02 +
no² +
(48)
TT
Q
n
where vo 6, + E
|100
-
E
1100 vs((2))]1
With the following
step-size, momentum parameter, and initial batch size
3/7 ( Edoa
2/3
Va
Eôna² Q2
to tōovn TT
min
min {a.
onT
8L
68
88
and Bunh max
a²
we have
Ldon
9/7 +
4/5
2/8
Ldo
Edo
Ebgo'o
Edng
Edga
[
aT
+
VaT
+
aall
a²la
+
nT
Corollary 5. Under the setting of Theorem 7. we have E [[(>(())>)]
after T
O
Eb0
Eb 1/3
16.0
Ebno wg
iterations.
Recently, Yau and Wai [2022] propose and analyze DoCoM-SGT algorithm for decentralized optimization with contractive compressor under the above Assumption 3. When their method is specialized to centralized setting (with mixing constant p = 1), their total sample complexity becomes
O ae2 2//2//2
1/5 + nes) (see Table 1 or Theorem 4.1 in [Yau and Wai, 2022]). In contrast, the in the last term and,
o²
sample complexity given in Corollary 5 improves the dependence moreover, achieves the linear speedup in terms of n for all stochastic terms in the sample complexity.
This assumption be also relaxed so-called expected smoothness.
43

---

Proof. Similarly to the proof of Theorem 3, we control the error between g' and (x(x)) by decom- posing it into two terms
vf(a"))| ||9' V(((t)) w² -
= 72 Σ 0 w||| + - -Vf(ct)]
In the following, we develop a recursive bound for each term above separately. Part I. Controlling the variance of STORM/MVR estimator for each wa and on average w'. Recall that by Lemma 7-(55), we have for each L,..., n, and any 17 S 1 and f 2
[| V [|] = (1 1)
[
[)( + 222 [| 111] + 2120² (49)
Averaging inequalities (49) over i = 1,...,n in and denoting P. = Ei= E [Imes Voi(=')1
Rg = E ||= z1
[|]] we have
Put S 11 + 28 R2 + 222/
Summing up the above inequality for f = O,...,T T - 1, we derive
Σ
P
20
T-1
Σ 1=
R2 + 2nj0²
1
Po-
(50)
T
1
niT
Similarly by Lemma 7-(56) denoting P; = E
IIw*
{S(xt))
we have
T P.
1 T-1
Σ t=
S
26 1 T
R
+
2n1² n
+ r/T
1
Po-
(51)
m
T
t=0
Part II. Controlling the variance of contractive compressor and STORM/MVR estimator: By
Lemma 8 we have for each i = 1, 1,...,7, n. and any 0 < 1) S 1 and /
2 0
E [10 (+1 w [1]]] < (1
(1-
E
-wtl ||] + 4nj2 E
|| - V)((=')]?
2
+ a
AL
+ e E ||
xx -011"]] + 2n700²
(52)
Averaging inequalities (52) over i = 1,... n, denoting V/ n up the resulting inequality for t 0,...,T T 1, we obtain
Di= Ilst - uo]l²]] and summing
1 T-1
81p2 1 T-1
8 a
2
1
T
211²02
Σ
V/
+ P
+
R₂
+
T
a
T
a
T
a
1=
2
16ml
T-1 1 Σ T t=
$
R
a2
a
a²
161002
2m 2
0²
81 22
Po.
(53)
a²
Part III. Combining steps I and II with descent lemma. By smoothness (Assumption of f(-) it follows from Lemma that for any ? S 12L) we have
f(att1) < f(x') -7 ||](2=))1
1
|
xzt
111 7 1lg" v)(x+))
(54)
47
s f(1t)
7 2/ ||
11
x²d
112
+ Σ o1 will + Iw' - -V v((a))12
47
44

---

Subtracting f" from both sides of (54), taking expectation and defining 5. = [ff(x²) f*) derive
T
E
E
Vf(x'))
T t=0
280
1 T
T-1 Σ
Vi
T-1 Σ
Pt.
Σ 1=
Rr
7
T
27 T
1=
1=0
280
1672
48t
+
32nl
T _5
1 T-1
Rs + 2
T-1
Pt
1
T-1
Σ
R
77
0²
0
0²
27 T
0=0
32m
4n/00
16n
+
Po
a²
(0)
280
167
47
32m
2
42
1
T 1 Σ
Rr
7T
a
0
mm
27
T
t=0
32 02
4nj²02
4no
16n
2
Po Po
a²
n
a²T
26
02
4nf0
4n
167
2
Po
Po.
TT'
a²
n
a²T
1/
where in (i) we apply (53), in (it) we use (51), and the last step follows by assumption on the step-size, which proves (48).
We now find the particular values of parameters. Using 1
Σ
Ej=
Bun (1(2%,4) for all
i 1, 1,...,n, n, we have
o²
n -
σ²
Po E [l V/
and Po
Σ
E
nB.i
Bun
We can substitute the choice of y and obtain [|T)(TT)
80
17-02
12202
no²
0²
n0²
=
7T
a
+
n
+
m Bini T
+
a² Bini T
Ldo
Edo
2do
01²02
11200
+ n1²
+ o²
no² a Bun T
+
aT
VaT
VnnTT
a
n
mp ammin T
Since Bini 2 Lógni we have
E
| [|]]
o
o
Lōo
260
fdo
11002
+
11002"
+
10²
+
na²
aT
VaT
VnnTT
a²
a
n
a²
Q²Bui
Notice that the choice of the momentum parameter such that 17
5
03
28n0²
7/7
17 S
0² o'V
Phaee
2/5
S
7/3
and
<
E8na Bim o²vR
ensures that n²0² at
S
75.
n200
<
75
na?
F6
T
vant
vani
n
and B
no²
Eho V
Therefore, we have
a
Ldo aT
28. VoT
Pogo
4/7
4/0
1800
2/3
Ed0g
2/3
1/3
[ = o
+
ants/nT
+
aaa
/ni
+
nT
+
vn
B F3T
Using Buit 2 T
we obtain
4/7
4/s
3/5
Lőu
Eōo
Edpo
1/3
Edgo
E || o
aT
+
VaT
+
(ri
+
at'a aril
+
nf
45

---

I.1 Controlling the variance of STORM/MVR estimator
Lemma 7. Let Assumptions 2 and 3 be satisfied, and suppose 0 < n S 1. For every i = I........
let the sequence {wi be updated via w f ff( . ( )) + (1 n) (x
Define the sequence w" := 11 Ei= wt. Then for every i = 1,..., n and 1 2 0 it holds
E || V/i(( s (1- - 1n) [Iw V)((E))) - 22, [|at 1|1 + 21f00, (55)
E ( / [|] 5 T) [ - v + -B
26"
E |||a*
x +2 |2]
2n)²0² (56)
Proof. For each 1. = 0,..., T 1, define a random vector & == (Si.... 5% and denote by ff(a", ==
1 " Li=1 f((x',, {. Note that the entries of the random vector 8 are independent
and Be [Vf(x') [t) = ff(²". ), then we have
+ Vf(xtt ()+ + +(1 1) (w' - Vf(x ((t)))
where w¹ = E w is an auxiliary sequence. We define
n W = Σ W
V : Vi( + v.((z'),
1t: Σ V/
W = V/((')) - Vf(('' ( + (0(xt+,,/++)) -
i=1
Then by Assumptions 2, we have
E [V:]] E [W:]]
E [M*] E [M]]] O,
(57)
E | []]]]]
م²²;
E [|>~"1²] z o²
(58)
Furthermore, we can derive
E
[1
E
1 Σ
W
1
E
WM
n²
1
E
||
E
[aw wW}]
n
n
E
[|
Σ
E
[w!] E (M
n
Σ
E
[|!:
af 1+ - - V/((a" 1
E
1 - x 20133] = L
70
Σ
GE
1 - 1 =1]
22
46

---

where (i) holds by the conditional independence of W and W and the last inequality follows by the individual smoothness of stochastic functions (Assumption 3). 3). Therefore, we have
E [ S eE PE [|= - ='
E
||alt|-2'11"
22117]
(59)
where the first inequality is obtained by using a similar derivation. By the update rule for w", we can also derive
w+t1 (x(ttt) = (1 1)) (w
+ (VS(x ) -v((ttt)
= (1 1)) (w² - -Vf(=*) + + ( -V((tt))
+(1 -1) 11 -(f(==")-V("''> ( + g( Vf(att)))
= (1 1) (w' V.(xx)) + m/pet + (1 n)Wh
Therefore, we have
E || - [((xtt))1)
1 E Ber+1
[|(1 - 1) (vo' - vʃ(x²)) + +1/++11 + (1 (1- m.:11 [|²]
= (1 - 2)²E E |||0 - vf(x'))] ||9] + E
+ (1 - -1)
S (1 - 11) || - VF(('') 12 + 217 E |||p+||1 ||]
[||0** [2]
+ 2E
(1 - B) |||0 - - + 20²17 + 2
|| x01 112]
where the last inequality holds by (58) and (59). Similarly for each i 1,..., n, we have
w
Vf((ttt)) (1-n) n) (m) - ff((z') + mpst1 + +11 W)
(60)
Thus.
E |1 ( $ - (1-7)B | { + +202,1 + 22 R..
1.2 Controlling the variance of contractive compression and STORM/MVR estimator
Lemma 8. Let Assumptions 1, 2 and 3 be satisfied, and suppose 0 << S 1. For every i = I,..., let the sequences {w] and {g) 1g0 be updated via
w 1+1 vf((=*11 .g5+') + (1 10--mi (n) Vfia"', ()))))
9 I+l = of + C (ut+ ++1 gt)
Then for every 1, l,..., a and t 2 it holds
E
9
4+1 - wf 1 [P]
< (1
a
E |1
-wfll ||]
+ 4n² E || - V\(('')1
2
+
AL?
+ e?)
E
||
21| 2n
(61)
a
Proof. By the update rule of wt. of. and definition of Dj, W given in the proof of Lemma we can derive
E
|| +1
:f 11²]
= E || +1 - -t) - (w - st)I
(1 aE
|| - g8 [c]
(
(1 a E
[|(1 - 1)) (m) - Vf((z')) + -, +11 + f 16/1
Beeta [[[1 - 17) (vof - v/((=')) + + m)W! + vii(e(tt)- - =f
(1 - FF
47

---

(G
(1-a) [|(1 - 1)) (wj - vif(a')) + Vfi(tttt)) - -sill"]
+(1-a) a)B ||111 + (1- -
19]
(1- a1-a)B [I[(w] - (f) (V - vli(z*)) - (w: (oo1~>(('')) v/((=')]1
+(1 a) ||1n (1 m)m |
(im)
(1- a) (1+ p) || |
sfll
+(1 (1- (1 + 1 E [1 -V/(a=)))))((() - (n - V)((a>))] -w:-vVi(>*)]]
+2(1 - a) || + 2(1 1011--a(1--0)
a) - 8) ||
(1 0) || || - 19
+ [|| [V +1 V n/ -
+2(1 o)n1²B || 1] a) (1-1) [|
(vi)
(1 O)L
|| o8 1|| + 2 || - V)(()')1
+28E |l
+ 2 | - 2011]] + 217² 0²
(1 D)
[| 1/
+ + || - [\((=))\1?)
+ (2BL3 + L)
E || - -1=tt1-0011" + 2n)²0²
where (i) holds by Definition 1, (ii) follows from (60). (iii) holds by unbiasedness of V and W
(57). In (iv) we use Young's 's inequality twice, in (v) we introduce the notation @ == 1 (1-a)
and B == (1 a1 + o '). in (vi) we again use Young's 's inequality and the bound (58) and (59).
The last step holds by smoothness of fa(-) (Assumption 1). The proof is complete by the choice p = a/2, which guarantees 0 I a/2, and 23 < 4/a.
48

---

J Simplified Proof of SGDM: Time Varying Parameters and No Tuning for Momentum Sequence
In this section, we give simplified proof of SGDM in the single node setting (n = 1) without compression (a 1). The following theorem shows that the momentum parameter can be chosen in parameter agnostic way as 1/vV++ (or 4 + 1), instead of being constant depending on problem parameters as is suggested in our main Theorem In other words, using SGDM with time varying momentum does not introduce any additional tuning of hlyer-paramette
Theorem 8. Let Assumptions 1, 2 hold. Letn and Algorithm I run with identity compressor C, Le.. a = 1, and (possibly) time varying momentum nN E (0, 1] and step-size paramters 7tt = YI with 7 E (0, 1/(za)]- Let a be sampled from the iterates of the algorithm with probabilities
Pt. = //t //t= - Te), then
2A07 + 202 =1=0 Th
E
<
Et
where Do == f(x") f + +B 11000 [](x9)]|] is the Lyapunov function.
Proof. By Lemma 2 denoting :; [lue- V Rr = E [|10* - -101112] we have
3L
P01 P +
R4 + 17:02
(62)
By descent Lemma 1, we have for any 7/2-
61+1 8c
7 2
V
||
1 - (1- Rg + "t P..
(63)
27
where dn := == f+.. Define the Lyapunov function as A, = 60 + 7Pc. Then summing up
(63) with a y multiple of (62) and noticing that 7/4 7, we get
A+11 < A, 2 [
1 (1 - R2 +ma00
2%
Since $ 11((3.), we have 1 7I. - 2,2 2 < O. and, therefore, by telescoping we can derive
Σ 1/t
M
2A + 20
=t= m
T- 2
-1= f1
The above theorem suggests that to ensure convergence, we can select any momentum sequence such that o² E oie < co, and E 1/22 for - co. The parameter 7 which determines the step-size = Mr, should be set to 7 = 1/(3L) (to minimize the upper bound). Let us now consider some special cases.
Deterministic case.
If 0, we can set it to any constant 7/ = E (0, 1] and derive
260
L55g
O
T/
2haht is. independently of the problem specific parameters
49

---

Stochastic case. For o² > O, select time-varying n
constant 7/ //41'' which
vrFI
gives Vt oi O (log(T)), and Ei Th = (T)
Thus
LAo ( o²
|>< =
VT
Notice that if set т) above, do need any tuning of momentum parameter. Only tuning of paramter y is required to ensure convergence with optimal dependence on T, as in SGD without momentum. Of course, this rate is not yet optimal in other parameters, e.g., o² and L. To make optimal in all problem parameters, Theorem 2.
LAg 1/3 similarly to the statement of set 1) max { (a-))
50

---

K Revisiting EF14-SGD Analysis under BG and BGS Assumptions
In this section, we revisit the analysis of the original variant of error feedback (EF14-SGD) to showcase the difficulty in avoiding BG/BGS assumptions commonly used in the nonconvex analysis of this variant. In summary, the key reason for BG/BGS assumption is to bound the second term in (67) or (68).
Recall that EF14-SGD has the update rule (Stich et al., 2018]
1 9
x = x² -5-- g
94:
(64)
1=1
c ++1 = e; + vV fi(a"" + gi:
EF14-SGD:
(65)
0: 1+1 = C (c: 4+1 + /i ,(+1))
where {</} are error/memory sequences with e = 0 for each i = 1,..., Let = En= The proof of this method relies on so called perturbed iterate analysis, for which one defines "virtual sequence": j == x² ee. Then is verified by direct substitution that for any 2
x++1 -++
V fa $)
If follows from Lemma 9 in [Stich and Karimireddy, 2021] that for any 7 S 1/21 and 2 0
E [|( < E [(())] 3 [IV ||]
Lo²
L
L E [1]
+
+
2n
Telescoping the recursion above and setting du = f(z²)
f we have
[
S
480 T
2g
+ 21
T-1
Σ
E
|e"119]
(66)
T
Now remains to bound efficiently the average error term E Jensen's incquality, we have
=E
[1
e/1l]]
By
E
E
and develop bound for each E
||>]|] individually, Denote by x et + 7 [. then
||et 114+11 ||]]
E [[((=) =|²]
(1 a)E
||o [
(1 a) (1+g) [|| + (1+ 2 21+2) (1x
(1-5) E ||=-1||| + 322 1 [Vir(''
(67)
where we used Definition 1 and Young's 's inequality.
BG asssumption. If we assume bounded (stochastic) gradients (BG), i.e., E [IVA((. for all = 1,..., n, then using (67) we can derive
5C
5
-
6²
-
a²
51

---

Combining this bound with (66), have
460 7T
2yLo²
g
Σ B
+
n
The step-size choice min
EOa TL
1/8
1/2
allows us to bound the RHS by
126
TLoz
72"
and guarantees
E
|[ || =0
Lón T
+
LooG
2/3
+
Löo
1/2
aT
nf
or, equivalently. T T 0 Lbo + ae
LooG Lgg) sample complexity to find a stationary point. This
analysis using BG assumption and derived sample complexity is essentially a simplified version of the one by Koloskova et al. [2020].* 23
BGS Em= E
asssumption. If
assume bounded
gradient similarity (BGS), i.e.,
- (vf()
G², we can slightly modify the derivation in (67) as
follows
||o|
< (1 - a)B
||e| + fi {1)
||ee + (z + +11-a)72B || / [
(1 aB
(1+ ( E || || + 1+ 2
a)
E [1>V +g20²
(1-
1 || + 3 E [|Vf(("')] +7202.
(68)
a
Averaging the above inequalities over i 1...., and using BGS assumption, i... 1 - E [|(A(0
< [|VS(()]] + G2 we can derive via averaging over t. = ,,...,T
Σ E [1E])]]
6
[[V
6y 2720² a²
E
a
Combining the above inequality with (66), we have
[ a²
1
Σ
[[V
460
L0
12-2
L22
+
T
TT
n
a²
a
By setting y = min
nón LT
1/2
2000
1/3
; I2o-T
) 1/3
we have (1
1212,² a²
and
4h
T
I2G2T
the RHS is at most
168g 7T
Therefore,
V || =
L5o aT
(50g
3/3
4/3 (varr
(oōgo
L5o
1/2
E
+
+
+
aT
nf
or, equivalently, T = 0 Lbg -
+
LonG asa
Lôgg Vael
+
Ldg ne*
sample complexity. Notice that in the single
node case (n = 1), we have G = 0, and by Young's inequality
Lóng /aT
Ló 3
Lōno"
at
Therefore, the above rate recovers the one by Stich and Karimireddy [2021] in the single node setting.
Up to smoothness constant and the fact that Koloskova et al. [2020] works in more general decentralized setting.
52


Reviews:
[{"review_id": "naHYAtfgXn", "reviewer": "Reviewer_Pi6q", "summary": "The authors propose a new version of EF-SGD which uses momentum. The authors show that under standard assumptions the proposed method has a better convergence rate. The authors claim that in several cases it is hard to perform large batch sampling like when performing RL training. To overcome this problem they propose a momentum based method, which can overcome the small batch issue. The perform additional experiments on Mnist and real sim datasets and compare there effectiveness.  ", "questions": "Please comment on the concerns raised in weakness sections. ", "limitations": "The authors in the opinion of this reviewer have not addressed limitations of their methods and their applicability to problems. ", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The proof indeed looks novel the assumptions are reasonable and the improvement in rates for small batch size is very encouraging. \n\n2. The problem is well motivated. \n\n3. The authors perform experiments and compare with different version of EF-SGD.\n", "weaknesses": "\n1. EF21 SGD although theoretically motivated is not a practical due to only 1 way compression and often highoverhead, authors should comment on the real world implication of EF21-SGD and EF21-SGDM. \n\n2. The authors are motivating their problem using examples from Medical Literature and Federated RL, but the actual experiments are performed on MNIST. In 2023, work like https://www.mosaicml.com/blog/mosaic-resnet trains Imagenet in 27 minutes using just 8 GPU, shouldn’t the paper at least have experiments using Cifar. \n\n3. The only comparison is with other EF21-SGD variants, can you please have additional comparison with other communication efficient methods. And the comparisons should be on wall clock time rather than bits communicated. \n\n4. Authors seems to be not accounting the memory consumption needed because of momentum, it would be great to have a discussion on that.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> 1. EF21 SGD although theoretically motivated is not a practical due to only 1 way compression and often high overhead, authors should comment on the real world implication of EF21-SGD and EF21-SGDM. \n\nIn our work, we specifically focus on the uplink communication (from clients to the server) since it is often the key bottleneck in distributed systems with many clients (many clients are trying to the server simultaneously), and it is crucial to tackle this problem before considering the downlink compression. It is common in this line of work to focus on the uplink compression [Stich et al., 2018], [Beznosikov et al., 2020], [Richtarik et al., 2021]. On the other hand, we agree with the reviewer that the downlink communication can be also important. One way to tackle this problem is to use compression with error feedback for both uplink and downlink communications. In this direction, Fatkhullin et al., 2021 propose a modification of the EF21 algorithm, which supports the bidirectional compression (Algorithm 5, EF21-BC), and analyze this method in a deterministic setting. Our momentum variant can be combined with EF21-BC to achieve (batch-free) convergence of the combined algorithm with stochastic gradients. Due to the space limitation, we describe the pseudocode of such combination above in the \"global\" response (Author Rebuttal). \n\n> 2. The authors are motivating their problem using examples from Medical Literature and Federated RL, but the actual experiments are performed on MNIST. In 2023, work like https://www.mosaicml.com/blog/mosaic-resnet trains Imagenet in 27 minutes using just 8 GPU, shouldn’t the paper at least have experiments using Cifar. \n\nAs requested by the reviewer, we additionally test the algorithms on image recognition task CIFAR10 with ResNet-18 deep neural network, see the attached PDF file. In summary, our observations based on non-convex logistic regression (with MNIST dataset) translate into this large scale experiment.\n\n> 3. The only comparison is with other EF21-SGD variants, can you please have additional comparison with other communication efficient methods. And the comparisons should be on wall clock time rather than bits communicated.\n\nWe respectfully disagree that the only comparison is with other EF21-SGD variants. Table 1 shows *theoretical comparisons* with Neolithic and EF14-SGD, which are based on the classical EF14 (EF) mechanism (Seide et al. [2014]). These two methods are not related to the EF21 mechanism. In experiments, we also compare our new method with Neolithic and EF14-SGD. The methods from Table 1 provide the current SOTA theoretical guarantees in our setting, which is why we only consider them.\n\nOur paper is not a systems/software work, where comparison using run time would be appropriate and expected. Instead, we address a specific algorithmic and theory issue  present in existing SGD methods with error feedback (the methods require large minibatches both in theory and practice), and thus our contributions are in designing an algorithmic fix and associated theory which proves that the fix indeed works. A theorem is worth a thousand experiments. Our experiments are meant to illustrate that our method solves this issue, and that our theory has predictive power. We believe that our experiments do exactly that. Combined with our theory, we believe this is conclusive evidence. Note that to show what we set out to show we do not need to rely on any particular computer system - indeed, our aim is to underline the system/architecture independent nature of our improvements.\n\nFor this reason, we aim to capture the dependence between the number of sent bits and convergence rates in experiments; these are system/architecture/runtime independent quantities. This way of comparing methods is standard in the literature on communication compression [Gorbunov et al, 2021], [Richtarik et al, 2021], [Huang et al, 2022], [Zhao et al, 2022], since such a measure is independent of specific implementation and computing system / architecture. It is also a way of comparison which ages much more gracefully - systems change quickly, but our plots are independent of these changes.\n\nNotice that compared algorithms calculate the same number of stochastic gradients and communicate the same number of bits in each communication round, so the comparison of methods will not change if we plot the convergence on the number of epochs. To support our argument, we re-run the experiment from Figure 3 (c) and measure the wall-clock time to get $\\varepsilon$-solution with $\\varepsilon = 0.1.$ One can see that the wall-clock times are strongly correlated with the communication complexity results from Figure 3 (c).\n| Alg.      | Wall-Clock Time |\n| ----------- | ----------- |\n| EF14-SGD | 1179.96 sec.  |\n| EF21-SGD   | 682.28 sec.  |\n| EF21-SGDM  | 314.47 sec.   |\n\n> 4. Authors seems to be not accounting the memory consumption needed because of momentum, it would be great to have a discussion on that.\n\nCompared to EF21-SGD, our momentum variant requires to store one more vector at each node $v_i^t$, thus the memory requirement of the proposed algorithm is indeed larger than that of EF21-SGD by a small numerical constant (< 2). It seems to be a relatively small price to pay considering that EF21-SGD may fail to converge (at least without batch size). On the other hand, compared to EF14-SGD, our EF21-SGDM algorithm requires to store the same number of vectors ($e_i^t <--> v_i^t$), which means that our improvement over EF14-SGD in the sample complexity and the strength of the assumptions comes without resorting to additional memory. We will include a brief discussion about this in the next revision; this is a good suggestion.\n\n---\n\nWe believe we addressed all criticism raised, which seems very minor to us. We hope this might lead to a better score. Thanks in advance! We are ready to answer any further questions!\n"}, {"review_id": "ZXB3Bvh1GE", "reviewer": "Reviewer_hi3u", "summary": "The authors present a new method called EF21-SGDM by combining EF21 and Polyak's momentum SGD. The theoretical contribution is that , it improves the communication and sample complexities of previous error feedback algorithms under standard smoothness and bounded variance assumptions. They also propose a double momentum variant to further improve the complexity. The experiments are conducted with non-convex logistic regression problems.", "questions": "Does EF21-SGD2M has practical benefits over EF21-SGDM? If not, how do you verify the complexity is improved over EF21-SGDM?", "limitations": "The authors did not discuss societal impact. I believe this is a theoretical paper and do not see much negative societal impact.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- only standard smoothness and bounded variance assumptions are needed.\n- identify an issue that EF21 with stochastic gradients has weak sample complexity guarantees, and fix it by leveraging our new Lyapunov function construction and new analysis.\n- sample complexity is free of $\\alpha$ and batch-free, the best from table 1.\n- The theoretical analysis is comprehensive and seems solid.", "weaknesses": "- Compared with theoretical contribution, the algorithm itself is straightforward, i.e., combining two existing methods EF21 and SGDM.\n- The experiments are validated on only logistic regression, where large-scale distributed training is not as crucial as in larger models.\n- EF21-SGD2M is not implemented in experiments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> 1. Compared with theoretical contribution, the algorithm itself is straightforward, i.e., combining two existing methods EF21 and SGDM.\n\nIn our opinion, the simplicity of the algorithms should be viewed as a strength rather than weakness of our work. \n\n**Multiple ways to combine EF21 and SGDM.** When our work is put into the context of the literature on compressed gradient methods, one can notice that several attempts were made before to combine EF with momentum. There are a number of ways one can combine EF with momentum, and it is not clear a priori which combination \"works\", i.e., gives any provable benefit over the non-momentum variant. For instance, [Xie et al., 2020] analyze the combination of EF14-SGD with Nesterov's momentum (M-CSER) and derive the convergence rate, which matches the one for EF14-SGD without any improvement (!). They also make a strong assumption on bounded gradients (BG) as for EF14-SGD. \n\nAnother approach to combine EF with momentum was proposed in [Fatkhullin et al., 2021]. In their work, it is suggested to look at the following scheme (EF21-HB):\n\n$$\n\\text{Master: } \\quad x^{t+1} = x^t - \\gamma v^t , \n$$\n\n$$\n\\text{Nodes: } \\quad  g_i^{t+1} = g_i^t + \\mathcal{C} (\\nabla f_i(x^t) - g_i^t ) ,\n$$\n\n$$\n\\text{Master: } \\quad g^{t+1} = \\frac{1}{n} \\sum_{i=1}^n g_i^{t+1}, \\qquad v^{t+1} = v^{t} + \\eta g^{t+1} .\n$$\n\nAs our EF21-SGDM, the above method is also a combination of EF21 and Polyak's momentum. However, the algorithm is very different: first EF21 mechanism is applied, the gradient estimators are aggregated by the Master, and finally the momentum is applied at the server level. In contrast, our EF21-SGDM applies momentum at each node followed by EF21 mechanism. Convergence analysis of EF21-HB is shown in the deterministic case and again only matches the rate of non-momentum variant. It is unclear if such variant would even converge when stochastic gradients (without mini batch) are used. \n\nIn summary, there are many ways to combine EF and momentum, and it is unclear if any other combination can show the provable benefit. A few previous works tried, but failed. That is why we believe it is *not straightforward* to find the combination that *works*. Our work is the first to demonstrate the provable advantage of our combination over all non-momentum variants of EF in the non-convex case. We manage to do so by proposing a new Lyapunov function analysis, which appears to be novel even when EF and the compressor ($\\alpha = 1$) are removed from our method. \n\n**Differences even in case of no compression.** We would like to point out that even in case of no compression ($\\alpha = 1$) the choice of the *step-size* and *momentum* parameters (in our Theorems 2, 3 and 8) are completely different from those proposed in the earlier works on SGDM, e.g., by Liu et al (2020). Due to a different order of momentum parameters, our proof technique is also completely different from [Liu et al., 2020]. Namely, we use the Lyapunov function presented in the equation (8), while the analysis of Liu et al. [2020] and the majority of other works on momentum (including EF21-HB in [Fatkhullin et al., 2021]) relies on (11), which has a completely different interpretation. We elaborate more on these differences in Appendix A (momentum). \n\nFrom the algorithmic side, this analysis with different momentum parameters can be viewed as an encouragement to use smaller momentum parameters (of order $\\eta_t = 1/\\sqrt{T}$ instead of constant) or even time varying momentum ($\\eta_t = \\eta/\\sqrt{t+1}$) as we describe in Appendix J. \n\n**New double momentum variant.** Additionally, we analyze a double momentum variant of EF21-SGDM (Section 3.4 and Appendix G), which further improves the sample complexity of EF21-SGDM. We are not aware if such an algorithm was proposed or analyzed before in the literature even in case of no compression ($\\alpha = 1$).  \n\n> 2. The experiments are validated on only logistic regression, where large-scale distributed training is not as crucial as in larger models.\n\nAs suggested by the reviewer, we include additional experiments with a larger model (ResNet-18 deep neural network with CIFAR10 image dataset), see attached PDF file above in the general response (Author Rebuttal). In summary, our previous observations based on non-convex logistic regression (with MNIST dataset) translate into this large scale experiment.\n\n> 3. EF21-SGD2M is not implemented in experiments.\n\nIn the above PDF file, we also provide experiments with the double momentum variant of our algorithm (EF21-SGD2M). Our simulations show that the performance of EF21-SGD2M is comparable to that of EF21-SGDM and also improves convergence of the previously known algorithms under this setting. \n\n> Question: Does EF21-SGD2M has practical benefits over EF21-SGDM? If not, how do you verify the complexity is improved over EF21-SGDM?\n\nBy \"EF21-SGD2M further improves the sample complexity of EF21-SGDM\", we mean the *theoretical improvement* when comparing the upper bounds in Corollaries 2 and 3. Notice that the iteration/sample complexity reported in Corollary 3 (for EF21-SGD2M) is better than the one in Corollary 2 (for EF21-SGDM) because the additive term with $1/\\varepsilon^3$ disappears for the double momentum variant. We provide some intuition behind this in the beginning of Appendix G. In our work, we do not claim any practical benefits of EF21-SGD2M over EF21-SGDM. \n\n---\n\nWe believe we addressed all criticism raised. We hope this might lead to a better score; thanks in advance! We are ready to answer any further questions!"}, {"review_id": "2TCu2NFVCZ", "reviewer": "Reviewer_5FHY", "summary": "This paper proves that momentum helps EF21-SGD. It makes several non-trivial contributions. First, it theoretically shows that EF21-SGD cannot converge when batch-size is small. Second, it proposes a simple remedy to this issue, i.e., incorporating momentum to EF21-SGD. Third, it proves that EF21-SGDM can converge well even if with small batch-size. Fourth, it extends EF21-SGDM can achieve linear speedup in distributed non-convex optimization without any assumptions on bounded gradient similarity. All these contributions are solid and novel. ", "questions": "See above.", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- It theoretically shows that EF21-SGD cannot converge when batch-size is small. \n\n- It proposes a simple remedy to this issue, i.e., incorporating momentum to EF21-SGD. \n\n- It proves that EF21-SGDM can converge well even if with small batch-size. \n\n- It extends EF21-SGDM can achieve linear speedup in distributed non-convex optimization without any assumptions on bounded gradient similarity. \n\n- The paper is well-written and easy to follow.", "weaknesses": "The paper is well-written. I have a few minor questions.\n\n1. In table 1, the authors claim that NEOLITHIC uses a large mini-batch, which may not be correct. While NEOLITHIC uses R times larger batch-size than EF21-SGD per iteration, it runs R times fewer iterations than EF21-SGD (see the NEOLITHIC algorithm in Huang et. al., 2022). On average, NEOLITHIC uses a normal O(1) mini-batch as EF21-SGD. \n\n2. Typo: In line 176, \"such\" should be \"such as\".\n\n3. In line 182, the authors claim that the proof technique can help establish linear speedup for Scaffold without relying on data similarity assumption. But Scaffold is not relying on this assumption, right?\n\n4. In Figure 2, NEOLITHIC is far slower than EF21-SGD, which somehow contradicts with the results shown in Huang et. al., 2022. Can the authors provide more details on the experimental settings on NEOLITHIC? How many iterations do NEOLITHIC run? Is accumulated gradient used? How does the total communication cost be counted in NEOLITHIC? Does NEOLITHIC converge slower than the other algorithms in terms of iterations (not in communication cost)?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> *Question 1.* In table 1, the authors claim that NEOLITHIC uses a large mini-batch, which may not be correct. While NEOLITHIC uses R times larger batch-size than EF21-SGD per iteration, it runs R times fewer iterations than EF21-SGD (see the NEOLITHIC algorithm in Huang et. al., 2022). On average, NEOLITHIC uses a normal O(1) mini-batch as EF21-SGD. \n\nAccording to Theorem 3 in [Huang et al, 2022], NEOLITHIC requires at each iteration a batch-size of order $\\frac{1}{\\alpha} \\log(G/\\varepsilon)$ (even in the deterministic case) in our notations. While the dependence on $G$ and $1/\\varepsilon$ are logarithmic, the dependence on $\\alpha = K / d$ can still result in a very large batch-size, especially when $K$ is small and the dimension $d$ is large. We are not aware if the analysis of NEOLITHIC can achieve $\\mathcal O \\left(\\frac{1}{\\alpha \\varepsilon^2} \\log(\\frac{G}{\\varepsilon}) + \\frac{\\sigma^2}{n \\varepsilon^4}\\right\\)$ sample complexity using the batch-size equal to one at each iteration (i.e., $R = 1$). \n\n>  *Question 3.* In line 182, the authors claim that the proof technique can help establish linear speedup for Scaffold without relying on data similarity assumption. But Scaffold is not relying on this assumption, right?\n\nWe thank the reviewer for pointing this out and admit that this sentence might be confusing. In fact, we meant to mention only Scaffnew/ProxSkip algorithm by Mishchenko et al, 2022 here. This remark relates to the corresponding limitation of Scaffnew in the stochastic setting, which is mentioned in the end of Section 5.1 of their work. That is although Scaffnew is provably faster than Scaffold in the deterministic case, their sample complexity in the stochastic setting does not have the linear speedup. We will edit this sentence accordingly in the revision. \n\n> *Question 4.* In Figure 2, NEOLITHIC is far slower than EF21-SGD, which somehow contradicts with the results shown in Huang et. al., 2022. Can the authors provide more details on the experimental settings on NEOLITHIC? How many iterations do NEOLITHIC run? Is accumulated gradient used? How does the total communication cost be counted in NEOLITHIC? Does NEOLITHIC converge slower than the other algorithms in terms of iterations (not in communication cost)?\n\nIt does not contradict the results from [Huang et. al., 2022] because they take the parameter $R = 4$ in their experiments. While we follow the theory from [Huang et. al., 2022, Theorem 3] and take $R \\approx 1 / \\alpha$ because the choice of $R = 4$ is not well justified. Although we admit that $R = 4$ can be a good practical choice, we want to avoid heuristics as much as possible. \n\nAll methods (including Neolithic) run the same number of iterations. In all methods, we calculate the number of sent bits in each iteration. This procedure is independent of the methods. \n\nWe have checked the convergence of Neolithic in terms of iterations. Neolithic converges **not** slower than other methods and has good performance w.r.t. # of iterations. This is the expected result because Neolithic sends $R \\approx 1 / \\alpha$ compressed vectors in each iteration.\n"}, {"review_id": "TlIgIjZ5ny", "reviewer": "Reviewer_naHZ", "summary": "This paper introduces a modification to the EF21-SGD algorithm by incorporating momentum, resulting in a new algorithm named EF21-SGDM. The innovative analysis accompanying this new method successfully addresses the challenges associated with EF21-SGD, reducing the sample complexity from $\\Omega(\\sigma^2/\\epsilon^2)$ to $\\mathcal{O}(\\sigma^2/(L\\delta_0)$. Importantly, EF21-SGDM operates without requiring an assumption of bounded gradient.", "questions": "The theoretical results suggest that $\\eta=\\mathcal{O}(1/T)$, but the experiment utilizes $\\eta=0.1$. Could the authors clarify the reasoning behind this discrepancy between theoretical and experimental parameters?", "limitations": "No.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper proposes a new algorithm for distributed settings with compressed gradient. The authors also provide an original analysis that delivers improved results, contributing substantially to the existing work.", "weaknesses": "Although the paper's sample complexity in each iteration number is independent of $\\varepsilon$, it still depends on the variance term, $\\sigma$. This dependence should be explicitly stated to ensure a comprehensive understanding of the algorithm. Furthermore, Algorithm 1 uses $B_{init}$, but the batch size remains consistent throughout the iterations. It may be more appropriate to avoid this term, considering the batch size does not vary.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> Although the paper's sample complexity in each iteration number is independent of $\\varepsilon$ , it still depends on the variance term, $\\sigma$. This dependence should be explicitly stated to ensure a comprehensive understanding of the algorithm. \n\nThe sample complexity of each iteration of our algorithms (EF21-SGDM and EF21-SGD2M) is $1$, since using one stochastic gradient is sufficient at each iteration at every node, see Theorems 2, 3 and 5. Our total sample complexities (see Corollaries 2 and 3) naturally depend on both $\\varepsilon$ and $\\sigma$. We report this dependence in all theorems, corollaries, tables and carefully compare the dependence on each quantity to the previous work, see lines 281-288 after Corollary 2.\n\n> Furthermore, Algorithm 1 uses $B_{init}$, but the batch size remains consistent throughout the iterations. It may be more appropriate to avoid this term, considering the batch size does not vary.\n\nOur equation (9) in the main Theorem 3 holds for any initial batch-size including $B_{init} = 1$, thus large initial batch size is not necessary for convergence. However, to make a fair comparison in the total sample complexities of EF21-SGD, EF14-SGD, EF21-SGDM and EF21-SGD2M, we distinguish between $\\delta_0$ and $\\Lambda_0$ (it could be that $\\delta_0 << \\Lambda_0$) and use a large initial batch size to make them of the same order. \n\n> *Question*. The theoretical results suggest that $\\eta = 1/T$, but the experiment utilizes $\\eta = 0.1$. Could the authors clarify the reasoning behind this discrepancy between theoretical and experimental parameters?\n\nAccording to Theorem 3, the best theoretical choice of $\\eta$ depends not only on the number of iterations $T$, but also on some unknown parameters such as $\\sigma$, $L$ and $\\delta_0$. Therefore, we resort to tuning the value of $\\eta$. We finetuned $\\eta$ from the set {$ 0.01, 0.1 $} on the independent dataset (w8a) before all our main experiments. We describe this procedure in Lines 312-313.  We also include an additional discussion regarding this in Appendix J. \n\n\n---\n\nWe believe we addressed all criticism raised. As we have shown, some of it was just based on a misunderstanding. We hope this might lead to a better score; thanks! We are ready to answer any further questions!\n"}]

Author rebuttal:

We thank the reviewers for their feedback and the overall positive evaluation of our work. We are glad that the reviewers appreciate that our studied problem is “**well motivated**”, the paper is “**well-written and easy to follow**”, the analysis is “**novel, comprehensive, solid**”, the assumptions are “**reasonable and standard**”, the improvement in rates is “**very encouraging and contributes substantially to the existing work**”. Reviewers hi3u and 5FHY also appreciate our **lower bound construction** for EF21-SGD and the **linear speedup** property of the proposed algorithms. 

At the same time, we took all the criticism seriously, and will soon upload a detailed response to each comment. As requested by several reviewers, we conducted additional experiments with deep neural networks and also tested the performance of the EF21-SGD2M method. We attach these results as a separate one page PDF file below. 

---
Due to the space limitation in the response to Reviewer Pi6q, we include here the description of the combination of our EF21-SGDM with EF21-BC algorithm (from [Fatkhullin et al., 2021]) to achieve sparse communication in both directions: from the server (master) to clients (nodes) and from clients (nodes) to the server (master). We denote by $\mathcal C_W$ and $\mathcal C_M$ contractive compressors at the clients and the master respectively. 

*Nodes:*
$$
 x^{t+1} = x^t - \gamma g^t ,
$$
$$
v_i^{t+1} = (1-\eta) v_i^{t} + \eta \nabla f_i(x^{t+1}, \xi_i^{t+1}) ,
$$
$$
c_i^{t+1} = \mathcal C_W ( v_i^{t+1} - \widetilde g_i^{t} ) , \quad \text{send } c_i^{t+1} \text{ to master, }
$$
$$
\widetilde g_i^{t+1} = \widetilde g_i^{t} + c_i^{t+1} , 
$$

*Master:*
$$
\widetilde g^{t+1} = \widetilde g^{t} + \frac{1}{n} \sum_{i=1}^{n} c_i^{t+1} ,  
$$
$$
b^{t+1} = \mathcal C_M (\widetilde g^{t+1} - g^t ) ,  \quad \text{send } b^{t+1} \text{ to nodes, }
$$

*Master and Nodes:*
$$
g^{t+1} = g^t + b^{t+1} .
$$

One can extend the convergence analysis of our EF21-SGDM variant to the above bidirectional scheme. For this, one should combine Lemma 7 and 8 from [Fatkhullin et al., 2021] with Lemma 2 and 3 in our work. 

Meta-review: The paper provides good theoretical contribution and the techniques are of sufficient interest. I recommend acceptance of the paper, though I also believe a more thorough experiments will further increase the strength of the paper.
Decision: Accept (poster)