BEER: Fast $O(1/T)$ Rate for Decentralized Nonconvex Optimization with Communication Compression
Authors: Haoyu Zhao
Boyue Li
Zhize Li
Peter Richtárik
Yuejie Chi
Venue: NeurIPS 2022 Accept (2022)
Keywords: decentralized optimization
communication compression
nonconvex optimization

Abstract: Communication efficiency has been widely recognized as the bottleneck for large-scale decentralized machine learning applications in multi-agent or federated environments. To tackle the communication bottleneck, there have been many efforts to design communication-compressed algorithms for decentralized nonconvex optimization, where the clients are only allowed to communicate a small amount of quantized information (aka bits) with their neighbors over a predefined graph topology. Despite significant efforts, the state-of-the-art algorithm in the nonconvex setting still suffers from a slower rate of convergence $O((G/T)^{2/3})$ compared with their uncompressed counterpart, where $G$ measures the data heterogeneity across different clients, and $T$ is the number of communication rounds. This paper proposes BEER, which adopts communication compression with gradient tracking, and shows it converges at a faster rate of $O(1/T)$. This significantly improves over the state-of-the-art rate, by matching the rate without compression even under arbitrary data heterogeneity. Numerical experiments are also provided to corroborate our theory and confirm the practical superiority of beer in the data heterogeneous regime.

