Linear Convergent Decentralized Optimization with Compression
Authors: Xiaorui Liu
Yao Li
Rongrong Wang
Jiliang Tang
Ming Yan
Venue: ICLR 2021 Poster (2021)
Keywords: Decentralized Optimization
Communication Compression
Linear Convergence
Heterogeneous data

Abstract: Communication compression has become a key strategy to speed up distributed optimization. However, existing decentralized algorithms with compression mainly focus on compressing DGD-type algorithms. They are unsatisfactory in terms of convergence rate, stability, and the capability to handle heterogeneous data. Motivated by primal-dual algorithms, this paper proposes the first \underline{L}in\underline{EA}r convergent \underline{D}ecentralized algorithm with compression, LEAD. Our theory describes the coupled dynamics of the inexact primal and dual update as well as compression error, and we provide the first consensus error bound in such settings without assuming bounded gradients. Experiments on convex problems validate our theoretical analysis, and empirical study on deep neural nets shows that LEAD is applicable to non-convex problems.

Published as a conference paper at ICLR 2021
LINEAR CONVERGENT DECENTRALIZED OPTIMIZA- TION WITH COMPRESSION
Xiaorui Liu', Yao Li Rongrong W Tang' & Ming Yan 3.2 Department of Computer Science and Engineering
Department of Mathematics
Department of Computational Mathematies, Science and Engineering Michigan State University, East Lansing, MI 48823, USA
(xiaorui, 1iyao6, wongron6, tangjilll myan @msu. edu
ABSTRACT
Communication compression has become key strategy to speed up distributed optimization. However, existing decentralized algorithms with compression mainly focus on compressing DGD-type algorithms. They are unsatisfactory in terms of convergence rate, stability, and the capability to handle heterogeneous data. Motivated by primal-dual algorithms, this paper proposes the first LinEAr convergent Decentralized algorithm with compression, LEAD. Our theory de- scribes the coupled dynamics of the inexact primal and dual update as well as compression eπrоr, and we provide the first consensus error bound in such settings without assuming bounded gradients. Experiments on convex problems validate theoretical analysis, and empirical study deep neural nets shows that LEAD is applicable to non-convex problems.
INTRODUCTION
Distributed optimization solves the following optimization problem
:= arg min [((x) = 1 Σ fx(x))
(1)
æERd
with n computing agents and communication network. Each f(()) Rd - is a local objective function agent i and typically defined on the data D; settled at that agent. The data distributions {D;} can be heterogeneous depending on the applications such as in federated learning. The vari- able æ E IR' often represents model parameters in machine learning. A distributed optimization algorithm seeks an optimal solution that minimizes the overall objective function f(x) collectively. According to the communication topology, existing algorithms can be conceptually categorized into centralized and decentralized ones. Specifically, centralized algorithms require global communica- tion between agents (through central agents parameter servers). While decentralized algorithms only require local communication between connected agents and are more widely applicable than centralized ones. In both paradigms, the computation can be relatively fast with powerful computing devices; efficient communication is the key improve algorithm efficiency and system scalability, especially when the network bandwidth is limited.
In recent years, various communication compression techniques, such as quantization and sparsi- fication, have been developed to reduce communication costs. Notably, extensive studies (Seide al. 2014 Alistarh et al., 201 7 Bernstein et al. 2018 Stich et al. 2018 Karimireddy al. 2019 Mishchenko al. 2019; Tang et al.) 2019b; Liu et al. 2020) have utilized gradient compression to significantly boost communication efficiency for centralized optimization. They enable efficient large-scale optimization while maintaining comparable convergence rates and practical performance with their non-com compesseeeee counterparts. This great success has suggested the potential and signifi- cance of communication compression in decentralized algorithms.
While extensive attention has been paid to centralized optimization, communication compression relatively less studied in decentralized algorithms because the algorithm design and analysis

---

Published as a conference paper at ICLR 2021
more challenging in order to cover general communication topologies. There recent efforts trying to push this research direction. For instance, DCD-SGD and ECD-SGD (Tang et al. 201 Sa) introduce difference compression and extrapolation compression to reduce model compression error. (Reisizadeh et al.) b) introduce QDGD and QuanT'mmed-DSGi to achieve exact convergence with small stepsize. DeepSqueeze (Tang al., (019a) directly compresses the local model and compensates the compression error in the next iteration. CHOCO-SGD (Koloskova et al., 2019]] 2020) presents novel quantized gossip algorithm that reduces compression error by difference compression and preserves the model average. Nevertheless, most existing works focus on the compression of primal-only algorithms, i.e., reduce to DGD (Nedic & Ozdaglar 2009 Yuan al.) 2016) or P-DSGD (Lian et al., 2017). They are unsatisfying in terms of convergence rate, stability, and the capability to handle heterogeneous data. Part of the reason is that they inherit the drawback of DGD-type algorithms, whose convergence rate is slow in heterogeneous data scenarios where the data distributions are significantly different from agent to agent.
In the literature of decentralized optimization, it has been proved that primal- -uall algorithms can achieve faster converge rates and better support heterogeneous data (Ling et al. 2015: Shi et al.) 2013 Li al., 2019; Yuan et al., 2020). However, it is unknown whether communication compres- sion is feasible for primal-dum dual algorithms and how fast the convergence can be with compression. In this paper, we attempt to bridge this gap by investigating the communication compression for primal-dual decentralized algorithms. Our major contributions can be summarized as:
We delineate two key challenges in the algorithm design for communication compression in decentralized optimization, i.e., data heterogeneity and compression error, and motivated by primal-dual algorithms, we propose a novel decentralized algorithm with compression, LEAD.
We prove that for LEAD, a constant stepsize in the range (0. 2/ + L)] is sufficient to ensure linear convergence for strongly convex and smooth objective functions. To the best of our knowl- edge, LEAD is the first linear convergent decentralized algorithm with compression. Moreover, LEAD provably works with unbiased compression of arbitrary precision.
We further prove that if the stochastic gradient is used, LEAD converges linearly to the O(o²) neighborhood of the optimum with constant stepsize. LEAD is also able to achieve exact con- vergence to the optimum with diminishing stepsize.
Extensive experiments on convex problems validate our theoretical analyses, and the empirical study on training deep neural nets shows that LEAD is applicable for nonconvex problems. LEAD achieves state-of-art computation and communication efficiency all experiments and significantly outperforms the baselines heterogeneous data. Moreover, LEAD is robust to parameter settings and needs minor effort for parameter tuning.
2 RELATED WORKS
Decentralized optimization be traced back to the work by Tsitsiklis et al. (1986). DGD (Nedic & Ozdaglar 2009) is the most classical decentralized algorithm. is intuitive and simple but con- verges slowly due the diminishing stepsize that is needed to obtain the optimal solution Yuan et al. 2016). Its stochastic version D-PSGD (Lian et al., 2017) has been shown effective for train- ing nonconvex deep learning models. Algorithms based on primal-dual formulations or gradient tracking are proposed to eliminate the convergence bias in DGD-type algorithms and improve the convergence rate, such D-ADMM (Mota et al. 2013). DLM (Ling al.) 2015). EXTRA (Shi et al. 2015), NIDS (Li et al. 2019), D (Tang et al. 2018b), Exact Diffusion Yuan et al. 2018), OPTRA(Xu et al. 2020)) DIGing (Nedic et al. 2017). GSGT (Pu & Nedić (020), etc.
Recently, communication compression is applied to decentralized settings by Tang et al. 2018a)... It proposes two algorithms, i.e., DCD-SGD and ECD-SGD, which require compression of high aceu- racy and are not stable with aggressive compression. Reisizadeh et al.] (2019a b) introduce QDGD and QuanTimed-DSGD to achieve exact convergence with small stepsize and the convergence is slow. DeepSqueeze (Tang al. 2019a) compensates the compression error to the compression in the next iteration. Motivated by the quantized average consensus algorithms, such as (Carli et al, 2010), the quantized gossip algorithm CHOCO-Gosee (Koloskova al. 2019) converges linearly to the consensual solution. Combining CHOCO- CHOCO--ossip and D-PSGD leads to a decentralized algo- rithm with compression, CHOCO-SGD, which converges sublinearly under the strong convexity and
2

---

