Year: 2021

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 LinEAr convergent Decentralized 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.

heading: 1 INTRODUCTION
text: Distributed optimization solves the following optimization problem
x∗ := argmin x∈Rd
[ f(x) := 1
n n∑ i=1 fi(x) ]
(1)
with n computing agents and a communication network. Each fi(x) : Rd → R is a local objective function of agent i and typically defined on the data Di settled at that agent. The data distributions {Di} can be heterogeneous depending on the applications such as in federated learning. The variable x ∈ Rd 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 communication between agents (through central agents or 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 to improve algorithm efficiency and system scalability, especially when the network bandwidth is limited.
In recent years, various communication compression techniques, such as quantization and sparsification, have been developed to reduce communication costs. Notably, extensive studies (Seide et al., 2014; Alistarh et al., 2017; Bernstein et al., 2018; Stich et al., 2018; Karimireddy et al., 2019; Mishchenko et 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-compressed counterparts. This great success has suggested the potential and significance of communication compression in decentralized algorithms.
While extensive attention has been paid to centralized optimization, communication compression is relatively less studied in decentralized algorithms because the algorithm design and analysis are
more challenging in order to cover general communication topologies. There are recent efforts trying to push this research direction. For instance, DCD-SGD and ECD-SGD (Tang et al., 2018a) introduce difference compression and extrapolation compression to reduce model compression error. (Reisizadeh et al., 2019a;b) introduce QDGD and QuanTimed-DSGD to achieve exact convergence with small stepsize. DeepSqueeze (Tang et al., 2019a) directly compresses the local model and compensates the compression error in the next iteration. CHOCO-SGD (Koloskova et al., 2019; 2020) presents a 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 et 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-dual algorithms can achieve faster converge rates and better support heterogeneous data (Ling et al., 2015; Shi et al., 2015; Li et al., 2019; Yuan et al., 2020). However, it is unknown whether communication compression is feasible for primal-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 knowledge, 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(σ2) neighborhood of the optimum with constant stepsize. LEAD is also able to achieve exact convergence 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 in all experiments and significantly outperforms the baselines on heterogeneous data. Moreover, LEAD is robust to parameter settings and needs minor effort for parameter tuning.

heading: 2 RELATED WORKS
text: Decentralized optimization can be traced back to the work by Tsitsiklis et al. (1986). DGD (Nedic & Ozdaglar, 2009) is the most classical decentralized algorithm. It is intuitive and simple but converges slowly due to 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 training 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 as D-ADMM (Mota et al., 2013), DLM (Ling et al., 2015), EXTRA (Shi et al., 2015), NIDS (Li et al., 2019), D2 (Tang et al., 2018b), Exact Diffusion (Yuan et al., 2018), OPTRA(Xu et al., 2020), DIGing (Nedic et al., 2017), GSGT (Pu & Nedić, 2020), 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 accuracy 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 et 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-Gossip (Koloskova et al., 2019) converges linearly to the consensual solution. Combining CHOCO-Gossip and D-PSGD leads to a decentralized algorithm with compression, CHOCO-SGD, which converges sublinearly under the strong convexity and
gradient boundedness assumptions. Its nonconvex variant is further analyzed in (Koloskova et al., 2020). A new compression scheme using the modulo operation is introduced in (Lu & De Sa, 2020) for decentralized optimization. A general algorithmic framework aiming to maintain the linear convergence of distributed optimization under compressed communication is considered in (Magnússon et al., 2020). It requires a contractive property that is not satisfied by many decentralized algorithms including the algorithm in this paper.

heading: 3 ALGORITHM
text: We first introduce notations and definitions used in this work. We use bold upper-case letters such as X to define matrices and bold lower-case letters such as x to define vectors. Let 1 and 0 be vectors with all ones and zeros, respectively. Their dimensions will be provided when necessary. Given two matrices X, Y ∈ Rn×d, we define their inner product as 〈X,Y〉 = tr(X>Y) and the norm as ‖X‖ = √ 〈X,X〉. We further define 〈X,Y〉P = tr(X>PY) and ‖X‖P = √ 〈X,X〉
P for
any given symmetric positive semidefinite matrix P ∈ Rn×n. For simplicity, we will majorly use the matrix notation in this work. For instance, each agent i holds an individual estimate xi ∈ Rd of the global variable x ∈ Rd. Let Xk and∇F(Xk) be the collections of {xki }ni=1 and {∇fi(xki )}ni=1 which are defined below:
Xk = [ xk1 , . . . ,x k n ]> ∈ Rn×d, ∇F(Xk) = [∇f1(xk1), . . . ,∇fn(xkn)]> ∈ Rn×d. (2) We use ∇F(Xk; ξk) to denote the stochastic approximation of ∇F(Xk). With these notations, the update Xk+1 = Xk − η∇F(Xk; ξk) means that xk+1i = xki − η∇fi(xki ; ξki ) for all i. In this paper, we need the average of all rows in Xk and ∇F(Xk), so we define Xk = (1>Xk)/n and ∇F(Xk) = (1>∇F(Xk))/n. They are row vectors, and we will take a transpose if we need a column vector. The pseudoinverse of a matrix M is denoted as M†. The largest, ith-largest, and smallest nonzero eigenvalues of a symmetric matrix M are λmax(M), λi(M), and λmin(M). Assumption 1 (Mixing matrix). The connected network G = {V, E} consists of a node set V = {1, 2, . . . , n} and an undirected edge set E . The primitive symmetric doubly-stochastic matrix W = [wij ] ∈ Rn×n encodes the network structure such that wij = 0 if nodes i and j are not connected and cannot exchange information.
Assumption 1 implies that −1 < λn(W) ≤ λn−1(W) ≤ · · ·λ2(W) < λ1(W) = 1 and W1 = 1 (Xiao & Boyd, 2004; Shi et al., 2015). The matrix multiplication Xk+1 = WXk describes that agent i takes a weighted sum from its neighbors and itself, i.e., xk+1i = ∑ j∈Ni∪{i} wijx k j , where Ni denotes the neighbors of agent i.

heading: 3.1 THE PROPOSED ALGORITHM
text: The proposed algorithm LEAD to solve problem (1) is showed in Alg. 1 with matrix notations for conciseness. We will refer to the line number in the analysis. A complete algorithm description from the agent’s perspective can be found in Appendix A. The motivation behind Alg. 1 is to achieve two goals: (a) consensus (xki − (Xk)> → 0) and (b) convergence ((Xk)> → x∗). We first discuss how goal (a) leads to goal (b) and then explain how LEAD fulfills goal (a).
In essence, LEAD runs the approximate SGD globally and reduces to the exact SGD under consensus. One key property for LEAD is 1>n×1D
k = 0, regardless of the compression error in Ŷk. It holds because that for the initialization, we require D1 = (I −W)Z for some Z ∈ Rn×d, e.g., D1 = 0n×d, and that the update of Dk ensures Dk ∈ Range(I − W) for all k and 1>n×1(I −W) = 0 as we will explain later. Therefore, multiplying (1/n)1>n×1 on both sides of Line 7 leads to a global average view of Alg. 1:
Xk+1 = Xk − η∇F(Xk; ξk), (3)
which doesn’t contain the compression error. Note that this is an approximate SGD step because, as shown in (2), the gradient ∇F(Xk; ξk) is not evaluated on a global synchronized model Xk. However, if the solution converges to the consensus solution, i.e., xki − (Xk)> → 0, then Eξk [∇F(Xk; ξk)−∇f(Xk; ξk)]→ 0 and (3) gradually reduces to exact SGD.
Algorithm 1 LEAD Input: Stepsize η, parameter (α, γ), X0, H1, D1 = (I−W)Z for any Z Output: XK or 1/n ∑n i=1 X K i 1: H1w = WH 1 2: X1 = X0 − η∇F(X0; ξ0) 3: for k = 1, 2, · · · ,K − 1 do 4: Yk = Xk − η∇F(Xk; ξk)− ηDk
5: Ŷk, Ŷkw,H k+1,Hk+1w = COMM(Y k,Hk,Hkw) 6: Dk+1 = Dk + γ2η (Ŷ
k − Ŷkw) 7: Xk+1 = Xk − η∇F(Xk; ξk)− ηDk+1
8: end for
9: procedure COMM(Y,H,Hw) 10: Q = COMPRESS(Y −H) 11: Ŷ = H+Q
12: Ŷw = Hw +WQ
13: H = (1− α)H+ αŶ 14: Hw = (1− α)Hw + αŶw 15: Return: Ŷ, Ŷw,H,Hw 16: end procedure
With the establishment of how consensus leads to convergence, the obstacle becomes how to achieve consensus under local communication and compression challenges. It requires addressing two issues, i.e., data heterogeneity and compression error. To deal with these issues, existing algorithms, such as DCD-SGD, ECD-SGD, QDGD, DeepSqueeze, Moniqua, and CHOCO-SGD, need a diminishing 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 a different way to solve these issues, as explained below.
Data heterogeneity. It is common in distributed settings that there exists data heterogeneity among agents, especially in real-world applications where different agents collect data from different scenarios. In other words, we generally have fi(x) 6= fj(x) for i 6= j. The optimality condition of problem (1) gives 1>n×1∇F(X∗) = 0, where X∗ = [x∗, · · · ,x∗] is a consensual and optimal solution. The data heterogeneity and optimality condition imply that there exist at least two agents i and j such that ∇fi(x∗) 6= 0 and ∇fj(x∗) 6= 0. As a result, a simple D-PSGD algorithm cannot converge to the consensual and optimal solution as X∗ 6= WX∗ − ηEξ∇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, as introduced in Section 2. Specifically, LEAD 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):
Dk+1 = Dk + I−W 2η (Xk − η∇F(Xk)− ηDk), (4)
Xk+1 = Xk − η∇F(Xk)− ηDk+1, (5)
where Xk and Dk represent the primal and dual variables respectively. The dual variable Dk plays the role of gradient correction. As k → ∞, we expect Dk → −∇F(X∗) and Xk will converge to X∗ via the update in (5) since Dk+1 corrects the nonzero gradient ∇F(Xk) asymptotically. The key design of Alg. 1 is to provide compression for the auxiliary variable defined as Yk = Xk − η∇F(Xk) − ηDk. Such design ensures that the dual variable Dk lies in Range(I −W), which is essential for convergence. Moreover, it achieves the implicit error compression as we will explain later. To stabilize the algorithm with inexact dual update, we introduce a parameter γ to control the stepsize in the dual update. Therefore, if we ignore the details of the compression, Alg. 1 can be concisely written as
Yk = Xk − η∇F(Xk; ξk)− ηDk (6)
Dk+1 = Dk + γ
2η (I−W)Ŷk (7)
Xk+1 = Xk − η∇F(Xk; ξk)− ηDk+1 (8)
where Ŷk represents the compression of Yk and F(Xk; ξk) denote the stochastic gradients.
Nevertheless, how to compress the communication and how fast the convergence we can 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 4.
Compression error. Different from existing works, which typically compress the primal variable Xk or its difference, LEAD first construct an intermediate variable Yk and apply compression to obtain its coarse representation Ŷk as shown in the procedure COMM(Y,H,Hw):
• 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̂w = Hw +WQ. It is the only communication step in each iteration. • Each agent recovers its estimate Ŷ by Ŷ = H+Q and we have Ŷw = WŶ. • States H and Hw are updated based on Ŷ and Ŷw, respectively. We have Hw = WH.
By this procedure, we expect when both Yk and Hk 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., 2018a) and CHOCO-SGD (Koloskova et 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+αŶ motivated from DIANA (Mishchenko et al., 2019), which reduces the compression error for gradient compression in centralized optimization.
Implicit error compensation. On the other hand, even if the compression error exists, LEAD essentially compensates for the error in the inexact dual update (Line 6), making the algorithm more stable and robust. To illustrate how it works, let Ek = Ŷk −Yk denote the compression error and eki be its i-th row. The update of D k gives
Dk+1 = Dk + γ
2η (Ŷk − Ŷkw) = Dk +
γ 2η (I−W)Yk + γ 2η (Ek −WEk)
where −WEk indicates that agent i spreads total compression error − ∑ j∈Ni∪{i} wjie k i = −eki to all agents and Ek indicates that each agent compensates this error locally by adding eki 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 Xk+1 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 et al., 2014; Wu et al., 2018; Stich et al., 2018; 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 algorithm, LEAD in Alg. 1, recovers NIDS (Li et al., 2019), D2 (Tang et al., 2018b), Exact Diffusion (Yuan et al., 2018). These connections are established in Appendix B.

heading: 4 THEORETICAL ANALYSIS
text: 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 decentralized optimization algorithms. All proofs are provided in Appendix E.
Assumption 2 (Unbiased and C-contracted operator). The compression operator Q : Rd → Rd is unbiased, i.e., EQ(x) = x, and there exists C ≥ 0 such that E‖x − Q(x)‖22 ≤ C‖x‖22 for all x ∈ Rd. Assumption 3 (Stochastic gradient). The stochastic gradient ∇fi(x; ξ) is unbiased, i.e., Eξ∇fi(x; ξ) = ∇fi(x), and the stochastic gradient variance is bounded: Eξ‖∇fi(x; ξ) − ∇fi(x)‖22 ≤ σ2i for all i ∈ [n]. Denote σ2 = 1n ∑n i=1 σ 2 i .
Assumption 4. Each fi is L-smooth and µ-strongly convex with L ≥ µ > 0, i.e., for i = 1, 2, . . . , n and ∀x,y ∈ Rd, we have
fi(y) + 〈∇fi(y),x− y〉+ µ
2 ‖x− y‖2 ≤ fi(x) ≤ fi(y) + 〈∇fi(y),x− y〉+
L 2 ‖x− y‖2.
Theorem 1 (Constant stepsize). Let {Xk,Hk,Dk} be the sequence generated from Alg. 1 and X∗ is the optimal solution with D∗ = −∇F(X∗). Under Assumptions 1-4, for any constant stepsize η ∈ (0, 2/(µ+ L)], if the compression parameters α and γ satisfy
γ ∈ ( 0,min { 2 (3C + 1)β , 2µη(2− µη) [2− µη(2− µη)]Cβ }) , (9)
α ∈ [ Cβγ
2(1 + C) , 1 a1 min {2− βγ 4− βγ , µη(2− µη) }] , (10)
with β := λmax(I−W). Then, in total expectation we have 1
n ELk+1 ≤ ρ 1 n ELk + η2σ2, (11)
where
Lk := (1− a1α)‖Xk −X∗‖2 + (2η2/γ)E‖Dk −D∗‖2(I−W)† + a1‖H k −X∗‖2,
ρ := max
{ 1− µη(2− µη)
1− a1α , 1− γ 2λmax((I−W)†) , 1− α
} < 1, a1 := 4(1 + C)
Cβγ + 2
The result holds for C → 0. Corollary 1 (Complexity bounds). Define the condition numbers of the objective function and communication graph as κf = Lµ and κg =
λmax(I−W) λ+min(I−W) , respectively. Under the same setting in
Theorem 1, we can choose η = 1L , γ = min{ 1 Cβκf , 1(1+3C)β }, and α = O( 1 (1+C)κf ) such that
ρ = max { 1−O ( 1 (1 + C)κf ) , 1−O ( 1 (1 + C)κg ) , 1−O ( 1 Cκfκg )} .
With full-gradient (i.e., σ = 0), we obtain the following complexity bounds:
• LEAD converges to the -accurate solution with the iteration complexity O (( (1 + C)(κf + κg) + Cκfκg ) log 1 ) .
• When C = 0 (i.e., there is no compression), we obtain ρ = max{1−O( 1κf ), 1−O( 1 κg )}, and the iteration complexity O ( (κf + κg) log 1 ) . This exactly recovers the convergence
rate of NIDS (Li et al., 2019). • When C ≤ κf+κgκfκg+κf+κg , the asymptotical complexity is O ( (κf + κg) log 1 ) , which also
recovers that of NIDS (Li et al., 2019) and indicates that the compression doesn’t harm the convergence in this case.
• With C = 0 (or C ≤ κf+κgκfκg+κf+κg ) and fully connected communication graph (i.e., W = 11 >
n ), we have β = 1 and κg = 1. Therefore, we obtain ρ = 1 − O( 1 κf ) and the
complexity boundO(κf log 1 ). This recovers the convergence rate of gradient descent (Nesterov, 2013).
Remark 4. Under the setting in Theorem 1, LEAD converges linearly to the O(σ2) neighborhood of the optimum and converges linearly exactly to the optimum if full gradient is used, e.g., σ = 0. The linear convergence of LEAD holds when η < 2/L, but we omit the proof. Remark 5 (Arbitrary compression precision). Pick any η ∈ (0, 2/(µ+ L)], based on the compression-related constant C and the network-related constant β, we can select γ and α in certain ranges to achieve the convergence. It suggests that LEAD supports unbiased compression with arbitrary precision, i.e., any C > 0.
Corollary 2 (Consensus error). Under the same setting in Theorem 1 , let xk = 1n ∑n i=1 x k i be the averaged model and H0 = H1, then all agents achieve consensus at the rate
1
n n∑ i=1 E ∥∥xki − xk∥∥2 ≤ 2L0n ρk + 2σ21− ρη2. (12)
where ρ is defined as in Corollary 1 with appropriate parameter settings. Theorem 2 (Diminishing stepsize). Let {Xk,Hk,Dk} be the sequence generated from Alg. 1 and X∗ is the optimal solution with D∗ = −∇F(X∗). Under Assumptions 1-4, if ηk = 2θ5θ3θ4θ5k+2 and γk = θ4ηk, by taking αk = Cβγk2(1+C) , in total expectation we have
1
n n∑ i=1 E ∥∥xki − x∗∥∥2 . O(1k ) (13)
where θ1, θ2, θ3, θ4 and θ5 are constants defined in the proof. The complexity bound for arriving at the -accurate solution is O( 1 ). Remark 6. Compared with CHOCO-SGD, LEAD requires unbiased compression and the convergence under biased compression is not investigated yet. The analysis of CHOCO-SGD relies on the bounded gradient assumptions, i.e., ‖∇fi(x)‖2 ≤ G, which is restrictive because it conflicts with the strong convexity while LEAD doesn’t need this assumption. Moreover, in the theorem of CHOCO-SGD, it requires a specific point set of γ while LEAD only requires γ to be within a rather large range. This may explain the advantages of LEAD over CHOCO-SGD in terms of robustness to parameter setting.

heading: 5 NUMERICAL EXPERIMENT
text: We consider three machine learning problems – `2-regularized linear regression, logistic regression, and deep neural network. The proposed LEAD is compared with QDGD (Reisizadeh et al., 2019a), DeepSqueeze (Tang et al., 2019a), 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 a ring topology network. Each agent can only exchange information with its two 1-hop neighbors. The mixing weight is simply set as 1/3. For compression, we use the unbiased b-bits quantization method with∞-norm
Q∞(x) := ( ‖x‖∞2−(b−1) sign(x) ) · ⌊ 2(b−1)|x| ‖x‖∞ + u ⌋ , (14)
where · is the Hadamard product, |x| is the elementwise absolute value of x, and u is a random vector uniformly distributed in [0, 1]d. Only sign(x), norm ‖x‖∞, 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., 2019), but we use the∞-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 η from {0.01, 0.05, 0.1, 0.5}. For QDGD, CHOCO-SGD and Deepsqueeze, γ is tuned from {0.01, 0.1, 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 as η and the additional parameter in these algorithms as γ for simplicity. For LEAD, we simply fix α = 0.5 and γ = 1.0 for all experiments since we find LEAD is robust to parameter settings as we validate in the parameter sensitivity analysis in Appendix D.1. This indicates the minor effort needed for tuning LEAD. Detailed parameter settings for all experiments are summarized in Appendix D.3.
Linear regression. We consider the problem: f(x) = ∑n i=1(‖Aix−bi‖2+λ‖x‖2). Data matrices Ai ∈ R200×200 and the true solution x′ is randomly synthesized. The values bi are generated by adding Gaussian noise to Aix′. 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 performance is showed in Fig. 1. The distance to x∗ in Fig. 1a and the consensus error in Fig. 1c verify
that LEAD converges exponentially to the optimal consensual solution. It significantly outperforms most baselines and matches NIDS well under the same number of iterations. Fig. 1b demonstrates the benefit of compression when considering the communication bits. Fig. 1d shows that the compression error vanishes for both LEAD and CHOCO-SGD while the compression error is pretty large for QDGD and DeepSqueeze because they directly compress the local models.
Logistic regression. We further consider a logistic regression problem on the MNIST dataset. The regularization parameter is 10−4. We consider both homogeneous and heterogeneous data settings. In the homogeneous setting, the data samples are randomly shuffled before being uniformly partitioned 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 homogeneous setting to Appendix D.2. The results using full-batch gradient and mini-batch gradient (the mini-batch size is 512 for each agent) are showed in Fig. 2 and Fig. 3 respectively and both settings shows the faster convergence and higher precision of LEAD.
Neural network. We empirically study the performance of LEAD in optimizing deep neural network by training AlexNet (240 MB) on CIFAR10 dataset. The mini-batch size is 64 for each agents. Both the homogeneous and heterogeneous case are showed in Fig. 4. In the homogeneous case, CHOCO-SGD, DeepSqueeze and LEAD perform similarly and outperform the non-compressed variants in terms of communication efficiency, but CHOCO-SGD and DeepSqueeze need more efforts for parameter tuning because their convergence is sensitive to the setting of γ. In the heterogeneous 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 different agents are moving to 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.

heading: 6 CONCLUSION
text: In this paper, we investigate the communication compression in decentralized optimization. Motivated 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 enjoying the benefit of efficient communication. The nontrivial analyses on the coupled dynamics of inexact primal and dual updates as well as compression error establish the linear convergence of LEAD when full gradient is used and the linear convergence to the O(σ2) neighborhood of the optimum when stochastic gradient is used. Extensive experiments validate the theoretical analysis and demonstrate the state-of-the-art efficiency and robustness of LEAD. LEAD is also applicable to non-convex problems as empirically verified in the neural network experiments but we leave the non-convex analysis as the future work.

heading: ACKNOWLEDGEMENTS
text: Xiaorui Liu and Dr. Jiliang Tang are supported by the National Science Foundation (NSF) under grant numbers CNS-1815636, IIS-1928278, IIS-1714741, IIS-1845081, IIS-1907704, and IIS1955285. Yao Li and Dr. Ming Yan are supported by NSF grant DMS-2012439 and Facebook Faculty Research Award (Systems for ML). Dr. Rongrong Wang is supported by NSF grant CCF1909523.

heading: Contents of Appendix

heading: A LEAD in agent’s perspective 14

heading: B Connections with exiting works 14

heading: C Compression method 15
text: C.1 p-norm b-bits quantization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
C.2 Compression error . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

heading: D Experiments 17
text: D.1 Parameter sensitivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
D.2 Experiments in homogeneous setting . . . . . . . . . . . . . . . . . . . . . . . . . 17
D.3 Parameter settings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

heading: E Proofs of the theorems 19
text: E.1 Illustrative flow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
E.2 Two central Lemmas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
E.3 Proof of Lemma 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
E.4 Proof of Lemma 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
E.5 Proof of Theorem 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
E.6 Proof of Theorem 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

heading: A LEAD IN AGENT’S PERSPECTIVE
text: In the main paper, we described the algorithm with matrix notations for concision. Here we further provide a complete algorithm description from the agents’ perspective.
Algorithm 2 LEAD in Agent’s Perspective input: stepsize η, compression parameters (α, γ), initial values x0i , h1i , zi, ∀i ∈ {1, 2, . . . , n} output: xKi , ∀i ∈ {1, 2, . . . , n} or ∑n i=1 x K i
n
1: for each agent i ∈ {1, 2, . . . , n} do 2: d1i = zi − ∑ j∈Ni∪{i} wijzj
3: (hw)1i = ∑ j∈Ni∪{i} wij(hw) 1 j 4: x1i = x 0 i − η∇fi(x0i ; ξ0i ) 5: end for 6: for k = 1, 2, . . . ,K − 1 do in parallel for all agents i ∈ {1, 2, . . . , n} 7: compute ∇fi(xki ; ξki ) B Gradient computation 8: yki = x k i − η∇fi(xki ; ξki )− ηdki 9: qki = Compress(y k i − hki ) B Compression
10: ŷki = h k i + q k i 11: for neighbors j ∈ Ni do 12: Send qki and receive q k j B Communication 13: end for 14: (ŷw) k i = (hw) k i + ∑ j∈Ni∪{i} wijq k j 15: hk+1i = (1− α)hki + αŷki 16: (hw) k+1 i = (1− α)(hw) k i + α(ŷw) k i 17: dk+1i = d k i + γ 2η ( ŷki − (ŷw) k i
) 18: xk+1i = x k i − η∇fi(xki ; ξki )− ηd k+1 i B Model update 19: end for

heading: B CONNECTIONS WITH EXITING WORKS
text: The non-compressed variant of LEAD in Alg. 1 recovers NIDS (Li et al., 2019), D2 (Tang et al., 2018b) and Exact Diffusion (Yuan et al., 2018) as shown in Proposition 1. In Corollary 3, we show that the convergence rate of LEAD exactly recovers the rate of NIDS whenC = 0, γ = 1 and σ = 0. Proposition 1 (Connection to NIDS, D2 and Exact Diffusion). When there is no communication compression (i.e., Ŷk = Yk) and γ = 1, Alg. 1 recovers D2:
Xk+1 = I+W
2
( 2Xk −Xk−1 − η∇F(Xk; ξk) + η∇F(Xk−1; ξk−1) ) . (15)
Furthermore, if the stochastic estimator of the gradient∇F(Xk; ξk) is replaced by the full gradient, it recovers NIDS and Exact Diffusion with specific settings. Corollary 3 (Consistency with NIDS). When C = 0 (no communication compression), γ = 1 and σ = 0 (full gradient), LEAD has the convergence consistent with NIDS with η ∈ (0, 2/(µ+ L)]:
Lk+1 ≤ max { 1− µ(2η − µη2), 1− 1
2λmax((I−W)†)
} Lk. (16)
See the proof in E.5.
Proof of Proposition 1. Let γ = 1 and Ŷk = Yk. Combing Lines 4 and 6 of Alg. 1 gives
Dk+1 = Dk + I−W 2η (Xk − η∇F(Xk; ξk)− ηDk). (17)
Based on Line 7, we can represent ηDk from the previous iteration as
ηDk = Xk−1 −Xk − η∇F(Xk−1; ξk−1). (18)
Eliminating both Dk and Dk+1 by substituting (17)-(18) into Line 7, we obtain
Xk+1 = Xk − η∇F(Xk; ξk)− ( ηDk +
I−W 2
(Xk − η∇F(Xk; ξk)− ηDk) ) (from (17))
= I+W 2 (Xk − η∇F(Xk; ξk))− I+W 2 ηDk
= I+W 2 (Xk − η∇F(Xk; ξk))− I+W 2 (Xk−1 −Xk − η∇F(Xk−1; ξk−1)) (from (18))
= I+W
2 (2Xk −Xk−1 − η∇F(Xk; ξk) + η∇F(Xk−1; ξk−1)), (19)
which is exactly D2. It also recovers Exact Diffusion with A = I+W2 and M = ηI in Eq. (97) of (Yuan et al., 2018).

heading: C COMPRESSION METHOD

heading: C.1 P-NORM B-BITS QUANTIZATION
text: Theorem 3 (p-norm b-bit quantization). Let us define the quantization operator as
Qp(x) := ( ‖x‖p sign(x)2−(b−1) ) · ⌊ 2b−1|x| ‖x‖p + u ⌋ (20)
where · is the Hadamard product, |x| is the elementwise absolute value and u is a random dither vector uniformly distributed in [0, 1]d. Qp(x) is unbiased, i.e., EQp(x) = x, and the compression variance is upper bounded by
E‖x−Qp(x)‖2 ≤ 1
4 ‖ sign(x)2−(b−1)‖2‖x‖2p, (21)
which suggests that ∞-norm provides the smallest upper bound for the compression variance due to ‖x‖p ≤ ‖x‖q,∀x if 1 ≤ q ≤ p ≤ ∞. Remark 7. For the compressor defined in (20), we have the following the compression constant
C = sup x ‖ sign(x)2−(b−1)‖2‖x‖2p 4‖x‖2 .
Proof. Let denote v = ‖x‖p sign(x)2−(b−1), s = 2 b−1|x| ‖x‖p , s1 = ⌊ 2b−1|x| ‖x‖p ⌋ and s2 = ⌈ 2b−1|x| ‖x‖p ⌉ . We can rewrite x as x = s · v. For any coordinate i such that si = (s1)i, we have Qp(xi) = (s1)ivi with probability 1. Hence EQp(x)i = sivi = xi and
E(xi −Qp(x)i)2 = (xi − sivi)2 = 0.
For any coordinate i such that si 6= (s1)i, we have (s2)i − (s1)i = 1 and Qp(x)i satisfies
Qp(x)i = { (s1)ivi, w.p. (s2)i − si, (s2)ivi, w.p. si − (s1)i.
Thus, we derive
EQp(x)i = vi(s1)i(s2 − s)i + vi(s2)i(s− s1)i = visi(s2 − s1)i = visi = xi,
and
E[xi −Qp(x)i]2 = (xi − vi(s1)i)2(s2 − s)i + (xi − vi(s2)i)2(s− s1)i = (s2 − s1)ix2i + ( (s1)i(s2)i(s1 − s2)i + si((s2)2i − (s1)2i ) ) v2i − 2si(s2 − s1)ixivi
= x2i + ( − (s1)i(s2)i + si(s2 + s1)i ) v2i − 2sixivi
= (xi − sivi)2 + ( − (s1)i(s2)i + si(s2 + s1)i − s2i ) v2i
= (xi − sivi)2 + (s2 − s)i(s− s1)iv2i = (s2 − s)i(s− s1)iv2i
≤ 1 4 v2i .
Considering both cases, we have EQ(x) = x and E‖x−Qp(x)‖2 = ∑
{si=(s1)i}
E[xi −Qp(x)i]2 + ∑
{si 6=(s1)i}
E[xi −Qp(x)i]2
≤ 0 + 1 4 ∑ {si 6=(s1)i} v2i
≤ 1 4 ‖v‖2 = 1
4 ‖ sign(x)2−(b−1)‖2‖x‖2p.

heading: C.2 COMPRESSION ERROR
text: To verify Theorem 3, we compare the compression error of the quantization method defined in (20) with different norms (p = 1, 2, 3, . . . , 6,∞). Specifically, we uniformly generate 100 random vectors in R10000 and compute the average compression error. The result shown in Figure 5 verifies our proof in Theorem 3 that the compression error decreases when p increases. This suggests that ∞-norm provides the best compression precision under the same bit constraint. Under similar setting, we also compare the compression error with other popular compression methods, such as top-k and random-k sparsification. The x-axes represents the average bits needed to represent each element of the vector. The result is showed in Fig. 6. Note that intuitively top-k methods should perform better than random-k method, but the top-k method needs extra bits to transmitted the index while random-k method can avoid this by using the same random seed. Therefore, top-k method doesn’t outperform random-k too much under the same communication budget. The result in Fig. 6 suggests that∞-norm b-bits quantization provides significantly better compression precision than others under the same bit constraint.

heading: D EXPERIMENTS

heading: D.1 PARAMETER SENSITIVITY
text: In the linear regression problem, the convergence of LEAD under different parameter settings of α and γ are tested. The result showed in Figure 7 indicates that LEAD performs well in most settings and is robust to the parameter setting. Therefore, in this paper, we simply set α = 0.5 and γ = 1.0 for LEAD in all experiment, which indicates the minor effort needed for parameter tuning.

heading: D.2 EXPERIMENTS IN HOMOGENEOUS SETTING
text: 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-
Squeeze and CHOCO-SGD require to tune a smaller γ for convergence as showed in the parameter setting in Section D.3. Generally, a smaller γ decreases the model propagation between agents since γ 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.

heading: D.3 PARAMETER SETTINGS
text: The best parameter settings we search for all algorithms and experiments are summarized in Tables 1– 4. QDGD and DeepSqueeze are more sensitive to γ and CHOCO-SGD is slight more robust. LEAD is most robust to parameter settings and it works well for the setting α = 0.5 and γ = 1.0 in all experiments in this paper.

heading: E PROOFS OF THE THEOREMS
text: E.1 ILLUSTRATIVE FLOW
The following flow graph depicts the relation between iterative variables and clarifies the range of conditional expectation. {Gk}∞k=0 and {Fk}∞k=0 are two σ−algebras generated by the gradient sampling and the stochastic compression respectively. They satisfy
G0 ⊂ F0 ⊂ G1 ⊂ F1 ⊂ · · · ⊂ Gk ⊂ Fk ⊂ · · ·
(X1,D1,H1) (X2,D2,H2) (X3,D3,H3) (Xk,Dk,Hk) · · ·
Y1 Y2 Yk−1 Yk
F0 F1 Fk−2 Fk−1
∇F(X1;ξ1)∈G0 ∇F(X2;ξ2)∈G1 ··· ∇F(Xk;ξk)∈Gk−1E 1
1st round
E2
···
Ek−1
(k−1)th round
⊂ ··· ⊂
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-σ-algebras. The downward arrows
determine the range of F-σ-algebras. E.g., up to Ek, all random variables are in Fk−1 and up to ∇F(Xk; ξk), all random variables are in Gk−1 with Gk−1 ⊂ Fk−1. Throughout the appendix, without specification, E is the expectation conditioned on the corresponding stochastic estimators given the context.

heading: E.2 TWO CENTRAL LEMMAS
text: Lemma 1 (Fundamental equality). Let X∗ be the optimal solution, D∗ := −∇F(X∗) and Ek denote the compression error in the kth iteration, that is Ek = Qk − (Yk − Hk) = Ŷk − Yk. From Alg. 1, we have
‖Xk+1 −X∗‖2 + (η2/γ)‖Dk+1 −D∗‖2M =‖Xk −X∗‖2 + (η2/γ)‖Dk −D∗‖2M − (η2/γ)‖Dk+1 −Dk‖2M − η2‖Dk+1 −D∗‖2
− 2η〈Xk −X∗,∇F(Xk; ξk)−∇F(X∗)〉+ η2‖∇F(Xk; ξk)−∇F(X∗)‖2 + 2η〈Ek,Dk+1 −D∗〉,
where M := 2(I−W)†− γI and γ < 2/λmax(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. 1, if we take the expectation over the compression operator conditioned on the k-th iteration, we have
E‖Hk+1 −X∗‖2 ≤ (1− α)‖Hk −X∗‖2 + αE‖Xk+1 −X∗‖2 + αη2E‖Dk+1 −Dk‖2
+ 2αη2
γ E‖Dk+1 −Dk‖2M + α2E‖Ek‖2 − αγE‖Ek‖2I−W − α(1− α)‖Yk −Hk‖2.

heading: E.3 PROOF OF LEMMA 1
text: Before proving Lemma 1, we let Ek = Ŷk −Yk and introduce the following three Lemmas. Lemma 3. Let X∗ be the consensus solution. Then, from Line 4-7 of Alg. 1, we obtain
I−W 2η
(Xk+1 −X∗) = ( I
γ − I−W 2
) (Dk+1 −Dk)− I−W
2η Ek. (22)
Proof. From the iterations in Alg. 1, we have
Dk+1 = Dk + γ
2η (I−W)Ŷk (from Line 6)
= Dk + γ
2η (I−W)(Yk +Ek)
= Dk + γ
2η (I−W)(Xk − η∇F(Xk; ξk)− ηDk +Ek) (from Line 4)
= Dk + γ
2η (I−W)(Xk − η∇F(Xk; ξk)− ηDk+1 −X∗ + η(Dk+1 −Dk) +Ek)
= Dk + γ 2η (I−W)(Xk+1 −X∗) + γ 2 (I−W)(Dk+1 −Dk) + γ 2η (I−W)Ek,
where the fourth equality holds due to (I−W)X∗ = 0 and the last equality comes from Line 7 of Alg. 1. Rewriting this equality, and we obtain (22).
Lemma 4. Let D∗ = −∇F(X∗) ∈ span{I−W}, we have
〈Xk+1 −X∗,Dk+1 −Dk〉 =η γ ‖Dk+1 −Dk‖2M − 〈Ek,Dk+1 −Dk〉, (23) 〈Xk+1 −X∗,Dk+1 −D∗〉 =η γ 〈Dk+1 −Dk,Dk+1 −D∗〉M − 〈Ek,Dk+1 −D∗〉, (24)
where M = 2(I−W)† − γI and γ < 2/λmax(I−W) ensures the positive definiteness of M over span{I−W}.
Proof. Since Dk+1 ∈ span{I−W} for any k, we have
〈Xk+1 −X∗,Dk+1 −Dk〉 =〈(I−W)(Xk+1 −X∗), (I−W)†(Dk+1 −Dk)〉
=
〈 η
γ (2I− γ(I−W))(Dk+1 −Dk)− (I−W)Ek, (I−W)†(Dk+1 −Dk)
〉 (from (22))
=
〈 η
γ (2(I−W)† − γI
) (Dk+1 −Dk)−Ek,Dk+1 −Dk 〉 = η
γ ‖Dk+1 −Dk‖2M − 〈Ek,Dk+1 −Dk〉.
Similarly, we have
〈Xk+1 −X∗,Dk+1 −D∗〉 =〈(I−W)(Xk+1 −X∗), (I−W)†(Dk+1 −D∗)〉
=
〈 η
γ (2I− γ(I−W))(Dk+1 −Dk)− (I−W)Ek, (I−W)†(Dk+1 −D∗) 〉 = 〈 η
γ (2(I−W)† − I)(Dk+1 −Dk)−Ek,Dk+1 −D∗ 〉 = η
γ 〈Dk+1 −Dk,Dk+1 −D∗〉M − 〈Ek,Dk+1 −D∗〉.
To make sure that M is positive definite over span{I−W}, we need γ < 2/λmax(I−W).
Lemma 5. Taking the expectation conditioned on the compression in the kth iteration, we have 2ηE〈Ek,Dk+1 −D∗〉 = 2ηE 〈 Ek,Dk + γ
2η (I−W)Yk + γ 2η (I−W)Ek −D∗ 〉 = γE〈Ek, (I−W)Ek〉 = γE‖Ek‖2I−W,
2ηE〈Ek,Dk+1 −Dk〉 = 2ηE 〈 Ek, γ
2η (I−W)Yk + γ 2η (I−W)Ek 〉 = γE〈Ek, (I−W)Ek〉 = γE‖Ek‖2I−W.
Proof. The proof is straightforward and omitted here.
Proof of Lemma 1. From Alg. 1, we have
2η〈Xk −X∗,∇F(Xk; ξk)−∇F(X∗)〉 =2〈Xk −X∗, η∇F(Xk; ξk)− η∇F(X∗)〉 =2〈Xk −X∗,Xk −Xk+1 − η(Dk+1 −D∗)〉 (from Line 7) =2〈Xk −X∗,Xk −Xk+1〉 − 2η〈Xk −X∗,Dk+1 −D∗〉 =2〈Xk −X∗,Xk −Xk+1〉 − 2η〈Xk −Xk+1,Dk+1 −D∗〉 − 2η〈Xk+1 −X∗,Dk+1 −D∗〉 =2〈Xk −X∗ − η(Dk+1 −D∗),Xk −Xk+1〉 − 2η〈Xk+1 −X∗,Dk+1 −D∗〉 =2〈Xk+1 −X∗ + η(∇F(Xk; ξk)−∇F(X∗)),Xk −Xk+1〉 − 2η〈Xk+1 −X∗,Dk+1 −D∗〉 (from Line 7) =2〈Xk+1 −X∗,Xk −Xk+1〉+ 2η〈∇F(Xk; ξk)−∇F(X∗),Xk −Xk+1〉 − 2η〈Xk+1 −X∗,Dk+1 −D∗〉. (25)
Then we consider the terms on the right hand side of (25) separately. Using 2〈A − B,B − C〉 = ‖A−C‖2 − ‖B−C‖2 − ‖A−B‖2, we have
2〈Xk+1 −X∗,Xk −Xk+1〉 =2〈X∗ −Xk+1,Xk+1 −Xk〉 =‖Xk −X∗‖2 − ‖Xk+1 −Xk‖2 − ‖Xk+1 −X∗‖2. (26)
Using 2〈A,B〉 = ‖A‖2 + ‖B‖2 − ‖A−B‖2, we have
2η〈∇F(Xk; ξk)−∇F(X∗),Xk −Xk+1〉 =η2‖∇F(Xk; ξk)−∇F(X∗)‖2 + ‖Xk −Xk+1‖2 − ‖Xk −Xk+1 − η(∇F(Xk; ξk)−∇F(X∗))‖2
=η2‖∇F(Xk; ξk)−∇F(X∗)‖2 + ‖Xk −Xk+1‖2 − η2‖Dk+1 −D∗‖2. (from Line 7) (27)
Combining (25), (26), (27), and (23), we obtain
2η〈Xk −X∗,∇F(Xk; ξk)−∇F(X∗)〉 = ‖Xk −X∗‖2 − ‖Xk+1 −Xk‖2 − ‖Xk+1 −X∗‖2︸ ︷︷ ︸
2〈Xk+1−X∗,Xk−Xk+1〉
+ η2‖∇F(Xk; ξk)−∇F(X∗)‖2 + ‖Xk −Xk+1‖2 − η2‖Dk+1 −D∗‖2︸ ︷︷ ︸ 2η〈∇F(Xk;ξk)−∇F(X∗),Xk−Xk+1〉
− (2η2 γ 〈Dk+1 −Dk,Dk+1 −D∗〉M − 2η〈Ek,Dk+1 −D∗〉 ) ︸ ︷︷ ︸
2η〈Xk+1−X∗,Dk+1−D∗〉
=‖Xk −X∗‖2 − ‖Xk+1 −Xk‖2 − ‖Xk+1 −X∗‖2
+ η2‖∇F(Xk; ξk)−∇F(X∗)‖2 + ‖Xk −Xk+1‖2 − η2‖Dk+1 −D∗‖2
+ η2
γ
( ‖Dk −D∗‖2M − ‖Dk+1 −D∗‖2M − ‖Dk+1 −Dk‖2M ) ︸ ︷︷ ︸
−2〈Dk+1−Dk,Dk+1−D∗〉M
+2η〈Ek,Dk+1 −D∗〉,
where the last equality holds because
2〈Dk −Dk+1,Dk+1 −D∗〉M =‖Dk −D∗‖2M − ‖Dk+1 −D∗‖2M − ‖Dk+1 −Dk‖2M.
Thus, we reformulate it as
‖Xk+1 −X∗‖2 + η 2
γ ‖Dk+1 −D∗‖2M
=‖Xk −X∗‖2 + η 2
γ ‖Dk −D∗‖2M −
η2
γ ‖Dk+1 −Dk‖2M − η2‖Dk+1 −D∗‖2
− 2η〈Xk −X∗,∇F(Xk; ξk)−∇F(X∗)〉+ η2‖∇F(Xk; ξk)−∇F(X∗)‖2 + 2η〈Ek,Dk+1 −D∗〉,
which completes the proof.

heading: E.4 PROOF OF LEMMA 2
text: Proof of Lemma 2. From Alg. 1, we take the expectation conditioned on kth compression and obtain
E‖Hk+1 −X∗‖2
=E‖(1− α)(Hk −X∗) + α(Yk −X∗) + αEk‖2 (from Line 13) =‖(1− α)(Hk −X∗) + α(Yk −X∗)‖2 + α2E‖Ek‖2
=(1− α)‖Hk −X∗‖2 + α‖Yk −X∗‖2 − α(1− α)‖Hk −Yk‖2 + α2E‖Ek‖2. (28)
In the second equality, we used the unbiasedness of the compression, i.e., EEk = 0. The last equality holds because of
‖(1− α)A+ αB‖2 = (1− α)‖A‖2 + α‖B‖2 − α(1− α)‖A−B‖2.
In addition, by taking the conditional expectation on the compression, we have
‖Yk −X∗‖2 =‖Xk − η∇F(Xk; ξk)− ηDk −X∗‖2 (from Line 4) =E‖Xk+1 + ηDk+1 − ηDk −X∗‖2 (from Line 7) =E‖Xk+1 −X∗‖2 + η2E‖Dk+1 −Dk‖2 + 2ηE〈Xk+1 −X∗,Dk+1 −Dk〉 =E‖Xk+1 −X∗‖2 + η2E‖Dk+1 −Dk‖2
+ 2η2
γ E‖Dk+1 −Dk‖2M − 2ηE〈Ek,Dk+1 −Dk〉. (from (23))
=E‖Xk+1 −X∗‖2 + η2E‖Dk+1 −Dk‖2
+ 2η2
γ E‖Dk+1 −Dk‖2M − γE‖Ek‖2I−W. (from Line 6) (29)
Combing the above two equations (28) and (29) together, we have
E‖Hk+1 −X∗‖2
≤(1− α)‖Hk −X∗‖2 + αE‖Xk+1 −X∗‖2 + αη2E‖Dk+1 −Dk‖2 + 2αη 2
γ E‖Dk+1 −Dk‖2M
− αγE‖Ek‖2I−W + α2E‖Ek‖2 − α(1− α)‖Yk −Hk‖2, (30) which completes the proof.

heading: E.5 PROOF OF THEOREM 1
text: Proof of Theorem 1. Combining Lemmas 1, 2, and 5, we have the expectation conditioned on the compression satisfying
E‖Xk+1 −X∗‖2 + η 2
γ E‖Dk+1 −D∗‖2M + a1E‖Hk+1 −X∗‖2
≤‖Xk −X∗‖2 + η 2
γ ‖Dk −D∗‖2M −
η2
γ E‖Dk+1 −Dk‖2M − η2E‖Dk+1 −D∗‖2
− 2η〈Xk −X∗,∇F(Xk; ξk)−∇F(X∗)〉+ η2‖∇F(Xk; ξk)−∇F(X∗)‖2 + γE‖Ek‖2I−W + a1(1− α)‖Hk −X∗‖2 + a1αE‖Xk+1 −X∗‖2 + a1αη2E‖Dk+1 −Dk‖2
+ 2a1αη
2
γ E‖Dk+1 −Dk‖2M + a1α2E‖Ek‖2 − a1αγE‖Ek‖2I−W − a1α(1− α)‖Yk −Hk‖2
= ‖Xk −X∗‖2 − 2η〈Xk −X∗,∇F(Xk; ξk)−∇F(X∗)〉+ η2‖∇F(Xk; ξk)−∇F(X∗)‖2︸ ︷︷ ︸ A
+ a1αE‖Xk+1 −X∗‖2 + η2
γ ‖Dk −D∗‖2M − η2E‖Dk+1 −D∗‖2
+ a1(1− α)‖Hk −X∗‖2−(1− 2a1α) η2
γ E‖Dk+1 −Dk‖2M + a1αη2E‖Dk+1 −Dk‖2︸ ︷︷ ︸
B
+ a1α 2E‖Ek‖2 + (1− a1α)γE‖Ek‖2I−W − a1α(1− α)‖Yk −Hk‖2︸ ︷︷ ︸
C
, (31)
where a1 is a non-negative number to be determined. Then we deal with the three terms on the right hand side separately. We want the terms B and C to be nonpositive. First, we consider B. Note that Dk ∈ Range(I−W). If we want B ≤ 0, then, we need 1−2a1α > 0, i.e., a1α < 1/2. Therefore we have
B =− (1− 2a1α) η2
γ E‖Dk+1 −Dk‖2M + a1αη2E‖Dk+1 −Dk‖2 ≤ ( a1α−
(1− 2a1α)λn−1(M) γ
) η2E‖Dk+1 −Dk‖2,
where λn−1(M) > 0 is the second smallest eigenvalue of M. It means that we also need
a1α+ (2a1α− 1)λn−1(M)
γ ≤ 0,
which is equivalent to
a1α ≤ λn−1(M)
γ + 2λn−1(M) < 1/2. (32)
Then we look at C. We have C =a1α2E‖Ek‖2 + (1− a1α)γE‖Ek‖2I−W − a1α(1− α)‖Yk −Hk‖2
≤((1− a1α)βγ + a1α2)E‖Ek‖2 − a1α(1− α)‖Yk −Hk‖2
≤C((1− a1α)βγ + a1α2)‖Yk −Hk‖2 − a1α(1− α)‖Yk −Hk‖2
Because we have 1− a1α > 1/2, so we need C((1− a1α)βγ + a1α2)− a1α(1− α) = (1 + C)a1α2 − a1(Cβγ + 1)α+ Cβγ ≤ 0. (33)
That is
α ≥ a1(Cβγ + 1)− √ a21(Cβγ + 1)
2 − 4(1 + C)Ca1βγ 2(1 + C)a1 =: α0, (34)
α ≤ a1(Cβγ + 1) + √ a21(Cβγ + 1)
2 − 4(1 + C)Ca1βγ 2(1 + C)a1 =: α1. (35)
Next, we look at A. Firstly, by the bounded variance assumption, we have the expectation conditioned on the gradient sampling in kth iteration satisfying
E‖Xk −X∗‖2 − 2ηE〈Xk −X∗,∇F(Xk; ξk)−∇F(X∗)〉+ η2E‖∇F(Xk; ξk)−∇F(X∗)‖2
≤‖Xk −X∗‖2 − 2η〈Xk −X∗,∇F(Xk)−∇F(X∗)〉+ η2‖∇F(Xk)−∇F(X∗)‖2 + nη2σ2
Then with the smoothness and strong convexity from Assumptions 4, we have the co-coercivity of ∇gi(x) with gi(x) := fi(x)− u2 ‖x‖ 2 2, which gives
〈Xk −X∗,∇F(Xk)−∇F(X∗)〉 ≥ µL µ+ L ‖Xk −X∗‖2 + 1 µ+ L ‖∇F(Xk)−∇F(X∗)‖2.
When η ≤ 2/(µ+ L), we have
〈Xk −X∗,∇F(Xk)−∇F(X∗)〉
= ( 1− η(µ+ L)
2
) 〈Xk −X∗,∇F(Xk)−∇F(X∗)〉+ η(µ+ L)
2 〈Xk −X∗,∇F(Xk)−∇F(X∗)〉
≥ ( µ− ηµ(µ+ L)
2 + ηµL 2
) ‖Xk −X∗‖2 + η
2 ‖∇F(Xk)−∇F(X∗)‖2
=µ ( 1− ηµ
2
) ‖Xk −X∗‖2 + η
2 ‖∇F(Xk)−∇F(X∗)‖2.
Therefore, we obtain
− 2η〈Xk −X∗,∇F(Xk)−∇F(X∗)〉 ≤ − η2‖∇F(Xk)−∇F(X∗)‖2 − µ(2η − µη2)‖Xk −X∗‖2. (36)
Conditioned on the kthe iteration, (i.e., conditioned on the gradient sampling in kth iteration), the inequality (31) becomes
E‖Xk+1 −X∗‖2 + η 2
γ E‖Dk+1 −D∗‖2M + a1E‖Hk+1 −X∗‖2
≤ ( 1− µ(2η − µη2) ) ‖Xk −X∗‖2 + a1αE‖Xk+1 −X∗‖2
+ η2
γ ‖Dk −D∗‖2M − η2E‖Dk+1 −D∗‖2 + a1(1− α)‖Hk −X∗‖2 + nη2σ2, (37)
if the step size satisfies η ≤ 2µ+L . Rewriting (37), we have
(1− a1α)E‖Xk+1 −X∗‖2 + η2
γ E‖Dk+1 −D∗‖2M + η2E‖Dk+1 −D∗‖2 + a1E‖Hk+1 −X∗‖2
≤ ( 1− µ(2η − µη2) ) ‖Xk −X∗‖2 + η 2
γ ‖Dk −D∗‖2M + a1(1− α)‖Hk −X∗‖2 + nη2σ2,
(38)
and thus
(1− a1α)E‖Xk+1 −X∗‖2 + η2
γ E‖Dk+1 −D∗‖2M+γI + a1E‖Hk+1 −X∗‖2
≤ ( 1− µ(2η − µη2) ) ‖Xk −X∗‖2 + η 2
γ ‖Dk −D∗‖2M + a1(1− α)‖Hk −X∗‖2 + nη2σ2.
(39)
With the definition of Lk in (12), we have
ELk+1 ≤ ρLk + nη2σ2, (40)
with
ρ = max
{ 1− µ(2η − µη2)
1− a1α ,
λmax(M)
γ + λmax(M) , 1− α
} .
where λmax(M) = 2λmax((I−W)†)− γ.
Recall all the conditions on the parameters a1, α, and γ to make sure that ρ < 1:
a1α ≤ λn−1(M)
γ + 2λn−1(M) , (41)
a1α ≤ µ(2η − µη2), (42) α ≥ a1(Cβγ + 1)− √ a21(Cβγ + 1)
2 − 4(1 + C)Ca1βγ 2(1 + C)a1 =: α0, (43)
α ≤ a1(Cβγ + 1) + √ a21(Cβγ + 1)
2 − 4(1 + C)Ca1βγ 2(1 + C)a1 =: α1. (44)
In the following, we show that there exist parameters that satisfy these conditions.
Since we can choose any a1, we let
a1 = 4(1 + C)
Cβγ + 2 ,
such that
a21(Cβγ + 1) 2 − 4(1 + C)Ca1βγ = a21.
Then we have
α0 = Cβγ
2(1 + C) → 0, as γ → 0,
α1 = Cβγ + 2 2(1 + C) → 1 1 + C , as γ → 0.
Conditions (43) and (44) show a1α ∈ [ 2Cβγ
Cβγ + 2 , 2
] → [0, 2], if C = 0 or γ → 0.
Hence in order to make (41) and (42) satisfied, it’s sufficient to make
2Cβγ
Cβγ + 2 ≤ min
{ λn−1(M)
γ + 2λn−1(M) , µ(2η − µη2)
} = min { 2 β − γ 4 β − γ , µ(2η − µη2) } . (45)
where we use λn−1(M) = 2λmax(I−W) − γ = 2 β − γ.
When C > 0, the condition (45) is equivalent to
γ ≤ min
{ (3C + 1)− √ (3C + 1)2 − 4C Cβ , 2µη(2− µη) [2− µη(2− µη)]Cβ } . (46)
The first term can be simplified using (3C + 1)− √ (3C + 1)2 − 4C Cβ ≥ 2 (3C + 1)β due to √ 1− x ≤ 1− x2 when x ∈ (0, 1).
Therefore, for a given stepsize η, if we choose γ ∈ ( 0,min { 2 (3C + 1)β , 2µη(2− µη) [2− µη(2− µη)]Cβ }) and
α ∈ [ Cβγ
2(1 + C) ,min {Cβγ + 2 2(1 + C) , 2− βγ 4− βγ Cβγ + 2 4(1 + C) , µη(2− µη)Cβγ + 2 4(1 + C) }] ,
then, all conditions (41)-(44) hold.
Note that γ < 2(3C+1)β implies γ < 2 β , which ensures the positive definiteness of M over span{I− W} in Lemma 4. Note that η ≤ 2µ+L ensures
µη(2− µη)Cβγ + 2 4(1 + C) ≤ Cβγ + 2 2(1 + C) . (47)
So, we can simplify the bound for α as α ∈ [ Cβγ
2(1 + C) ,min {2− βγ 4− βγ Cβγ + 2 4(1 + C) , µη(2− µη)Cβγ + 2 4(1 + C) }] .
Lastly, taking the total expectation on both sides of (40) and using tower property, we complete the proof for C > 0.
Proof of Corollary 1. Let’s first define κf = Lµ and κg = λmax(I−W) λ+min(I−W) = λmax(I −W)λmax((I − W)†).
We can choose the stepsize η = 1L such that the upper bound of γ is
γupper =min { 2 (3C + 1)β ,
2 κf ( 2− 1κf ) [ 2− 1κf ( 2− 1κf )] Cβ , 2 β } ≥ min { 2 (3C + 1)β , 1 κfCβ } ,
due to x(2−x)2−x(2−x) ≥ x 2−x ≥ x when x ∈ (0, 1).
Hence we can take γ = min{ 1(3C+1)β , 1 κfCβ }.
The bound of α is α ∈ [ Cβγ
2(1 + C) ,min { 2− βγ 4− βγ Cβγ + 2 4(1 + C) , 1 κf (2− 1 κf ) Cβγ + 2 4(1 + C) }] When γ is chosen as 1κfCβ , pick
α = Cβγ
2(1 + C) =
1
2(1 + C)κf . (48)
When 1(3C+1)β ≤ 1 κfCβ , the upper bound of α is
αupper = min { 2− βγ 4− βγ Cβγ + 2 4(1 + C) , 1 κf (2− 1 κf ) Cβγ + 2 4(1 + C) } = min { 6C + 1
12C + 3 , 1 κf (2− 1 κf )
} 7C + 2
4(C + 1)(3C + 1) ≥ min { 6C + 1
12C + 3 , 1
κf
} 7C + 2
4(C + 1)(3C + 1) .
In this case, we pick
α = min
{ 6C + 1
12C + 3 , 1
κf
} 7C + 2
4(C + 1)(3C + 1) . (49)
Note α = O (
1 (1+C)κf ) since 6C+112C+3 is lower bounded by 1 3 . Hence in both cases (Eq. (48) and
Eq. (49)), α = O (
1 (1+C)κf
) , and the third term of ρ is upper bounded by
1− α ≤ max { 1− 1
2(1 + C)κf , 1−min
{ 6C + 1
12C + 3 , 1
κf
} 7C + 2
4(1 + C)(3C + 1) } In two cases of γ, the second term of ρ becomes
1− γ 2λmax((I−W)†) = max
{ 1− 1
2Cκfκg , 1− 1 (1 + 3C)κg
}
Before analysing the first term of ρ, we look at a1α in two cases of γ. When γ = 1κfCβ ,
a1α = 2Cβγ
Cβγ + 2 =
2 2κf + 1 ≤ 1 κf .
When γ = 1(3C+1)β ,
a1α = min
{ 6C + 1
(12C + 3) , 1
κf } ≤ 1 κf .
In both cases, a1α ≤ 1κf . Therefore, the first term of ρ becomes
1− µη(2− µη) 1− a1α ≤ 1− 1κf (2− 1 κf ) 1− 1κf = 1− 1− 1κf κf − 1 = 1− 1 κf .
To summarize, we have ρ ≤ 1−min { 1
κf ,
1
2Cκfκg ,
1
(1 + 3C)κg ,
1
2(1 + C)κf ,min
{ 6C + 1
12C + 3 , 1
κf
} 7C + 2
4(1 + C)(3C + 1)
}
and therefore
ρ = max { 1−O ( 1 (1 + C)κf ) , 1−O ( 1 (1 + C)κg ) , 1−O ( 1 Cκfκg )} .
With full-gradient (i.e., σ = 0), we get −accuracy solution with the total number of iterations
k ≥ Õ((1 + C)(κf + κg) + Cκfκg).
When C = 0, i.e., there is no compression, the iteration complexity recovers that of NIDS, Õ (κf + κg) .
When C ≤ κf+κgκfκg+κf+κg , 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 2. Note that (xk)> = Xk and 1n×1X∗ = X∗, then n∑ i=1 E‖xki − xk‖2 = E ∥∥Xk − 1n×1Xk∥∥2
= E ∥∥Xk −X∗ +X∗ − 1n×1Xk∥∥2
= E ∥∥∥∥Xk −X∗ − 1n×11>n×1n (Xk −X∗) ∥∥∥∥ ≤ E‖Xk −X∗‖2
≤ ρEL k−1 + nη2σ2(1− ρ)−1
1− a1α
≤ 2ρkL0 + 2nη 2σ2
1− ρ . (50)
The last inequality holds because we have a1α ≤ 1/2.
Proof of Corollary 3. From the proof of Theorem 1, when C = 0, we can set γ = 1, α = 1, and a1 = 0. Plug those values into ρ, and we obtain the convergence rate for NIDS.

heading: E.6 PROOF OF THEOREM 2
text: Proof of Theorem 2. In order to get exact convergence, we pick diminishing step-size, set α = Cβγ 2(1+C) , a1α = 2Cβγk Cβγk+2 , θ1 = 12λmax((I−W)†) and θ2 = Cβ 2(1+C) , then
ρk = max
{ 1− µηk(2− µηk)− a1α
1− a1α , 1− θ1γk, 1− θ2γk } If we further pick diminishing ηk and γk such that µηk(2− µηk)− a1α ≥ a1α, then
µηk(2− µηk)− a1α 1− a1α ≥ a1α 1− a1α = 2Cβγk 2− Cβγk ≥ Cβγk.
Notice that Cβγ ≤ 23 since (3C + 1) − √ (3C + 1)2 − 4C is increasing in C > 0 with limit 23 at ∞. In this case we only need,
γk ∈ ( 0,min { (3C + 1)−√(3C + 1)2 − 4C Cβ , 2µηk(2− µηk) [4− µηk(2− µηk)]Cβ , 2 β }) . (51)
And ρk ≤ max {1− Cβγk, 1− θ1γk, 1− θ2γk} ≤ 1− θ3γk
if θ3 = min{θ1, θ2} and note that θ2 ≤ Cβ. We define
Lk := (1− a1αk)‖Xk −X∗‖2 + (2η2k/γk)E‖Dk+1 −D∗‖2(I−W)† + a1‖H k −X∗‖2.
Hence ELk+1 ≤ (1− θ3γk)ELk + nσ2η2k.
From a1α ≤ µηk(2−µηk)2 , we get
4Cβγk Cβγk + 2 ≤ µηk(2− µηk).
If we pick γk = θ4ηk, then it’s sufficient to let
2Cβθ4ηk ≤ µηk(2− µηk).
Hence if θ4 < µCβ and let η∗ = 2(µ−Cβθ4) µ2 , then ηk = γk θ4 ∈ (0, η∗) guarantees the above discussion and ELk+1 ≤ (1− θ3θ4ηk)ELk + nσ2η2k.
So far all restrictions for ηk are
ηk ≤ min { 2
µ+ L , η∗ } and
ηk ≤ 1
θ4 min
{ (3C + 1)− √ (3C + 1)2 − 4C Cβ , 2 β }
Let θ5 = min { 2 µ+L , η∗, (3C+1)− √ (3C+1)2−4C Cβθ4 , 2βθ4 } , ηk = 1Bk+A and D = max { AL0, 2nσ 2 θ3θ4 } ,
we claim that if we pick B = θ3θ42 and some A, by setting ηk = 2 θ3θ4k+2A , we get
ELk ≤ D Bk +A .
Induction: When k = 0, it’s obvious. Suppose previous k inequalities hold. Then
ELk+1 ≤ ( 1− 2θ3θ4
θ3θ4k + 2A
) 2D
θ3θ4k + 2A +
4nσ2
(θ3θ4k + 2A)2 .
Multiply M := (θ3θ4k + θ3θ4 + 2A)(θ3θ4k + 2A)(2D)−1 on both sides, we get MELk+1 ≤ ( 1− 2θ3θ4
θ3θ4k + 2A
) (θ3θ4k + θ3θ4 + 2A) + 4nσ2(θ3θ4k + θ3θ4 + 2A)
2D(θ3θ4k + 2A)
= 2D(θ3θ4k + 2A− 2θ3θ4)(θ3θ4k + θ3θ4 + 2A) + 4nσ2(θ3θ4k + θ3θ4 + 2A)
2D(θ3θ4k + 2A)
= 2D(θ3θ4k + 2A) 2 + 4nσ2(θ3θ4k + 2A)− 4Dθ3θ4(θ3θ4k + 2A) + 2Dθ3θ4(θ3θ4k + 2A) 2D(θ3θ4k + 2A)
+ −4D(θ3θ4)2 + 4nσ2θ3θ4
2D(θ3θ4k + 2A)
≤θ3θ4k + 2A.
Hence ELk+1 ≤ 2D
θ3θ4(k + 1) + 2A
This induction holds for any A such that ηk is feasible, i.e.
η0 = 1
A ≤ θ5.
Here we summarize the definition of constant numbers:
θ1 = 1
2λmax((I−W)†) , θ2 =
Cβ
2(1 + C) , (52) θ3 = min{θ1, θ2}, θ4 ∈ ( 0, µ
Cβ
) , η∗ =
2(µ− Cβθ4) µ2 , (53)
θ5 = min
{ 2
µ+ L , η∗,
(3C + 1)− √ (3C + 1)2 − 4C
Cβθ4 ,
2
βθ4
} . (54)
Therefore, let A = 1θ5 and ηk = 2θ5 θ3θ4θ5k+2 , we get
1 n ELk ≤
2max {
1 nL
0, 2σ 2θ5
θ3θ4 } θ3θ4θ5k + 2 .
Since 1− a1αk ≥ 1/2, we complete the proof.

Review summaries:
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. 

This 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.