CANITA: Faster Rates for Distributed Convex Optimization with Communication Compression
Year: 2021

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 compressed and accelerated gradient method based on ANITA [20] for distributed optimization, which we call CANITA. Our CANITA achieves the first accelerated rate O (√( 1 + √ ω3 n ) L + ω ( 1 ) 1 3 ) , which improves upon the state-of-the-art nonaccelerated rate O ( (1 + ωn ) L + ω+ω ω+n 1 ) of DIANA [12] for distributed general convex problems, where is the target error, L is the smooth parameter of the objective, n is the number of machines/devices, and ω is the compression parameter (larger ω means more compression can be applied, and no compression implies ω = 0). Our results show that as long as the number of devices n is large (often true in distributed/federated learning), or the compression ω is not very high, CANITA achieves the faster convergence rate O (√ L ) , i.e., the number of communication rounds is O (√ L ) (vs. O ( L ) 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).

text: O (√( 1 + √ ω3
n
) L + ω ( 1 ) 1 3 ) , which improves upon the state-of-the-art non-
accelerated rate O (
(1 + ωn ) L + ω2+ω ω+n 1
) of DIANA [12] for distributed general
convex problems, where is the target error, L is the smooth parameter of the objective, n is the number of machines/devices, and ω is the compression parameter (larger ω means more compression can be applied, and no compression implies ω = 0). Our results show that as long as the number of devices n is large (often true in distributed/federated learning), or the compression ω is not very high, CANITA
achieves the faster convergence rate O (√ L ) , i.e., the number of communication
rounds is O (√ L ) (vs. O ( L ) 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).

heading: 1 Introduction
text: 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 the raw data into information is via federated learning [15, 29], where typically a single global supervised model is trained in a massively distributed manner over a network of heterogeneous devices.
Training supervised distributed/federated learning models is typically performed by solving an optimization problem of the form
min x∈Rd
{ f(x) := 1
n n∑ i=1 fi(x) } , (1)
where n denotes the number of devices/machines/workers/clients, and fi : Rd → R is a loss function associated with the data stored on device i. We will write
x∗ := arg min x∈Rd f(x).
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
If more than one minimizer exist, x∗ denotes an arbitrary but fixed solution. We will rely on the solution concept captured in the following definition:
Definition 1 A random vector x̂ ∈ Rd is called an -solution of the distributed problem (1) if
E [f(x̂)]− f(x∗) ≤ ,
where the expectation is with respect to the randomness inherent in the algorithm used to produce x̂.
In distributed and federated learning problems of the form (1), 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 or even billions 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 a model of sufficient quality, and the computation and communication cost associated with a typical communication round.

heading: 1.1 Methods with compressed communication
text: One of the most common strategies for improving communication complexity is communication compression [37, 1, 40, 8, 30, 9, 26, 24]. This strategy is based on the reduction of the size of communicated messages via the application of a 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.
Several recent theoretical results suggest that by combining an appropriate (randomized) compression operator with a suitably designed gradient-type method, one can obtain improvement in the total communication complexity over comparable baselines not performing any compression. For instance, this is the case for distributed compressed gradient descent (CGD) [1, 13, 8, 24], and distributed CGD methods which employ variance reduction to tame the variance introduced by compression [7, 30, 9, 24, 6].

heading: 1.2 Methods with acceleration
text: The acceleration/momentum of gradient-type methods is widely-studied in standard optimization problems, which aims to achieve faster convergence rates (fewer communication rounds) [33, 31, 32, 17, 28, 2, 18, 16, 23, 20]. Deep learning practitioners typically rely on Adam [14], or one of its many variants, which besides other tricks also adopts momentum. In particular, ANITA [20] obtains the current state-of-the-art convergence results for convex optimization. In this paper, we will adopt the acceleration from ANITA [20] to the distributed setting with compression.

heading: 1.3 Can communication compression and acceleration be combined?
text: 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 acceleration/momentum, 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 acceleration/momentum? To the best of our knowledge, no such results exist in the general convex regime, and in this paper we close this gap by designing a method that can provably enjoy the advantages of both compression (compressed communication in each round) and acceleration (much fewer communication rounds).
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 combination of gradient compression and acceleration/momentum was recently achieved by the ADIANA method of Li et al. [26]. However, Li 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
both design a new method to handle the convex case, and perform its analysis. A-priori, it is not clear at all what approach would work.
To the best of our knowledge, besides the initial work [26], we are only aware of two other works for addressing this question [41, 34]. However, both these works still only focus on the simpler and less practically relevant strongly convex setting. Thus, this line of research is still largely unexplored. For instance, the well-known logistic regression problem is convex but not strongly convex. Finally, even if a problem is strongly convex, the modulus of strong convexity is typically not known, or hard to estimate properly.

