Compressed Decentralized Momentum Stochastic Gradient Methods for Nonconvex Optimization
Authors: Wei Liu
Anweshit Panda
Ujwal Pandey
Christopher Brissette
Yikang Shen
George Slota
Naigang Wang
Jie Chen
Yangyang Xu
Venue: Accepted by TMLR ()

Abstract: In this paper, we design two  compressed decentralized algorithms for solving nonconvex stochastic optimization under two different scenarios. Both algorithms adopt a momentum technique to achieve fast convergence and a message-compression technique to save communication costs. Though momentum acceleration and compressed communication have been used in literature, it is highly nontrivial to theoretically prove the effectiveness of their composition in a decentralized algorithm that can maintain the benefits of both sides, because of the need to simultaneously control the consensus error, the compression error, and the bias from the momentum gradient. 

For the scenario where gradients are bounded,  our proposal is a compressed decentralized adaptive method. To the best of our knowledge, this is the first decentralized adaptive stochastic gradient method with compressed communication.  For the scenario of data heterogeneity without bounded gradients, our proposal is a compressed decentralized heavy-ball method, which applies a gradient tracking technique to address the challenge of data heterogeneity.  Notably, both methods achieve an optimal convergence rate, and they can achieve linear speed up and adopt topology-independent algorithmic parameters within a certain regime of the user-specified error tolerance. Superior empirical performance is observed over state-of-the-art methods on training deep neural networks (DNNs) and Transformers.

Jie Chen Compressed Decentralized Momentum Stochastic Gradient Methods for Nonconvex Optimization
Wei Liu
lwdsdqgb Ggmall com
Deportment of Mathematical Sciences
Rensselaer Polytechnic Institute
Anweshit Panda
pandaa2@rpii.cmm edu
Department of Computer Science
Rensselaer Polytechnic Institute
Ujwal Pandey
pondeu@rpi.cm edu
Department of Computer Science
Rensselaer Polytecknic Institute
Christopher Brissette
brisscrrpi..cm edu
Department of Computer Science Rensselaer Polylechmic Institute
Yikang Shen
yikang. shn akn&@gmaill.. com
MIT-IBM Watson Lab, IBM Research
George M. Slota
slotag @rpii edu
Department of Computer Science
Rensselaer Polylechnic Institute
Naigang Wang
swangghus.ibm.
IBM T. J. Wotson Research Center
chenjic@us..o ibm.
MIT-IBM Watson Al Lab, IBM Research
Yangyang Xu*
auy21 @trpi. edu
Department of Mathematical Sciences Rensselaer Polytechnic Institute
Abstract
In this paper, design two compressed decentralized algorithms for solving nonconvex stochastic optimization under two different scenarios. Both algorithms adopt momentum technique to achieve fast convergence and message-compression technique to save commu- nication costs. Though momentum acceleration and compressed communication have been used in literature, it is highly nontrivial to theoretically prove the effectiveness of their com- position in decentralized algorithm that can maintain the benefits of both sides, because of the need to simultancously control the consensus error, the compression error, and the bias from the momentum gradient.
For the scenario where gradients are bounded, our proposal is a compressed decentralized adaptive method. To the best of our knowledge, this is the first decentralized adaptive stochastic gradient method with compressed communication. For the scenario of data het- erogeneity without bounded gradients, our proposal is compressed decentralized heavy-ball
* *Corresponding author

---

method, which applies gradient tracking technique to address the challenge of data hetero- geneity. Notably, both methods achieve an optimal convergence rate, and they can achieve linear speed up and adopt opplogy-independentt algorithmic parameters within a certain regime of the uscr-specified error tolerance. Superior empirical performance observed over state-of-the-arl methods on training deep neural networks (DNNs) and Transformers.
1 Introduction
In this paper, we consider multi-agent nonconvex stochastic optimization problems in the form of
1 Σ f(x), with f((x) = BE [1] Ei)]
min f(x) = xERd
(1)
1=1
Here, we suppose that there are agents on connected graph G; for cach i E [m] := fl...., n), the functions Ji and F; are owned and can be accessed directly only by the i-th agent; {Di)== are possibly non-i.i.d data distributions or represent heterogeneous datasets; the n agents collaboratively solve (1) by communicating messages to their 1-hop neighbors on g. Applications of training DNNs with pro-collected data can be formulated into (T), where the data {D:) are collected by (or distributed onto) agents. Similarly, the data for training large language models consist of diverse corpora that are non-i.i.d We are interested in problems that are in the form of [ and satisfy the following structural assumption.
Assumption 1 In [ for each i E [n]], the function fi is L-smooth, i.e., [[V]((x)~ Vf(Y)ls L||x yll, for any x,y Rd, and I is lower boundedd, i.e,, S 2 minx f(x) -00.
1.1
Motivation and challenges
The stochastic gradient method (SGM) RRobbins & Monro. 1951 Nemirovski et al. 2009 Ghadimi & Lan
2013
Bottou et al.] 2018) and its varions momentum-based or adaptive variants Kingmaa & Ba 2014 Reddi
ct al. 2018 Duchi et al. 2011 Xu & Xu 2023 Cutkosky & Orabona 2019 are now the workhorse for training DNNs and Transformers. Compared to the classic SGM, the momentum or adaptive SGMs are usually significantly faster to reach the same level of accuracy. On the other hand, for solving multi-agent stochastic optimization problems in the form of (1) docentralizod SGMs have boen designed and analyzed in
many papers. However, most existing decentralized methods are about classic SGMs, e-g., Lian e.g.,Lian
al. (2017):
Tang al. (2018): Lian et al.
(018); Zhao et al.
(002aa): Yan et al.
2023 and few about momentum
adaptive SGMs (Nazari et al.
2022 Chen et al.
2023b Xiao et al.
2023 To save communication cost,
certain message-compression technique has been adopted in many
works Yan et al. 2023 Zhao et al.
2022a: Koloskova et al.) 2019: Song et al.) 2022 Taheri et. al. 2020 Seide et al. 2014 Tang et al. 2019b)
for distributed algorithms. remains unknown whether a compression technique can be incorporated into a momentum or adaptive decentralized SGM, to simultaneously achieve fast convergence, low communication cost, and linear speedup for solving nonconvex multi-agent optimization problems.
Unlike in centralized environment, it is difficult to keep at the same status the information held by the multiple agents in decentralized system, due to the communication restriction. This difficulty makes it challenging to ensure the convergence or show an optimal complexity result of a momentum cannentuu-based or adaptive decentralized SGM, especially when data are heterogenious across the agents.
1.2 Our contributions
Our contributions are threc-fold. First, on solving multi-agent nonconvex stochastic optimization, we design two decentralized momentum-based SGMs with the option of message compression to save communication costs. Our first method, called DAMSCo and given in Alg. [ is a compressed decentralized version of AMSGrad (Reddi et al., (2018) that adopts adaptive updates for fast convergence; our sccond method, called DaSHCo and given in Alg. is designed by using the heavy-ball acceleration technique (Polyak] 1964
Ochs et al. 2014
Xu et al. 2022). To the best of our knowledge, methods the first. decentralized
2

---

SGMs that adopt compression technique together with momentum-basee or adaptive learning rate to accelerate empirical convergence. Compared to the decentralized adaptive methods in Chen et al. (2023b), our method DAMSCo needs only one round of communication per update and enables message compression, leading to significant higher communication efficiency while maintaining fast convergence. Though the method in Nazari el al. (2022) also needs only a single round of communication per update, relies on full- message communication and more problematically, does not have guaranteed convergence to stationarity for nonconvex optimization, as pointed out in Chen et al. (2023b). Compared the gradient tracking based decentralized method in Xiao et al. (0023), method DaSHCo is more communication efficient by using two rounds of communication (compared to three rounds in Xiao et al. (023) per update and enabling compressed communication.
Second, we analyze the convergence rate of DAMSCo under the assumption of bounded sample gradients
standard for analyzing adaptive SGMs (Kingma & Ba 2014 Reddi al. 2018 Chen et al. 2023b, 2019
Xu al. 2023), and the assumption of nonexpansiveness of the compression error. The analysis is highly non-trivial as it needs to handle the challenges raised by the coexistence of nonconvexily, decentralization, compression, stochasticity variance, and the adaptive update. By meticulously controlling the errors caused by stochasticity, docentralization, compression, and adaptive learning rate, we show that DAMSCo can achieve a convergence rate of A in terms of expected norm-square of the objective's gradient and consensus deviation at all agents' local iterates, where T is the number of updates. The rate is optimal for smooth nonconvex stochastic optimization and matches with the lower bound established in [Arjevani et al. (203)). In addition, DAMSCo enjoys linear speed up with respect the number n of agents in a certain region of (T and its learning rate can be independent of the topology of the communication graph. Empirically, we obscrve significantly faster convergence of DAMSCo over cxisting docentralized adaptive SGMs on homogeneous data, in terms of the communication rounds.
Third, we analyze the convergence rate of DaSHCo in the scenario of heterogeneous data. By using the gradient tracking tochnique, we relax the assumption of bounded sample gradicnts, which is required by DAMSCo and most existing adaptive SGMs. With the nonexpansiveness condition of the compression error, we show that DaSHCo also converges to a stationary and consensual point, in expectation, at the optimal rate of O 2). Similar to DAMSCo, DaSHCo achieves lincar speed up with respect to the number of agents and can use topology-independen based acceleration, the linear speed up is another significant advantage of DaSHCo over the compressed decentralized method CDProSSGT in Yan et al. (2023). Empirically DaSHCo exhibits significantly faster convergence than CDProXSGT on both homogencous and heterogencous data, in particular for complicated neural architectures.
learning rate in regime of T. In addition to the momentum-
To highlight the advantage and novelty of our methods, we compare them few closely relevant methods in Table More detailed comparisons are given in Appendix D In addition to these theoretical highlights, the proposed methods significantly improve the training efficiency of large-scale neural networks. The theoretical and empirical findings contribute to broader understanding of decentralized adaptive gradient techniques and may inspire further research.
1.3 Notations
We denote [4] (I.. |I-1| is used for the Euclidean norm of a vector and the Frobenius norm of a matrix and |/ is for the spectral norm of matrix A. For two vectors and b of the same size, and a b respectively denote the componentwise division and multiplication, and vc takes a componentwise square root of a nonnegative vector c.
To solve (1) in a decentralized manner, we introduce a local copy of variable, denoted as 24, for the i-th agent for each E [n). We let X [x1, X2,..,,... x,] Rdxa concatinate all local variables. I is reserved for the identity matrix and 1 for all-one vector of appropriate size. Also, we denote
VP' /V/i (x.))...,
..... V.n. (xx)], VF [VF (x):51) ..... Va
3

---

strong condition
Methods
CMP
(AG, MMT)
DH
LS
TI
CMR
DADAM (Nazari et al. 2022
X
X
/
1
bounded gradient bounded gradient bounded gradient
DAGM
Chen et. al. 2023b
X
X
/
/
2
Choco-SGD
Koloskova et al. 2019
V
(X, X)
X
/
/
1
strong convexity
BEER ZZao et al. 2022a
(X, X)
/
/
2
big batch
CDProxSGT Yan et al. 2023
(x, X)
/
/
/
2
none bounded gradient
DAMSCo (this paper)
x
/
1
DaSHCo (this paper)
Xx
2
none
Table 1: Comparison between proposed methods and a few existing ones. "CMP" designates the use of compressed communication. In our convergence bounds, the parameter 7j quantifics the compression error: smaller 1) values correspond to higher compression ratios. "AG" is for whether an adaplive gradient update is used. "MMT" represents whether momentum is used. "DH" is for data heterogeneity. "I.S" refers linear speedup, which indicates that the convergence rate scales proportionally with the number of workers. Specifically, the 1 factor in the complexity bound explicitly demonstrates this linear speedup, showing that " using n workers yields an n-fold acceleration compared to the single-worker case. "TI" stands for topology independence, which refers to the algorithm's robustness with respect to the underlying communication network. "CMR" denotes the communication round per iteration.
and we define J the averaging matrix, and 11I
1 X = X1, == X X(I-J,,,, VF' -
Vf
1 f'1
We use E, for the expectation about { conditional on the t-th iterate and E for the full expectation. @ used for a (random) compression operator and Eg for its expectation.
2 Related Work
In this section, we review existing works on distributed SGMs either centralized or decentralized setting for solving nonconvex problems.
2.1 Decentralized Nonadaptive Stochastic Gradient Methods
Many decentralized stochastic methods have been designed for solving problem (1. and most of them adopt
nonadaptive updates, such decentralized SGMs in Lian et al. (2017); Assran al. (2019); Tang et al.)
(2018), gradient tracking-basod methods (Koloskova et al. 2019 Lu et al. 2019), and momentum-based variance reduction methods (Xin et al. 2021).
A huge number of parameters are usually involved in training very large-scale neural networks, especially Transformers, and a high communication cost will incur to communicate the models or gradients among multiple agents. Consequently, reducing the communication cost is critical in designing efficient distributed methods. Techniques such as 1-bit SGD (Seide et al.) 2014), SignSGD (Bernstein et al., 2018). QSGD AAlisarr et al. 2017), TernGrad WWen al. (017)) Random-k (Stich al. 2018), Top-k (Aji Heaheeld 2017), Threshold-e (Dttta et al. 2020) and ScaleCom (Chen al. 2020a). have emerged pivotal tools for compression, acting on either the gradients model parameters, to achieve low communication cost. Tang et al. (2019b); Karimireddy et al. (2019) apply such tool in a centralized setting. In decentralized scenarios, Tang et al. (2019a) applies the compression with error compensation to the communication of model parameters. Koloskova et al. (2019) proposes Choco-Gossip, which compresses a residue between the model parameter and its estimation, and designs Choco-SGD by Choco-Gossip. BEER (Zhao et al. 2022a) and CDProxSGT (Yan et al.) (023) include gradient tracking and compress both tracked stochastic gradients and model parameters at. each iteration by Choco-Gossip.
4

---

2.2 Centralized or Decentralized Adaptive Stochastic Gradient Methods
Three distinct categories of stochastic algorithuss have emerged in literature: momentum-based, adaptive learning rate, and adaptive gradient methods that combine the ideas of the first two categories. In practice, adaptive SGMs like AdaGrad (Duchi ct al. 2011), Adam (Kingma & Ba 2014), and AMSGrad (Reddi et al. 2016) are more effective compared with a standard SGM.
Efforts have been made to incorporate the technique of adaptive gradient updates into distributed methods to achieve fast convergence. Houu et al. (2018) propose a distributed Adam for convex problems. Chen [020bb] : Zhao et al. (2022b) introduce locally adaptive algorithms for centralized distributed training. Chen et al. 2021 propose quantized Adam, which considers error feedback in only one direction. Chen (0223a) then presents a compressed distributed Adam that communicates the gradient error at each iteration. centralized distributed AMSGrad is explored in Li et al. [002]]. 1, and its compressed version is presented in Wang et al. 2022)..
et al.
et al.
Few explorations have been made to integrate momentum- or adaptive gradient updates into de- centralized method, possibly because of the challenge of understanding their convergence behaviors. A decentralized ADAM (called DADAM) is developed in (Nazari et al. 2022) for online optimization. Though Nazari ct al.
[2022] gives regret bounds for DADAM on both convex and nonconvex problems, Chen et al. (202bb) points out that for oflline nonconvex problems, DADAM may not converge to a stationary point. Then, Chen et al. 2023b) presents a framework of decentralized adaptive gradient method (DAGM), which communicates both model parameter and the second- momuntum vector at each iteration. DAGM success- fully integrates the use of adaptive gradient updates and decentralized communication protocols. While Nazari et al. (0022 and Chen et al. (2023b) are most closely related to our work, neither of them explore compression to reduce communication cost. Moreover, they both require boundedness of gradients and thus cannot handle data heterogeneity. In contrast, both algorithus that we propose can have the option of com- pressed commumication, and our momentum based method (in Alg. 2 can successfully address the challenge of data heterogeneity without requiring boundedness of gradients.
3 Decentralized Stochastic Methods with Compressed Communication
In this section, we present two decentralized SGMs with compressed communication for solving ( The first method in Alg. D is designed for the scenario where gradients are bounded, while the second one in Alg. can additionally handle data heterogeneity where gradients are unbounded.
In order for the agents to collaboratively solve (1), we let each agent maintain local copy of the variable. For each E [n), let x, be the local copy by the i-th agent. To perform neighbor communication, we use a mixing (or called "gossip") matrix W that satisfies the following standard assumption.
Assumption 2 For the miring matria W, it holds that (1) W is doubly stochastic, i.e., W W 0, W1 =1-1 and 1 W = =1;; (ii) W. = 0 if and j are not neighbors to each other; (iii Null(W - I) = span [1} and p W J J||2<11 1.
Under Assumption 2 i), weighted averaging of local variables or sample gradients will be performed at cach agent with its neighbors. Condition (ii) is enforced because message can be communicated directly only between immediate (a.k.a. 1-hop) neighbors. Tf the underlying communication graph G is connected, then a W can be chosen such that Assumption among the multiple agents through neighbor communication. Particularly, the value of p depends on g and the choice of W. Examples of W for different graphs are given in Koloskova et al. (2019); Nedié et al. (2018): Mancino-Bll et al.] (2023). It also shown in Xiao & Boyd (2004) that an optimal W can be designed subject to the constraints in Assumption i)), (ii) and Null(W I) = span(1), such that p minimized.
2 is satisfied. The condition < 1 is crucial to ensure consensus
3.1 Compressed Decentralized AMSGrad
With a mixing matrix W satisfying Assumption 2 we propose a compressed decentralized adaptive SGM for solving (1) where we adopt similar adaptive update as AMSGrad (Reddi al. 2018). The pseudocode is
5

