EControl: Fast Distributed Optimization with Compression and Error Control
Authors: Yuan Gao
Rustem Islamov
Sebastian U Stich
Venue: ICLR 2024 poster (2024)
Keywords: Optimization
Federated Learning
Contractive Compression
Primary area: optimization

Abstract: Modern distributed training relies heavily on communication compression to reduce the communication overhead. In this work, we study algorithms employing a popular class of contractive compressors in order to reduce communication overhead. However, the naive implementation often leads to unstable convergence or even exponential divergence due to the compression bias. Error Compensation (EC) is an extremely popular mechanism to mitigate the aforementioned issues during the training of models enhanced by contractive compression operators. Compared to the effectiveness of EC in the data homogeneous regime, the understanding of the practicality and theoretical foundations of EC in the data heterogeneous regime is limited. Existing convergence analyses typically rely on strong assumptions such as bounded gradients, bounded data heterogeneity, or large batch accesses, which are often infeasible in modern Machine Learning Applications. We resolve the majority of current issues by proposing EControl, a novel mechanism that can regulate error compensation by controlling the strength of the feedback signal. We prove fast convergence for EControl in standard strongly convex, general convex, and nonconvex settings without any additional assumptions on the problem or data heterogeneity. We conduct extensive numerical evaluations to illustrate the efficacy of our method and support our theoretical findings.

Published as a conference paper at ICLR 2024
ECONTROL: FAST DISTRIBUTED OPTIMIZATION WITH COMPRESSION AND ERROR CONTROL
Yuan Gao Rustem Islamov Sebastian U. Stich Universität des Saarlandes, Universität Basel, SCISPA Helmholtz Center for Information Security [yuan. gao, stichi 0cispa. de, rustem. is islamov@unibas ch
ABSTRACT
Modern distributed training relies heavily on communication compression to reduce the communication overhead. In this work, we study algorithms employing popu- lar class of contractive compressors in order to reduce communication overhead. However, the naive implementation often leads to unstable convergence even exponential divergence due to the compression bias. Error Compensation (EC) is an extremely popular mechanism mitigate the aforementioned issues during the training of models enhanced by contractive compression operators. Compared to the effectiveness of EC in the data homogeneous regime, the understanding of the practicality and theoretical foundations of EC in the data heterogeneous regime is limited. Existing convergence analyses typically rely on strong assumptions such bounded gradients, bounded data heterogeneity, large batch accesses, which are often infeasible in modern Machine Learning Applications. We resolve the majority of current issues by proposing EControl, novel mechanism that regulate error compensation by controlling the strength of the feedback signal. We prove fast convergence for EControl in standard strongly convex, general convex, and nonconvex settings without any additional assumptions on the problem or data heterogeneity. We conduct extensive numerical evaluations illustrate the efficacy of our method and support our theoretical findings.
INTRODUCTION
The size of modern neural networks has increased dramatically. Consequently, the data required for efficient training is huge as well, and accumulating all available data into a single machine is often infeasible. Because of these considerations, the training of large language models (Shoeybi al. 2019), generative models (Ramesh et al., 2021 (022). and others (Wang et al.) 2020) is performed distributed fashion with decentralized data. Another quickly developing instance distributed training is Federated Learning (FI.) (Konečný et al.) 2016 Kairouz et al. 2019) where the goal is to train a single model directly on the devices keeping their local data private.
The communication bottleneck is main factor that limits the scalability of distributed deep learning training (Seide et al. 2014, Strom 2015). Methods that use lossy compression have been proposed as remedy, with great success (Seide et al. 2014] Alistarh et al. (017)). It has been observed that error compensation (EC) mechanisms are crucial to obtain high compression ratios (Seide et al. 2014 Stich et al.) 2018). and variants of these techniques (Vogels et al. 2019) are already integrated in standard deep learning frameworks such as PyTorch (Paszke et al. 2019 and been successfully used in the training of transformer models (Ramesh et al.) 2021).
These methods were primarily developed for data center training scenarios where training data is shuffled between nodes. This data uniformity was also limiting assumption in early analyses for distributed EC (Cordonnier) 2018 Stich & Karimireddy 2020). To make compression suitable for training beyond data centers, such as federated learning, it is essential take data heterogeneity (also termed client drift or bias) (Karimireddy et al.) 2020 Mishchenko et al.) 2019) into account. Mishchenko al. (2019) designed method for this scenario. but it can only support the restrictive class of unbiased compressors. It turned out, that handling arbitrary compressors is a challenge. A
"Equal contribution.

---

Published as a conference paper at ICLR 2024
line of work developed the EF21 algorithm (Richtárik al. 2021) that successfully handle the bias/drift, but cannot obtain a linear speedup in parallel training, i.c. the training time does not decrease when more devices are used for training.
One of the main difficulties in developing a method that simultancously combats client drift and maintains linear acceleration has been the complicated interaction between the mechanisms of bias and error correction. In this work, we propose EControl, a novel mechanism that can regulate error compensation by controlling the strength of the feedback signal. This allows us to overcome both challenges simultaneously. Our main contributions can be summarized as:
New Method. We propose novel method EControl that provably converges (i) with arbitrary contractive compressors, (ii) under arbitrary data distribution (heterogeneity), (iii) and obtains linear parallel speedup.
A Practical Algorithm. EControl does not need to resort to impractical theoretical tricks, such as large batch sizes or repeated communication rounds, but instead is a lightweight extension that can be easily added to existing EC implementations.
Fast Convergence. We demonstrate the convergence guarantees in all standard regimes: strongly convex, general convex, and nonconvex functions. In all the cases complexities are asymptotically tight with stochastic gradients. In the nonconvex case, the rate in the noiseless setting matches the known lower bound (He et al., (023). In the strongly convex and general convex settings, we achieve the standard linear and sublinear convergence respectively, with tight dependency on the compression parameter in the noiseless setting. To the best of our knowledge, our work is the first demonstrating that in strongly convex and general convex regimes without additional assumptions on the problem.
Empirical Study. We conduct extensive empirical evaluations that support theoretical findings and show the efficacy of the new method.
2 COMMUNICATION BOTTLENECK AND ERROR COMPENSATION
In our work, we analyze algorithms combined with compressed communication. In particular, consider methods utilizing practically helpful contractive compression operators.
we
Definition 1. We say that (possibly randomized) mapping C: RRd + R is a contractive compression operator for some constant 0 < S it holds
E [[((x) xx3] (1- |x|]
Vx E Rd
(1)
The classic example satisfying (T is Top-K (Stich et al. 2018). which preserves the K largest (in absolute value) entries of the input, and zeros out the remaining entries. The class of contractive compressors also includes sparsification (Alistarh et al. 2018 8 Stich et al. 2018) and quantization operators (Wen al., 2017: Alistarh et al.) 2017 7| Bernstein al. 2018 Horväth al. 2019). and many others (Zheng et al.) 2019:; Beznosikov et al. [2200] Vogels et al. 2019 Safaryan et al. 2022 Islamov al.) 2003). this section, we review related works on error compensation, with a focus on the works that also consider contractive compressors.
2.1 SELECTED RELATED WORKS ON ERROR COMPENSATION
The EC mechanism Seide et al. (014) was first analyzed for the single worker case in Stich al. (2018); Karimireddy et al. (2019). Extensions the distributed setting were first conducted under the assumption of homogeneous (IID) data, a constraint imposed either implicitly by assuming bounded gradients Cordonnier y Alistarh et al. (2088) or explicitly without the bounded gradient assumption Stich & Karimireddy (2020). Choco-SCa was designed for communication compression over arbitrary networks and analyzed under similar IID assumptions Koloskova et al. (2019) 2020a).
The analyses of distributed EC where further developed in Lian al. (2017): Beznosikov al.
(2020): Stich (2020).
The DIANA algorithm by Mishchenko et al. 2019 proposed solution for the heterogeneous data case, and introduced a mechanism that was able to account for the drift/bias on nodes with different data, but only when unbiased compressors were used. However, their result inspired many
2

---

Published as a conference paper at ICLR 2024
follow-up works that combined contractive compressors with their bias correction mechanism (which requires an additional unbiased compressor that doubles the communication cost of the algorithm per iteration), such as Gorbunov et al. 2020); Stich (2020); Qian et al. 20221b.
Recently, Richtárik et al. (2021) introduced EF21 that fully supports contractive compressors and presented strong analysis in the full gradient (i.e. noiseless) regime. Nevertheless, the main problem of EF21 is weak convergence guarantees in the stochastic regime, i.e. when clients have access to stochastic gradient estimators only. The analysis of EF21 and its modifications require large batches and do not have linear speedup with n. Moreover, they demonstrate poor dependency on the compression parameter 8. Zhao al. (2022) improves the dependency on the compression parameter ó in a nonconvex setting but still requires large batches. Recently, Fatkhullin et al. (2023) resolved those issues by introducing a momentum- based variant of EF21. They demonstrate asymptotically optimal complexity for nonconvex losses.
line of work studied accelerated methods with communication compression (Li al. 2020 Li Richtárik| [202 Qian et al.) la 2023 He et al. 2023), each with different additional requirements on the problem, the compressor class, or stochasticity and batch size of the gradient oracle. These methods show accelerated rates matching lower bounds in some regimes but are typically impractical due to those requirements and many parameter tuning.
2.2 EXISTING PROBLEMS WITH ERROR COMPENSATION
Below we list the main problems of existing theoretical results and highlight a historical overview of the main existing theoretical results in Table !
Additional Communication. Gorbunov et al. (2020): Stich (2020) modify the original EC mech- anism following the DIANA method. However, their approach requires an additional unbiased compressor. Such an idea allows for building a better sequence of compressed gradient estimators but with doubled per-iteration communication cost.
Strong Assumptions. Many earlier theoretical results for EC require strong assumptions, such as either the bounded gradient assumption (Koloskova et al. 2019 2020a) or globally bounded
dissimilarity assumption (Lian et al. 2017 Huang et al. 2022 He et al. 2023 & Li, 2023
Besides, Makarenko et al. (202)) amalyses EF21-based algorithm under bounded iterates assumption.
Large Batches. Fatkhullin et al. (002)) gives an example where EF21 fails to converge with small batch size. NEOLITHIC (Huang al. 2022 He et al.) 2023) matches lower bounds with large batch requirements combined with stage execution for hyperparameter tuning. These requirements make these methods less suitable for DL training. where small batches known to
improve generalization performance and convergence (LeCun et al. 2012 Wilson & Martinez 2003
Keskar al. 2017).
Suboptimal Convergence Rates. Current theoretical analysis of distributed algorithms combined with contractive compressors do not match known lower bounds in the nonconvex regime (Huang et al. 2022 He et al. 2023). Zhao et al. (2022); Fatkhullin et al. (2021) do not achieve a speedup in (u22))/Ftt
n asymptotic regime while in contrast Koloskova et al. a (2020a) has suboptimal rates in the low noise regime (e.g. full gradient computations). We are aware of only the works by Fatkhullin et al. (2023) and He et al. (2023), but the latter requires large batches at each iteration.
Missing a Practical Method for the Convex Regime. He et al. (2023) analyzed the accelerated NEOLITHIC in general convex and strongly convex regimes with large batch requirements. In fact, this method is mostly of a theoretical nature as the choice of the optimal parameters relies on the gradient variance at the solution, and it was shown to be slow in practice (Fatkhullin et al., 2023). To the best of our knowledge, there is no distributed algorithm utilizing only a contractive compression operator and provably converging in general convex and strongly convex regimes under standard assumptions.
In our work, we propose a novel method, which we call EControl, and push the theoretical analysis of algorithms combined with contractive compression operators further in several directions.
This assumption heavily restricts the class of functions and typically does hold in Federated Learning.
3