Published as a conference paper at ICLR 2021
gradient boundedness assumptions. Its nonconvex variant is further analyzed in (Koloskova al. 2020). A new compression scheme using the modulo operation is introduced in (Lu De Sal 2020) for decentralized optimization. A general algorithmic framework aiming to maintain the linear con- vergence of distributed optimization under compressed communication is considered (Magnússon et al. 2020). It requires contractive property that is not satisfied by many decentralized algorithms including the algorithm in this paper.
3
ALGORITHM
We first introduce notations and definitions used this work. We use bold upper-case letters such X define matrices and bold lower-case letters such vectors with all ones and zeros, respectively. Their dimensions will be provided when necessary. Given two matrices X, Y E R"xd, we define their inner product as (X, Y) tr( YY)
define vectors. Let and 0 be
Y) and the for
norm as ||||| = (X, We further define (X, Y)p tr(X PY) and |X = V(x, X) (x,x) any given symmetric positive semidefinite matrix P RTx=, For simplicity, we will majorly use the matrix notation in this work. For instance, each agent holds an individual estimate E Ie of the global variable æ E Rd. Let X* and (X* be the collections of {o, 1i= and { which are defined below:
X
[ ....,,.......................... #1
RR VF(X*) [V ... V (+))) Raxd
We use VF ) to denote the stochastic approximation of ( With these notations, the for all i. In this paper, we need the average of all rows in X and (F( so we define X = (1 and VF(X*) = (1 )F)((*)))/ They are row vectors, and we will take transpose if we need a column vector. The pseudoinverse of matrix M is denoted M The largest, ith-largest, and smallest nonzero eigenvalues of a symmetric matrix M are Amax (M), A,MM,, and Amiu (M).
update X ++1 = X VVF( +*) means that x/+1 = o f : <
Assumption (Mixing matrix). The connected network G = {V,E} consists of node set =
{1,2.... ...,....,T) , and undirected edge set E. The primitive symmetric doubly-stochastie matrix W
[wyj] E Ruxa encodes the network structure such that Wij = if nodes and j are not connected and cannot exchange information.
Assumption I iimples that -1 < A (W)= S WW) < -.. Se (W) < \1 (W) = and W1 =
(iiao & Boyd, 2004, Shi et al. 2015). The matrix multiplication g++ W & describes that agent takes weighted sum from its neighbors and itself, i.e., x E EjEN.U(A) Wyyaf, where N; denotes the neighbors of agent i.
R+1
3.1 THE PROPOSED ALGORITHM
The proposed algorithm LEAD solve problem 1 is showed in Alg. D with matrix notations for conciseness. We will refer to the line number in the analysis. A complete algorithm description from the agent's perspective
be found in Appendix A The motivation behind Alg.
D is to achieve two 0) and (b) convergence ((*)T x²). We first discuss how
goals: (a) consensus (a:) (X*)T=
goal (a) leads to goal (b) and then explain how LEAD fulfills goal (a).
In essence, LEAD runs the approximate SGD globally and reduces the exact SGD under sensus. One key property for LEAD is 1 D 0, regardless of the compression error in Y W)Z
Raxd holds because that for the initialization, we require D' (I-W)Z for some
e.g., D = Oaxd and that the update of D ensures D E Range(I - W) for all k and 1 [I W)
as we will explain later. Therefore, multiplying (1/n)ITx 7 on both sides of Line 7 leads to a global average view of Alg.
X X -VVF(FX
which doesn't contain the compression error. Note that this is an approximate SGD step be- cause, shown in ( the gradient (F( g*) is not evaluated
global synchronized model X However, if the solution converges to the consensus solution, i.e., x (X+)T + 0, then Eg+ (VF(X* (x c+)] + and (3) gradually reduces to exact SGD.
3

---

Published as a conference paper at ICLR 2021
Algorithm LEAD
Input: Stepsize 7. parameter (a: 7), X H D = W)z for any Z
Output: X or 1/n Ei= X
1: H = WH
9: procedure COMM(Y H, Hw)
2: X X -/VVF(X )
10:
Q COMPRESS(Y H)
3: for k 1, K - do
11:
Y H+Q
4:
Y = = /F(( ; (0)) Dj
12:
Y,, = H + WQ
5:
Yk, Y H H COMM Y H H
13:
H
aY
6:
D = =D g + 2y 2(= Y
14:
H = (H-a)H aY
7:
X x VVF(( ; m/D
15:
Return: Y.Y.: H, H.,
8:
end for
16: end procedure
With the establishment of how consensus leads to convergence, the obstacle becomes how achieve consensus under local communication and compression challenges. It requires addressing two is- sues, i.e., data heterogeneity and compression erro. To deal with these issues, existing algorithms, such as DCD-SGD, ECD-SGD, QDGD, DeepSqueeze, Moniqua, and CHOCO-SGD, need a dimin- ishing or constant but small stepsize depending on the total number of iterations. However, these choices unavoidably cause slower convergence and bring in the difficulty of parameter tuning. In contrast, LEAD takes different way solve these issues, as explained below.
Data heterogeneity. It is common in distributed settings that there exists data heterogeneity among agents, especially real-world applications where different agents collect data from different sce- narios. In other words, we generally have fi()) 7 [)( for i j. The optimality condition of problem (1) gives 1 VF(X*) O, where X [x:". ,.... , x=) is consensual and optimal so- lution. The data heterogeneity and optimality condition imply that there exist least two agents and such that V fxx") لf 0 and (x²" of 0. As result, simple D-PSGD algorithm cannot converge to the consensual and optimal solution as X + WX nB (F(X*; ; even when the stochastic gradient variance is zero.
Gradient correction. Primal-dual algorithms or gradient tracking algorithms are able to convergence much faster than DGD-type algorithms by handling the data heterogeneity issue, introduced in Section 2 Specifically, L.AD is motivated by the design of primal-dual algorithm NIDS (Li et al. 2019) and the relation becomes clear if we consider the two-step reformulation of NIDS adopted in (Li & Yan 2019):
I-W (X - V/X('* - -,)x)))))>>))))
D D
(4)
2n
x X ,/(F* D1
(5)
where X and D represent the primal and dual variables respectively. The dual variable D plays the role of gradient correction. As k - co, we expect D* + - VF(X*) and X will converge X* via the update in 5 since D++1 corrects the nonzero gradient (X(x)) asymptotically. The key design of Alg.
to provide compression for the auxiliary variable defined as Y x (X*) - DD Such design ensures that the dual variable D lies Range(I W), which is essential for convergence. Moreover, it achieves the implicit error compression explain later. To stabilize the algorithm with inexact dual update, we introduce a parameter y to control the stepsize in the dual update. Therefore, if we ignore the details of the compression, Alg can be concisely written as
will
Y X </ D/
k++ D* +
w)
2n
X = - - DD
where V represents the compression of 4 and F(X:; (*) denote the stochastic gradients.
4

---

Published as a conference paper at ICLR 2021
Nevertheless, how to compress the communication and how fast the convergence we attain with compression error are unknown. In the following, we propose to carefully control the compression error by difference compression and error compensation such that the inexact dual update (Line 6) and primal update (Line 7) can still guarantee the convergence as proved in Section
Compression error. Different from existing works, which typically compress the primal variable X or its difference, LEAD first construct an intermediate variable Y* and apply compression to obtain its coarse representation Y as shown in the procedure COMM(Y, H H.:):
Compress the difference between Y and the state variable H as Q: Q is encoded into the low-bit representation, which enables the efficient local communication step Y H + WQ. It is the only communication step in each iteration.
Each agent recovers its estimate Y by Y = H + Q and we have Y. WY.
States H and H. are updated based on Y and Y.., respectively. We have H., = WH.
By this procedure, we expect when both Y and H converge to X*, the compression error vanishes asymptotically due to the assumption we make for the compression operator in Assumption 2
Remark 1. Note that difference compression is also applied in DCD-PSGD (Tang et al. (208a)) and CHOCO-SGD (Koloskova al. 2019), but their state update is the simple integration of the compressed difference. We find this update is usually too aggressive and cause instability as showed in our experiments. Therefore, we adopt a momentum update H = (1 H + aY motivated from DIANA (Mishchenko et al. 2019), which reduces the compression error for gradient compression in centralized optimization.
Implicil error compensation. On the other hand, even if the compression error exists, LEAD es- sentially compensates for the error in the inexact dual update (Line 6), making the algorithm more stable and robust. To illustrate how it works, let E Y Y denote the compression error and e be its i-th row. The update of * gives
D*+1_ = D
Y (Y* 2m
Y = D* +
Y 2m
(I
w)Y +
Y (E* WE*) 2m
where- WE indicates that agent spreads total compression error ΣyEM. Wyee - to all agents and E* indicates that each agent compensates this error locally by adding et back. This error compensation also explains why the global view in (3) doesn't involve compression error.
Remark 2. Note that in LEAD), the compression error is compensated into the model x through Line 6 and Line 7 such that the gradient computation in the next iteration is aware of the compression error. This has some subtle but important difference from the error compensation or error feedback in (Seide al.) [2014] Wu et al.) 2018 Stich et al.) 20188] Karimireddy et al. 2019 Tang et al. 2019b Liu et al.] -2020- Tang et al.] 2019a), where the error is stored in the memory and only compensated after gradient computation and before the compression.
Remark 3. The proposed ulgorithm, LEAD in Alg.
recovers NIDS Li et al. 2019). D2 Tang
al. 2018b), Exact Diffisiio (Yuan et al. 2018 These connections established in Appendix
4 THEORETICAL ANALYSIS
In this section, we show the convergence rate for the proposed algorithm LEAD. Before showing the main theorem, we make some assumptions, which are commonly used for the analysis of decen- tralized optimization algorithms. All proofs are provided in Appendix E
Assumption 2 (Unbiased and C-contracted operator). The compression operator Q : R Rd
is unbiased, i.e., EQ(x) æ. and there exists C 2 0 such that El[ Q()) 113 < C' for all x Idd.
Assumption 3 (Stochastic gradient). The stochastic gradient V f. E) unbiased, i.e. E, ( E) (i()), and the stochastic gradient variance is bounded: Eg f(
v ft(()) of for all E [n]. Denote o² -.
5

---

Published as a conference paper at ICLR 2021
Assumption 4. Each fi is L-smooth and p-strongly comvex with L 2 μ 0, L.e.. for 1,2,.... and V', E Rd, we have
f(() + (Vf((y), y)
p. 2
x y1l² S f((x) S f(()) + (Vi(l)) x y)
L 2
yll
Theorem (Constant stepsize). Let (X* Hd, D be the sequence generated from Alg. 7 and X*
is the optimal solution with D = (x Under Assumptions for any constant stepsize n E (0, 2/ [p++ + L)}, if the compression parameters a and y satisfy
0, {
(3C' + 1)3" [2 - un pT) })
2pm - pm)
E
(9)
2(1 + C)* min {2- B7 1un(2 mm)
CB7
E
(10)
14 Bry
with 3 = Amax W). Then, in total expectation we have
1 Ec <P=EC* + +
(11)
n
where
= =1==aaaaa|x*
-x11 (2n2/1) />) D* D' (I-Wt + +ai |H -X1
1-mmm122 mm)
7 2Amax (II w)t)' 1 1,01 C5yy +2
4(1+C)
p max
1-010
The result holds for C ->
Corollary (Complexity bounds). Define the condition numbers of the objective function and com- munication graph KG f and Kig
Amax (I (I-W) respectively. Under the same setting in
X (I- W)
Theorem we can choose 11 = 2.7 =minf CBny (1+3013) ). and a 0 ( such that
1 -
max {1 01-0( (1 (1+ (1- (1-)))))) o Creyrig! (
1
With full-gradient (i.e., 0), we obtain the following complexity bounds:
LEAD converges to the e-accurate solution with the iteration complexity
((11 + C)y + kig) + CKtytg)) log 1 2)
When C (i.e., there is no compression), we obtain p -
and the iteration complexity O ((1s + Ky) ky) log This exactly recovers the convergence rate of NIDS (Li et al. 2019).
k.)) log log ! which also k. the asymptotical complexity is O ( +xg)
When C' S
recovers that of NIDS (Li et al. 2019) and indicates that the compression doesn't harm the convergence in this case.
tg With = (or C S "yagttyta, and fully connected communication graph (i.e., we have B = and Kg 1. Therefore, obtain p 1 -1-0 Keg complexity bound {l This recovers the convergence rate of gradient descent Nes-
W 11
( and the
terov 2013).
Remark 4. Under the setting in Theorem 1 LEAD converges linearty to the O neighborhood of the optimum and converges linearly exactly to the optimum if full gradient is used, e.g. a 0. The linear convergence of LEAD holds when 1) < L/L, but omit the proof.
Remark 5 (Arbitrary compression precision). Pick any y E (0, 2/p L)}, based on the compression-relates constant C and the network-related constant B, we can select 7 and a in tain ranges to achieve the convergence. It suggests that LEAD supports unbiased compression with arbitrary precision, i.e., any C > O.

---

Published as a conference paper at ICLR 2021
Corollary 2 (Consensus error). Under the same setting in Theorem 1. let x averaged model and H H', then all agents achieve consensus the rate
1 Ei= ot
be the
2C
20²
x. x²11"
n p +
"
(12)
where p is defined as in Corollary 7 with appropriate parameter settings.
Theorem 2 (Diminishing stepsize). Let (X* ", DE, be the sequence generated from Alg. 20g
Land
X is the optimal solution with D ( Under Assumptions 1 4
if 630405k+2 and
C9Tl. in total expectation we have Nkk = 84t by taking ag = C(1+C)*
E 1 - 11'1² O (1)
(13)
where 01, 00,02,00 03. 0g and 05 are constants defined in the proof. The complexity bound for arriving at the e-accurate solution is (
Remark 6. Compared with CHOCO-SGI, LEAD requires unbiased compression and the conver- gence under biased compression not investigated yet. The analysis of CHOCO-SGH relies on the bounded gradient assumptions, i.e., (a))l < G. which is restrictive because it conflicts with the strong convexity while LEAD doesn't 't need this assumption. Moreover in the theorem of CHOCO-SGD, it requires specific point set y while LEAD only requires ? to be within rather large range. This may explain the advantages of LEAD over CHOCO-SGD in terms of robustness parameter setting.
NUMERICAL EXPERIMENT
We consider three machine learning problems - 62 -egguullrri linear regression, logistic regression, and deep neural network. The proposed LEAD is compared with QDGD (Reisizadeh et al. 2019a). DeepSqueeze (Tang et al., 9a), CHOCO-SGD (Koloskova et al. 2019), and two non-compressed algorithms DGD (Yuan et al. 2016) and NIDS (Li et al. 2019)..
Setup. We consider eight machines connected in ring topology network. Each agent can only exchange information with its two I-hop neighbors. The mixing weight is simply set as 1/3. For compression, we use the unbiased b-bits quantization method with oc-nomm
20011) [c]
Q = (1|=1| 2- (b-1) sign(z))
+
(14)
||0||0
where is the Hadamard product, [2]] the elementwise absolute value of æ, and is a random vec- tor uniformly distributed in [o, 1]d Only sign(#) (x), norm || and integers in the bracket need to be transmitted. Note that this quantization method is similar to the quantization used in QSGD (Alistarh) et al. 2017) and CHOCO-SGD (Koloskova et al. (201)), but we use the co-norm scaling instead of the 2-norm. This small change brings significant improvement on compression precision as justified both theoretically and empirically in Appendix C In this section, we choose 2-bit quantization and
quantize the data blockwise (block size 512).
For all experiments, we tune the stepsize 7 from f0.01, 0.05, 0.1, For QDGD, CHOCO-SGI and Deepsqueeze, 7 is tuned from (0.01, 0.2, 0.4, 0.6, 0.8, 1.0]. Note that different notations are used in their original papers. Here we uniformly denote the stepsize parameter in these algorithms as 7y for simplicity. For LEAD, we simply fix a = 0.5 and y = 1.0 for validate in the parameter
1) and the additional
all experiments since find LEAD is robust to parameter settings sensitivity analysis in Appendix D.I This indicates the minor effort needed for tuning LEAD. Detailed parameter settings for all experiments
summarized in Appendix D.3
Linear regression. We consider the problem: f(x) = -E (|, -,,:=bbb:: +||==11))11
Data matrices A, E 200 and the true solution is randomly synthesized. The values b, are generated by adding Gaussian noise to A,æ'. We let À 0.1 and the optimal solution of the linear regression problem be x². We use full-batch gradient to exclude the impact of gradient variance. The perfor- mance is showed in Fig. [ The distance x² in Fig. Ta and the consensus error in Fig. 1c verify
7

---

Published as a conference paper at ICLR 2021
that LEAD converges exponentially the optimal consensual solution. It significantly outperforms most baselines and matches NIDS well under the same number of iterations. Fig. Tb demonstrates the benefit of compression when considering the communication bits. Fig. Id shows that the com- pression error vanishes for both LEAD and CHOCO-SGD while the compression error pretry large for QDGD and DeepSqueeze because they directly compress the local models.
10
10
10
10
10 -2
10
DGD1 32 1i90
DGD 32 20x)
10
NDS 322 bh5)
10
MDS: 32 6Rs)
QDGD
00CD
10
10
2
(a))
26
50
75
100
125
1000000 3000000
Epoch
Bits transmilled
(a)
X
X
X
X
1|
10
10
10
Conserauus Entor
Compresioo Error
10"
10
10
0G2:32 (32 2ea)
32 ais)
10
10
GD:2 hi))
10 -3
GDGD 12
DeepSrasna (2i)))
DespSiquaaze
10
CHOCO (2b8))
10
bis)
Epoch
Epoch
(c) X
nx1 x
(d) Compression error
Figure 1: Linear regression problem.
Logistic regression. We further consider logistic regression problem on the MNIST dataset. The regularization parameter is 10-1 We consider both homogeneous and heterogeneous data settings. In the homogeneous setting, the data samples are randomly shuffled before being uniformly par- titioned among all agents such that the data distribution from each agent is very similar. In the heterogeneous setting, the samples are first sorted by their labels and then partitioned among agents. Due to the space limit, we mainly present the results in heterogeneous setting here and defer the ho- mogeneous setting to Appendix D.2 The results using full-batch gradient and mini-batch batch gradient (the mini batch size is 512 for each agent) showed in Fig. (2 and Fig. respectively and both settings shows the faster convergence and higher precision of LEAD.
DGD (32 bits)
DGD (32 bits)
NIDS (32
NIDS (32
QDGD (2 bits)
CDGD bits)
DeepSqueeze
16'
CHOCO-SGO (2 bits)
CHOCO.SGD (2 bits)
1O05
(2 bits)
3x10
Epoch
Bila transmittedd
1670
(a) Loss f(X
(b) Loss f(x*)
Figure Logistic regression problem in the heterogeneous case (full-batch gradient).
8

---

Published as a conference paper at ICLR 2021
1.1
11
DGD (32 bits)
DGD (32 bils)
NIDS (52 bits)
NIDS (32 bits)
QDGD (2 bits)
QDGD bits)
0.8
DeeuSeue bits)
0.8
DeepSqueece (2 bits)
CHOCO-SGD (2 bits)
CHOCO-SGD (2 bits)
bits)
Lose
07
(2 bits)
0.6
0.5
0.6
transmilted
160
(a) Loss f(x²)
(b) Loss f(x*)
Figure 3: Logistic regression in the heterogeneous case (mini-batch gradient).
Homogeneous data
Heterogeneous data
DGD (32 bits)
DGD (32 bits)
NIDS (32 bits)
NISS (32 bits)
20
QDGD (2 bits)
GDGD' (2 bits]
DeepSqueez0 bits)
DeepSqueeze (2 bits)
1.5
SHOCO-SGD (2 bits)
CHOCO-SGD* (2 bits)
L099
LEAD (2 bils)
Lops
LEAD (2 bits)
1.0
Bits transmitted
1014
Bits transmitted
1014
(a) Loss f(X*)
(b) Loss f(x*)
Figure 4: Stochastic optimization on deep neural network (* means divergence).
Neural network. We empirically study the performance of LEAD in optimizing deep neural net- work by training AlexNet (240 MB) on CIFARIO dataset. The mini-batch size 64 for each agents. Both the homogeneous and heterogeneous case are showed in Fig. 4 In the homogeneous case, CHOCO-SGI, DeepSqueeze and LEAD perform similarly and outperform the non-compressed variants in terms of communication efficiency, but CHOCO-SGD and DeepSqueeze need more ef- forts for parameter tuning because their convergence is sensitive to the setting of 7. In the hetero- geneous cases, LEAD achieves the fastest and most stable convergence. Note that in this setting, sufficient information exchange is more important for convergence because models from differ- ent agents are moving significantly diverse directions. In such case, DGD only converges with smaller stepsize and its communication compressed variants, including QDGD, DeepSqueeze and CHOCO-SGD, diverge in all parameter settings we try.
In summary, our experiments verify our theoretical analysis and show that LEAD is able to handle data heterogeneity very well. Furthermore, the performance of LEAD is robust to parameter settings and needs less effort for parameter tuning, which is critical in real-world applications.
6 CONCLUSION
In this paper, we investigate the communication compression in decentralized optimization. Mo- tivated by primal-dual algorithms, a novel decentralized algorithm with compression, LEAD, is proposed to achieve faster convergence rate and to better handle heterogeneous data while enjoy- ing the benefit of efficient communication. The nontrivial analyses on the coupled dynamics of inexact primal and dual updates as well compression error establish the linear convergence of LEAD when full gradient is used and the linear convergence to the ((a²) neighborhood of the optimum when stochastic gradient is used. Extensive experiments validate the theoretical analysis and demonstrate the state-of-the-ar efficiency and robustness of LEAD. LEAD is also applicable non-convex problems as empirically verified in the neural network experiments but we leave the non-convex analysis as the future work.

---

Published as a conference paper at ICLR 2021
ACKNOWLEDGEMENTS
Xiaorui Liu and Dr. Jiliang Tang are supported by the National Science Foundation (NSF) un- der grant numbers CNS- 181-18, IIS- 192828,, I18-1714741, IIS- 1845081, LIS-1907704 and IIS- 1955285. Yao Li and Dr. Ming Yan are supported by NSF grant DMS-2012450 and Facebook Faculty Research Award (Systems for ML). Dr. Rongrong Wang is supported by NSF grant CCF- 1909523.
REFERENCES
Dan Alistarh, Demjan Grubic, Jerry Li. Ryota Tomioka, and Milan Vojnovic. QSGD: Communication--fficcennt sgd via gradient quantization and encoding. In Advances in Neural Information Processing Systems, pp. 1709-1720. 2017.
Jeremy Bernstein, Yu-Xiang Wang, Kamyar Azizzadenesheli, and Animashree Anandkumar. SIGNSGD: compressed optimisation for non-convex problems. In Proceedings of the 35th In- ternational Conference on Machine Learning, pp. 559-568 2018.
Ruggero Carli, Fabio Fagnani, Paolo Frasca, and Sandro Zampieri. Gossip consensus algorithms via quantized communication. Automatica, 46(1):70-80, 2010.
Sai Praneeth Karimireddy, Quentin Rehjock, Sebastian Urban Stich, and Martin Jaggi. Error feed- back fixes SignSGD and other gradient compression schemes. In Proceedings of the 36th Inter- national Conference on Machine Learning, pp. 3252-3261. PMLR, 2019.
Anastasia Koloskova, Sebastian U. Stich, and Martin Jaggi. Decentralized stochastic optimization and gossip algorithms with compressed communication. In Proceedings of the 36th International Conference Machine Learning, pp. 3479-3487. PMLR, 2019.
Anastasia Koloskova, Tao Lin, Sebastian U Stich, and Martin Jaggi. Decentralized deep learning with arbitrary communication compression. In International Conference Learning Represen- tations, 2020.
Yao Li and Ming Yan. On linear convergence of two decentralized algorithms. arXiv preprint arXiv:1906.0722. 2019.
Zhi Li, Wei Shi, and Ming Yan. A decentralized proximal-gradient method with network indepen- dent step-sizes and separated convergence rates. IEEE Transactions on Signal Processing, 67 (17):4494 2019.
Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsieh, Wei Zhang, and Ji Liu. Can decentralized algorithms outperform centralized algorithms? case study for decentralized parallel stochastic gradient descent. In Advances Neural Information Processing Systems, pp. 5330 5340,, 2017.
Qing Ling, Wei Shi, Gang Wu, and Alejandro Ribeiro. DLM: Decentralized linearized alternating direction method of multipliers. IEEE Transactions on Signal Processing, 63(15):4051-455 1-4044, 2015.
Xiaorui Liu, Yao Li, Jiliang Tang, and Ming Yan. A double residual compression algorithm for efficient distributed learning. The 23rd International Conference on Artificial Intelligence and Statistics, 2020.
Yucheng Lu and Christopher De Sa. Moniqua: Modulo quantized communication in decentralized SGD. In Proceedings of the 37th International Conference on Machine Learning, 2020.
Sindri Magnússon, Hossein Sookri-Ghadikolei.. and Na Li. On maintaining linear convergence of distributed learning and optimization under limited communication. IEEE Transactions on Signal Processing, 68:6101-6116 2020.
Konstantin Mishchenko, Eduard Gorbunov, Martin Takáč, and Peter Richtárik. Distributed learning with compressed gradient differences. arXiv preprint arXiv: 1901. 000669999999......99999990.... 2019.
10

---

Published as a conference paper at ICLR 2021
Joao FC Mota, Joao MF Xavier, Pedro MQ Aguiar, and Markus Püschel. D-ADMM: A communicationn-effccett distributed algorithm for separable optimization. IEEE Transactions on Signal Processing, 61(10))2718 (1110))2718-2223 2723, 2013.
Angelia Nedic and Asuman Ozdaglar. Distributed subgradient methods for multi-agent optimiza- tion. IEEE Transactions on Automatic Control, 54(1):48-61, 2009.
Angelia Nedic, Alex Olshevsky, and Wei Shi, Achieving geometric convergence for distributed optimization over time-varying graphs. SIAM Journal on Optimization, 37(4):2597-2333 2017.
Yurii Nesterov. Introductory lectures on convex optimization: A basic course, volume 87. Springer Science & Business Media, 2013.
Shi Pu and Angelia Nedić. Distributed stochastic gradient tracking methods. Mathematical Pro- gramming, pp. 1-49, 2020.
Amirhossein
Reisizadeh, Aryan Mokhtari, Hamed Hassani, and Ramtin Pedarsani. An exact quan- tized decentralized gradient descent algorithm. IEEE Transactions Signal Processing, 67(19): 4934-4947, 2019a.
Amirhossein Reisizadeh, Hossein Taheri, Aryan Mokhtari, Hamed Hassani, and Ramtin Pedarsani. Robust and communication-efficeni collaborative learning. In Advances in Neural Information Processing Systems, pp. 8388-8399, 2019b.
Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu. 1-bit stochastic gradient descent and application to data-pat mata-parallel distributed training of speech DNNs. In Interspeech 2014, September 2014.
Wei Shi, Qing Ling, Gang Wu, and Wotao Yin. EXTRA: An exact first-order algorithm for decen- tralized consensus optimization. SIAM Journal Optimization, 25(2):944 96669 2015.
Sebastian U. Stich, Jean-Baptiste Cordonnier, and Martin Jaggi. Sparsified SGD with memory. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pp- 4452 4463, 2018.
Hanlin Tang, Shaoduo Gan, Ce Zhang, Tong Zhang, and Ji Liu. Communication compression for decentralized training. Advances Neural Information Processing Systems, pp. 7652-7662. 2018a.
Hanlin Tang, Xiangru Lian, Ming Yan, Ce Zhang, and Ji Liu. D2: Decentralized training over decentralized data. In Proceedings of the 35th International Conference on Machine Learning, pp. 4848-4856, 2018b.
Hanlin Tang, Xiangru Lian, Shuang Qiu, Lei Yuan, Ce Zhang, Tong Zhang, and Ji Liu. Deepsquecze: Decentralization meets emoor-comeensated compression. CoRR, Abs/1907.00346, 2019a. URL
http::/arxx org/ htgg/abb/1907 07346
Hanlin Tang, Chen Yu, Xiangru Lian, Tong Zhang, and Ji Liu. DoubleSqueeze: Parallel stochastic gradient descent with double-pass compensaeed compression. In Proceedings of the 36th International Conference Machine Learning, pp. 6155-6165, 2019b.
John Tsitsiklis, Dimitri Bertsekas, and Michael Athans. Distributed asynchronous deterministic and stochastic gradient optimization algorithms. IEEE transactions on automatic control, 31(9): 803-812, 1986.
Jaaxiang Wu, Weidong Huang, Junzhou Huang, and Tong Zhang, Error compensated quantized SGD and its applications large-scale distributed optimization. In Proceedings of the 35th Interna- tional Conference on Machine Learning, pp. 5325-5333, 2018.
Lin Xiao and Stephen Boyd. Fast linear iterations for distributed averaging. Systems & Control Letters, 53(1):65-78, 2004.
Jinming Xu, Ye Tian, Ying Sun, and Gesualdo Scutari. Accelerated primal-dual algorithms for distributed smooth convex optimization over networks. In International Conference on Artificial Intelligence and Statistics, pp. 2381-2391. PMLR, 2020.

