Revisiting Optimal Convergence Rate for Smooth and Non-convex Stochastic Decentralized Optimization
Authors: Kun Yuan
Xinmeng Huang
Yiming Chen
Xiaohan Zhang
Yingya Zhang
Pan Pan
Venue: NeurIPS 2022 Accept (2022)
Keywords: decentralized optimization
stochastic optimization
non-convex optimization
optimal complexity

Abstract: While numerous effective decentralized algorithms have been proposed with theoretical guarantees and empirical successes, the performance limits in decentralized optimization, especially the influence of network topology and its associated weight matrix on the optimal convergence rate, have not been fully understood. While Lu and Sa have recently provided an optimal rate for non-convex stochastic decentralized optimization using weight matrices associated with linear graphs, the optimal rate with general weight matrices remains unclear. 

This paper revisits non-convex stochastic decentralized optimization and establishes an optimal convergence rate with general weight matrices. In addition, we also establish the first optimal rate when non-convex loss functions further satisfy the Polyak-Lojasiewicz (PL) condition. Following existing lines of analysis in literature cannot achieve these results. Instead, we leverage the Ring-Lattice graph to admit general weight matrices while maintaining the optimal relation between the graph diameter and weight matrix connectivity. Lastly, we develop a new decentralized algorithm to attain the above two optimal rates up to logarithm factors. 

