DoCoM: Compressed Decentralized Optimization with Near-Optimal Sample Complexity
Authors: Chung-Yiu Yau
Hoi To Wai
Venue: Accepted by TMLR ()

Abstract: This paper proposes the Doubly Compressed Momentum-assisted stochastic gradient tracking algorithm (DoCoM) for communication-efficient decentralized optimization. The algorithm features two main ingredients to achieve a near-optimal sample complexity while allowing for communication compression. First, the algorithm tracks both the averaged iterate and stochastic gradient using compressed gossiping consensus. Second, a momentum step is incorporated for adaptive variance reduction with the local gradient estimates. We show that DoCoM finds a near-stationary solution at all participating agents satisfying $\mathbb{E}[ \| \nabla f( \theta ) \|^2 ] = {\cal O}( 1 / T^{2/3} )$ in $T$ iterations, where $f(\theta)$ is a smooth (possibly non-convex) objective function. Notice that the proof is achieved via analytically designing a new potential function that tightly tracks the one-iteration progress of DoCoM. As a corollary, our analysis also established the linear convergence of DoCoM to a global optimal solution for objective functions with the Polyak-Łojasiewicz condition. Numerical experiments demonstrate that our algorithm outperforms several state-of-the-art algorithms in practice.

Published in Transactions on Machine Learning Research (07/2023)
DoCoM: Compressed Decentralized Optimization with Near- Optimal Sample Complexity
Chung-Yin Yiu Yau The Chinese University of Hong Kong
cyyau@se. edu.hk
Hoi-To Wai
htwai@se. culkk edu. hk
The Chinese University of Hong Kong
Reviewed on OpenReview: https: // openreview. net/ forun? id- WDehjkl997
Abstract
This paper proposes the Doubly Compressed Momentum-assisee stochastic gradient track- ing algorithm (DoCoM) for conmunication-effiieei decentralized optimization. The algo- rithm features two main ingredients to achiove a near-optimal sample complexity while allowing for communication compression. First, the algorithm tracks both the averaged iterate and stochastic gradient using compressed gossiping consensus. Second, a momen- tum step is incorporated for adaptive variance reduction with the local gradient estimates. We show that DoCoM finds near-stationary solution at all participating agents satislying B|IIV [0) = ( (1/33333 in T iterations, where [() is smooth (possibly non-convex) ob- jective function. Notice that the proof is achieved via analytically designing new potential function that tightly tracks the one-iteration progress of DoCoM. As a corollary, our analysis also established the linear convergence of DoCoM a global optimal solution for objective functions with the Polyal-Lojasieviez condition. Numerical experiments demonstrate that our algorithm outperforms several stale-of-the-art algorithms in practice.
1 Introduction
Decentralized algorithms lackle an optimization problem with inter-connected agents/workers possessing local data without a central server. For many scenarios in large-scale learning, these algorithms improve computational scalability and preserve data privacy. Owing to these reasons, docentralized algorithms have become the critical enabler for sensor networks (Schizas et al., 2007), federated learning (Konečný et. al., 2016; Wang al., 2021), etc.
This paper concentrates on the communication and sampling efficiency issues with decentralized algorithms, which is key bottleneck as decentralized algorithms rely heavily the bandwidth limited inter-agent communication links (Wang et al., 2021). Tnefficiently designed algorithms may lead to significant overhead and slow down to downstream applications. Several approaches have been studied to tame with this issue. The first approach is to consider algorithms that are optimal terms of the number of communication rounds. Scaman et al. (2019); Gorbunov et al. (2019); Uribe al. (2021) studied algorithms with an optimal iteration complexity, Sun & Hong (2019); Sun al. (2020); Lu De Sa (2021) focused on non-convex problems and studied lower bounds on the number of communication rounds needed. We remark that common paradigm to achieve better communication or sampling efficiency requires multiple gradient steps (Nadiradze et al., 2021) multiple consensus steps (Lu & De Sa, 2021).
Perhaps a more direct approach to improve communication efficiency is to apply compression to control bandwidth usages in every communication step of the algorithm. This idea was first studied in the context of distributed optimization where workers communicate with a central server. Many algorithms have been studied with compression strategies such as sparsification (Stich et al., 2018; Alistarh et al., 2018: Wangni al., 2018), quantization (Wen et al., 2017; Alistarh et al., 2017; Bernstein et al., 2018; Reisizadeh et al.,

---

Published in Transactions on Machine Learning Research (07 (07/2023)
Table 1: Comparison of decentralized stochastic optimization algorithms for smooth non-convez problems. Sample complexity is the no. of samples required per agent to obtain e-stationary solution, 0, such that [[)]] < e.. Constants 0, Go, are defined in Assumption 2.2, 2.3, 2.4, Theorem 3.1. Highlighted in red are dominant terms when + 0.
Algorithms
Sample Complexity
Compress
Remarks
DSCD
mlatte)) p²c²
(Lian et al., 2017)
max
x
<² sup -
GNSD
Cu, C1 are not explicitly defined, (Lu al., 2019).
(Lu et al., 2019)
o
cjpT
X
DeTAG
B Blog( + pl
so variance of init. stoc. gradient, B is batch size.
(Lu & De Sa, 2021)
o
max
X
GT-HSGD
(Xin et al., 2021)
O
max
3
plez
Go
ny nاo
CHOCD-SGD
(Koloskova et al., 2020)
max
5pte3
G
G sup Bç (I:(()))) 1,0 Requires batch size
BEER
7
(Zhao et al., 2022)
max
8
0ptc2
CEDAS
o maxx
na²
nGa
Go nn Ei (VA00))
(Huang & Pu, 2023)
pe
pe
DoCoM
O max
6
3
8"ppe"1
GGo
8 pg
1.25
See Theorem 3.1
2020), low-rank approximation (Vogels et al., 2019), etc., often used in combination with error compensation
(Mishchenko et al., 2019; Tang et al., 2019); also see the recent work (Richtárik et al., 2021) for more details on compression strategies.
For decentralized optimization which operates in the absence of central server, the design of compression- enabled algorithms is more challenging. Tang al. (2018a) proposed an extrapolation compression method, Koloskova et al. (2019; 2020) proposed the CHOCD-SGD algorithm which combines decentralized SGD (Lian et al., 2017) with error compensation, Vogels et al. (2020) studied compression with low-rank matrices, Zhao et al. (2022) considered algorithms deploying large batch size. Despite the simplicity and appealing practical performance, algorithms such as CHOCD-SGD suffer from sub-optimal iteration/sami /samll complexity. Their analysis also shows that the performance hinges on a mcasure of data similarity across agents which is not ideal in light of applications such as federated learning with non-i.idd data. We inquire
Can we design compression-enable decentralized algorithm for non-L..dd data with near-optimal sample complerity Does such algorithm work well in practice?
This paper addresses the above questions by incorporating two ingredients in decentralized optimization algorithm: (A) compression with gradient tracking, (B) momentum-based variance reduction. In summary,
We design the Doubly Compressed Momentun--ssiitee Slochaslic Gradient Tracking (DoCoM) algorithm which utilizes two levels of compressions for tackling decentralized stochastic optimization. The design of DoCoM involves a judicious combination of compression with gradient tracking to maximize convergence speed. Our algorithm finds a stationary solution without relying on restrictive conditions such as bounded similarity between data. distributions found in prior compression-enablel algorithms.
We provide a unified convergence analysis for DoCOM. Let f(0) be the overall objective function across the network to be defined in (1), we show that DoCoM finds the averaged iterate 0 in T iterations and communccatios rounds with [[]
O(1/T2/3) for mean square smooth objective functions, and with E(f - f*] = Olog T/T) for objective functions satisfying the Polyak- condition. Note the algorithm takes O(1) sample per iteration. For the latter case, we show that if deterministic gradients are available, DoCaM converges linearly to optimal solution.
We note that the analysis of DoCoM comprises number of deter-dependent error quantities, whose conver- gences are not straightforward to observe due to the nonlinear coupling between them. To this end, our
2

---

Published in Transactions on Machine Learning Research (07/2023)
analysis technique, which can be of independent interest, relies on the construction of tight potential function to yield the desirable (light) bound; see Lemma 3.10.
We empirically evaluate the performance of DoCoM on training linear models and deep learning models using synthetic and real data, non-convex losses.
Note that recently, Zhao et al. (2022) proposed the BEER algorithm for tackling decentralized non-convex optimization with compression and optimal communication complexity. The latter has been achieved using a large batch size per iteration. Huang & Pu (2023) proposed the CEDAS algorithm which achieves an improved transient time for approaching the asymptotic convergence rate as centralized SGD. Yan et al. (2023) proposed the CDProxSGT algorithm to handle composite objective functions (possibly non-smooth) using proximal update. However, under the mean square smoothness assumption considered in this paper, the best known analysís for these algorithms only show a suboptimal sample complexity of O(e-)) as they do not incorporate momentun--asee variance reduction step in DoCoM. We sunmarize the sample complexities for state-of-the-art decentralized algorithms in Table 1. As seen, DoCoM is the only algorithm with compression and an O sample complexity. Such sample complexity matches the complexity lower bound for stochastic first order algorithms (Arjovani et al., 2022), making DoCoM the first compression-enabled algorithm to achieve near-optimal sample complexity under the mean square smoothinss assumption.
Related Works Algorithms for decentralized optimization have been first studied in (Nedic & Ozdaglar, 2009). It has been extended to the stochastic setting (a.k.a. DSGD) in (Ram et al., 2010), and to directed graphs (Tsianos et al., 2012; Assran et al., 2019). Notably, multiple works (Qu & Li, 2017; Di Lorenzo & Scutari, 2016; Shi et al., 2015) proposed a gradient tracking technique where agents communicate local gradients to accelerate convergence.
In stochastic non-convex optimization, Lian et al. (2017) provided a performance analysis of DSGD; Lu et al. (2019) proposed GNSD which combines gradient tracking with stochastic gradient. (also see (Tang et al., 2018b)); Lu & De Sa (2021) proposed DeTAG with optimal et al. (2021) proposed GT-HSGD which extended GNSD with momentun-based variance reduction, and similar algorithms are in (Xin et al., 2020; Zhang et al., 2021b). Note that the momentum-basee variance reduction idea was proposed in (Tran-Dinh et al., 2021; Cutkosky & Orabona, 2019) to achieve optimal sampling complexity for centralized SGD. For a general overview, see (Chang et al., 2020).
tradeoff; Xin
On the other hand, mothods for roducing communication burden in decentralized algorithms have been developed. Aysal et al. (2008); Kashyap el al. (2007); Reisizadeh et al. (2019); Saha et al. (2021) studied quantization for average consensus which is main building block for decentralized algorithms. Notably, recent works (Liu al., 2020; Liao et al., 2021; Song et al., 2021; Zhang et al., 2021a; Song et al., 2021) showed that combining compression with gradient tracking lead to algorithms that achieve linear convergence to an optimal solution. These algorithms bear similar structure to DoCaM, yet are limited to strongly convex objective functions and full batch gradients; see (Kovalev et al., 2021) for the extension to stochastic settings.
Notations I1 II- ||r denote Fuclidean norm, Frobenius norm, respectively. The subscript-less operator
|B|| is total expectation taken over all randomnesses in operand.
2 Problem Setup & Background
Consider a connected, weighted and undirected graph G = == W) with N = (l..... n} representing a set of n agents, E C N x N representing the communication links between agents, and W E Raxa is a symmetric, weighted adjacency matrix. Note that self-loops are included such that {i E & for all i. Our goal is to tackle the following optimization problem:
1 n = n
min BERd
f(0)
f100)
(1)
where f. Rdd > R a continuously differentiable (possibly non-convex) objective function known to the ith agent. The objective function can be expressed as f((0) = Eç=n, [f: (0: ()) such that μ denotes the data distribution available at agent i. We assume that m() for any 0 E Rdd
3

---

Published in Transactions on Machine Learning Research (07/2023)
Throughout this paper, we assume the following conditions on the objective function and the adjacency matrix W: Assumption 2.1. There exists I E 1R, such that for any E EN,, 0,0' E Rd.
E [IV V [ S L 0 8'12.
(2)
Assumption 2.2. The adjacency matrix W E R satisfies: (i) W = 0 if (i. & E; (ii) W1, W 1,, = i,; (iii) let U E R=x(n=1) be a matrix with orthogonal columns satisfying I, - (1/n)11 = UU
there exists p E (0, 1] such that [|U] I 1 - p; (iv) there exists w e (0.2) such that I| - I. S w.
The above conditions are standard. Assumption 2.1 requires the objective function to be mean square smooth. It is also known that there exists W such that Assumption 2.2 is satisfied when G is a connected graph; e.g., by using the intsspolls-Fasstings weight; see (Boyd et al., 2004). For any W which is a weighted adjacency matrix on a connected graph satisfying conditions (i)-(ii), the unique cigenvector of W. It follows that Definition 1), see Appendix D.
max (>2, [An]] and conditions (i)-(iii) are equivalent to (Koloskova al., 2019,
We assume that the gradient of fi can be estimated as (f(; satisfying:
Assumption 2.3. There exists 2 0 such that for any A E R i I,,,,, the gradient estimate (f: with { ~ (4 is unbiased with bounded second order moment, ie.,
[ (e:()) VV)((), (V VS(0)
Again, Assumption 2.3 is standard setling for stochastic optimization.
DSGD and CHOCO-SGD Equipped with Assumption 2.2, 2.3, common practice for lackling (1) in decentralized manner is to utilize W mixing matrix and combine mixing with stochastic gradient descent. To illustrate the basic idea, we observe the decentralized stochastic gradient (DSGD) algorithm (Ram et al., 2010): at iteration 1 2 0 and all i I,..., n2
0++1 = EØ= Wo V where Vî. = VV c))
(4)
such that 17 0 is the step size and V is a shorthand notation for the unbiased stochastic gradient with the data G ~ 14 drawn independently upon fixing Of and satisfying Assumption 2.3. For agent i, the consensus step - Wiy0f can be computed with local average among the neighbors of
Notice that for (4), agents are required to transmit d real numbers on the graph G to their neighbors at every iteration. In practice, the communication links between agents are bandwidth limited. To this end, a remedy to apply compression to messages transmitted on G. Formally, we consider a stochastic compression operator Q: Rd IRd satislying the condition:
Assumption 2.4. For any x E Red, the compressor output ((x) is the random vector ²(x; with & ~ nr such that there exists 8 E (0, 1] satisfying
E || 2(x)) = E [|| [P S (1 6) ||x]|
(5)
The above is general condition on compressors discussed in (Koloskova et al., 2019). It is satisfied by number of designs. For instance, with h < d, the top-k (resp. random-k) sparsifier:
[O(z),, = x; if i Iz: [Q(z)], = otherwise.
(6)
where I, C (1,...,d} d} with |Zz| = k is the set of the coordinates of x with the largest magnitudes (resp. uniformly selected at random), satisfies Assumption 2.4 with 5 = k/d. Other compressors such as random quantization (Wen al., 2017; Alistarh et al., 2017: Stich et al., 2018; Alistarh al., 2018) can also satisfy (5) with re-scaling: see Appendix C.4 and (Koloskova et al., 2019). Note that sending Q(x) in (6) communication channel requires only k real number transmission, achieving k/d compression ratio.
4

---

Published in Transactions on Machine Learning Research (07/2023)
However, applying 2(-) to the consensus step in (4) directly does not lead to convergent algorithm as (i) the compressor is not unbiased, and (ii) the compression error will accumulate with ( - xo. The CHOCO-SGD algorithm (Koloskova et al., 2019) resolves the issue by incorporating an error feedback step: at iteration t,
0 0,11 = 0: + 200) V. 0)
(7)
07+ = 0 - + 7 W. -
(8)
for all i, where 7 > O is the consensus step size, and 7/ Vf. were defined in (4). Instead of directly transmitting compressed version of 0; -n fi a key feature of CHOCO-SGD is that the latter maintains an auxiliary variable 0: that accumulates the compressed difference Q V f 0)). Koloskova et al. (2020) proved that in 7 iterations, CHOCO-SGD finds near-stationary solution of (1); (0 with TE {O....,T - 1}, satisfying ff -1 ""= =
However, drawback of CHOCO-SGD is that its convergence requires the stochastic gradient B|l f [2] to be bounded for any i, 1, see (Koloskova et al., 2019; 2020); or it can be shown that it requires the data similarily supøeR" [[) V I()) is bounded. These conditions may not be valid when the local data are non-i.idd such as in the federated learning setting (Konečný et al., 2016).
3 Proposed DoCoM Algorithm
Taking a closer look at CHOCO-SGD SGD (8) reveals that the algorithm is only able to utilize information from the local gradient estimates f. Re ((( in the local update step. The local update dynamics may thus remain non-stationary even when the solution of is close to a stationary point of (1). The issue is particularly severe when the local objective functions are not similar in the sense that fa(0)) + (.) This motivates us to design an algorithm that will make n-1 Σn Vs available locally.
We propose the Doubly Compressed MomennJnn-assisted Stochastic Gradient Tracking (DoCoM) algorithm. Our algorithm involves two main ingredients: (A) a gradient tracking step with compression where each agent maintains an estimate of n- Σ vf. variance reduction that improves the variance of estimate of Vff using (11) sample per iteration.
at low commuicatiin cost; (B) adaptive momentum-based
Let 17 0 be step size, 8,B E (0, 1], the DoCoM algorithm at iteration t E N reads: for i 1,..., n,
01 = 0: ng! + Σド= W3
0
(9a)
+1 = 0: + 2 (0: - !.r o
(9b)
1+1 8V pvftt + +(1 3) (uf + V - -v}}
(9c)
0 ++1 of + oft1 - of + Ez Wij 10,+1- 1
(9d)
0. of Q (o) + ott1 of g
(9c)
In the above, we draw tt μi at agent: i (or minibatch of samples) as V = v..(0t+ (
V = + such that the stochastic gradients (9c) are formed using the same data batch. To implement (9c) with 9 & 1, agent needs direct access to the data batch c!+1 and the oracle vf((=i )) Readers are referred to Algorithm for details on the initialization and decentralized implementation.
Unlike CHOCO-SGD (8), the local update steps in (9a), (9b) are computed along the direction given by gf. The latter is then updated according to (9d), (9e), which aims at tracking the dynemically updated average gradient estimator of ~ n-' Ey= of with compressed communications given by @(-). In this way, we say that the DoCoM algorithm is doubly compressed. Furthermore, as for ut,, (9c) uses recursive variance reduced estimate to estimate the (exact) gradient of & (fz( (Cutkosky & Orabona, 2019; Tran-Dinh et al., 2021). Together, DoCoM yields a consensus based algorithin where the variance reduced and averaged gradient of n E ut is simultaneously available at each agent.
From an implementation perspective, DoCoM shares the communccatin and computation costs per iteration of the same order CHOCO-SGD at O(d). In fact, only an extra communication step (with compression) is
5

---

Published in Transactions on Machine Learning Research (07/2023)
Algorithm DoCoM Algorithm
1: Input: mixing matrix W: step sizes 7/, 7. 8; initial batch number bu; initial iterate 0 R
2: Initialize 0 = 0 Vi E [n]; 0% = 00 [i, EE
3: Initialize stochastic gradient estimate
of 1/ - V., "P",,, 1 T== pá of = of vi E [n]; Th Oa Viij)E&
4: for in O, T do
5: (UPDATE) Vi E [m] Agent i updates 01 = 0 - -ngi
6: for {i,j] E (notice { E E) do
7: (PRM. GOSSIP) Agent j receive Q(0)+ ( from agent i and update 0 = 0,, + 2(0,+* - -
8: end for
(PRM. ACCREGATE) Vi [n] Agent i updates 0.+1 0 + E jifilee Ww (1y 0,11
10: Draw data batch c μ4 and compute ff++1 f. (0:-1,11 V Vf. (0;:c,1)))
(MOMENTUM) Vi E [m] Agent updates uft1 = BV f++1 + +(1 (1- () + V - -V})
11:
(GRAD, TRACKER) Vi [n]: Agent updates 9i /- = g + +u t -
12:
13:
for {i,j} E (notice {i, E E) do
(G.T. GOSSIP) Agent j receive Q(g," ++ - F(,)) from agent and update 9j.1 = - Q ++ - -
14:
15:
end for
(G.T. AGGREGATE) Vi E [x] Agent updates of = (+ + + WT ( o(.11)
16:
17: end for
18: Output: pick the Tth iterate 0,,, where T uniformly selected from (o...., 1 or T TT
needed for the tracking of n Ei= of and an extra computation step is needed for computing V in (9d),
(9e). A detailed comparison on computational costs is shown in Table 5. As we will show later, the above shortcomings can be compensated by the improved convergence rate of DoCoM.
3.1 Main Results
We show that DoCoM achieves state-of-tho-art convergence rate for smooth problems. Let 0¹ == n Σ'= 0 be the averaged iterate, Go := n -E ||02 | the optimal objective value. We first summarize the convergence results under the mentioned assumptions where (1) is smooth but possibly non-convex:
be the initial expected gradient norm, f == ming f(0") be
Theorem 3.1. Under Assumption 2.1, 2.2, 2.3, 2.4. Suppose that the step sizes satisfies
n S min { Noo v //n y %oor
(10)
where Toor Too are defined in (24). Set 3 (0,1), 3 min
22 42 B}. For any T 1, it holds
5
E
|
1
8
0: 2
f(00) ft
+ C,
2320²
402
n
236I.
2T
nf
1/T
3n
TT
22
t=
1=1
where
1
6
2 6pp
172 4L2n
C, 4
+
(11)
733
p3
25
72 w2
L
141 p²
C 8(1 - T, T.
mr)
96
p
400
We provide the proof of Theorem 3.1 in Section 3.2. Below we discuss its main consequences.

---

Published in Transactions on Machine Learning Research (07/2023)
Near-optimal Iteration/Sample Complexity Setting the step sizes and parameters as 17 277/5
2/8
1/33 TV/a Yoo: 7373. by 22/55 Further, we select the Tth iterate as the output of DoCoM such that is indepen- dently and uniformly selected from {0,... (0....: T 1} [ef. the output of Algorithm I], similar to (Ghadimi & Lan, 2013). For sufficiently large T, it can be shown that
E [IVA@DI - ( (nT)2/33
o²
nGo
o2n0/3 83p0T4/3
(12)
(nT))//3
p2T
where we have used the Lipschitz continuity of Vf(()) [ef. Assumption 2.1] to derive a bound on the gradient of individual iterate 0.T
For any agent i 13...,,,,, the iterate 0. is guaranteed to be 0(1/T**))stationar is the state-of-the-art convergence rate for first order stochastic optimization even in the centralized setting; see (Cutkosky & Orabona, 2019; Tran-Dinh et al., 2021); and it also matches the lower bound in (Arjevani et al., 2022). Our rate is comparable to or faster than a number of decentralized algorithms with or without compression; see Table 1. Further, we remark that Theorem 3.1 does not impose condition on ʃi's similarily supo [I (0) - f(0)ll in which our convergence rate is independent of the data heterogeneity.
(1). Notice that this
Note that the step size configuration in (12) requires n S 1(1 in order to satisty 1) 1 1/oo thereby necossitating 7 = (n??). As an alternative, it is possible to select 7,717 Y Voo, B = 7473. bo n275: which yields
n1/3 T3/3
| =0 [[f((0)) - f*)
g²
Go
σ n//5/3
(13)
T2/3 (nTT)2/3
n1/382
83 pT7/3
In this case satisfying 1) S 7o0 requires n - T and thus T = Q(n) similar to Koloskova et al. (2020). However, as trade-off, gives a worse dependence on s(0") f
Impacts of Network Topology and Compressor Eq. (12) indicates the impacts of network topology (due to p) and compressor (due to 5) vanish as T co. This can be observed by recognizing that the last two terms in (12) are OL/TT) (1/T443)) In Appendix A.9, we demonstrate with a similar set of step sizes, for any 2 Terams 2 (0 (1)),, DoCoM enjoys a matching convergence behavior as centralizod SGD algorithm employing a momentun-based variance reduced gradient estimator with a batch size of n, o.g., (Tran-Dinh et al., 2021). In the latter case, we have n -1 Σー= E [[]T)( ||[] ((o2/(TT2/3)) The constant Trrans is also known as the transient time decentralized algorithm (Pu et al., 2020).
Our result does not require any assumption on the data heterogeneity level nor the boundedness of gradient as in CHOCO-SGD (Koloskova al., 2020) or DSGD (Lian et al., 2017). As hinted before, this is a consequence of gradient tracking. In Appendix B, we provide a separate analysis for the case of B 1 when no momentum is applied in (9c). Interestingly, in the latter case, the convergence rate is only ((1/VT) [ef. (60)), indicating that the momentum term is crucial in accelerating DoCoM
PL Condition Finally, we show that the convergence rate can be improved when the objective function satisfies the Polyak-Lojasievicz (PL) condition:
Assumption 3.2. For any E Rdd it holds that |V](0) 2n( - f*] for some μ > 0.
Notice that the PL condition is satisfied by strongly convex functions as well as number of non-convex functions; Karimi et al. (2016). We obtain:

---

Published in Transactions on Machine Learning Research (07/2023)
Corollary 3.3. Under A Assumption 2.1, 2.2, 2.3, 2.4; 3.2. Suppose that the step size condition (10)
holds and (0, 1). Then, for any t t 1, it holds
2 Bn
8'1 = (1 (1- (A'+ (1
2n
n192
2C,0²
A +
yo
+
(14)
Bn
3B
where 3 == min (np, 3/2], A = f is the expected optimality gap and the constant C, is defined in (11). Notice that vo con be upper bounded with (29).
Setting the step sizes and parameters as log IogT/T, = Yoo: 3 log bo ((1). For sufficiently large T, it can be shown that
( 1 -loog T/T); ΣΣ - - 01oo T/T),
(15)
(16)
see Appendix A.10. Moreover, in the deterministic gradient case with o² O, we can select constant, 9, 17- Then, (14) shows that DoCoM converges linearly to optimal solution such that B[](0")]- (((1-)) We remark that the latter rates match the recent algorithms with compression (Liu el. al., 2020; Liao el. al.,
2021; Song et al., 2021; Kovalev et al., 2021) for strongly convex problems.
3.2 Proof of Theorem 3.1
We preface the proof by defining the following notations for the variables in DoCoM. For any t 2 0:
(01)
(vf)
(gf)T
O'
v =
G =
(0%)
(v
(of)
which are n matricos. Similarly, we define the matrices O¹ G² based on (0: (0) and the matrices
V V F based (v { (VS(()))
The norm of the matrix O UTO i.e., - | I (1/))) 10 measures consensus error of the iterate Oc. We denote G UT G such that ||G measures consensus error of G
Denote the average variables 0r = 1 o' n 11 g' -1 G³ VF n 1 We first make the following obscrvation regarding the d'-update:
Lemma 3.4. Under Assumption 2.1 and the step size condition S 1 ZI
Then, for any t N 0, it holds
TP s(0++) $(()) " [ n
|10 / + + [VF' " 4 117911
(17)
The proof relegated Appendix A.I. The above lemma utilizes just Assumption 2.1 and results a deterministic bound of 1(0++)). We highlight that the bound contains a negative term of the stochastic gradient 4 1|" which is slightly different from the standard bound implied by the descent lemma. Such negative term is crucial for deriving the near-optimal sampling complexity of DoCoM in Theorem 3.1, also see (Cutkosky Orabona, 2019).
Lemma 3.4 shows that controlling || requires bounding || and -V are anticipated to converge to zero, we see that characterizing their convergence results in a set of coupled recursions as follows:
11.. While the latter
Lemma 3.5. Under Assumplion 2.2, 2.4. Then, for any 2 0, il holds
E|||0 s (1 -= + 2 72 R G |ا +
2²
71 0 - - 10]
(18)
8

---

Published in Transactions on Machine Learning Research (07 (07/2023)
Lemma 3.6. Under Assumption 2.1, 2.2, 2.3, 2.4 and let B E [0, 1). Then, for any t 0, it holds
E bt
(19)
$ (1- 3)28
||
2,82
+ +(1
B)² 8T.2
n² 1 p
" GGll + 2 [10"119]
n
SL2
81-8
O¹ G 1 F + ||0:11? 2
+ (1 - (1-
w² 2
E
n2
The proofs are Appendix A.2, A.3. Notice that (18), (19) further depend on the quantities BII
122,, Ell@' - nG - @111..]. - which are handled by the following lemmas:
Lemma 3.7. Under Assumption 2.1, 2.2, 2.3, 2.4 and the step size conditions (01(I-
P
7 S 8w For any t 2 0, it holds
2
251 +
E [| - (1- E [|G
+
E
G²
G
E
[1!!1
(20)
P
P
13L²
||00 -n -
+
5)E
P
+
pm E
||001|"
3 ||v
V
+ 7n 0²00
5
Py
Lemma 3.8.
Under Assumption 2.1, 2.2
2.3, 2.4 and the step size
conditions 1) 62
min
101(1 -m) /1 th), x2 I min 1634(1 1632(1-0)11 8]11 12)(1 11111-211 2/85 pz: 64m }. n S
P7
For ony
12485- L
t 2 0, it holds
nj -
0' G - --12
E -
S
E
(21)
8
F
+
1
50
||G
+ 77
35
G
2
P
F
29
38L²
3
||00 [|]
+ 181?
|10" 2
+
w
E
n
8
P
8
84
n²n1
2
84
32n2n00
+
18
+
E
+
18
+
PY
Pn
5
Lemma 3.9. Under Assumption 2.1, 2.2, (L(1-p1))/44330 For any t 2 0, it holds
2.9, 2.4 and the step size conditions ?
S
S
85 1
[4
12 1
s (1
G² Go
10 72
w2 +
p²
E |||1||?]]
(22)
8
+ 7 122
20
||001|]]
+22
0 G -
F
2 3p²
nE
+
31 8
||
VF
[2]
+ no² 8
32
56
The proofs are in Appendix A.4, A.5, A.6.
Potential Function As we are equipped with the above lemmas, showing the convergence of DoCoM requires tracking the error quantities in unified fashion. This may not be obvious at the first glance due to the coupling between error quantities illustrated in the lemmas. Naturally, one can proceed by defining the sequence of potential function values:
Vt =
r,2
11 +n |
VF' -
1 |
VF
9

---

Published in Transactions on Machine Learning Research (07/2023)
+ tollor - - - + E a G + - -
-6
(23)
F
that comprises of the coupled error quantities, where a, b, > constants to be determined. Our plan is then to study the convergence of vt. However, fully specifying the potential function and to ensure the near-optinal sample complerity for DoCoM require finding the tight conditions on a, b, >> 0, together with the step size conditions, which is not trivial as it requires approximately solving 5 x 5 system of (nonlinear) inequalities; see (46) in the appendix.
In Appendix A.T, we provide a systematic construction for finding the parameters of the tight potential function, which results in the following lemma:
Lemma 3.10. Under Assumption 2.1, 2.2, 2.3, 2.4 and let B E (0, 1). Suppose that the step sizes satisfy:
8
6p
6/(222)
? Σ min
Yoer
4p
64
10w
25952
{V11
v
upp
7 L
7 min
8n
45
240
T/oc.
(24)
Sel the paramelers in the polential function Vi such that
96L pa7 1
x/²
3072
7 48I2
(25)
7(1 71 8p
1 -Y öp
Then, for any t 2 O, it holds
v441 < (1- B)v' + 8² + C ||3911]
(26)
where Co, Cg,B were defined in Theorem 3.1.
The above lemma shows that the potential function V is connected to the noise variance 0² and the gradient norm | The convergence of the latter term is of interest to our theorem. We observe the following consequence.
Equipped with (26) and define A := [f
f
From Lemma 3.4, we can deduce that
A 1+1
2m v nB
+
21 vt +
2n C2
1 z ||
L + n
(27)
nz
+ (11 1-1 1
as in (10) shows that the last term in the r.h.s of the above can be upper bounded by zero. Summing up both sides of (27) from t = 0 to t = T - yiclds
Setting 17 S
Bu SCg
EE
L + -
0
< S
21
v
2n/T
(28)
n3
Furthermore, with the initialization, choice of b, e and the step size 7 S Joo, il can be shown that
20 118L2n
vo
(272(1-9) Go7
(29)
bo
Dividing (28) by v/ and observing |10 (|(I - (1/m)11 (1/m)11T)@<111 concludes the proof.
Proof of Corollary 3.3 Applying the PL condition of Assumption 3.2 to the inequality (17) shows
A ++1 < (1 - A + +n
L2
10 +
| |F
2B [
10

---

Published in Transactions on Machine Learning Research (07 2022))
$ (1 nu) +
Lv E
(30)
n
4
Combining with Lemma 3.10 shows that
[+1_ +
Bn
21
4++1 - (1 1 3)
0² +
Bn
21
vs
+
n132
Bn
2C 2C
(3n
(3 2C,
(0, - -/) ;)) ||0"1"]
(31)
where we used 1 - +
1-3+
3n u
< 1 - min 3/23) Set n7² -
On and telescope the relation concludes the proof. 42g
2n n
4 Numerical Experiments
Setup We run the decentralized optimization algorithms on a 40 threads ITt) Xeon(R) Gold 6148 CPU @ 2.40GHz server with MPI-enabled PyTorch and evaluate the performance of trained models on a Tesla K80 GPU server. To simulate heterogeneous data distribution, each agent has disjoint set of training samples, while we evaluate each trained model on all training/testtigg data.
Hyperparameter Tuning For all algorithms we choose the learning rate from 00.1, and fix the regularization parameter as x= 10-1 [cf. (32)]- For compressed algorithms, we implement the top-k compressor and random quantizer, and we tune the consensus step size y starting from the theoretical value of 6. For DeTAG, we adopt the parameters from (Lu & De Sa, 2021). For DoCoM and GT-HSGD, we choose the best momentum parameter 3 in {0.0001, 0.001, 0.01, 0.1, 0.5, 0.9} and fix the initial batch number as bo.: = my- We choose the batch sizes such that all algorithms spend the same amount of computation on stochastic gradient per iteration, except for BEER which requires large batch size according to (Zhao et al., 2022). The tuned parameters and additional numerical results can be found in Appendix C.
DoCoM Top-
CHOCO-SGD Top-k(10%
BEER Top-k15%)
GNSD
GT-HSGD
DoCoM Quant.(4-bits)
CHOCO-SGD Quant.(8-bits)
BEER Rand. Quant. (4-bits)
Consensus gap
consencus gap
10
Loos
Loss
10-1
10
10-1
10
10-4
2.0
Bits Transmitted 1c9
Bits Transmitted 1e10
Samples Drawn 1e5
Samples Drawn
Figure 1: Experiments on Synthetic Data with Linear Model. Worst-agent's train loss value and consensus gap against the number of bits transmitted (left) and total number of samples drawn for gradient approximation (right).
Synthotic Data with Lincar Model Consider a set of synthetic data generated with the 1eaf bench- marking framework (Caldas et al., 2019) which provides features from agent-dependent distributions. The task is to train a linear classifier for a set of d = 1000-dimensional features with m = 1443 samples parti- tioned into n 25 non-i.i.d. portions, each held by an agent that is connected to the others on ring graph with uniform edge weights. Each feature vector is labeled into one of 5 classes. Altogether, the local dataset for the ith agent is given by {ay, (C) (C D" where m = Lisl m4, st E R1000 denotes the jth feature, and 1e E 135 is the label such that fG =1 if the jth feature has label & E (1.....5..
To train a linear classifier 0 = (O , 0s) E R5000 we consider (1) with the following objective function that models modified logistic regression problem with sigmoid loss and & regularization:
S((0)
(C, (2f 0w)) 1012
(32)
mi
where p(z) (1+6-2)- and À 1 the regularization parameter. The function f((-) not convex, and we estimate its gradient by sampling mini-batch of data.
11

---

Published in Transactions on Machine Learning Research (07/2023)
DoCaM Top-k(5%) 16 batch
DoCoM Tog-k(5%) 64 batch
DoCoM Top-k(5%) 256 batch
CHOCO-SGD Top-k(10%) 256 batch
BEER Top k(5%) 16 batch
BEER Top k(5%) 64 batch
BEER Top k(5%) 256 batch
BEER Top. k(5%) 1024 batch
Train Gradient Norm
Train Accuracy
Consensus gap
0.75
10
10
Loss
10
0.50
10
0.25
10
10
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
Bits Transmitted 1e9
Bits Transmitted
Bits Transmitted1e9
Bits Transmitted 1e9
Figure 2: Experiments MNIST Data with Feed-forward Network. Worst-agent's train loss values, train accuracy, consensus gap and train gradient norm against the number of bits transmitted.
DoCoM Top k(5%)
BEER Top 9(5%)
CHOCO-SGD SGD (op-k(10%
GNSD
GT HSGD
0.9
Trinn Gradient Norm
Test Accuracy
Consensus gap
100
0.8
10a
Loss
10-1
10a
0.7
10-2
10-2
0.6
10a
104
10
10
10*
105
10a
10
10
10:
10
10
MBytes Transmitted
MBytes Transmitted
MBytes Transmitted
MBytes
Transmitted
Figure 3: Experiments on FEMNIST Data with LeNet-5. Worst-agent's train loss values, test accu- racy, consensus gap and train gradient against the number of MBytes transmitted.
Figure 1 compares the worst agent's loss values max; (0f) and consensus gap 16 6'1l against the communication and gradient computation costs. For compressed algorithms that require communication of two compressed variables (DoCoM and BEER), we use half the amount of bits/retained non-zero after sparsification with (6) to make a fair comparison with CHOCO-SGD. DoCoM achieves the fastest convergence in terms of the communication cost (number of bits transmitted) and shows fast convergence on par with uncompressed algorithms in terms of gradient computation cost, when used with 4-bit. random quantizer. Comparing among compressed algorithms, DoCoM and BEER find solutions with the lower consensus gap (10 times lower than CHOCO-SGD) and DoCoM stands out to be more sample efficient than all existing compressed approaches. Observe that DoCoM outperforms CHOCD-SGD and BEER due to the use of gradient tracking and variance reduction.
MNIST Data with Feed-forward Network We consider training 1 hidden layer (with 100 neurons) feed-forward neural network with sigmoid activation function on the MNIST dataset. The samples are partitioned into n = 10 agents where each agent only gets 1 class of samples. These agents are arranged according to a ring topology with uniform edge weights. We tackle (1) with f() taken as the cross entropy loss function of the local dataset and an & regularization is applied with the parameter of X 10-4.
Figure 2 compares the worst-agent's 's loss function, max; f(0), and other metrics in the same manner against the communication cost (i.e., bits transmitted). We observe that DoCoM already achieved nearly the best performance in loss and accuracy using just small batch size of 16. On the other hand, CHOCO-SGD suffered from slower convergence due to the heterogeneity nature of data under the unshuffled MNIST setup, and the performance of BEER is sensitive to the choice of batch sizes. Notice that in this experiment, we selected a compression ratio k/d of 0.05 for DoCoM and BEER, and 0.1 for CHOCO-SGD for a fair comparison.
FEMNIST Data with LeNet-5 Lastly, we consider training the LeNet-5 (with d = 60850 parameters) neural network on the FEMNIST dataset. The dataset contains m = 805263 samples of 28 x 28 hand-written character images, cach belonging to one of the 62 classes. The samples are partitioned into n 36 agents according to the groups specified in (Caldas al., 2019). These agents are arranged according to ring topology with uniform edge weights. We scale the learning rate by 0.1 at the (4,40, 40)-thhh thousand
12

---

Published in Transactions on Machine Learning Research (07/2023)
iteration and momentum B by 0.1 at the 40, thousand iteration for DoCoM; see Table 4 in the appendix for the hyperparameters values.
Denote the LeNet-5 classifier g(z;0) _28x22 + R which is parameterized by the weights vector E R We optimize (1) with cross-entropy loss and lg regularization such that fi is defined over the local dataset (afy 3m of (image, class) pairs by
1
ma
(p)(B( k= exp(1e(1)) 0)))) + 1111..
A
1:(0)
log
(33)
my
where z/) E 28228 vj E {1....,62) 62).
Figure 3 compares the performance of benchmarked algorithms against the communication cost. We observe that DoCoM achieves similar performance as CHOCO-SCD and BEER, while demonstrating a slightly better performance torms of the consensus gap. We speculate that the performance gap has narrowed due to the highly non-smooth nature of LeNet-5.
5 Conclusions
We have proposed the DoCoM algorithm for communication efficient decentralized learning and shown that the algorithm achieves a state-of-the-art ( sampling complexity. Future works include investigating the effect of reducing the frequency of (compressed) communicaiinn. For example, through considering asynchronous updates with possibly time varying random graph.
References
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. Qsgd: Communication- efficient sgd via gradient quantization and encoding. Advances in Neural Information Processing Systems, 30:1709 1720, 2017.
Dan Alistarh, Torsten Hoefler, Mikael Johansson, Sarit Kririrat, Nikola Konstantinov, and Cedric Renggli. The convergence of sparsified gradient methods. Advances in Neural Information Processing Systems $1, pp. 5973 5983, 2018
Yossi Arjevani, Yair Carmon, John C Duchi, Dylan J Foster, Nathan Srebro, and Blake Woodworth. Lower bounds for non-convex stochastic optimization. Mathematical Programmingg pp. 1 50, 2022.
Mahmoud Assran, Nicolas Loizou, Nicolas Ballas, and Mike Rabbat. Stochastic gradient push for distributed deep learning. International Conference on Machine Learning, pp. 344 353. PMLR, 2019.
Tuncer Can Aysal, Mark J Coates, and Michael G Rabbat. Distributed average consensus with dithered quantization. IEEE Transactions on Signal Processing, 56(10):4905-49) 4918, 2008.
Jeremy Bernstein, Yu-Xiang Wang, Kamyar Avizzadenesheli, and Animashree Anandkumar. signsgd: Com- pressed optimisation for non-convex problems. In International Conference on Machine Learning, pp. 560-569. PMLR, 2018.
Stephen Boyd, Persi Diaconis, and Lin Xiao. Fastest mixing markov chain on graph. SIAM review, 46(4): 667-689, 2004.
Sebastian Caldas, Sai Meher Karthik Duddu, Peter Wu, Tian Li, Jakub Konečný, H. Brendan McMahan, Virginia Smith, and Ameet Talwalkar. Leaf: A benchmark for federated settings. In NeurIPS Workshop on Federated Learning for Data Privacy and Confidentialityy 2019.
Tsung-Hup Hui Chang, Mingyi Hong, Hoi-To Wai, Xinwei Zhang, and Songtao Lu. Distributed learning in the nonconvex world: From batch data to streaming and beyond. IEEE Signal Processing Magazine, 37(3): 26 06-38, 2020.
13

---

Published in Transactions on Machine Learning Research (07/2023)
Ashok Cutkosky and Francesco Orabona. Momentum-based variance reduction in non-convex sgd. Advances Wn neural informalion processing systems, 32, 2019.
Paolo Di Lorenzo and Gesualdo Scutari. Next: In-network nonconvex optimization. IEEE Transactions on Signal and Information. Processing over Networks, 2(2):120-136, 2016.
Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4:)2341 2368, 2013.
Eduard Gorbunov, Darina Dvinskikh, and Alexander Gasnikov. Optimal decentralized distributed algorithms for stochastic convex optimization. arXiv preprint arXiv:1911.0796; 2019.
Kun Huang and Shi Pu. Cedas: A compressed decentralized stochastic gradient method with improved convergence. arXiv preprint ar Xrx::22001.055 05877, 2023.
Hamed Karimi, Julie Nutini, and Mark Schmidt. Lincar convergence of gradient and proximal-gradient methods under the polyak-lojasiewicr condition. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 795 811. Springer, 2016.
Akshay Kashyap, Tamer Başar, and Rayadurgam Srikant. Quantized consensus. Automatica, 43(7):1192- 1203, 2007.
Anastasia Koloskova, Sebastian Stich, and Martin Jaggi. Decentralized stochastic optimization and gossip algorithms with compressed communication. In International Conference on Machine Learning, pp. 3478- 3487. PMLR, 2019.
Anastasia Koloskova, Tao Lin, Sebastian U Stich, and Martin Jaggi. Decentralized deep learning with arbitrary communication compression. In ICLR, 2020.
Jakub Konečný, Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. arXio preprint arXiv:1610.05.: 05,92, 2016.
Dmitry Kovalev, Anastasia Koloskova, Martin Jaggi, Peter Richtarik, and Sebastian Stich. A linearly con- vergent algorithm for docentralized optimization: Sending less bits for free! In International Conference on Artificial Intelligence and Stalistics, pp. 4087-4095. PMLR, 2021.
Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsich, Wei Zhang, and Ji Liu. Can decentralized algorithms outperform centralized algorithms? case study for decentralized parallel stochastic gradient descent. In Newral Information Processing Systems, pp. 5336-5346, 2017.
Yiwei Liao, Zhuorui Li, Kun Huang, and Shi Pu. Compressed gradient tracking methods for decentralized optimization with linear convergence. arXiv preprint arXiv:2103. 13748, 2021.
Xiaorui Liu, Yao Li, Rongrong Wang, Jiliang Tang, and Ming Yan. Linear convergent docentralized opti-
mization with compression. In International Conference on Leurningg Representations, 2020.
Songtao Lu, Xinwei Zhang, Haoran Sun, and Mingyi Hong. Gnsd: a gradient-tracking based nonconvex stochastic algorithm for decentralized optimization. In 2019 IEEE Data Science Workshop (DSW), pp. 315-321, 2019.
Yucheng Lu and Christopher De Sa. Optimal complexity in decentralized training. In Proceedings of the 38th International Conference on Machine Learning, pp. 7111-7123. PMLR, 2021.
Konstantin Mishchenko, Eduard Gorbunov, Martin Takáë, and Peter Richtárik. Distributed learning with compressed gradient differences. arXie preprint arXiv:1901.0920 2019.
Giorgi Nadiradze, Amirmojtaba Sabour, Peter Davies, Shigang Li, and Dan Alistarh. Asynchronous decen- tralized sgd with quantized and local updates. Advances in Neural Information Processing Systems, 34: 6842, 2021.
14

---

Published in Transactions on Machine Learning Research (07/2023)
Angelia, Nedic and Asuman Ozdaglar. Distributed subgradient methods for multi-agent optimization. 1EEE Transactions on Aulomalic Control, 54(1):48- 61, 2009.
Shi Pu, Alex Olshevsky, and Ioannis Ch Paschalidis. Asymptotic network independence in distributed stochastic optimization for machine learning: Examining distributed and centralized stochastic gradient descent. IEEE signal processing magazine, 37(3):114-122, 2020.
Guannan Qu and Na Li. Harnessing smoothness to accelerate distributed optimization. IEEE Transactions on Control of Network Systems, 5(3):1245-1260, 2017.
S Sundhar Ram, Angelia Nedié, and Venugopal V Veeravalli. Distributed stochastic subgradient projection algorithms for convex optimization. Journal of optimization theory and applications, 147 (3):3)) 545, 2010.
Amirhossein Reisizadeh, Aryan Mokhtari, Hamed Hassani, and Ramtin Pedarsani. An exact quantized decentralized gradient descent algorithm. IEEE Transactions Signal Processing, 67119):49444447, 2019.
Amirhosscin Reisizadch, Aryan Mokhtari, Hamed Hassani, Ali Jadbabaic, and Ramtin Pedarsani. Fed- paq: A communication--ffiteene federated learning method with periodic averaging and quantization. In International Conference on Artificial Intelligence and Statistics, pp. 2021-2033 PML.R 2020.
Peter Richtárik, Igor Sokolov, and Ilyas Fatkhullin. Ef21 A new, simpler, theoretically better, and practically faster error feedback. In Advances in Neural Information Processing Systems, 2021.
Rajarshi Saha, Stefano Rini, Milind Rao, and Andrea J Goldsmith. Decentralized optimization over noisy, rate-constrained networks: Achieving consensus by communicating differences. IEEE Journal on Selected Areas in Communications, 40(2):4494477, 2021.
Kevin Scaman, Francis Bach, Sébastien Bubeck, Yin Lee, and Laurent Massoulié. Optimal convergence rates for convex distributed optimization in networks. Journal of Machine Learning Research, 20:1 31, 2019.
Toannis D Schizas, Alejandro Ribeiro, and Georgios B Giannakis. Consensus in ad hoc wsns with noisy links- partt i: Distributed estimation of deterministic signals. IEEE Transactions on Signal Processing, 56(1):350 114350036,,440 2007.
Wei Shi, Qing Ling, Gang Wu, and Wotao Yin. Extra: An exact first-order algorithm for decentralized consensus optimization. SIAM Journal on Optimization, 25(2):944-966, 2015.
Zhuoqing Song, Lei Shi, Shi Pu, and Ming Yan. Compressed gradient tracking for decentralized optimization over general directed networks. arXiv preprint 1xXi::2006.07243, 2021.
Sebastian U Stich, Jean -aptiste Cordonnier, and Martin Jaggi. Sparsified sgd with memory. Advances in Newral Information Processing Systems, 31:4447-44 4458, 2018.
Haoran Sun and Mingyi Hong. Distributed non-convex first-order optimization and information processing: Lower complexity bounds and rate optimal algorithms. IEEE Transactions on Signal processing, 67 (7(2)): 5912-5928, 2019.
Haoran Sun, Songtao Lu, and Mingyi Hong. Improving the sample and communication complexity for de- centralized non-convex optimization: Joint gradient estimation and tracking. In International Conference on Machine Learning, pp. 9217-9228. PMLR, 2020.
Hanlin Tang, Shaoduo Gan, Ce Zhang, Tong Zhang, and Ji Liu. Communication compression for decentral- ized training. Advances in Neural Information Processing Systems, 31:7652-766 2018a.
Hanlin Tang, Xiangru Lian, Ming Yan, Ce Zhang, and Ji Liu. d²: Decentralized training over docentralized data. In International Conference on Machine Learning, pp. 4848 4856. PMLR, 2018b.
Hanlin Tang, Chen Yu, Xiangru Lian, Tong Zhang, and Liu. Doublesquoeze: Parallel stochastic gradi- ent descent with double-pass compennaped compression. In International Conference on Machine Learning, pp. 6155 6165.666..66 PMLR, 2019.
15

---

Published in Transactions on Machine Learning Research (07/2023)
Quoc Tran-Dinh, Nhan H Pham, Dzung T Phan, and Lam M Nguyen. A hybrid stochastic optimization framework for composite nonconvex optimization. Mathemalical Programmingg, pp- 1-67, 2021.
Konstantinos I Tsianos, Sean Lawlor, and Michael G Rabbat. Push-sum distributed dual averaging for convex optimization. In 2012 feee 51st feee conference on decision and control (ede), pp. 5453 5458. IEEE, 2012.
César A Uribe, Soomin Lee, Alexander Gasnikov, and Angelia Nedić. A dual approach for optimal algorithms in distributed optimization over networks. Optimization Methods and Software, 36(1):171 210, 2021.
Thijs Vogels, Sai Praneeth Karimireddy, and Martin Jaggi. Powersgd: Practical low-rank gradient compres- sion for distributed optimization. Advances in Neural Information Processing Systems, 0114259-14268 2019.
Thijs Vogels, Sai Praneeth Karimireddy, and Martin Jaggi. Practical low-rank communication compression decentralized deep learning. In Advances in Neural Information Processing Systems, volume 33, pp. 14171 14181, 2020.
Jianyu Wang et al. A field guide to federated optimization. arXiv preprint arXiv:2107.06917 2021.
Jianqiao Wangni, Jialei Wang, Ji Liu, and Tong Zhang. Gradient sparsification for communication-effee distributed optimization. Advances in Newral Information Processing Systems, 31:1299-1300 2018.
Wei Wen, Cong Xu, Feng Yan, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Terngrad: Ternary gradients to reduce communication in distributed deep learning. Advances in neural information processing systems, 30, 2017.
Ran Xin, Usman A Khan, and Soummya Kar. Variance-reduced decentralized stochastic optimization with accelerated convergence. IEEE Transactions on Signal Processing, 68:6255 6271, 2020.
Ran Xin, Usman A Khan, and Soummya Kar. hybrid varianco-reduced method for decentralized stochastic non-convex optimization. In ICML, 2021.
Yonggui Yan, Jie Chen, Pun-Yu Chen, Xiaodong Cui, Songtao Lu, and Yangyang Xu. Compressed decen- tralized proximal stochastic gradient method for nonconvex composite problems with heterogeneous data. arXiv preprint Xim:22302. 14252, 2023.
Jiaqi Zhang, Keyou You, and Lihua Xie. Innovation compression for commuicatiion-effeiennt distributed optimization with lincar convergence. arXiv preprint 2rXiv:2105.06697, 2021a.
Xin Zhang, Jia Liu, Zhengyuan Zhu, and Elizabeth S Bentley. Gt-storm: Taming sample, communication, and memory complexities in decentralized non-convex learning. In Mobilooe 2021b.
Haoyu Zhao, Boyue Li, Zhize Li, Peter Richtárik, and Yuejie Chi. Beer: Fast o(l/t) rate for decentralized nonconvex optimization with commmication compression. arXiv preprint arXiv:2201.1332 2022.
A
Missing Proofs from Section 3.2
Using the matrix notations defined in the preface of Sontion 3.2, we observe that DoCoM (9) can be expressed conveniently as
@ O - +WW + 1
6++1 +'' n -²)
Q(z1)T
y*+1
= 3VF++ +(1- 3)( V VF' .((X)
X Raxd
G++1 =G' + V1+1 - -W
Q(xx)
G+1 = = + 2(G++ -V
The above simplified expression of the algorithm will be useful for subsequent analysis.
16

---

Published in Transactions on Machine Learning Research (07 2023)
A.1 Proof of Lemma 3.4 Using the L-smoothness of [ef. Assumption 2.1], we obtain:
L 10+1-091
)(
S f(0") + (Vf(0') Ø++1 - 8¹) + 2
f(00) - 7 (Vf(O) 0²) + 2n²
2 1|g¹13
f(0') 7 (11=1) + f 1 -166' - v)(0))²) + Ln²
2 ||0011
2
3
& (()) 3 |16 - 11 2 1 / - v)(0))1
2
S <0()>
4 | 7/ |V )1² +1 (15- - VV + |T | v)(0)(²)
7
S s(0) - " ||'0 2 2/ 2 || + 3 - VF | + 1,21
- -
(34)
where (a) is due to 1 zτ. We remark that (x v) = xT denotes the inner product between the vectors 2, V.
Note that by construction and the initialization of = g.. we have g' = oe for any t 2 O; see (9d). Applying
the upper bound
||0 - = =1(c (1/n)11 = - $10511
(35)
leads to Lemma 3.4.
A.2 Proof of Lemma 3.5
Observe that
0 = -T -C'
+ (W )
= =UT ''' G + +( -1) (1) (0 2 - n - -0) 0r + + + 0 - -
-0)- = =UT { (W W - (0' - n + + 11) 21000 n - - (0' -
(36)
Notice that it holds UT + ( - 1)) = (W and ||U
< - py:
Taking the Frobenius norm on (36) and the conditional expectation Ee[T] on the randomness in DoCoM up to the 7th iteration:
E. [ |7
(37)
n)uu (0' - = = WW
-n') + u (w- - 1) 1 - (0' - n -6)]
< (1+a)] (1 + DW
- -
+ +(1+a-1)E, | (w - |0(0'- G - - - (0' - n -
<(1+a)
- ( | - G
+(1+0 U (w- - - 0 - n - Qt) - (0' - n - -6>11² |
( (1+ -1++)[1-m))100 , +1+ - 8) 1 n 6/1/²
+ $(1+ -0))))(1-0)(11+ +1)) || + -1))) )) |
17

---

Published in Transactions on Machine Learning Research (07 2202)
+ + a (1 - -1- n - -
(8)
- (1 - (1- | _ +
2
n² | F و5n |0 n 1
-
F
where (a) is due to |W- -0-1] I|| S ت and (b) is due to the choices a 1-py, B = = The proof is completed.
A.3 Proof of Lemma 3.6
Defining V = V
F = n 1 FV we get
ह VF = - + (1 - ()- Vλ) VF
(38)
= (1 - (b - VF - -VVFF V
+ (1 3) (VF - VF (VF't) - vQlt)))
Tt follows that
S (1 8)
| 3" - -V'V |
+ + 4 +1 7
Aデ. (VFL+1 vo++1 >/ ||]
+ 2(1 2E
VF
$ (1 - 8)2B
|| 8' - V
+ +2320²
+ +2(1 3)2 I n?
119
n
Furthermore, applying Lemma A.1 leads to
VF
S (1- (1-8)²E 11 VF' 27
+ 2,300
E
n
+ 8(1
3)²
2
(1211
23
[| ||
n2
L2
+ +nn(1 3)²
1?
2(1
1 ||0' [
(39)
n12
L2
+ +8(1 - -))
nT
w
2222 2
|0:01 2
Pl
1,2
- - -6011/
+ 4(1 - 5)2 ne w
8)E 2
0 - G/
This concludes our proof for the stated lemma.
Bound on the Matrix Form Observe that
pe1 vpt+1 = v + (1 (1- - VF -
(40)
(1 (00v'--FF - Vftti)
+ +11 -F' - (VF'+ -VFFII-Í7tH)
Taking the full expectation yields
E B||
[[]]]
< -3 || - VF [2]]
+ 2(1 =232n00
L [|0 00
18

---

Published in Transactions on Machine Learning Research (07/202) 2022)
Again, applying Lemma A.1 leads to
E ||| - V V| [[]]]
(1-3))EL) || 1 - [ + n03"no²
+8(1 - 17 (1- P3) ||G* 1P
4n(1 339131/(11 17)
|
(41)
+8(1 3)T123377
|
4(1 31 8)
0 - n/ - -6:1/-
This concludes our proof.
A.4 Proof of Lemma 3.7
We begin by observing the update for Gt+1 as:
Gt+1 = U G + v - v' WW ( - 1
U G'+1441 - (W -W- -1)(0'+ (0'+ + v44 -
V- 1---vi1 -(-)))
-U [11 + (W IJ) (G' + +
+ (w- - 1//210 + - -²) (G' + 11-11-'-677 [3]
pit
The above implies that
Eg c [F]
S + (1) ||G. + +U -
[3)12]]
+ +11+ (1 1) -11 | + v v²-6" -6" [3]
Fr
- 2, - 11 (1) | + +1 a /| - volli]]
$
+0 5)R - + +||ett1 [|
07 Taking ag I--7 a1 =
T gives
E2
G
[2] F S $11-
( ) |G + 200² 10- - 6o1
2
2
(1 + ?² E, |||etl= - --1 pr
+ my
Taking the full expectation and applying Lemma. A.2 give
E || < (1 (1- 2 [ G + 2 E 0² - 0
1
P
2 (1 (1+ (LL'E ' 1 + +35' -F
+ 3n 02)
+ my
Furthermore, applying Lemma A.1 yields
E G c 2 < 1 - PY + 241 + (1+))1+))111111111000))))))))))) (P)))))))))))))))))))))))))))))) E [|G r
2 E +
c - 2
2
PY
p
F
24L (1 + ?
2 E |
PY
19

---

Published in Transactions on Machine Learning Research (07 (07/2023)
12 + + 50n2(1 - -6)B 00 n - - 21
PY 12L (1 + PWP)
(1 - p2 E [1001
PY 6(1 + PWP
|| |F
PY
6 (1 + 72²²) 3²
mn
The step size condition
" n
Py
7 8w
(42)
10 07) /
implies that
E
||ot111
[1]]]
$ <11
P7)
E
|
| +
2
E
G² - Gr 1
+
25
E
|10%11
4
P
+ Y
13L²
w²(1 - 8)
00' -n/ - 0.
+7 pm
E
[|
p
F
5
7 mn
B E 1|1e - [
+ 7n
8²0²
py
This concludes our proof.
A.5 Proof of Lemma 3.8
Observe that
E | n/ Q/+1 0041 2
Ee | n - -(0' 2(0' - - - -
F.
=E, ||0001 n7GHt1 - (0' - -n")= + (0'
Q - n - - 1|]
nn
1 -6')
Q(0'-
< (1 + 5) R
|100- - 06 - 11( |3>
+ +(1 + 20 d) |00 ,00 - -612 r
$ 2( + 2
2 3 E
|| - 06 + 217 + 2 B.
|| |-|
+(1 -
5 / l100 - n - -601
(43)
Note that as
G G² = G++ - 1( + 1(/ht1)- - -G'1 + +1
UG UG + 1(g - =g
we obtain the bound
E || 21 F < LE [I + 2E || [|2]] + 2E [|c::]]]
With Lemma A.2, we substitute back into (43) and obtain
E. | -,,h--n----- - G |=]
( 2 E
0 - n -----/--'" -6:1(
+ +472(1 + - TE
2
[|c 11 +
[F]
+ + 2 3) L2 + 1}E ||0 1
0' +
2
E
||v
- vr|]1]]
+ 6,3212 + 2
8 )no
(44)
20

---

Published in Transactions on Machine Learning Research (07 2202)
We further apply Lemma A.1 to obtain
1 n - G 1/]] S (1 - 1-22) 1B 00 - -7 601]]] + 4n + - || 1| + |_
E
+ +6,317(11
5) ]B ||Ve /F |0] (1
2
2 mno 8(1 + / ) 1, 1)0²(1 وン) [||:11]]
2
+ +8(1 + 2
(3n 122 + +1) ||0 | F
+ 4(1 + ) L2 + +)mm7 m3) |1010
8
2 + 411 + 5 (3n L2 +1) -)
0 n 0 21
(45)
F]
Using the step size condition:
5
16 5)(1 3, (1) + 2/0)
and we recall that 17 s 1/(D), the upper bound in (45) can be simplified as
E - 1 n - - -041
S (1
8 E
0
1o''-nGs n - 6.
+
12
8 " [|c.
-
18 331p²E ||
-F
F
+ 8
18
17 noo² + 8
41
T [|G] 12]
+ 3
29
[|0:1|]]
+
15
n' E [1577]]
The above bound can be combined with Lemma 3.7 and 7p S 1 to give
E ||o- n - 6
[-]
1
8
+
n
156 2,222 5)
E
0'
nG
-6:1
1
4
p
50
E
|
+ 7
24
E
G²
1m1
cel
||3
8p
F
+
29
w2y²
+
300T.202 p??
E
|10:
2
1817
n
| |0'1"]]
p
F
5
+
82n 18 +
84
E
1
||:]]
+
18 +
84
1022102
PY
8
p7
8
Taking x2² S 1248(1 (88(1-6)-330 م3 and 7
8²p
simplifics the bound into
8
E | - 6 6 1
(1-
6)
0 n - 6.0
2
E
F
8
F
50
+ 1,² 3
||ct E+
2
1/²
EE
[|]]]
E
P
F
+
29
2 +
381, 30m
27
E [|19916]]
+
181/
E
11 11
8
18 +
84
8212²
E
[|ve
|
+
18
84
1222
Mn
8
/7
8
This concludes the proof.
A.6 Proof of Lemma 3.9
We begin by observing the following recursion for G Ó::
- -6+11 = =G* + + - V + (n(W - Q)++
=>(W - I)( + -441+ - vt)
+ - 1) 1) |Q(G* + v++1 - yy -C' - - G7]
21

---

Published in Transactions on Machine Learning Research (07 2202)
This implics
E
| al1ott-- -
- |p]
1 (1 + an)(1 +1)))++)))() 8) (1 + a1)
1 03 (1+ |
- v-1
+ 2(1 " ||c/!|2 +
Taking ag = 2. a1 = 6 and the step size condition
8
8
8w
6w
give
[ G++1]] -0tt1- 12]
1 <(1-
0) 8
E 6+ + 10
E [|0:1|]]]
E
(1 _ [ + )) + 2 (1 + ))) || v
8
8
E G² Gu [112]] + 10 2w2
E ||
+ 10(1
E || 11]
Applying Lemma A.2 and Lemma A.1 gives
||o++1 -|++11)
|r s 1
8 5)
E
G
2
+ 10
E ||c|||]]] p
+ [B]] (
+ +no²)
30(1 + )
||0
6'
5
5
E
G - 6'
[]]
+
10
E [
8
F
8
120 + 2
2 |105512
8
60(1
L2
||05 10--n6- n/ - -611
wP - علاة (1-
8
60(1
>>
2
1n72 - pT)²E [|,54|9]
5
31
32
E
V
|F] + no²)
Using the step size condition from (42), i.e. 222 - p-) above to
+
2222
and y
< 85
simplifies the
100
E 10tt1-
G [+1 S 1 888
E
|| 0² - 6-113]
10
w2
+
0²)
E
[|c:
|
8
+ 7 2 122
E
[10.112]
6
E
0
G
C. pp)
+ 7 3p²
nE
||~:||]
31
||
-
Vp
[2]]
31
32n02
50
8
This concludes our proof.
A.7 Proof of Lemma 3.10
Below, we illustrate how to find a set of tight conditions for the free parameters a, b, > 0. Combining
Lemma 3.5, 3.6, 3.7, 3.9, 3.8 and (41) yields
E La 1
+ |++1 vF "I
+a -
+ (0411 + tellot+1 -n - -6/11
22

---

Published in Transactions on Machine Learning Research (07/2023)
<
PY
16 (1 - 2)2 + ay
25
by
1225
+ c(2 29022
+ np pbbir) )
E L2 [[:11
2 n
P
5
8L2
+ (1 - 8) nB
84 VF
+ (11 31- + a.32 7n
+ 1132
31n
+
/
E ||Ve [
MY
5
MY
+ 2 2T.
1 16 (1 - (1 - p3) + =
b
10
E ||c:1|1]
+a
+
+
4
PY
8
a
8
a 25
||o' - -cylp
1
+
E
8
P
b
p
1
8
+ 5
1 1.702
18
(1 33 6)
a 131.
w2
(1
8)
+
=
b 2
600.7522
E
- n
0
1/
8
P
en
6
4 8 +
7
31
84 / no²
a3
+B8
1 +
p
6
P7
p3)² + 5
p
+ by 3p²
cn
18 E
[|b*1|]]]
5
58
8
Our goal is to find conditions on step sizes and the choices of a, b, c such that
P7 16
25
12252
2 29
38
2 (1 3)
a0y
+ by
+ =((2
+
1j
S
P
8
8L2
p
8
7n
31n
84
(1
3)2 + aB²
1,32
c32 10
Mn 1
S (1 3)
mi
PY 1
11²
2 2T2
+
166
1
3) - 13) +
b 2 10
p
r 2
50
S
1
MY
a
py
a
8
a
8
8
1
8 a 2
+
7
+
"
c
2
3
< 1
87
8 b
p
p
8 1 L2
7 - 33 -1 5)
18
8)+ + a - w² (1
13L²
b 2
600 w2
87
+ - P
+
8)
_
1 1
8
8
To this end, with the step size condition
pn
Y S min
(S1)
4p" 64(1 - ,) 8(1 - ()2 5)p
the above set of inequalities can be guaranteed if a, b, c satisfy
96L
{ (1 11-80 8)
2
p2g2" 2 Sas S min
(46)
21,3n
13(1
8) 600
7 32
172 48
1/2
281
8
(1- 3)5
6p
max
" 1- 7 p5
C 1 ? pō
<
S min
3p(a2
2
+
8)
30p7'
93,8n
2928-
(47)
7 2
5pI.
28T
1- B
6
?
S c < min
(48)
1 1-y 6p
1392 25px'
Bnp2
3n
84)²
1 1824
p7
Notice that the step size conditions:
v2 S min (1-3)7² 0² 72p²
7²p²
(S2)
2016,3n I 624(1 - 8)122' 57600 1
guarantees the existence of a which satisfies (46). In particular, we take a
961.2
p²q= 2/2
At the same time, with the step size conditions:
(1- (1-3)
2
29pw
2
8 p2
n < min
(S3)
Bn
(18
+
84 0y
)LL
38612
7
6681 1 1651
23

---

Published in Transactions on Machine Learning Research (07/2023)
guarantee the existence of which satisfies (48). In particular, we take -
182"=² 6p
This simplifies
1-7
(47) into
112
3072
n
2304
112
25I.²
6
(1
3)8
8p
max
(1(1 6p*
(1 (1-
82p²
< b I min
5p(w² + )
30p7
933n
y928
(49)
Combining with the step size conditions:
x² < min
2w² +
>
8
(1 3)7 5p(w² + 5)
( +
e"
8
127.2
Bn
18612
58562 2 1,2
72 min
p²p²
48
(S4)
7
7680 ( + ) 3 p
guarantees the existence of which satisfies (49). Finally, we take b = 7(1-) 8p2
n²
30725² 1.2
Using the upper bound on 7²/ - 7) from (S4) and the above choices of a, b, yield:
v++1 S ( 1 --mm min
PY 8y
672L2n
n72 166 pp' 8
172 4L'n
8 8 3 v³ + 82
4
+
o²
7/3
p
?
25
72 w
+ 7² 8(1 - 31 - pr)² + Ltn pn
(96
141 p²
]
E [|39
96
+
400 w2)
Furthermore, we observe that the above steps require step size conditions (S1), (S2), (S3), (S4). Together with the requirements in Lemma 3.5, 3.6, 3.7, 3.9, 3.8, we need
2 S min {
(1-3)²3 p²
1-7
464
29p
20022 + x) (1 B) 5p(w²
2016,n T
Bn
(18
84
HpL
3851.2
121.2
8n
18612
M
5x² + g
22p²
p2
p2g²
8²pp
5856 L2
624(1- - 8)L2 57600
100L2(1
(101111p)0))) P1) + +~
1248
V5
pn
n
Y S min
(1 8(1 - 31 - 8)p² 88 (1- 0) 1 2/0) 4p" 64(1 - 3)
22
82p2
82 p2
46
min
66816w4
7680 2w²2 + (²)
3w02p
Taking the restriction that w [1,2], the above can be simplified and implied by
pn
8 8pv1- 0/(8w²)
7 S min
Ap 64
105"
25952
Yoor
min {
1-1 3
p²
n I L
(V
=:100.
1700.
8n 45
240
where we have used the upper bound S 7, This concludes the proof.
85 to remove the self-dependence on 1 - for the constraints on
A.8
Auxilliary Lemmas
Lemma A.1. Under Assumption 2.2, 2.4. For any t 2 0, it holds
E |
-
-
11]
< 41 (1- - 31
G _ + 2nr - (1) ||0" [-]
(50)
+ 2 ||00:11
+ 2 - 5) ||00 - - -6'1
24

---

Published in Transactions on Machine Learning Research (07 2022)
Proof. We observe that:
| - > - 116
- = =|[1 (W -))() + (W - 1J@t + + 1) [e n/" - - (0' -n - -
s <2|1(1 + <( - -1))
- -
+ +2//(W - -0(0-- n - 66 (0' - n - -61)
$ n/ 111 - I)) + 7 |[W - -n + (I( - I)((-0') >( n)or
+ 232 2(0' - no - -²) (0' n - -69) |
(11)
Observe that leads to
-1) (W-
7(W - 1)0") = -W--(W(--UUC ><W - I)0*), the above
E, |100t1-0911 2 - -7- 1 + -277(1
-my) |. + 412 (W - 1)0
- -
- -o
- 6/1
(52)
Notice that
E || = |
+ G =E |UUTU G 1|10/)111
| [|0
(53)
By combining (52), (53), and the fact ([w - 1) < 3551100 110 we have
E
|| e01
< 4n - pT) || + 2nn (1 - p ||011
+ 2 [
+ 2 - 5)E 00 n - -6113²
This concludes the proof.
Lemma A.2. Under Assumplion 2.1, 2.3. For any 1. 2 0, it holds
| V-[2]] $37.2 1|00t2--0000 0-122] + 3,8 [|ve 1y'-VP'11 + 3n
Proof. Observe that
F*+ -== - + -1 () VF V
VF*) 3(V VF
It holds that
B
1 - v-[ 3T.2 || -001
+ 3
- vF'1 + +3,32 |
< SLL'R ||0 - (1(
+ 3
1 1=
+ +3 0
This concludes the proof.
25

---

Published in Transactions on Machine Learning Research (07 (07/2023) /023)
A.9 Transient Time of DoCoM
We follow a similar argument as in (12). Particularly, consider setting the step sizes and parameters
3 = O 7473 ), ( 1: ) = Yoo bo = /3T1//3). Then for sufficiently large T, we obtain
| - (
T2/3 (44
o² +
Go 82p
o²
+ 83,07133)
(54)
nT2233
The transient time can be calculated by bounding T such that the second term dominates over the last two terms. We get
n G n
})
Ttrans =
max
7 p1d
81.5p5
56
(55)
n ouggpp
Taking < guarantees that Trrans (2(
A.10 Sublinear bound of ( under PL Condition
We consider setting 3 = 77 = log T)(T)) 7 = Yoo, by = Notice that for a sufficiently large T, these step sizes will satisfy (10). Furthermore, setting = T, the upper bound in (14) given by:
(1-bo-7
log 7 T
T Ao A
1181.2
(log
))
o log T
20 + p2 7) Go
(56)
T
n
HT
We observe that
log T
1 (1- T
S e
log
T
Thus the expression in (56) can be further upper bounded by Ollog T /T). This implies (16).
B Convergence Analysis of DoCoM with B =
This section provides the convergence analysis of (9) for the special case when the momentum parameter is f = 1, i.., there is no momentum applied. Observe that the DoCoM algorithm can be simplified as
r++ = O - G + +> 1)
0++1 @ + - - -
G++1 G* + -f+++1
-I G++1 = -G* + Q(G + - G³)
where we have eliminated the use of V since V (1/n)11Tee. Te..
v st for any 2 0. Additionally, we define O
In such setting, the convergence analysis has to follow different path from the case of 3 1. We begin by analyzing the 1-iteration progress with Lemma B. Under Assumplion 2.1, 2.2, 2.3, and the step size salisfies nj S 1/(AA). Then, for any 2 0, it holds
? Ea f(0)) 4 |
3L
11!
LIPa²
(57)
4n
2n
The proof is relegated to Appendix B.1. Notice that the above lemma departs from Lemma 3.4 as it results in a bound that depends only on the consensus error. Our next endeavor is to bound |@ which can conveniently controlled by Lemma 3.5 as quoted below:
e|| s T
2 n Elll [|[[c||[]+ + r
W² 7E
T - - -
(58)
Moreover,
26

---

Published in Transactions on Machine Learning Research (07 (07/2023)
Lemma B.2. Under Assumption 2.1, 2.2, 2.3, 2.4. Suppose the step size satisfies n $
81(1-07)/147224
S 8w
Then, for any 2 0, the consensus error of G is bounded as follows:
E
G++1 0
- (1 (1- +) E ||G.!P +
2w
G²
G
+ 7
4
18L
0 F
+7 p
9L2 Be
||00 - nG ../
+
pn
E
+
7n
+
PY
0²
FF
4
py
8
The proof is relegated to Appendix B.2. We also bound the subsequent terms by Lemma B.3. Under Assumplion 2.1, 2.2, 2.9, 2.4. Suppose the slep size salisfies 14
mn
6 S 8w
Then, for any 2 0, it holds:
E
-
- Ge+1
2 F
+ 1 1 d E G -41
10
w2
+
0²)
E
[
8
+ +?² 48
(0² + 72L
E |
+
40L
E
|100
-n0
-cul- c01
6
2 5p²
nE
V
|1
5
(p-9²
+
7n
o².
48
Lemma B.4. Under
Assumplion 2.1, 2.2,
2.3,
2.4.
Suppose the slep size satisfies ?
Then, for any 2 0, holds
46 (1-8)(1+1) " 22)142/))
E 0 - -na - 6t+1 2
3 (1
8 E
0'
G - 6. - 2
+
12 5
E
||
|1|]]
+ 8 1
24
+
38
E
|G/ p]
+
26
(1
-333) |1 + + +
6
Furthermore, if the step size satisfies 1j²r 1
8²p
then
864 L2
E
|00 n/a²11 - G++1 12 |
1
E
0² G
- -6
F
8
+ 17
50
E
|lc%
2
+ 11
3w
EE'
C - 1
17
29L4
1
w
+
26
2
E [10:1101
8
29n
E
|
2
240²
(1+
4n のm)
The proofs are relegated to Appendix B.3, B.4, respectively. Combining the above lemmas and optimizing the bounds for step sizes lead to Lemma B.5. Under Assumption 2.1, 2.2, 2.3, 2.4 and the step size conditions
1 min
Pn
p²y
p² 8881--
n 5 L
4' 881811110 m/) 1
2252
105m
13035
1/02
6
Vo
/53/2
8/(80)
p
6/
82p
7 min
n S
(''8'' 8w Aw 0)
(1
+ 2/8)
882
2 0²
123
864.²L²
L
Define the constants:
NMM
1- 7
192
2(1 - 7)
p3g
320
p
15W2
NNM
C
1
12
PY
- 7
256
p
+
58w 27
p8?
27

---

Published in Transactions on Machine Learning Research (07 (07/2023 /022)
Then, for any t 2 O, it holds
E @ | + a || I|
f - -G + +
- - - 2 |
min o, )) E | +a
a + +b|lo - -o1 + tcll0t -n - -6'
8
+ 1) non + tn
M nE ||
where 189/ ,ー b 15360 2)2 P p0)8(177)
24 pb(1-7)
The proof is relegated to Appendix B.5.
To simplify notations, we let 7MM == min (in 0/8. Using I||
G111 = no² and Lemma B.5 imply that
E
| [ S a (1 - (1-))M,)) no² +1² Σ (1 (1- ,NM (CN + ONyNE [|][(*)
==0
C
CNMiino0 NNL
+ nPN
Σ (1 NM y) |
(59)
where the inequality is due to the fact that CNM,,
172
2
We now observe that (57) implies
1(0%) -(00))
+ +1² 7000
CNM 3Ln
4T
E
SE
T
2n
1 +
2pNM
31,2
1
T-1
+ 17
CM
NM 41
Σ
T
1=0 s=0
f(00) -((AT)
02
3Ln
E
17
1
wND
T
2n
+ 17 CM
3L2
T-2
E
[||
4D
T
Therefore, under the additional step size condition ns
holds
V
8 E E [1] & n
[(00) - f(0²)
+ 102L.
1 CNM 3Im
(60)
T
2pNMa
Setting v = ((IvVT) shows the expected convergence rate of 1 IT= E
==
O(IVT). We
remark that similar result to Corollary 3.3 can be established under the PL condition Assumption 3.2.
B.1 Proof of Lemma B.1
Using the L-smoothness of f, we obtain:
f(0)+1) < f(0)) + (Vf(0)) | g++1 -0) +
2 10+t1-80
= - - (VS(O)) 1 ('--((0') + L1²²
|
(61)
2
Taking the conditional expectation on the inner product:
1n -VS(0)))))) -
28

---

Published in Transactions on Machine Learning Research (07/2023)
12 1
= =- (1(
ViS(0)) VI(0)
11² +
(V):(0)) (((
2
n
|/(00)|
"
Σ
+
2
2n
$ 2/2
"
|)(00))
+
1/
Σ
L 100 - -011
2
2n
i=1
+ n2
7 |/(00)] 1|
||0 - -01l
2
2n
where we denote é = 1(0))=== , 10
Putting back into (61) yields
Lnj²
nT.
Blf(( s f(0)) " |
2 +
E,
||'0|
+
||00 - -
(62)
2
2n
Observe that as E, 11
=
=
E, 1 G²
| we have
10
E2 1 G
1 =
V VI.(0%
= =B,
Σ V1(00
- Σ
+
Σ
1=1
12
< <n0² +2
Σ
(V) - {\(00)
+2
Σ V)i(0))
i=1
<no² + 2nI. |0' - -01 F + 2n |
(63)
Putting back into (62), and assuming that -(2 - -nn)= S 1 + 1) S 4
Lnd
+ nL2 2n
Bx S s(0') - 2/2 ||][0>> +
2n (no² + +2nL2 1222100 8'1|² + 2n² || |
110r 6'/|
= - - nn - L || + (Lin² L371)
||0 - 0¹1 + Lii²0²
-6'1"
2n
2n
# S 100) 31 ||ا00)| + 3L'1
Liiz0²
|0' -0'1(² 0²1
F + 2n
(64)
4n
The proof is completed.
B.2 Proof of Lemma B.2
We preface the proof by stating two lemmas that will be instrumental to the proof of Lemma B.2. Their proofs can be found in the later part of this subsection.
Lemma B.6. Under Assumption 2.3. For any t 2 0, it holds:
E
rr < -||0PHI-V>+1?
21
(16/tt-10113 + 3no
(65)
Lemma B.T. Under Assumption 2.1, 2.2, 2.3, 2.4. For any 12 0, it holds
E, [[0]]] < 4n (1- p1 1| + 4 ( 23) + =هوه) ||o 12 + 210 -8)
G 600 2
+ 2n -
(1 370 + 4m |
(66)
29

---

Published in Transactions on Machine Learning Research (07/2023)
Proof of Lemma B.2. We begin by observing the update for Go!l! as:
_o! I + V - VF" + - 1
=UT VV+ vス + ( -I((' + +2 + + - -())
-UT ( Neww-Ija -I)
-VF"
+ (W- (WUTWW-1 - 1) [e(G' 2 - --))
- (G' + vftt - -c9
The above implies that
E, ||o. [|]]
s (1+ - "E) 0 + UJ (V - -V,)
+ ))-))) - -d), || 0 + v - vf - 6// rr
$ (1 + ao) "3 (+an)||Goll (1 + a p A [/]
F + + + (01+-01)200(1111 8) o² 6e 2 + 1
Taking ag
07 1-pp> 01 =
0
T gives
2552 Es [| [|?]] S (1-2) ||c.|:2 + P
| 02 1
P py (1+ Ba | - -V [ ]
2
Taking the full expectation and applying Lemma B.6 give
E ||o [2]]
< (1 (1-27 E || + 2 E
||a-
|
FF]
2 2
(1 + 200) (3no² + +2L'E 119-t1-69910
+ My
Furthermore, applying Lemma B.7 yields
E o
F] S 1 1-
py
+ 2 16L (22))
E |||G!| 2 F
+
2 E
|||
c
6² 2
2
M
Fr
16L + 2
2 - p7)3 + 2 IE | |
Py
81 + ?
w² 22 SEE ||0| ./ - 6611]]]
mn
16 + 2
(1 - p E [
Py
6
8 7711 + 21 m))² 0²
(1 + 727)
n p7
py
Using the step size condition
1n
n 81(1 pr) /1 2:
7 8w
(67)
implies that
E
2 S
|| -1
E
|
2 E +Λ
|| 0 - G* [2
+
0
18L2
E
|
[
p
F
4
P
30

---

Published in Transactions on Machine Learning Research (07/2023)
-1. +y a² - 5) 0² - n/ -601(²]
+ pm
||
7n
mi
+
+
4
py
8
This concludes our proof.
B.2.1 Proofs for the Auxilliary Lemmas
Proof of Lemma B.6 Observe that:
E f - = -
( - (v - + -
+ 2E ( - -4 - vF (
Notice that
E ((VTtt - -VP-- vFF
= -B -B (<v vF (aeti-vi9
As such,
E - Via |3]
-
s 3no + 2 || - -
This concludes the proof.
Proof of Lemma B.7 Observe that:
10t11 - 0² = > n)++1
= =|(1 + -D) +>( - 1)0" + + - 1) - -0) (0'0))00--00)))))))
n/
< <2|l(1 + <W +
=2// - 2000 - -0) - -0'-
- G - -6)] 2
22 17 |1(T + -WW- > 1/ + + + + ()(-)")) ( ((w--))'))
+ 200g2 0(0' - 76 - -²) - (0' - G - -61| ?
(68)
Observe that ((1 7(W ())(-)() 7(W 1)0">
- ((++(W--)) 1 I)e"), the above
leads to
E, |||00| - 001 x 207
- p3) ||00|12 + 2112(1 - m\) | |
+ 42² (W - 1)
-2 -00000n+ G - 6
+200g2 6) 0
(69)
Notice that using (63), we obtain
E, || 2 F
E, [|((L/m)]1 + UU "G' E, | o I1(1/))1
< G 2 21. |0:11= + 2n \ ||| +02
(70)
By combining (69), (70), and the fact II( - 1)0*1 < w2 ||0:1| we have
E, -01]]] < (1) || 2 41 L² ||o5|l
4nd (1- (1- || )(
+1 - pr) + 4327 |0:12-- + 25 20 6) ||0- n7 - -6012-
This concludes the proof.
31

---

Published in Transactions on Machine Learning Research (07 2202)
B.3 Proof of Lemma B.3
We begin by observing the following recursion for G 6::
G - G =G + V - Vー + (+ -I) - 1
= - =>(WWDIC'++
p+t V -
+ + - 1) 1) e(6' + vf+t
v -
This implies
G² GO 2
+ + (1+ a1)) | - 1001--v6 -
E
+ + (1) 5) (1 (1
+ 01 ||اا||/ +
- - ?
Taking og 4. an 8 and the step size condition
8
8
8
6
give
E 1
8)
E G² -6-
2
10
[
$
1
+
E
8
F
8
(1 + 8
4
4 |3]
(1 4
)) + +27200(1
1
0 E
G² Ge
2
+
ww2
[|c:1|]]]
+ 10 + 7202)
V - Frt
F
6
F.
Applying Lemma B.6 and Lemma B.7 gives
E 10t216
1
8)
E
G²
- 8
[|]]
+
10
E
[| [2]
+
30(1 + 2202)
no²
FF]
8
8
5
20(1
L2
|10
E
8
1
8
E
0² 6-1(3]
+
10
8 (7"0² -
-1 (. + 7w0)
m3)7 E [|cBll]]
80(1
2 1?
(1² 22 p3)² 2 1/ |11:0l|
40(1 2 I.2
22n211 - 5)m
00 G - -011
8
80(1 + )
(1 33
|7]
8
10(1 + +22
( - 07)20² + +3no²)
Using the step size condition from (67), i.e., 1/² [22 07) (1 -²w²)) <
2²2 64
simplifies the above to
E c - G++1
|2] F
<
(1- 0 5 B
1
[ o E+ [/]
+
10
2
w +
p²
E [|c
2
8
+ 2 5
(0² + 72 TE
|10%
2
+ +
2 2
||00 1/0" -c01 1
-
48
F
5
F
+ 2 5p2
1222
nL
|
+ 3
+ 7n 0²
45"
8
This concludes our proof.
32

---

Published in Transactions on Machine Learning Research (07 202))
B.4 Proof of Lemma B.4
Observe that
F 0 1+ -
6142 2
=t ||0 - - (Ó' + 2 - - -9)) |/ 1r
||00|1 n1 - -6' n/²)) + +00 n - - Q n 61) //2
E,
F
(1
3 E
2
||6 - 0e nn [3)l +(1 5) 5) |00 n - -6112
S 21 + 2
2
E
|| 011 21 + 2 8 B | - G-|l2]] - (1 2 1100 n - -6013
8,
(71)
We can bound the second term as
E - = L [ + 2E || + 2 ||::
Observe that
E 1 (V
[V
<E 1 (V -V
-2E |
[ - |FS|!"]
+ 2 2 | | |F
< 3no + 2nL'E -
Substituting back into (71) yiclds
|0+1 1 - -
21
$ (1 2 E 00 - n/6 - -61
8
2 -) || + ||c:|]]]
+ +472(1 (1+
8
21 + 2 310011 1)B -110t1-00011
60 + 2 ?n
(72)
We further apply Lemma B.7 to obtain
E |00+| n 6 2 | s 5
8 I 0r n/
- n -6:110]] 4
8 ))10
2
||tt11/ + ||G:11]]]
2
+60 + 30²² + 41 11) +
2 3 8) ||00 G A 1/2
FF
+8 +8(1+ + 2
8 17 p0 PB
||c L² 1|!9||/ + || + 02//2
+ +8(1 2 E
||001
(73)
Using the step size condition:
5
12
16 - 0) + 222
and we recall that 17 S 1/(4L), the upper bound in (73) can be simplified
E |1 - - -
5( - 8
(1-2211
00 [
1/6¹
+
12 +
||c.
F
F
+ 8
24
0/00=
~"
38
E
|||
2
+
26
o
E 1m22 L2
10:1 + +n |1²
This concludes the proof of the first part.
33

---

Published in Transactions on Machine Learning Research (07/2023)
The above bound can be combined with Lemma B.2 and pp I to give
E - n -
61+1 12]
s 1 4
108 L2 ?
E 1
n
- 611
pd
+ 1j
50
E
||c|||?
+ +1²²
24w²
E
G
1
2
8
11 L2
3 + 267,
216
26 w
E
| |
P
2912
24
4n
+
n
|
1
6
p7
Taking 1p s 8615-12
8p
simplifies the bound into
0 n 6
6 8
0 n
-
1
E
m
50
||
+ 1 E
||0' O+
+ 17
E
5r
11 6
2914
1
~0
+
26
way?
|10:
29n
[|>
240²
(1 (1+ 4ni
17
E
+ 1/
5
8
pr)
This concludes the proof.
B.5 Proof of Lemma B.5
Let a, b, c > 0 be some constants to be determined later, combining Lemma 3.5, B.2, B.3, B.4 yields
E
1
|| F
+
1| +
Gr-1 - || + + - nGG+ -cl100+-1n/44 10241-6:10 10+h1
b|
<(1
17
+
azy
P
18L2
by
2 2
(0² + 45T.2 + 29 + p
gnp + 200222)) E. [[lsaal]]
2
4
+o
pr
1
n
b
10
1 p²) +
r
50
[|
4
a
py
a
82
a
2
3
G² O+ |p
+b
1
E
+
2
a
W
b 202
||00
G
- 0. 2
8
p
8
+ 8
a
5
+
en
15
+
+ by
2p²
+ on
2
29 8
nE ||]}(0)1
pY
pdy
8
We wish to find conditions on the step sizes and a, b, c such that
MY
+ aay
1
by2
92T
58T/A
1/
+ 2832g2
51
2
P
8
p
1
PY
1
2
b 10
(802
+
p²)
+
n"
2 50
< 1
m
4
a
py
a
82
6
8
8
a
2
2
3
87
1
+
<1
8
8
1
2
a
2
2 2
87
1
< 1
8
8
34

---

Published in Transactions on Machine Learning Research (07 (273))
The above set of inequalities can be guaranteed if a, b, satisfy
48
p²
21 S a
S
(74)
p2g2"
228
7
32
112
48w²
pó
1/2
82
max
7 pō
C
1
pō
S
min
1104L2
73 5p(60² + p2)
(75)
7 2A
7.
22
72 960L2
pô7
8
max
1 p5
0
p5
b 1-7
pd
Scs min
12(
58
122 + 26W2
25p7
(76)
P
Notice that the step size condition:
n² - 10944L202
guarantees the existence of a which satisfies (76) into
(74). In particular, we take a pr This simplifies (75).
4
32
p
n
8²
17 max
22n e
< b
min
pô(1 - 7)
y 1104L2 78
5p(dw² + p²)
24
432
pōS
5
pô(l -7)
max
Y p²g
L211²
S c S min
12( 12(58L4# 172 + 2602222) 25p7
Observing that as 172 < simplification:
p¹n
0²n²
and we impose the extra condition c S
32 pay
We obtain the
109441202
43272
1536
pd
8²
1/² SbS min
p387(1 - -7)
11041252
733
5p 5p(2 + p2]
24
pôy
8
32
pō(1 77) max {7, 40L < min
12(
58L 1/2 + 26w2x2)
25
pP-y
Again, the condition on b is feasible
p182(1--) 77)
22
p²8a
1536 1104 12544'
1-7
7680 (ow>" + p²)
and we take 15360 (7((117)) ? Note that as 7 s 8/80, the bound on y can be implied by:
1200 8/83) < 7680 (8 + p2)
Observe that with this choice of b and the step size condition, we have 40L2?²b S 7. Finally, the condition on e is simplified to
24 po(1 7) y S S min
pōy
32 25pr''
12(
58L
112
26w2222
pPy
P
The above condition is feasible if
22
48
8²
1²8²
p282
1085
1- < min
1/ <
3
600
14976w
14976
16704LA4
24 and we take -o(1-7))
The above choice of a, b, ensures that
E || + +a || 1p. + -
-
- -
-
6
+
35

---

Published in Transactions on Machine Learning Research (07/2023)
< 1 min
p }
R)
||0:1|= + a |
F +b
G
+
+ n
- 6
8'
F
FF
+ 1 1-7
192n
2(1 - 7)
320W²
+ p28dy
1502
0²12² + 1-7
12n
7 +
256
+
58
1
||
p2ng3
p2d2y
Py
poa
The proof is completed.
36

---

Published in Transactions on Machine Learning Research (07 (02)))
C
Additional Numerical Results
In the first two sections provide additional plots and the tuned hyper-parameterr of our simulation. In the last section we describe the implementation details of our simulation.
C.1 Synthetic Dataset
This dataset is generated from the benchmark framework leaf (Caldas et al., 2019). The number of data points possessed by each agent is different. In particular, we have the distribution (m,)es which follows (470, 403, 91, 84, 79, 51, 51, 38, 31, 25, 24, 19, 14, 10, 9, 6, 6, 5, 5, 4, 4, 4, 4, 3, 3/. Table 2 provides the tuned parameters used for the experiment in Figure 1.
Table 2: Tuned hyper- parameters for linear model on synthetic dataset.
Learning
Consensus
Momentum param.
Algorithms
Batch size
rate f
step size y
GNSD
0.005
DeTAG (R = 1)
0.005
0.1
4
GT-HSGD
0.01
0.01
2
CHOCO-SGD (Top-k 10%)
0.01
0.5
4
CHOCD-SGD (Random Quant. 8bits)
0.01
0.9
4
BEER (Top-k 5%)
0.01
0.16
100
BEER (Ramdon Quant. 4bits)
0.01
0.5
100
DoCoM (Top-k 5%)
0.01
0.2
0.01
2
DoCoM (Random Quant. 4bits)
0.01
0.6
0.01
In Figure 4, we provide additional numerical results on the trajectories of gradient norm, training/testing accuracy of the algorithms. Similar comparisons between DoCoM and existing algorithms are observed. No- tably, we see that DoCoM achieves the best gradient stationary solution in limited communication budget and recovers the same level of gradient stationary solution as the uncompressod GT-HSGD the last itcration. Also, we observe that DoCoM is the first achieve the best accuracy with the least network cost.
GNSD
DeTAG
Consensus gap
100
DoCoM Top_ k(5%)
Loss
DoCoM Rand Quantid-Nits
CHOCO-SGD k110%)
10
CHOCO SGD Rand Quant( bits)
10-2
BEER Top k(%%)
Rand Quant(4-bits)
10
1000
2000
3000
4000
2000
4000 6000
8000 10000
Iterations
Iterations
Train Gradient Norm
10
Train Gradient Norm
10
Train Gradient Norm
101
10-1
10-1
10-1
1
2500 5000 7500 Iterations
10000
2
4
Bits Transmitted 1e10
Samples Drawn
le5
Figure 4: Additional Results on Synthetic Data and Lincar Model. Loss and consensus gap against iterations, and worst-agent's gradient norm, training/ /esting accuracy.
37

---

Published in Transactions on Machine Learning Research (07 (07/2023) 2023)
C.2 1 Layer Feed-forward Network MNIST Dataset
Table 3 summarizes the tuned hyper parameters used by the experiment in Figure 2. We provide additional plots against wall clock time to demonstrate the practical improvement one can achieve using DoCoM.
Table 3: Tuned
for layer food-forwadd network on MNIST.
Learning Consensus step size y param.
Momentum
Algorithms
rate !]
CHOCO-SGD (Top-k 10%)
0.01
0.3
BEER (Top-k 5%)
0.01
0.2
DoCoM (Top-k 5%)
0.01
0.2
0.01
Top 16 Top k:535) 1000
256 batch 1000
Consensus gap
10
Loss
100
10-1
10
20
30
10
20
30
Training Time (sec.)
Training Time (sec.)
Train Gradient Norm
Train Accuracy
Test Accuracy
0.75
0.75
10
0.50
0.50
10
0.25
0.25
10
0
10
20
30
10
20
30
10
20
30
Training Time (sec.)
Training Time (sec.)
Training Time (sec.)
DoCaM Top k(5%) 16 batch
DoCoM Top k(5%) 64 batch Top-k(5%) 64 batch
DoCaM Top k(5%) 256 batch
CHOCO SGD Top k(10%) 256 batch Top-k(5%) 1024 batch
BEER Top-k(5%) batch
BEER Top-k(5%) 256 batch
Consensus gap
100
Loss
100
10-1
10
106
10
10
106
10
Samples Drawn
Samples Drawn
Train Gradient Norm
Train Accuracy
Test Accuracy
0.75
0.75
10-1
0.50
0.50
10
0.25
0.25
10-3
105
105
10
10
106
10
10
105
10
Samples Drawn
Samples Drawn
Samples Drawn
Figure Additional Results MNIST Data with Feed-forward Network. Worst-agent's loss, consensus gap, training/testing accuracy and gradient norm against wall clock time in seconds and the number of samples drawn. In the legend of wall clock time plots we denoted the number of iterations used for training.
38

---

Published in Transactions on Machine Learning Research (07 2022))
C.3 LeNet-5 on FEMNIST Dataset
We conduct another practical experiment and consider training a LeNet-5 neural network which has d' = 60850 parameters. The dataset contains m 805263 samples of 28 x 28 band-written character images, each belongs to one of the 62 classes. The samples are partitioned into = 36 agents (of ring topology) according to the groups specified in (Caldas et al., 2019). We scheduled the learning rate at its initial value for the initial stage, then decay by a factor of 10-1 certain iterations. This allows us perform large step size training the initial stage and arrive a consensual solution eventually.
Additionally, observe that when training LeNet-5 using momentum-basee variance reduced algorithms (including GT-HSGD and DoCoM), we found that the algorithms can be unstable when small momentum parameter (e.g., 3 = 0.1) is adopted, unlike the experiments on synthetic data MNIST. We suspect that this is due to the stronger requirements on Lipschitz continuity of the gradient of objective function in Assumption 2.1, i.., we require"
Eg [V ( 12110- 0'11"
YO.0'ER.
This is stronger than the typical Lipschitz continuity on the expected gradient which only demands [ ()] (() s L|le 6'|l. Particularly, the convergence of these momentum-bases al- gorithms depend on the less smooth loss landscape from the neural network model and data distribution.
Table 4: Tuned hyper-paramette for LeNet-5 on FEMNIST. Numbers on the n,, scaling schedule columns indicate the iteration number (in thousands) when n. B are scaled by 0.1 correspondingly.
Learning Consensus Momentum
Batch
7) scaling schedule
8 scaling
Algorithms
rate !)
step size param. /
size
schedule
GNSD
0.02
32
4, 20, 35
GT-HSGD
0.02
0.3
16
4, 20, 35
10, 20, 35
CHOCD-SGD (Top-k 10%)
0.01
0.25
32
4, 40, 80
BEER (Top-k 5%)
0.01
0.15
32
4, 40, 80
DoCoM (Top-k 5%)
0.01
0.2
0.3
16
4, 40,
80
10, 40, 80
DoCoM Top-k(5%)
BEER Top-k(5%)
CHOCO-SGD Top-k(10%)
GNSD
GT-HSGD
Consensus gap
100
Loss
10
10
10
10
10
10c
107
10a
Samples Drawn
Samples Drawn
0.9
0.9
Train Gradient Norm
Train Accuracy
Test Accuracy
100
0.8
0.8
10-1
0.7
0.7
10
0.6
0.6
10
10" Samples Drawn
10a
10
10" Samples Drawn
10
10
10"
10
Samples Drawn
Figure 6: Additional Results on FEMNIST Data with LeNet-5. Worst-agent's loss, consensus gap, training/testingg accuracy and gradient norm against the number of samples drawn.
This assumption known the squared smoothncss condition (Arjevaní et al., 2022). Specifically, this assumption only used in the proof Lemma The analysia for
be further relaxed the typical smoothness assumption (((:c) (0') ]]] < r,2 10 of I2, applied in the proof of Lemma B.6.
39

---

Published in Transactions on Machine Learning Research (07 2022)
C.4 Implementation Details
Compression Operators. We adopt either a greedy biased compressor Top-k (sparsification) re-scaled random compressor (quantization) (Alistarh et al., 2017) in our experiment for algorithms with compressed communication. Specifically, a re-scaled b-bits random quantization (Koloskova et al., 2019) on x E IRd that satisfies Assumption 2.4 can be described as
((v(E.))= sign(0;) || &
f//20 (4 + 1)/2" otherwise.
w-p. 1 1(/0://110/112)2
(77)
7
with level & of r, satisfying |æ.1/||=|2 E 14/2", (4, + 1)/2"), T = 1+ min vd/2%), s) as -L
With the unbiasedness of random quantization (Alistarh et al., 2017) that gives Eg (2;; fo, and with the proof in Appendix A.1 of (Alistarh et al., 2017) that gives Eş Eg[ll((s {1):) < 1|1=11
Reg (1)))) x||3| = (1x; E)I |0||² 22g x S + 1=01=== -1-
(78)
Therefore, a re-scaled random quantizer satisfies Assumption 2.4 with 8= 1/T. Moreover, as pointed out in (Koloskova al., 2019, Section 3.5), the above re-scaling trick can be applied on any unbiased compressor 2(+) satisfying (x: =) s r||=||| such that the rescaled compressor (1-r) satisfics Assumption 2.4 with 5 = 1/T.
For Top-k compressor, the communication cost per iteration is - bere bits, where bpre is the number of bits for representing a full-precision scalar, added to the cost for sending & indices. For random quantization with b bits, the communication cost per iteration is (b+ bits added to the cost of sending the ε--norm of the vector as a full-precision floating point scalar.
Table 5: Comparison of decentralized optimization algorithmss on computational complexity per iteration and node. b denotes the batch size used at every itcration. by denotes the initial batch size. R denotes the potentially multiple rounds of gossip for DeTAG. denotes the model dimension. {BEER uses large batch size of OLL/e).
Algorithms Init. Stoch. Grad. Stoch. Grad. Gossip Comm. Round
Memory Usage
GNSD
2
3d
DeTAG
b
R
3d
GT-HSGD
by
2b
2
5d
CHOCO-SGD
b
b
1 (+ Compress)
3d
BEER bt
b1
2 (+ Compress)
7d
DoCoM
60
2b
2 (+ Compress)
9d
Memory Efficient Implementation. From line 1 and 1 of Algorithm 1, observe that DoCoM relies the sum Σ, Wi, and E, WirKi, Similar to the steps described in Appendix E of (Koloskova et al., 2019) for the CHOCO-SGD algorithm, the DoCoM algorithm can be implemented with a per-node memory complexity of (d). See Table 5 for details.
Connection between Assumption 2.2 and Spectral Gap
Conditions (i), (ii) of Assumption 2.2 are standard in the litcrature of decentralized optimization, while at the same time (iii) equivalent to the spectral gap condition. To see this, we suppose W is the weighted adjacency matrix of a connected graph and note from the Perron-Frobenius theorem that 1 is the eigenvector corresponding to the leading eigenvalue of W which has multiplicity of 1. It follows from orthogonality of
U and UUT = I, (1/n)11² that
JU WU |oo wou ||2 max (12, |aal
(79)
40

---

Published in Transactions on Machine Learning Research (07 (07/2023)
Therefore, condition (iii) that asserts the existence of p (0, 1], max(A2, [h,1] S p is equivalent to max (>2, |Ail < 1. Lastly, it is obvious that || I|l2 s || + ||]|| S 2 and we used + E (0. in (iv) of Assumption 2.2 to simplify notations.
41


Reviews:
[{"review_id": "wzRCTHz68R", "reviewer": "Reviewer_pmUt", "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": "Strength:\n\n1. New algorihm incorporating compression while achieving the near-optimal sample complexity for decentralized optimization.\n2. Avoid some restrictive assumptions like bounded gradient/heterogeneity and large batch.\n3. The flow of the paper is good and easy to understand.\n\nWeakness:\n\n1. Some comparison is a bit confusing. Authors mentioned the paper BEER (https://arxiv.org/abs/2201.13320), saying that \"...... and results in a suboptimal sampling complexity......\", but as far as I can see, their paper assumed only the population function $f$ to be Lipschitz smooth (Assumption 2.3), rather than your assumption that the estimator $f_i(\\cdot;\\zeta)$ is also Lipschtz smooth (Assumption 2.1), your assumption should be (much) stronger than their setting, which is a point that I think authors should clarify when comparing. \n\n2. Also the \"suboptimal\" argument, due to their Assumption 2.3, I think their $O(\\epsilon^{-4})$ complexity should have already matched with the lower bound in Arjevani's paper? If so, I think it is a bit unfair to say BEER is suboptimal? Could you please clarify this point, or do I miss any details?\n\n3. In your algorithm Line 10, the computation of $\\nabla \\hat{f_i}^{t+1}$ and $\\nabla\\tilde{f_i}^{t+1}$ requires the same data $\\zeta_i^{t+1}$, i.e., you need to reuse the data. My impression is that common gradient tracking applies things like \n$$\nv_{t+1}=v_t+\\nabla f(\\theta_{t+1};\\zeta_{t+1})-\\nabla f(\\theta_t;\\zeta_t).\n$$\nI think in some cases reusing may not be that plausible, e.g., online setting. Do you think the algorithm can be revised, or could you please elaborate more on the data reusing?\n\n4. Regarding the time stamp of the TMLR submission, there appears some other closely related papers at least two months ago, authors may consider to add them into the text and have a comparison, e.g., Yan, Yonggui, et al. \"Compressed decentralized proximal stochastic gradient method for nonconvex composite problems with heterogeneous data.\" arXiv preprint arXiv:2302.14252 (2023).\n\nGenerally I think the paper makes a good and interesting contribution to decentralized optimization, while there are still some points I am confused. I appreciate authors' efforts on the work, please definitely correct me if I misunderstand the details. Thank you very much.", "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 proposed a new algorithm for decentralized optimization, which combines both gradient tracking, compression and momentum. Authors provided an improved sample complexities for both nonconvex smooth and PL condition cases, which nearly match known lower bounds. The proposed algorithm, compared to existing works, does not require some restrictive conditions, e.g., bounded gradient, bounded heterogeneity and large batch. Authors also provided numerical experiment results to validity the effectiveness of the proposed algorithm.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See above questions for more details.", "broader_impact_concerns": "Not applicable.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "C8u7RzHQGP", "reviewer": "Reviewer_9Bad", "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 main strength of the paper is that the convergence bounds do not require assumptions on the data heterogeneity and the boundedness of gradient as previous work, which seems to be due to gradient tracking.\n\n-----------------\n\nWeaknesses: \n\n- I am mainly concerned about the rates in Theorem 3.1. When $n$ is large, $\\eta_{\\infty}$ and $\\eta$ will be very close to zero (23). I am not sure how the authors could set $\\eta$ as shown in the paragraph after Theorem 3.1 given that they should satsify (23). Satisfying the conditions together will result in a bound on $n$ in terms of $T$, which should be discussed clearly. Such a bound will change the rate in terms of $T$. \n\nA similar comment applies to Corollary 3.1. \n\n- Discussion of lower bound: \"Such sampling complexity matches the complexity\nlower bound for stochastic first order algorithms (Arjevani et al., 2022)\"\n\nFor smooth optimization and without additional assumptions, Theorem 3 (Arjevani et al., 2022) establishes a lower bound in $\\Omega(\\epsilon^{-4})$. They also establish another lower bound in $\\Omega(\\epsilon^{-3})$ but under different sets of assumptions compared to this paper. The authors should clarify whether the improved upper bound in this paper is due to additional assumptions? Please clarify the connections with the lower bounds in Theorem 3 (Arjevani et al., 2022)  considering that the papers have different sets of assumptions. \n\n- The condition in 2 is a bit strong. What if the upper bound does not hold for some points in the support with some negligible probability measure. Imposing this condition will result in a relatively large $L$.  \n\n- Assumption 2.2. (iii) and (iv) are not very standard in my view. The authors state that such assumptions are satisfied with a particular weight matrix. However, it is not clear whether they hold for all ${\\bf W}$'s that satisfy Assumption 2.2. (i) and (ii).\n\n- Compressor: \"Other compressors such as random quantization can also satisfy (5)\"\nThis is not necessarily correct. For unbiased quantization schemes e.g., QSGD, TernGrad, and NUQSGD, the coefficient in the upper bound of (5) is  greater than one although they usually outperform the biased compression schemes. \n\n- \"we note that DoCoM shares a similar communication and computation cost per iteration as CHOCO-SGD\"\nThis is not accurate.  Considering the updates in DoCoM, the additional computation (backpropagation) compared to the original CHOCO-SGD or decentralized method with unbiased compression schemes is at least three fold since the stochastic gradients are obtained for different points in the space of parameters of different baches. It is unclear whether those baselines without variance reduction can outperform DoCoM using equivalent batches for example. \n\n- Checking the tuned hyperparameters in Appendix C, it seems the momentum is set to 0.01 in most experiments, which essentially means no momentum is applied. This does not validate the theory where the authors state that adding momentum provably accelerates convergence, e..g,  \"the momentum term is crucial in accelerating DoCoM\" before the discussion of PL condition. \n\n- On the MNIST experiments, different baselines have different batch sizes. The authors wrote in Section 4 that \"We choose the batch sizes such that all algorithms spend the same amount of computation on stochastic gradient per iteration\" However, it is not clear why for DoCoM and BEER multiple batch sizes are shown in the same plot? It is challenging to compare performance of different baselines with such bacth sizes. ", "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": "The authors propose a training algorithm in decentralized settings that uses compression with gradient tracking in addition to momentum-based variance reduction. The convergence of Doubly Compressed Momentum-assisted Stochastic Gradient Tracking does not require bounded similarity assumption between data distributions. They establish a rate of ${\\cal O}(1/T^{2/3})$ for smooth optimization and the averaged iterates. They rate is imrpoved to ${\\cal O}(\\log(T)/T)$ under PL condition and stocahstic gradients. \n", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please address the comments listed in the weaknesses above. ", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "bIVDsXptbk", "reviewer": "Reviewer_insd", "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:** \nThe selected topic of decentralized optimization is popular and important. The paper is well written. The presentation is very clear. The contribution in near-optimal sample complexity with compression is non-trivial. I did not check the proof, but based on my knowledge of STORM variance reduction and decentralized optimization, the algorithm design and theoretical results look valid. There are also sufficient experimental results on both synthetic and real-world data which demonstrate the sample and communication efficiency of the proposed DOCOM.\n\t\n**Weaknesses:** \nA few omissions in detail are listed in \"Requested Changes\" below. ", "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 work proposes the first compression-enabled decentralized optimization algorithm called DOCOM that achieves near-optimal sample complexity, and the complexity result does not require any assumption on the data heterogeneity level nor the boundedness of gradient. To achieve this goal, DOCOM uses compression with gradient tracking and momentum-based variance reduction. Experimental results on both synthetic and real-world data demonstrate the sample and communication efficiency of the proposed DOCOM. ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "**Requested changes (critical for acceptance):**\n\n(1) In the italic research question of the introduction, I think \"iteration/sampling complexity\" could be changed to \"sample complexity\", since the iteration complexity could further be reduced using minibatch. \n\t\n(2) In the caption of Table 1, change \"dominate\" to \"dominant\". \n\t\n(3) In the experiment section, you said ''where each agent only get''. You could change ''get'' to ''gets''.\n\n(4) Fix “In Figure ??” in Section C.3.\n\t\n(5) In the experiment section, what's $f_i(\\theta)$ for FEMNIST Data with LeNet-5? You could write that answer in the paper. \n\t\n**Requested changes (not critical for acceptance):** \n\t\n(6) In the second paragraph of the introduction, \"also see (Gorbunov et al., 2019)\" looks vague. Why not move \"(Gorbunov et al., 2019)\" to before \"studied algorithms with\" or before \"focused on non-convex problems\"?\n\t\n(7) You could add citations to Table 1 if convenient. \n\t\t\n(8) At the end of the third paragraph of the introduction, do you mean \"See the recent work (Richtárik et al., 2021) for more details on compression strategies.\"?\n\n(9) Assumption 2.2 (iv) will certainly hold with $\\overline{\\omega}=2$, since Assumption 2.2 (ii) and (iii) imply that the eigenvalues of $W$ are real numbers in $[-1,1]$. Isn't it simpler to remove Assumption 2.2 (iv) and let $\\overline{\\omega}=2$ throughout the paper? \n\t\n(10) Between Assumptions 2.2 and 2.3, add parenthesis in ''see (Boyd et al. (2004))''.\n\t\n(11) You could mention the name of the variance reduction technique. Like STORM or Hyrbrid SGD? \n\t\n(12) $=$ in eq. (12) is better to be $\\le$. \n\t\n(13) In the experiment section, there are figures with the x-axis \"samples used\" for synthetic data, but there are no such figures for MNIST and FEMNIST datasets. Why? Could you add the latter? For example, Figures 2 and 3 could each have 8 subfigures of which 4 have x-axis \"samples used\". ", "broader_impact_concerns": "I did not see any broader impact concerns for this theoretical paper. ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: In this paper, the authors propose a communication-efficient decentralized optimization algorithm, named as Doubly Compressed Momentum-assisted stochastic gradient tracking (DoCoM). They demonstrate that DoCoM achieves improved sample complexities for both nonconvex smooth and PL condition cases, without relying on restrictive conditions such as bounded similarity between data distributions. Finally, the authors provide numerical results to evaluate the effectiveness of DoCoM.

All the reviewers are positive with this paper. The proposed DoCoM is strong in the sense that it is the only algorithm with compression and an $O(\epsilon^{-3})$ sample complexity. The contribution in near-optimal sample complexity with compression is non-trivial. The paper is well-written, and the theoretical results are supposed by empirical studies. 

Decision: Accept (poster)