heading: 2 Summary of Contributions
text: In this paper we propose and analyze an accelerated gradient method with compressed communication, which we call CANITA (described in Algorithm 1), for solving distributed general convex optimization problems of the form (1). In particular, CANITA can loosely be seen as 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 in the general convex regime.

heading: 2.1 First accelerated rate for compressed gradient methods in the convex regime
text: For general convex problems, CANITA is the first compressed communication gradient method with an accelerated rate. In particular, our CANITA solves the distributed problem (1) in
O (√( 1 + √ ω3
n
) L + ω ( 1 ) 1 3 ) communication rounds, which improves upon the current state-of-the-art result
O (( 1 + ωn ) L + ω2+n ω+n 1 ) achieved by the DIANA method [12]. See Table 1 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 ω ≈ 10 (see Section 3.1). Further, if the number of devices/machines is n = 106,
1In this strongly convex column, κ := L µ denotes the condition number, where L is the smooth parameter and µ > 0 is the strong convexity parameter.
2Here QSGD [1] needs an additional bounded gradient assumption, i.e., ‖∇fi(x)‖2 ≤ G2, ∀i ∈ [n], x ∈ Rd.
and the target error tolerance is = 10−6, then the number of communication rounds of our CANITA method isO(103), while the number of communication rounds of the previous state-of-the-art method
DIANA [12] is O(106), i.e., O (√ L ) vs. O(L ). This is an improvement of three orders of magnitude.
Moreover, the numerical experiments in Section 6 indeed show that the performance of our CANITA is much better than previous non-accelerated compressed methods (QSGD and DIANA), corroborating the theoretical results (see Table 1) and confirming the practical superiority of our accelerated CANITA method.

heading: 2.2 Accelerated rate with limited compression for free
text: For strongly convex problems, Li et al. [26] showed that if the number of devices/machines n is large, or the compression variance parameter ω is not very high (ω ≤ n1/3), then their ADIANA method enjoys the benefits of both compression and acceleration (i.e., √ κ log 1 of ADIANA vs. κ log 1 of previous works).
In this paper, we consider the general convex setting and show that the proposed CANITA also enjoys the benefits of both compression and acceleration. Similarly, if ω ≤ n1/3 (i.e., many devices, or limited compression variance), CANITA achieves the accelerated rate √ L vs. L of previous works. This means that the compression does not hurt the accelerated rate at all. Note that the second term( 1 ) 1 3 is of a lower order compared with the first term √ L .

heading: 2.3 Novel proof technique
text: The proof behind the analysis of CANITA is significantly different from that of ADIANA [26], which critically relies on strong convexity. Moreover, the theoretical rate in the strongly convex case is
linear O(log 1 ), while it is sublinear O( 1 ) or O
(√ 1 ) (accelerated) in the general convex case. We
hope that our novel analysis can provide new insights and shed light on future work.

heading: 3 Preliminaries
text: Let [n] denote the set {1, 2, · · · , n} and ‖ · ‖ denote the Euclidean norm for a vector and the spectral norm for a matrix. Let 〈u, v〉 denote the standard Euclidean inner product of two vectors u and v. We use O(·) and Ω(·) to hide the absolute constants.