Revisiting Optimal Convergence Rate for Smooth and Non-convex Stochastic Decentralized Optimization
Kun Yuan 3, Xinmeng Huang"* Yiming Chen 1.49
Xiaohan Zhang', Yingya Zhang', Pan Pan"
DAMO Academy, Alibaba Group
University of Pennsylvania Peking University *MetaCarbon
(kun, yuan, yingya. zyy, panpan ppl@allaaba--iaillapppppppaaaaaa com
xinmengh@sas upenn. edu yimingomet vip zxiaohanSseas upenn edu
Abstract
Decentralized optimization is effective to save communication in large-scale ma- chine learning. Although numerous algorithmms have been proposed with theoretical guarantees and empirical successes, the performance limits in decentralized opti- mization, especially the influence of network topology and its associated weight matrix on the optimal convergence rate, have not been fully understood. While Lu and Sa [4 have recently provided an optimal rate for non-convex stochastic decentralized optimization with weight matrices defined over linear graphs, the optimal rate with general weight matrices remains unclear.
This paper revisits non-convex stochastic decentralized optimization and establishes an optimal convergence rate with general weight matrices. In addition, we also establish the optimal rate when non-convex loss functions further satisfy the Polyak- Lojasiewiez (PL) condition. Following existing lines of analysis in literature cannot achieve these results. Instead, we leverage the Ling-Lattice graph to admit general weight matrices while maintaining the optimal relation between the graph diameter and weight matrix connectivity. Lastly, we develop a new decentralized algorithm to nearly attain the above two optimal rates under additional mild conditions.
Introduction
1.1 Motivation. Decentralized optimization emerging paradigm for large-scale machine learning. By letting each node average with its neighbors, decentralized algorithms save great communication overhead compared to traditional approaches with central server. While numerous effective decentralized algorithms (see, e.g., [51 11
78]) have been proposed in literature showing both theoretical guarantees and empirical successes, the performance limits decentralized optimization have not been fully clarified. This paper provides further understandings in optimal convergence rate in decentralized optimization and develops algorithms to achieve these rates.
62
39 5
Weight matrix and connectivity measure. Assume computing nodes are connected by some network topology (graph). We associate the topology with weight matrix W j Raxx in which Wiy E (0, 1) if node j is connected to node otherwise Wi, 0. We introduce I[ - 11, 1 (0, 1). where 11, (1, ...,, 1)" I= has all entries being as the connectivity
measure to gauge how well the network topology is connected. Quantity 3 - 0 (which implies
W + 1
n I,, 1 indicates well-connected topology while 3 - (which implies W -> 7) indicates
badly-connecter topology. It is the weight matrix W and its connectivity measure / that bring major challenges to convergence analysis decentralized optimization.
Equal Contribution. Corresponding Author: Kun Yuan
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Table 1: Rate comparison between different algorithms in smooth and non-convex stochastic decentralized optimization. Parameter denotes the number of all computing nodes, / [0, denotes the connectivity measure the weight matrix, o² measures the gradient noise, b² denotes data heterogeneity. and ' is the number of iterations. Other constants such as the initialization f(x:")) - f and smoothness constant I. are omitted for clarity. Detailed complexities with constant L are listed in Table Appendix [ The definition of transient iteration complexity can be found in Remark smaller the better). "LB" lower bound while "UB" is upper bound. Notation Ó()) hides all logarithm factors.
References
Gossip matrix
Convergence rate
Tran, iters.
44
8 = cos(s
LB
VeT
T(1
(1- [1-8)o2
Theorem 2
e cos(c(/TT))
Ω VnT
0
n [1-9107
T(1-8)2
T(1
DSGD 30
E 10.1)
0 ( +
a
69
0 (1 n
VnT
T (1-)))) (1
T3 (1-9)
(1-9)202)
UB
DD 666
E 10,1,
VnT
T(-
0 [1 (1-M)o02 n (1- [1-3]>02
n
DSGT 29
E [0,1)
Ö VnT
a 7 (1-8))
DeTAG 44
| e [0,1)
Ö VNT
T(1-0)
(I-M)ø7
MG-DSGD
E (0.1)
0 vnf
Ō (I (1-B]o²
T(1-0)
n² The complete complexity is 0( (1-3)3 (02. (1)1)-1-555 ). which reduces to 0
(1-3)2o2) for small o².
n
Decentralized optimization. Decentralized approaches are built upon the partial averaging x; EjeN, Wejzy (or x² = Wr in a more compact manner) where N₁ is the set of neighbors of node i (including node itself). The sparsity and connectivity of W significantly influence the efficiency and
effectiveness of the partial averaging. Decentralized gradient descent [5T 79), diffusion [ [5] and
dual averaging [19] are well-known decentralized methods. Other advanced algorithms. which can
correct the bias caused by heterogeneous data distributions, include decentralized ADMM [45] 63
explicit bias correctttttonn 62 80 38
gradient tracking 50
17
54
74,, and dual acceleration 60 68
In the stochastic regime, decentralize SGD [1]
59
39
30 and its momentum and adaptive variants
41
78
47
have attracted a lot of attentions. After being extended to directed topologies [5] 75).
topologies
(30 48 69 asynchronous settings [40]. and data- data-heterogeneous scenarios
2 29]. decentralize SGD has much more applicable scenarios with significantly improved performance. Decentralized algorithms are also closely related to federated learning methods [46] 64
666
73
43
76
28
37 when they admit weight matrices alternating between JL 11,, 1 and the identity matrix.
Prior understandings in theoretical limits. A series of pioneering works have shed lights on the theoretical limits in decentralized optimization. These works establish the optimal convergence rate for convex non-stochastic decentralized optimization 66
61
65
32]. and propose decentralized
However, there are few studies on the theoretical limits in non-convex stochastic decentralized optimization, which is quite common in large-scale deep learning, even when the costs are smooth.
algorithms that (nearly) match these optimal bounds [60 61 68
65
33 32
A recent novel work [44) establishes the optimal complexity for smooth and non-convex stochastic decentralized optimization. While this optimal bound is inspiring, it is valid for a restrictive family of weight matrix W associated with the linear graph whose connectivity measure B cos(IT/ /n/] However, the linear graph is just one of the commonly used topologies. A more difficult but fundamental question still remains open:
What is the optimal convergence rate of smooth and non-convex stochastic decentralized optimization with general weight matrix (that does not necessarily satisfy B = cos( (z (rn))?
It is not known whether the lower bound in 44 still holds for other commonly-used weight matrices resulted from grids, toruses, hypercubes, etc. whose connectivity measure B o cos(TT/n).
Challenges. Following existing lines of analysis, to our knowledge, cannot provide an assuring answer. It is known that the communication complexity in decentralized optimization is typically
"See Corollary I in the latest aiv version of [4 uploaded in Jan. 2022: WiXix:20060080855/0

---

Table 2: Rate comparison between different algorithms in smooth and non-convex stochastic decentralized optimization under the PL condition. Constants such as the initialization f(x(0)) f and smoothness constant I are omitted for clarity. Detailed complexities with constants I and μ are listed in Table o Appendix B
References
Gossip matrix
Convergence rate
Tran. iters, complexity
LB
Theorem
B (0s((T)//)))
2 + c -(T()-1)))
RT
DSGD 330
B 10
d²
6²
RT [1(1-0]
[1- min
UB DAGD
57 1
B E (0,1)
0 te -T----1-0 ((11)))))
0 (1-M1177
D*/ED
77
B (0.1)
0 RT [1[18] + - -))
x²
Ō (1pB)
DSGT 2
B 10.1)
Ō + 1 (=(1-8) - -((-
0²
Ō 0(1^))
DSGT 73
0 WT
+ + T1133p + - -1(--))
d2
Ô (1-97)
MG-DSGD
8 E (0,1)
Ó o KT + (1-
11-8)172
This rate is derived under the trongly-conver assumption.
This rate is achieved by utilizing increasing (non-constant) mini-batch sizes.
proportional to the diameter D of the network topology [60]. Establishing the relation between D and is key to clarifying the influence of the weight matrix on optimal convergence rate. Existing works utilize the linear graph to establish the optimal relation as D O /VI - :3). However, weight matrices associated with linear graph are quite limited. Given a fixed network size n (which prerequisite when discussing complexities in distributed stochastic optimization 44] 24 31 21). they have to satisfy 3 = cos(T/ //n). Weight matrices with other cannot be implied from the linear graph. To examine the lower bounds with more general weight matrix W, [65] proposes wider class of networks named linear-star graph, which, however, leads to suboptimal relation between D and B. As result, network topology that admits general weight matrices W while maintaining the optimal relation between D and B is critical to clarify the above fundamental question.
600 61
1.2 Main results. This paper successfully identifies the desired network topology which facilitates the theoretical limits over the general weight matrices. Our contributions are summarized as follows.
We discover that ring-lattice graph maintains the optimal relation between D and B for much broader class of weight matrices. Given any fixed n and 3 E [0, cos(T/n)), we can always construct a weight matrix W E R associated with some ring-lattice graph, whose connectivity measure is 3, that satisfies D = 0(1/vI- B). Since cos(T//)) approaches to when n is large, the ring-lattice graph admits far broader weight matrices than linear graph used in 60
With the above results, we provide the optimal convergence rate for smooth and non-convex stochastic decentralized optimization that holds for any weight matrix with 8 E [0, cOs(TT/))) In contrast, the optimal rate in 44 only applies weight matrix satisfying = cos(TT/)) We also provide the optimal convergence rate when the non-convex cost functions further satisfy the Polyak-Logg Lojsslewijis (PL) condition 227 for any weight matrix with B E [0, cos(T (T/)))
We prove that the above two optimal complexities can be nearly- (under mild assumptions and up to the condition number L/ [t as well as other logarithmic factors) by simply integrating
multiple gossip communication 42 58) and gradient accumulation (6) (5 44] to the vanilla decentralized SGD (D-SGD) algorithm. Compared to DeTAG 44. the extended D-SGD avoids the gradient tracking steps and saves half of the communication overheads. Compared to DAGI [57], the extended D-SGD achieves the near-optimality using constant mini-batch sizes and has theoretical guarantees in the non-convex (as well as the PL) scenario.
All established results in this paper as well as those of existing state-of-the- decentralized algorithms are listed in Tables and [2] The smoothness constant L and PL constant μ are omitted in these tables for clarity. The detailed complexities of these algorithms with constant L and μ are listed in Tables 6 and in Appendix B
1.3 Other related works. Some other related works are discussed as follows.
3

---

Lower bounds and optimal algorithms. The lower bounds and optimal algorithms for stochastic
and convex optimization have been intensively studied in [35 36 55 [5]. References
[0]
established the lower bounds to find stationary solutions for non-convex optimization, and [21 3
proposed algorithms with near-optimal convergence rate for non-convex finite-sum minimization. In
deterministic decentralized optimization, the optimal convergence rate was established for strongly convex optimization [60], non-smooth convex optimization [6]], and non-convex optimization [65]. Furthermore, the lower bounds and optimal algorithms over time-varying topologies are studied in
57 58 [6]. In stochastic decentralized optimization, works [77] and [30] established the lower bounds for strongly-comve decentralized SGD. 44 proves the optimal complexities for non-convex problems when weight matrices satisfy = cos(TT/.).
33
as basis model to generate the small world graph. However, its relation between graph diameter and connectivity measure is not clarified to our knowledge. A related work [72] examines the robustness of the ring-lattice graph, but does not discuss its connectivity measure. Furthermore, ring-lattice has never been utilized to establish the influence of the weight matrix on the optimal rate in decentralized optimization before.
Ring-lattice Graph. The ring-lattice graph was used in 70
2 Problem setup
Problem setup. Consider the following problem with a network n computing nodes:
min f())= fi(z) where f((x) := DE,DD,
(1)
Function fi(z) is local to node i, and random variable & denotes the local data that follows distribution D,. Each local data distribution D; can be different across all nodes.
Assumptions. The optimal convergence rate is established under the following assumptions.
Function class, We assume each local loss function is L-smooth, i.e.,
[V(zz) - v fl()ll S L|| - vll. Vz, y E IR",
(2)
for some constant O. We let the class Fr denote the of all functions satisfying 2 We
may also assume the global loss f(x) = 1 E fi(x) satisfies the μ-PL condition:
2p([(z)) f*) s [V Var E IR.
where f* is the optimal function value in problem ① and μ > is some constant. We let the function class Fr,,, denote the set of all functions satisfying both (2) and (3).
Oracle class. We assume each node i interacts with fa(x) via the stochastic gradient oracle (æ, {) where is random variable. In addition, assume oracle gx {) satisfies
(x, f. and (x, {) {f So.
(4)
We let O₂2 denote the class of all such stochastic gradient oracles.
Weight matrix class. We let Wn,s denote the class of all gossip matrices W ppxx satisfying
W1, = 1n, I W = I || 1 1 I B E [0, 1),
(5)
where 1, = (1,..., 1)2 R with all entries being 1. If W is positive semi-definite, then connectivity measure is its second largest eigenvalue.
Algorithm class. We consider an algorithm A in which each node accesses an unknown local function fo via the stochastic gradient oracle ğ (x; {,) E O2 Each node running algorithm A will maintain local model copy x; policy, i.e., each node communicates via protocol
(k) at iteration k. We assume A follow the partial averaging
(k)
Σ JEN
WiJU
(k)
Vi E [n]]
for some W = [wiy]i E Wn.s where [m] == (1,.... m). and y and z are the input and output variables of the communication protocol. In addition, assume A to follow the zero-respecting

---

R10,2
R10,4
R10,6
Figure I: An illustration of the ring-lattice graph with size 10 and degrees 4, 6, 9. It observed that R10,2 ring graph while R10,9 is complete graph.
policy 9 25
Informally speaking, the zero-respecting policy requires that the number of (k)
non-zero entries of local model copy 2; can only be increased by sampling its own stochastic gradient oracle or interacting with the neighboring nodes. The zero-respecting policy is widely followed by all methods in Tables and 2 and their momentum and adaptive variants. We let Aw be the set all algorithms following the partial averaging and zero-respecting policies.
Lower bound metrics. With the above classes, we now introduce the measures for convergence rate's lower bound. Given loss functions {fi]
[iJi= S Fr (or Uij S Fr,,,), stochastic gradient ) C O²2, weight matrix W E Wn,3. an algorithm A Aw, the number of gradient (which will be denoted a
oracles {
queries (or communications rounds) T, we let (6)
when there is ambiguity) be the output of algorithm A with & Span( (12/) [ p> The lower bound for smooth and non-convex stochastic decentralized optimization is defined as
inf sup sup Λελw W W E0, SARLISA
sup
1.. W..) (.)
(6)
The lower bound under the PL condition defined as inf sup AεAw W
sup E0,, ST
sup
BIJG f*).
Fixed network size n. This paper considers stochastic decentralized optimization where the network size is a fixed constant. A fixed is prerequisite in distributed stochastic optimization which enables distributed algorithms achieve the linear speedup in convergence O /VTT), the algorithms listed in Tables] Iaalls[[ande []d In decentralized deterministic optimization, however, size n does not appear in the convergence rate. Thus, does not need be specified and can be varied freely when establishing the lower bounds [60 61]
3 Ring-Lattice graph
The main challenge analyzing theoretical limits in decentralized optimization lies in clarifying the influence of network topology and its associated weight matrix. It is intuitive that the graph diameter D affects the convergence rate. In the worst case, one node needs to take at least D communication steps transmit its own gradient information established, the influence of the weight matrix on lower bounds will become clear. However, existing results either establishes suboptimal relation between D and 3 655 admits restrictive weight matrices 660 61 44 given fixed n. Now we show that the ring- graph maintains the optimal relation between D and 3 for broad class of weight matrices. All proof details are in Appendix
the other. If the relation between D and / is
Definition 1 (RING-LATTIC) GRAPH [7I]). Given any positive integers n, l such that k is even and 2 < k < n 1, the k-regular ring-lan ring-lattice graph over nodes {1.... .n), denoted by Rn, an undirected graph in which each node E [m] is connected with the set of nodes {(i + mod [E] < k/22 where (i + f) mod defined as
i lite
filittii n;
(i + 2) mod n
i itttn fi+t< 1;
i itt- n ifit
Apparently, each node in Rr. has degree k.
5

---

Ring-lattice is a k-regular graph. When k = 2, ring-lattice will reduce to the ring graph. While Definition fexxlude the case in which & n - 1, the complete graph can be exceptionally viewed as the ring lattice with degree k = 1. Therefore, for general 2 S k S n 1, Rn., can be regarded as an intermediate state between the ring and complete graphs, see the illustration in Fig. The following lemma clarifies the diameter of R,,.k.
Lemma 1. The diameter of the ring-lattice graph Rn, is D = ((n/k).
It is derived from the above lemma that the diameters of Rn,2 and Rn,, are (n) and @ respectively, which are consistent with the ring and complete graphs.
The following fundamental theorem establishes the relation between D and connectivity measure B.
Theorem 1. Given a fixed n and any B E [0, (oos(T/n)], we can always construct a ring-lattice graph Rm, so that
(1) it has an associated weight matrix W E Wn.5. i.e., W E 12xx" and [| - 1 = B,
(2) its diameter D satisfies D = =0(1//VT-))
Remark 1. The works 160 61 44 utilize the linear graph to establish the same relation D
((1/ -111/-1111 3). However, given fixed network size n, the linear graph admits limited weight matrices with 3 = cos(TT/)).
Remark 2. Sun and Hong [65] propose a slightly wider class of networks named limear-star graph, which, however, leads suboptimal relation D = [011/m((1 B)}) 165 Proof of Corollary 3.1].
Remark 3. It is worth noting that for deterministic decentralized optimization where n may vary, one can tune n to make 3 = cos π nn) lie in the full interval (0, 1) as shown in 160 6ly. In other words, 160 677 proved that D = 0(1/VI- - 3) for any 3 E (0, 1) if n is a varying parameter. However, this result is not valid in stochastic scenarios where required to be fixed.
4 Lower bounds with general weight matrices
This section will establish the lower bounds for smooth and non-convex decentralized stochastic optimization. All proof details are Appendix [D. When the cost function does not satisfy the PI. condition 33), we will derive that the convergence rate is lower bounded by Q VaT + P). This result together with Theorem [ leads to:
Theorem 2. For any L > 0, n > 2, 3 E [0, cos(s//) (T))], and a > 0, there exists a set of loss functions (f.).m S FL. set of stochastic gradient oracles { C Oza, and weight matrix W E Wn.s.
such that it holds for any E Aw starting form (0) that
LVL
E V M(EA w. Ω
(8)
VnT
TVI-3
Remark 4 (Comparison with existing bounds). Comparing to the lower bound established in
(44), Theorem 2 Jadmits a much broader class of weight matrices with B E [0, cos( n /n]]. While the interval (0, cos /m)] C [00,1] 1), it approaches to [0. 1) as n goes large. Such interval is broad enough to cover most weight matrices (generated through the Laplacian rule W = =I LI-L/dmees /max) resulted from common topologies such as line, ring, grid, torus, hypercube, exponential graph, complete graph, Pedos-Renyi graph, geometric random graph, etc. whose 33 lies in the interval [0, cos(TT (T])) when n. is sufficiently large, see details in Appendix D
Remark 5 (Linear speedup). The first term 1/vnT dominates (8) when T is sufficiently large, which will require T 0(1 (n)())))))))))))))))()))))))(( )) (it is inversely proportional to n) iterations to reach accuracy c. Therefore, if the term involving n.T is dominating the rate for some T, we say the algorithm is in its linear-sp speedau stage. Linear speedup is a fundamental property that distributed algorithms enjoy.
Remark 6 (Transient iteration complexity). Due the topology-incurred overhead in conver- gence rate, a decentralized algorithm has to experience a transient stage to achieve linear-speedup. Transient iterations are referred to those iterations before an algorithm reaches linear-speedup stage. To reach linear speedup in the lower bound 8). T has to satisfy TVI3 S VeT and hence T = O O(T-T))))) which is the transient iteration complexity shown in the first line in Table 7 The smaller the transient iterations are, the faster the algorithm can achieve linear speedup. Transient iteration complexity is important metric to evaluate how sensitive the algorithm is to B.

---

Algorithm 1: Decentralized SGD with multiple gossip steps (MG-DSGD)
Require: Initialize x; (0) the weight matrix W, and the rounds of gossip steps R. for k = 2,,,,.... K, every node do
(k), Sample (c((.r) r= independently and let gt 91hh =
grad. accumulation
Update /f (k+11) Jj (k)
79: (k)
D local stochastic gradient descent
Update xq
(k+1) FastGossip.vverage (++1) ia
1i=1 Rt);;
> multiple gossips
Algorithm 2: x; FastGoosippAvergee((()) W.
Require: {0: W, R. and 3; let 2, 2(-1) di and 17
1-VI-8 1- 1+ 14,72
for r 0, 1, 0,,, R 1, every node do
Update 2, (r+1) + 17) E ΣJEN, Wiyzt (r) 1r-1); 1723
D fast gossip averaging
Output: v; =4 (R)
When the cost function satisfies PL condition B.. we prove the convergence rate is lower bounded by Q1 a + exp(-CT/ D)) where C some constant. This result together with Theorem I lleads to: VnT
Theorem 3. For any T. > 0,
2, B [0, cos( cos(s//n)), and > O, there exists a set of loss functions {f+)== S Ft, set of stochastic gradient oracles {ūr]==1 Og2, and a weight matrix W E Wn.3. such that it holds for any A E Aw starting, from (0) that
( JUT +
BIA(BAAA)) w.)) - f1 = 0
Rate results in an Õ ()(1-8) -)- transient complexity.
Expression (9) is the first lower bound for smooth and non-convex stochastic decentralized optimiza- tion under the PL. condition to our knowledge. Please note that the above lower bound also applies to strongly-convex stochastic decentralized optimization, the construction details in Appendix [
DSGD with multiple gossip communications
This section will present decentralized algorithm that achieve the lower bounds established in Sec. up to constants I. and j.. The new algorithm is direct extension of the vanilla decentralized SGD (DSGD) [T] 30). Inspired by the algorithm development in [57 44
add two additional compo- nents to DSGD: gradient accumulation and multiple-gosse communication. The main recursions are listed in Algorithm| [ which utilizes the fast gossip average step 42 in Algorithm 2 We call the new algorithm as MG-DSGD where "MG" indicates "multiple gossips". All proofs are in Appendix E
The DeTAG algorithm proposed in 44 applies the gradient accumulation and multiple- gossip communication techniques gradient tracking, which achieves the optimal rate in non-convex (without PL condition) stochastic decentralized optimization. This paper finds in MG-DSGD that the multiple gossip technique can significantly reduce the influence of data heterogeneity, and the gradient tracking step can be saved to achieve the convergence optimality. Similar observations also appeared in [57] albeit in the strongly-convex scenario. Removing gradient tracking from algorithm updates brings two benefits. First, it saves half of the communication overhead and memory storage per iteration. Second, enables numerous effective acceleration techniques designed exclusively for decentralized SGD such Quasi-global momentum [1), DecentLaM [78), adaptive momentum [7], etc. which cannot be easily extended to gradient tracking.
Let T be the toal number of gradient queries (or decentralized communications) at each node. Since each node takes gradient queries and communications at round k; holds that T K R when MG-DSGD finishes after K rounds. The following theorems clarify the convergence rate of MG-DSGD where = K R. We omit the initialization constants below. Our analysis techniques relate to the classic SGD analysis but with inaccurate oracles in the nonconvex case 20).
7

---

Theorem 4. Given L > 0, n 2, (0.1), a> O, and let A denote Algorithm 1 Assuming that
1 Di= [((x)) - Vf(=)) - 1s for any I E Th" and the number of gossip rounds R is set as in
Appendix the convergence of A can be bounded for any {felim Ft and any W E Wn,3 that
- VnT
(OVL
L
where x
(0)
(10)
K
TVT-B
Remark 7. The rate (10) matches with the lower bound
$ up to logarithm factors. Furthermore, we
remark that the gradient similarity assumption 1. - obtain the lower bound in Theorem 2 Due to these two restrictions, MG-DSGD is nearly-optimal (not fully-optimal) algorithm. However, while the analysis in MG-DSGD needs to assume bounded gradient similarity b2, it only affects the convergence rate as a logarithm term hidden in the (.)) notation. If one wants to completely removes the gradient similarity assumption from Theorem 4
IV f(()) - V f(=)] 6² is not required to
he/she can refer to the techniques in gradient tracking 144 73 43
The rate I0) matches with the lower bound 8 up to logarithm factors. The comparison between MG-DSGD with other state-of-the-arr algorithms is listed in Table I MG-DSGD matches DeTAG in convergence rate and saves half of the communications, see experiments in Fig. 2 While the analysis in MG-DSGD needs to assume bounded data heterogeneity 6², it only affects the convergence rate as a logarithm term hidden in the (.) notation.
Theorem 5. Under the same assumptions as in Theorem 4 and setting R as in Appendix E the convergence of A can be bounded for any loss functions {feli=1 C FL,, and any W Wn, by
Σ B(f(a()) K
1
- f"
Lo 11nnT + -xpp(- B/1))
(11)
Remark 8. Comparing and lower bound 9.. we find its dependence on 0², n,, T, and 1 3 is optimal while that on and μ. not. One reason that our algorithm does not involve any Nesterov acceleration (52] mechanism. The established upper bound in a recent work (57] is closer to the lower bound ( by utilizing Nesterov acceleration, see Table in Appendix However, it requires an scenario.
increasingly large mini-batch of data per iteration, and only works for the strongly-come It is not known whether the acceleration mechanisms in [57] can be extended the non-convex and is state-of toee-----hh-----ee ahe under the general PL condition to our knowledge.
PL scenario. The bound
6 Experiments
This section will validate our theoretical results by empirically comparing different decentralized algorithms DSGD 33 D2 677, DSGT [82]. DeTAG [44) and MG-DSGD in deep learning.
Implementation setup. We implement all decentralized algorithms with PyTorch (53) 1.6.0 using NCCL 2.8.3 (CUDA 10.1) as the communication backend, in which the partial averaging primitive is implemented by NCCL send/receive primitives. For parallel SGD, we used Py PoTchh's native Distributed Data Parallel (DDP) module. All the models and training scripts in this section run servers with 8 NVIDIA V100 GPUs with each GPU treated as one node. Similar to existing works 44), we use Ring graph throughout all experiments.
Tasks and training details. A series of experiments are carried out with CIFAR-10 34 and ImageNet [16] to compare the aforementioned methods. For CIFAR-10 dataset, it consists of 50,000 training images and 10,000 validation images in 10 classes For ImageNet dataset, consists of 1, 1,281,16 training images and 50,000 validation images in 1000 classes. We utilize ResNet variants [23 on CIFAR-10 2ResNet-20 with 0.27M parameters and ResNet- 18 with 1 11.17M parameters) and ResNet-50 on ImageNet. For training protocol, we train total 300 epochs and the learning rate is warmed up in the first 5 epochs and is decayed by a factor of 10 at 150 and 250-th epoch. For learning rate, we tuned a strong baseline in the PSGD setting (5e-3 for single node) and used the same setting in all decentralized methods. The batch size is set to 128 on each node. All CIFAR-10 10 experiments repeated three times with different seeds. For fair comparison, we maintain the total number of gradient queries the same for algorithms in experiments, i.e., T K.R
Performance with homogeneous data. Table compares the proposed MG-DSGD with centralized parallel SGD and other baselines with homogeneous data distributions. For DeTAG and MG-DSGD, the communication round R. is set as 2. We also performed an ablation study on the effect of
8

---

Table 3: Accuracy comparison on CIFAR-10 with homogeneous data (8 nodes).
WITH MOMENTUM
WITHOUT MOMENTUM
METHODS
RESNET18
RESNET20
RESNET18
RESNET20
PSGD
93,99 0.52
91.62 0.13
93.22 0.19
89.06 0.08
DSGD
0.05
9.06
93.67 + 0.04
89.14 0.08
DSGT
0.004
91.64
03.57
88.85 + 0.11
D
0.077
89.83 0.08
92.18
88.67 +
0.11 0.11
DETAG 0.13
91.77 0.25
93.17
88.97 0.11
MG-DSGD
94.57
91.77 0.09
93175
89.18 + 0.08
Table 4: Accuracy comparison on CIFAR-10 with heterogeneous data (ResNet-20).
METHODS
DSGD
DSGT
D²
DETAG
MG-DSGD
0.1 a
58.14 1.76
55.16 0.42
53.85
0.40
58.77 1.30
59.42 + 3.36
84.74 0.97
84.74 0.32
84.1 # 0.64
84.82 # 0.19
84.91 # 0.74
a =
10
90.19 + 0.47
89.83 # 0.12
89.80 + 0.25
90.27 # 0.08
90.43 + 0.04
Val Acc CIFAR-10 (ResNet-20)
Val Acc on ImageNet (Resnet-50)
800
Evol Top-1 Accuracy
3
Lccuee
66
40
DSGT
@
20
76.50
10
20
MG DSGD
3.0
10
30
50 60
80
0.0
0.5
1.0
2.0
2.5
3.0 3.5
Communication Volumn(1e2 MB)
Communication Volurnn(1e6 MB)
Figure 2: Accuracy in terms of the communication volumes. Left: CIFAR-10 with heterogeneous
data (a = 1); Right: ImageNet with homogeneous data.
momentum acceleration. Except for the ResNet-20 scenario with momentum in which MG-DSGD and DeTAG achieve the same performance, MG-DSGD consistently outperforms baseline methods in other scenarios. Moreover, MG-DSGD is more communication--efiiiiae than DSGT and DeTAG.
Performance with heteogeneous data. Following previous works 81 41, we simulate data heterogeneity among nodes with a Dirichlet distribution-based partitioning. A quantity a controls the degree of the data heterogeneity. The training data for particular class tends to concentrate in single node as a + 0, i.c. becoming more heterogencous, while the homogeneous data distribution co. We tested 0 100 for all compared methods corresponding to setting with high/mild/low heterogeneity. As shown in Table DeTAG and MG-DSGD outperform the other baselines by visible margins, and MG-DSGD is with slightly better accuracies. The left plot in Fig. 2 illluttraees that MG-DSGD achieve a competitive accuracy to DeTAG using much less communication budgets CIFAR-I0 with a
is achieved
Latch-batch training ImageNet. To train ResNet-50 on ImageNet, utilization of the large-batch is necessary to speedup the training process. Since MG-DSGD based on DSGD, we can extend the large-batch acceleration techniques introduced in [78 41 to MG- DSGD to achieve better performance. These techniques are developed exclusively for DSGD and cannot be integrated to DeTAG easily. Following 78), we train total 120 epochs. The learning rate is warmed up the first 20 epochs and is decayed in cosine annealing scheduler. The results are listed in Table showing that MG-DSGD has better accuracy than other approaches.
Table 5: Performance of dif- ferent methods (lmageNet).
Methods
Acc.
DSGD
76,23 0.06
DSGT
76.37 0.07
DeTAG
76.57 0.02
MG-DSGD
76.64 0.03
Fig. 2 right) illustrates how different algorithms perform in terms of communication budgets used.
More results. In Appendix F we depict the accuracy curves in terms of epochs (rather than communication volumes). The ablation on the influence of inner loop R is also listed there.
Conclusion
This paper revisits the theoretical limits smooth and non-convex stochastic decentralized optimiza- tion. Existing lower bound proved in 44 is only valid for special weight matrices with connectivity

---

measure 3 = /o)( It is not known what the lower bound is when using weight matrices with other To address this issue, this paper establishes the lower bound for any weight matrix with B E [0, cos((T/1) IT //n]]. We also clarify the lower bound when loss functions satisfy the PI. condition. A new algorithm is proposed to match these lower bounds up to logarithm factors.
Acknowledgements
The authors are grateful to all anonymous reviewers in NeurlPS 2022 for the very helpful discussions during the rebuttal process as well as useful references on accelerated decentralized gradient descent.
References
[1] Alekh Agarwal, Martin J Wainwright, Peter Bartlett, and Pradeep Ravikumar. Information- theoretic lower bounds on the oracle complexity of convex optimization. Advances in Neural Information Processing Systems (NeurIPS), 22, 2009.
[2] Sulaiman A Alghunaim and Kun Yuan. A unified and refined convergence analysis for non- convex decentralized learning. arXiv preprint arXiv:2 00.09993, 2021.
[3] Zeyuan Allen-Zhu. How to make the gradients small stochastically: Even faster convex and nonconvex sgd. Advances in Neural Information Processing Systems (NeurIPS), 31, 2018.
[4] Yossi Arjevani, Yair Carmon, John C. Duchi, Dylan J. Foster, Nathan Srebro, and Blake E. Woodworth. Lower bounds for non-convex stochastic optimization. ArXiv, abs/1912.023655 2019.
[5] Mahmoud Assran, Nicolas Loizou, Nicolas Ballas, and Mike Rabbat. Stochastic gradient push for distributed deep learning. In International Conference on Machine Learning (ICML), pages
344-353, 2019.
[6] Itai Benjamini, Gady Kozma, and Nicholas Wormald. The mixing time of the giant component of random graph. Random Structures & Algorithms, 45(3):383 2014.
[7] Stephen P Boyd, Arpita Ghosh, Balaji Prabhakar, and Devavrat Shah. Mixing times for random walks on geometric random graphs. In ALENEX/ANALCO, pages 240-249, 2005.
[8] Lucien Le Cam. Asymptotic methods in statistical decision theory. 1986.
[9] Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points i. Mathematical Programming, 184(1):71-12) 2020.
[10] Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding
stationary points ii: first-order methods. Mathematical Programming, 185(1):315-355, 2021.
[11] Jianshu Chen and Ali H Sayed. Diffusion adaptation strategies for distributed optimization and
learning over networks. IEEE Transactions on Signal Processing, 60(8):4289-4306 2012.
[12] Yu Chen, Sanjeev Khanna, and Huan Li. On weighted graph sparsification by linear sketching. In 2022 JEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), 2022.
[13] Yiming Chen, Kun Yuan, Yingya Zhang, Pan Pan, Yinghui Xu, and Wotao Yin. Accelerating gossip SGD with periodic global averaging. In International Conference Machine Learning (ICML),022)
[14] Imre Csiszár and János Körner. Information Theory- - Coding Theorems for Discrete Memoryless Systems, Second Edition. Cambridge University Press, 2011.
(15) Anindya De, Sanjeev Khanna, Huan Li, and MohammadHesam NikpeySalekde. Approximate optimization convex functions with outlier noise. Advances in Neural Information Processing Systems, 2021.
[16] Jia Deng. Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 248 228..55. Ieee, 2009.
[17] P. Di Lorenzo and G. Scutari. Next: In-network nonconvex optimization. IEEE Transactions on Signal and Information Processing over Nenworks, 2(2): 2016.
[18] Jelena Diakonikolas and Cristôbal Guzmán. Lower bounds for parallel and randomized convex optimization. In Conference Learning Theory, pages 1 1132-1157. PMLR, 2019.
[19] John C Duchi, Alekh Agarwal, and Martin J Wainwright. Dual averaging for distributed Convergence analysis and network scaling. IEEE Transactions on Automatic control, 57(3):793--)3) 6066 2011.
optimization:
10

---

[20] Pavel Dvurechensky. Gradient method with inexact oracle for composite non-convex optimiza- tion, 2017.
[21] Cong Fang. Chris Junchi Li, Zhouchen Lin, and Tong Zhang. Spider: Near-optimal non- convex optimization via stochastic path-integrated differential estimator. Advances in Neural Information Processing Systems, 31, 2018.
[22] Brian Hayes. Computing science: Graph theory in practice: Part it American Scientist,
88(2):104-109, 2000.
[23] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages
770-778, 2016.
[24] Samuel Horvath, D. Kovalev, Konstantin Mishchenko, Sebastian U. Stich, and Peter Richtárik. Stochastic distributed learning with gradient quantization and variance reduction. arXiv, 2019. [25] Xinmeng Huang, Yiming Chen, Wotao Yin, and Kun Yuan. Lower bounds and nearly optimal algorithms in distributed learning with communication compression. Advances in Neural Information Processing Systems (NeurIPS), 2022.
[26] Xinmeng Huang and Kun Yuan. Optimal complexity non-convex decentralized learning over time-varying networks. arXiv preprint urXiv:2211.00533 2022.
[27] Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal- gradient methods under the polyak-tojasiewicz condition. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 795-8 155-811. Springerr 2016.
[28] Sai Praneeth Karimireddy, Saryen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In International Conference on Machine Learning (ICML), pages 5132-5143, PMLR, 2020.
[29] Anastasiaa Koloskova, Tao Lin, and Sebastian Stich. An improved analysis of gradient tracking for decentralized machine learning. Advances in Neural Information Processing Systems, 34, 2021.
[30] Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian U Stich. A unified theory of decentralized sgd with changing topology and local updates. In International Conference on Machine Learning (ICML), pages 1-12, 2020.
[31] Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian U. Stich. A unified theory of decentralized sgd with changing topology and local updates. In International Conference on Machine Learning. 2020.
[32] Dmitry Kovalev, Elnur Gasanov, Alexander Gasnikov, and Peter Richtarik. Lower bounds and optimal algorithms for smooth and strongly convex decentralized optimization over time-varying networks. Advances in Neural Information Processing Systems (NeurIPS), 34, 2021.
[33] Dmitry Kovalev, Adil Salim, and Peter Richtárik. Optimal and practical algorithms for smooth and strongly convex decentralized optimization. Advances in Neural Information Processing Systems (NeurIPS), 33:18342-11833 2020.
[34] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[35] Guanghui Lan. An optimal method for stochastic composite optimization. Mathematical Programming, 133(():365-39) 0111365-377,50 20,,,,9,21222 2012.
[36] Guanghui Lan and Yi Zhou. An optimal randomized incremental gradient method. Mathematical programming, 171(1):177-215, 2018.
[37] Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang. and Zhihua Zhang. On the convergence of fedavg on non-iid data. In International Conference on Learning Representutions, 2019. [38] Z. Li, W. Shi, and M. Yan. A decentralized proximal-gradient method with network independent step-sizes and separated convergence rates. IEEE Transactions on Signal Processing. July 2019. early acces. Also available on arXiv:1704.078007
[39] Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsieh, Wei Zhang, and Ji Liu. Can decentralized algorithms outperform centralized algorithms? A case study for decentralized parallel stochastic gradient descent. In Advances in Neural Information Processing Systems (NeurIPS), pages 5330-5340, 2017.
[40] Xiangru Lian, Wei Zhang, Ce Zhang, and Ji Liu. Asynchronous decentralized parallel stochastic gradient descent. In International Conference on Machine Learning (ICML), pages 3043-3052, 2018.
11

---

[41] Tao Lin, Sai Praneeth Karimireddy, Sebastian U Stich, and Martin Jaggi. Quasi-globut mo- mentum: Accelerating decentralized deep learning on heterogeneous data. In Interationaal
Conference on Machine Learning. 2021.
[42] Ji Liu and A Stephen Morse. Accelerated linear iterations for distributed averaging. Annual Reviews in Control, 35(2):160-165, 2011.
[43] Songtao Lu, Xinwei Zhang, Haoran Sun, and Mingyi Hong. Gnsd: A gradient- tracknng based
nonconvex stochastic algorithm for decentralized optimization. In 2019 IEEE Data Science Workshop (DSW). pages 315-321. IEEE, 2019.
[44] Yucheng Lu and Christopher De Sa. Optimal complexity in decentralized training. In Interna- tional Conference on Machine Learning (ICML), pages 7111 1-1123.. PMLR, 2021.
[45] Gonzalo Mateos, Juan Andrés Bazerque, and Georgios B Giannakis. Distributed sparse linear regression. IEEE Transactions on Signal Processing, 58(10):5262-5276 2010.
[46] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication--fiicee effficienntiii learning of deep networks from decentralized data. In Artificial Intelligence and Statistics, pages 1273-1282. PMLR, 2017.
[47] Parvin Nazari, Davoud Ataee Tarzanagh, and George Michailidis. Dadam: A consensus-based distributed adaptive gradient method for online optimization. arXiv preprint arXiv:1901.09109 2019.
[48] Angelia Nedié and Alex Olshevsky. Distributed optimization over time-varying directed graphs.
IEEE Transactions on Automatic Control, 60(3):601-615, 2014.
[49] Angelia Nedić, Alex Olshevsky, and Michael G Rabbat. Network topology and communication- computation tradeoffs in decentralized optimization. Proceedings of the IEEE, 106(5):953-976, 2018.
[50] A. Nedic, A. Olshevsky, and W. Shi. Achieving geometric convergence for distributed optimiza- tion over time-varying graphs. SIAM Journal on Optimization, 27(4):2597-2333, 2017.
[51] Angelia Nedic and Asuman Ozdaglar. Distributed subgradient methods for multi-agent opti- mization. JEEE Transactions on Automatic Control, 54(1):48 2009.
[52] Yurii Nesterov. Introductory lectures on convex optimization: A basic course, volume 87. Springer Science & Business Media, 2003.
[53] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killcen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems (NeurIPS), pages 8024-8035, 2019.
[54] G. Qu and N. Li. Harnesssig smoothness to accelerate distributed optimization. IEEE Transac- tions on Control of Network Systems, 5(3):1245-11) 1260, 2018.
[55] Alexander Rakhlin, Ohad Shamir, and Karthik Sridharan. Making gradient descent optimal for strongly convex stochastic optimization. In International Conference on Machine Learning (ICML), pages 1571-1578, 2012.
[56] Aaditya Ramdas and Aarti Singh. Optimal rates for stochastic convex optimization under tsybakov noise condition. In International Conference on Machine Learning, pages 365-373, 2013.
[57] Alexander Rogozin, Mikhail Mikhailovich Bochko, Pavel E. Dvurechensky, Alexander V. Gasnikov, and Vladislav Lukoshkin. An accelerated method for decentralized distributed stochastic optimization over time-varying graphs. IEEE Conference on Decision and Control (CDC), 2021.
[58] Alexander Rogozin, Vladislav Lukoshkin, Alexander Gasnikov, Dmitry Kovalev, and Egor Shulgin. Towards accelerated rates for distributed optimization over time-varying networks. In International Conference on Optimization and Applications, 2021.
[59] Ali H Sayed. Adaptive networks. Proceedings of the IEEE, 102(4):4604497, 2014.
[60] Kevin Scaman, Francis Bach, Sébastien Bubeck, Yin Tat Lee, and Laurent Massoulié. Optimal algorithms for smooth and strongly convex distributed optimization in networks. In International Conference on Machine Learning (ICML), pages 3027-3036, 2017.
[61] Kevin Scaman, Francis Bach, Sébastien Bubeck, Laurent Massoulié, and Yin Tat Lee. Opti- mal algorithms for non-smooth distributed optimization in networks. In Advances in Neural Information Processing Systems (NeurIPS), pages 2740-2749, 2018.
[62] 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.
12

---

[63] Wei Shi, Qing Ling. Kun Yuan, Gang Wu, and Wotao Yin. On the linear convergence of the admm in decentralized consensus optimization. IEEE Transactions on Signal Processing. 62(7): 2014.
[64] Sebastian Urban Stich. Local sgd converges fast and communicates little. In International Conference on Learning Representations (ICLR), 2019.
[65]
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(22):5912-533)
2019.
[66] Hanlin Tang, Xiangru Lian, Ming Yan, Ce Zhang, and Ji Liu. d:: Decentralized training over decentralized data. In International Conference on Machine Learning, pages 4848-4856, 2018.
[67] Hanlin Tang, Chen Yu, Xiangru Lian, Tong Zhang, and Liu. Doublesqueeze: Parallel stochastic gradient descent with double-pass ceroo-compensatedd compression. In International Conference on Machine Learning, pages 6155-6165. PMLR, 2019.
[68] 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, pages 1-40, 2020.
[69] Jianyu Wang, Anit Kumar Sahu, Zhouyi Yang, Gauri Joshi, and Soummya Kar. MATCHA: Speeding up decentralized SGD via matching decomposition sampling. arXiv preprint 1rXiv:1905.09435, 2019.
[70] Dunean Watts. Small worlds: the dynamics of networks between order and randomness, 1999.
[71] Duncan J Watts and Steven H Strogatz. Collective dynamics of 'small-world networks. nature,
393(6684):440-444 442, 1998.
[72] Jun Wu, Mauricio Barahona, Yue-jin Tan, and Hong-zhong Deng. Robustness of random graphs based on graph spectra. Chaos: An Interdisciplinary Journal of Nonlinear Science,
22(4):043101, 2012.
[73] Ran Xin, Usman A Khan, and Soummya Kar. An improved convergence analysis for decen- tralized online stochastic non-convex optimization. IEEE Transactions on Signal Processing, 2020.
[74] Jinming Xu, Shanying Zhu, Yeng Chai Soh, and Lihua Xie. Augmented distributed gradi- methods for multi-agent optimization under uncoordinated constant stepsizes. In IEEE Conference on Decision and Control (CDC), pages 2055-2060, Osaka, Japan, 2015.
[75] Bicheng Ying, Kun Yuan, Yiming Chen, Hanbin Hu, Pan Pan, and Wotao Yin. Exponential graph is provably efficient for decentralized deep training. Advances in Neural Information Processing Systems (NeurIPS), 34, 2021.
[76] Hao Yu, Rong Jin, and Sen Yang. On the linear speedup analysis of communication efficient momentum sgd for distributed non-convex optimization. In International Conference on Machine Learning, pages 7184-7193. PMLR, 2019.
[77] Kun Yuan, Sulaiman Alghunaim, and Xinmeng Huang. Removing data heterogene- ity influence enhances network topology dependence of decentralized sgd. arXiv preprint
arXiv:2105.0802 2021.
[78] Kun Yuan, Yiming Chen, Xinmeng Huang, Yingya Zhang, Pan Pan, Yinghui Xu, and Wotao Yin. DecentLaM: Decentralized momentum SGD for large-batch deep training. In 2021 IEEE/CVF International Conference on Computer Vision (ICCV), 2021.
[79] Kun Yuan, Qing Ling, and Wotao Yin. On the convergence of decentralized gradient descent. SIAM Journal on Optimization, 26(3):1835-18)
2016.
[80] Kun Yuan, Bicheng Ying, Xiaochuan Zhao, and Ali H. Sayed. Exact difuusion for distributed optimization and learning Part I: Algorithm development. IEEE Transactions on Signal Processing. 67(3):708 723, 2019.
[81] Mikhail Yurochkin. Mayank Agarwal, Soumya Ghosh, Kristjan Greenewald, Nghia Hoang, and Yasaman Khazaeni. Bayesian nonparametric federated learning of neural networks. In International Conference on Machine Learning, pages 7252-7261. PMLR, 2019.
[82] Jiaqi Zhang and Keyou You. Decentralized stochastic gradient tracking for non-convex empirical risk minimization. arXiv preprint arXiv: 19tp::27122202 2019.
Checklist
1. For all authors...
13

---

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


Reviews:
[{"review_id": "j32MifwxW9c", "reviewer": "Reviewer_a2U2", "summary": "In this paper, the authors investigate the optimal convergence rate for smooth and nonconvex decentralized stochastic optimization. Specifically, given function class F_L, oracle class O_{\\sigma^2}, and weight matrix class W_{n,\\beta}, the authors establish a tight lower bound for any \\beta within (0,cos(\\pi/n)). An algorithm based on multiple-step gossip is also proposed.\n\nPost-rebuttal update: I have raised the score from 5 to 7.\n\n", "questions": "1. For the optimal rate of decentralized stochastic optimization algorithms, readers should be interested in the following question: “Given a network topology, what are the best algorithm and its rate?” In [33], the optimal rate is in the sense of “given a line network of n nodes, finding an optimal algorithm with the best weight matrix (and hence \\beta).” It is limited to the line topology, but consistent to our intuition. In this paper, the optimal rate is in the sense of “given a network of n nodes, finding the worst topology and corresponding weight matrix whose connectivity measure is \\beta, and finding an optimal algorithm.” This is a little bit confusing because in most cases we do not prefer the worst weight matrix. Please clarify.\n2. “Surprisingly, we find in MG-DSGD that the multiple gossip technique can significantly reduce the influence of data heterogeneity, and the gradient tracking step can be saved to achieve the convergence optimality.” Why?\n", "limitations": "N/A.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. A tight lower bound for any \\beta within (0,cos(\\pi/n)).\n2. An algorithm that matches the lower bound.\n\nWeaknesses:\n1. For the optimal rate of decentralized stochastic optimization algorithms, readers should be interested in the following question: “Given a network topology, what are the best algorithm and its rate?” In [33], the optimal rate is in the sense of “given a line network of n nodes, finding an optimal algorithm with the best weight matrix (and hence \\beta).” It is limited to the line topology, but consistent to our intuition. In this paper, the optimal rate is in the sense of “given a network of n nodes, finding the worst topology and corresponding weight matrix whose connectivity measure is \\beta, and finding an optimal algorithm.” This is a little bit confusing because in most cases we do not prefer the worst weight matrix. Please clarify.\n2. Related to the above comment. From the very beginning the authors mention that “this paper revisits non-convex stochastic decentralized optimization and establishes an optimal convergence rate with general weight matrices.” Weight matrix design should be a part of algorithm development. I cannot fully understand the necessity of finding the worst weight matrix.\n3. In the problem setup the authors talk about the zero-respecting policy, but do not mention it in the proof.\n4. “Surprisingly, we find in MG-DSGD that the multiple gossip technique can significantly reduce the influence of data heterogeneity, and the gradient tracking step can be saved to achieve the convergence optimality.” Why?\n5. Mistakes: The degree of a 10-node complete graph is 9, not 10. In Line 3 of Algorithm 2, z_i^{(r)} should be z_j^{(r)}.\n6. For these reasons, I recommend “borderline accept” and would like to see further clarifications from the authors.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "ehW3jgtLmsq", "reviewer": "Reviewer_Xrfd", "summary": "The paper study optimal convergence rates in  decentralized nonconvex (smooth) optimization and develops algorithms to achieve such lower complexity bounds up to log factor. More specifically the key contributions are:\n\n(i) Establishing optimal convergence rates for smooth, non convex stochastic optimization for  mesh networks compliant with gossip matrices whose connectivity measure is not $\\cos(\\pi/n)$, where $n$ is the number of agents. Example of such graphs are grids, hypercubes, toruses, etc. Previous literature considered lower complexity bound only for linear graphs. \nThe authors established lower complexity bounds for ring-lattice graphs, for connective values within $[0,cos(\\pi/n)]$; for large $n$ the interval spans [0,1].  A key enabler of such new results is a tight relationship between the connectivity of the graph and its diameter, a fact that was established before for linear graphs (meaning connectivity values equal to $\\cos(\\pi/n)$). \n\n(ii) By modifying properly the distributed SGD algorithm, the authors provide a solution method that achieve lower complexity bounds. Differently from the existing method, DeTAC, still achieving lower complexity bounds, the proposed algorithm does not require gradient tracking and hence save one communication (O(d)) per iteration. \n\n(iii) The authors extend the results above  to the case of nonconvex functions satisfying the PL condition.", "questions": "Is the proof of lower complexity bounds in Th. 2 significantly different from [38], once the connection between the connectivity and the diameter of ring-lattice graphs is established?\n\nThe convergence proof of DSGD has been already established in the literature , e.g. in [12, 25]. I think it would be useful if the authors can elaborate in the paper (and in their reply) on the key difference in their analysis, which lead to slightly different results. What was the key enabler for that?\n\nDo the author have some intuition why MG-DSGD can deal with data heterogeneity's efficient as gradient tracking methods? It would be good to provide some inside substantiated by some technical reasoning.  \n\nI would write the upper bounds making explicitly the dependence on L and b, to be consistent with the presentation of complexity bound in the literature. Is the dependence on these parameters of the same order of that in the literature?\n\nI would change the merit function using to measure stationarity: the current one does not capture consensus errors. I would include a consensus error term rather than considering only the gradient along the average. The average is representative of the local iterates only when the consensus error is sufficiently small. It is true however that the consensus error decays faster than the optimization one, but still I would consider a more comprehensive merit function to measure performance of the algorithm. ", "limitations": "See my comments above under weaknesses.", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n The paper advances the state of the art on SDGD-like algorithms for smooth, nonconvex problems. The authors identified a gap in the literature (the lower complexity bound were established for a restricted class of gossip matrices and associated graphs) and provide a solution to it. The overall presentation is good and the paper is easy to read. The comparison with the state of the art is satisfactory (to my knowledge). \n\nWeaknesses: \nOn the technical side, it is not very clear which new technique has been developed in the proofs to derive some of the results. For instance, once the connection between the connectivity and the diameter of ring-lattice graphs is established, it seems that the proof of Th.2 follows the same path of that in [38]. Same comment apply to the convergence analysis of DSGD; except of a suitable choice of the learning rate, I see a fairly standard proof. Since the proposed MG-DSGD has the same structure of the vanilla DSGD (with a different gossip matrix and a gradient accumulation), same comment applies to its proof of convergence. I do not find the proof under PL particularly more difficult than under strong convexity, the functional relationship between the optimality gap and gradient steps is basically the same.\n\nI would not consider MG-DSGD a new algorithm: it is the DSGD with multiple consensus steps (accelerated) and batch gradients. Both features have been extensively used in the literature.  What is unclear is why the acceleration via multiple round of consensus copes with the data heterogeneity and allows one to get ride of the gradient tracking, which is notoriously known to be beneficial under data heterogeneity. \n\n ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "c08_tcObUJU", "reviewer": "Reviewer_oRXZ", "summary": "This paper revisits non-convex stochastic decentralized optimization and extends existing convergence analysis with special weight matrices to establish an optimal convergence rate with general weight matrices. The algorithms proposed has a convergence rate that matches DeTAG's rate but avoids gradient tracking and saves half of the communication overheads per step.", "questions": "Is it possible for a time-varying communication pattern to improve the convergence? It will be nice to include the discussion if some conclusions can be drawn.", "limitations": "N/A", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper studies decentralized optimization algorithm over general communication weight matrix, but the weight matrix has to be fixed over time, so it does not seem to apply to decentralized algorithms where the communication pattern is different in different steps.\n\nWhen the matrix is fixed, the paper proves the optimal convergence rate for nonconvex objectives (where the lower bound and upper bound match). Also an algorithm MG-DSGD is proposed to achieve that optimal convergence rate while being simpler and less communication costy than existing algorithms such as DeTAG.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "WSzVRiWkmSz", "reviewer": "Reviewer_o2Rv", "summary": "The paper considers decentralized stochastic non-convex optimization problems. The main innovation is the new structure of the connection graph, which can be used to revisiting the lower bounds. In a supplement, the authors apply this graph structure to obtain lower estimates in the non-convex case. Finally, the authors present an algorithm based on FastGossipAverage which achieves lower bounds.  ", "questions": "The question is about experiments. It is rather rhetorical and I am just interested in your opinion here. \n\nI sometimes have to work with the learning problems on decentralized architectures. Despite the fact that I have a quite good theoretical experience in gossip protocol, we never use it (neither with single step, nor with multi steps). It's easier to use tricky all-reduce procedures. For me gossip protocol is about simpler tasks and simpler computing devices (not powerful GPU), for example about signal processing and transmission. \n\nWhat do you think about it?", "limitations": "No potential negative societal impact", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n\n1) The new ring-based graph structure is interesting to me. Previous methods of deriving lower bounds consist in that we fix $\\beta$ (in the literature it is also $\\chi$), on the basis of this $\\beta$ a connection graph (typically a path) with some number of vertices $n$ is constructed. The new graph structure allows to fix not only $\\beta$ but also $n$. This can be important. \n\n2) The rest of the results, including lower bounds for non-convex problems (in the general case and in the PL case), the algorithm that achieves these lower bounds, and the experiments, complement the paper well.\n\n3) The article is quite well written and easy to follow. The literature review is satisfactorily done. \n\n**Weaknesses:**\n\n1) It is a pity that the new graph construction works only for $\\beta \\in [0; \\cos \\pi/n]$.\n\n2) Unfortunately, the rest of the results of the work, except for the construction of the graph are not particularly interesting. Most of them are obvious and represent a simple combination of existing works. Read more below.\n\n3) Lower bounds in the general non-convex case can be obtained by simply replacing the graph in the available results in the literature.\n\n4) Lower bounds in the PL case are actually made for the strongly convex case, and this also can be done by simply replacing the graph in the available results. I also do not like that in the main paper the estimates in the PL case does not show the dependence on the factor $L/\\mu$. It replaces by $C$. Most likely this is due to the fact that in the lower bounds $C = \\sqrt{L/\\mu}$, and in the upper estimates $C = L/\\mu$. This spoils the optimality of the algorithm, and perhaps the authors want to hide it.\n\n5) The algorithm, which is set as optimal, is simply an analysis of SGD with inexactness + gossip consensus. Such results are obvious and do not cause much interest.\n\n**Conclusion:**\n\nIn this paper the interesting thing is the construction of the new graph, with which one can get more accurate lower bounds. The rest of the facts (including experimental ones) complement the paper and make it more solid, but for me are minor in comparison with the new graph. I am hesitant to decide on acceptance and would like to discuss with fellow reviewers and AС their impressions of the paper. I put a borderline reject, but I'm ready to easily change it after discussion.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept