CANITA: Faster Rates for Distributed Convex Optimization with Communication Compression
Authors: Zhize Li
Peter Richtárik
Venue: NeurIPS 2021 Poster (2021)
Keywords: distributed optimization
federated learning
communication compression
acceleration/momentum

Abstract: Due to the high communication cost in distributed and federated learning, methods relying on compressed communication are becoming increasingly popular. Besides, the best theoretically and practically performing gradient-type methods invariably rely on some form of acceleration/momentum to reduce the number of communications (faster convergence), e.g., Nesterov's accelerated gradient descent [31, 32] and Adam [14]. In order to combine the benefits of communication compression and convergence acceleration, we propose a \emph{compressed and accelerated} gradient method based on ANITA [20] for distributed optimization, which we call CANITA. Our CANITA achieves the \emph{first accelerated rate} $O\bigg(\sqrt{\Big(1+\sqrt{\frac{\omega^3}{n}}\Big)\frac{L}{\epsilon}} + \omega\big(\frac{1}{\epsilon}\big)^{\frac{1}{3}}\bigg)$, which improves upon the state-of-the-art non-accelerated rate  $O\left((1+\frac{\omega}{n})\frac{L}{\epsilon} + \frac{\omega^2+\omega}{\omega+n}\frac{1}{\epsilon}\right)$ of DIANA [12] for distributed general convex problems, where $\epsilon$ is the target error,  $L$ is the smooth parameter of the objective, $n$ is the number of machines/devices, and $\omega$ is the compression parameter (larger $\omega$ means more compression can be applied, and no compression implies $\omega=0$). Our results show that as long as the number of devices $n$ is large (often true in distributed/federated learning), or the compression $\omega$ is not very high,  CANITA achieves the faster convergence rate $O\Big(\sqrt{\frac{L}{\epsilon}}\Big)$, i.e., the number of communication rounds is $O\Big(\sqrt{\frac{L}{\epsilon}}\Big)$ (vs. $O\big(\frac{L}{\epsilon}\big)$ achieved by previous works). As a result, CANITA enjoys the advantages of both compression (compressed communication in each round) and acceleration (much fewer communication rounds). 

CANITA: Faster Rates for Distributed Convex
Optimization with Communication Compression
Zhize Li KAUST
Peter Richtárik
KAUST
zhize 10kaust.edu..e edu.
beter.richtarikkkkenn edu.
Abstract
Due to the high communication cost in distributed and federated learning, meth- ods relying on compressed communication are becoming increasingly popular. Besides, the best theoretically and practically performing gradient-type methods invariably rely on some form of acceleration/mommntum to reduce the number of communications (faster convergence), e.g., Nesterov's accelerated gradient descent [31 32) and Adam [14]. In order to combine the benefits of commu- nication compression and convergence acceleration,
propose compressed and accelerated gradient method based on ANITA [20] for distributed optimiza- tion, which we call CANITA. Our CANITA achieves the first accelerated rate
(1+
which improves upon the state-of-the-art non-
accelerated rate ((1+ # w't= of DIANA 12 for distributed general w+n
convex problems, where is the target error, L is the smooth parameter the objective, n is the number of machines/devices, and w is the compression parameter (larger means more compression can be applied, and no compression implies w 0). Our results show that as long as the number of devices n is large (often true in distributeedfedeeraeed learning), or the compression w is not very high, CANITA
achieves the faster convergence rate (V i.e., the number of communication
rounds is ( (v (vs. O achieved by previous works). As result, CANITA enjoys the advantages of both compression (compressed communication in each round) and acceleration (much fewer communication rounds).
1
Introduction
With the proliferation of edge devices, such as mobile phones, wearables and smart home appliances, comes an increase in the amount of data rich in potential information which can be mined for the benefit of humankind. One of the approaches of turning raw data into information is via federated learning [15 29), where typically single global supervised model is trained in massively distributed manner over a network of heterogeneous devices.
Training supervised distributed/feddrraee learning models is typically performed by solving an optimization problem of the form
{ Mw)) zER
min
a=1
where n denotes the number of devviee//achiiesvvorreeeeiciii and f; RRd - R is a loss function associated with the data stored on device We will write
x²
arg min f()) 2E3d
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

If more than one minimizer exist, x= denotes an arbitrary but fixed solution. We will rely on the solution concept captured the following definition:
Definition A random vector T E I2 is called an e-solution of the distributed problem ①
[ff - f(==)======))) S,
where the expectation is with respect the randonness inherent in the algorithm used to produce T.
In distributed and federated learning problems of the form ( communication of messages across the network typically forms the key bottleneck of the training system. In the modern practice of supervised learning in general and deep learning in particular, this is exacerbated by the reliance on massive models described by millions even billiions of parameters. For these reasons, it is very important to devise novel and more efficient training algorithms capable of decreasing the overall communication cost, which can be formalized as the product of the number of communication rounds necessary to train model of sufficient quality, and the computation and communication cost. associated with a typical communication round.
1.1 Methods with compressed communication
One of the most common strategies for improving communication complexity is communication compression [37
This strategy is based the reduction of the size of communicated messages via the application of suitably chosen lossy compression mechanism, saving precious time spent in each communication round, and hoping that this will not increase the total number of communication rounds.
g 30
26 24
Several recent theoretical results suggest that by combining appropriate (randomized) compression operator with a suitably designed gradient-type method, one can obtain improvement the total comparable baselines not performing any compression. For instance, this is the case for distributed compressed gradient descent (CGD) [I 13 g 24], and distributed CGD methods which employ variance reduction tame the variance introduced by compression 7
communication complexity
30 9
24 6]
1.2
Methods with acceleration
The acceleration//omenttun of prradient-type methods is widely-studied in standard optimization problems, which aims to achieve faster convergence rates (fewer communication rounds) [33 31 32
28
I8
[6] 23 [20]. Deep learning practitioners typically rely Adam (14), or of its many
variants, which besides other tricks also adopts momentum. In particular, ANITA [20] obtains the current state-of-the-arn convergence results for convex optimization. In this paper, will adopt the acceleration from ANITA 20) to the distributed setting with compression.
1.3 Can communication compression and acceleration be combined?
Encouraged by the recent theoretical success of communication compression, and the widespread success of accelerated methods, in this paper we seek to further enhance CGD methods with acceleratio/mmmmnnum,. with the aim to obtain provable improvements in overall communication complexity.
Can distributed gradient-type methods theoretically benefit from the combination of gradient compression and no such results exist in the general convex regime, and in this paper we close this gap by designing method that can provably enjoy the advantages of both compression (compressed communication in each round) and acceleration (much fewer communication rounds).
To the best of our knowledge,
While there is abundance of research studying communication compression and acceleration in isolation, there is very limited work on the combination of both approaches. The first successful was recently achieved by the
combination of gradient compression and poceleration/momennt ADIANA method of Li (26). However, et al. 26 only provide theoretical results for strongly convex problems, and their method is not applicable to (general) convex problems. So, one needs to

---

Table 1: Convergence rates for finding e-solution B[f(=")) f(x²) of distributed problem
Algorithms
Strongly convex
General convex
Remark
QSGD MI
O wG
v compression
acceleration
(((1 #) +oxx+to log
compression
DIANA 30
acceleration
DIANA 9
(( + ;)x log
o ( + +
compression
X acceleration
o ((1 #) -
compression
DIANA 12
x acceleration
ADIANA 26
((VR+ (V++Vl# + / + log
compression
acceleration
CANITA (this paper)
o((( - v +
v compression
acceleration
both design a new method to handle the convex case, and perform its analysis. A-priori, it not clear all what approach would work.
To the best of our knowledge, besides the initial work 266 we are only aware of two other works for addressing this question A1 34]. However, both these works still only focus the simpler and less practically relevant strongly convex setting. Thus, this line research is still largely unexplored. For instance, the well-known logistic regression problem is convex but not strongly convex. Finally, a problem is strongly convex, the modulus of strong convexity is typically not known, or hard to estimate properly.
2 Summary of Contributions
In this paper we propose and analyze an accelerated gradient method with compressed communication, which call CANITA (described in Algorithm T), for solving distributed general conver optimization problems of the form (I) In particular, CANITA can loosely be seen a combination of the accelerated gradient method ANITA of [20). and the variance-reduced compressed gradient method
DIANA of [30]. Ours is the first work provably combining the benefits of communication compression and acceleration the general convex regime.
2.1 First accelerated rate for compressed gradient methods in the convex regime
For general convex problems, CANITA is the first compressed communication gradient method with accelerated rale. In particular, CANITA solves the distributed problem (1) in
o (I(+
communication rounds, which improves upon the current state-of-the-ar result
w w+n
achieved by the DIANA method 12] See Table I for more comparisons.
Let us now illustrate the improvements coming from this new bound on an example with concrete numerical values. Let the compression ratio be 10% (the size of compressed message is 0.1 d, where d is the size of the uncompressed message). If random sparsification or quantization is used to achieve this, then x 10 (see Section 3.1.. Further, if the number of devices/machines is n 10
denotes the condition number, where is the smooth parameter and > 0 is the strong convexity parameter.
In this strongly convex column,
"Here QSGD [T] needs additional bounded gradient assumption, i.e. [[/[(=]] G Vi e [M], e
gd

---

and the target error tolerance is = 10 then the number of communication rounds of our CANITA method O110)), while the number of communication rounds the previous state-of-the-arr method
DIANA 12] is O(10%) i... OVV ) vs. ²) This is an improvement of three orders of magnitude.
Moreover, the numerical experiments in Section iindeed show that the performance of our CANITA is much better than previous -oneeccelertted compressed methods (QSGD and DIANA), corroborating the theoretical results (see Table I and confirming the practical superiority of our accelerated CANITA method.
2.2 Accelerated rate with limited compression for free
For strongly convex problems, Li et al. [26 showed that if the number of devices/machines v is large, or the compression variance parameter w is not very high (w S 3 then their ADIANA method enjoys the benefits of both compression and acceleration (i.e., / log ! of ADIANA vs. log ! of previous works).
In this paper, consider the general convex setting and show that the proposed CANITA also enjoys the benefits of both compression and acceleration. Similarly, if w I n (i.e., many devices, or limited compression variance), CANITA achieves the accelerated rate / vs. y of previous works. This means that the compression does hurt the accelerated rate at all. Note that the second term (2) is of lower order compared with the first term V
2.3 Novel proof technique
The proof behind the analysis of CANITA is significantly different from that of ADIANA [26), which critically relies strong convexity. Moreover, the theoretical rate in the strongly convex case is linear Olog t), while it is sublinear O (( (accelerated) in the general convex case. We hope that our novel analysis can provide new insights and shed light on future work.
3 Preliminaries
Let [n] denote the set norm for a matrix. Let (u, v) denote the standard Fuclidean inner product of two vectors u and v. We use O(-) and (2-)) to hide the absolute constants.
2, 21, , and || denote the Euclidean norm for vector and the spectral
3.1 Assumptions about the compression operators
We now introduce the notion of randomized compression operator which we compress the gradients to save on communication. We rely on a standard class of unbiased compressors (see Definition 2 that was used in the context of distributed gradient methods before
13 9 24 26
Definition 2 (Compression operator) A randomized map C IRdd b Rd is an w-compression operator if
[C(x)) x,
E [[[((=) x1| s w/ w|| Ve Rd..
In particular, compression (C(x) x)) implies 0.
It is well known that the conditions are satisfied by many practically usefuul compression operators For illustration purposes, we now present couple canonical examples: sparsification and quantization.
(see Table in 3 36)
Example (Random sparsification). Given & Rdd the random-k sparsification operator is defined by
d K (Ex @x),
C(x)
where @ denotes the Hadamard (element-wise) product and & E (0, 1] is uniformly random binary vector with & nonzero entries (llEx k). This random-k sparsification operator C satisfies

---

2 with w = 1. By setting & = d, this reduces to the identity compressor, whose variance is obviously zero: 0.
Example 2 (Random quantization). Given æ E R2d the (p, s)-quantization operator is defined by
(x) == sign(x)
||>||> S..
where p, s 2 are integers, and &. E Fd random vector with i-th element
I 1, with probability |x. || 4
(1) =
1 otherwise.
The level satisfies
1xc 20
E
1 ++ The probability is chosen so that I [5.( = |z, -
This (p, 8)-
(2) with 2 d'/2-a'/2 In particular, QSGD 1 used p 2 (i.e., (2, quantizzatin) and proved that the expected sparsity of (xx) is E [z) (z))zz [lo] = (s(ss vd))
quantization operator C satisfies
3.2 Assumptions about the functions
Throughout the paper, assume that the functions fi are convex and have Lipschitz continuous gradient.
Assumption Functions fü IRd - R are corvex, differentiable, and L-smooth. The last condition
means that there exists constant L > 0 such thatfor all E [n] we have
[V)(x) v(fi())I < L|| wll,
Vx, E Rd
It is easy to see that the objective f(x) = Em= f((x) in constituent functions {fi} do.
satisfies 3 provided that the
4 The CANITA Algorithm
In this section, we describe our method, for which we coin the name CANITA, designed for solving problem ( which is of importance distributed and federated learning, and contrast the most closely related methods ANITA [20], DIANA 30 and ADIANA [26].
Algorithm Distributed compressed accelerated ANITA method (CANITA)
........, Input: initial point 0 Rd. initial shift vectors ....... Na E Rdd, probabilities {pr), and positive stepsizes (ar) {1h }. (0,)
1: Initialize: " =
and h E
2: for t = 0, 2. do
3: y = 0,x² (1-1,
4: for all machines i 1, 2, ... do in parallel
5: Compress the shifted local gradient (V( - ht) and send the result to the server
6: Update the local shift h+*1 h +
- hς)
7: end for
8: Aggregate received compressed local gradient information:
g' ht
(((V((())) k&)
Compute gradient estimator
h1+1 = ht + az Σ (VVF.((')) h9) i=l
Maintain the average of local shifts
9: Perform update step:
x x¹
gz
0.9
20+1 0, 11 + (1 0
w11 = 1111,
with probability Pt
11:
with probability 1 Pr.
12: end for
5

---

4.1 CANITA: description of the method
Our proposed method CANITA, formally described in Algorithm | an accelerated gradient method supporting compressed communication. It is the first method combing the benefits of acceleration and compression in the general convex regime (without strong convexity).
In each round t, each machine computes its local gradient (e.g., V fi(")) and then a shifted version compressed and sent to the server (See Line 5 of Algorithm D. The local shifts h are adaptively changing throughout the iterative process (Line 6 and have the role of reducing the variance introduced by compression C-)). If no compression is used, we may simply the shifts to be hf = 0 for all i, f. The server subsequently aggregates all received messages to obtain the gradient estimator g² and maintain the average of local shifts h (Line 8), and then perform gradient update step (Line (9) and update momentum sequences (Line [0 and 3). Besides, the last Line II adopts a randomized update rule for the auxiliary vectors w² which simplifies the algorithm and analysis,
resembling the workings of the loopless SVRG method used in [16 20
4.2 CANITA existing methods
CANITA can be loosely seen as a combination of the accelerated gradient method ANITA of (0]]
and the variance-reduced compressed gradient method DIANA of [30]. In particular, CANITA uses
momentunn/acceleratiii steps (see Line 3 and of of Algorithm| I inspired by those ANITA 20
and adopts the shifted compression framework for each machine (see Line and of Algorithm in the DIANA method 30
as
We prove that CANITA enjoys the benefits of both methods simultaneously, i.e., convergence acceleration of ANITA and gradient compression of DIANA.
Although CANITA can conceptually be seen as combination of ANITA 20 and DIANA 30 12 from algorithmic perspective, the analysis of CANITA is entirely different. Let us now briefly outline some of the main differences.
For example, compared with ANITA 20 CANITA needs deal with the extra compression of shifted local gradients in the distributed network. Thus, the obtained gradient estimator ge in Line 8 of Algorithm is substantially different and more complicated than the one in ANITA, which necessitates a novel proof technique.
Compared with DIANA 30 9 12], the extra momentum steps in Line 3 and 10 of Algo- I make the analysis of CANITA more complicated than that of DIANA. We obtain the
accelerated rate 0(1 rather than the non-accelerated rate ( of DIANA, and this
impossible without a substantially different proof technique.
Compared with the accelerated DIANA method ADIANA of (26), the analysis of CANITA is also substantially different since CANITA cannot exploit the strong convexity assumed therein.
Finally, please refer to Section 2 where we summarize our contributions for additional discussions.
5 Convergence Results for the CANITA Algorithm
In this section, we provide convergence results for CANITA (Algorithm) I In order to simplify the expressions appearing in main result (see Theorem i in Section 5.1 and in the lemmas needed to prove (see Appendix A). will be convenient to let
F² = f(w't - f(x),,
H'
[Vi(w()- 121
D == - x=1 -1==-1=-=111
(4)
T
5.1 Generic convergence result
We first present the main convergence theorem of CANITA for solving the distributed optimization problem (1) in the general convex regime.

---

Theorem Suppose that Assumption 1 holds and the compression operators {C.) used in Algo-
rithun 7 satisfy 2 of Definition 2 For any two positive sequences { and {7t) such that the
probabilities {pt) and positive stepsizes (o4), (ne), (0c) of Algorithm / satisfy the following rela-
tions
0i S 1+
M S
(5)
(1 (1+ 4pr7o (1+ +22)) 2)))
for all t 2 O, and
2w Ben
+4p:%c (1+ 2pb)
11-8: 0s,
(1 prOefme
1
+ (1 de
)0
S
-t- 1ip-
P:0f
0e-10/1
2
0
07
(6)
for all 2 1. inequality
Then the sequences (0", w/, n1 of CANITA (Algorithm) D for all 1 2 0 satisfy the
pt E
TsPt H
Oipr T/t
(1 (1-0opo)mo Oopo)ra p +
Cppo
3om
w
((1-((1))
+
0K0
70
0 I
110
H
D
where the quantities Ft, H D' are defined in (4)
The detailed proof of Theorem I which relies on six lemmas is provided in Appendix A In particular, the proof simply follows from the key Lemma (see Appendix AA.2) while Lemma 6 closely relies
on previous five Lemmas 5 (see Appendix C.6 Note that all proofs for these six lemmas
deferred to Appendix C
As we shall see in detail in Section 5.2 the sequences 3t,7,,P
T/ Pt and a; can be fixed to some constants B However, the relaxation parameter 0g needs to be decreasing and the stepsize T)c may be increasing until a certain threshold. In particular, we choose
B = C1
7t = C2.
Pe = C3+
0: = C5 at = C4,
t + co'
Tie = min {11 t+ 0T
M--1,
CgL
1
S
(8)
where the constants } may depend on the compression parameter w and the number of de- vices/machines n. As result, the right hand side of (7) will be of the order O (#), which indicates an accelerated rate. Hence, in order to find an e-solution of problem ( i.e., vector wT+1 such that
E [f f(x')
E F S.
the number of communication rounds of CANITA (A (Algorithm 1b is at most T = 0
While the above rate has an accelerated dependence c, it will be crucial to study the omitted constants {cx) (see (8), and in particular their dependence on the compression parameter w and As expected, for any fixed target error
the number of devices/machines communication rounds 7 (sufficient to guarantee that holds) may grow with increasing levels of compression, i.c., with inereasing w. However, the same time, the communication cost in each round decreases with w. It is easy to see that this trade-off benefits compression. In particular, as we mention in Section [ if the number of devices n is large, or the compression variance w is not very high, then compression does not hurt the accelerated rate of communication rounds at all.
the number of
5.2 Detailed convergence result
We now formulate concrete Theorem from Theorem I which leads to a detailed convergence result for CANITA (Algorithm by specifying the choice of the parameters Be, Pt,Pt, Os, Ot and f)t- The detailed proof of Theorem is deferred to Appendix B
Theorem 2
Suppose that Assumption
/ holds and the compression operators (C) used in Algo-
of Definition 2 Let b = min w. w(1+w)? and choose the two positive
rithm
satisfy
"Exception While indeed choose &: = 3 for t 2 1, the value of 90 may be different.
7

---

sequences } and {7t) as follows:
B0 9[++b+w] (1+8)L
for ==
(1+
Br
13 =3= 48w(1 (4642(((4))
for t t21"
7t 7 8(1 + ++ 2(1 + w))
for 12 0.
n(1+6]
(10)
If we set the probabilities {pr) and positive stepsizes {ac), {m:) : { of Algorithm 7 follows:
3(1 + b)
Pr = 1+b
a = 1+
8, t
for t t2 0,
(11)
and
1 +//2)
for t
1/
min
(1
[19(1+buu)
1h-1
L/843/2)
for 12 1
(12)
Then CANITA (Algorithm 7 for all T 2 0 satisfies
w /n)
w
E +1
SO
(13)
T
T3
According to (3), the number of communication rounds for CANITA (Algorithm 7 find an e-solution of the distributed problem ( i.e.,
E [f - f
E
F
Sc
at most
11+ (
w
L
T ==0
+
6 Experiments
In this section, we demonstrate the performance of our accelerated method CANITA (Algorithm) I and previous methods QSGD and DIANA (the theoretical convergence results of these algorithms can be found in Table ! with different compression operators on the logistic regression problem,
min f(x) Σ log (1 exp(-bia, x)),
(14)
EERd
where bi ER x {+1} are data samples. We three standard datasets: a9a, mushrooms, and w8a in the experiments. All datasets are downloaded from LIBSVM [4.
Similar to Li et al. 126]. we also use three different compression operators: random sparsification (c.g. (39)), natural compression (c.g. ( ). and random quantization (c.g. [I]. In particular, we follow the same settings as in Li et al. (26). For random-r sparsification, the number of commu- nicated bits per iteration 32r, and we choose r = d/4. 4. For natural compression, the number of communicated bits per iteration is 9d bits [8] For random (2, x) -quannizzation. we choose vd. which means the number of communicated bits per iteration is 2.8d + 32 [1] The default number of nodes/maachineswoorees is 20. In our experiments, we directly use the theoretical stepsizes and parameters for all three algorithms: QSGD (T] 24). DIANA [12]. our CANITA (Algorithm) []. To compare with the settings of DIANA and CANITA, we use local gradients (not stochastic gradients)
QSGD. Thus here QSGD is equivalent to DC-GD provided in 24
In Figures we compare our CANITA with QSGD and DIANA with three compression operators: random sparsification (left), natural compression (middle), and random quantization (right) three datasets: a9a (Figure [], mushrooms (Figure 2). and w8a (Figure The z-axis and y-axis represent the number of communication bits and the training loss, respectively.
Regarding the different compression operators, the experimental results indicate that natural com- pression and random quantization are better than random sparsification for all three algorithms, For

---

QBGD DYAMA
QSGD
DIANA CANITA
DIANA
CANITA
Training toss
Training f02s
Cormunnication ion bits
Communcation bis
Communication bits
Figure I: Performance of different methods for three different compressors (random sparsification, natural compression, and random quantization) the a9a dataset.
Sparsiiicction
OSGD
QSGD
OSGO
DIANA
DIANA
DIANA
Transig
Traniig
Communication Lits
Communicatio bits
Communication bits
Figure 2: Performance of different methods for three different compressors (random sparsification, natural compression, and random quantization) on the mushrooms dataset.
Rancim Sparsiitarion
Natural Compression
Random Gusntirat on
OSGD
OSGB
QSGD
DIANA
DIANA
CANITA
CANITA
CANITA
Trainin 1006
Trainin
12
km bis
Communcation
Cummurication bits
Figure 3: Performance of different methods for three different compressors (random sparsification, natural compression, and random quantization) on the w8a dataset.
instance, in Figure DIANA uses 1.5 10 (random sparsification), 1.0 10 (natural compression), 0.4 x 10th (random quantization) communication bits for achieving the loss 0.4, respectively.
Moreover, regarding the different algorithms, the experimental results indeed show that CANITA converges the fastest compared with both QSGD and DIANA for all three compressors all Figures в validating the theoretical results (see Table and confirming the practical superiority of our accelerated CANITA method.
7 Conclusion
the first gradient method for distributed general convex optimiza- tion provably enjoying the benefits of both communication compression and convergence acceleration. There is very limited work on combing compression and acceleration. Indeed, previous works only focus on the (much simpler) strongly convex setting. We hope that our novel algorithm and analysis can provide new insights and shed light on future work in this line of research. We leave further improvements to future work. For example, one may ask whether our approach can be combined with the benefits provided by multiple local update steps 22 38
In this paper, we proposed CANITA:
42 with additional variance reduction techniques [9] 24 and to what extent one can extend our results to structured nonconvex
problems
22
19
27
21
25
6 35| 5).

---

References
[1] Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. QSGD: Communication-effccenn SGD via gradient quantization and encoding. In Advances in Neural Information Processing Systems, pages 1709-1720, 2017.
[2] Zeyuan Allen-Zhu. Katyusha: The first direct acceleration of stochastic gradient methods. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 1200-1205, ACM, 2017.
[3] Aleksandr Beznosikov, Samuel Horváth, Peter Richtárik, and Mher Safaryan. On biased compression for distributed learning. arXiv:2002. /2410, 2020.
[4] Chih-Chung Chang and Chih-Jen Lin. Libsvm: library for support vector machines. ACM Transactions Intelligent Systems and Technology (TIST), 2(3): 2011.
[5] lyas 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.
[6] Eduard Gorbunov, Konstantin Burlachenko, Zhize Li, and Peter Richtárik, MARINA: Faster non-convex distributed learning with compression. In International Conference Machine Learning, pages 3788-3798. PMLR, arXiv:2102.07845 2021.
[7] Filip Hanzely, Konstantin Mishchenko, and Peter Richtárik. SEGA: variance reduction via gradient sketching. Advances in Neural Information Processing Systems 31, pages 2082-2093, 2018.
[8] Samuel Horváth, Chen-Yu 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: 10988, 2019.
[9] Samuel Horváth, Dmitry Kovalev, Konstantin Mishchenko, Sebastian Stich, and Peter Richtárik. Stochastic distributed learning with gradient quantization and variance reduction. arXiv preprint arXiv:1904.05115. 2019.
[10] Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. SCAFFOLD: Stochastic controlled averaging for federated learning. In International Conference on Machine Learning, pages 5132-5143. PMLR, 2020.
[11] Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. Tighter theory for local SGD on identical and heterogeneous data. In International Conference on Artificial Intelligence and Statistics, pages 4519 4529. PMLR, 2020.
[12] Ahmed Khaled, Othmane Sebbouh, Nicolas Loizou, Robert M Gower, and Peter Richtárik. Unified analysis of stochastic gradient methods for composite convex and smooth optimization. arXiv preprint arXiv:2006.11 11573, 2020.
[13] Sarit Khirirat, Hamid Reza Feyzmahdavian, and Mikael Johansson. Distributed learning with compressed gradients. arXiv preprint 1806 06573, 2018.
[14] Diederik P. Kingma and Jimmy Ba. Adam: method for stochastic optimization. In The 3rd International Conference Learning Representations, 2014.
[15] 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.
[16] Dmitry Kovalev, Samuel Horváth, and Peter Richtárik. Don't jump through hoops and remove those loops: SVRG and Katyusha are better without the outer loop. In Proceedings of the 31st International Conference on Algorithmic Learning Theory, 2020.
[17] Guanghui Lan and Yi Zhou. optimal randomized incremental gradient method. arXiv preprint 1rXiv:1507.02000 2015.
10

---

[18] Guanghui Lan, Zhize Li, and Yi Zhou. A unified variance-reduse reduced accelerated gradient method for convex optimization. In Advances in Neural Information Processing Systems, pages 10462- 10472, 2019.
[19] Zhize Li. SSRGD: Simple stochastic recursive gradient descent for escaping saddle points, In Advances in Neural Information Processing Systems, pages 1521-1531 2019.
[20] Zhize Li. ANITA: An Optimal Loopless Accelcrated Muriance-Reduced Gradient Method. arXiv preprint arXiv:2103.11333, 2021.
[21] Zhize Li. A Short Note of PAGE: Optimal Convergence Rates for Nonconvex Optimization. arXiv preprint (eXix:2/06.9960) 2021.
[22] Zhize Li and Jian Li. A simple proximal stochastic gradient method for nonsmooth nonconvex optimization. In Advances in Neural Information Processing Systems, pages 5569-5579, 2018.
[23] Zhize Li and Jian Li. A fast Anderson-Chebyshen Chebyshev acceleration for nonlinear optmizationn In International Conference on Artificial Intelligence and Statistics, pages 1047-1057. PMLR. 2020.
[24] Zhize Li and Peter Richtárik. A unified analysis of stochastic gradient methods for nonconvex federated optimization. arXiv preprint arXiv:2006.07013, 2020.
[25] Zhize Li and Peter Richtárik. ZeroSARAH: Efficient nonconvex finite-sum optimization with zero full gradient computation. arXiv preprint arXiv:2103.01447, 2021.
[26] Zhize Li, Dmitry Kovalev, Xun Qian, and Peter Richtárik. Acceleration for compressed gradient descent in distributed and federated optimization. In International Conference Machine Learning, pages 5895-5908 PMLR, arXiv:2002.1 13664, 2020.
[27] Zhize Li, Hongyan Bao, Xiangliang Zhang, and Peter Richtárik. PAGE: A simple and optimal probabilistic gradient estimator for nonconvex optimization. In International Conference on Machine Learning, pages 6286-6295. PMLR, arXiv:2008. 10898, 2021.
[28] Hongzhou Lin, Julien Mairal, and Zaid Harchaoui. A universal catalyst for first-order optimiza- tion. In Advances in Neural Information Processing Systems, pages 3384-3392, 2015.
[29] H Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Agüera Arcas. Communication-efficcee learning of deep networks from decentralized data. In International Conference on Artificial Intelligence and Statistics, pages 1273-1282. PMLR, 2017.
[30] Konstantin Mishchenko, Eduard Gorbunov, Martin Takáč, and Peter Richtárik. Distributed learning with compressed gradient differences. arXiv preprint arXiv: 1exXiv::91..00 1901.0929,, 2019.
[31] Yurii Nesterov. A method for unconstrained convex minimization problem with the rate of convergence o(1/k?). In Doklady AN USSR, volume 269, pages 543-547, 1983.
[32] Yurii Nesterov. Introductory lectures on convex optimization: a basic course. Kluwer Academic Publishers, 2004.
[33] Boris T Polyak. Some methods of speeding up the convergence of iteration methods. Ussr computational mathematics and mathematical physics, 4(5):1-17, 1964.
[34] Xun Qian, Peter Richtárik, and Tong Zhang. Error compensated distributed SGD can be accelerated. arXiv preprint ww.Xi::00100009/) 2020.
[35] Peter Richtárik, Igor Sokolov, and Ilyas Fatkhullin. EF21: A new, simpler, theoretically better, and practically faster error feedback. arXiv preprint (0ti::2206.052000 2021.
[36] Mher Safaryan, Egor Shulgin, and Peter Richtárik. Uncertainty principle for communication compression in distributed and federated learning and the search for an optimal compressor. Information and Inference: A Journal of the IMA, 2021.
11

---

[37] 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.
[38] Sebastian U. Stich. Local SGD converges fast and communicates little. In International Conference on Learning Representations, 2019.
[39] Sebastian U. Stich, Lean-Baptiste Cordonnier, and Martin Jaggi. Sparsified SGD with memory.
In Advances in Neural Information Processing Systems, pages 4447-4458, 2018.
[40] Jianqiao Wangni, Jialei Wang. Ji Liu, and Tong Zhang. Gradient sparsification for communication--ciiccintt distributed optimization. In Advances in Neural Information Pro- cessing Systems, pages 1306-1316, 2018.
[41] Tian Ye, Peijun Xiao, and Ruoyu Sun. DERD: general quantization scheme for communication efficiency in bits, arXiv preprint arXiv:2006. / /401, 2020.
[42] Haoyu Zhao, Zhize Li, and Peter Richtárik. FedPAGE: A fast local stochastic gradient method for communication efficient federated learning. arXiv preprint wxXi:2208.00455,, 2021.
12


Reviews:
[{"review_id": "mLg-dtQyH0X", "reviewer": "Reviewer_Jr2k", "summary": "This paper proposes a novel distributed methods with acceleration and communication compression. Authors proof the convergence and show that it is faster than existing SOTA methods.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Positive: \nThis method achieves bigO(1/T^2) convergence rate benefit from the acceleration technique.\n\nNegative:\n1. I do not think this method is suitable for traditional distributed optimization problems or federated optimization problems. In traditional distributed optimization problems, the data size and dimension are large. Calculating \\nabla f_i(w) is slow and usually is worse than calculating a stochastic gradient, even when the model is convex. Furthermore, additional parameters h_t, \\bar{x}_t and w_t will cost huge memory. In federated  learning, usually only few machines participate training in each communication round.\n\n2. Authors should add experiments to compare CANITA with other distributed communication efficient optimization methods. I think a convex optimization experiment can be easily conduct on pytorch and tensorflow. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See above.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2 hours"}, "extra_text": {}}, {"review_id": "fmTBHAabs5g", "reviewer": "Reviewer_Yf7V", "summary": "This paper considers a distributed GD setting where multiple nodes need to jointly minimize the average of individual convex objectives by computing and communicating its compressed local gradients.  The proposed algorithm is shown to achieves an accelerated convergence rate with compressed gradient passing.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper is clearly written and well organized. The proven convergence with the proposed algorithm is faster than a few earlier works.\n\nMy major concern is the usefulness of the studied setting. Requiring each node to compute its gradient (instead of stochastic/sampled gradient) in a distributed optimization does not seem practical. The setting is much less challenging than the conventional distributed (compressed) SGD setting as considered in QSGD in [1].  So it is unfair to say the results in the current paper improve [1] as in table 1.  The order-wise faster convergence (compared to [1]) is not quite surprising to me under this distributed GD setting.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "JucAPL7wQm", "reviewer": "Reviewer_y4iy", "summary": "This paper studies the compressed and accelerated gradient method for nonstrongly convex federated learning. State-of-the-art accelerated convergence rate is established.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: This paper combines the accelerated ANITA in [16] and the compressed DIANA in [23]. I think it is a novel combination of two well-known techniques. It also extends the accelerated and compressed gradient method in [19] from strongly convex problems to nonstrongly convex ones. The convergence rate improvement over previous results is compared clearly.\n\nQuality: The theory is technically solid. State-of-the-art convergence rate for nonstrongly convex problems is proved.\n\nClarity: This paper is written well. The proof is organized very clearly.\n\nSignificance: This paper studies acceleration and compression in federated learning. This is a significant topic. State-of-the-art convergence rate for nonstrongly convex problems is proved. The previous work on acceleration and compression all focus on strongly convex problems. I think the result is significant.\n\nMajor comment:\n\nThe experiment is missing. I suggest to include the numerical experiment in the final version. This paper proposes a new method, rather than reanalyzing a widely used method. So I think the numerical experiment is necessary.\n\nMinor comment:\n\n1. This paper studies the nonstrongly convex problems while [19] studied strongly convex ones. I am interested how fast CANITA converges for strongly convex problems by adoptting the proof techniques used in this paper. Is it faster than the one in [19]? The two rates in the last two lines of Table 1 looks different by letting $\\kappa=\\frac{L}{\\epsilon}$ in the first one. I suggest to include the proof for strongly convex problmes in the supplementary material such that other researchers are likely to use the proof techniques in their work. For example,  the authors may organize the proof in a unified framework for both strongly convex and nonstrongly convex problems. \n\n2. I suggest to remove the proof of Lemma 6 to the supplementary material and inlcude the numurical experiment in page 8.\n\n3. The proof of Theorem 1 in page 16 is redundant, because it is proved in page 9.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No limitation is discussed. I suggest to include the numerical expriment in the final version.", "review_text": "", "extra_scores": {"ethical_concerns": "no", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6 hours"}, "extra_text": {}}, {"review_id": "4TMuQnUzNwH", "reviewer": "Reviewer_CD9C", "summary": "The paper propose a compressed and accelerated gradient method called CANITA for distributed optimization. \nIt improves the the state-of-the-art result which is achieved by DIANA in smooth and convex problems.\nThe main contribution is the (near) optimal algorithm and its theoretical analysis.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality:\n\nThe paper considers a unexplored topic, how to fuse acceleration technique and unbiased compression operator organically. \nThough the algorithm (CANITA) is a combination accelerated ANITA method and compressed DIANA method, the analysis of the resulting algorithm has its own difficulty, i.e., how to analyze the error introduced by the compression operator while not ruining the delicate structure of acceleration for convex problems.\nI think the analysis is new.\n\nQuality:\n\nThe theoretical analysis is valid.\nThe author also provides a proof sketch to illustrate how to construct a potential function for convergence analysis.\n\nClarity:\n\nThe paper is well written and clear.\n\nSignificance:\n\nThe paper improves the state-of-the-art result of non-accelerated compressed algorithms.\nI think the work might give insights on how to combine compression and acceleration optimally.\n\n\n======================================================\n\n\nI have read the author's response.\nI think the author well answers my questions.\nI keep my score.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Some questions:\n1. Though CANITA has a theoretical superiority, it is still unclear how it performs empirically. I suggest the author could add some numerical experiments to investigate the empirical performance and its dependence on the hyper parameters. \n2. I am curious about why not provide the convergence rate of CANITA for strongly convex cases? ANITA could handle convex and strongly convex cases simultaneously. So I naturally expect CANITA could achieve it also. Comparing ANITA and CANITA, I find that the key is how to perform update rule (line 9). So why not use $x_{t+1}=\\frac{1}{1+\\mu \\eta_{t}}\\left(x_{t}+\\mu \\eta_{t} \\underline{x}_{t}\\right)-\\frac{\\eta_{t}}{\\theta_{t}} \\widetilde{\\nabla}_{t}$ in the line 9 of CANITA? Does there exist some fundamental difficulties？\n3. A typo: In line 148, I guess it should be $\\theta_t = \\frac{a_3}{t+a_4}$.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The review committee agreed that the paper is an interesting contribution and hence should be accepted for presentation at Neurips. However, there were some concerns regarding the practical relevance of the work. The authors mentioned in their response that they have run experiments on "logistic regression tasks". I strongly encourage the authors to include those simulations in the final version of the paper.


Decision: Accept (Poster)