---

Published as a conference paper at ICLR 2024
Table 1: Theoretical comparison of error compensated algorithms using only contractive compressors for distributed optimization a heterogeneous setting. We omit the comparison in general convex regime since most of the works focus on strongly convex and general nonconvex settings. nCVX = supports nonconvex functions; sCVX = supports strongly convex functions. We present the convergence E [I (X < E in the nonconvex and B (x(x) f in the strongly convex regimes for specifically chosen Xou- Here Fo =
f (xo)
Algorithm
nCVX
SCVX
Scide et al.
EC
2014
LFio² ng
+
LFolo+(/VB)
V8g2/2
LFo ())
65
vi(o+c/v8)
pvd8
+
ju8
L (0)
Choco-So0 SGD
Linax Fao ne
Linay FoG. 023/2
L (h)
y Lmmaz Noz!/a
Ga/a
(b)
Koloskova et al.
22020a
66
417502173
EF21-SGD
LFa0" 2-
LRa (6)
Loa
L (c) ps
(alkhullin cl al. 2021
+
dz
EF21-SGD2M
LFG0 me=
2/10213 8775
+ LFotoVLFa (d)
x
(Fatkhullin et al. 2023]
This work
EControl
LFa net
+
84:372
LFea
LFa
oz
uun
a²
1182g772
TTa
pá
L
Lower Bounds
LFa ne?
LFoo
(e)
o² pon
L
(He et al.| [023]
(a) The analysis assumes gradient dissimilarity bound of local gradients 1, Ei= [V & C
[
Stich 2020)
(b) The analysis is done under the second moment bound of the stochastic gradients E [Ils"(x))] "] S G².
We emphasize that strongly
convex functions do not satisfy this ussumpption.
(c) This result requires the assumption that each batch size least 8-7 in nonconvex regime and
the strongly convex regime.
(d) The last term becomes de
LED the initial batch size is at least IPG
The unalysis is done under gradient disimilurity ussumption n. E
VV((() vx(o)] 2 Moreover, the result requires
large mini- haihheseees and performing 1/8 communication rounds per iteration.
(f) The result requires large chosen with an assumption that >D ( (x") Ill 6 is known.
and performing 1/8 communication rounds per iteration. Morcover, the optimal parameters
3 PROBLEM FORMULATION AND ASSUMPTIONS
We consider the distributed optimization problem
f(x) = 1 Σ f(() 1=1
= min XERd
(2)
where x represents the parameters of a model we aim to train, and the objective function f: Rd R is decomposed into n terms f;: Rd + R, E [n] == (1.....n). Each individual function fx(x = [f E.)] is loss associated with local dataset D, available to client i. We let x := arg min fxx).
We analyze the centralized setting where the clients are connected with each other through a server. Typically, the server receives the messages from the clients and transfers back the aggregated information. In contrast to many prior works, we study arbitrarily heterogeneous setting and do not make any assumptions on the heterogeneity level, i.e. local data distributions might be far away from each other. We now list the main assumptions on the optimization problem
First, we introduce assumptions on J and St that we use to derive convergence guarantees. Assumption 1. We assume that the average function f has L-Lipschitz gradient, and each individual function fs has Li-Lipschitz gradient, i.e. for all x,y E Rdd and E [n] it holds
[Vy()) - fx()) < L -iy-ly-- xIl.
[V [f(())l < L; lly - x||
We define a constant Σ= / Σー_ L? We note that most works derive convergence guarantees
with maximum smoothness constant Lixx == max4e|n] L; which can be much larger than L. Next, in some cases we assume y-strong convexity of f.
Note that the following chain of incqualities always hold: T. S T. S Tmax == maxigjn Tu-
4

---

Published as a conference paper at ICLR 2024
Algorithm 1 EC-Ideal
Algorithm 2 EControl
Input: Xg. c 14=00:
0a, h²
Vf((x"),
Input: Xp. e-= =0=02. hj gù. 7: 77 and C3
2:
3: fort= n Σ [= h
h,
2: he = > hj
2.... do
for f 1......... do
4: client side:
4: client side:
5:
compute g g' (xt
compute
g (x,)
6:
compute A Cs (ej
+ gi h
6: compute A = C (ne
+ gi hg)
7:
update ei11 e gi h -
update e e Bi h; A
8:
send to server A
8:
and h = h A
9:
server side:
9:
send to server A
10:
update X = Xx -hh
- A
10:
server side:
11: update X == Xt 7h;
2 Si AF
12:
and h h, + n Σ Di
Assumption 2. We assume that the average function f is p-strongly convex, i.e. for all x, y E R holds
f(x) 2 f(y) (Vf(y), - y) + 4. y11
We say that f convex it satisfies with μ
We highlight that need the strong convexity (convexity resp.) only of the average function f while individual functions fi do not have to satisfy it, and they can be even nonconvex. On top of that, in analysis we apply the strong convexity (convexity resp.) around x" only, thus, it is sufficient to assume that (4) holds for any and x = x". In this case, we say that a function is ju-ttrongly quasi-convex (quasi-convex resp.) around x see (Stich & Karimireddy 2020).
Finally, we make an assumption on the noise of local gradient estimators used by the clients.
Assumption We assume that we have access to a grudient orucle g (x): Rd - TRd for each local function Is such that for all E Rdd and i E [ni] it holds
E [x)] (x).
E [Ilg'(x) (x( o²
(5)
Note that mini-batches are also allowed, effectively dividing this variance quantity by the local batch size. However, we do not need to impose any restrictions on the (minimal) batch size and, for simplicity, always assume batch size of one.
EC-ldeal AS A STARTING POINT
To motivate some the key ingredients of main method, we start with a simple idea developed in an ideal setting, which shed some light on the nuances of the interactions between bias and етrоr correction. Assume for moment that we have access h fx*)x)). We can utilize this additional information to modify the original EC mechanism so that we only compress the difference between the current stochastic gradient gi and the h., See Algorithm 1 the highlight below:
A = Cc + g: h() 1 c g.
EC-Ideal update:
h A
It turns out that this simple trick leads to a dramatic theoretical improvement. Now we do not have to restrict the heterogeneity of the problem in contrast to the analysis of original EC Stich 2020). The
next theorem presents the convergence of EC-Ideal.
Theorem (Convergence of EC-ldeal), Let f IRd R p-strongly quasi-convex around x*, and each fü be L-smooth and convex. Then there exists a stepsize y 8/6L such that after most
T T=0 Jine
VLo
1V/be1/2
nd
5

---

Published as a conference paper at ICLR 2024
iterations of Algorithm 1 it holds (X - S E, where Your is chosen randomly from {xo.... .T) with probabilities proportional to - (++1))
We defer the proof to Appendix E Note that the output criteria (selecting random iterate) is standard the literature and for convex functions could also be replaced by a weighted average over all iterates that can be efficiently tracked over time (see e.g. |Rakhiin et al. 2011). EC-Ideal achieves very desirable properties. First, provably works for any contractive compression. Second, achieves optimal asymptotic complexity and the standard linear convergence when a² - O. All of these results are derived without enforcing data heterogeneity bounds. However, there are several drawbacks as well. First, EC-ldeal requires knowledge of [h: [xe[n] which is unrealistic in most applications. In
Appendix D we show that the algorithm, in fact, needs only approximations of (h', je(n) as input. Nonetheless, there is still an issue that EC-ldeal's convergence is only guaranteed under the convexity condition, which stems from the fact that we always need control the distance between V (xx, and V V. (x"). To overcome this issue, we need to build estimators of the current gradient, instead of the gradient the optimum, parallel maintaining the error term.
EControl is A SOLUTION TO ALL ISSUES
Inspired by the properties of EC-ldeal, we aim to build a mechanism that will progressively learn the local gradient approximations (see also Remark T5 in Appendix B). [tich (2020); Gorbunov et al. (2020) created learning process based on an additional compressor from a more restricted class of unbiased compression operators. To make their method work for any contractive compressor, we can replace the additional unbiased compressor with more general contractive one, but this leads to worse complexity in the low noise regime and more restriction on the stepsize. We refer the reader to Appendix [ for more detailed discussion. In this work, we propose a novel method, called EControl, that overcomes all of aforementioned issues by
building the error term and the gradient estimator with a single compressed message, enabling error compensation for the gradient estimator;
introducing a new parameter y) precisely control the error compensation and balance error compensation carried from the gradient estimator.
We summarize EControl in Algorithm 2 and highlight the key ingredients as follows:
A = Cn + gi h²) e = e + gi
EControl update:
h A
h4 h² + A
Fusing the error and the gradient estimator updates improves the algorithm's dependency on σ² and but also enables the gradient estimator to carry some level of the error information. This brings forth the challenge of balancing the strength of the feedback signal, and we introduce the 1) parameter obtain finer control over the error compensation mechanism. This new parameter brings additional flexibility and allows us to stabilize the convergence of EControl. The effect of such a parameter in the context of the original EC mechanism without gradient estimator might be of independent interest. We observe in practice that Algorithm with 7) = 1 is unstable and sensitive to the choice of initialization, which we illustrate in Appendix C.2 with a toy example. This highlights the importance of the finer control over EC that y enables. We refer the interested readers to Appendix C.1 for more detailed discussion on the importance of n from a thcoretical perspective. In Appendix C.3 we also discuss the connection between EControl and EF21 when 1j + 0. A similar idea of weighting error terms appeared in Abdi & Fekri (2020); al. 2023). However, their algorithm is based on the original EC.
THEORETICAL ANALYSIS OF EControl
We move to theoretical analysis of EControl. Below summarize the convergence properties of Algorithm in in all standard cases. We start with the convergence results in the strongly quasi-convex regime.

---

Published as a conference paper at ICLR 2024
Theorem 2 (Convergence of EControl for strongly quasi-convex objective). Let f be p-strrnglyy quasi-comse around x" and L-smooth. Let each fr be L.-shhhth. Then for 17= có (where c is an absolute constant specify in the proof), there exists a S O1/2 such that after most
0²
VL
I μ
T=
LIME
162e112
ierattions of Algorithm 2 holds E (x(m)) [*] S where Xou is chosen randomly from (xo...... , with probabilities proportional to 2) -
The asymptotic complexity of EControl in this regime with stochastic gradient matches the lower bound Q yune up log term, as opposed to previous works (Fatkhullin et al. 2021 Zhao et al. 2022). As we can see, the first term linearly improves with n, similar convergence behavior of distributed SGD. Moreover, EControl achieves standard linear convergence and desired inverse linear dependency on the compression parameter å in the noiseless setting. Next, we switch to general convex setting.
Theorem (Convergence of EControl for quasi- quasi-convex objective). Let f be quasi- consi-coovex around x' and L- L-smooth. Let each fs be L,-smooth. Then for 1j = có there exists r S O(8/L) such that after at most
Roo NE²
VLRgo
LRo
T ==
+
gg3/
de
iterations of Algorithm 2 it holds E (X - [*] where Ro l|xo x11 2 and Xour is chosen uniformly at random from X, E (X0,...,TT)
Similar the previous case, the first enjoys a linear speedup by the number of nodes. We achieve standard sublinear convergence and a desired inverse linear dependency on ó in the noiseless regime.
Theorem 4 (Convergence of EControl for nonconvex objective). Let f be T-smooth, and each fü be L-smohthh. Then for 1) cB there exists y S O6/II) such that after at most
LFo02
LFoo
LFo
T o
+
+
nE²
82g3/2
8z
iterations of Algorithm 2 holds E [|V (Xout) uniformly at random from Xx {xo..... ).).
8, where Fo = f(xo) -f* and Xost is chosen
The complexity of EControl in both asymptotic and noiseless regimes matches known lower bounds (He al., (2023) for nonconvex functions that are derived under much stronger assumptions. We achieve these results without any theoretical restrictions, such as large batch sizes or repeated commu- nication rounds, making it easy to deploy in practice as extension to existing EC implementations.
7 EXPERIMENTS
In this section, we complement our theoretical analysis of EControl with experimental results. We corroborate our theoretical findings with experimental evaluations and illustrate the practical efficiency and effectiveness of EControl in real-world scenarios.
7.1 SYNTHETIC LEAST SQUARES PROBLEM
First, we consider the least squares problem designed by Koloskova et al. (2020b). For each client i, fx() = || || b,ll², where A, = 2 Ia and each b, is sampled from (0, & Ia) for some parameter (. The parameter Ç controls the gradient dissimilarity of the problem. It's easy see that
"Note that the stepsize can depend on e. Here we use the notation S (6//2) to denote that the stepsize satisfy 7 G. for absolute constant specified the proof.
7

---

Published as a conference paper at ICLR 2024
102
Clients
100
Clents
10-2
R 1100
100
EContrel Compressed SGD
6
10
10 Bits
10
5000 Iterations
10000
Figure The comparison of Compressed-SGD, EC. and EControl. n 5, 300, Ç 50 and σ = 10. We apply Top-K compressor with K/a- 0.1. Stepsizes were tuned for each setting. X-axis represents the number of bits sent. Compressed- SGD (without error compensation) does converge and EControl slightly outperforms classic EC.
Figure 2:
The behavior of EControl with different
numbers of clients where df 200, ( 100, 50. We apply Top-K compressor with X/2 0.1. The stepsize is fixed y IDT 0.001 for the purpose of illustration. EControl exhibits clear linear speedup by n, the number clients, which verifies the linear parallel speedup property of EControl.
10
100
10
10
10-2
100-
210-
fori
10
10
500
503
10-
102
10 10-6
10a
104
10
10-6
10a
10
109
Figure 3: Comparison of mini-batch SGD, EC, and EControl for vairous problem parameters where = 5, 300 a 10. apply the Top-K K compressor with K/a = 0.1. Stepsizes were tuned each setting, X-axis represents the number of bits sent. EControl is not affected by the data heterogeneity parameter and is superior over SGD in terms of the number of hits sent (roughly hy factor of 4/x = 10, as expected from theory).
when Ç - O, (x( = 0, Vi. We add Gaussian noise to the gradients to control the stochastic level x² of the gradient. In Figure one can see that simply aggregating the compressed local gradient without error compensation (termed Compressed SGD (Khirirat et al. 2018 Alistarh et al. 2018) does not lead to convergence, while EControl and EC do. This result shows the need to use EC to make the method convergent. Further, we use this simple synthetic problem to demonstrate some off the key features of EControl:
Increasing the number of clients. In Figure 2 we investigate the effect of the number of clients the complexity of EControl. Crucially, the theory predicts that EControl achieves a linear speedup in terms of the number of clients when using stochastic gradient. In experiment, stepsize and investigate the error that EControl converges to. We see that as the number of clients doubles, the error that EControl oscillates around is roughly divided by half. This confirms theoretical prediction of the linear speedup.
fix a small
Independence from gradient dissimilarity. In Figure 3 we see that EControl is not affected by the gradient dissimilarity parameter Ç and its complexity stays stable across the three figures. On the other hand, the original EC suffers from the increasing Ç, taking longer converge o²
increases. Moreover, as Theorem predicts, the O june term is dominant, and the performance of EControl
(in terms of the number of bits sent) is superior over that of SGD with batch size n. The stepsizes fine-tuned over (5 x 10-5 10 4 4.5 10 10 10 1.101,, }, and for EControl we fine-tune n over (10-3,5 5 x 10 30 10-2.5 5. x 1 10-1). As increases, the performance of EControl is not affected, while the performance EC deteriorates.
7.2 LOGISTIC REGRESSION PROBLEM
Next, we consider the Logistic Regression problem for multi-class classification trained on MNIST dataset (Deng, 2012) and implemented in Pytorch (Paszke et 2019). First, we split 50% of the dataset between 10 clients according to the labels (the data point with i-th labels belongs to client i + 1). The rest of the data is distributed randomly between clients. Then, for each client, we divide the local data into train (90%) and test (10%) sets. Such partition allows make the problem
8

---

Published as a conference paper at ICLR 2024
Mal
Tost Rccurccycyyy
Trai
Epochs
Epochs
Figure 4: The comparison of EF21, EF21-SGDM, and EControl with fine-tuned parameters for Logistic
Regression problem on MNIST dataset.
Mill
aril
Accuraty
Accraay
Bann Lonn
12
Epochs
Epochs
Epochs
Epochs
Resnet18
(b) VGG13
Figure 5: The comparison of EF21, EF21-SGDM, and EControl with fine-tuned parameters for training Deep Learning models on Cifar-10 dataset.
more heterogeneous. compare the performance of EControl, EF21-SGDM and EF21. For all d. We fine-tune the stepsizes of the methods methods, we use Top-K compression operator with K" = TO fine-tune 77 parameter for EControl over {0.2, 0.1, 0.05), and for EF21-SGDM we set 1) = 0.1 according to (Fatkhullin et al. 2023). We choose the stepsizes that achieve the best performances
over [1, 10-1 10-2, 10-3). Moreover,
the train set such that the test loss does not diverge. The results are presented in Figure 4 Note that the communication cost of the methods per iteration is the same, therefore, the number of epochs is proportional to the number of communicated bits.
We observe that EControl has the fastest convergence in terms of training loss. The same behavior is demonstrated with respect to test accuracy. Nevertheless, the test accuracy difference for all methods is within 1 percent.
7.3 TRAINING OF DEEP LEARNING MODELS
Finally, we consider the training Deep Learning models: Resnet18 (He al. 2016) and VGG13 (Simonyan & Zisserman 2015). The implementation is done in Pytorch (Paszke et al. 2019). We
run experiments on Cifar- 10 (Krizhevsky al. 2014) dataset. The dataset split across the clients is the same as for the Logistic Regression problem half is distributed randomly, and another half is portioned according to the labels. For the compression, we utilize Top-K compressor with K 0.1. We fine-tune the stepsizes over the set (1, 0.1, 0.01) for EControl, EF21-SGDVV and EF21 and select the best stepsize on test set. For EControl and EF21-SGDM we set v = 0.1.
According to the results in Figure 5a all methods achieve similar test accuracy, but EF21 has more unstable convergence with many ups and downs. EControl achieves a better stationary point as the training loss is smaller than for the other model; see Figure 5b) The training with EControl allows to reach stationary point with a smaller training loss. Moreover. EControl outperforms other methods from test accuracy point view: gives slightly better test accuracy than EF21 and considerably higher accuracy than EF21-SGDM.
methods. Similar results are demonstrated for VGGI3
8 DISCUSSION
In this work, we propose novel algorithm EControl that provably converges efficiently in all standard settings: strongly convex, general convex, and nonconvex, with general contractive compression and without any additional assumption on the problem structure, hence resolving the open theoretical problem therein. conduct extensive experimental evaluations our method and show its efficacy in practice. Our method incurs little overhead compared to existing implementations of EC, and we believe is an effective and lightweight approach to making EC suitable for distributed training of large machine learning models, especially when also using the standard momentum mechanism for reducing the variance of the stochastic gradients deep learning training. However, the theoretical analysis of this extension is outside the scope of this paper, and will leave it for future work.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
YG/SS acknowledge partial funding from Google Scholar Research Award.
REPRODUCIBILITY STATEMENT
We provide source code as part of the supplementary material which allows to reproduce Deep Learning and synthetic least squares experiments. Additionally, for our theoretical results, we offer clear explanations of any assumptions in the main paper and complete proof of all statements in the appendix.
REFERENCES
Afshin Abdi and Faramarz Fekri. Quantized compressive sampling of stochastic gradients for efficient communication in distributed deep learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 3105-311 3112, 2020.
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. QSGD: Communication- efficient SGD via gradient quantization and encoding. In Proceedings of Advances in Neural Information Processing Systems, pp. 1709-1720, 2017.
Dan Alistarh, Torsten Hoefler, Mikael Johansson, Nikola Konstantinov, Sarit Khirirat, and Cédric Renggli. The convergence of sparsified gradient methods. In Proceedings of Advances in Neural Information Processing Systems, 2018.
Jeremy Bernstein, Yu-Xiang Wang. Kamyar Azizzadenesheli, and Animashree Anandkumar. signsgd: Compressed optimisation for non-convex problems. In International Conference Machine Learning, pp. 560-569. PMLR, 2018.
Aleksandr Beznosikov, Samuel Horváth, Peter Richtárik, and Mher Safaryan. On biased compression for distributed learning. Journal on Machine Learning Research, 2020.
Jean-Baptist Cordonnier. Convex optimization using sparsified stochastic gradient descent with memory. Technical report, 2018.
Li Deng. The mnist database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine, 2012.
Ilyas Fatkhullin, Igor Sokolov, Eduard Gorbunov, Zhize Li, and Peter Richtárik. E121 with bells & whistles: Practical algorithmic extensions of modern error feedback. arXiv preprint arXiv: 2110.03294, 2021.
Ilyas Fatkhullin, Alexander Tyurin, and Peter Richtárik. Momentum provably improves error feedback! arXiv preprint arXiv: 2305. 2023.
Eduard Gorbunov, Dmitry Kovalev, Dmitry Makarenko, and Peter Richtárik. Linearly converging error compensated sgd. In Proceedings of Advances in Neural Information Processing Systems, 2020.
Kaiming He. Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2016.
Yutong He, Xinmeng Huang, Yiming Chen, Wotao Yin, and Kun Yuan. Lower bounds and accelerated algorithms in distributed stochastic optimization with communication compression. arXiv preprint arXiv: 2305.07612, 2023.
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 arXiv: 1905.10988, 2019.
10

---

Published as a conference paper at ICLR 2024
Xinmeng Huang, Yiming Chen, Wotao Yin, and Kun Yuan. Lower bounds and nearly optimal algorithms in distributed learning with communication compression. In Proceedings of 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. Transactions on Machine Learning Research, 2023.
Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista A. Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, Rafael G. D'Oliveira, Salim EI Rouayheb, David Evans, Josh Gardner, Zachary Garrett, Adrià Gascón, Badih Ghazi, Phillip B. Gibbons, Marco Gruteser, Zaïd Harchaoui, Chaoyang He. Lie He, Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi, Tara Javidi, Gauri Joshi, Mikhail Khodak, Jakub Konečný, Aleksandra Korolova, Farinaz Koushanfar, Sanmi Koyejo. Tancrède Lepoint, Yang Liu, Prateek Mittal, Mehryar Mohri, Richard Nock, Ayfer Özgür, Rasmus Pagh, Mariana Raykova, Hang Qi. Daniel Ramage, Ramesh Raskar, Dawn Song, Weikang Song, Sebastian U. Stich, Ziteng Sun, Ananda Theertha Suresh, Florian Tramèr, Praneeth Vepakomma, Jianyu Wang. Li Xiong, Zheng Xu. Qiang Yang. Felix X. Yu, Han Yu, and Sen Zhao. Advances and open problems in federated learning. arXiv preprint arXiv: 1912.04977, 2019.
Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian Stich, and Martin Jaggi. Error feedback fixes signsgd and other gradient compression schemes. In Proceedings of the 36th International Conference on Machine Learning (ICML 2019), 2019.
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank J. Reddi, Sebastian U. Stich, and Ananda Theertha Suresh. SCAFFOLD:: Stochastic controlled averaging for on-device federated learning. Proceedings of International Conference on Machine Learning (ICML). 2020.
Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Peter Tang. On large-batch training for deep learning: Generalization gap and sharp minima. In Proceedings of International Conference on Learning Representations, 2017.
Sarit Khirirat, Hamid Feyzmahdavian, and Mikael Johansson. Distributed learning with compressed gradients. arXiv preprint arXiv: 1806.06573, 2018
Anastasia Koloskova, Sebastian Stich, and Martin Jaggi. Decentralized stochastic optimization and gossip algorithms with compressed communication. In Proceedings of the 36th International Conference Machine Learning, 2019.
Anastasia Koloskova, Tao Lin, Sebastian Stich, and Martin Jaggi. Decentralized deep learning with arbitrary communication compression. In Proceedings of International Conference on Learning Representations, 2020a.
Anastasia Koloskova, Nicolas Loizon, Sadra Boreiri, Martin Jaggi, and Sehastian Stich. A unified the- ory of decentralized sgd with changing topology and local updates. In Proceedings of International Conference Machine Learning, pp. 5381-5393. PMLR, 2020b.
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 Proceedings of NIPS Private Multi-Party Machine Learning Workshop, 2016.
Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. Cifar-10 10 dataset. 2014.
Yann LeCun, Leon Bottou, Genevieve Orr, and Klaus-Robert Muller. Efficient backprop. Neural Networks: Tricks of the Trade, Springer-Verlee 2012.
Bingcong Li, Shuai Zheng, Parameswaran Raman, Anshumali Shrivastava, and Georgios B. Giannakis. Contractive error feedback for gradient compression. arXiv preprint arXiv: 2312.08538, 2023.
Xiaoyun Li and Ping Li. Analysis of error feedback in federated non-convex optimization with biased compression: Fast convergence and partial participation. In Proceedings of the 40th International Conference Machine Learning, 2023.
11

---

Published as a conference paper at ICLR 2024
Zhize Li and Peter Richtárik. Canita: Faster rates for distributed convex optimization with communi- cation compression, 2021.
Zhize Li, Dmitry Kovalev, Xun Qian, and Peter Richtárik. Acceleration for compressed gradient descent in distributed and federated optimization, 2020.
Zhize Li, Hongyan Bao, Xiangliang Zhang, and Peter Richtárik. Page: A simple and optimal proba- bilistic gradient estimator for nonconvex optimization. In Proceedings of the 38th International Conference on Machine Learning (ICML 2021), 2021.
Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsieh, Wei Zhang, and Ji Liu. Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent. In Proceedings of Advances in Neural Information Processing Systems (NIPS), 2017.
Maksim Makarenko, Elnur Gasanov, Rustem Islamov, Abdurakhmon Sadiev, and Peter Richtárik. Adaptive compression for communication-effiiii distributed training. Transactions on Machine Learning Research, 2023.
Konstantin Mishchenko, Eduard Gorbunov, Martin Takáč, and Peter Richtárik. Distributed learning 2019.
with compressed gradient differences. arXiv preprint
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary VeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high beggh-eeformancc deep learning library. In Proceedings of Advances in Neural Information Processing Systems 32, 2019.
Xun Qian, Hanze Dong, Peter Richtárik, and Tong Zhang. Error compensated loopless svrg, quartz, and sdea for distributed optimization. arXiv preprint arXiv:2109. 2021a.
Xun Qian, Peter Richtárik, and Tong Zhang. Error compensated distributed sgd can be accelerated. In Proceedings of Advances in Neural Information Processing Systems, 2021b.
Xun Qian, Hanze Dong, Tong Zhang, and Peter Richtárik. Catalyst acceleration of error compen- sated methods leads to better communication complexity. In Proceedings of 25th International Conference Artificial Intelligence and Statistics, 2023.
Alexander Rakhlin, Ohad Shamir, and Karthik Sridharan. Making gradient descent optimal for strongly convex stochastic optimization. arXiv preprint arXiv: 109,567, 2011.
Aditya Ramesh, Mikhail Pavlov, Gabriel Goh, Scott Gray, Chelsea Voss, Alec Radford, Mark Chen, and Ilya Sutskever. Zero-shot text-to-image generation. In International Conference on Machine Learning, pp. 8821-8831. PMLR, 2021.
Aditya Ramesh, Prafulla Dhariwal, Alex Nichol, Casey Chu, and Mark Chen. Hierarchical text- conditional image generation with clip latents. 2022.
Peter Richtárik, Igor Sokolov, and Ilyas Fatkhullin. Ef21: A new, simpler, theoretically better, and practically faster error feedback. In Proceedings of Advances in Neural Information Processing Systems, 2021.
Mher Safaryan, Rustem Islamov, Xun Qian, and Peter Richtarik. FedNL: Making Newton-type methods applicable to federated learning. In Proceedings of the 39th International Conference on Machine Learning, 2022.
Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu. 1-bit stochastic gradient descent and its application to data- partllaaallll distributed training of speech dnns. In Proceedings of 15th annual conference of the international speech communication association. 2014.
Mohammad Shoeybi, Mostofa Patwary, Raul Puri, Patrick Le Gresley, Jared Casper, and Bryan Catan- zaro. Megatron-Img Training Millti-illionn parameter language models using model parallelism. arXiv preprint arXiv: arXi:: 1909 08053, 2019.
12

---

Published as a conference paper at ICLR 2024
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. Proceedings of International Conference on Learning Representations, 2015.
Sebastian U. Stich. On communication compression for distributed optimization on heterogeneous data. arXiv preprint arXiv: 0209.0 2020.
Sebastian Stich and Sai Praneeth Karimireddy. The error-feedback framework: Better rates for sgd with delayed gradients and compressed updates. Journal of Machine Learning Research, 2020.
Sebastian U Stich, Jcan-Baptiste Cordonnier, and Martin Jaggi. Sparsified sgd with memory. In Proceedings of Advances in Neural Information Processing Systems, 2018.
Nikko Strom. Scalable distributed DNN training using commodity GPU cloud computing. In Proceedings of Interspeech 2015, 2015.
Thijs Vogels, Sai Praneeth Karimireddy, and Martin Jaggi. PowerSGD: Practical low-rank gradient compression for distributed optimization. In Advances in Neural Information Processing Systems 32, 2019.
Meng Wang, Weijie Fu, Xiangnan He, Shijie Hao, and Xindong Wu. survey on large-scale machine learning. IEEE Transactions on Knowledge and Data Engineering, 2020.
Wei Wen, Cong Xu, Feng Yan, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Temgrad: Ternary gradients to reduce communication in distributed deep learning. Advances in neural information processing systems, 30, 2017.
Randall Wilson and Tony Martinez. The general inefficiency of batch training for gradient descent learning. Neural Networks, 2003.
Haoyu Zhao. Boyu Li, Zhize Li, Peter Richtárik, and Yuejie Chi. BEER: Fast So(1/t)S rate for decentralized nonconvex optimization with communication compression. In Proceedings of Advances in Neural Information Processing Systems, 2022.
Shuai Zheng, Ziyue Huang, and James Kwok. Communication-effccenn distributed blockwise momentum sgd with error-feebback. Advances in Neural Information Processing Systems, 32, 2019.
13

---

Published as a conference paper at ICLR 2024
A USEFUL LEMMAS AND DEFINITIONS
In this section, we state the important notations and useful lemmas that we use in our convergence analysis. We use the following notation throughout the proofs
P. = E[xx)) - f*,
and
E
(8)
n
For shortness, all our proofs we use the notation
g g g
S
e,
and
h
h
(9)
Besides, we additionally introduce the sequence of virtual iterates which are defined as follows
Xn =
Xo:
R =
Σ
(10)
T 1=1
Performing simple derivations we get the link between real and virtual iterates Algorithm
(11)
In addition to the notations introduced inEquation 1 we define
X₁ = E [||x x=]]
(12)
Finally, we introduce another quantity that bounds the size of the compressed message:
H.
1
||net + gi --lll"]]]
(13)
n
The following lemmas were taken from other works (as indicated) and we omit their proof. Lemma 1 (Lemma from Stich & Karimireddy (2020)). Assume f is L-smooth and p-strongly
quasi-convex. Let the sequences {x:), (oite())) be generated by Algorithm 2 If S at then
X (1 -1-
7p 1
2
F. 2 +3 E..
X,
(14)
The descent lemma in Fe taken from (Stich & Karimireddy 2020
Lemma (Lemma 9 from Stich & Karimireddy (2020). Assuming that f is L-smooth, and x and e, are generated by Algorithm then
Lo²
F.11 S. EE [xxx))
E,
(15)
2n
For the sake of completeness, first lemma is used in order to derive convergence guarantees in the strongly convex case.
list two summation lemmas from (Stich) 2020) without proofs. The
Lemma 3 (Lemma 25 from Stich 20200). Let (rebeza and (st be sequences of positive numbers satisfying
T & (1 min(),,
Bys, C-² + D.3
(16)
for some positive constants A, B > 0, D, 2 0, and for constant stepsize <>> for 2 0, and for parameter F
< 1. Then there exists a constant stepsize 7 S E such that
B
wist
min { {A,
F 7
rr+1 < r E
A
exp
min
A F F
(T
+1)
WT
0=0
2C In
Dln²T A2 + 1)²
A(T + 1)
for w. (1 (y,, -(++))
(t+1), WT = Et Wt. and
A + 1)²
A (T + 1)3
T := max
exp((). min
C
D
14

---

Published as a conference paper at ICLR 2024
Remark 4 (Remark 26 from Stich 2020)).
Lemma established bound of the order
δ ro
A E
exp
min
(
A F (r)
C
D
AT
A2T
that decreases with ensure that this expression is smaller than 8,
Ō c
VD
F
= -0
VD
E
+
log
+
log
+ +
AE
AVE
F
A
AE
AVE F A
steps are sufficient.
The second lemma shows the convergence rate in the nonconvex convex settings.
Lemma 5 (Lemma 27 from Stich 2020)). Let frehe2o and {sy322 be sequences of positive numbers satisfying
T++1 S - By8, + Cy² + Dy?,
(17)
for some positive constants A, B > D, 0, and for constant stepsize 0 < I for 2 0, and for parameter < F < 1. Then there exists a constant stepsize 7 S t such that
B
T
8t 1 T
Ero
2D1/3
To T+1
2/3
+2
Cro
1/2
(18)
T+1
+1
T ++11
Remark 6 (Remark 28 from Stich 2020 ) To ensure that the right-hand side of
188 is smaller than
8 >>
Cro 62
Vro
Fro
T ==
+
+
g3/2
8
steps are sufficient.
B MISSING PROOFS FOR EControl
In this section we prove Theorem Theorem and Theorem 4
B. STRONGLY CONVEX SETTING
We start with the strongly convex case setting. First, we bound the distance between two consecutive iterates.
Lemma 7. Let of be L-smooth, then:
[|x++1 -x,11
x1|?]] 522
(2(
2(1 - -8)H, + 4 E, + 4LF, +
20
(19)
15

---

Published as a conference paper at ICLR 2024
Proof.
||x++1 - x1|?] -x11=
h + A,1l2]
722
=
E
A n/; - -g + h, + r/c + ge
2E
| 11; 8r + hr ||
+ 2E
|1,ee + 8:112]
(18)
20
2E
| n/c,
Bt + h1p
+ 2B
||ne + vf(xx))11
(w))
2
E
||
ne!
g + h;l
+ 4n
E
[|e:1|]]
iml
20²
4E
f |1
+
n
(50)
2(1 8)
|| + g²
h([l²]
417
Σ
|
1=1
==1
20
4LE -x)
where in (i) - (iii) we use Young's 's inequality; in (di) we use Assumption and in (iv) we use the definition of the compressor, L-smoothness and convexity.
The next lemma gives the descent of Eg.
Lemma 8. For any O we have:
E1+1 S (1+ - 2 + a ")((1 H)
(20)
Proof.
hf -=ll"
Es41
e + g:
n
1 ) Σ
|| Iee gi hτ - -b?? + (1+ aa)(1 (1) =,
(1+a*
E
n im1
(#)
< (1+a ))
5)
Σ
E Il + h:ll"] (1 a) - =
i=1
(1+ (1 E
where in (1) we use Young's 's inequality, and in (ii) we use the definition of the compressor.
Now we give the descent of He.
Lemma 9. Let I be L-smooth and each be Li-smooth. Let for some k 2 andd
5
4k
32/2L"
Then we have:
5
883
128I2228
128
L
Hat <
+
+
E, +
Fe
32
b444
k242
8
+
+
(21)
5
16

---

Published as a conference paper at ICLR 2024
Proof. We unroll the definition of H(+1
H1t1 =
1
E || + gi+1 - -1/
n =
1
||1vef + +ng! .//h/ n/ h - A + tg 11]
E
n2
(
(1+ 31)
1
Σ
n
E ||net + (1+ (L + n) -1+ 4:
71
+ +1+ 3T -
E ||| [1si s:l1
(0)
(1+ (1)
- Σ E
mee + (1 + +ngg - (1 + n)b - (1 + 4;1
+ +1(1+ + 8T
Σ
[ [x(()))) + +4(1+ + 372
7
(60)
S
1 (1+ (1)
E
||nvet + (1 + n) - (1 + n))h (1 + 1 ا 1:1
71
+ 2(1 87 2 ||xx+1-
4(1 + 3
(22)
where in (1) we use Young's ' incquality, in (ti) we use assumption 5 and in (izi) we use smoothness of fü. Now we consider the first term in the above:
ΣΣ B nei + (1 + n)gi - (1 + n)h; m)+m)h; - (1 (1+11) m)
(
+ +n) I!ne + g -hi - =:1" + +11 +1+ )n')n"E Ee
(0)
(1
+ 7) 8)H, + (1+ (1'
where in (i)
we use Young's 's inequality, and in (it) we use the definition of the compressor. Putting it
back in 22 we have:
H4t S (1++1)(11 (1) + 21 (1+ 55 )n EE,
+ +111+ + T.2 [|xx+] - x, [2] +
By Lemma we can substitute E
||xc+] 1x--xx-- x.1l²] and get:
H4t I
(1+ + -2) + .)) - 5)H, + (1 + 3:) + "n Es
2 + 37 )832 (2(1-6) - 5) + 4n7 E, + +LF,, + 20
+4(1+37))0
= [1+ + ( ()
He
+ [1+ +++)))(++ + E.
+ 8(1 + + 4(1 [(1 +T + 4(1 + BT 122 02.
Since 17
5 4h for some k 2 1, we must have:
(1 (1+m) (1+1)(11- 6) $ 5
4'
17

---

Published as a conference paper at ICLR 2024
Let us choose B1
16-26
5
and
B2
8-26
5
get:
8
8ny +
128I2
Hat1 S
1
+
He +
Er
16
128L L
64
1 L2
P.
0²
n
8
64T,22
85
128T,320
+
H +
E
16
h444
k.42
L
64
T2222
F
1+
0².
n
If y 32//E"
8 then:
883
12882928
H141 I
[
H1 +
+
Ex
32
kd41
k242
1
64
I272
F2 +
1+
8
8
Finally, we consider the Lyapunov function V = Xx + aH, + bE, where constants and are set as
follows: b = 48kLT" a 512kh where k will be set later.
Lemma 10. Let J be L-smooth and p-strongly quasi-convex around x", and each Si be Le-smooth. 6. and 7 S 3200 then we have
Let 1) 200
Mo+1 S (1-min min
Tp 8
1)
v. FF 2 02 3 Lo2
(23)
8850
84
n
Proof. With v k(4-25) we set a 85-25 in Lemma 8 and get
8
8k He
E
E.
8k
5
We can put the link between the real and virtual iterates and get
and the descent lemma for X₃ together
L 1-1
(1
7/1
X₂
7
F
3 E, T² +
2
2
8
85
128I2120
128i2L72
+
1
H +
+
Fy +
F
32
k444
k242
64
2
[(
8k E,
+
1+
0²
+
+
H
5
8k:
8
Rearranging the terms we continue follows
7/1
5
8kb
V
<
X,
+
+
oH,
2
32
da
8
3
3
a
883
128
+
+
+
bEi
8k
b
b
h:44
1242
128
L
2
0²
64a
I2g²
F. +
F.
+
1
o2.
2
5
18

---

Published as a conference paper at ICLR 2024
Now set 7 32v2kL
and then get:
1+1 1 (1
7/14
(1- 6
8kb
8
8'a
X +
+
aH; +
+
bR.
2
32
da
8k:
b
16k
7 Ft
128 Ly
a
F.
+
20
64a
1
0..
2
6
Let 48kLy" 5
and a
512kb 82
then for the coefficient next to He have
6 8kb
8
+
S
32
da
64
For the coefficient next to E, term we have
8
3L1
8
8
328
+
$
8k
b
16A46
16k
k3
For the coefficient F, term have
128L
La
7 3r
5
4k.2
Finally, for the coefficient to o² term we have
64a
S 7.3 10
1
8
84
Therefore, combining all together and setting
100, we get:
11 - (1
7/14
X, +
(1
8
aHi +
1
δ
bE:
2
64
8850
Y Fe 72
02
+ +
10
Lo²
n
84
7/4
8
22
473
15310"
Lo2
min
8850
n
84
Now we give the precise statement of Theorem
Theorem 5. Let be j--strongly quasi-convex around and L-sootth. Let each fo be L.-smooth. 5 Then for 11 106 there exists 7 I 3200v2L such that after at most
o2
VLo
I
T T
+
Juns
182g112
1
iterations of Algorithm 2 holds E (X (xa.... } with probabilities proportional to 24)
f*] E, where Xou is chosen randomly from X; -(++))
Proof. The claim of theorem 5 follows from Lemma 10 Lemma 3 and remark from Stich 2020).
Note that by the initialization, we have v ||x0
x" x² Also note that by the choice parameters
2
8850
B.2 CONVEX SETTING
We switch the convex regime. The considered setting differs from the previous one by setting
O. Then the claim of Lemma T0mmma|T0chaan 100 as follows.
Lemma 11. Let ʃ L-smooth and quasi convex, and each Ji be Li-smooth. Let v = 300 and
y S 320 then we have
7
2
n + 3 10 La²
41 S L
F.
7
(24)
4
84
19

---

Published as a conference paper at ICLR 2024
Proof. The proof immediately follows from lemma by plugging in μ O.
Now we give the precise statement of Theorem
Theorem 6. Let f be quasi-convex around x' and I--mmoohh Let each Ji be Te-smooth. Then for 7 100 there exists Y S 3200/EL such that after at most
Roo NE
VLRgo
LRo
T= O
+
+
82g3/2
ås
iterations of Algorithm it holds EE (xoow) - f*] S E, where Ro == ||x0 - x²1 and Your is chosen
uniformly at random from X, {x0,..., XT
Proof. The claim of theorem 6 follows from lemma 11 lemma 5 and remark from Stich & Karimireddy 2020). Note that by the initialization V Ro-
B.3 NONCONVEX SETTING
Now give the small modification of lemma 7 that is used in the nonconvex setting.
Lemma 12. Let f be L-smooth, then:
20
E [||x++1 - x=110 2(1 He + 4n E. + 4E [x))(()))]]]
(25)
Proof.
E 7.2
[|x44] xx11?]
E
h 1r11
E
A n/,
gr + h, n0 + grl?
2E
| - 1/ gt + hy [1
+ +2 2E |Ime, + Bill
202
2E
|4 n1,
+ h,1
+ 2F
|1me= + [x(x))11
2
E
|| jar
gi + hi
+ 4n Σ
E |0:17
1=1
1=1
+ 20²
+ 4E
|12
(10)
2(1
8)
net +
gi
h hill
4n
E
|0:l
1=1
202
4E
|| [
where in (1) - (iii) we use Young's inequality; in (ii) we use Assumption 5 and in (iv) we use the definition of the compressor.
Next, give simple modification of lemma 9 nonconvex setting as well.
Lemma 13. Let f be L-smooth, and each fü be L.-moooth Let 8 Then we have
5. ak
for some k 2 and
7 32.21.'
(1
8
883
128Σ2728
2
H141
<
H
+
+
E, +
fx(x))11 ||
32
6444
6242
8
Izg²
+
1+
(26)
20

---

Published as a conference paper at ICLR 2024
Proof. The proof is almost exactly the same the proof of lemma 9 where the bound of [|| - xell²] by lemma is replaced by lemma
Now consider the Lyapunov function V, = F, + all, + bE, where constants a and b set as follows: 6 = 8.--- == 62
512kb where is will be set later.
Lemma 14. Let f be L-smooth, and each Sa Li-smooth. Let 1j = 100 and y S 3200
Then we
have:
Lo²
+ gB 1202
V S V. E [V
+ 7 2n
(27)
8a
Proof. Note that lemma 8 still holds in the smooth nonconvex case. Therefore, with 1) 4k
6 if
in 20
set
8k- 28
6
then:
5
8k 8
B S
1
E,
+
H
8k
Now put all inequalities together:
L2
22L 0²
V++1
F,
E
|
E. +
2
2n
(1-
8
883
128T2728
128i2y²
+ a
H₂
+
Eg +
f (x, [x
32
h-44
1244
6
64
2T222
+
0²
8
Y
8k
+
Es +
H1
8k
8
6
8kb
F.
+
1
aH.
32
8a
11-
1-
5
+
L2
883
+
228
))
bE,
8k
2b
h:444
1:24
128T.222
E |
(x,
)13
E [|VS(}))11
Lo²
64a
i2n²
+ 72 2n
a²
m
Similar as before, we now set 7 <
and get:
32.
8kb
L273
8
Me+1 S Fe +
all, +
1
+
+
bE,
32
da
8k
2b
16k.4b
128 128
L
64a
(
I2g2
E
[
+ 2
0² +
2n
5
n
Let b 8kL2n" and
5126b 8a
then for the coefficient next to He term, we have
8 8kb
8
1
+
32
8a
64
for the coefficient next to E, term, we have
8
1,233
83
8
8a
8
325
1
+
<
+
<
8k
2b
16k-4h
16k
16
16k
13
21

---

Published as a conference paper at ICLR 2024
for the coefficient next to E | fxx)]] term, we have
1²
7
7 8k
+
5
4
for the coefficient next to o² term, we have
64a
2
22
1
+
S
7
n
81
Therefore, if we set k 100, we get:
1 S Ft +
1
5
aH, +
1- 6
bEg
64
8850)
7 | (xx)) )13
+ Lo²
7:8 1000
8
2n
+ Lo²
+ 73 10'0
$ V. E [Vx
2n
84
Now we give the precise statement of Theorem
Theorem 7. Let f be I-smooth, and each be T4-smooth. Then for
there exists
300
7 S 3200 such that after at most
T= (L100² ne?
LFGo 8253/2
LFo de
+
+
iterations of Algorithm holds E ||| [ (Xou))] uniformly at random from X2 E (xu,...,xy)
S 8, where Fo == f(xo) f and Xou is chosen
Proof. The claim of theorem follows from lemma 14 lemma 5 and remark 6 from Stich 2020). Note that by our choice of initialization, Vo Fo-
Remark 15. Notice that we do not explicitly bound the distance between h; and the full local gradient (((x)) like in the proof of EF21 (see also Appendix G). Instead, we only control the size of the error term and the compressed message. Interestingly, this way we also indirectly control the distance between by and the local stochastic gradient:
E 11ot
nill?]
<
Il + oi
1113
+
Σn T [1c 1=1
2H,, + 2
With the choice n ~ 6, H. 2/2 E, proportional to the aH, + bE, term involved in the Lyapunov function we use in the analysis. Taking into account the convergence guarantees for the Lyapunov function, the above derivations show that the distance between hi and gi indeed controled and does not blow up.
C IMPORTANCE OF 7) CHOICE
C.1 THE ROLE OF FROM A THEORY PERSPECTIVE
Here we review the role of 7j in the lemmas, and shine some light on why the choice 7) ~ is important. For simplicity, we only consider the strongly convex case.
The descent of E, is achieved through 77. In particular, in Lemma E, is scaled by (1 + a1 2 For ~ and appropriate choice of a, we get descent on E, the scale
(1 2(5)), which is proportional to the descent of H, in Lemma
22

---

Published as a conference paper at ICLR 2024
(a) ejj = 0, hg
(xo)
(b) ej
0, hij
10a5
10
7ma7.am6
10
10
10
10
10
10-2
10-3
0
2
3
5
2
3
4
Iterations, x10
Iterations, x10*
Figure The convergence of EControl with y = and r) = 0.5 for two different initializations. EControl with = 8 converges regardless of the initialization while EControl with is sensitive to the initialization. Here 3200/2L i.e. theoretical value of the stepsize.
Perhaps more importantly, v controls the contribution of E,, and balances the scale between E, and He. Crucially, an E, term is introduced into the descent of H₃ in Lemma 9 via the upper bound on E
||x, Xx+ I1² (Lemma 77. With the v term, the contribution of E, from
is of the order O(>²*P/s). This turned out be extremely important in Lemma 10 where b ~ 5²a (recall that is the coefficient of H, and b is the coefficient of E, in the Lyapunov function VD) Taking a closer look at Lemma [0] we see that setting
E
[ x
1) 5 scales the E, term from the descent of H, by 0r²"² 8. This allows us pick
? ~ 5 resulting in 8 scale in front the E, term from the descent of Hç-
C.2 UNSTABLE BEHAIIIR WHIEN 7
Let us first consider simple problem with n 2, where Si and f2 are defined as follows
fi(x) = (1,
xx| f2(x) 1)
||
Obviously, this problem is strongly convex. We show that 7 parameter plays an essential role in stabilizing the convergence of EControl. We show that if initialization EControl may diverge while with 7) = converges.
1, then with the specific choice of
In the first set of experiments we consider cj = O, h/ O, while in the second one we initialize as ej = 0, h1 V (xo).. For simplicity, we use full gradients both cases in order not be affected by the noise. We apply Top-1 compression operator in all the cases, i.e. 8 = 3. For EControl with 7 = we set y according to Theorem 2
We demonstrate the convergence in both cases for EControl with 1 and = 6. The results are presented in Figure/6] We observe that both cases EControl with = 8 converges linearly to the solution it is predieted by theory. In contrast, EControl with rj 1 converges only h = (X,)) and diverges if h/ = 0 regardless of the choice of y. Very small values of the stepsize postpone the gradient norm blow up. This example illustrates that 7p å makes the algorithm converge more stable, i.e. it is necessary for efficient performance.
C.3 COMPARISON WITH EF21 AND DIMINISHING
Note that in Algorithm) when 7 - O. the algorithm recovers EF21. However, the crucial difference between EControl and EF21 is precisely the fact that each update is injected the scaled error term, which is the key ingredient for achieving the linear speedup in the number of clients. In this section we the synthetic least squares problem in Section to demonstrate that, 1) - 0, the performance of EControl degrades in the stochastic regime and its performance converges to that of EF21. The results summarized in Figure
23

---

Published as a conference paper at ICLR 2024
0.0001
10
EF21
10
0
5000 Iterations
10000
Figure 7: The convergence of ECOntrol with changing y) and EF21. = 200, < 100, 50 and number of client 16. We apply Top-K compressor with //4 0.1. The stepsize is fixed y 0.001 for the purpose of illustration. EControl the performance degrades as 17 -
Algorithm 3 EG-Approximate: EC with Approximate Bias Correction
1: Input: Xo.Y, ej
Od, Cs, and (h' (h' NE(M) such that 1/2 Em= E [ V
sa
2: h -> -/==1 h'
3:
for -0,1, 1,,
do
4:
gi 6==g. -gi
V client side
5:
Á; = Cs(e) + gi - h²)
6:
e++1 = e + gi - h A
7:
send to server: Á;
8:
Xe+1 X 7h ΣE Á
V server side
D EC-Approximate: APPROXIMATE BIAS CORRECTION
In Section|4 we described the ideal version EC when we have access to h fi(')) However, in practice. it not known most of the time. Therefore, propose to good enough approximation instead to make the method implementable. This idea leads to EC-Approximate summarised in its estimator h' which should estimate the true value ht
Algorithm 3 There, instead of h² well enough. In more details, we run EC with h' satisfying
n [
VAxx)) Sa,
in other words, the average distance between and (x+) is at most a. A trivial choice of the vectors, for which Algorithm recovers the D-EC-SGD (Stich 2020) algorithm with bounded gradient (at optimum) assumption. However, the smaller a is (i.c., the better approximation we have), the better convergence is. Thus, beneficial obtain h' after preprocessing. For
example, nontrivial choice would be some ht such that 1 Σ E |
(x*))
||]] O o
Such (h' Nejj) can be obtained by running EF21 for Ö L rounds, which is constant and does not depend on the accuracy 6. We show that it is indeed possible in Appendix G for completeness.
D.1 CONVERGENCE ANALYSIS
In this section we prove the convergence of Algorithm 3 The next lemma bounds the descent of E,. Lemma
(ee) be such that En ||lh* Vx((x))]1]] s a, then the iterates of Appoooixeeee satisfy
16. Let fi be L-smooth and convex.
Let
E $ (1-3)
Fg +
8L
F
4a
+ o²
(28)
8
24

---

Published as a conference paper at ICLR 2024
Proof.
Bi+1 =
E3
e
+
gi
- (cs + + -')l"]
1=1
(1
|
h']l?]
m
(1 8)
E
||0]
()(())) h²|l²] +
n
(1 (1 + 3)
EE
||e:|
2
i=1
+ (1 8) 3-
Vf((x,) - -h'l²² 0²
n
where in the last inequality we used Young's 's inequality. Setting B 2[158] we have:
(1-9) 5)
41
E+1 1
E,
Σ
E
[ - vf((('))1
2
8
n ==1
+
41
E
vf(('')
- h hill +
8
1=1
5 (1-2
8L 5
4a 5
E,
P.
+
2
where for the first inequality we used Young's inequality again, and for the second inequality we used the smoothness and convexity of fi, and our assumption on h'.
12L Now consider the Lyapunov function v = X, abc for = b descent lemma Ve..
We obtain the following
Lemma 17. Let f be p-strongly quasi-comvex around x*, and each fo be L-soooth and convex. Let
Jeem be such that 1.2 En= E || v/i(x*)
< or, and the stepsize be 7 S SVGL.
8
Then the
iterates of EC-Approximmte satisfy
Vet1 $ (1-c) c) 2 F. + 72 20 +33
48La
12Lo²
4
82
8
(29)
where == 12L and == 2
Proof. Putting Lemma and Lemma 16 together, we have:
Fi + 72 2 0²
1 S (1
7/4
X,
+ 3 E,
2
8L F, +
4a
+
E, +
8
(1
7/1
(1
8
3
X,
a.
2
+ 22 2
4a
o²
a
n
8La
Fr.
Plugging in the choice of a, we have for the E, term:
3
8
+
1
2
4"
25

---

Then Published as a conference paper at ICLR 2024
and for Fe term:
7
8La
9
7
5
8²
Combining the above together we derive the statement of the lemma.
Theorem 8 (EC-Approximate: EC with approximate bias correction). Let f R be u-strongly quasi-convex, and each fi be L-smooth and convex. Let {hO Jie[n] be such that
TR
1 D h vx((x)
S a. Let stepsize be S 8VEL'
Then after at most
T T= Ō=ō 0²
VLo
vLa jáve
L
+
LiNE IVOOE
iterations of Algorithm 3 it holds E (X(oo)))) f S where is chosen randomly from {xo,... } with probabilities proportional to (1 (0112222-111
Proof. We need to apply the results of Lemma 17 Lemma
3 and Remark noticing that 24
S
always due to the choice of the stepsize.
According to the statement of Theorem 8 the inaccuracy in the approximation affects the higher order terms only. We clearly see that Approxixie achieves optimal sample complexity. This result suggests that preprocessing in the beginning of the training for constant number of iterations may lead to better convergence guarantees in comparison with original EC.
In Appendix G show that in constant number of rounds of preprocessing using EF21, one can obtain a good (h' heii in] with error of the order ( for D-EC-SGD with approximate bias correction. We summarize it in the following corollary.
Corollary 18. Let R I be p-strongly quasi-convex, and each ft be L-smooth and convex.
Let run EF21 preprocessing for O after at most
bp log LFGe rounds. Let the stepsize be ay S 8v61."
0²
Lo
L μd!
T δ
+
uum
3
iterations of Algorithm 3 it holds TE (x)me) (Xo.... ), chosen with probabilities proportional to 11- (141)
- S e, where Neut is chosen randomly from
Proof. We only need to apply the results of Lemma 25 and Lemma 26 in Theorem
E CONVERGENCE OF EC-ldeal
In this section we derive the convergence of EC-Ideal. The result directly follows from Theorem with = O.
Theorem 1 (Convergence of EC-ldeal). Ler Rd - R be p-strongly quasi-convex around x", and each fo be L-smooth and convex. Then there exists a stepsize ry S 8V6L such that after at most
o2
Via
L
T
une 1/2611/2
μ
iterations of Algorithm 7 holds TE (xxou) - [*] < e, where Xom is chosen randomly from
(xo...., xx] with probabilities proportional to (1 - 101-///2)2-00) (1++1)
Proof. We need to apply the results of Theorem g with
26

---

Published as a conference paper at ICLR 2024
Algorithm 4 D-EC-SGD with Bias Correction and Double Contractive Compression
1: Input: Xg, 6/ O2. hj
B0: hg
E hg: Ciyy Caz. and 7
2: for t= 0, 1, 2. do
3: compute gi gi
client side
4: compute A; Cś, (e)
+ g:
h)) and ò Co (gi h;)
5:
update 1/+1 ci gi
hj A and h = h Ái
6:
send to server A/ and Â
7: update X == X; Th
2 =E i= A
V server side
8:
update h = ht + Di=1 A
F D-EC-SGD WITH BIAS CORRECTION AND DOUBLE CONTRACITVE COMPRESSION
In this section we follow algorithm D-EC-SGD with bias correction (Sichh 2020 In this algorithm, the learning mechanism for hi to approximate h built using additional compressor from more restricted class of unbiased compression operators. We show that unbiased compressor can be replaced by more general contractive one; see Algorithm 4 for more detailed description.
F.1 NOTATION
For D-EC-SGD with bias correction and double contractive compression we consider the following notation
12
X, E [||S
[|| E.
E ||ee||1]
and H.
E [IV)(x))
h2ll
(30)
F.2 CONVERGENCE ANALYSIS
Now we present the convergence rate for D-EC-SGD with bias correction and double contractive compression.
First, we highlight that Lemma I Next, we present the descent lemma in E,, Lemma 19. The iterates of D-EC-SGD with bias correction and double contractive compression satisfy
E s (1 111--/2 8/2) 2(1 2(1-8) -1) H, + (1 - -8,)0².
(31)
61
Proof. We have
n
E
E [[|e] +++ [|]]
71
im1
1 n
E e||e
g h- Cs, (e) + gi -h))l
71
(1
51)
<
E ||ee +gi -h:l11
51)
E [ Vx(x))) bill +11+0011 =1
Using Young's inequality we continue
P < (11 + a.)
(1 51)(1 + t
Σ
E [IVV)((x) - h;
(1-8)00²
27

---

Published as a conference paper at ICLR 2024
81 Now, if we choose 01 2(1-61)
obtain the statement of the lemma.
Lemma 20. Let I be T-smooth, then the iterates of D-EC-SGD with bias correction and double contractive compression satisfy
1 E
Xx+1
xx|1?|
4o 4H, + SE, + 8LF.
(32)
Proof. We have
1 722
1
E
[|x(+1
xxl1?|=1
|h' i e + gr
A 11
7
n
2E
h e
ge
+
Cs, (e) + gi h;)l
2E [lle gr]]]]
2
σ²
E
e
gt + Cs, (e + gi -1/1l
+ +2 4E
71 1=1
4E ( ||
2(1 - 81)
0² 2- + 4E, + 8LFF
Σ
E | oj gg]
0²
< 2(1 61)0² 4(1 8, 4(1 81 H, + 44, + 4LF,
S 40 + 4H, + SE, SLF
In our next lemma we state the descent Hy.
Lemma 21. Let f be L-smooth and each Ji be T--smmooth, then the iterates of D-EC-SGD with bias correction and double contractive compression satisfy
82 +
16i
32i22² E.
16Î2
16i2n²
8
Hel < (1
H.
+
+
F. +
+
82
82
82
82
5n
In particular, i < 8/27. then:
82 H,
32
1672 L
1662n²
Hol 5 (1-
+
E, +
F, +
(33)
8
82
82
82
82
28

---

Published as a conference paper at ICLR 2024
Proof. We have taking the expectation E, [ w.r.t.g:
[[ h - Cs. - n;)ll |]
E, [M++1]
E
72
(1)
(1 + B) V vf((x()1
12
1
(1 + 8 | [[] - hn -Cs -h;) h;)l
11
i=1
(60
S (12 + B)T |||
-
M1 || + (V]((x;) - g/) 13)-b hh -Co bb)11
n
(00)
$ (1 B) [|| ||x - xx11
1
(1+ B )1 + 81 ) |||s hj Cs. h;)11a]
"
1
(1 + 11+ + 1 [[V - Bill]]
(10)
i2 + E Xt+1 x
1 Σ 11+ ) s1) - 82) [|g: -hill] + (1+ si 'o²
where in (i) we use Young's 's inequality; in (ii) we L-smoothness; (iii we use variance decomposition; in (iv) we use the definition of Cs2 and bounded variance assumption. Note that g 's are independent from (x,,)) h,, and F. (Xx, gd] = 0, we have:
E. [+++] < (1 B)
||xe-- xel13]
1 Σ
(1+ 3 (11++)))+) (xx -hil?
n
+ (1 + B 1) (1 + 81) (1- 82)0² + (1 + 3 (1 + 1
We also can upper bound | - xx by Lemma 20 which leads to
E, < (1+ + 9 31 + s1) 82)Hz
+ [1 + 3)>? (8E, + -HH + 4LF, + 40 .
+ +(1 - 8-1
+ (1+ +L+
+ s1)( 82)) 0²
Now we need to properly set all constants 3, $1, to derive the lemma statement. In particular, if we
choose 3 1-262 and 81 21-0,5 then
82
82
2
32i22²
167
16i2n²
8
H < (1
H +
E, +
F.
+
d²
82
82
82
Next we consider the Lyapunov function V = X, + aH, + bE,
Lemma 22. Let f be L-smooth and p-strongly quasi-convex, and each ft be smoohh.h If s 5.
64./1 then:
7H v4
2 F, 4
02 3100LO
Vz+1 < (1
(34)
2
0705
where b = 12L 8,
and 326 8,02
29

---

Published as a conference paper at ICLR 2024
Proof. By Lemma 1 Lemma 19 and Lemma 21 have:
141 = Xt+1 + atl + b
2
1 (1
Y/11
Xx
7 Fi
0²
3
Es
2
2
n
82 H1 +
32
16
16L3n²
8
+a
(1
Et +
Fit
+
o²
82
82
82
82
51
2(1
51)
0²
+
(1- 2
F4 +
H:
+ (1
81)
81
B
7
82
2(1
61)b
= (1
Xx, +
1
aH!
2
8
b1a
61 +
3
3
+
1
bE:
2
8zb
Y + al
1
8
+
+
+
b(1
81)
o²
82
82
Y +
La
+
Fr
2
82
If
12
61
a
8,62"
and if S
64
6,6
then for coefficients next to H, we have:
82
2(1
61)6
82
1
3
δ1a
16
for the coefficients next to E, we have:
3
32
51
+
<
2
82b
for the coefficients next to 2² we have:
167
2
3310LL
+ b(1 - 81) $ 73
82
82
5700
for the coefficients next to we have:
162 Ly
7
7
2
82
Putting together have:
1 - (1
7/4 11
)
F.
202
3100Lo2
4
07
where we note that TH 5 and nH <
62 16:
Theorem 9. Let J be p-strongly quasi-convex around x* and I-smooth. Let each S be I.-smooth. 6,62 Then after at most
Let 61v21.
0²
VLo
T T= uume
+
1d182g1/2
iterations of Algorithu 4 it holds E (X fr] S E, where Xoma is chosen randomly from E Xr with probabilities proportional to (1 (1-17 -
Proof. We need to apply the results of Lemma Lemma 22 and Remark
We observe that D-EF-SGD with double contracitve compression still achieves nearly optimal asymptotic complexity with stochastic gradients, where a o² factor is hidden in the log terms. However, in the non-asymptotic regime it has poor dependency 52. In the simplest full gradient case, when 8, = 82 and o² = 0, the linearly convergent term is proportional to 5-2, In opposite, EF21 and EControl have only 5-1 dependency in this setting.
compression parameters ón and
30

---

Published as a conference paper at ICLR 2024
G COMPLEXITY OF EF21-SGD
In this section we consider EF21 mechanism. Richtárik et al. (2021) demonstrate that EF21-GD,
Le. EF21 with full local gradient computations converges linearly. In the stochastic setting, it has been shown (Fatkhullin et al. 2023) that EF21-SGD converges only with large batches. For completeness, we present convergence guarantees of EF21 with arbitrary batch size. In particular,
show that EF21 can converge to an error of O d in a log number rounds. EF21 is summarized in Algorithm
82ح
Algorithm 5 EF21
Input: ho. (xx)) 7, and h, + " Σi=1 h
2: for 0, 2.... do
3:
g: = gi:
client side
4:
A; = Cs(g) - h²)
5:
hi+1 hi 1 Ai
6:
send to server: A
7:
Xe+1 Xx h,
side
8:
h = h1 + Ei= A
Consider P. = [(x.) f and H, modifications of the lemmas in (Li et al. 2021) and (Richtárik et al. 2021 in the presence of stochasticity. Therefore, we state them without proofs.
bill [
(((r))
The following lemmas are simple
Lemma 23 (Lemma from Li al. (20T)). Let I be p-strongly convex and L-smooth. Then iterates of EF21-SGD sutisfy
F+1 S (1 7P)F
E
[|x+1 - xI1l"] -
+2 82y0 + 88714
(35)
27
Lemma 24 (Lemma 7 from Richtárik et al. (202I)) Let f be p-strongly convex and fi be L-smooth for all [n). Then iterates of EF21-SGD satisfy
2T.2 11 +
30
E, [1++1] S 1
E | xel?
(36)
8
Now consider V == Fe + all,, where = 100g 8
Putting these two lemmas together, we have:
Lemma 25. Let f be u-strongly convex and fs be L-smooth for all i [m]. Let S 1001. Then
iterates of EF21-SGD satisfy
40L E, [++1] (1-c)
300 82
[|x++] - xx|1²] + 2
a²
(37)
8
where c := 7/p.
Solving the recursion, one can show that
(7M(T+1
300 82
Lo +
2
d²
In particular, this means that & decreases O ( in O log FubL rounds. Therefore, EF21- a²
SGD can be used as warm up algorithm to find good approximation of h; As we can see, the output
of EF21-SGD satisfies the restriction for Algorithm 3 In particular, we show that at any iteration of EF21-SGD, we have 1 En IE b| fx(xx) II] 4LV, if r and a are chosen as in Lemma 25
Lemma 26. If fs is L-smooth and convex, and h, and x are generated by EF21 with y 100%. then
$
1
E [ h
vf(x'))] 4L%,
t=1
where V. Fr + aH, and 4
31

---

Published as a conference paper at ICLR 2024
Proof.
E
hi
2 n -
E
h
(x(( 19]
21
+ 2
E [V - vx((x))1
i=1
n
E
[bi {((())11
11
(
- 11(x)) (V -xx))
2 E
+4L(f(x)) - fr)
2H, + +LLF
$ 4L
32


Reviews:
[{"review_id": "FNeBXRUQGt", "reviewer": "Reviewer_8MAp", "summary": "This work proposes a new EC algorithm for distributed training with communication compression. Unlike traditional error compensation methods where we only add the previous compression back to the compressed gradient, in EControl authors achieve a faster convergence rate by controlling the strength of the feedback signal. Authors proved the superiority of EControl from both theoretical and experimental side.", "questions": "No", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The algorithm design looks smart to me. By starting from the EC-ideal, the convergence rate of the compressed SGD could achieve optimal asymptotic complexity. Afterwards authors further extend this idea to general cases where h^* cannot be attained.", "weaknesses": "No", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "db41PDb7vM", "reviewer": "Reviewer_NamU", "summary": "This paper proposes EControl, a novel mechanism that can regulate error compensation by controlling the strength of the feedback signal. Theoretical analysis is provided for EControl in strongly convex, general convex, and nonconvex settings without any additional assumptions on the problem or data heterogeneity. The experiments show that the proposed algorithm out-performs the baselines in large-scale vision tasks.", "questions": "1. Is there a variant of EControl which is combined with momentum?\n\n2. Could the authors give a more detailed discussion about the (theoretical) connection and comparison between EControl and EF21?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. This paper proposes EControl, a novel mechanism that can regulate error compensation by controlling the strength of the feedback signal. \n\n2. Theoretical analysis is provided for EControl in strongly convex, general convex, and nonconvex settings without any additional assumptions on the problem or data heterogeneity. \n\n3. The experiments show that the proposed algorithm out-performs the baselines in large-scale vision tasks.", "weaknesses": "1. It is unknown how to combine EControl with momentum SGD. The original EF has well-developed momentum variants. EF21 has the variant of EF21-SGDM. Although the experiments include EF21-SGDM, there is no EControl + momentum provided.\n\n2. There seems to be a strong connection between EControl and EF21. If we the compressed version of $h$ in the initialization $h_0^i = \\mathcal{C}(g_0^i)$, and take $\\eta = 0$, then EControl will be equivalent to EF21. In other words, with a little bit twist in the initialization, EF21 can be viewed as a special case of EControl. However, I haven't found any discussion about the relationship between EControl and EF21 like this. Furthermore, I recommend to add some ablation experiments where $\\eta$ varies and gets tuned gradually closer to 0, which I guess will give a training loss curve closer to EF21.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "6r3RCNhgBm", "reviewer": "Reviewer_iMbi", "summary": "This paper presents EControl, a novel algorithm introduced to address communication compression challenges in modern distributed training. EControl utilizes contractive compressors to reduce communication overhead, effectively mitigating issues like unstable convergence and compression bias commonly associated with naive implementations. Notably, EControl's standout feature lies in its ability to regulate error compensation by controlling the feedback signal's strength, making it a valuable solution for data heterogeneous scenarios.\n\nUnlike previous methods, EControl dispenses with impractical assumptions such as bounded gradients or data homogeneity. It demonstrates rapid convergence rates in standard convex and nonconvex settings, showcasing its adaptability and robustness. Through comprehensive numerical evaluations, the paper substantiates the effectiveness of EControl, highlighting its potential to revolutionize distributed training by alleviating communication overhead challenges and facilitating more efficient and stable model training processes.", "questions": "Same questions related to the issues on specific lemmas or inequlities asked in \"Weaknesses\".", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The proposed method EControl does not need the assumptions such as large batchsizes and bounded gradient, it also enjoys linearly speedup, therefore, it overcomes the shortcomings of previous error-compensation framework.", "weaknesses": "While the importance of the crucial parameter $\\eta$ in EControl is discussed in section 4, its significance could benefit from a more comprehensive explanation within the main body of the paper. I would strongly recommend the inclusion of lemmas and inequalities to elucidate the pivotal role of $\\eta$. Additionally, providing similars lemmas into how $h_t^i$ approximates gradient information and how the strength of the feedback signal is controlled would enhance the clarity and understanding of the proposed method.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1vrLjCvsWy", "reviewer": "Reviewer_6rfE", "summary": "The paper proposes EControl algorithm that provably converges for strongly convex, convex, and nonconvex, with general contractive compression and with classic assumptions on the problem. It also gives experimental evaluations of EControl to show its efficacy\nin practice.", "questions": "-In step 6 of EC-Ideal you don't have the extra parameter \\eta that you have in EControl, can you explain why for EC-Ideal this is not needed. Will EC-Ideal have the same convergence guarantees if you add \\eta in step 6, with the same values as for EControl?\n-Bounded variance: This assumption contradicts strong convexity. I understand it is in several works in the literature. Take for instance F(x,y,z) = zx^2 + (1-z)y^2, z follows Bernoulli (1/2), then E_z(norm(\\nabla F(x,y,z) - \\nabla E_z(F(x,y,z)))^2) = (x-y)^2 and this is not bounded for all x and y in R.\n-You mention in page 7 that \"The asymptotic complexity of EControl in this regime with stochastic gradient is tight and cannot be improved,\"  I understand for the depence on \\epsilon, however can you tell why the dependence on other parameters can not be improved.\n-In the experiments, how you relate \\zeta to the noniddness, why for instance zeta equal to zero is iid and zeta >0 is non idd.\n-Did you try \\eta= delta/400 suggested by the theory in the experiments? why you need to fine tune it, since it is fixed by theory. Is only fixed \\eta = \\delta/400 that works in theory or many other values can work, this is not clear in the paper.\n-Did you test with other compressors?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "New error compensation algorithm: EControl with theoritical gaurantees for strongly convex, general convex, and nonconvex functions\nEmpirical experiments to support the theoretical gaurantees and assess the efficacy of EControl.", "weaknesses": "see the section below (Questions)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)