---

shown in Alg. Lines 5-6 follow AMSGrad and perform local update the first and second momentum: Line 7 performs a local update to the model; X is used to estimate the local model, while we compress the estimate error; Line 8 performs neighbor communication, which can be realized through communicating the compressed vectors; see the discussions above Assumption g Notice that for simplicity, we take only one random sample ę at each ileration. In general, one can take a mini-batch of random samples, and all our theoretical results established Section 4 remain valid.
Algorithm 1: Decentralized AMSGrad with Compressed Communication (DAMSCo)
Input: choose
0, 0 < $1 I, < $2 1, 8 0 < S 1, and maximum number T of updates, set 2; 2, m; 9: u; and u, to 0, and choose a mixing matrix W.
for 1 1= 0, 1,.1........ , T-1 do
for all nodes E [n] in parallel do obtain one random sample ç and compute stochastic gradient of <- VF; (x), let m = f,m (- + (1
B1)g
6
let पे-- - Byū
+ (1 o of and uf = max K
update z; ++
x! Vul+o
m and set z z! + Q(0; + ==1]
8
let ++1 x.
4+
+ + W W
is the first decentralized adaptive SGM that incorporates compressed communictiio. Previous methods have either focused on adaptive updates with full-message communication (Chen et al.,
Alg. [
2023b;
Nazari et al. 2022) or have applied compression strategics to non-adaptive algorithms Yaan et al.
2023
Koloskova et al. 2019
When I, Alg. ! reduces a non-compeessed decentralized version of AMSGrad. Note that even in this special non-compressed case, our algorithm differs from that in Chen et al. (023b). First, we always use the most recent stochastic gradient gf in the setting of ut to update 2;, while the decentralized AMSGrad in Chen et al. (023bb) uses of only to update its first moment vector but not the second momentum vector at the f-th step. Second, our algorithm only performs one round of communication for æ,-variables, while the method in Chen et al. (2023b) needs additional communication for u,-iterates. Thus, our method can save half of the communication costs, even without using compression.
When Q + I, our algorithm can achieve higher communication efficiency. Note that by maintaining the weighted average 8; == Σ/= W,,,, for each i, we only need to communicate the compressed vectors [ol=) - to update v, and thus obtain x, by ot = of + Σÿ=1 WorQlz - xiل. To ensure reliability of the algorithm, Q must satisfy certain quality condition. Throughout this paper, we assume the following condition.
Assumption 3 There exists n (0, such that Ee [||x [[x]]|]] S 12 Vx Rd.
The condition in Assumption
3 satisfied by various compression operators in the literature, such
Random-k (Stich et al. 2018), Top-k (Aji & Heafield 2017). and the rescaled quantizations (Chen et al. 2023a). In the appendix, we give a few concrete examples of Q that satisfy the above assumption. More examples can be found in Koloskova et al. (2099) Chen et al. (002aa).
3.2 Compressed Decentralized Heavy-ball Method
Similar to existing distributed adaptive SGMs, the boundedness condition on (sample) gradients is needed to ensure convergence of Alg. [] Such condition implies data similarity among the multiple agents, which is n. >>>nl>> fx)
often measured by the quantity sup 1
To address the challenge of data heterogene- ity and to achieve fast convergence and efficient communication, we propose to incorporate the techniques of
gradient tracking (Lorenzo & Scutari 20166] Nedic al. 2017), momentum-based updates, and compressod communication, resulting in compressed decentralized stochastic heavy-ball method in Alg. 2 This method

---

does not require bounded gradients and can successfully handle data heterogencity. Note that can also apply gradient tracking in Alg. but a gradient boundedness assumption will still be required to ensure convergence.
In Alg. 2 we communicate not only model but also stochastic gradient. In addition, Line 5 uses the gradient tracking technique to handle data heterogeneity. Similar to the model compression, we use g as an estimate
of g; 1- and compress the estimate error. This technique helps control the impact of possibly unbounded gradients by allowing agents to track the global gradient. If the gradients are bounded, DaSHCo will not need to communicate gradients for convergence. Line 6 mixes local gradients and updates the first. momentum. Line performs the local update to model by using the first momentum term and then compresses the model estimate error. Line 8 performs a neighbor communication of local models.
Algorithm 2: Decentralized Stochastic Heavy-ball
Method with Compressed Communication
(DaSHCo)
Input: choose 0, 0 < B1 < 1, Yo, 79 (0, and maximum number T of updates, set aº, z!,
m;- 91 9:
9; and g, to 0, and choose mixing matrix W.
for t= 0.1,...,
do
for all nodes E [n] in parallel do
4
obtain one random sample & and compute a stochastic gradient g < VF, (x), 1--1 + 2ig. t-
5
let 9. t-
= =g: -.------ J + g and set g g
g
let g 9, 1- Ng E W gil and m f.m! 1-1 +1 B1) g::
update x; ++ xf am, and set tt =xi + Q[a;* ++ =
let artt m. + Yo ド W Waa 11
1+
The heavy-ball (a.k.a. momentum) technique has been used in several distributed methods, e.g., Xu et al. 20022; Xiao et al. (2023). However, Alg. 2 is the first decentralized method that uses such technique together with a compression technique and gradient tracking to simultaneously achieve fast convergence and efficient communication for handling data hetcrogeneity.
4 Convergence Analysis
In this section, we analyze the convergence of Alg. D and Alg, 2 rate in terms of the violation of first-order optimality condition and consensus error. The analysis is chal- lenging due to the nonconvexity of the problem, combined with the use of stochastic gradients, compressed decentralized communication, and momentum acceleration. Specifically, the coupling of compressed commu- nication with momentum acceleration or adaptive gradient updates significantly complicates bounding both the consensus еrror and stationarity violation. To address this challenge, we carefully construct Lyapunov functions that explicitly separate compression error, consensus error, and stochastic noise. By delicately balancing these error terms through tailored choices of stepsizes and mixing parameters, we establish the first convergence guarantees for decentralized adaptive methods that simultancously incorporate adaptive gradient updates and compressed communication (see Theorems A.1 and A.2). Main results are given below and detailed proofs in the appendix.
We aim at establishing their convergence
4.1 Convergence Results of Compressed Decentralized AMSGrad
Besides Assumptions we make the next assumption that is standard for analyzing (distributed or non-
distributed) adaptive SGMs (Reddi et al. 2018 Kingma & Ba 2014 Xu et al. 2023 Chen et al. 2023h
2019

---

Assumption 4 The random samples (4) [em]etn are independent. For each t and i, it holds E.ggi] (ar)). In addilion, there are constants B and B such that | S B, l I Bo for any E [m] and any t, and [V B, [))(())) I Boo for all æ.
The next two thcorems give the convergence rate results. Thoir complete descriptions are given in Theo- rems A.1 and A.2 in the appendix, with proofs provided there.
Theorem 4.1 Under Assumptions
let { be generated by Alg. 1 with
(1 12)
32 { y S min { 1 - 7
172 a
5 min
(2)
24TT B +0"
60n
25 'n'
where
7 + (1 - (1-))1125 1 1.
Then with C =
1 1-pa
6(1 6(1-p2)
[nnn
+
nB²
458
+
301 71
10n
it holds that
T -
T-1
E
X |
S a and
Σ
E [IVV (z') [1a]
4V B +8 1=0
0. dB²
dB
24T TB²
< (I))
f1 +
+
1- B1
V
8(1 31)²
nd
Lia
B +
B 2d T-1
a La
Σ
(1
31
nd
n
2V8
t=
T-1
dB
L2
V B& + 1
+ a
(1 - g++1)
82
- -1)
2v0
[=0
By Theorem 4.1
we specify the choice of a and 8 and obtain the convergence rate as follows.
Theorem 4.2 Let a / +5)
satisfy (2) for some constant 0 (Le 2. and large enough T. Suppose that all other conditions assumed in Theorem 4.1 also hold and suppose S T. Then we have the following resulls.
vT
(i) Let 5
VT BB.
Vn for universal constant w 0 and C defined in Theorem 4.1 Set B2 E
T
( Then
T+I
T 1 1P] = ( 1
+ n
C+C)
E
V
(3)
T
VnT
T
t=
PT (i) Let 8 = O1) be universal positive constant. Set 82 E (pf+1,1) 1) with p VnT. Then also holds.
Remark 1 (Linear speed up and topology independence) In Case (i) of Theorem 4.2 we have C =
n O(1) and # O O( (tT) if T is large enough such that T S max (1-p5)0) 12-1213/
3
Thus (2) holds,
and
Σ
E
V
3 1
0
(4)
T
VnT
(1- (1- })
For Case (ii) of Theorem 4.2 T is large enough such that = max
it then holds 1+C = 0 ) Thus again we have 4.. Therefore, if T is large enough, we obtain linear speed up, and T
the learning rale is independent of p defined in Assumption i.e., topologg-independen..

---

4.2 Convergence Results of Compressed Decentralized Heavy- ball Method
Instead of Assumption we assume & weaker condition, which is standard for analyzing SGMs.
Assumption 5 The random samples (L) iem,,,.2 are independent. In addition, there is a 2 0 such that E, |g"| = f((t) and E ||ll V I o² for all t and i.
A complete description of the next theorem about the convergence rate is in Theorems B.3 and B.4
0ive Theorem 4.3 Suppose Assumptions and hold. Let a ovT 7 TvT
0syn 02vn and Y ov for some
conslants 0,, 02 03 E (0,1)
1) such lhat
1 2
1 1-
n²
a
v2
11
Na S min
60n
25
21
- 03
1-
172 1 17²
7g S min
25y
25L
25
25L
(1
19 (1 7
7/
P%)
7 1 79
(1 - B1) /
S min
16b*
32
12L
12vb
12LVn
6L07 (1-8))
b 242243
2012
15(1-93)
(1 (1-1")
(1 (1-og)²
with b = 4 (97: 1
721
601.2 (1 (1-12)
and P. = 11 W + (1 7 1 for E (2,g)- Then
(1-1")²
X 1| 0 (Var
E
12
n
+ (1 (1- -
VnT
T 11-P Pg
Remark 2 (Linear speed up and topology independence) Prom Theorem 4.3
if T is large enough
such that
T 2
max
2
Pg)
2
P
66
0² 1 27)6
n²
0²(1 73) 02 P2) 0² - 1/214 - ))
n²
n2
113
p3)1
we obtain that 7g and Yo are all O
vī
and
+ リー = 0 VrT
Thus it holds
ovT
Σ
|
T
VnT
and we obtoin linear speed up with a independent of p defined in Assumption
5 Numerical Results
We now demonstrate the efficacy of the proposed algorithms over a set of numerical experiments. We consider three standard benchmarks, including training a convolutional neural network LeNet5 (LeCun al.
1998
the PASH dataset (Xiao et al. 2017), restnet architecture Fixup-ResNet-20 (Zhang et al. 2019 the CIFAR-10 dataset (Krizhevsky et al. 2009). and a small-scale GPT model, called NanoGPT (Andrej 2022), on the tiny-shakspeeare dataset. We will show the performance of our proposed methods (DAMSCo and DaSHCo) on homogeneous data and the ability of DaSHCo on handling heterogeneous data. Our test data and neural networks are selected to demonstrate practical performance. Our code is available for DaSHCo
download at the following repository:
We primarily compare against three prior works: CDProXSGT Yan et al., 2023), Distributed Adam Nazari
al. 2022), and Distributed AdaGrad DDuchi al. 2011 with adaptive learning rates (Chen et al. 2023b
9

---

2.0
DaSHCu
DADAM
DAdeCrae
Toor Accurayyy
Consemtt Erorks
20
1.5
CDPrucSGi
Taaiing
1.0-
20.1
0.5
20
10-4
0.0
40
100
20
40
60
100
Communication Rounds
Communication
Communication
10a
2.5
DAMSCo
80
10.1
2.0
DAdeCrad CDPrUXSOT
DADAM
Accurcy
80-
Comverouu Erroass
10-2
To-
Teiteng
Te.
1.0
4.0
0.5-
10-4
0.9
100
150
200
250
300
50
100
150
200
250
300
50
1.00 Communication Rounds
150
2:00
25.0
300
Communicall al Bounds
Communication Rounds
Figure 1: Results with homogeneous data: Plotted above are (from left to right) the training loss, test accuracy, and consensus eгror per communication round for the FashionMNIST (top) and CIFAR- 10 (bottom) datascts, comparing DAMSCo and DaSHCo with CDProxSGT, Distributed AdaGrad, and Distributed Adam with Top-k compression.
Recently, CDProXSGT was proposed as a proximal SGM for training on heterogencous data in compressod and decentralized setting. It demonstrated superior numeric performance other competing methods (Xin) et al. 2021 Koloskova al. 2019 Zhao et al., 2022a). Chen et al. (Chen et al. 2023b presented general framework for decentralized adaptive gradient methods. They demonstrated that communicating the second- momentum vector information is critical to guarantecing convergence of decentralized adaptive methods. Therefore, we incorporate their method inlo our implementation of Distributed Adam and AdaGrad. We consider these methods to be a practical representation of the state-of state-of-the-art.
Our methods and the methods for comparison are implemented in Python with PyTorch and MPI for Python (mpi4py) and they will be open-sourced upon publication. For LeNet5 and Tixuu-ReeNNet-2.,, we run experiments CPU server. This server has two-way 64-core (256 threads) AMD EPYC 7742 CPUs at 2.25GHz and 2TB DDR4 memory. It runs Ubuntu 20.04 with PyTorch version 2.3.0+-cul2, Python 3.8.10, and mpi4py version 3.0.3. For NanoGPT, we run the experiments on 4 NVIDIA A100 GPUs.
We run the experiments for LcNet5 and Nextp-RosNet-20 on n = 5 MPI ranks and for NanoGPT on n = 4 MPI ranks with the communication network in a ring topology. Each rank only communicates with their two neighbors. We measure and report objective loss on the full training data, accuracy on the full test data, and consensus rounds, under the assumption that these methods are targeting systems where communication is extremely costly. In the appendix, we show the same experimental results but function of epoch. In addition, we show results for larger ranks, a grid network topology, and QSGD compression (Alistarh et al. 2017) to demonstrate that our methods can generalize beyond the carlier computational results.
calculated as 12 We plot these outputs against the number of communication
5.1 Results for Training LeNet5 and Fixup- Resup- on Homogeneous Data
Here, we present results on the described optimizers with random homogencous training data. For compres- sion, we use the Top-k compressor (Aji & Heafield 2017 to compress gradient data and model parameter for CDProxSGT, DaSHCo, Distributed AdaGrad (DAdaGrad), and Distributed Adam (DADAM), while we only communicate parameter updates with DAMSCo. We set 72 = 7 = = = 1.0 for all compressors to mirror prior experiments (Yan et al. (023). For FashionMNIST, we use top-k(0.3). communicating the largest. 30% of values. For CIFAR-10, use (0.4k(0.4).
10

---

We train LeNet5 on the FashionMNIST dataset for 100 communication rounds for all optimizers. For CDProxSGT, we use the code published by the authors along with the same learning rate (0.02), batch size (8), and value for the regularizer (10-4), as tuned by the authors. We mirror these hyperparameter settings for DaSHCo. For DADAM and DAMSCo, we mirror the batch size of 8, set the learning rate to the PyTorch default for Adam of 0.001, and similarly use the standard / defaults of 31 = 0.9, B2 = 0.999. For DAdaGrad, we use the same batch size and the PyTorch default learning rate of 0.01.
We train Fixup-ResNet-20 on the CIFAR-10 dataset for 300 communication rounds. We again use the authors' tuned values for CDProxSGT, with the batch size increased to 64. We mirror the batch size of 64 and keep the other hyperparameter settings the same as described above for the other optimizers.
Results for homogeneous data are shown in Figure 9 We observe that our DAMSCo method is very com- petitive, converging at about the same rate on the FashionMNIST dataset as DADAM and much quicker on the more challenging CIFAR-10 datasct, with respect to the objective function and test accuracy. We note that both DAMSCo and DaSHCo demonstrate better performance than CDProxSGT on both datasets, which itself had recently given strong numerical performance against several other state-of-the-art methods (note that CDProxSGT was primarily developed for heterogeneous data).
5.2 Results for Training LeNet5 and Fixup-ResNet-20 on Heterogeneous Data
Next, we compare all methods on heterogeneous training data, with an equal number (i.e., 2) of label classes from each dataset distributed to each of the 5 MPI ranks. We lower the batch size to 32 to help improve generalization performance on CIFAR-10, but we otherwise reuse the same lcarning rates and other hyper- parameters from the earlier experiments. We again run for 100 communication rounds on FashionMNIST and use 300 rounds on CIFAR-10. We demonstrate our results for these experiments in Figure [0
We note several obvious differences with the results on homogencous data. CDProxSGT is considcrably more competitive, as it was primarily developed for the heterogeneous case. Our DaSHCo method converges most quickly with respect to testing accuracy on both FaNSIO and CIFAR-10. DAdaGrad, DADAM, and DAMSCo are unable to quickly converge in these experiments. This is expected with these types of methods, as data heterogeneity can break assumptions for convergence guarantees, such as bounded gradients and gradient similarities.
5.3 Results for Training NanoGPT
Lastly, we compare all methods on homogeneous training data using customizable GPT model implemented by Andrei (022). It is a standard Transformer architecture but we experiment with fewer parameters: 6 layers, 6 heads in each layer, 384 feature channels, and 256 context length. This totals to 10.67M parameters. We run training on 4 NVIDIA A100 GPUs and thus 4 MPI Ranks. We tune two hyperparameters: learning rate (a) and batch-size. For all optimizers, we set the batch-size to 256 and a = 10-1 except for DaSHCo and CDProxSGT, in which we set a = 0.02. We train the GPT model on the tiny-shakespeare dataset with top-k(0.55) and use 650 communication rounds. After training, we achieve minimum validation losses of 2.321, 1.649, 1.641, 1.635, 1.620 for CDProxSGT, DAMSCo, DAdam, DAdaGrad, and DaSHCo respectively. We demonstrate results for these experiments in Figure 11 We give a qualitative comparison of inference performance in the appendix.
6 Conclusion
We have presented two compressed decentralized stochastic gradient methods (SGMs), DAMSCo and DaSHCo, with a technique of either adaptive updates or heavy-ball (a.k.a. momentum) acceleration, for solving multi-agent nonconvex stochastic optimization. Our methods can simultaneously achieve fast con- vergence (by adaptive or heavy-ball updates) and efficient commuication (by message compression). Both methods achieve the optimal convergence rate. Similar to existing distributed adaptive SGMs, the conver- gence of DAMSCo relies the condition of bounded gradients, while DaSHCo does not require any bound-
11

---

2.0
DAMSCO
80
10r
Camueruu trrods.
1.5
DAdaGrad CDPPNNSGT
80
10:1
tor3
101
20
10"7
0.0
20
40
100
20
40
60
90
100
20
40
60
80
100
Communication Rounds
Communication Rounds
Communication Rounds
10a
DaSHCs
DADAM
Traiiing Lo4s
DAdaCrrad
Test Accuracr
10t
3-
10.1
2-
60-
20-1
1-
10
100
150
50
Communication
Figure Results with heterogeneous data: Plotted above are (from left to right) the training loss, test accuracy, and consensus error per communication round for the FashionMNIST (top) and CIFAR- (bottom) datasets, comparing DAMSCo and DaSHCo with CDProXSGT, Distributed AdaGrad, and Distributed Adam with Top-k compression.
1000
Conzanuu
10-1
202
ConMAACatoO Reunce
Rounds
Figure 3: GPT Results with homogeneous data: Plotted above are (from left to right) the training loss, validation loss, and consensus error per communication round for the Shakespeare datasct, comparing DAMSCo and DaSHCo with CDProxSGT, Distributed AdaGrad, and Distributed Adam with Top-k com- pression.
edness condition and can successfully address the challenge of data heterogeneity. Numerical experiments training deep neural networks demonstrate the superiority of the proposed methods over stale-of-the-art methods.
Acknowledgements
The authors would like to thank three anonymous reviewers for their valuable comments. This work is partly supported by NSF grant DMS-2208394, ONR grant N000142212573, and also by IBM through the IBM-Rensselaer Future of Computing Research Collaboration.
References
A. F. Aji and K. Heafield. Sparse communication for distributed gradient descent. In EMNLP 2017: 7: Confer- ence on Empirical Methods in Natural Language Processing, pp. 440-445. Association for Computational Linguistios (ACL), 2017.
D. Alistarh, D. Grubic, J. Li, R. Tomioka, and M. Vojnovic. Qsgd: Commmicationn-ffiieene sgd via gradient quantization and encoding. Advances in neural information processing systems, 30, 2017.
12

---

K. Andrej. NanoGPT. http://hhhbb..oo//aaappttaaaaaap 2022. Last Accessed March 2025.
Y. Arjovani, Y. Carmon, J. C. Duchi, D. Foster, N. Srebro, and B. Woodworth. Lower bounds for non-convex stochastic optimization. Mathematical Programming, 199(1) 214, 2023.
M. Assran, N. Loizon, N. Ballas, and M. Rabbat. Stochastic gradient push for distributed deep learning. International Conference on Machine Learning, pp.
PMLR, 2019.
J. Bernstein, Y. Wang, K. Azizzadenesheli, and A. Anandkumar. signsgd: Compressed optimisation for non-convex problems. In International Conference on Machine Learning, pp. 560-569. PMLR, 2018.
L. Bottou, F. E. Curtis, and J. Nocedal. Optimization methods for large-scale machine learning. SIAM review, 60(2):223 311, 2018.
C. Chen, Shen, H. Huang, and W. Liu. Quantized adam with error feedback. ACM Transactions on Intelligent Systems and Technology (TIST), 12(5):1 26, 2021.
C. Chen, L. Shen, W. Liu, and Z. Luo. Efficient-adam: Commmicattion-efiient distributed adam. IEEE Transactions on Signal Processing, 2023a.
C.-Y. Chen, J. Ni, S. Lu, X. Cui, P.- Chen, X. Sun, N. Wang, S. Venkataramani, V. V. Srinivasan, and W. Zhang. Scalecom: Scalable sparsified gradient compression for communication-efiiiene distributed training. Advances in Neural Information Processing Systems, 33:13551 13563, 2020a.
X. Chen, M.Hong, S. Liu, and R. Sun. On the convergence of class of adam-type algorithms for non-convex optimization. In 7th International Conference on Learning Representations, ICLR 2019, 2019.
X. Chen, X. Li, and P. Li. Toward communication efficient adaptive gradient method. In Proceedings of the 2020 ACM-IMS Foundations of Data Science Conference, pp. 119-122 1-9-128, 2020b.
X. Chen, B. Karimi, W. Zhao, and P. Li. On the convergence decentralized adaptive gradient methods. In Asian Conference on Machine Learning, pp. 217 232. PMLR, 2023b.
A. Cutkosky and F. Orabona. Momentum-based variance reduction in non-convex sgd. Advances in newral information processing systems, 32, 2019.
J. Duchi, E. Hazan, and Y. Singer. Adaptive subgradient methods for online learning and stochastic opti- mization. Journal of machine learning research, 12(7), 2011.
A. Dutta, E. H. Bergou, A. M. Abdelmoniem, C.-Y. Ho, A. N. Sahu, M. Canini, and P. Kalnis. On the discrepancy between the theoretical analysis and practical implementations of compressed communication for distributed deep learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 3817 3824, 2020.
S. Ghadimi and G. Lan. Stochastic first-and zeroth-order methods for non-convex stochastic programming. SIAM Journal Optimization, 23(4):2341 2368, 2013.
L. Hou, R. Zhang, and J. T. Kwok. Analysis of quantized models. International Conference on Learning Representations, 2018.
K. Huang and S. Pu. Cedas: A compressed decentralized stochastic gradient method with improved conver- gence. IEEE Transactions on Aulomatic Control, 2024.
R. Islamov, Y. Gao, and S. U. Stich. Towards faster decentralized stochastic optimization with communica- (ion compression. arXiv preprinl 2XXi:2405.20114, 2024.
S. P. Karimireddy, Q Rebjock, S. Stich, and M. Jaggi. Error feedback fixes signsgd and other gradient compression schemes. In International Conference on Machine Learning, pp. 3252 -261. PMLR, 2019.
D. P. Kingma and Ba. Adam: A method for stochastic optimization. aix preprint arXiv: arXiv:1412.6998, 2014.
13

---

A. Koloskova, S. Stich, and M. Jaggi. Decentralized stochastic optimization and gossip algorithms with compressed communication. In International Conference on Machine Learning, pp. 3478 -487--3477--00 PMT.R, 2019.
A. Krizhevsky, G. Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner. Gradient- based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278-233) 1998.
X. Li, B. Karimi, and P. Li. On distributed adaptive optimization with gradient compression. In International Conference on Learning Representations, 2022.
X. Lian, C. Zhang, H. Zhang, C.-J. Hsieh, W. Zhang, and J. Liu. Can decentralized algorithms outperform contralized algorithms? case study for decentralized parallel stochastic gradient descent. Advances in neural informalion processing systems, 30, 2017.
X. Lian, W. Zhang, C. Zhang, and J. Liu. Asynchronous decentralized parallel stochastic gradient descent. In International Conference on Machine Learning, pp. 9043-3055 PMLR, 2018.
P. Di Lorenzo and G. Scutari. Next: In-network nonconvex optimization. IEEE Transactions on Signal and Information Processing over Networks, 2(2):120-136, 2016.
S. Lu, X. Zhang, H. Sun, and M. Hong. Gnsd: A maaieett-racckin based nonconvex stochastic algorithm for decentralized optimization. In 2019 IEFE Data Science Workshop (DSW), pp. 315-321. TEFE, 2019.
G. Mancino-Ban Y. Xu, and J. Chen. A decentralized primal-cual framework for non-convex smooth consensus optimization. IEEE Transactions on Signal Processing, 71:525-538, 538, 2023.
P. Nazari, D. A. Tarzanagh, and G. Michailidis. Dadam: A consensus- distributed adaptive gradient method for online optimization. IEEE Transactions on Signal Processing, 70:6065-6079. 2022.
A. Nedic, A. Olshevsky, and W. Shi. Achieving geometric convergence for distributed optimization over time-varying graphs. SIAM Journal on Optimization, 27(4):2597-2633, 2017.
A. Nedić, Olshevsky, and M. G. Rabbat. Network topology and communictioon-compttaaaa tradeoffs in docentralized optimization. Proceedings of the IEEE, 106(5))953-976, 2018.
Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic approxima-
tion approach to stochastic programming. SIAM Journal on optimization, 19(4):1544-1699, 2009.
P. Ochs, Y. Chen, T. Brox, and T. Pock. iPiano: Inertial proximal algorithm for nonconvex optimization. SIAM Journal on Imaging Sciences, 7(2):1388-1444 2014.
B. T. Polyak. Some methods of speeding up the convergence of iteration methods. Ussr compulational mathematics and mathematical physics, 4(5):1-17, 1964.
S. Reddi, S. Kale, and Kumar. On the convergence of adam and beyond. In International Conference on Learning Representations, 2018.
S. J. Reddi, A. Hefny, S. Sra, B. Poczos, and A. Smola. Stochastic variance reduction for non-convex optimization. International conference on machine learning, pp. 314-323. PMLR, 2016.
H. Robbins and S. Monro. A stochastic approximation method. The annals of mathematical statistics, pp. 400-407, 1951.
F. Seide, H.Fu, J. Droppo, G. Li, and D. Yu. 1-bit stochastic gradient descent and its application to data- parallel distributed training of speech dnns. In Fiffeenthh annual conference of the international speech communication association, 2014.
N. Singh, D. Data, J. George, and S. Diggavi. Squarm-sgd: Commmication- momentum sgd for decentralized optimization. IEFE Journal on Selected Areas in Information Theory, 2(3):954-99) 969, 2021.
14

---

Z. Song, L. Shi, S. Pu, and M. Yan. Compressed gradient tracking for decentralized optimization over general directed networks. TEEE Transactions on Signal Processing, 70:1775-111 1777-, 2022.
S. U. Stich, J.-B. Cordonnier, and M. Jaggi. Sparsified sgd with memory. Advances in neural information processing systems, 31, 2018.
H. Taheri, A. Mokhtari, H. Hassani, and R. Pedarsani. Quantized decentralized stochastic learning over directed graphs. In International Conference on Machine Learning, pp. 9324 9333. PMLR, 2020.
H. Tang, X. Lian, M. Yan, C. Zhang, and J. Liu. d: Decentralized training over decentralized data. International Conference on Machine Learning, pp. 4848 4856. PMLR, 2018.
H. Tang, X. Lian, S. Qiu, L. Yuan, C. Zhang, T. Zhang, and J. Liu. Deepsqueeze: Decentralization meets comor-comeenstted compression. arXiv preprint arXit:1907.07344 2019a.
H. Tang, C. Yu, X. Lian, T. Zhang, and J. Liu. Doublesquezz: Parallel stochastic gradient descent with double-pass error-compensated compression. In International Conference on Machine Learning, pp. 6155- 6165. PMLR, 2019b.
Y. Wang, L. Lin, and J. Chen. Commmicatton-comppessss adaptive gradient method for distributed non- convex optimization. In International Conference on Artificial Intelligence and Statistics, pp. 6292-622662222 6320. PMLR, 2022.
W. Wen, Xu, Yan, C. Wu, Y. Wang, Chen, and H. Li. Terngrad: Ternary gradients to reduce communication in distributed deep learning. Advances neural information processing systems, 30, 2017.
H. Xiao, K. Rasul, and R. Vollgraf. mashion-mnist: novel image dataset for benchmarking machine learning algorithms. Xiv preprint ar arXiv:1008.0770 2017.
L. Xiao and S. Boyd. Fast linear iterations for distributed averaging. Systems Control Letters, 53(1): 65-78, 2004.
T. Xiao, X. Chen, K. Balasubramanian, and S. Ghadimi. A one-sample decentralized proximal algorithm for non-convex stochastic composite optimization. In Uncertainly in Artificial Intelligence, pp. 2324 2334. PMLR, 2023.
R. Xin, Das, U. A. Khan, and S. Kar. A stochastic proximal gradient framework for decentralized non- convex composite optimization: Topology-independent sample complexity and communication efficiency. arXiv preprint orXiv:2110.01500 2021.
Y. Xu and Y. Xu. Momentum- based variancc-roduced proximal stochastic gradient method for composite nonconvex stochastic optimization. Journal of Optimization Theory and Applications, 196(1):266-29) 297, 2023.
Y. Xu, Y. Xu, Y. Yan, and J. Chen. Distributed stochastic inertial-acceelratee methods with delayed derivatives for nonconvex problems. SIAM Journal on Imaging Sciences, 15(2):550-590, 2022.
Y. Xu, Y. Xu, Y. Yan, C. Sutcher-Shepard, L. Grinberg, and J. Chen. Parallel and distributed asynchronous adaptive stochastic gradient methods. Mathemalical Programming Compulation, 15(3):471-8 1171--58,,1 2023.
Y. Yan, J. Chen, P.-.. Chen, X. Cui, S. Lu, and Y. Xu. Compressed decentralized proximal stochastic gradient method for nonconvex composite problems with heterogeneous data. In International Conference on Machine Learning, pp. 39035-39061. PMLR, 2023.
C. Yau and H. Wai. Docom-sgt: Doubly compressed momentum-assiste stochastic gradient tracking algo- rithm for commmication efficient docentralized learning. arXiv e-prints, pp. arXiv-2202, 2022.
Chung- Yiu Yau and Hoi- To Wai Docom: Compressed decentralized optimization with near-optimal sample complexity. Transactions Machine Learning Research, 2023.
15

---

H. Zhang, Y. N. Dauphin, and T. Ma. Fixup initialization: Residual learning without normalization. In International Conference on Learning Representations, 2019.
Н. Zhao, B. Li, Z. Li, P. Richtárik, and Y. Chi. Beer: Fast O(1/T) rate for decentralized nonconvex optimization with communication compression. Advances in Neural Information Processing Systems, 35: (665-31667, 2022a.
w. Zhao, X. Jiao, M. Hu, X. Li, X. Zhang, and P. Li. Paddlebox: Commuication-effiieett terabyte-scale model training framework for online advertising. In 2022 IEEE International Conference on Big Data (Big Dala), pp. 1401-1408. IEEE, 2022b.
A Convergence Rate Results of Algorithm 1
In this section, we analyze the convergence rate of Algorithm D By the notation introduced in Section write the updates of Algorithm 1 in the more compact matrix form:
1.3
M = 3.M-1 + +1 -11-)))
(5)
Ū B₂ 80 (1- 32) G',
(6)
U max Ü ( 1
(7)
M
Y VU +0"
(8)
X X -aY!
(9)
X X' + Q X x
(10)
X = tt+ + 7 [+] (W - I),,
(11)
where
G
g .... M
m ; m
m U = [ui u.y u
Also we use similar notations in Section L.3 by letting
m'
M'1
Y'1. Y YY.
Let W > (1 I. Then we can write to
X -
1x411_x++) (W - -I).
(12)
When W satisfies the conditions in Assumption Indeed, we have
it be shown that W also satisfies all three conditions.
p w
Below we bound the sequence (M'), (U'} and [Y'}.
Lemma A.1 Under Assumption
holds that for any 2 0,
|M (1 - (1-) vnB S VnB,
|Y'IS Vn:6612
(13)
|m|||s B, || 00 Bao:
|1/ (1 -1/+2) B² < B2 (
(14)
16

---

Proof. From the update of m, ie., m = 3im! r-1 + +(1 - g', we have that for any 2 0 and each i e [n].
|m || + (1 Bi B))gfls B1
|ل)اlc| Bi |1m - B,)
where the second inequality holds from above and noticing m, 0, we obtain
|اااووا B by Assumption
4
Recursively applying the inequality
Imill (1+ B1 + + + +.... Bi) (1- (1--31100 3
= (1 (1- 2 B S B.
Hence, |M - 1(+1) VnB. Now by U² 2 0, we immodiately have |Y VU=+o
M
S vnBB-*. 1
In addition, we have that for any t 2 0 and each i E [m],
| + [1 + (1 31 - S +1
- 31)l -11
3 311mm +1x00 - Boc
where the second inequality follows from || Boo by Assumption above and noticing m 1 0, we obtain
Recursively applying the inequality
m S (1 + 31 + 8 + ........ + 31) (1 Bx) -1- (1-tt) Boo S Box
Similarly, by noticing ū, 1 = 0 and وو o gilloo - B%,, we have 1o0 S (1 - 11-2t)) Ba for each i E [n] and
t 120 O. Now by un = max (7). un 1, it holds
|| S max (| i bo; ||اu-1 11o) s
b0 | | 1 lu 1
S max {1] o || l| ........ | cl, |lac)
S max {(1 15+2) B² (1- - (35) B (1 1-3) B
||u
100}
= (1- 1351) B
where the equality holds because BB E (0, 1) and u, = 0. The proof is then completed.
The next lemma shows the bound of the consensus error of X.
Lemma A.2 Under Assumptions 2 and S. let a S
(1-n?)
and y S min
1-ا²
1-n²
25 g.
Then
32
60n
E 1|] S a²c, where C==
12
( 4n
+
nB2
320anB2
(15)
1- p2 6(1 pp)
456
8(1 - n21-2
Proof. By 12 and (W - -I W I, we have X = x W(I - J) + xX X I)
and thus for any m/ > 0, it holds
+ | <(1 + m)
x X W(I-J)/ 1>|² - + +( و )) 1/ - (w (w-1)
<(1 x + W(I / 4 (1++m))) x² (x - x )||
(16)
where the second inequality follows from W - -11125 2. In addition by WJ = J, we have
x t W(I J) /|| = x (w- (W-J)) || = (x' aYY) (W - J) ||
(xX' .x-)
(x'-aX") ) ( -1) 2 60² X - ax2
1 1 72
27º a² 11 1
8
X ||
2 +
7-
1 1+7 7
1 ++7 70
1 7
272a² a² 1- p2
||_|| ||
p a
Y
_|² S
X ||
Y 1|2
(17)
2
1 p
2
17

---

Notice
nB²
| 3=
1111=11
1= |
Y 1||==|101122
(18)
6
which together with 17 gives
x 2 W(I 1)|l²
1 72
2nB²pa2
|
(19)
8(1- pP)
Moreover, by
100 and Assumption 3 it holds
E
x
x
= E RQ 0 x xx - -xx++ x )1'
x + x² |
x + x + x - x x
= 12211
5// (1 + (2l E
x x11" + +1² (1 1/ 4) E
x x 19
=1² (1 + 1
X - x11 + (1 +1+17 1/2 )) a2E ||| |2]
(20)
<つ 12+
X x ||]
+ + (1 aBnB28-1
(21)
where 1/2 > 0 is any positive number. Substituting
19
with 112 = into 16 after taking full and 21
expectation, we obtain
1 (1+ 72 E x 21
2nB2p802
E
|
5(1 + m)
2
5(1 - (())
+ 2 (1 + ./ ) 7²
(R ||
x x'11 + +
(22)
Let 171 = Tny in (22). Then by 7 S
1- 60y
we obtain
1-
1 p
3 3+
1/ (1 (1+ ( x2 < m1 -p))
1+w 7 2, (1 + 1/1
<
(23)
4
360
Thus we have from 22 that
E
x 1 2
3+
22
E
X
AnB2pa'
4 - 41 p2)
E
x
x
2
a²nB²
(24)
8(1 g2)
3
456
Now let us consider the compression error of X, namely, E |||x - x [..
By 12). we have that for any
1/a >0 0,
E [ [ E -|(x*+-x**+) x( (7(W I) I) + x (I () - -D|l"]
E || - x - 1[]] (1 + n35 1T || 1 27
(1 + 78) (1 2E
(25)
where have used JW J in the equality and (l - 11 |WW - 1||25 2 in the inequality. For the second term in the RHS of 25 we have
-1--1
< > w - I||++||0|
+ 27 and
E
x
IE
x
ax 19|
22
x
+ 2a 2
2E
x
|
+ 2a 2n.22
(26)
18

---

Plugging 266 and (21
with 1/2
1-1 into (25), we have
E
x
x
s [|]]
+ n3'') 472 2
X 11a] + 2a2nnB20
(27)
+ 13) (1 + 27)²
1 + 1/
E
||x
X
x11]]
2n/²
a
nB2 1828--11
1p
1-n² -12 in 127
1- Then by 7 26 we obtain
Let 1/3
1
1
n²
3 3+12
2 + 17) (1+27)
4
(1 (1+1) 1/3 11+ 87
(1+ 13) (1
(28)
2
2
4
1 172
1 n72
Thus, we have from
27 that
E
11
2
-
1
E
x
2
3
+
E
||
x
x²1 21 + 5a2nB²
(29)
172
4
5(1 r72)
Denote 52' =
[E
|
1|2
E
Then (24 and (99
imply 1 < ASl' + c, where
3+
417(1- 3+m 2
4nB B²
A
c=
5(1 5(1-p2)
455
5a nB2
I- y
8(1-)²*
For any q = (91,92) 2 0, we have
q T < + (qq - -4 q + C..c.
Take = 3 and
1-p²
=
1-12
16a We have q A q s (-2. by 7 s a and a 5 (1-17)²
32
Thus
q [ <q l E + Tc. Summing up the above inequality for all t = 0, 1,
T 1.., 1, obtain
- 1
S T (q TT q T22)) + 4q C.
(30)
From x!- = x² = _ = 0, vi E [n], we have
8- 0 and B[[ x [22
0.
Thus by the nonnegativity
of X [|2], we have q s?0 q Ω2 < O. Hence
1 x |P]
12o²
B2p
nB²
320a
T
1 p2
8(1 )
458
8(1 172)2
The proof is then completed.
To prove the convergence of Algorithm
we define an auxiliary sequence as follows
31 x1-1)) Vt 2 0,
(x'
(31)
B1
with x- - .0. The lemina below shows the difference of two consecutive z-points.
Lemma A.3 Let {xt} be defined in
31
It holds that for all t 2 0,
B
z 1+1
m t-1
(32)
31 71
u 1- + 5
VuL +5
n
u
8
19

---

Proof. By
11 and (W-I) - [WJ--- 0, have x'+1
x'+2, Hence, it follows from
8
and
(
that
m
(33)
U +
Thus by 31
we have
31
B1
T0
+
T
1
B1
1
$1
-
31
3
1
m
81
1-1
31
11
1=1
U
+
31
11
1=1
+
1
Q
3mm 1-1 (1
(1) g
31
a
m
1
31
n1 i=1
Vui= 8
B
11
i=1
u
8
B1
0
1-1
g
m;
81
+ 6
Vui +
i=1
u
+
which is the desired result.
Lemma A.4 Under Assumptions and
it holds
2
L
fa (m:) (o()))
S n
| 11:
(34)
and
[Vf(2') v( 32
(35)
- -1)2
Proof. First, by the L-smoothness of fa for each i E [n] and Young's inequality, we have
I
Σ V (x:) - (3))
=111
n
which indicates 34 by the definition of x Also, by the L-smoothness of f, it follows
L3
VV vf(*')|
1.31 x'
xx 1=d-xx-11p 111
(1-
L3
L238
Q²L2BRBB
33
a
m
m
<
(1- 31
(1 3
12
8(1 8(1-3,)22
u
+ 8
+
where the last inequality holds by ||m - "11- B from 14 This completes the proof.
Lemma A.5 Under Assumptions 1 and 4 it holds that
2d2
Σ
-1 -
-11]
(36)
5(1 - B1)2
+ 20²
24
T2 +
61
E
T- 1
x
+
2
+
Σ
2d
(1
355 1)
Ba
nd
nd
52
t=0
20

---

Proof. By 32
and Young's inequality, have
Σ R || - z11
SR
2
3
m;
1-1
1
t=
1
B1
t=1
u -
+
Vui
+
T
+
2
(37)
72
To bound the first term in the RHS of (37
notice
MM
m
Vu +
1
V u
+0
1-1
m:
o
1/ 1-1 +6
Vu 8
+6
Vui
+
1
<B²
(38)
+
u
+
+0 5
v +
In addition, it holds
and
Vu
48
Vut+5
Vat- +
(39)
u
u
v8
where the equality holds because ut is nondecreasing with for each i [n]. Therefore, it follows from that
38
Σ
m
o
1
dBa
(40)
1-1
Vu! + 8
t=0
To bound the second term in RHS of 37
first apply Young's incquality to have
E
+
t=
g
g
g
<2E
2E
(41)
u
+
Vu
+
1=1
Notice
T-1 1
g
g
g
g
+ 8
Vu
+8
0=
T
u
1
1
(42)
21

---

In addiiion, holds that
vo and
Va
16
Vu
1
u
+ 8
(uf + =0)("²=1
+
(v +8
1 0
d
14
1lo0
(1- /22 B²
(43)
28
28
8%
Therefore, we have from
41
and
42
that
9
9
2d
E
2E
(1
32
B
(44)
+
u
82
t=
t=0
1=
Now we bound the first term in the RHS of 44 follows
9
21E
T-1
2
Σ
g
vf(xa) + V)(()))) Vf(=') +
8
n2
6
Σ
vf(aaa)
(f((())) vi(ET)
+ Σ
V ||
n
/
T
6
Σ
(=()))
(ff((())) -(
Σ
|
n08
n
8
6L
4
x
E
(45)
2
nd
where the equality holds because gi gh. .... gh. are conditionally independent of cach other, and in the last inequality, we have used
34 Plugging
45
into 44
gives
n
g
E
(46)
n
24 <
TB²
6L
2
f.
2d Σ
(1
B3
gt+1)
B
nd
nd
82
1=
The proof is then completed by substituting
440
and
46
into
37
Lemma A.6 Under Assumplions and
4 il holds
E, (V)(2))
g
(47)
+8
1
B2
+
1
B2 +
VV
2
|X|
2
2/ BB2
+0
8
2v8
8(1
31)
8
2
22

---

Proof. By Assumption it holds that
E,
v
1
9
(x'))))
Vf
Vf((2;)
U
8
Ve +6
1
1
Vf(x"
v (z') vs(3')
(Vi((z))
V/(('')
nv u
+
V
==1
V5(T') nv
((()) - vf(>))
V
(48)
Next we bound each of the four terms in the RHS of 48 For the first term in the RHS of Young's inequality, 344. and 35 to have
we use
(5(2) VI(T')
Vf((a)) -
V)(('))
1
(Vf(2') vf(T')]
V.. (x v
2/8
n
1
1?2
| [2)
(49)
2
8(1 - 31)²
n
where we have used ttt 2 0 in the first incquality. For the sccond term in the RHS of 48). we have
Vf(z')
V\(=)) VS(x')
(50)
T + B 8
(>'))) 4V B3 5
+
| (x')
028 B3 + 8B2
Vf
4 B +
82 81)
where the first inequality follows from Young's inequality and i 48 have from Young's inequality and [34 that
0. For the third term in the RHS of
Σ
(Vf(())) -
nV
|V
B 6
VV (z:) - (F
4V
8
iml
V
L B2 +
| 11?
(51)
4V B +
no
The last term in the RHS of
48 can be bounded as
f
V / T 11
(52)
BB +
Substituting 49
52 into
48 and rearranging terms yields the desired result.
Now we are ready to show the main convergence result of Algorithm
Theorem A.1 (Complete statement of Theorem 4.1 salisfy
Under Assumptions
4
let > and 7 >
0
6 (1- 22
< min 1-
1-
17²
a
a < min 24T. B3 +
533)
32
60n)
25
23

---

Then with C
defined in
15 it holds
α
E
[1
-=(
+
a
dB²
+
L.Ra²
B% BB2 4/
+
1- B1
v8
8(1 B1)2
0
24La²
6L
L'a
B +8
1
2d
TB² +
+
CT + La
B
Σ
(1- B2 1
(54)
nd
nd
n
2V8
82
1=0
T-1
dB²
(1 85 1 + a L22 B2
B +6
+
03
5(1 - B1)3
6
2 2/8
f=0
Proof. By the L-smoothness of f, we have
f 1 S {
+ (VV((=)), 2 - x²) +
L
|| - -221?-
which together with 32 gives
1 (2 Ss (2') - a (vF(e))
1
Σ
g
L
|| | - z21?
+ 2
n 1=1
ut
+8 8
+ 1- B
31
vf
(2')
α
m
1-
o
Vu +0
u 1- + 5
Take expectation, sum up over t, and rearrange terms of the above inequality. We have
(7/(6))
1
g
)
T
|| - 211]]]
+
E
n
u
+ 8
(55)
+
a31
T
E
V (z*)
1 n
Σ
m
1
|>
3
Vuf 8
1=0
uu
Below we bound the two inner-product terms on the LHS and RHS of 55 First,
1 V (2*)
Σ
1
1
E
m
n
(-1 +6
Vul +8
uu
E
IV (24) 1l
Σ m 1-1
u1!
11 +
5
Vu 8
E
|VV (24)
11:0 Σ
72
m 10
1
V
u
(-1
+
Vuf
+
1
39
dB3
(56)
8
8
24

---

where in the third inequality, have used V
1l00 I Boc and |lmp-"bbo Boo by Assumption and
Lemma A.1 Second, we write
a
Vf (x))
9
(57)
u
+
g
gi
(f()))
1
g
Vf
+
u
+
V
+
7 --1 + 8
By IIf (z*) Iloo Bx and l19 zo Bx from Assumption
we have
g
g
Vf
(58)
u
+
1
+
==1
1
13
2 20
(1
52t B
+
+ Vu
6
8
Substituting 477
and 58
into
57
after taking conditional expectation, we obtain
E.
(F((')
vf
g
dB xc
(1-12+1)
+
IVf 1?
(59)
8
82
B/, +
==1
I
B
+
1
B2
B% +
1
+
|X1|2
2
5(1 11)
2/8
Now plugging
36
56
and
59
after full expectation into
55 and rearranging terms gives
6La
2
dB
E
V
S - (x")
2.
B2
+8
1- 31 v8
t=
+
L
dB2
2a²
24
TB2
6T. no
E
X1 2
2d
(1- 15+1) Bie
2
8(1 31)²
110
02
(==
t=0
T-1
dBA
2
BB2
+8
B23
v B2
+ 8
1
(1
3
+ n
E X|
12]
8
2v8
8(1 31)²
2v8
Plug (15) into the inequality above, notice
GLa 5
and rearrange terms. We obtain the
2
RBB3, +5
4 B3 +8
desired result and complete the proof.
Below we give few choices of the algorithmic parameters and give the convergence rate of Algorithm
Theorem A.2 (Complete statement of Theorem 4.2 Suppose that the conditions assumed in Theo-
rem 4.1 hold with 49 (P +8) for a sufficiently large 2 n and some 0 (%e F). Then with C
VT defined in 15). we have the following results.
(i) Let 8 8= w2B2
VT vn
for some universal constant 0. Set 82
T T41: (
( Then
| x ||= 1
E
T
1=0
(s(²)) - fr LB2 dB2 (1 + C(1 12)82) + +C(1 + 1?2
B²
+
BL²B²)
(60)
VnT
T
T
25

---

(8) Let =1) be universal positive constant.
Suppose
7+1 S
x
1.
Set 32 E
vnl
( OL T+1 VnT
T
}+
Then
- 7 (f(2) f +B LB + +dB L+ dLB
|V (x') 12+-= 1x
(61)
CB
12 B
-0
(1 [1+ +
+ T
VnT
T
Proof. From S
211 BBlBBB +6'
5
it follows that La S
48
21
B3 B1/B3
V
S 27'
Hence,
6L
L²a
1
no
4nvo'
a,1 dB²
+ LBga2dB2
a31 dB²
81
.24 2331) dB²
< 1- 31 V6
1+
1- B1
v8
8(1 - B1)²
24(1 Bi)
24(1 - B,)2 v8
and
2d
dB
La B
(1 - 11-12-)
g(41)
+
(1- 1
82
6
0=0
13adB1
T
13ddB1
B2 (3
g1+1)
T
120 3
128
1 - B2
Now dividing both sides of (54 by
of
= OvnT, using the three inequalities above, and noticing
4 BB
{(=T) 2 f from Assumption
wC have
E
119
1
(1(*9 (1=
03:1 2331)
dB3 24(1 - 31 V8
96La B'. +
5 B
Vn
nd
312a
La v
B +
+ 4v B2 +
aC
4nvo
n
13adB4
32(1 3h)
Q²
[ +
1
T
+ +4VBB B& +8
BVnT
128
1 B2
8(1 8(1-3:) 31)²
2/8
48
B2 +ō
Replacing a by
in the above inequality and adding the resulting inequality to d15 we obtain
vT
1 1
[(x2) - fr O B% + 5,31 23311 dB²
V
X 112
S
T
n
BVnT
6(1 - 6(
VTT
1=0
3840L( B2 5)
(
3
B% +
6462 T.2 + +5)
1682 (B² + 6)
B2 +0
8/nT
4V8
8
T
T
13dB4
/B. +8
T 86
32(1 - 33
(62)
3
T
1 1- 82
BR
B2 +0
6402 L2 n (B3 + +)
8(1
B1)3
8
2V8
T
Case (i): When 8 = w2B2
vT
we have
B² B2 = 1 +
/n
0(1) because S T. In addition, not
vn
WT/T
82 7(1-9.)
from 8g T4i and thus
T
Be(1 B5)
B²(1 - 8T
AL
T
=
$ 3 <
(63)
1 1- 32
T(1 - B2)
26

---

where the last inequality follows from 82 S ) Therefore, by ignoring universal constants, we have from
15
and
62
that.
1
E
[V
11 12
| 12
(64)
T
dB vT
B T +
nI² B²
[f(²)- f
+ LB2 +
C(1+ +2) +(1 + C(1 +
VnT
VT
T
Because n S T, we have
60
from 64
Case (ii): Define h(32) 7 T
8a(1 1111-80 83
Notice that ((82) 7 + ΣT- (1 11- and thus h is decreasing
F2
[0, 1). Hence h(32) < h( |
for any 32 E
1 15747:1). 1). In addition,
( (xT4T) )" (1 5 (o
(0T 1)
pf S
and
32 T(1-ba) for 32
FT+I- Thus it holds that for any $2 E
of
pf 1);
vf
h(22) h pf
- = 1-p (1
pT (
(11- 1 マं
pl pf S
1
(65)
pT +1
By Taylor expansion - at the origin point, we have e
pT+T +
Ta 21p++1y3 which together
with 65 gives
pT
pT pT + +
1332) I pT +1 2(pT 1)2 pf
S
BB
(66)
2p"
With the choice T n and = VnT, we have h(32)= S VnT n, have from 62 that by ignoring universal constants,
Hence, when independent of and
Σ
E
|
| 1
71
=0
((()))
- +
dB3 Vn VT
+ LB + dBB L+ dBs.
CB2 (1+I2BB
122 B
VnT
T
which indicates
61 by S.
Remark 3 (Linear speed up and topology independence) In Case (i) of Theorem A.2 with the cho- sen and 6, if
n
(1- 172) (2- 1)
n
T= Ω
max
(67)
(1 p2)a
we have C = 0(1) and T = 0 1 ) and thus 60 implies
T
Σ
E
V
12+
= =0 | 113
(68)
T
VnT
For Case (ii of Theorem A.2 with the chosen and 8, if
n == max (1 72yd (1
n²
(69)
then C 0( ) and 7 0 (
V Thus 61 also implies
68
Notice that letting be selected
from {0, .O....IT T 1-11 1} uniformly at random, we have from 68) that E
V
[ [1] O Vnf For
given > O, we need T θ ( iterations produce an E-stationary solution in expectation, i.e., E [Vi(x*) H <
=² 2 If is sufficiently small such that T θ ( (+ satisfies the conditions in 677 and 60). we obtain linear speed up with respect to n, and the parameters and 8 are independent of the commumication graph.
27

---

B Convergence Rate Results of Algorithm 2
In this section, we analyze the convergence rate of Algorithm 2
B.1 Noncompressed case of Algorithm 2
For case of reading, we first consider the special noncompressed case, where T = 7g = 1 and Q = I. In this case, we can write the update in the more compact matrix form as follows
G = - - VF' VF'-VF"11
(70)
G = G'
(71)
M = 8, B/-3')
(72)
x X' aM
(73)
x = x
(74)
where we use notations in Scction by letting
G
g 9
9h. G' =
91 4- 1-3
.9
1-1
Under Assumption 5 one can easily have
E,
g
V fi (x
(75)
In addition, is straightforward to have
1 Σ
9
VF, (2. 5t)
(76)
n
n
1=1
im1
With these, we first show the following lemma.
Lemma B.1 Under Assumplions and
it holds that.
o²
+ 2L
E [1g E
9
+ 2E
[ [19]
(77)
n
Proof. We have
E
E
(s(())
V
75
1
9
+E
V
f((E))
1m1
76
E
(of.
v(((t)))
+E
Σ
v
fa (x)
i=1
1=1
127
<E
VF
1
+
||
||3]
+
2E
-
f((())) - V
n
+ 2E
||
[1
2L2
X [19]
7
where the first incquality follows from Young's inequality, and the second one holds from the independence of (C), Assumption 5 and (34). The proof is then completed.
28

---

Lemma B.2 Under Assumptions
and 5 let $ at. Then
20
E |
[B [ (z*) - E / (2(+)) +
(78)
61,2
6I.222
E X 11
(1- E
m mm- 11]
Proof. By 55
with u = and 1, we have
E
vs (z) Σ g )
+
_
|| - =2111²]
(79)
2a
In addition, it holds
( V (z)) (z'). 1
Bc
75
V 1 Σ
V (a+)
Vf (2 V (3))
(z!) (
(f()") ) V/ (3')
Vf (
V
(x))
1=1
31
L
2/'
x²11
L
1| 1.2 1| x1 -
1 1 || (z*)]²
2n
1 |V (z')1²²
L
X
2
+
V xx') 1
3L
3L
1
||
=='1"
X
||
V क 2
2n
3L 87
3L2
m 1112
X
||
2/2 Vf (=))
(80)
2(1
31)2
2n
where we have used 31 and 33
with u 0 and = 1 in the last equality.
Moreover, by
32 with u
0 and 8 = 1, we have z++1 x²= - gf Thus
L E ||
20
2911]]
aL E
9
aLo²
+ aLE ||パ
aLa E
[|X]|] [1
(81)
2a
2n
Substituting 80
and
81
into 79
yields
1 - ab
aL
E
V
)|²
- (E [ (2'] -
aLo²
2
2n
(82)
LL3
3L2
3L2a23?
+
E
E
m -71-1113
2n
2(1 31)2
Now notice 1 aL 2 1 from the condition on a, and we complete the proof by 82
Lemma B.3 Under Assumptions 1 and let S +.
Then for all t 2 0,
0²
2L E ||| 111
m' [3]] 2 [[m=- + (1 - 81)
+
2 ||V
(83)
n
29

---

Proof. By
72
it holds
|| + (1 g 19]
E
m
E
3
E
m
11
+ (1 B1) E |0
(84)
E
21
(1 Bi) (-- n
+ 21E
|V
2L E
||X [|Xx|PP)
which completes the proof.
Lemma B.4 Under Assumptions 1
22
and
holds that for all 2
E ||
[]]
1 +
p²
E
||
|
+
p²(1 + p²)
2no²
(85)
2
1- p²
8BB
||
||]]
4a 2a²p²1
|| 11]]
+ 4
|
E
||
||]
s
8
M
["]
+ (1
3,)
||
(86)
Proof. By
70 and 71 we have
G
_| G (W- J) G J) + (VF' VF (W- - =]]
- J) + (VF VF- (W- -J]
+ (w)) (VF'-VF"") (W -J)
1/ pp² VF VF' 2 (W--IWW--- J), (VF' VF'-1) (w -J)).
(87)
where we have used JW JJ = J and W - J1|2 p. For the third term the RHS of 87 we have
2(G (W - JJ,, (VF' - VF (W J))
<2 G - -J)] || VF- )) (W- JJ)|
<20² | VF VF 1 1 p²
2p
G 1|
VF
(88)
1 I-p² pa
where the second inequality holds because follows from Young's incquality. Plugging 88 into
W - 2 and W - = (I-J) - JJ, and the third one
87
gives
G
2 _
+
0²
G
p1 p²) p2
VF' -VF-112
(89)
In addition, we have
E
V
VF
E
V
VF - +
-
E
VF - VF - Vf
- V - -
<2no² 2 + L2 | - -X
(90)
30

---

Moreover, by
73
and 74 it holds
x
x
(x' aM W- X
< 2 x (W - r)|l 2a |
(W- 1) - (W- - 1 l|
+ 2n² M w - M + M 1-1
2 x
s 8 | 112
4
M 1 (W- - J)(l² + 4a²
| M I
-1-11
8
2
| [I J)(W - ]]
+ 4a2n m 11
s 8 x
4a² p² M 2 + 4o m 1|
(91)
Now substituting 90 and
91 into
(8 and taking full expectation yields (85)
Finally by 72 and the convexity of I1-112, we obtain (86) and complete the proof.
We are now ready to show the convergence rate of the noncompressed case of Algorithm 2 by combining Lemmas B.2 B.4 and the following inequality that is obtained from 17 with Y M
< 1+
p²
2p²a²
+
M
(92)
2
Theorem B.1 Under Assumptions Q = I, and 0 < S I salisfying
1
3 and
let (X'} be generated from Algorithm 2 5
with 7/2 = Yg 1,
p1 + p²)
022L3p²a²
+ +4a² p²22p²1² + 2 + 4p²a²
1+ p²
(93)
1- p2
(1 - p2-
(1 (1- p2)3
4
12L²a²33 (1- (1-31)2
+ 8882 no2nnI2C - 2'
(94)
where Cg is defined as
4p²(1 + x²)
4p²a²
(4aL3
6L
12L4a²8
Cg
+
(95)
p2 (1 02y²
n(1 81)
Then it holds
V (x |||]= S 8
at (1 -5²) + 4aLo²
E
+ 22, 4422200
(96)
n
+
X < (1 22)2 (1 12)2
4p²a² 4p²(1 + p²)
22n0 + 4a² L20 + 80 2 nL²
T-1
[|(
(97)
T
1=0
Proof. Sum up 92
over t = 0 To T - 2. We have
T Σ
X 1+ 2 T 2
2p²a² T-2 p2
X
M 1|
which together with Xº = 0 gives
4p²a²
T-2 Σ
Σ
12 <
x
M 1|2
(98)
(1
22)²
1=0
31

---

Similarly, summing up 86 over t == -1 to T", noticing M 0, and rearranging terms, we have
E M
E
Gill
.T' > 1.
(99)
1=
Plugging 99 with TT=T- 1 into 98
yields
T E
4p²a² 12)2
T-2
X1
2
- (1
Σ
E
|
(100)
t=
t=
In addition, summing up
83
over t = 0 to T - gives
T
T-1
T-1
0² + 2E |[ ||²]
2L
33
E
m
+ (1 - 31)
Σ
+
E
[ 1P]
n
t=
t=
100
81
T-1
E
m
1-1 2
(1 (1- 3
+ - 31)
T-1
Σ E |,<>)
(101)
t=0
2(1
B1)1.
4p²a²
T-2
Σ
E G 1|]]
n
(1
2²)²
1=0
Since m =0, 0, we have from 101 that
E
To²
+2 Σ
E
2L
4p'a²
T-2
Σ
E
G
[|]]
2
(102)
n (1 p))
Now sum up 85 inequality. We have
over t 0 to and plug 99 with T =
1, 100
and
102) into the resulting
Σ
B
[[
||]
<
1+
22
T
|
+
p + p²)
T-1
Σ
2no²
2
1 1- /2
1=0
1=0
+ I
8E
||X|_ 11]]]
+ 4a 2 p²
|M-111
+ 4a Laa2ma
m --
(0--)11)) 11)))
1+ 2 T-1
E
G ||-
+
(11+
T
(32T.2002
+ +402pI2
T-2
Σ
e [|c 17)
2 1=0
1- 0²
(1 p2)
22)2
1=0
+ 44a² nL (1+
To²
+2
E
||
212
4p202
T-22
E [|CH|I?]
(103)
1 p-
n1
n (1- 2²
t=
Define
1 1+ /²
(1 p2)
(3212p2a²
4a 2 + 8 4p²a²
A
1 1- p²
(1 p2)²
By the condition in 933, it holds X A 3(1 3(1-p"),
Then 1 - > > 1-p² and
1030 indicates
1
EE
<
40²(1+p²)
2mo"T + Sa nL2
T
E [((T))|)
(104)
(1 22
32

---

Finally, sum up 78 over == 0 to T - and recall f(z) 2 f 2 to have
||
3 ) 11
(5(=)) -*) + 2aLo"T
4
279
T-1
6L?a? 39
E
m
m1
(1- 31)
t=
t=0
4
4aL'3 2aLorT
2L2
4p2a²
T-2
<- () -r)
E
G
(1 p²)²
n
m
n
6L22288
To
+ 2
T-1
E
Vi((*') [|2]
+
2L 4p²a²
E
| [[]
(1 -31)2
11
n (1 p²)²
t=0
(s (2") - -³) + 2aLo"T T
a 89 (1- 31)
T-1
Σ
E ||< |
(105)
+ Cg
2n + 4a 1,2 + 80²
E [|
(106)
where the second inequality follows from 100 and 102 the third one obtained by plugging q144 and
Cg is defined in (95). By the condition in 994. we obtain
(96) from [155.. Plugging (104) into (100) gives
97 and completes the proof.
Below we specify the choice of a such that the conditions in 93 and 94 hold and simplify the convergence rate result in Theorem B.1 for Algorithm with T/e 7a = 1, and Q
Thcorem B.2 Suppose that the conditions assumed Theorem B. hold. Let T be large enough such that
OVa for some universal constant E (0, 1) satisfies a oVT
p-p² (1-
1-
(1-p2)²
S min
(107)
8L
PLv160
160
BLLV48
(nT)
Then it holds
1 x 1|
E
Vf
0
(108)
VnT
Proof. By a < L-p² it holds 24 VSL
402a² (1-p3y
<
4a 1a²p21² L2 Hence,
32L²p²aa
4p²a²
32L2p²a²
40L3p²a² 1 1- p-p² + 222 (1 2282 -
(1 o2y3 + 4a p² 8a
<
22)
p2-²
(1-
where the last inequality follows from a < PLv160 Thus the condition in (93) holds by p S. 1.
1-81 In addition, it follows from a - 3,LVI
that 121,2022
(1-31P- < 1 Moreover, by z and B,LV48 it holds
1-8
12 -11-81)
< SL2 Hence,
Cg S 4p² + p²) 4p²a² 8L2
(109)
(1 - 22)2 (1 - 22)2 n
and
na2nL2C, < 3a²n1" Ap² + p²) 40²a² 8L2 1
(1 (1- 22)² (1 22
4'
33

---

where the last inequality follows from a 8L and 97 hold.
1-p²
This verifies the condition in (4 Therefore, both (96)
Finally, notice that by 109 and a S (1-p8)2 we have
16L (1T)
2C + 4422 < 41+
4p² 8L2
p2)² (1 p-2 2(2no= + 44a2
p p2) (2no² + 4a 22000 S
2
(2no² + =0
(110)
nvnTo
nv nvnTo
Hence, (96 implics 1 +Σ= E
=0
Also, by the same arguments in 110 and (97
vnT
have E XX
2
Thus (108)
follows. This completes the proof.
VnT
B.2 General case of Algorithm
2
In this subsection, we analyze the convergence rate of Algorithm in the general case. Again, we write the updates in the more compact matrix form:
- VF' VF
G' G'= G G G G
G' = -'- + 1),
M = 3M +(1 - G)
x X aM'
X X' Q 1 X
x x x (+] (W- - I).
Let W, 72 (1 7x) I and W 7g W + (1 %// I. Then we can write the X and G updates to
x = x W x % x - -x+##) (W- - 1),
(111)
G - - W + % G (W- I).
(112)
Again when W satisfies the conditions in Assumption 2
W = and W, also satisfy all three conditions.
Indeed, we have
J
1, Pg = W g
1.
The next lemma directly follows from Yan et al. 2023 Lemma 15).
Lemma B.5 Under Assumptions
and holds that
E
G c+t - - +
2 || - G 11]
+ 6n) + L ||
||xt1-x|11]]
E
c G c+
1 G' 1
2
6n
+
41,2
||
(xx+1xxx117]
x'11a]
1 172
1 '-
Lemma B.6 Under Assumptions
1 and let a and 7a satisfy
(1 11-17 ?)
1- 2
r?
a
V2
0
<
7a < min
32
60n
25
2n
34

---

Then
x
11
3+ 22
E
X
11²
+ a² 1- PH
40
E
M [1a]
4
+
4my
(1
x
x-11²
+ a²
||M [1]]
3
45
E
x
X
[1]]
1
E
X [-]
3 3+
E
X x11
1
172
a²
+ 4a²
E
[|MM
[1
18 [[M 11
1/2
x - x x-11² |||
- 2a
|| ||
+ 12IE
|
|2]
+
4v
X - -x-1²
|M = E ||M [1]]
m 1 ["]
E
nE
Proof. By
16 with W replaced by Wa, v. we have that for any mn > 0,
| < (1+ (4+m) x Wa J)|l +4(1 + vi 2/ ( 2 -x -x
(113)
In addition, by 20 with Y replaced by M, we have that for any 122 > 0,
x ++1
x
s (1 72) ||x - xx11 + + (1+ no a²E |
(114)
Moreover, we obtain from 17 with Y replaced by M and W replaced by Wa that
x W (I n
1+ 2
X
a 7
M 11
(115)
Substituting (155
and 114b with 722 = 1 into 113) with 7
Tnnz
we obtain the first desired result by
1-p
using 233
By 25 we obtain that for any 773 > O,
E x
<1+ ma) (1 2 B
x x 1|]
(1 152 4 x
(116)
Also, it follows from 26 with Y replaced by M that
E
2E
X
11]]
+ 2a 2
M [1
(117)
Substituting 117 and 114 with
7/
1-9" 2n²
into
116
with 7s 1-9² we obtain the second desired result
by using 288
35

---

To show the third desired inequality, notice
E || - x 11] = B
- X x W. x² + - x (w 11l2
X x W - x'1 + (1+ + ni )
7/ ( x ( -1)
5(1 + (hh E
[x x' + x (W -bl²
+4 (1 + nT TBB | x
5 + 1
| x-1 xx|]
+ 8IE | [|x1|9]]
5(1 + 944)
2
(118)
x -x( 1|] - -1 - xx1x x(())
+8 + na 1) 22:1?
IE
S4B
x
X* 22
[]]
+ 12E
| 11
+ 4v 22
||X' -x'I
2B [|M]]]]] + 12E
27
+ 2 IE || -x|]]
(119)
where M/ is any positive scalar, the second inequality holds by || -1|25 2, the third one follows from and in the fourth incquality, we take 171 = 27 and have from Yv 1 v2-1 that
20
2n
2(1 + 14) 8 (1 + n/ ' 2zn2 2(2 + 1)² S 4, 8(1 + m1 s 12, 8 (L + )) S 4V
This completes the proof of the third desired inoquality. The fourth desired equation follows straightforwardly from the fact (M1MM) = O.
The following lemma bounds the consensus error and compression error of G.
Lemma B.7 Under Assumptions
1 2. 3
and
let 7a < min
V VI- 12n
1-
Then
25
E ||
<
2
T
E
||
+
48
|| - G2||
+ 11no2
+
5L2
IE'
X [xt+1 -x x1]
3
- P3
1 P
E ||
1|]
n
3
12
||| - G']
+ i- 172
1047 2
E
|| [1]
+ 1-
61.2
E
||||||_
x 11]
9no
172
7
Proof. By the second incquality after (69) in Yan ct al.
2023 Lemma 18) (with Y in Yan et al.
2023
replaced by our notation G), we have the first desired inequality. The second desired inequality follows from the inductions after (71) in Yan al. 2023 Lemma 18) (with Y in Yan et al. (2023) replaced by our notation G).
Notice that Lemmas B.2 B.3 and 866 still hold for the compressed case. With these, we are ready to show the convergence rate of A Algorithm in the general case.
Denote
(ET
4 f*), 13 ||| 12] E || E [|]]"|]]]
| |+
E || E -
E
Then Lemmas
B.2
B.3 and
86
together with Lemmas B.5 B.7 imply
2 < A + AΩ + + + c.
(120)
36

---

where
1
1a
GL
(1-8))²
3+p2
11
4p2
0
0
1
P
15
3+
0
0
I-1j
1-1]
A
(1
31) 2.
81
0
0
0
0
0
B1
0
0
601
20v 2nr 1
20n 1
2+P
181""
1 1-P8
1-P3
1 03
3
1 1-p3
721."
24/2mm7 L
24a 12
1047
3 3+1
14
1-17-
0
0
0
0
0
0
2
0
45
0
G 12
0
0
1-11
A
0
0
0
0
c
(1 - B1) g"
0
0
1
31
0
20
0
1lno2
1-p2
24 24n²nn 1-1-
0
1-1
9nd"
-E
[| (x.) [1]
0
0
b'_
2 - 31) E
V (2+)1
for all 2
0
0
Theorem B.3 (Complete statement of Theorem a/a: 7g and a satisfy
4.3
Suppose Assumptions 1
2
and 5
hold. Let
1
Pr
172
V2-1
1 Pg
Pg
1
172
To S min
79 I min
60y)
25
21
25r)
25L
25
25L
1
Yo (1-
17²)
Yg (1 n72)
1o p3)
1o(1 P
a S min
165
32
12L.
12vb
12L n
(121)
(1- 3i)
2L
(1-A1)²
61,3
+
45(1
b 2412+1
p))
+
2012 (1-12)² (1-P3)²
with b 4 (T.
72
601
Then it holds that
(1 11-
(1- (1-p2)²
T-1
Σ
[|V]
Σ
E
[|| [12]
2LT
nt
4
200
02 1 B1)
11
9:z02
(f(x:") - 1n)
aLT
2Ln
1 P3
122?
Proof. For any (q1, 42. 93. 94 9s. 97)
2 0, multiplying q" to both sides of 120 gives
(q T - q A) <q AΩ 1
+ q T b' + T
= -qq A) + (q A A +q
TT.
(122)
37

---

Let
b
1
Q1
L
Q2
1
Q3
1
rp2
na?
6
b
24L +1
2012
91
31
(1-31)
+
45(1
pgg
22
ig
9g
Q5 6(1 B1)
98
47
Dg
1p
With the choice of a, we claim that
q
q A q
A S (0, (0,,-1,,,,,,00,00
(123)
First notice
77g
n
91 I
<
79 $
2L
8L'
2L
and it is straightforward to have \ = Second;
aL3
3L
3 +
p
1
93 + (1 - 31) 2L
60L
72L
A2
=4
11
2n
q1
+
4
Q2 +
112
"
44 +
1 - Pg
96 +
11 97
92
3L
b
1
2L
60
727 L2
=4
aL2 2
+ (1-
Q1 + (1 12g )2
2
(1 1/222
n
-1-1
b
1
+ (1 B.)L + 60 2 L2
?21
S8L
22)2 S 11
(1 2))
(1 Pg 2
where the first inequality follows from I the definition of b. Third,
1 and 인1 S
n 2L
and the second inequality holds by To S 1 and
2L,
A1- 4ma (1
3 12
20 20
24
24 L2
3
42 +
4
23 +
1
P3
46 +
1
-17
'77
93
4
20 2
Yoe
I
24v
2m
ig
2
4ab
1
1
1
+
< 0,
3
(1
(1
1222
3
4
12
12
by the choice of 7g. Yas and a <
1 Fourth,
166
6L
ann
a²n
2022n
24a2nL2
A1
(1 31)2 91 + + 24 +
92
1/2 43
Q6 +
1 1-1 97
45
1
1 - 72
6Tma2 B7
(1 - B1 144 + a2n
b
20a 22222 n2L
2 2Aa??2nL
+
< 0,
(1 31)2
45
1
2
(1
12)2
(1 m2y2
(1 1222
by a, 2g I1 1 and the choice of qu- Fifth,
17
5a
20a2
24a2
Ag =0
42
43 + B.99 +
96 +
1 1- 17² 97 - q3
P2
45
1
1/2
1-
1
p3
172
1
b
5a
20a 202
1g
24a 24a²221 12
=0
(1 - 2722 (1 (1-11)93 +
0,
2
45
1
P
(1 22)
(1 1?)2
(111)??)
1o(1 (1-92)
(1-2-))
(1(1-p))
x/2 Sixth,
by < min
and q
32
12L/a
12vb
12L//
2
2+ 03
104-2 2
22
2
104
Ag = (1 - --
+
46
+
47
96
(1 - 22 0 0
3
172
6
3
38

---

by 7g 25
1-n"
Seventh,
48n"11g
3+ n22
48n T pgy )2
X7
96
47
97
<
1
Pg
4
4
1-2 25n
by 7g v
Thus, (123 is obtained. From (122) and 123
it then holds
(0,1100000000000222 $ (q T q A) - (q -q A' + + +q"c.
which implies
E [ (q _ q
(q q A)Ω' + + be + t
(124)
Summing up 124 over 0, ..... T and then dividing by nT gives
1
E
[P] $ nT (q
------
1
Σ t=
q b' + 1
cTc.
(125)
nf
nf
1=0
Notice q _ - A- _ A X and Ω- 0. Hence (q T q AA 12 0, and thus
1
1
(q - q
AA) A) -2-1 12- - nT (q - -q AA)--
n
4
4
onT 11 (J(2²) - (r)
aL. (J(=9) 1*)
(126)
no² 2L
In addition, we know from S
that
2002
21 B1)
2
117002
97.02
q
<
1g
(127)
n
2Ln
P
(1 172
Moreover, it holds
[[
(
+14 31)11 (+)) [2])
B1)LB
nT
n21 B1) E
E
||
x
|||]
4L
||
(x*)
|+]
(128)
2LT
where the first incquality follows from 94
Substituting
126
128
into
125
yields
T-1
1 T-1
E
113]
Σ E | 12]
2LT
nT
1=
1=0
4
2002
2g 000 (1--1) B1)
11:302
97300
(f(2²)
(*)
+
aLT
n
2Ln
1 22
(1- 72)2
The proof is then completed by noticing 20 = 5
The theorem below directly follows from Theorem B.3 by plugging the specified algorithmic parameters and ignoring certain constants that independent of and T.
39

---

Theorem B.4 Suppose that the conditions assumed in Theorem B.3 hold and a Pivn ovT
7
02y/
ovT
and
lsv N = oFT for some 01, 22 0g E (0, independent of ' and n. Also, suppose n S ST. Then
T-1 IV
1 1 =0 1
(VO +
1212 ))
(129)
VnT
P3 (1 - 17)3
Remark 4 (Linear speed up and topology independence)
Prom Theorem
B. we see that if
2 0² - pgy 0²
n²
n
n1
n
n
n
T= max
02(11 p3)
-
o2 11-1
22) o² pg) 0² n1² )
130
then a = 0 (( 7 = 0 (( 7 =
0 ) T
= 0 ((TT)) and the RHS of 1-pz + イー
129
becomes ( (aT) Thus we have
Σ
IVf (T)) 1 11?
=0 =((2
(131)
VnT
For a given 0, let T = 0 nc+
( and be selected from {0, 1, ................................ T 1} uniformly at random. Then
X is an e-stationary solution in expectation, i.e., E [ (x 11 [X{ S e². When & sufficienlly
small such that T = n satisfies the conditions in 130), we obtain linear speed up, and the algorithmic paramelers are independent of the communication graph.
C Examples of Compression Operators that satisfy Assumption 3
In this section, we provide few concrete examples of compression operators that satisfy the condition in
Assumption More examples that satisfy Assumption 3 can be found in Chen et al. (2023a); Koloskova
ct al. 2019).
Example C.1 QSGD
Alistarh et al. 2017) compresses Rdd by Qagd(x) sign(x))
xx]
E where
xxl
is uniformly distributed on [0, 11 s is a porameter about compression level. Then 2(x) = 1 1 Qusgal( (x) with
== 1 min { dd/3,, vd/s)) satisfies Assumption with v 1
Example C.2 Q (x) Stich et al. 2018 randomly selects l. out of d coordinates from x, or the k coordinates with the largest values in magnitude from æ. Then Qsparse(x) satisfies Assumption 3 with = 3/2
Example C.3 Q (x) sets Qgoessp(x) (x) x with probability E [0, 1] and Q gosssip(2 (x) = 0 with probability p. Then Q gossip (x) satisfies Assumption with p.
D More Detailed Comparisons
In this section, we provide more detailed comparisons with related work.
D.1 Term- -y-m-by-term Comparison with Prior Work in Table
To complement Table D we provide a detailed term-by-term comparison of theoretical convergence results between our proposed algorithms (DAMSCo and DaSHCo) and related methods listed in Table [
CMP, AG, MMT: DADAM Nazari et al. 2022). DAGM(Chen et al.] 2023b). and our proposed DAMSCo incorporate both adaptive gradient updates and momentum acceleration. However, unlike DAMSCo. DADAM and DAGM do not utilize compressed communication. Choco-SGD(Kollooovn et al. 2019
40

---

BEER Zhao et al. 2022a and CDProxSGT Yan et al. 2023 perform compressed communicatio but do not apply adaptive gradient updates or momentum acceleration. The compression effects in these meth- ods are represented through a simple reduction factor of (1 -1)) 1)) per communication round, while this is absent from DADAM and DAGM.
DH: DADAM, DAGM, Choco-SGD, and our first method DAMSCo require the bounded gradient assump- tion. This limits their theoretical guarantees in scenarios with DH. In contrast, our second method DaSHCo, and CDProxSGT and BEER do not need this assumption, thus being able to handle DH.
CMR: In terms of communication rounds, the number required per iteration varies depending on the use of gradient tracking. BEER, CDProXGGT, DAGM, and our proposed DaSHCo perform gradient tracking and transmit both model parameters and local gradients at each iteration, leading to two communication rounds. In contrast, Choco-SGD and our proposed DAMSCo, without gradient tracking, require only one communication round per itcration.
LS, TI, convergence rate: Here, LS is characterized by clear 1 dependency in the convergence rale, showing that the convergence rate improves linearly with the number of agents (n); TI refers to the capability of choosing learning rate independent of the topology parameter p. We do not compare to the convergence rate of Choco-SGD as it assume strong convexity, which is not directly comparable with our considered nonconvex case. When is sufficiently large, all methods except Choco-SGD in Table I have the convergence rate of O and thus achieve LS and TI.
D.2 Comparisons to more related work
In this section, we compare our proposed algorithms (DAMSCo and DaSHCo) to several more existing decentralized stochastic optimization methods.
Our first method DAMSCo is designed with adaptive gradient updates, i.e., Adam-type updates. Its con- vergence rate is O(1/VT) and aligns with the rates established for existing (nondistributed or distributed) stochastic nonconvex optimization algorithms that use Adam-type updates.
For momentum-basee algorithms, a few recent works enhance thcoretical convergence rates by incorporating variance reduction (VR) techniques. However, we observe that, in practice VR-based methods can ex- hibit unstable performance and poor generalization, particularly in training large-scale deep neural networks (DNNs). Specifically, through additional experiments comparing our algorithms DAMSCo and DaSHCo against the VR-based method DoCoM (Yau & Wai 2022), we found that our methods significantly outper- form DoCoM; see Figures and 10 in Appendix
E
Below we compare the convergence rate of our second method DaSHCo with four recent notable decentralized algorithms, along with the difference of their assumptions.
SQuARM-SGD (Singh et al., 2021 achieves the same convergence rate as DaSHCo. But unlike DaSHCo, SQuARM-SGD does not use the gradient tracking technique. It requires either a bounded gradient dissimilarity assumption or bounded gradient assumption, which is stronger than our assumption for analyzing DaSHCo.
DoCoM Yaau Wai 2022) achieves better sample complexity than ours. It relies on the VR. technique and requires the so-called mean-squared smoothness assumption, which is stronger than our assumption on smoothness of the population function. Moreover, VR techniques can yield poor
generalization performance, we observed from Figures g and 10 in Appendix E
Cedas (Huang Pu 2024) achieves the same convergence rate as our method DaSHCo in a noncon- vex setting. But it makes stronger assumptions on the mixing matrix W, requiring W to be positive semidefinite and symmetric, while we do not need these restrictive conditions.
Islamov et al. [slamov et al. 2024) give two methods: MoTEF and MoTEF-VR. MoTEF has the same convergence rate as our method DaSHCo but needs stronger assumption than ours in W. More precisely, it additionally needs W to be symmetric. Similar to DoCoM, MoTEF-VR achieves the
41

---

DANSCo DaSHCo
DADAM
Toiiiing Lnte
1.5
CDPras
Test Accurecy
60
10-2
Consanuus
10-4
0.5
10-4
20
40
60
80
100
0
20
40
60
80
100
20
40
60
80
100
Epechs
Epechs
Epochs
DaSHCo
10-1
DADAM
10-2
Traning 1085
DAdaGrad CDPRoXSOT
Test Accuracy
60-
Consensus
10-3
20
20
20
10
50
100
150
200
250
300
50
100
150
200
250
300
50
100
150
200
250
300
Epochs
Figure 4: Results with homogeneous data: Plotted above are (from left right) the training loss, test with respect to epoch for the FashionMNIST (top) and CIFAR-10 (bottom)
accuracy, and consensus datasets, comparing DAMSCo and DaSHCo with CDProxSGT (Yan et al.
2023 Distributed Adam (Nazari
et al. 2022 Chen et al. 2023b), and Distributed AdaGrad (Duchi et al. 2011 with Top-k compression.
optimal convergence rate, by utilizing the VR technique and assuming the stronger mean-squared smoothness assumption.
E
Additional Numerical Plots
In this section, we first include our experimental results plotted with epochs as the x-axis instead of commu- nication rounds. Figure 4 gives the results for homogeneous data and Figure 5 for heterogeneous data. We also include QSGD quantization (Alistarh et al., 2017) of compression instead of Top-k k in Figure 0 Here, Irain the model on FashionMNIST with both heterogeneous and homogeneous data. We note that our proposed algorithms perform quite similarly to what we observed for Top-k compression for the homogeneous case, while Distributed AdaGrad failed to generalize. For the heterogencous data, we note that DaSHCo can successfully train the model and achieve the highest test accuracy, though convergence slower. We suspect that 4-bit quantization more aggressive than Top-k(0.3) and thus leads to less competitive results.
Further, include comparison between grid and ring topologies for the communication network. Our primary experiments utilized ring topology, and these additional experiments demonstrate the ability of our methods to generalize to additional network topologies. For the experiments given in Figure 7 and Figure R we run with 9 MPI ranks in ring or a 3 x 3 grid on the FashionMNIST data. We run with homogeneous data Figure 7 and heterogeneous data Figure g For the heterogencous case, we only perform training and testing on 9 label classes, with each MPT rank training on a single class. We note that the difference results between the diffcring topologies is minimal for DAMSCo and DaSHCo, though there is an apparent difference in results with the higher number of MPI ranks. We further note that we observed instability with DADAM training with heterogeneous data and our test hyperparameters. Future work will focus hyperparameter tuning for larger MPI ranks and more in depth study of the effects of MPT rank counts, communication topology, and their interplay with the performance of the proposed algorithms.
Additionally, we include a comparison to the sfate-of-the-eeee DoCoM optimizer Yaau & Wai 2023). We select DoCoM for comparison, as theoretical convergence rate tighter than ours and the other suggested SOTA methods, and the code and experimental data used by the authors are readily available. We directly use the hyperparameters the authors tuned for the LeNet5 network Fashion dataset, and replicate
42

---

102
DANSCo
2.0
DaSHCo
80
10a
DADAM
DAvaGrad
Acouracy
101
Traiiin
10-1
1.0
60-
10
10-5
20
10-1
0.0
100
Epochs
Epochs
Epochs
DaSHCo
80-
DADAM
Training uoss
DAdaGrad CDProX5GT
Text Accuracy
60-
101
Consensus
10"1
9.-
20
10:4_
0-
50
100
150
200
250
300
50
100
250
300
50
100
200
250
300
Plottod above are (from left to right) the training loss, test accuracy, and consensus error with respect to epoch for the MNIST (top) and CIFAR-10 (bottom) datasets, comparing DAMSCo and DaSHCo with CDProxSGT, Distributed Adam, and Distributed AdaGrad with Top-k compression.
Figure 5: Results with heterogencous data:
10a
DAMSCa
2.0
DoSHCoo
DADAM
Taining Lodk
Test Accuracy
60
Consensus
100
1.0
40
10-1
10-1
M
0.0
10-2
20
40
60
80
100
0
40
60
80
100
40
60
80
100
Epochs
Epochs
DAMSCC
70
10:
2.0
DADAM
60
10'
DMdaaGrrd
50
100
Traiiing
40
Consensus
10-1
1.0
Iest
10
10-1
0.0
10:4
20
60
100
100
40
60
100
Epocihs
Epochs
Epochs
Figure 6: Results with QSGD: Plotted above are (from left to right) the training loss, test accuracy, and consensus error with respect. to epoch for the FashionMNIST datasets using homogenous data (top) and heterogenous data (bottom), comparing DAMSCo and DaSHCo with Distributed Adam and Distributed AdaGrad with 4-bit QSGD compression.
43

---

DAMSCo
2.0
DADAM
1.5
DAdsCrrd
Test Accuracy
60
10-3
Traiiing
10-3
40-
10.1
10'1-
0.0
20
40
60
80
100
40
60
80
100
40
60
100
Epochs
Epochs
Epochs
DAMSCo
10a
2.0
DADAM
80
10'
DAdaGrad
Acturacy
60-
10-t
Training
Consensus
10-3
10
0.5
20
10-1
0.0
20
100
Epachs
Epochs
Epochs
Figure 7: Grid versus ring communication networks comparison with homogeneous data: above are (from left to right) the training loss, test accuracy, and consensus error with respect to epoch for the FNsHT datasets rumning on Ring (top) and Grid (bottom) topologies for the communication network, comparing DAMSCo and DaSHCo with Distributed Adam and Distributed AdaGrad with Top-k compression.
Plotted
DAMSCo DADAM
80
10a
2.0
107
Test Accurecy
60
Trahing
Consanuus
10-2
1.0
40-
20-4
10-4
10
0.0
20
60
80
100
40
60
80
100
60
100
Epochs
Epochs
Epochs
10:
DAMSCo
2.0
DaiSHCo
102
DMDAM
DAdaaGrad
Test Acoracy
60-
101
Training
3.0
M
10-5
20
10-7
0.0
100
Epochs
Epochs
Epochs
Figure 8: Grid versus ring communication networks comparison with heterogeneous data: Plot- ted above are (from left to right) the training loss, test accuracy, and consensus crror with respect to epoch for the FasHionMNIST datasets rumning on Ring (lop) and Grid (bottom) topologies for the communication network, comparing DAMSCo and DaSHCo with Distributed Adam and Distributed AdaGrad with Top-k compression.
44

---

the experiments from Figures 2, and 3. We give these updated figures below in Figures 9 A preliminary study suggests that hyper-parameter tuning with DoCoM by itself is unlikely to significantly improve upon the results presented here.
10 and
2.0
DAsaGrad
70
20
15
Da9iCo
DoCoM
30
1.0
30
20
30
30-1
2.5
CDPre SCT
107
DADAM
2.0
DAMSCo
70
Conaamus Emeets
20
DoCoM
50
20
1.0
20
0.5
20
20
0.0
10.
25
175
25
50
125 Communicatie Bounds
75
100
150
175
1500 125
175
Commurication Rounds
Communication Rounds
Figure Results with homogeneous data: Plotted above are (from left to right) the training loss, test accuracy, and consensus error per communication round for the FashionMNIST on LeNet5 (top) and CIFAR-10 on Fixup-ResNet-20 (bottom) benchmarks, comparing DAMSCo and DaSHCo with DoCoM, CDProxSGT, Distributed AdaGrad, and Distributed Adam with Top-k compression.
CaPros501
90
DADAM
107
2.0
DAMSCo
DAdaGrad
1.5
50
20
Itan
1.0
40
20:9
30
0.5
20
30-1
20
40
80
100
0
20
60
100
Communication Rounds
Communication Rounds
Communication Rounds
CDProNSOr
102
DAMSCo
Los3
DoCol
DAddsGrad
Daditit
70
Ornemuu Erooks
101
10-1
20
30
150
250
300
Communicatioo Rounds
Figure 10: Results with heterogeneous data: Plotted above are (from left to right) the training loss, test accuracy, and consensus error per communication round for the FashionMNIST on LeNet5 (top) and CIFAR-10 on Nixup-ResNet-200 (bottom) benchmarks, comparing DAMSCo and DaSHCo with DoCoM, CDProxGTT, Distributed AdaGrad, and Distributed Adam with Top-k compression.
45

---

CANBOC SAdin
10:1
10-
10-
200
200
400
200
(9
100
Communicction Rounds
200
100
400
500
600
5
100
703
Communication Rounds
100
4.00
500
600
Figure 11: GPT Results with homogeneous data: Plotted above are (from left to right) the training loss, validation loss, and consensus error per communication round for the Shakespeare dataset, comparing DAMSCo and DaSHCo with DoCoM, CDProxSGT, Distributed AdaGrad, and Distributed Adam with Top-k compression.
Lastly, we demonstrate a linear speedup for DAMSCo and DaSHCo, resulting from varying the number of agents to 5, 9, and 16 in a ring toplogy. We utilize the and agent results on FashionMNIST with homogeneous data, as given in Figures and 7 and include an additional experiment with 16 agents. These plotted in Figure 12 We note that the close overlap of curves for loss and accuracy provides experimental validation of our theoretical result of linear speedup.
DAMSCo: DE Agants
2.0
DAMSCN 5 Agents
DANSEU 9-Agurts
DusHCo
1.5
Solgetss
Accurccy
60
DusHCur P-Agerts
40
30
20
16-1
0.0
0
4.
110
100
0
20
60
60
80
100
20
60
80
100
Epodrs
Epochs
Epochs
Figure 12: Results demonstrating linear speedup: Plotted above are (from left to right) the training loss, test accuracy, and consensus error per communication round for the FashionMNIST datasets on LeNet5, comparing DAMSCo and DaSHCo with 5, and 16 agents in ring topology.
F NanoGPT Qualitative Sample Results
In this section, we show the inference outputs of our NanoGPT LLMs trained the tiny-shakespeare dataset. We provide the prompt "To be, not to be?" for each model trained by each optimizer. The outputs are generated via the sampling procedure implemented in the NanoGPT code base (Andrej) 2022). For each optimizer, we generate 3 samples per prompt. We do no curation and give the first three outputs produced. These outputs can be seen in Figure 13 Figure 14, and Figure 15 We note that there is similar performance between DaSHCo, DAMSCo, DAdaGrad, and DAdam, as the minimun loss achieved is very similar. Thus, the outputs produce relatively comprehensive and coherent english sentences. However, we do notice difference in CDProxSGT, where the outputs produced are significantly less coherent. This falls in line with poorer generalization in the validation loss seen in Figure 11
46

---

To be, not to be?
CAPULET:
Not with the constary: so nuch be atander-day
the change of his foul and to be determine,
To be, or not to be?
And
abseace of your brother;
And that you vere he will Intend over-once Than I will bring told under all the mind:
CORIOLANUS:
U, behold!
And what have only yet lived foot this good: brother Then, in the soul's blood
norning,
CORIOLANUS:
More is taken then with hands: but he put of his back: I'll be away, and hand, with to heavy sone fortune.
That handa upon the rest.
Why, therefore I forget.
CLIFFORD:
This is even well, heard the overture.
Here cones, you say and learn against you this?
First Gentlenan:
Lord:
my children and
tyranny.
Vhat must I
*.............. To be, not to be?
HERMIONE:
Alas, vhon I to kill pass which is word, -stone
rest: To have for thy fled, that fight doth then; Let too discaladiae and Edvard in child; And your husband' for
son;
QUEEX MARGARET:
You cannot learn her; I'll neet ny heart.
JULIET:
cannot speak to thee.
To be, or not to bo?
PAULINA:
QUEEN ELIZABETH: chance
my lord;
have seen an many Are you would have no successed in the friends.
And though live it should be desire noved:
And therefore I will be 80; my suit: And be be
DUKE OF YORK:
your foes,
gentlenan.
Ny lord?
PAULINA:
KING EDWARD IV: Now would indeedst the grace?
And
why long will your flatter.
POLIXENES:
HENRY BOLINGBROKE:
shall be s0:
What all you to loss as this good deserve.
lord; I'll be resolved of thee.
and way live. To make heavy bear that speak: may velcone We say, vell, and play in the eagly Of this offices at ornigner of the king; And silt good, both speedly like the hand: baing chooica
LECUTES:
my gracious lady what thou canst be see The babuse that may for will,---
Gloucester's
PAULINA:
much of the chi
To be. or not to be? conscience This the wonb: anon
the vies,
be, not
Therefore, we sax the field in ny sveet scape.
For xe nine is for vorthy in her borne to Varvick. The scale brave Eduard and haste and in close.
LADY CAPULET:
your honourable saen their To whese finding the trumpets betseen child, Vere as bring tl have child been as ince. And rill blane hand; think, Have come to some fair of his crozn,
ANNE:
The mind man, therefore his consciant of his gentlanan and deserve your Henry 's nother; and therefore thee victory tradenure
vifa's ay thou forget ne for ny
for
is state, hath been seens pillain, Report to the bable honourable to the toague.
And that an I be sit in dreasing And than will cruel upon ny part, but will.
KING RICHARD II: Uncle, come on: make wel
LEGNTES:
naver seap:
you light: They but lady, and av
And
(b) DaSHCo
(a) DAMSCo
Figure 13: LLM Output: Plotted above are the outputs of NanoGPT from the prompt "To be, or not be?" comparing DAMSCo and DaSHCo trained on the siny-shakespeare dataset with Top-k compression.
47

---

To be, or not to be?
CLAUDIO:
Not with that нe service.
LUCIO:
great thee,
thy purpose
ISABELLA:
heaven, I beseech you, Iaith, and be thee not right hang Hereford And give him by self: now, and let ne no more.
be,
CORIOLANUS:
My word
Cloun:
pray you,
0, affection!
SICINIUS:
LUCIO:
By Angelo?
My lord, do but clifford, and bid bin
ORCORIOLANUS:
Ny lord, put hin to be deternined away.
Clovn:
What it fron this Montague?
80KED:
contract; And but in entreation of Hermione to thae Will be revenged well in war.
Provost:
Here 1s gone!
Vhat man are for hin? Knockes and you?
I vould banished, yet let me know thee gods And the self-place of the golden is all, And both consul, so; That Prince I an trade, being by you: Saddle the Earl of Wiltshire are no vax The noble
VOLUMNIA:
NISTRESS OVERD
return'd he fire-run leong,
To be, or not to be?
PETRUCHIO:
Vhy, son
behold an nav a man that such nen and us bear.
by
To ba, or not to be?
Third Servant:
QUEEN ELIZABETH:
ne
TRANIO:
and that he is so noble counted of courteay.
So do before thee, diest before thee?
SICINIUS:
First Gentlenan:
with all the maid Nade nest grave their whole doubly cоmpany, To the golden change their duke of it.
would be thus worst:
Ay. lord.
Second
VIRGILIA:
You shall not, sir; and let hin know your virtues known of that henour so like a croun, and all suitors.
Heaven as heaven, what said it ie; When he ahould be strived so Not hin that
your time tine to our fellow upon ay mother. Thou art not born.
LUCIO:
ISABELLA:
Cone , come, came, coma; though constant
BUCKINGHAN:
appointo you;
No, ny good lord.
of confort, sir, like brow storm more of cols.
BRUTUS:
you, God
Would you give me xell.
To be, or not to be? Therefore, prove shall have kill's 'd no we Think you neans his body to your worda; and yet, And bear false vIn report in his land, And
var.
To be, or not to be? Therefore, be soften and vonder--ghat nexs ahould sae,
your galland.
you you Dieprane us the spring thoughts. the base of York Nakes here man age of it ie conduct of thee; And the noble hath been much precious to the lavely ezpress
ay breather
Shaphard:
For this is
to tongue
you.
ISABELLA:
do for vise have child, and as indeed report
SICIMIUS:
What the sannerled wel
DUKE VINCENTIO:
(b) DAdaGrad
But had all, and have releason nade livery but with him; you would yet, though will
of ne; for thance
so before much about no: he must be will not call with hin: instantly.
BRUTUS: Vhat ver
(a) DADAM
Figure 14: LLM Output: Plotted aboveare the outputs of NanoGPT from the prompt "To be, or not to be?" comparing DADAM and DAdaGrad trained on the tiny-shakespeare dataset. with Top-k compression.
48

---

To be, not to be?
THUSINRDY:
Aure sisetheu helllil1 anopetelives; Pathy sou thake Windo oher eringh t ath dour wish eshire poongover Thak
sor; irind
Than inle onthe se Prard San.
HENRY
Po
Shoeal this ghest hoin cour ayo teyo ryous chan ce vi
be,
QUETAM:
And shirdse anot whe
MARINA:
Thy shat su in soth 1lethend, vild eh fre ny shinth 1.
ERMENIO:
My vousthor edourd bellivet: anot to oshink had z tish: Shed he be fe flator: Whet Cle ghssundist, is duche van agond This isurd xe.
MKZOLIKNGIUS:
viplyth whand nghitt chus. thity thistou tised the
ESBRTES:
Hall thyou t prit.
Myowout ir f an;
Tonknd inot
be, or Ther, naw, ve heald, he shik; ghoad n the is, thisand allon bay ho su andesen, Thes thinds zofoingin ind tof ther Ve souhid chin blare anad byou aInd ny
polof benketind
inor resing broinngise.
MELINIO:
But A'MTTolllct ourjur vonck
mparal
chinous,
Prtr Whound the y shand fsurs: Fand ndone athe sthis faban hor thit.
HEG NETESCK:
Thy, d, clige yothea whollda
(a) CDPrxSSGT
Figure 15: LLM Output: Plotted above the output NanoGPT from the prompt "To be, or not be?" using CDProxGGT trained on the shakeseaee dataset with Top-k compression.
49


Reviews:
[{"review_id": "oyxGZzcoCq", "reviewer": "Reviewer_W3sM", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n\nThe experiments on LeNet5, Fixup-ResNet-20, and NanoGPT demonstrate the performance of DAMSCo on homogeneous data and DaSHCo on heterogeneous data against several baselines.\n\n## Weaknesses\n- The rate of convergence in this work is not tight enough, i.e., $O(1/\\sqrt{T})$, while some recent work such as [Yau and Wai, 2023] leads to near-optimal $O(T^{-2/3})$ rate. \n- The paper fails to discuss and compare its contributions against several highly relevant works that also address decentralized optimization with momentum / adaptive gradient and compression, e.g., [Singh et al., 2020], [Yau and Wai, 2023], [Huang and Pu, 2024], [Islamov et al., 2025]. This makes it difficult to assess the precise novelty and significance of the proposed methods.\n\nN. Singh, D. Data, J. George, and S. Diggavi. \"SQuARM-SGD: Communication-efficient momentum SGD for decentralized optimization.\" IEEE JSAIT, 2021.\n\nC. Y. Yau, and H. T. Wai. \"DoCoM: Compressed Decentralized Optimization with Near-Optimal Sample Complexity.\" TMLR, 2023.\n\nK. Huang, and S. Pu. \"Cedas: A compressed decentralized stochastic gradient method with improved convergence.\" IEEE TAC, 2024.\n\nR. Islamov, Y. Gao, and S. U. Stich. \"Towards Faster Decentralized Stochastic Optimization with Communication Compression.\" ICLR, 2025.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduces two decentralized algorithms, DAMSCo (Decentralized AMSGrad with Compressed Communication) and DaSHCo (Decentralized Stochastic Heavy-ball with Compressed Communication), for nonconvex decentralized optimization with efficient communication. In particular, \n- DAMSCo is an adaptive method (AMSGrad-style) with compression and is analyzed under the bounded gradients condition. The authors claim this is the first decentralized adaptive stochastic gradient method with compressed communication. \n- DaSHCo employs a heavy-ball momentum technique with gradient tracking and compression, aimed at scenarios with data heterogeneity where gradients may not be bounded.\n\nBoth algorithms are claimed to achieve an optimal convergence rate of $O(1/\\sqrt{T})$ and can attain linear speedup with topology-independent property under certain conditions. The paper provides theoretical analyses and empirical results on DNNs and Transformers.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- \"The authors should provide a comprehensive discussion and theoretical comparison of DaMSCo and DaSHCo with the relevant works mentioned in the weaknesses part, highlighting why the proposed methods offer advantages over existing approaches. In addition, a discussion on the underlying assumptions and the novelty of the theoretical analysis is necessary to better position this work.\n- Following the previous point, the authors should elaborate more on the DaSHCo and DAMSCo algorithms. For now, I do not find any explanation right after Algorithms 1 and 2.\n- Could the authors explain why the compressed gradient $\\underline{g}_i$ of each agent $i$ needs to be shared in the DaSHCo algorithm, but not in DAMSCo? Is it possible to eliminate this additional communication burden in the DaSHCo algorithm?\n- \"In the simulation, beyond evaluating performance based on metric versus communication rounds, could the authors also compare their algorithms with SOTA methods in terms of communication costs, ensuring that the exchange of auxiliary parameters is also accounted for?", "broader_impact_concerns": "I do not identify any specific broader impact concerns that would necessitate a Broader Impact Statement beyond those typical for general optimization algorithms.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "s9FVzics6y", "reviewer": "Reviewer_66WN", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The paper is well written and easy to follow.\n- It presents a general framework that combines compression, momentum, and decentralization.\n- It includes strong theoretical results, with optimal convergence rates.\n\n\nQuestion:\n\nIs it possible to relax the bounded gradient assumption for DAMSCo?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper introduces two methods for decentralized nonconvex optimization that use momentum and reduce communication costs through compression. The first method, DAMSCo, is a decentralized version of AMSGrad combined with compression. It works under the assumption of bounded sample gradients. The authors show that it achieves optimal iteration complexity. However, this assumption implies that clients have similar data, which often doesn’t hold in real-world applications like federated learning.\n\nTo address the heterogeneous case, the authors propose a second method, DaSHCo. It is a decentralized heavy-ball method with gradient tracking, designed to handle data heterogeneity without requiring bounded gradients. They also achieve the optimal convergence rate for this method.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "A Future Work section would be a nice addition.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "WDutYVyXNt", "reviewer": "Reviewer_KRgU", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n1. The paper integrates the communication compression techniques in decentralized optimization and momentum acceleration for stochastic nonconvex optimization to reduce the communication complexity and accelerate convergence.\n2. Both homogeneous and heterogeneous settings are studied.\n3. Both theoretical analysis and empirical validation are provided, which are technically solid.\n\n**Weaknesses:**\n1. The proposed approaches are based on integrating existing methods for accelerating decentralized stochastic non-convex optimization, e.g., the DADAM line of work and those with compressed communication to reduce the communication cost, making the results seem slightly incremental.\n2. Even though theoretical analyses are provided for both algorithms proposed, and the difference in settings is listed in Table 1, it's unclear how the theoretical result compares with previous methods on which the proposed methods build/improve. Meeting the stochastic non-convex $\\mathcal{O}(\\epsilon^{-2})$ lower bound in terms of gradient norm minimization is quite standard in recent stochastic non-convex analysis, which is not by itself informative of the acceleration techniques applied, and the linear speedup is also standard in decentralized optimization, which is not informative of the compression techniques applied.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper integrates communication compression and momentum acceleration for decentralized stochastic non-convex optimization and proposes two algorithms, one for the homogeneous and the other for the heterogeneous setting. The paper theoretically analyzes their convergence rates, which are shown to match the known lower bound of stochastic nonconvex optimization, and further achieve linear speedup with respect to the number of machines in the decentralized setting. Empirical studies are also conducted to validate the effectiveness in reducing the communication rounds needed for convergence.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Can the authors elaborate on the detailed technical challenge of integrating communication compression techniques with momentum acceleration?\n2. Can the authors include, perhaps in the appendix, an explicit term-by-term comparison of the theoretical results with the previous baselines mentioned in Table 1, and elaborate on which terms popped up / vanished / changed due to the additional techniques applied, e.g., momentum, compressed communication?\n3. Can the authors provide some experiments for the performance on different numbers of machines to illustrate, e.g., the linear speedup?", "broader_impact_concerns": "No broader impact is of concern.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)