BEER: Fast (11/T) Rate for Decentralized Nonconvex Optimization with Communication Compression
Haoyu Zhao Princeton University hacyubprinceton.c edu
Boyue Li
Zhize Li Carnegie Mellon University zhizel Candrew. cmu edu
Carnegie Mellon University
Boyuel@andres cmu. edu
Peter Richtárik
Yuejie Chi
King Abdullah University of Science and Technology peter ri
Carnegie Mellon University yuejiecdandrew. cmu, edu
edu. sa
Abstract
Communication efficiency has been widely recognized as the bottleneck for large- scale decentralized machine learning applications in multi-agent or federated envi- ronments. To tackle the communication bottleneck, there have been many efforts design communication-coppeee compressed algorithms for decentralized nonconvex op- timization, where the clients are only allowed to communicate a small amount of quantized information (aka bits) with their neighbors over a predefined graph topology. Despite significant efforts, the state-of- oftee-o--hh-rrrr art algorithm in the nonconvex setting still suffers from slower rate of convergence ((G/T)2//3 compared with their uncompressed counterpart, where measures the data heterogeneity across different clients, and T' is the number of communication rounds. This paper pro- poses BEER, which adopts communication compression with gradient tracking, and shows converges at faster rate of O1)/T). This significantly improves over the ofate-of-the-art rate, by matching the rate without compression even under arbitrary data heterogeneity. Numerical experiments are also provided to corroborate our theory and confirm the practical superiority of BEER data heterogeneous regime.
Introduction
Decentralized machine learning is gaining attention in both academia and industry because of its emerging applications in multi-agent systems such as the internet-of-thingg (IoT) and networked autonomous systems (31 43). One of the key problems in decentralized machine learning is device training, which aims to optimize a machine learning model using the datasets stored on (geographically) different clients, and can be formulated as decentralized optimization problem.
Decentralized optimization aims to solve the following optimization problem without sharing the local datasets with other clients:
min [(x 1 20 RER
Σ f(x;
f(; Di)
where (a;;
D,) := BE..D, & for E [m). and n the total number clients. Here, æ Rd is the machine learning model, [m;; D), fa: D:), and [(x; {i) denote the loss functions of the model ar on the entire dataset D, the local dataset D,, and random data sample &,, respectively. Different
CCoreesoodingg author.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

from the widely studied distributed or federated learning setting where there is central server to coordinate the parameter sharing across all clients, in the decentralized setting, each client can only communication with its neighbors over communication network determined by predefined network topology.
The main bottleneck of decentralized optimization-hhenn it comes to large-scale machine learning applications-is communication efficiency, due to the large number of clients involved in the net- work [3] and the enormous size of machine learning models 4 exacerbated by resource constraints such as limited bandwidth availability and stringent delay requirements. One way to reduce the communication cost is communication compression, which only transmits compressed messages (with fewer bits) between the clients using compression operators. The compression operators come with many design choices and offer great flexibility in different trade-offs of communication and computation in practice. Even though communication compression has been extensively applied to distributed or federated optimization with central server [4 12 6 26
40 41 27], its use in the decentralized setting has been relatively sparse. Most of the existing approaches only apply to and only few consider the general nonconvex
25
the strongly convex setting [39 17 19 29 23
setting [6 51 45
Our contributions This paper considers decentralized optimization with communication compres- sion, focusing on the nonconvex setting due its critical importance in modern machine learning. such as training deep neural networks [21], word embeddings. and other unsupervised learning models (22. Unfortunately, existing algorithms [6 ST 45 suffer from several important drawbacks in the nonconvex setting: they need strong bounded gradient or bounded dissimilarity assumptions to guarantee convergence, and the convergence rate is order-wise slower than their uncompressed counterpart in terms of the communication rounds (see Table
In this paper, we introduce BEER, which is a decentralized optimization algorithm with communica- tion compression using gradient tracking. BEER not only removes the strong assumptions required in all prior works, but enjoys a faster convergence rate in the nonconvex setting. Concretely, we have the following main contributions (see Tables I and 2
1. We show that BEER converges a fast rate of (1/TT) in the nonconvex setting, which im- proves over the state-of off-the-art rate ((1/T2/3) of CHOCO-SGD [16] and Deepsqueeze [51], where T is the number of communication rounds. This matches the rate without compression even under arbitrary data heterogeneity across the clients.
2. We also provide the analysis of BEER under the Polyak- Lojasiewicz (PL) condition (As- sumption 4. and show that BEER converges at a linear rate (see Table 2. Note that strong convexity implies the PL condition, and thus BEER also achieves linear convergence in the strongly convex setting.
3. We rum numerical experiments real-world datasets and show BEER achieves superior competitive performance when the data are heterogencous compared with state-of-the-as baselines with and without communication compression.
To the best of our knowledge, BEER is the first algorithm that achieves O(1/T) rate without the bounded gradient or bounded dissimilarity assumptions, supported by strong empirical performance in the data heterogeneous setting.
Notation Throughout this paper, we use boldface letters to denote vectors, e.g., x E Rdd Let [n] denote the set 21, .n). 1 be the all-one vector, I be the identity matrix, ||-I| denote the Euclidean norm of a vector, and ||= denote the Frobenius norm of a matrix. Let (u, v) denote the standard Euclidean inner product of two vectors u and In addition, we use the standard order notation (-)) to hide absolute constants.
Due to space constraints, additional discussions of related work, further experiments, and the proof details can be found in the appendix.
Problem Setup
In this section, we formally define the decentralized optimization problem with communication compression, and introduce few important quantities and assumptions that will be used in developing our algorithm and theory.

---

Algorithm
Convergence rate
Strong assumption
SQuARM-SGD 45
0
1
+
nG
Bounded Gradient
VnT
DeepSqueeze 51
0
G
G)2/3
Bounded Dissimilarity
T
[C) 2/3
CHOCO-SGD [6
0
Bounded Gradient
BEER (Algorithm)
O ((+)
Table 1: Comparison of convergence rates for existing decentralized methods with communication compression the nonconvex setting. Here, the parameter G refers the quantity either in the bounded gradient assumption -E,,D, f[V E.)l < G² or the bounded dissimilarity assumption E, | f(x, D.) Vf D)I < G2, both of which are very strong assumptions (the bounded dissimilarity assumption is slightly weaker) that BEER does not require. All algorithms support the of stochastic gradients with bounded local variance local clients.
Assumptions
Convergence rate
Theorem
fi is L-smooth
L )1
2(4r--9o)) 97
Theorem
J; is L-smooth
인r S (1 un) "nn' 20
Theorem 3
f satisfies PL condition
Table 2: Summary of the established convergence rates for the proposed BEER algorithm in the nonconvex setting. Here, æ² is the average model all clients, 7j is the step size, t the Lyapunov function (cf. (4)), and is the Pl.-condition parameter (cf. Assumption 4). We do not assume the bounded gradient or bounded dissimilarity assumption.
Decentralized optimization The goal of decentralized optimization is to solve
n
min #ERd
f(x)
Σ f1(z))
where n is the number of clients, f(x) is the global objective function, and f((x) := f(x; D,) Eg fax {,) the local objective function, with æ the parameter of interest, & random data sample drawn from the local dataset D;,
In the decentralized setting, the clients only communicate with their local neighhors over prescribed network topology, which is specified by an undirected weighted graph [[n), E). Here, each node in [n] represents client, and E the set of possible communication links between different clients. Information sharing across the clients is implemented mathematically by the use of mixing matrix W = [way] [0, 1]mx", which defined in accordance with the network topology: we assign a positive weight W.j for any (i,j) E E and Wig = 0 for all (i,j) & E. We make the following standard assumption on the mixing matrix [36].
Assumption (Mixing matrix) The mixing matrix W [w,y] 1],1] is symmetric (WT_ W) and doubly stochastic (W1 = 1,1 W )T). Let its eigenvalues be 1 [Nr(W]] > [>2(W) 2 ... (W)(W),. The spectral gap is denoted by
= 1- 1-1--aa(W)) (0,1).
(2)
The spectral gap of a mixing matrix closely related to the network topology, see Nedić et al. [36 for its scaling with respect the network size (i.e. the number of clients n) for representative network topologies.
Compression operators Compression, the forms of quantization or sparsification, can be used to reduce the total communication cost. We now introduce the notion of randomized compression operator, which is widely used in the decentralizeddffederreed optimization literature, e.g. Tang et al. 49), Stich et al. [47), Koloskova al. [16), Richtárik et al. [40], Fatkhullin et al. [8].

---

Definition (Compression operator) A randomized map C Rd + R is an a-compression operator for all æ E Rd, it satisfies
E [I((x))
5 -=]l]]
a=1²]
a) |
In particular, compression (C æ:) implies =
Compared with the unbiased compression operator used in, c.g., Alistarh et al. M. Khirirat et al. [5], Mishchenko al. [33], Li and Richtárik (24), the compression operator in Definition [ does not impose the additional constraint on the expectation such that [[[(x)] æ. Besides, it is always possible convert an unbiased compression operator into a biased one satisfying Definition T
and thus Definition Tis is a generalization of the unbiased compression operator that allows biased compression. Practical examples of the compression operators are provided in Appendix [B]
Assumptions on functions We now state the assumptions on the functions {Li} and f. Throughout
this paper, assume that f* min (a) exists and f* -oc.
In the nonconvex setting, we assume that the functions (fieej)) are arbitrary functions that satisfy the following standard smoothness assumption.
Assumption (Smoothness) The function f is L-smooth if there exists L 2 O such that
[V/ V (x=))) S L ||> - æ2ll Va,, 22 E R
In addition, we allow local computation to be performed via stochastic gradient updates, where f(())) == (.; denotes local stochastic gradient computed via sample & drawn i.i.d. from Exg) denotes the stochastic gradient computed by a minibatch
D. and Vzf((z) E Va with size drawn i.idd. from D: We assume V fxx) and (x) have bounded variance, which is again standard in the docemtraliized/federaae optimization literature [32 13 16).
Assumption (Bounded variance) There exists constant 2 such that for all [n]] and
Rdd
Ví((2)
-
Vf(l)) so²
For stochastic gradient with minibatch size b, have
o²
E (
In addition, we consider the setting when the function f additionally satisfies the following Polyak-
Eojasiewicz (PI.) condition 37 which can lead to fast linear convergence even when the function nonconvex.
Assumption (PI. condition) There exists some constant μs > O such that for any a E TRdd.
|V/())| (x(s(x)- -*) f*).
Note that the PL condition is weaker assumption than strong convexity, which means that if the objective function of is 4-strongly convex, then the PL condition also holds with the parameter J..
Proposed Algorithm
In this section, we introduce our proposed algorithm BEER for decentralized nonconvex optimization with compressed communication. Before embarking on the description of BEER, we introduce some convenient matrix notation. Since a decentralized setting, the parameter estimates at different clients are typically different, we use X [21, 221, Ø2. =,,] to denote the collection of parameter estimates from all clients, where x; is from client The average of (a;))etr is denoted by X1. Other quantities are defined similarly. With slight abuse of notation, we define
VF(X)
[V fi (f))))
f2(22).....
(xx,)) Rddx

---