---

Published as a conference paper at ICLR 2021
Kun Yuan, Qing Ling, and Wotao Yin. On the convergence of decentralized gradient descent. SIAM Journal on Optimization, 26(3):1835-1854 1854, 2016.
Kun Yuan, Bicheng Ying, Xiaochuan Zhao, and Ali H Sayed. Exact diffusion for distributed opti- mization and learning-part Algorithm development. IEEE Transactions on Signal Processing, 67(3):708-723, 2018.
Kun Yuan, Wei Xu, and Qing Ling. Can primal methods outperform primal-dual methods in decen- tralized dynamic optimization? arXiv preprint 0rXiv:2003.08816 2020.
12

---

Published as a conference paper at ICLR 2021
Contents of Appendix
LEAD in agent's perspective
14
Connections with exiting works
14
Compression method
15
p-norm b-bits quantization
15
C.2 Compression error
16
D Experiments
17
D.I Parameter sensitivity
17
D.2 Experiments in homogeneous setting
17
D.3 Parameter settings
18
Proof' of the theorems
19
Musstrttvv flow
19
Two central Lemmas
20
Proof of Lemmal
20
Proof of Lemma
22
Proof of Theorem
23
Proof of Theorem
28
13

---

Published as a conference paper at ICLR 2021
A LEAD IN AGENT'S S PERSPECTIVE
In the main paper, we described the algorithm with matrix notations for concision. Here we further provide complete algorithm description from the agents' perspective.
Algorithm LEAD Agent's Perspective
input: stepsize 77, compression parameters (a, ?), initial values x/. h., 2i, Vi E (1,2..... n) Em-r,
output: 2/¹ Vi (1,2....,,?
.,2,,..,,,,............ n) for each agent i f1.2..... do
2: di = EjEnJU()) Wijz;
3: (hw)i = E) ExEXU(E) (hw))
4: at ==?-- -V[[((())))))
5: end for
6: for
1, 2, ..... K do in parallel for all agents i {1, {1,2,.... ..,,,
7:
compute (a )
Gradient computation
8:
y x. v fi { nd h
9:
q Compress
Compression
10:
of h + of
for neighbors j N₂ do
12:
Send otth and receive of
Communication
13:
end for
14:
( =(hw); EjeN,ue "ing"
15:
h k+t = =11- -a)h + agj
(hw)) k+1 (1 ah)) + a(Dw)
17:
d=t1 d in (it (Dw)
18: x; k+1 x n/ (2 nd!
D Model update
end for
B CONNECTIONS WITH EXITING WORKS
The non-compressed variant of LEAD in Alg. recovers NIDS Li et al.
2019). 2 Tang et al,
2018b) and Exact Diffusion (Yuan et al. 2018) as shown in Proposition that the convergence rate of LEAD exactly recovers the rate of NIDS when C = 0,y = and = 0.
Corollary we show
Proposition 1 (Connection NIDS, D2 and Exact Diffusion). When there is communication
compression (i.e., Y k Y and 1, Alg 1 recovers D2:
X I W (2x* -
VX* gh) + (V
(15)
2
Furthermore, if the stochastic estimator of the gradient V {*) ) is replaced by the full gradient, it recovers NIDS and Exact Diffusion with specific settings.
Corollary (Consistency with NIDS). When C (no communication compression), & 1 and
(full grudient), LEAD has the convergence consistent with NIDS with (0, 2/(μ + L)):
C k+1 < max u(2n - - 2Amas ((I - W)t)
c
(16)
See the proof in
E.5
Proof of Proposition
Let and Y Y Combing Lines 4 and 6 of Alg. gives
I W
D D++ D*
x vxV n/D*).
(17)
2n
14

---

Published as a conference paper at ICLR 2021
Based on Line 7, we represent 7/D from the previous iteration
D x X
(18)
Eliminating both D* and D by substituting
18
into Line 7, we obtain
I
x X 7 VV x ; - nD
+
VVF(X - -n)*))
(from 177)
2
It W X -
+ W
n
2
I+ W
I W
(X* VF {*))
(X
X VF (from (18)
I W
22X X - {t) VX (h
(19)
which is exactly D² also recovers Exact Diffusion with A I+W and M 7 in Eq. (97) of (Yuan et al. 2018).
C COMPRESSION METHOD
C.I P-NORM B-BITS QUANTIZATION
Theorem (p-norm b-bit quantization). Let us define the quantization operator as
2
[
Qp(x) (| sign(x))) (1gx))))iggn (0-1))
(20)
| lp
where is the Hadamard product, [x] the elementwise absolute value and u is a random dither vector uniformly distributed in [0, 11 Qp(z)) is unbiased, i.e.. EQp(x) and the compression variance is upper bounded by
B| Qp(z))1 < sign( x2 (20)2-((-11)))
(6- 1/2
(21)
which suggests that co-norm provides the smallest upper bound for the compression variance due to |alpp S |ا Væ $115spp oc.
Remark For the compressor defined
20 we have the following the compression constant
sign(()) )
(6-1)121100)
= sup
4 ||
Proof. Let denote ||>||p (x)) (6 (b-1), s can rewrite æ as æ = s
20-1|p|
||
81
2--1 [m] T
and 82
We
For any coordinate such that s; (51).. we have Qp(x;) (s1)ee, with probability 1. Hence EQ, s;U; æ; and
E(a; - Qp(x))) = (x; - s;u,)² (,,,); = 0.
For any coordinate i such that s; # (s1);, we have (82); (81) = 1 and Qp(x), satisfies
2x(x), (81):0 w.p. (82): 8is
(82):0; w.p. 8; (81);-
Thus, we derive
EQp(x); oo s); 0 s1); 0,8,(82 81); 02;; 2;:
15

---

Published as a conference paper at ICLR 2021
and
- E|æ;- Op(z));² (a; - s1);
- x² (s)) -2,00,000
(52 s1)a2, + tt) -(t)))))(((())))) -2s,(82 a1),0
(at; s,v;)² (- (52) + +81; - o7
= (at; s,v;)² + (82 88;(s 8)),0
= (32 s) - s1):e
1
Considering both cases, we have EQ(x) = x and
E| 0p(z)]]==
Σ
Ele;
Qp(x))1++
E
Elx; (x)))
(s1=()))c)
(orA(an))))
$ 0 + 4
2
|101|
sign(x))2
(2))))(-1))))
C.2 COMPRESSION ERROR
3b2
6b5s
I|X 100/1)111
10"
10a2
Figure 5: Relative compression error Q(=)(e))l for p-norm b-bit quantization
|
To verify Theorem 3 we compare the compression error of the quantization method defined in (20) with different norms (p- 1, .,.... 6, oo). Specifically, we uniformly generate 100 random vec- tors in R 10000 and compute the average compression eттor. The result shown in Figure 5 verifies our proof in Theorem B that the compression error decreases when p increases. This suggests that co-norm provides the best compression precision under the same bit constraint.
Under similar setting, we also compare the compression error with other popular compression meth- ods, such as top-k and random-k sparsification. The x-axes represents the average bits needed to rep- resent each element of the vector. The result is showed in Fig. Note that intuitively top-k methods should perform better than random-k method, but the top-k method needs extra bits to transmit- ted the index while random-k method can avoid this by using the same random seed. Therefore, top-k method doesn't 't outperform random-k too much under the same communication budget. The result in Fig. [ suggests that oc-morm b-bits quantization provides significantly better compression precision than others under the same bit constraint.
16

---

Published as a conference paper at ICLR 2021
1IX- 100000l////1)
10
10"
10"
2-mmm b-tiix quantizstio
nom this quarrazzion
10
inf bibits quantzalion
spand erotiin
10
spenefiotion
Figure 6: Comparison of compression error
[ Q2 between different compression methods
||||a
D EXPERIMENTS
D.1 PARAMETER SENSITIVITY
In the linear regression problem, the convergence of LEAD under different parameter settings of a and y are tested. The result showed in Figure that LEAD performs well in most settings and is robust to the parameter setting. Therefore, in this paper, we simply set a = 0.5 and y = 1.0 for LEAD in all experiment, which indicates the minor effort needed for parameter tuning.
10
LEAD ( 0.21
10
LEAD (r-
LEAD 0o 0.41
LEAD (g 0.4)
LEAD
10
0.6)
10
LEAD (am 1)
0.81
10
LEAD ()=1)
10
10
10
10
10
10
10
10
25
50
75
100
125
150
175
0
25
50
75
100
125
150
175
Epoch
Epech
(a) 7 = 0.4
(b) 7 = 0.6
10
LEAD 6.22
10
2
LEAD (a 0.22
LEAD (a- 0.41
LEAD (a- 0.4)
LEAD
(r-00
10
LEAD 0.8)
10
(a 0.8)
LEAD (a- 1)
LEAD (a 1)
10
10
10
10
10
10
60
100 Epech
125
150
175
25
60
76
100
125
150
175
Epech
(c) y = 0.8
(d) y = 1.0
Figure 7: Parameter analysis on linear regression problem.
D.2 EXPERIMENTS IN HOMOGENEOUS SETTING
The experiments on logistic regression problem in homogeneous case are showed in Fig. 8 and Fig. 9. It shows that DeepSqueeze, CHOCO-SGD and LEAD converges similarly while Deep-
17

---

Published as a conference paper at ICLR 2021
Squeeze and CHOCO-SCI require tune smaller y for convergence showed in the parameter setting in Section D.3] Generally, a smaller y decreases the model propagation between agents since y changes the effective mixing matrix and this may cause slower convergence. However, in the setting where data from different agents are very similar, the models move to close directions such that the convergence is not affected too much.
DGD (32 bis)
bits)
NIDS (32
NIDS (32 bits)
(2 bis))
bits)
DeeuSe bits)
Sueeeqeeece bits)
CHOCO-SGO (2 bits)
CHOCO-SGD (2 bit))
1005
3x100
3x100
1000
0.25
8.50
1.00
175
Epach
BBs transmitted
1610
(a) Loss f f(X*)
(b) Loss f(X*)
Figure 8: Logistic regression in the homogeneous case (full-batch gradient)
DGD (32 bits)
DGD (32 bits)
NIDS (32 bits)
NIDS (32 bits)
1.0
QDGD (2
1.0
QDGD bits)
DeepSqueeze (2 bits)
DeepSqueeze (2 bits)
CHOCO-SGD (2 bits)
CHOCO-SGD (2 bits)
LO88
LEAD
LoBs
0.6
LEAD
10
Epoch
Bils transmitted
160
(a) Loss f(X
(b) Loss / (X*)
Figure 9: Logistic regression in the homogeneous case (mini-batch gradient)
D.3 PARAMETER SETTINGS
The best parameter settings we search for all algorithms and experiments are summarized in Ta- bles QDGD and DeepSqueeze more sensitive y and CHOCO-SGD is slight more robust. LEAD Is most robust to parameter settings and it works well for the setting a = 0.5 and . = 1.0 in all experiments in this paper.
Algorithm
DGD
0.1
NIDS
0.1
QDGD
0.1
0.2
DeepSqueeze
0.2
CHOCO-SGD
0.1
0.8
LEAD
0.1 1,0
0.5
Table 1: Parameter settings for the linear regression problem.
18

---

Published as a conference paper at ICLR 2021
Algorithm
7)
Algorithm
17
?
DGD
0.1
DGD
0.1
NIDS
0.1
NIDS
0.1
QDGD
0.1
QDGD
0.2
DeepSqueeze
0.1
0.4
DeepSqueeze
0.1
0.6
CHOCO-SGD
0.1
0,6
CHOCO-SGD
0.1
0.6
LEAD
0.1
1.0
0.5
LEAD
0.1
1.0
0.5
Homogeneous case
Heterogeneous case
Table 2: Parameter settings for the logistic regression problem (full-batch gradient).
Algorithm
y
@
Algorithm
77
?
DGD
0.1
DGD
0.1
NIDS
0.1
NIDS
0.1
QDGD
0.05
0.2
QDGD
0.05
0.2
DeepSqueeze
0.1
0.6
DeepSqueeze
0.1
0.6
CHOCO-SGI
0.1
0.6
CHOCO-SGI
0.1
0.6
LEAD
0.1
1.0
0.5
LEAD
0.1
1.0
0.5
Homogeneous case
Heterogeneous case
Table 3: Parameter settings for the logistic regression problem (mini- batch gradient).
Algorithm
y
Algorithm 17
?
DGD
0.1
DGD
0.05
NIDS
0.1
NIDS
0.1
QDGD
0.05
0.1
QDGD
*
DeepSqueeze
0.1
0.2
DeepSqueeze
CHOCO-SGI
0.1
0.6
CHOCO-SC -GD
LEAD
0.1
1.0
0.5
LEAD
0.1
1.0
0.5
Homogeneous case
Heterogeneous case
Table 4: Parameter settings for the deep neural network. (* means divergence for all options we try)
E PROOFS OF THE THEOREMS
E. ILLUSTRATIVE FLOW
The following flow graph depicts the relation between iterative variables and clarifies the range of conditional expectation. {9 and (Fi are two o alageebras generated by the gradient sampling and the stochastic compression respectively. They satisfy
Go C C CACCCCCC
C C
(X+, D1, H²
X D2
H
(X* D H*)
FF(X+e")ee
E²
E 7F x 10
Y2
kk
round
(k- jth round
Fo
FR
Ft-1
The solid and dashed arrows in the top flow illustrate the dynamics of the algorithm, while in the bottom, the arrows stand for the relation between successive F-g-algebras. The downward arrows
19

---

Published as a conference paper at ICLR 2021
determine the range of F-o-algebras. E.g., up to E", all random variables are in F and up to ; all random variables are in G--1 with G--1 C F Throughout the appendix, without specification, E is the expectation conditioned the corresponding stochastic estimators given the context.
E.2 Two CENTRAL LEMMAS
Lemma 1 (Fundamental equality). Let X be the optimal solution, D = -VF(X') and E denote the compression error in the kth iteration, that is E Q" (Y* -H) Y Y From Alg.
7 we have
X k+1 x + (///))/D++ DM
=I x1 (1//>)) D' (ni D D -
2n Xx" VF(* ; VF(X')) + + (V VF 2n D D*),
where M = 2(I w) - and < 2/ mmax (I W) ensures the positive definiteness of M over range(I- W).
Lemma 2 (State inequality). Let the same assumptions in Lemma 1 hold. From Alg. ! if we take the expectation over the compression operator conditioned the k-th iteration, have
E EIIH
1 (1
a)
|
X
112
x x an/ an -D
20112 E D 1 +
+
IB - a(1 - a))l (((1-a)llYe)
2
1²
E.3 PROOF OF LEMMA I
Before proving Lemma we let E - and introduce the following three Lemmas.
Lemma 3. Let X" be the consensus solution. Then, from Line 4-7 of Alg.
7 we obtain
W 1xk+1
x*) = (1 I- w
W
(D*+11 k+ -D*)
E
(22)
2m
2
2n
Proof. From the iterations in Alg. I we have
D D
t
[I
W) Y (from Line 6)
2n
* +
[I
WY + E²a)
211
D* +
7 (I W)(X - V Eh) - 1/D* + +E²)
(from Line 4)
2n
D
7
[I
W)(X - /X gt)) DD+ X
DD -D*) + E+)
21
*
[I -](X*+1-X*
W) D + (I W)E*
2n
2n
where the fourth equality holds due (I w Alg. Rewriting this equality, and we obtain 22
0 and the last equality comes from Line 7 of
Lemma 4. Let D - ) span W}, we have
k+1 X*, D D* _ D 100--DD*' D - -
(E*,D*+1 -D*),
(23)
(X D D*) = D D D D - (E*, D D++1
D*),
(24)
where M = 2(I w) - VI and 7 < 2/ Amax (I W) ensures the positive definiteness of M over span(I- W).
20

---

Published as a conference paper at ICLR 2021
Proof. Since Dk++1 span - W for any k. have
(x#t1 X" ,' D
-(1- ([--)((**++ -x'), (I W) -D*))
2(1 - -1l1-211-W-i) (II-W)(D(+1_ D*) - (I w)E", -I- (I- -D")
(from (22
(2 w) - -D) D*)
E., D D
-" "|D - D -E*, Db+1 -
Similarly, we have
(X++1 X
- "*D (--))( - -x'), (I (I- W)((D*+1 -D")
2(2 71 W)) D*) - (-W)EE (I- (D))(DDF--DD -D9)
((2(1 (o) I)(D*t Dd) E D DD
" D D D*+1 - -D") (E* D D
To make sure that M is positive definite over span [I W.. we need y < 2//mmxx W). Lemma S. Taking the expectation conditioned on the compression in the kth iteration, we have
2E D - -D") = 2 E D* + Y (I-W)Y
2 [I - D
21
2n
= =E,EE", ,I, (1
W W)E*) - E 1
2n,,EE,, D -D = 2n/B E 2n
(I Y 1s + 2 (I W)E
20y
EE (I W) E 1
Proof. The proof is straightforward and omitted here.
Proof of Lemma
7 From Alg. [ we have
( X X", VF(X <*) - VF(X*))
=2 VF k. :6) - VVF(''))
=2( X*,X* -x+11 (nDD*+ K+1 -D")
(from Line 7)
=2(x* X',** -x Xx X", X*,D*t -D"
-2( x* x - 21 - x+1 b++ - DD) - (x X D 1 - DD)
- - X* - In k+1 - D*),X* -x*+1 - 21 k+1 - X* - -
-2(X +1 - X' + (VF ) VF(X*)) X -x (n -xt, -D) (from Line 7)
++
X*,
=2(X* X x X 27 X : - VF(X'), x
VF
x X ++1 D
(25)
Then consider the terms on the right hand side of 25 separately. Using 2(A - B.B C)
AA - CCI22 - IB 2 A B
?
we have
X* x x
x
=2
x
x+1
k+1 x*)
x
X
1 - 11
(26)
21

---

Published as a conference paper at ICLR 2021
Using 2(A, B) | + |B| |A Bll have
VF k ) - VF(X") x 1
VF VF X* R. (5*) VF(X"|| ) + X * - X 1| |x
X x+1 77 (VF((X*; VF(X))I
= (X*, 5*) VF(X")|| + | X -
- ?
(from Line 7)
(27)
Combining 25
26
and 23
we obtain
(x X", VF
X
(X()))
|
X" 1
X
x 2|
X |x++1 1
2(x X
VF(X )112
X 12 D 1
Vn (th)
-x-11)
20 (D k+1 D. D k+ D' EE" Dé+1 - D D")
2x D -D"
X 1 - |X k+1 - x+1
|x
x+1 1
V g*)) VF(X
| x 12- 11 DD11
(ID* D'
|D
|
D'
I D +2n(EE D D*)
-2DD D D
where the last equality holds because
2 k - D D* - -D"M =IID* D |D - -ID* - -D =
Thus, reformulate it as
2 D D
| X+1
7
=|| 1 + !12 7
D D n²² | - D*1 1 D
(x - XX, VF(X* VF(X') + + VF(X))12 + (n D D*).
which completes the proof.
L
E.4
PROOF OF LEMMA
Proof of Lemma
From Alg.
we take the expectation conditioned on kth compression and obtain
E E| X 1
=1] (H* X*) + (YY -X*) + 1 (from Line 13)
=II(1 - (H -X*) + at Y = + 2
=(1 a) |) - 1 + a Y x=1 - a(1 H Yk + a E
(28)
In the second equality, we used the unbiasedness of the compression, i.e., EE 0. The last equality holds because of
(111 - a) HBB = -)] a B
a(1 A Bll
22

---

Published as a conference paper at ICLR 2021
In addition, by taking the conditional expectation the compression, we have
Y x 1 = + VF - r,D* 1 (from Line 4)
- -D =E| ++ -
=E| ++1 - -
(from Line 7) En (X ++1
k+1 111
X", x', D D
=E|XX*+1 - - 1 k+ D* 1
201²
+
E D 6+ D* 1 M En D D (from 22
= =E| k+ X 11
D 121
+ 21/2 D+1 D*
MM
> E --
(from Line 6)
(29)
Combing the above two equations
(8 and
together, we have
E
1
2an2
S(1 a) H 12 + aB x + a 12
D+1 D* |
M
ayE P w + a |+ a(1 a 1
(30)
which completes the proof.
E.5 PROOF OF THEOREM
Proof of Theorem Combining Lemmas 1 compression satistying
7
and
we have the expectation conditioned on the
7
E
X
X
1
E
D
k+
D
a,
E
H
X
7
2
X
X 12
D 1
M
D
E
D
I'm D D7112
7
2 X", VF )
VF
{*) VF(X*) E
+ (1-
| H
x 2 +
an
k++ 1212
2n
B| D 11 11 + a
E 22 -aaallll------aa--a---aa-aaaaaa-
a) a)) H²12
-
X
1
21
x VF(X (t) (F(X")) -F
1
+ ajaE x b+1 1²1
|D 1 n D k+1 17112
x1 (11 - a 12 BJD 1 + a on 2
Ha)
+ -1-aa H
=
=aaaEElEE - E - a H²
(31)
where is neg-negative number to be determined. Then we deal with the three terms on the right hand side separately. want the terms and to nonpositive. First, we consider B. Note that D E Range(I- W). If we want B < 0, then, we need 2aja > 0. i.e. ara < 1/2. Therefore
we have
B (1-2aja) 2 LEID 8+1 D* + a 1
7 (1 2a -211))d-1(MM
,' *+1 - DD*12
a10
23

---

Published as a conference paper at ICLR 2021
where A > 0 is the second smallest eigenvalue of M. It means that we also need
a1a + (2a 1)An-1 (M) I 0,
which is equivalent
(M)
010 S
< <1/2.
(32)
y 1MM)
Then we look at C. We have
C - (1-
E* / w - aja(1 - a) a) H=
18 aja(1 [ a)l 1
Y -aaaaaaa--aaaaaaaaaaaaaaa---aaa- Y
-
H²1
Because we have 1 010 1/2, need
C((1 - a10) + -1) --
(C 1)a + CBy 5..
(33)
That is
a1(C8y+11 1) - (( 00;
(34)
2(1+ C)a1
a a ai (1 + 1)
- 01
(35)
+ C)ai
Next, we look at A. Firstly, by the bounded variance assumption, we have the expectation condi- tioned on the gradient sampling in keth iteration satisfying
E X k - 1+1 2x k X x VF(X))) + ( VF
<| R - 1 (x - X VF(X*) VF(X*)) 1/ VF(X')I
Then with the smoothness and strong convexity from Assumptions we have the co-coercivity of (z) with gx(x) fi()) b 1 which gives
μL
1 |VF(*) VF(X'II
X X", VF(X*) VF(')) 2
#+L x - -X1
+ # #
When 7) S 2/( + L). we have
(x* x", VF(X*) - VF(X'))
nu+ L)
(x* X", VF(X*) - VF(X') nu (x* X2,
2
2
Ma(H + L)
MuL
-x 2 VI - VF(X:)12
p
2
2
=/
X
-x-1111
x21
112 + IVF(( - VF(X')11
2
Therefore, we obtain
2x X", VF(X*) - VF(X')
<ー VF(X n22n )x 1
(36)
Conditioned on the kehe iteration, (i.e., conditioned the gradient sampling in kth iteration), the inequality 31 becomes
E x+1 X
1 " D
++
a1E H 1²1
<1 pl2n- ) |
x 2
a1
X k+1 X 1
1/2
IID*
D' DI
2
D
++
- o)
D
01
-X
+
(37)
24

---

Published as a conference paper at ICLR 2021
if the step size satisfies
M+L- Rewriting 37
we have
2 E
(1 a1a)
X 11
D
D'M + 1
D
D²1 aj
x11 1
q
$ 1u22 1 |X*
x |
D
D a1 a) X nn²d
(38)
and thus
(1 - 11 n EID -D + t -
+
x21 + ạ 1 D + a1 ( x nn
$ (1 p(2n) yn -|x=
(39)
With the definition of C in we have
Bc S ph + nn?²
(40)
with
(22 - 2m12))
Amax (M)
max
Amax (M) a
a10
where
Amax (M) 2Amax ((I w)t) 7
Recall all the conditions on the parameters 01, a, and to make sure that p < 1:
XM)
a10 S
(41)
7 21
S (2n - pm72);
(42)
- a 01 (C3y 1) D2
(43)
2(1 + C)ai
01 (CBT / (CCCBy + + a1
(44)
2(1 C'ai
In the following, show that there exist parameters that satisfy these conditions. Since we can choose any a1, we let
C(1+C)
a1 = CBy +2
such that
d((B C)Cai of.
Then we have
CBy
00
+ 0,
as 7 + 0,
2(1 +C)
CBy
+2
1
a1
as 0
2(1
140'
Conditions
43 and
44 show
20By
01
CB²+2
2
[0,2], if C 0 or 0.
25

---

Published as a conference paper at ICLR 2021
Hence in order to make 41 and
42
satisfied, it's sufficient to make
20By
I min
7 2 (M) (2(2)) -mm²m)
An- (M)
min
2
M2n m//))]
(45)
CBy+2 +
where we use A (M)
Anmax II W)
= 7.
When C' > 0, the condition 45 is equivalent to
(3C' 1)2 V
40
22 - pT))
S min
(46)
C3
[2 1n (1) CB
The first term can be simplified using
(3C + 1) /3C + 1)2 4C
C3
(3C + 1)3
due to vI- < 1 - when x E (0, 1).
Therefore, for a given stepsize 17, if we choose
E (0. (0.
(3C + 1)3' [2 1-nn (m) }
2
2pm(2 umm
and
CB7 2(1+ C)
CB. +2 2- mh C3y+2
CB + 21 A(1+C))
E
min
2(1 C)' 4- 3 111 C) umm2
pm)
then, all conditions
hold.
Note that 7 < 3C 1 implies y < n. which ensures the positive definiteness of M over span
W] in Lemma
Note that 7) S a+L
ensures
+B
C
1m(2 pn))
<
(47)
4(1 (1+00
2(1+C)
So, we can simplify the bound for a as
CBy
2 By CBy +2
CBy + 2 4(1 C)
E
min
14 By 4(1 1m(2 (2- (1n))
2(1+C)
Lastly, taking the total expectation both sides of 40 and using tower property, we complete the proof for C
Proof of Corollary 7 Let's first define K,y and Kig
Arna (I-W) W) main (T WW
Amaxm (I W) ((1
W)
We can choose the stepsize 7 T, such that the upper bound of is
2. (2 1
Yupper = =min
Kj
2
2 min
2
1
(3C + 1),8¹
3
(3C + 1)18 KGCB
2 Ky
2
C8
due x(2-x) 2-x(2-0) 2- when x E (0, 1).
Hence take y min [30+1)3 CBC
26

---

Published as a conference paper at ICLR 2021
The bound of is a
Cgyy 2(1 C)
2 2 By CBy+ +2 1 -(2
1 1 CBy +
+
min
[ By 4(1+ C) Kf
Ki 4(1 + +0
When y is chosen as
KyCB pick
CB7 2(1+C) 2(1+0)K/
a
(48)
When (30+1)g v kyBB the upper bound of a is
By C3² +2
1
CB +2
Oupper = min
(2
4- By 4(1 + C) Kf
Kf
4(1 + +C]
60 +1 1
1
7C'2
min
- (2
12C +3' Kf
Kf
4(C + +)(CC +1)
+1 1
7C+2
min
120 + Kf
4(C'+ 1)(3C +1)
In this case, we pick
70 +2 12C +3' Kf 4(C + 1)(3C +1)
6C'+1 11
a min
(49)
Note a 0 [[+C)s]]
GC+1 since T2C+3 is lower bounded by 1.- Hence in both cases (Eq. (88) and
Eq. 449 ) = [I+C)18
and the third term of is upper bounded by
2(1 + C)ns min {
1
6C +1 11 12C +3' Ki
7C' + 2 4(1 C3C + +1)
1 S max
In two cases of y, the second term of becomes
7 27 (II W)J)
max
2CKg
(1 1 3C)
Before analysing the first term of p, we look a in two cases of y. When 7 kyC
2C3y
2
1
aja =
CBy+2
2k. +
KJ
When y (3C+1)88*
6C +1
60
a1a = min
<
(12C' + 3)'
Kif
Kj
In both cases, 01 1. Therefore, the first term of p becomes
kj
1 (2 mm7)
1
Ky
Kj
01
Ri
Kif
To summarize, we have
6C 1
7
S 1 - -min
min
Kg 2CkgKg (1 3C)Ryy 2(1 + C)ny""
12C' 3' Ky 4(1 + (1+C0))
27

---

Published as a conference paper at ICLR 2021
and therefore
max { (1-0( 0 ( (1+ (1-+)))))1-00( (1- ( Ckigg (c
1
With full- aull-gradient (i.e., 0 = 0), we get c-accuracy solution with the total number of iterations
k 2 Õ + C) + kg) + (k)
When C O, i.e., there is compression, the iteration complexity recovers that of NIDS, Ô (ky Kg).
When C' S Ky tRyt, the complexity is improved to that of NIDS, i.e. the compression doesn't harm the convergence in terms of the order of the coefficients.
Proof of Corollary
Note that (7**)
X and 1nx1 X X", then
Bl|a
E X 1 1nx1X 1111
E X X* x 1 xxx| 1
1 1nxi1
X X
x xx)
E X X11
pBCk
1 01 p)-
11010 010
S 2p L. +2 117²02
(50)
The last inequality holds because we have a S 1/2.
Proof of Corollary 3 From the proof of Theorem 1 when C O, 7 1, and
a1 = 0. Plug those values into and we obtain the convergence rate for NIDS.
E.6 PROOF OF THEOREM 2
Proof Theorem In order to get exact convergence, we pick diminishing step-size, set a C84
203 O 2Amse (Mm- and 02 2(1+0)* then
2(1+C), 010
C8:++2"
Pk max (1 pm jmm)) aia - 017ks 0271
a1
If we further pick diminishing and 7h such that pmdaa (2 - -UTN)) - a1a 2 aja, then
pmp (2 pmnx 010
Q10
2C3 2 C.7.
aja
a10
2 -C3%%
Notice that C3yy $ since (3C + 1) - v V33 + 1)2 342-0
40 is increasing in C > with limit 2 at
In this case we only need,
(3C + (3C+ 4C
2 [ (2 CB 3 2 (51)
2pmp (2 pm))))
0, min
Th E
C3
And
Pk max
CBT,,
017k, 02 5 037k
28

---

Published as a conference paper at ICLR 2021
if 0g min B2) and note that 02 - CB.
We define
= (1-aaiaa)ll
x=112 + (2 DE D D'I + +ai||H* x²
Hence
EC S <(1 (1- 12l-0311 -111)))))B + no??
From 01a
MT (2mm2))m))
we get
2
4C
S 1mi pm))))
CB3xx +2
If we pick Y 0177, then it's sufficient to let
2C,8277 I pmll2 - p(T)). 2(a-036.) n²²
Hence if 0g čs and let 1/-
then 7i 7t E (0. 1-) guarantees the above discussion
and
E < (1 - 0g024k ).C + no?
So far all restrictions for n are
Th S min 2
11 I, 11
and
(3C' + 1) - / + 1)2 - 4C 2
S
min
04
CB
3
Let 0g min {
2 p-I 17.
(3C++) -BC+11)/133++)3----- 113
2
Bk+ and D = max AAC
2nd 0,0,
C38,
30
1l
claim that if we pick B
0g0l 2
and some A, by setting The 050,K+2A' we get
D
EC S Bk+ A
Induction:
When & = 0, it's obvious. Suppose previous i inequalities hold. Then
EC (1
20z04
2D
4no
0z0,k 2A
0z0,k + 24 (0g0 22)22
Multiply M (0z04k: + 0z04 + (2))(2) on both sides, we get
20,04
(0g04k 0z04 +A) 4no 40z0(0200k 0z04 2A)
MECK+1
0z04k + 2A
2D(0g04k + 2A)
2D(0g0gk + 2A 20g0.) + 030, + 2AA) + 4n 0g04 2A)
2D(030ak: + 2A)
2D(0g0,k + 2A) + 4no (ng 2A) 4D8g6, + 2A) 2 2D830, 2A)
2D(0g0sk + 2A)
4D(030,)2 2
2D(0,0,k + 2A)
<0z0sk +2A
Hence
2D
EC <
0z04(k + 1) + 2A
2A
29

---

Published as a conference paper at ICLR 2021
This induction holds for any A such that Th is feasible, i.e.
1
To =
A S 0g.
Here we summarize the definition of constant numbers:
CB
0 2Amax ((I W)F) 02
(52)
2(1 + C)'
2(μ 2(p- c)0
03 min 02), 01 E
CB
1/2
112
(53)
2
(3C + 1)
/3C
1)2 4C
2
05 min
(54)
1l + L
C
1304
Therefore, let A = 8.
1. and
28,
we get
0g0.0kk-2-
20 max 1,
1 E <
0g04
0z040zk +
Since - aj03 2 1/2, we complete the proof.
30


Reviews:
[{"review_id": "aJqEi10ELCG", "reviewer": "AnonReviewer2", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper introduces a novel decentralized algorithm (LEAD) incorporated with compression that achieves linear convergence rate in strongly convex setting. The main idea is to apply and communicate the compression of an auxiliary variable instead of the primal or dual iterates.  Convergence analysis is provided for both deterministic and stochastic variants. Experiments shows the state-of-the-art performance. \n\nThe paper is well written and the results are presented clearly. I only have a few questions regarding the presentation of the algorithm. \na) It would be better to discuss in more details that the algorithm reduces to NIDS when there is no compression. In the current presentation, this point is not clearly stated in the main paper (only in appendix B). \nb) The role of the auxiliary variables $Y$ and $H$ deserves a better  explanation. It is unclear to me why we apply the quantization on the difference between $Y$ and $H$, in other words, what does this difference represent? Providing more intuitions on these points will be helpful for further understanding. \nc) According to the equation on the top of page 5, it seems like the quantization only introduces an additive noise in the update. Can it be viewed as an inexact variant of NIDS where the noise is bounded by some iterate dependent quantity? \nd) Does the result transfer to the convex but non-strongly convex setting? \ne) I am wondering whether the parameter $C$ in the contractive operator is dimension dependent, in which case would the stepsize also be dimension dependent? \nf) In Figure 1 b) and Figure 2 b), some curves stop very early, it would be better to fix them. \n\nOverall, I am very positive about the paper and hence recommend acceptance. \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "XWIjUG9S578", "reviewer": "AnonReviewer1", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "## Summary\nThis work proposes a new stochastic algorithm for distributed optimization. I really enjoyed reading the paper. It has a strong theory, nice experiments with several objectives and parameter-sensitivity tests, and the writing is sufficiently good. This authors did a great job comparing both theoretically and numerically to the most relevant literature. The paper builds on top of the recent successes in distributed optimization and two particularly popular approaches: quantization and decentralized topology of the network. The paper's main weakness, in my opinion, is that the algorithm is a bit hard to understand at first, and it has a number of extra parameters, but this seems to be a common issue for decentralized algorithms, and the experiments show that their tuning is not difficult. Another issue is that the paper might be too technical for an unprepared reader, and the theorem statement is hard to parse.\n\n## Detailed comments\n1. The paper presents a clear motivation for developing a new algorithm by explaining the shortcomings of the existing ones. For instance, D-PSGD is explained to not converge precisely when the data is heterogeneous; error-feedback has a slow rate due to the delayed compensation of errors; DCD-PSGD is mentioned in Remark 1 to be too aggressive and to perform worse numerically. I think that the thorough comparison to the prior work is one of the main strengths of this paper.\n\n2. I think the algorithm is not explained well. Its design consists of multiple pieces: a consensus algorithm based on NIDS/D^2, a compression scheme based on Diana, and the gradient updates of SGD, all of which are given together immediately. The authors present the algorithm without any warm-up, and there are several ways to fix it. Firstly, the meaning of the variables that are presented in the algorithm could help to understand it. Before presenting the full algorithm, it makes sense to mention that D^k is a dual variable needed to ensure stationarity at the optimum and that its role is to estimate the gradient there. Similarly, the communication procedure is not obvious and the meaning of H^k is unclear when just looking at the algorithmic steps. I do think that the paper would benefit from introducing some of the concepts before the algorithm. My first impression was a lot of confusion, mainly because of the communication procedure. Maybe it's best if the authors explain what happens when the algorithm is fully centralized, what it boils down to, and why it works in that case.\n\n3. Theorem 1 assumes that the gradients are bounded uniformly over the space. A number of recent papers showed that SGD works even if the variance is bounded only at the optimum, for example, (Gower et al., \"SGD: General Analysis and Improved Rates\"). Do the authors think that it's possible to relax the assumptions for LEAD as well?\n\n4. Can the authors present a complexity bound based on Theorem 1 that would show explicitly every term? I think it should be something O((C*kappa+beta)*log(1/eps) + kappa*sigma^2/eps) and I'd hope to see a comparison to the bound of (Koloskova et al., 2019).\n\n5. The authors should provide a reference for the claims around Assumption 1, such as the eigenvalue bounds. For instance, (Xiao and Boyd, \"Fast linear iterations for distributed averaging\") or any other material where the properties of mixing matrices are explained.\n\n6. The convergence rate recovers that of NIDS as mentioned in Remark 3. Does it also recover the right rate in other special cases, for instance, when the algorithm is fully centralized (W=I)?\n\n6. In figure 4, please clarify if you use the running average of the losses or the full train loss.\n\nTypos:\nCorollary 1: the expression for condition number has u instead of \\mu in the denominator.\np.7, \"before uniformly partitioned\": should be \"before being uniformly partitioned\"", "extra_scores": {}, "extra_text": {}}, {"review_id": "To412n6QUHP", "reviewer": "AnonReviewer4", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\nThis paper introduces a novel algorithm for decentralized optimization when nodes can only communicate a compressed signal with their neighbors. Unlike most decentralized methods with compression that are inspired by primal methods (DGD type methods), this paper introduces a new primal-dual algorithm with compression. The proposed method's main idea is borrowed from the NIDS algorithm, which converges linearly when the local loss functions are smooth and strongly convex. As the proposed LEAD method is based on primal-dual methods, it succeeds in improving the sublinear rate of primal-based methods. To the best of my knowledge, this is the first decentralized method that achieves a linear convergence rate in the setting that nodes use compressed signals. \n\nOverall, the paper is well-written, and the authors explain the intuition behind each step of their proposed method very well. Although the main proposed method and its convergence analysis are similar to the ones in the paper that introduce the NIDS algorithm, the final theoretical result is strong. Therefore, the reviewer recommends the acceptance of this paper. A few minor comments:\n\n\nIt is acceptable that the authors provide a linear convergence rate for the proposed method, but it would be better to characterize the overall complexity bound for their proposed method to achieve an $\\epsilon$ accurate solution. In particular, it would be great if they could study the dependency of the overall complexity (number of communication rounds) on the graph connectivity  parameter and the objective function parameters (strong convexity and smoothness constants.)\n\n\nFor the stochastic case, there has been a recent line of work that shows that if each local function can be written as a finite sum of a large number of functions (which is often the case in most machine learning problems), it is possible to obtain exact linear convergence rate. The current result for the stochastic setting is a bit trivial, considering the result for the deterministic setting. It would be interesting if the authors could use the tools used in the following papers to improve their results for the stochastic setting.\n\n\n 1- Dual-Free Stochastic Decentralized Optimization with Variance Reduction\n \n 2- An accelerated decentralized stochastic proximal algorithm for finite sums\n \n 3- DSA: Decentralized Double Stochastic Averaging Gradient Algorithm\n \n 4- Towards More Efficient Stochastic Decentralized Learning: Faster Convergence and Sparse Communication\n \n 5- An Optimal Algorithm for Decentralized Finite Sum Optimization\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper introduces LEAD, a decentralized optimizer with communication compression that can achieve linear convergence rate in the strongly convex setting. In terms of novelty, the authors should still add a discussion of `Magnusson et al., 2019, On Maintaining Linear Convergence of Distributed Learning and Optimization under Limited Communication`,  which is a related linear convergence result in the deterministic (full gradient) case, and relates to the analysis here which is stochastic but also exploits the deterministic case. Nevertheless, reviewers reached consensus-*with communication compression in the given time*-that the paper in its current form is well written and the results are presented clearly in both experiments and theory (which builds up on the earlier NIDS algorithm). The presentation of the algorithm can be slightly improved. We hope the authors will incorporate the remaining smaller open points such as mentioned by R1, such as making the constants in the convergence bounds explicit when comparing with other methods.
Decision: Accept (Poster)