heading: 3.1 Assumptions about the compression operators
text: We now introduce the notion of a randomized compression operator which we use to 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 [1, 13, 9, 24, 26].
Definition 2 (Compression operator) A randomized map C : Rd 7→ Rd is an ω-compression operator if E [C(x)] = x, E [ ‖C(x)− x‖2 ] ≤ ω‖x‖2, ∀x ∈ Rd. (2)
In particular, no compression (C(x) ≡ x) implies ω = 0.
It is well known that the conditions (2) are satisfied by many practically useful compression operators (see Table 1 in [3, 36]). For illustration purposes, we now present a couple canonical examples: sparsification and quantization.
Example 1 (Random sparsification). Given x ∈ Rd, the random-k sparsification operator is defined by
C(x) := d k · (ξk x),
where denotes the Hadamard (element-wise) product and ξk ∈ {0, 1}d is a uniformly random binary vector with k nonzero entries (‖ξk‖0 = k). This random-k sparsification operator C satisfies
(2) with ω = dk − 1. By setting k = d, this reduces to the identity compressor, whose variance is obviously zero: ω = 0.
Example 2 (Random quantization). Given x ∈ Rd, the (p, s)-quantization operator is defined by
C(x) := sign(x) · ‖x‖p · 1
s · ξs,
where p, s ≥ 1 are integers, and ξs ∈ Rd is a random vector with i-th element
ξs(i) := { l + 1, with probability |xi|‖x‖p s− l, l, otherwise.
The level l satisfies |xi|‖x‖p ∈ [ l s , l+1 s ]. The probability is chosen so that E [ξs(i)] = |xi| ‖x‖p s. This (p, s)quantization operator C satisfies (2) with ω = 2+ d 1/p+d1/2
s . In particular, QSGD [1] used p = 2 (i.e., (2, s)-quantization) and proved that the expected sparsity of C(x) is E [‖C(x)‖0] = O ( s(s+ √ d) ) .

heading: 3.2 Assumptions about the functions
text: Throughout the paper, we assume that the functions fi are convex and have Lipschitz continuous gradient.
Assumption 1 Functions fi : Rd → R are convex, differentiable, and L-smooth. The last condition means that there exists a constant L > 0 such that for all i ∈ [n] we have
‖∇fi(x)−∇fi(y)‖ ≤ L‖x− y‖, ∀x, y ∈ Rd. (3)
It is easy to see that the objective f(x) = 1n ∑n i=1 fi(x) in (1) satisfies (3) provided that the constituent functions {fi} do.
4 The CANITA Algorithm
In this section, we describe our method, for which we coin the name CANITA, designed for solving problem (1), which is of importance in distributed and federated learning, and contrast it to the most closely related methods ANITA [20], DIANA [30] and ADIANA [26].
Algorithm 1 Distributed compressed accelerated ANITA method (CANITA) Input: initial point x0 ∈ Rd, initial shift vectors h01, . . . , h0n ∈ Rd, probabilities {pt}, and positive
stepsizes {αt}, {ηt}, {θt} 1: Initialize: w0 = z0 = x0 and h0 = 1n ∑n i=1 h 0 i 2: for t = 0, 1, 2, . . . do 3: yt = θtxt + (1− θt)wt 4: for all machines i = 1, 2, . . . , n do in parallel 5: Compress the shifted local gradient Cti (∇fi(yt)− hti) and send the result to the server 6: Update the local shift ht+1i = h t i + αtCti (∇fi(wt)− hti) 7: end for 8: Aggregate received compressed local gradient information:
gt = ht + 1n n∑ i=1 Cti (∇fi(yt)− hti) • Compute gradient estimator
ht+1 = ht + αt 1 n n∑ i=1 Cti (∇fi(wt)− hti) •Maintain the average of local shifts
9: Perform update step: xt+1 = xt − ηtθt g t
10: zt+1 = θtxt+1 + (1− θt)wt
11: wt+1 = { zt+1, with probability pt wt, with probability 1− pt 12: end for
4.1 CANITA: description of the method
Our proposed method CANITA, formally described in Algorithm 1, is 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.,∇fi(yt)) and then a shifted version is compressed and sent to the server (See Line 5 of Algorithm 1). The local shifts hti 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 set the shifts to be hti = 0 for all i, t. The server subsequently aggregates all received messages to obtain the gradient estimator gt and maintain the average of local shifts ht+1 (Line 8), and then perform gradient update step (Line 9) and update momentum sequences (Line 10 and 3). Besides, the last Line 11 adopts a randomized update rule for the auxiliary vectors wt which simplifies the algorithm and analysis, resembling the workings of the loopless SVRG method used in [16, 20].
4.2 CANITA vs existing methods
CANITA can be loosely seen as a combination of the accelerated gradient method ANITA of [20], and the variance-reduced compressed gradient method DIANA of [30]. In particular, CANITA uses momentum/acceleration steps (see Line 3 and 10 of Algorithm 1) inspired by those of ANITA [20], and adopts the shifted compression framework for each machine (see Line 5 and 6 of Algorithm 1) as in the DIANA method [30].
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, 9, 12] from an 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 to deal with the extra compression of shifted local gradients in the distributed network. Thus, the obtained gradient estimator gk in Line 8 of Algorithm 1 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 Algorithm 1 make the analysis of CANITA more complicated than that of DIANA. We obtain the accelerated rate O (√ L ) rather than the non-accelerated rate O(L ) of DIANA, and this is
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 1). In order to simplify the expressions appearing in our main result (see Theorem 1 in Section 5.1) and in the lemmas needed to prove it (see Appendix A), it will be convenient to let
F t := f(wt)− f(x∗), Ht := 1 n n∑ i=1 ‖∇fi(wt)− hti‖2, Dt := 1 2 ‖xt − x∗‖2. (4)

heading: 5.1 Generic convergence result
text: We first present the main convergence theorem of CANITA for solving the distributed optimization problem (1) in the general convex regime.
Theorem 1 Suppose that Assumption 1 holds and the compression operators {Cti} used in Algorithm 1 satisfy (2) of Definition 2. For any two positive sequences {βt} and {γt} such that the probabilities {pt} and positive stepsizes {αt}, {ηt}, {θt} of Algorithm 1 satisfy the following relations
αt ≤ 1
1 + ω , ηt ≤
1 L ( 1 + βt + 4ptγt ( 1 + 2pt
αt )) (5) for all t ≥ 0, and 2ω βtn +4ptγt ( 1+ 2pt αt ) ≤ 1−θt, (1− ptθt)ηt ptθ2t ≤ ηt−1 pt−1θ2t−1 , ( ω βtn + ( 1− αt 2 ) γt ) ηt θ2t ≤ γt−1ηt−1
θ2t−1 (6)
for all t ≥ 1. Then the sequences {xt, wt, hti} of CANITA (Algorithm 1) for all t ≥ 0 satisfy the inequality
E [ F t+1 +
γtpt L
Ht+1 ] ≤ θ
2 t pt ηt
( (1− θ0p0)η0
θ20p0 F 0 + ( ω β0n + ( 1− α0 2 ) γ0 ) η0 θ20L H0 +D0 ) ,
(7)
where the quantities F t, Ht, Dt are defined in (4).
The detailed proof of Theorem 1 which relies on six lemmas is provided in Appendix A. In particular, the proof simply follows from the key Lemma 6 (see Appendix A.2), while Lemma 6 closely relies on previous five Lemmas 1–5 (see Appendix C.6). Note that all proofs for these six lemmas are deferred to Appendix C.
As we shall see in detail in Section 5.2, the sequences βt, γt, pt and αt can be fixed to some constants.3 However, the relaxation parameter θt needs to be decreasing and the stepsize ηt may be increasing until a certain threshold. In particular, we choose
βt ≡ c1, γt ≡ c2, pt ≡ c3, αt ≡ c4, θt = c5
t+ c6 , ηt = min
{( 1 + 1
t+ c7
) ηt−1, 1
c8L
} ,
(8)
where the constants {ci} may depend on the compression parameter ω and the number of devices/machines n. As a result, the right hand side of (7) will be of the order O ( L t2 ) , which indicates an accelerated rate. Hence, in order to find an -solution of problem (1), i.e., vector wT+1 such that
E [ f(wT+1)− f(x∗) ] (4) := E [ FT+1 ] ≤ , (9)
the number of communication rounds of CANITA (Algorithm 1) is at most T = O (√ L ) .
While the above rate has an accelerated dependence on , it will be crucial to study the omitted constants {ci} (see (8)), and in particular their dependence on the compression parameter ω and the number of devices/machines n. As expected, for any fixed target error > 0, the number of communication rounds T (sufficient to guarantee that (9) holds) may grow with increasing levels of compression, i.e., with increasing ω. However, at the same time, the communication cost in each round decreases with ω. It is easy to see that this trade-off benefits compression. In particular, as we mention in Section 2, if the number of devices n is large, or the compression variance ω is not very high, then compression does not hurt the accelerated rate of communication rounds at all.

heading: 5.2 Detailed convergence result
text: We now formulate a concrete Theorem 2 from Theorem 1 which leads to a detailed convergence result for CANITA (Algorithm 1) by specifying the choice of the parameters βt, γt, pt, αt, θt and ηt. The detailed proof of Theorem 2 is deferred to Appendix B.
Theorem 2 Suppose that Assumption 1 holds and the compression operators {Cti} used in Algorithm 1 satisfy (2) of Definition 2. Let b = min { ω, √ ω(1+ω)2
n
} and choose the two positive
3Exception: While we indeed choose βt ≡ β for t ≥ 1, the value of β0 may be different.
sequences {βt} and {γt} as follows:
βt =
{ β0 = 9(1+b+ω)2
(1+b)L for t = 0
β ≡ 48ω(1+ω)(1+b+2(1+ω))n(1+b)2 for t ≥ 1 , γt = γ ≡
(1 + b)2
8(1 + b+ 2(1 + ω)) for t ≥ 0.
(10)
If we set the probabilities {pt} and positive stepsizes {αt}, {ηt}, {θt} of Algorithm 1 as follows:
pt ≡ 1
1 + b , αt ≡
1
1 + ω , θt =
3(1 + b)
t+ 9(1 + b+ ω) , for t ≥ 0, (11)
and
ηt =
{ 1
L(β0+3/2) for t = 0 min {( 1 + 1t+9(1+b+ω) ) ηt−1, 1 L(β+3/2) } for t ≥ 1 . (12)
Then CANITA (Algorithm 1) for all T ≥ 0 satisfies
E [ FT+1 ] ≤ O
( (1 + √ ω3/n)L
T 2 + ω3 T 3
) . (13)
According to (13), the number of communication rounds for CANITA (Algorithm 1) to find an -solution of the distributed problem (1), i.e.,
E [ f(wT+1)− f(x∗) ] (4) := E [ FT+1 ] ≤ ,
is at most
T = O √(1 +√ω3 n ) L + ω ( 1 ) 1 3  .

heading: 6 Experiments
text: In this section, we demonstrate the performance of our accelerated method CANITA (Algorithm 1) and previous methods QSGD and DIANA (the theoretical convergence results of these algorithms can be found in Table 1) with different compression operators on the logistic regression problem,
min x∈Rd
f(x) := 1
n n∑ i=1 log ( 1 + exp(−biaTi x) ) , (14)
where {ai, bi}ni=1 ∈ Rd × {±1} are data samples. We use three standard datasets: a9a, mushrooms, and w8a in the experiments. All datasets are downloaded from LIBSVM [4].
Similar to Li et al. [26], we also use three different compression operators: random sparsification (e.g. [39]), natural compression (e.g. [8]), and random quantization (e.g. [1]). In particular, we follow the same settings as in Li et al. [26]. For random-r sparsification, the number of communicated bits per iteration is 32r, and we choose r = d/4. For natural compression, the number of communicated bits per iteration is 9d bits [8]. For random (2, s)-quantization, we choose s = √ d, which means the number of communicated bits per iteration is 2.8d+ 32 [1]. The default number of nodes/machines/workers is 20. In our experiments, we directly use the theoretical stepsizes and parameters for all three algorithms: QSGD [1, 24], DIANA [12], our CANITA (Algorithm 1). To compare with the settings of DIANA and CANITA, we use local gradients (not stochastic gradients) in QSGD. Thus here QSGD is equivalent to DC-GD provided in [24].
In Figures 1–3, we compare our CANITA with QSGD and DIANA with three compression operators: random sparsification (left), natural compression (middle), and random quantization (right) on three datasets: a9a (Figure 1), mushrooms (Figure 2), and w8a (Figure 3). The x-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 compression and random quantization are better than random sparsification for all three algorithms. For
Random Sparsification
Natural Compression
Random Quantization
Random Sparsification
Natural Compression
Random Quantization
Random Sparsification
Natural Compression
Random Quantization
instance, in Figure 1, DIANA uses 1.5×106 (random sparsification), 1.0×106 (natural compression), 0.4× 106 (random quantization) communication bits for achieving the loss 0.4, respectively. Moreover, regarding the different algorithms, the experimental results indeed show that our CANITA converges the fastest compared with both QSGD and DIANA for all three compressors in all
Figures 1–3, validating the theoretical results (see Table 1) and confirming the practical superiority of our accelerated CANITA method.

heading: 7 Conclusion
text: In this paper, we proposed CANITA: the first gradient method for distributed general convex optimization 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 [29, 38, 11, 10, 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].

Review summaries:
The paper propose a compressed and accelerated gradient method called CANITA for distributed optimization.  It improves the the state-of-the-art result which is achieved by DIANA in smooth and convex problems. The main contribution is the (near) optimal algorithm and its theoretical analysis.