Algorithm BEER: BEtter comprEssion for decentRalized optimization
1: Input: Initial point X
Tol
GO = 0, H = 0, V
VF(X)), step size 17, mixing step
size y, minibatch size b.
2: for t= 0, l.... do
3:
X X (W
I)
v
4:
Q C(X -H)
// client i sends Th.s
all its neighbors
5:
H H' + +Q
++1
V V + ( - I) V - V.F(X')
6:
7:
Q C(V G*)
client sends 42,3 neighbors
8:
G G' + +Q+11
9: end for
which collects the local gradients computed at the local parameters. Similarly, the stochastic variant is defined as (xF(X) := (ofi( V2.22 V (zx)). We also allow the compression operator to take vector values, which are applied in column-wise fashion, i.e.. Rdxx.
C(X)= =
We proceed to describe BEER, which is detailed in Algorithm [ using the matrix notation introduced above. At the 1-th iteration, BEER maintains the current model estimates X and the global gradient estimates V across the clients. At the crux of its design, BEER also tracks and maintains two control sequences H and G' that serve as compressed surrogates of X and Vt, respectively. In particular, these two control sequences are updated by aggregating the received compressed messages alone (cf. Line and Line
It then boils down to how carefully update these quantities in each iteration with communication compression, which we now explain in details. To begin, note that for each client i, BEER not only maintains its own parameters (act, of h4 (... }. but also the control variables from its neighbors, namely, {he) (E)(() and (e)))eN()-
Update the model estimate Each client first updates its model x according to Line 3 of (h) JEV()) as a surrogate of {ær (e)(()) the second term aims to achieve better consensus among the clients through mixing, while the last term performs gradient descent update.
By thinking
Update the global gradient estimate Each client i updates the global gradient estimate of+1 according to Line 6 where the last correction term-based on the difference of the gradients at consecutive models tracking is critical: as shall be seen momentarily, it contributes to the key difference from CHOCO- SGD that enables the fast rate of O(1/T) without any bounded dissimilarity or bounded gradient assumptions. Indeed, if we remove the control sequence G and substitute Lines 6 by V1+1 V,F(X++1), recover CHOCO-SGD from BEER.
known as a trick called gradient tracking [38 7 35| The use gradient
Update the compressed surrogates with communication To update (h:) )eN()) each client first computes compressed message q that encodes the difference x/+1 - ht, and broadcasts to its neighbors (cf. Line 4h. Then, each client updates (h)))ev()) by aggregating the received compressed messages {ghh jeeN()) following Line 5 The updates {g]) bevt() can be performed similarly. Moreover, all the compressed messages can sent in a single communication round at one iteration, i.e., the communications in Lines and can be performed at once. This leverages EF21 [40] for communication compression, which a better and simpler algorithm that deals with biased compression operators compared with the error feedback (or error compensation, EF/EC) framework [12 46). Using the control sequence G BEER does not need to apply EF/EC explicitly and can deal with the error implicitly.
c+1
4 Convergence Guarantees
In this section, we show the convergence guarantees of BEER under different settings: the ((1/T) rate the nonconvex setting in Section 4.1 and the improved linear rate under the PI. condition (Assumption 4 in Section 4.2 In Section 4.3 briefly sketch the proof.
5

---

Our convergence guarantees are based on an appropriately designed Lyapunov function, given by
c2p² 0z 22
cap² nL
$ = Ef(x'') - ft
o +
+
S2 +
(4)
nL
n
where the choice of constants {cilim might different from theorem to theorem, Ef(x') represents the sub-optimality gap, and the errors {1)) are defined by
-
22 = : || V P 1 = E H' - x F. 2 = E x I Oi = E V 1'
-
(5)
Here, 2 and 22 denote the compression enrors for X and V when approximated using the compressed surrogates H' and G' respectively, and 22 and f2 denote the consensus errors of X and V
4.1 Convergence in the nonconvex setting
First, we present the following convergence result of BEER in the nonconvex setting when there is no local variance (o² = 0), i.e., use the local full gradient V F(X)) instead of (x*)) in Line Line of Algorithm]]
Theorem (Convergence in the nonconvex setting without local variance) Suppose
Assump- tions] L and 2 hold, and we can compute the local full gradient V f((=)) for any æ. Then there exist absolute constants C1 C22 C3 C42 Coys Cy > such that if we set 7 = C. ap, n ?p? LL, then the
Lyapunov function 4 in 44) it holds
Σ |
2(2u 2x)
T/T
Theorem shows that BEER converges at a rate of O(1/T) when there no local variance (o² 0), which faster than the 13133333 rate by CHOCO-SGD [16] and DeepSqueeze [5]] and the O(1/VT) rate by SQuARM-SGD [5]; see also Table 1
More specifically, achieve + B
iterations communication rounds, where and a are the spectral gap (ef. 2 and the compression parameter (cf. 3)), respectively. In comparison, the state-of-the-art algorithm CHOCO-SGD [T6] converges at rate of O((G/pPaT))//) which translates to iteration complexity of O
e, BEER needs O
with G being
the bounded gradient parameter, namely, RE,-D (ax 2 < G2. Therefore, BEER improves
over CHOCO-SCO not only in terms of a better dependency on but also removing the bounded gradient assumption, which significant since in practice, can be excessively large due to data
heterogeneity across the clients.
The dependency on a of BEER is consistent with other compression schemes, such as CHOCO-SGD DeepSqueeze and SQuARM-SGD for the nonconvex setting, as well as LEAD 30 and EF-C-GT 29 for the strongly convex setting.
As for the dependency on BEER is slightly worse than CHOCO-SGD, where CHOCO-SGD has dependency of O(1/p²) whereas BEER has a dependency of O(1/p²). This degeneration is also in the analysis of uncompressed decentralized algorithms using gradient tracking (48 [54 where the
rate O(1/p²) is worse than the rate of ( /p) for basic decentralized SGD algorithms [14 28 by
a factor of p. In addition, both BEER and CHOCO-SGD use small mixing step size to guarantee convergence, which makes the dependency on P worse than their uncompressed counterparts.
Stochastic gradient oracles BEER also supports the use of stochastic gradient oracles with bounded local variance (Assumption 3) More specifically, have the following theorem, which generalizes Theorem
Theorem (Convergence in the nonconvex setting) Suppose Assumptions 7 and hold. Then there exist absolute constants C1, C22 c3, Cá. Cyy, Cn O, such that we set 7y c,p., 1 Cp7p'" //

---

Algorithm
Communication rounds
Gradient complexity
SQUARM-SGD 45
0
nC
0
nG
e²
bree
DeepSqueeze 51
0
C
g²
0
Ø²²
+
c3
brcc
ucc
c
CHOCO-SGD 16
biee
nel
+
BEER (Algorithm)
O
a² ct
+
22
Table 3: A more detailed comparison of the communication complexity and the gradient complexity with existing decentralized stochastic methods in the nonconvex setting to reach e-accuracy. Here, G again measures the bounded gradient or bounded dissimilarity assumption, o² and denote the gradient variance and batch size respectively. We omit the dependency on the compression ratio and the network topology parameter for brevity.
then for the Lyapunov function & in
it holds
T-1
2(D0 ²T)
6c40²
T Σ E Vf
1/I
cy,baL'
1=
In the presence of local variance, the squared gradient norm of BEER has an additional term that scales on the order of O
(ignoring other parameters). By choosing a sufficiently large
minibatch size 6, i.e. 2 O + [V S e2. without the bounded gradient assumption, thus inheriting similar
BEER maintains the iteration complexity O (aae to reach
advantages over CHOCO-SOO SGD as discussed earlier.
While focus is communication efficiency, gain more insights, Table summarizes both the communication rounds and the gradient complexity for different decentralized stochastic methods. While BEER does require the bounded gradient assumption, may lead to a worse gradient complexity in the data homogeneous setting due to the use of large minibatch size. Fortunately, this only impacts the local computation cost, and does exacerbate the communication complexity, which is often the bottleneck. It is of great interest to further refine the design and analysis of BEER terms of the gradient complexity.
4.2 Linear convergence with PL condition
Now, we show that the convergence of BEER can be strengthened to linear rate with the addition of the PL condition (Assumption 4 Similar to the nonconvex setting, we first show the convergence result without local gradient variance (a 0).
Theorem (Convergence under the PL condition without local variance) Suppose tions I 2 and 4 hold, and we can compute the local full gradient V f(((()) for any æ. Then there exist constants Ct 022 C3, Ca. Coy, Gn > 0, such that if we set 7 a, 1) = G,yp² 2 LL, then for the Lyapunov function 4, in (44, it holds
Assump-
T S (1 pm) Pn-
Theorem demonstrates that under the PL condition, BEER converges linearly to the global optimum iterations, with k = L/u the condition 29 proposed an algorithm that also uses
f", where it finds an e-optimal solution in O number. Note that in the strongly convex case, Liao eтror feedback compression and gradient tracking simultaneously. which achieves a linear rate of convergence with unclear dependencies with salient problem parameters. In comparison, BEER achieves an explicit linear rate of convergence in the strongly convex case as well, given strong convexity implies the condition. In fact, our analysis for nonconvex setting-as will be made evident in our proof-almon implies immediately the linear convergence under the PL condition, thus provides major step forward compared with prior analyses that only considered the strongly convex setting.
Pa log (+)
7

---

Stochastic gradient oracles Under the PL condition, BEER also supports the use of stochastic gradient oracles with bounded local variance (Assumption The following theorem shows that BEER linearly converges neighborhood of size O around the global optimum.
Theorem (Convergence under PL condition) Suppose Assumptions - and hold. Then
there exist absolute constants Ci C22 C3 C4. Cy. Cy such that we set 7 a,a,, 17 oyj Cn
then for the Lyapunov function 22 in (4) it holds
6c40²
DT S (1 (-))) 4o +
Cy CyL.b
4.3 Proof sketch
We now provide proof sketch of Theorem which establishes the O(1/T) rate of BEER in the nonconvex setting using full gradient, highlighting the technical reason of the rate improvement of BEER over CHOCO-SGD. The full proofs of our theorems delegated Appendix [
Recalling the quantities 22 to 22 from 5). which capture the approximation errors using compression and the consensus errors of X and V we would like control these errors by obtaining inequalities of the form:
27 s (1 a)) + b, Vi (1,2,3,4) 4),
where 0 < a, < denotes the size of the contraction, and b, > wraps together other terms which may be dependent on f2j for * i as well the expected squared gradient norm of o', i.e.,
= 1
(6)
Then, by choosing the Lyapunov function properly (cf. 4.) we can show that the Lyapunov function actually descends, and small manipulations lead to the claimed convergence results in Theorem
We now explain briefly how gradient tracking helps BEER. Note that CHOCO SGD also has the control variable H' for the model X therefore in its analysis, it also deals with the quantities 22 and D However, CHOCO-SGD also needs bound the term V'll where V (F(*)) for CHOCO-SGD when using full gradients. Thus, CHOCO --DDOO needs to assume the bounded gradient assumption and only obtain a slower (11/T2/3 convergence rate. In contrast, BEER deals with the term | p by decomposing it using Young's 's inequality, leading to V < (1+ () + (1))
for some 3> 0. Here, 24 can be controlled via the gradient tracking technique (see Line 6 in Algorithm without the bounded gradient assumption, and 22 can be handled using the smoothness assumption (Assumption 2}
Numerical Experiments
This section presents numerical experiments real-world datasets to showease BEER's superior ability to handle data heterogeneity across the clients, by running each experiment on unshuffled datasets and comparing the performances with the state-of-the-ar baseline algorithms both with and without communication compression. The code can be accessed at:
Experiment setup We run experiments two nonconvex problems compare with the baseline algorithms both with and without communication compression: logistic regression with a nonconvex regularizer (52 the a9a dataset (5), and training 1-hidden layer neural network the MNIST dataset 200)
For logistic regression with nonconvex regulaarze, following Wang et al. [52]. the objective function over datum (a, b) is defined as
f(x; (a, b)) log (1 exp(-ba (bax)))))))))))))))){))))) xx)
Σ
x
8

---

0.8
Thaini gnadiess narni
0.5
Teelang accureeg
Tontin sccurecy
0.6
0.6
Triinnng
0.5
2.4
0.0
0.4
3E51
CH3C0-520
3500
32
500
1,000
1,500
2,000
300 1,000
1,500
2,000
10.2 0.4 0.6 08
0
0.2 0.4 0.6 0.
Communicc Soo mesemes
Commuication rounds
Commumiittoo bits 100
Communication
Figure The training gradient norm and testing accuracy against communication rounds (left two panels) and communication bits (right two panels) for logistic regression with nonconvex regularization on unshuffled a9a dataset. Both BEER and CHOCO-SGD employ the biased gsgd, compression [ with b = 5.
where the last term is the nonconvex regularizer and the regularization parameter is set to a = 0.05.
For 1-hidden layer neural network training, we 32 hidden neurons, sigmoid activation functions and cross-entropy loss. The objective function over a datum (a,b) b) is defined as
f(;; (a, b)) = ((softmax( W2 sigmoid Wia + c1) + c2),
where -): denotes the cross-entropy loss, the optimization variable collectively denoted by vec( W1, C12 W2. C2), where the dimensions of the network parameters WT. C1. W2, C2 64 x 784, 64 x 1, 10 x 64, and 10 x 1, respectively.
For both experiments, we split the unshuffled datasets evenly to 10 clients that are connected by a ring topology. By using unshuffled data, we can simulate the scenario with high data heterogeneity across clients. Approximately, for the a9a dataset, 5 clients receive data with label 1 and others receive data with label 0; for the MNIST dataset, client receives data with label i. We use the FDLA matrix [53] as the mixing matrix to perform weighted information aggregation to accelerate convergence.
Results We compare BEER with 1) CHOCO-SGD 17, which is the state-of-the-ar nonconvex decentralized optimizing algorithm using communication compression, and 2) DSGD (28] and D2 [50], which are decentralized optimization algorithms without compression. All algorithms are initialized in the same experiment by the same initial point. Moreover, learning rate 1) = 0.1, batch size = 100, and biased compression operator (gsgd,) [ for BEER and CHOCO-SGD both experiments.
the same best-tuned
Figure and Figure pigu the training gradient norm and testing accuracy against communication rounds and communication bits for logistic regression with nonconvex regularization and 1-hidden- layer neural network training, respectively.
In the nonconvex logistic regression experiment (cf. Figure D. the algorithms with communication compression (BEER and CHOCO-SGD) converge faster than the uncompressed algorithms (DSGD and D in terms of the communication bits. However, CHOCO-SGD fails to converge to small gradient norm solution since it cannot tolerate a high level of data dissimilarity across different clients, and its performance is not comparable to D² In contrast, BEER can converge to a point with a relatively smaller gradient norm, which is comparable to D The performance of testing accuracy is similar to that of the training gradient norm, where BEER achieves the best testing accuracy and also learns faster than the uncompressed algorithms.
Tumning to the neural network experiment (cf. Figure 2). in terms of the final training gradient norm, BEER converges to a solution comparable D² but a lower communication cost, while CHOCO-SGD and DSGD cannot converge due to the data heterogeneity. In terms of testing accuracy, BEER and 2² have very similar performance, and outperform CHOCO-SGD and DSGD.
Convolutional neural network training We further compare the performance of BEER and CHOCO-SGD on training convolutional neural network using the unshuffled MNIST dataset. Specif- ically, the network is consist of three modules: the first module is 2-d convolution layer (1 input channel, 16 output channels, kernel size 5, stride and padding 2) followed by 2-d batch normal- ization, ReL.U activation and 2-d max pooling (kernel size 2 and stride 2); the second module is the same as the first module, except the convolution layer has 16 input channels and 32 output channels; the last module is a fully-connected layer with 1568 inputs and 10 outputs. We adopt the standard

---

Troining graciten moom
Tosting oceureey
0.8
accuaacy
0.8-
0.6
Trakiin 2
BEER DSGO
0.2
0.2
D2
300 1,000 1,500
2,000
500 1,000
1,500
2,00
0.2 10.4
01.
11.5
12
11.2
014
055
US 1
Commmicctiio rounds
Commonication rounds
Conumunication lots.
1015
Commaniictton Lits.jo"
Figure 2: The training gradient norm and testing accuracy against communication rounds (left two panels) and communication bits (right two panels) for classification on unshuffled MNIST dataset using a I-hidden-layer neural network. Both BEER and CHOCO-SGI employ the biased gsgd, compression 1 with b 20.
cross-entropy loss, and simply average each agent's model with its neighbors. Figure shows the testing gradient norm and accuracy against the communication bits. can be seen that BEER outper- forms CHOCO-SGD in terms of both testing gradient converge fast initially, however, due to to the extreme data heterogeneity, their convergence speeds significantly degenerate after short time. BEER keeps improving the objective when CHOCO-SGD hits its error floor, which highlights BEER's 's advantage to deal with data heterogeneity.
and testing accuracy. Both algorithms
0.8
Tellas grationn
0.6
Testing
40
0.4
0.2
0.8
Commumication bits -10P
Commemication bits
Figure 3: The testing gradient norm and testing accuracy against communication bits unshuffled MNIST dataset using a 3-layer convolutional neural network. Both BEER and CHOCO -HODO-SGD employ the biased g compression
II with b 5.
In summary, BEER has much better performance in terms of communication efficiency than CHOCO- SGD in heterogeneous data scenario, which corroborates our theory. BEER also performs similarly or even better than the uncompressed baseline algorithm 17 and much better than DSGD. In addition, by leveraging different communication compression schemes, BEER allows more flexible trade-offs between communication and computation, making it appealing choice in practice.
6 Conclusion
This paper presents BEER, which achieves a faster O(1/T) convergence rate for decentralized non- convex optimization with communication compression, without imposing the bounded dissimilarity bounded gradient assumptions. In addition, faster linear rate of convergence is established for BEER under the PI. condition. Numerical experiments are provided to corroborate our theory on the advantage BEER the data heterogeneous scenario. An interesting direction of future work is to investigate the lower bounds for decentralized (nonconvex) optimization with communication compression. In addition, improving the dependency of BEER with the network topology parameter possibly leveraging the analysis in Koloskova et al. 18] is of interest.
Acknowledgement
The work of Zhao is supported in part by NSF, ONR, Simons Foundation, DARPA and SRC through awards to S. Arora. The work of B. Li, Z. Li and Y. Chi is supported in part by ONR N00014- 19-1-2404, by AFRL under 748750020-2-0504, and by NSF under CCF- 1901 199, CCF-200791 and CNS-2148212 12. B. Li is also gratefully supported by Wei Shen and Xuehong Zhang Presidential Fellowship at Carnegie Mellon University. The work of P. Richtárik supported by KAUST Baseline Research Fund.
10

---

References
[1] D. Alistarh, D. Grubic, J. Li, R. Tomioka, and M. Vojnovic. QSGD: Communication-cfficinn SGD via gradient quantization and encoding. In Advances in Neural Information Processing Systems, pages 1709-1720, 2017.
[2] D. Alistarh, T. Hoefler, M. Johansson, S. Khirirat, N. Konstantinov, and C. Renggli. The conver- gence of sparsified gradient methods. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pages 5977-5987, 2018
[3] D. Bertsekas and J. Tsitsiklis. Parallel and distributed computation: numerical methods. Athena Scientific, 2015.
[4] T. B. Brown, B. Mann, N. Ryder, M. Subbiah, J. Kaplan, P. Dhariwal, A. Neelakantan, Shyam, G. Sastry, A. Askell, et al. Language models are few-shot learners. arXiv preprint 20X 2020.
[5] C.-C. Chang and C.-J. Lin, LIBSVM: a library for support vector machines. ACM transactions on intelligent systems and technology (TIST), 2(3):1-27, 2011. 2011.
[6] R. Das, A. Hashemi, S. Sanghavi, and I. S. Dhillon. Improved convergence rates for non-convex federated learning with compression. arXiv preprint arXiv:2012.04061, 2020.
[7] P. Di Lorenzo and G. Scutari. Next: In-newwork nonconvex optimization. IEEE Transactions on Signal and Information Processing over Networks, 202):120-136, 2016.
[8] I. Fatkhullin, I. Sokolov, E. Gorbunov, Z. Li, and P. Richtárik. EF21 with bells & whistles: Practical algorithmic extensions of modern error feedback. arXiv preprint a 10.00394, 2021.
[9] R. Glowinski and A. Marrocco. On the solution of a class of non linear dirichlet problems by penalty-duality method and finite elements of order one. In Optimization Techniques IFIP Technical Conference, pages 327-333. Springer, 1975.
[10] E. Gorbunov, F. Hanzely, and P. Richtárik. Local SGD: Unified theory and new efficient methods. arXiv preprint arXiv:201 1.02828, 2020.
[11] E. Gorbunov, Burlachenko. Z. Li, and P. Richtárik. MARINA: Faster non-convex distributed learning with compression. In International Conference on Machine Learning, pages 3788-3798. PMLR, 2021.
[12] S. P. Karimireddy, Q. Rebjock, S. Stich, and M. Jaggi. Error feedback fixes signsgd and other gradient compression schemes. In International Conference on Machine Learning, pages 3252-3261. PMLR, 2019.
[13] P. Karimireddy, S. Kale, M. Mohri, S. Reddi, Stich, and A. T. Suresh. SCAFFOLD: Stochastic controlled averaging for federated learning. In International Conference on Machine Learning, pages 5132-5143. PMLR, 2020.
[14] D. Kempe, A. Dobra, and J. Gehrke. bassip-based computation of aggregate information. In 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings. pages 482-491. IEEE, 2003.
[15] S. Khirirat, H. R. Feyzmahdavian, and M. Johansson. Distributed learning with compressed gradients. arXiv preprint arXiv: 06573, 2018.
[16] A. Koloskova, T. Lin. S. U. Stich, and M. Jaggi. Decentralized deep learning with arbitrary communication compression. International Conference on Learning Representations, 2019.
[17] A. Koloskova, S. Stich, and M. Jaggi. Decentralized stochastic optimization and gossip algorithms with compressed communication. International Conference on Machine Learning, pages 3478-3488 PMLR, 2019.

---

[18] A. Koloskova, T. Lin, and S. U. Stich. An improved analysis of gradient tracking for decentral- ized machine learning. Advances in Neural Information Processing Systems, 34:1 143445 2021.
[19] D. Kovalev, A. Koloskova, M. Jaggi, P. Richtarik, and S. Stich. A linearly convergent algorithm for decentralized optimization: Sending less bits for free! In International Conference on Artificial Intelligence and Slutistics, pages 4087-4095. PMLR, 2021.
[20] Y. LeCun, L. D. Jackel, L. Bottou, C. Cortes, J. S. Denker, H. Drucker, I. Guyon, U. A. Muller, E. Sackinger, and P. Simard. Learning algorithms for classification: A comparison on handwritten digit recognition. Neural networks: the statistical mechanics perspective,, (2762
2, 1995.
[21] Y. LeCun, Y. Bengio, and G. Hinton. Deep learning. Nature, 521(7553):436 444, 2015.
[22] B. Li, Z. Li, and Chi. DESTRESS: Computation-optimal and communicaaton-effcceeett decentralized nonconvex finite-sum optimization. SIAM Journal on Mathematics of Data Science, 103):10311105,, 2022.
[23] Y. Li. X. Liu, J. Tang, M. Yan, and K. Yuan. Decentralized composite optimization with compression. arXiv preprini Tit:::0088044448, 2021.
[24] Z. Li and P. Richtárik. A unified analysis of stochastic gradient methods for nonconvex federated optimization. arXiv preprint arXiv:2006.07013, 2020.
[25] Z. and P. Richtárik. CANITA: Faster rates for distributed convex optimization with commu- nication compression. In Advances in Neural Information Processing Systems, 2021.
[26] Z. Li, D. Kovalev, X. Qian, and P. Richtárik. Acceleration for compressed gradient descent in distributed and federated optimization. In International Conference on Muchine Learning, pages 5895-5904. PMLR, 2020.
[27] Z. Li, H. Zhao, B. Li, and Y. Chi. SoteriaFL: A unified framework for private federated learning with communication compression. arXiv preprint urXiv:2206.0998 2022.
[28] X. Lian, C. Zhang, H. Zhang, C.-J. Hsieh, W. Zhang, and Liu. Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pages 3336, 2017.
[29] Y. Liao, 7. Li, K. Huang, and S. Pu. Compressed gradient tracking methods for decentralized optimization with linear convergence. arXiv preprint 2rXiv:2103.13748, 2021.
[30] X. Liu, Y. Li, R. Wang, Tang, and M. Yan. Linear convergent decentralized optimization with compression. In International Conference on Learning Representations, 2020.
[31] A. K. Marvasti, Y. Fu, S. DorMohammadi, and M. Rais-Rohani. Optimal operation of active distribution grids: A system of systems framework. IEEE Transactions on Smart Grid, 5(3): 1228-1237, 2014.
[32] H. B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. Agüera Arcas Communication- efficient learning of deep networks from decentralized data. In International Conference on Artificial Intelligence and Statistics, pages 1273-1282, 2017.
[33] K. Mishchenko, E. Gorbunov, M. Takáč, and P. Richtárik. Distributed learning with compressed gradient differences. arXiv preprint arXiv: 1901109900099 2019.
[34] A. Nedic and A. Ozdaglar. Distributed subgradient methods for multi-agent optimization. IEEE Transuctions on Automatic Control, 54(1):48-61. 2009.
[35] A. Nedic, A. Olshevsky, and W. Shi. Achieving geometric convergence for distributed optimiza- tion over time-varying graphs. SIAM Journal on Optimization, 27(4):2597-233, 2017.
[36] A. Nedić, A. Olshevsky, and M. G. Rabbat. Network topology and communicationn-compttaioo tradcoff's in decentralized optimization. Proceedings of the IEEE, 106(5):953-975 2018.
12

---

[37] B. T. Polyak. Gradient methods for the minimisation of functionals. USSR Computational Mathematics and Mathematical Physies, 3(4):864-87) 878, 1963.
[38] G. Qu and N. Li. Harnessing smoothness to acceerate distributed optimization. IEEE Transac- lions on Control of Network Systems, (33):1245-122) 2017.
[39] A. Reisizadeh, A. Mokhtari. H. Hassani, and R. Pedarsani. An exact quantized decentralized gradient descent algorithm. IEEE Transactions on Signal Processing, 67(19):4934-4947 2019.
[40] P. Richtárik, I. Sokolov, and I. Fatkhullin. EF21: A new, simpler, theoretically better, and practically faster error feedback. arXiv preprint
2021.
[41] Richtárik, I. Sokolov, E. Gasanov, I. Fatkhullin, Z. Li, and E. Gorbunov. 3PC: Three point compressors for communication-efficeen distributed training and a better theory for lazy aggregation. In International Conference Machine Learning, pages 18596-18648. PMLR, 2022.
[42] N. Saunshi, O. Plevrakis. S. Arora, M. Khodak, and H. Khandeparkar. A theoretical analysis of contrastive unsupervised representation learning. In International Conference on Machine Learning, pages 1128-5637. PMLR, 2019.
[43] S. Savazzi, M. Nicoli, and V. Rampa. Federated learning with cooperating devices: A consensus approach for massive loT networks. IEEE Internet of Things Journal, 7(5):4641 4655444414664,,, 2020.
[44] W. Shi, Q Ling, G. Wu, and W. Yin. EXTRA: An exact first-order algorithm for decentralized consensus optimization. SIAM Journal on Optimization, 25(2):944-666, 2015.
[45] N. Singh, D. Data, J. George, and S. Diggavi. Squarm-sgd: Communication momentum sgd for decentralized optimization. IEEE Journal on Selected Areas in Information Theory, (3:954-9699 2021.
[46] S. U. Stich and S. P. Karimireddy. The error-feedback framework: Better rates for sgd with delayed gradients and compressed updates. Journal of Machine Learning Research, 21:1-36, 2020.
[47] S. U. Stich, J.-B. Cordonnier, and M. Jaggi. Sparsified SGD with memory. Advances in Neural Information Processing Systems, 31:4447-4458 2018.
[48] H. Sun. S. Lu, and M. Hong. Improving the sample and communication complexity for decentralized con-convex optimization: Joint gradient estimation and tracking. In International Conference on Machine Learning, pages 9217-9228. PMLR, 2020.
[49] H. Tang, S. Gan, C. Zhang, T. Zhang, and J. Liu. Communication compression for decentralized training. Advances in Neural Information Processing Systems, 31:7652-7662, 2018
[50] H. Tang, X. Lian, M. Yan, C. Zhang, and J. Liu. D²; Decentralized training over decentralized data. In International Conference on Machine Learning, pages 4848-4845 PMLR, 2018.
[51] H. Tang, X. Lian, S. Qiu, L. Yuan, C. Zhang, T. Zhang, and J. Liu. Deepsqueeze: Decentraliza- tion meets error-compensated compression. arXiv preprint arXiv: 0907/99774745 2019.
[52] Z. Wang, K. Ji, Y. Zhou, Y. Liang, and V. Tarokh. SpiderBoost and momentum: Faster stochastic variance reduction algorithms. arXiv preprint 1rXiv:1810 10690, 2018
[53] L. Xiao and Boyd. Fast linear iterations for distributed averaging. Systems & Control Letters, 53(1):65-78, 2004.
[54] R. Xin, U. Khan, and S. kar. Fast decentralized non-convex finite-sum optimization with recursive variance reduction. arXiv preprini arXiv:2008.07428,, 2020.
[55] R. Xin, U. A. Khan, and S. Kar. fast randomized incremental gradient method for decentralized non-convex optimization. IEEE Transactions Automatic Control, 2021.
13

---

[56] K. Yuan, B. Ying, X. Zhao, and A. H. Sayed. Exact diffusion for distributed optimization and learning part Algorithm development. IEEE Transactions on Signal Processing, 67(3): 708-723, 2018.
[57] H. Zhao, K. Burlachenko, Z. Li, and P. Richtárik. Faster rates for compressed federated learning with client-variance reduction. arXiv preprint arX11:2112.13097,,220 2021.
[58] H. Zhao, Z. Li, and P. Richtárik. FedPAGE: A fast local stochastic gradient method for communication-efiitie federated learning. arXiv preprint arXiv:2108.04755, 2021.
[59] M. Zhu and S. Martínez. Discrete-time dynamic average consensus. Automatica, 46(2):322-329, 2010.
14

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See the discussions on the dependency with p in Section 4.1
(c) Did you discuss any potential negative societal impacts your work? [No] This is theoretical work that we don't foresee any negative societal impacts.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix D
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [No]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [No]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you eite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either the supplemental material or as URL? [Yes]
We provided the code for our experiments.
(d) Did you discuss whether and how consent obtained from people whose data you're
using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
15


Reviews:
[{"review_id": "lq9iTKi6-bv", "reviewer": "Reviewer_bXnv", "summary": "In this paper, the authors propose a decentralized nonconvex optimization algorithm with communication compression. With the gradient tracking technique, the convergence rate is improved over the existing ones.", "questions": "1. There is another very relevant work that also considers decentralized optimization with communication compression:\nY. Liao, Z. Li, K. Huang, and S. Pu. Compressed gradient tracking methods for decentralized optimization with linear convergence. arXiv preprint arXiv:2103.13748, 2021.\nPlease clarify the differences (for example, strongly convex and nonconvex).\n2. The comparison in Table 1 is unfair. The other algorithms are stochastic but BEER is deterministic.\n", "limitations": "N/A.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. In this paper, the authors propose a decentralized nonconvex optimization algorithm with communication compression. \n2. With the gradient tracking technique, the convergence rate is improved over the existing ones.\n3. Overall, the writing is smooth, although there are some typos.\n\nWeaknesses: \n1. There is another very relevant work that also considers decentralized optimization with communication compression:\nY. Liao, Z. Li, K. Huang, and S. Pu. Compressed gradient tracking methods for decentralized optimization with linear convergence. arXiv preprint arXiv:2103.13748, 2021.\nPlease clarify the differences (for example, strongly convex and nonconvex).\n2. The comparison in Table 1 is unfair. The other algorithms are stochastic but BEER is deterministic.\n3. The numerical experiments could be strengthened if the authors consider training a deeper neural network, and show the evolution of accuracy with respect to runtime.\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "b-zBO2Mzuip", "reviewer": "Reviewer_AhEM", "summary": "This paper proposes a decentralized algorithm with communication compression named BEER. In the deterministic non-convex setting, BEER improves the convergence rate of existing algorithms to O(1/T), which is a state-of-the-art result. The author also establish the convergence rate of BEER in the stochastic setting or with PL conditions. Numerical experiments have been conducted to validate the results.", "questions": "While the convergence rate established in the deterministic scenario is SOTA, the rate for stochastic settings is not. \n\n1. According to the established rate, BEER cannot converge to the stationary solution even with decaying learning rate. In contrast, other decentralized compression algorithms such as CHOCO-SGD and SQuARM-SGD can converge to the stationary solution with decaying rate. It is a major drawback;\n\n2. The authors argue that by utilizing large enough mini-batches, BEER can converge to the stationary solution. In this setting, its convergence rate is still worse than CHOCO-SGD and SQuARM-SGD if they also utilize large enough mini-batches.\n\n3. Another major drawback is that, under the stochastic setting, BEER does not show a linear speedup rate. In contrast, SQuARM-SGD shows a clear linear speedup term $O(\\sigma^2/\\sqrt{nT})$. In contrast, BEER cannot even have a diminishing term associated with $\\sigma^2$. \n\n4. Also, even in the deterministic non-convex setting, the dependence on the network topology established in existing works (without communication compression) is far better than $O(1/\\rho^3)$. For example, in the following reference, the network topology dependence of the GT algorithm is $O(1/\\rho)$.\n\n[Ref] A.  Koloskova, T. Lin, and S. Stich, An Improved Analysis of Gradient Tracking for Decentralized Machine Learning, NeruIPS 2021.\n\nCan the authors please have a few comments on the above points. Are these drawbacks valid? Can these drawbacks be improved? If not, can the authors provide the reason or insight why these drawbacks are difficult to overcome?\n", "limitations": "Yes", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strength\n\n- BEER works under weaker assumptions. It removes the assumption on bounded gradients and gradient dissimilarity;\n\n\n- In the deterministic setting, BEER achieves the state-of-the art convergence rate in terms of T.\n\n### Weakness\n\n- The convergence rate in the stochastic and non-convex setting is not satisfactory; it is worse than existing algorithms such as SQuARM-SGD\n\n- The dependence on the network topology is not satisfactory; it is worse than existing state-of-the-art algorithms\n\nIn general, the reviewer values the strengths more and hence rates the paper positively. ", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "D8hrxSzp6Tn", "reviewer": "Reviewer_3QWf", "summary": "This paper presents a new decentralized nonconvex optimization algorithm, termed BEER, with communication compression to reduce the number of communication rounds in networked systems. Specifically, the authors introduced two auxiliary variables to track the parameter and global gradient updates. They theoretically showed that the convergence rate was improved over the state-of-the-art and matched the uncompressed counterpart. Additionally, they also analyzed the convergence when the objective satisfies the PL condition. They claimed that the strong bounded gradient assumption can be relaxed using the proposed algorithm. To validate BEER, the authors used two simple benchmark datasets and two simple models to show that the proposed algorithm is comparable to the uncompressed algorithm and better than the best available compressed decentralized algorithm.", "questions": "1. Is $\\Phi_T$ with respect to $T$? Can the authors show it is a constant in the error bound in both Theorem 1 and Theorem 2?\n2. How is the performance of the proposed algorithm when it is applied to larger benchmark datasets and more complex models?", "limitations": "I don't think the authors have adequately addressed the limitations of their proposed approach. It would be better and great to see some discussion regarding this aspect, particularly in terms of the perspective of applications and the comparison with other existing methods.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I think overall the investigated topic in this paper is quite interesting, as communication overhead is a critical issue that needs to be resolved in order to achieve scalability in multi-agent systems. This paper is well written and easy to follow. While I still have a few concerns here that the authors should address to make the current paper more technically solid and sound.\n\n1. The algorithmic framework has to be agent-wise. Though the authors have defined the terminologies well and explain the algorithm clearly. Since the focus of this paper is a decentralized optimization algorithm, it will be clear and straightforward to understand how the parameters are updated. That way, an agent-wise algorithm is better than the current algorithmic framework.\n\n2. The authors defined the Lyapunov function, $\\Phi_t$ , to measure the convergence progress. For Theorem 1 and Theorem 2, the error bounds are actually determined by $\\Phi_T$, which might be with respect to $T$. Hence, it will cancel out the $T$ in the denominator. I wonder if the authors could get something like $\\Phi_0-\\Phi_T\\leq \\Phi_0-\\Phi^{*}$, which will turn the error bound being independent of $\\Phi_T$. This is typically in theoretical analysis. Otherwise, the authors need to make a guarantee that $\\Phi_T$ won’t be with respect to $T$ in the paper. Additionally, by inspecting Theorem 3 and Theorem 4, the authors use $\\Phi_t$ as the measure. Since you have used $f$ in the previous two theorems, why didn’t you follow the same idea?\n\n3. The experimental results are not promising. Though the theoretical analysis looks interesting and decent, to me, the experimental results are not that convincing, due to the only usage of very simple datasets and models. Given the results by baseline methods, BEER actually performs comparably. I think the authors should be presenting more quantitatively to tell how much of gain BEER can achieve. The current discussion is too qualitative. It should be noted that these experiments were conducted by only using simple datasets and models. Then how about with more complicated datasets, such as CIFAR 10, CIFAR 100, ImageNet, and models, such as VGG and ResNet? Moreover, the authors have mentioned different other decentralized optimization algorithms with communication compression in the paper? Then why not compare BEER with them? The authors should present more experimental results to validate the proposed algorithm.\n\n4. Regarding the coefficients for $c_1, c_2, c_3, c_4$ in the Lyapunov function, the authors mentioned in the paper that they depend on different theorems, can the authors give specific values at least for one scenario?\n\n5. Minor comment: The authors have used $\\alpha$ as the compression constant. Then for the nonconvex regularization, they should have used another different character.\n\n***********************************************\nOverall, the responses from the authors clarified my confusion and addressed most of my concerns. While I think this work delivers some useful insights to the community in theory, which is not a reason to just have simple evaluations for validating the proposed method. The authors have claimed that they will have additional experimental results, which can add values to the paper. So I raised my score. However, the authors should take all comments from other reviewers into account to make the draft more technically solid and sound.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept