Communication-Efficient Topologies for Decentralized Learning with $O(1)$ Consensus Rate
Authors: Zhuoqing Song
Weijian Li
Kexin Jin
Lei Shi
Ming Yan
Wotao Yin
Kun Yuan
Venue: NeurIPS 2022 Accept (2022)
Keywords: Decentralized optimization
network topologies
maximum degree
consensus rate
communication-efficient

Abstract: Decentralized optimization is an emerging paradigm in distributed learning in which agents achieve network-wide solutions by  peer-to-peer communication without the central server. Since communication tends to be slower than computation, when each agent communicates with only a few neighboring agents per iteration, they can complete iterations faster than with more agents or a central server. However, the total number of iterations to reach a network-wide solution is affected by the speed at which the information of the agents is ``mixed'' by communication. We found that popular communication topologies either have large degrees (such as stars and complete graphs) or are ineffective at mixing information (such as rings and grids). To address this problem, we propose a new family of topologies, EquiTopo, which has an (almost) constant degree and network-size-independent consensus rate which is used to measure the mixing efficiency.

In the proposed family, EquiStatic has a degree of $\Theta(\ln(n))$, where $n$ is the network size, and a series of time-varying one-peer topologies, EquiDyn, has a constant degree of 1. We generate EquiDyn through a certain random sampling procedure. Both of them achieve $n$-independent consensus rate. We apply them to decentralized SGD and decentralized gradient tracking and obtain faster communication and better convergence, both theoretically and empirically. Our code is implemented through BlueFog and available at https://github.com/kexinjinnn/EquiTopo.

Communication-Eficien Topologies for Decentralized Learning with ((1) Consensus Rate
Zhuoqing Song'; Weijian Li Kexin Jin Lei Shi Ming Yan*.5, Wotao Yin', Kun Yuan 2.6
Fudan University Alibaba DAMO Academy Pprinceton University
"The Chinese University of Hong Kong, Shenzhen "Michigan State University
Peking University 'Shanghai Artificial Intelligence Laboratory
gggoon190ffun edu. en, weijian. 110al bbaba-inn... kexinj @math, princeton. edu
yanmingecuhk. edu. cn, leishi@fudan www.fuunnnuuuu...ee.e. edu. on
notao.y.neaalbbba-inee
kun www.yyaaaaaaaaaaiieeeee..
Abstract
Decentralized optimization is an emerging paradigm in distributed learning in which agents achieve network-wide solutions by peer-to-peer communication with- out the central server. Since communication tends to be slower than computation, when each agent communicates with only a few neighboring agents per iteration, they can complete iterations faster than with more agents or central server. How- ever, the total number of iterations to reach a network-widk solution is affected by the speed at which the agents' information is "mixed" by communication. We found that popular communication topologies either have large maximum degrees (such as stars and complete graphs) or are ineffective at mixing information (such as rings and grids). To address this problem, we propose a new family of topologies, EquiTopo, which has (almost) constant degree and network- wwwooor--siz-iidde size-indeeendent consensus rate that is used to measure the mixing efficiency.
In the proposed family, EquiStatic has a degree of ((I(n)), where n is the network size, and series of time-dependent one-peer topologies, EquiDyn, has constant degree of 1. We generate EquiDyn through a certain random sampling procedure. Both of them achieve an r-independent consensus rate. We apply them decentral- ized SGD and decentralized gradient tracking and obtain faster communication and better convergence, theoretically and empirically. Our code is implemented through BlueFog and available at battps://gitaai com wwwp:/eeioeeeiinieeiceiee wtt.exiiiiiiinnnuuuuooooooo EquiTopo
1
Introduction
Modern optimization and machine learning typically involve tremendous data samples and model parameters. The scale of these problems calls for efficient distributed algorithms across multiple computing nodes. Traditional distributed approaches usually follow a centralized setup. where each node needs communicate with a (virtually) central server. This communication pattern incurs significant communication overheads and long latency.
Decentralized learning is emerging paradigm to communications in large-scale optimization and learning. In decentralized learning, all computing nodes are connected with some network topology (e.g., ring, grid, hypercube, etc.) in which each node averages/communicaes locally with its immediate neighbors. This decentralized setup allows each node to communicate with fewer neighbors and hence has much lower overhead per-iteration communication. However, local averaging is less effective in "mixing" information, making decentralized algorithms converge slower
"Equal Contribution. Corresponding Author: Kun Yuan
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Table 1: Comparison between different commonly-used topologies. "Static Exp.": static exponential graph:
"O.-P. Exp.": one-peer exponential graph; "E.-R. Rand": Erdos-Renyi random graph ((n. p) with probability
(1 + a] In(n)/n for some a > 0: "Geo. Rand": geometric random graph G(n, r) with radius r (1+ a) In(n)/n n for some 0. Undirected graphs admit symmetric gossip matrices. If some graph has
dynamic pattern, its associated gossip matrix will vary at each iteration.
Topology
Connection
Pattern
Degree
Consensus Rate
size n. arbitrary arbitrary
Ring
12
undirect.
static
(1)
1-1(1/2²)
Grid
22
undirect.
static
(
1 1- ((((n(((z)
Torus
22
undirect.
static
(1)
(1/nn)
arbitrary
Hypercube 31
undirect.
static
(In(n))
1 (-1(1/)(())
power of 2 arbitrary
Static Exp. 37
directed
static
(In(n))
(1/Imm)())
O.-P. Exp. 37
directed
dynamic
1
finite-time conv.'
power of 2 arbitrary
R. Rand 22
undirect. undirect.
static
θ (In(n))
((1)
Geo. Rand
static
θ (In(n)
1 1-0(Inn)/n))
arbitrary
D-EquiStatic
directed
static
o (In(n))
p E (0,
arbitrary
U-EquiStatic
undirect.
static
e (In(n))
PE 1)
arbitrary
OD-EquiDyn
directed
dynamic
1
V (1+
arbitrary
OU-EquiDyn
undirect.
dynamic
(22 + p)/3
arbitrary
One--per exponential graph has finite-time exact convergence only when n the power 2.
([m(m)) is the averaged degree; its maximum degree can be O(n) with non-zero probability.
Constant p θ (1) is independent of network-size
than their centralized counterparts. Therefore, seeking balance between communication efficiency and convergence rate in decentralized learning is critical.
The network topology (or graph) determines decentralized algorithms' per-iteration communication and convergence rate. The maximum graph degree controls the communication cost, whereas the connectivity influences the convergence rate. Intuitively speaking, densely-connecter topology enables decentralized methods to converge faster but results in less efficient communication since each node needs to average with more neighbors. Selecting appropriate network topology is key to achieving light communication and fast convergence in decentralized learning.
1.1 Prior arts in topology selections
Gossip matrix and consensus rate. Given connected network of size n and its associated doubly- stochastic gossip matrix W E RR (see the definition in & ( its consensus rate , determines how effective the gossip operation W to mix information (see more explanations in $ $ It is long-standing topic in decentralized learning to seek topologies with both small maximum degree and fast consensus rate (i.e., small 8 as close
possible).
Static graphs. Static topologies maintain the same graph connections throughout all iterations. The directedness, degree, and consensus rate of various common topologies summarized in Table The ring, grid, and torus graphs (22 are the simplest sparse topologies with O(1) maximum degree. However, their consensus rates quickly approach as network size n increases, which leads to inefficient local averaging. The hypercube graph (31 maintains a nice balance between degree and consensus rate since In(n) varies slowly with However, this graph cannot be formed when size n is not the power of 2. The static exponential graph extends hypercubes to graphs with any size n, but its directed communications cannot enable symmetric gossip matrices required in well-known decentralized algorithms such as EXTRA (28). Exact-Diffusio [40), NIDS [16), D² [30]. Two widely-used random topologies, i.e., the Erdos- Renyi graph 20 3 and the geometric random graph [4] [. are also listed in Table It is observed that the Erdos- Renyi graph achieves a network- size-ine indeeeeddddent consensus rate with (In(n)) averaged degree in expectation. However, is worth noting that the communication overhead in network topology is determined by the maximum degree. Since some nodes may have much more neighbors than others in a random realization, the maximum degree in the Renos graph can be ((n) with a non-zero probability. Moreover, the random graphs listed in Table are undirected. The may not be used in scenarios where directed graphs are preferred.

---

Dynamic graphs. Dynamic graphs allow vary-ig topologies between iterations. When an exponential graph allows each node cycle through all its neighbors and communicate only to When the network size n is the power of sequence of one-peer exponential graphs can together achieve periodic global averaging. However, its consensus rate is unknown for other values of n. A closely related work Matcha [34] proposed a disjoint matching decomposition sampling strategy when training learning models. While it decomposes a static dense graph into series of sparse graphs with small degrees, the consensus rates these dynamic graphs are not established.
single node per iteration, we achieve the time-varying one-peer exponential graph 2 37
Finally, it is worth noting that the consensus rates of all graphs (except for the Erdos Menls- graph) discussed above are either unknown or dependent on size n. Their efficiency in mixing information gets less effective as goes large.
1.2 Main results
Motivation. Since existing network topologies suffer from several limitations, ask the follow- ing questions. Can we develop topologies that have (almost) constant degrees and network-size- independent consensus rates that admit both symmetric and asymmetric matrices of any size? Can these topologies allow one-peer dynamic variants? This paper provides affirmative answers.
Main results and contributions. This paper develops several novel graphs built upon set of basis graphs in which the label difference between any pair of connected nodes are equivalent. With general name EquiTopo, these new graphs can achieve network-size-inder while maintaining (almost) constant graph degrees. Our contributions are:
consensus rates
We construct a directed graph named D-EquiStatic that has a network wirvvork-szze--ee iize-inneeendent consensus rate p with degree (In(n)). Furthermore, we develop an one-peer time-varying variant named OD-EquiDyn to achieve a wwwwoo---izz-iideeeedeeeee consensus rate with degree 1.
We construct undirected graph U-EquiStatic, which has a network-size weaek-szzz-iiiiie independent consensus rate p with degree (In(n)). It admits symmetric gossip matrices that are required by various important algorithms. We also develop an one-peer time-varying and undirected variant named OU-EquiDyn achieve a wwwtooo-sizz-inddeeeddeeee consensus rate with degree 1.
We apply the EquiTopo graphs to two well-known decentralized algorithms, i.e., decentralized
stochastic gradient descent (SGD) 6 17 12 and stochastic gradient tracking (SGT) 23 36
7,35). to achieve the state-of-the-art convergence rate while maintaining ((n(n)) (with D/U- EquiStatic) or 1 (with ODuDU-E degree in per-iteration communication.
The comparison between EquiTopo and other common topologies in Table shows that the EquiTopo family (especially the one-peer variants) has achieved the best balance between maximum graph degree and consensus rate. The comparison between EquiTopp and other common topologies when applying to DSGD and DSGT are listed in Tables and 4 in Appendix C.2 and Table
Note. This paper considers scenarios in which any two nodes can be connected when necessary. The high-perffrmance data center cluster is one such scenario in which all GPUs are connected with high-bandwidth channels, and the network topology can be fully controlled. EquiTopp may not be applied to wireless network settings where two remote nodes cannot be connected directly.
1.3 Other related works
In decentralized optimization, decentralized gradient descent 224
6 26 39
and dual averaging S are
well-known approaches. While simple and widely used, their solutions are sensitive to heterogeneous data distributions. Advanced algorithms that can overcome this drawback include explicit bias-
correction 228
40 16,, gradient tracking 23
25 36). and dual acceleration 27 33 Decentralize
SGD is extensively studied in
[6
17
2 to solve stochastic problems. It has been extended to
directed 2 37 or time-varying topologies
37], asynchronous settings 18] and data- to achieve better performances.
heterogencous scenarios
30 35
3

---

u 3
U == 4
a = 5
Figure
The set of the basis graphs (G(A())))
2 Notations and Preliminaries
Notations. We let ,,, IR" be the all-ones vector and I E Rax= be the identity matrix. Furthermore,
we define J = 11 11, 17 and = J. matrix = [aayl E Rax= is nonnegative if oij 2 for all 1 < <ijj
1, Ln. Given a matrix A [2mxx, | lll is its spectral norm. For æ E R", [x || is its Euclidean norm. We let n). Throughout the paper, we define mod operation that returns value in [m] as
A nonnegative matrix A is doubly stochastic if A1,
[n] =1, f1,
{
if i = kn + & for some & Z and & E [n - 1), if kn for some Z.
i mod
(1)
Network. Given a graph G(V,E) E) with a (j,i) & means node j can directly send information to node i. For undirected graphs, (j, i) E & if and only (i,j) &. Node i's degree the number of its in-neighbors ()) E EHH. one-peer graph means that the degree for each node is at most 1.
nodes V and set of directed edges An edge
Weight matrices. To facilitate the local averaging step in decentralized algorithms,, each graph is associated with a nonnegative weight matrix W = [[ay]= R=**" whose element Way is non-zero only if (j, i) E & = j. One benefit of an undirected graph that can be associated with symmetric matrix. Given nonnegative weight matrix W E Roxn, we let G W) be its associated graph such that (j. & if way and 7
Consensus rate. For weight matrices { ( Je20 S R"Xn, the consensus rate B is the minimum nonnegative number such that for any 2 0 and vector æ E I2" with the average ã = - Zi.
E
(1) x - x. 1n
g o F 1..1
or equivalently, E
II (4)
< 82 | For (
W, essentially equals [[
3 Directed EquiTopo Graphs
3.1 Basis weight matrices and basis graphs
Given graph of size n, we introduce set of doubly stochastic basis matrices {A (a,))p==) where (u.m) = [a. (u.m)] E IR" TR* with
if i mod n,
(j+ if i-
(u,n)
Oij
(2)
0, otherwise.
Their associated graphs {g( (G(Alo (u.n) (u.)) |ao are called basis graphs. A basis graph G ((.n)))) has degree one and the same label difference (i -)) mod n for all edges (j.i). The set of five basis graphs {g( (=. for n = 6 shown in Fig. | When n is clear from the context, we omit and write A (1) instead.
3.2 Directed static EquiTopo graphs (D-EquiStatic)
Our directed graphs are built on the above basis graphs, and a weight matrix has the form
W
ΣM -i= A (w.).
(3)
M

---

where E [n 1] and M > O is the number of basis graphs we will sample. Throughout this paper, the multiset {u, [=] are called basis index. It is possible that u, u for some * j. Since each (w) has the form (2), the matrix W is doubly stochastic, and all nodes of the directed graph G W) have the same degree that no more than M.
Since G W) is a directed static graph and built with M basis graphs, we name it D D-EqiStaaic. The following theorem shows that we construct weight matrix W such that its consensus rate is independent of the network size n by setting M properly. The proofs of all theorems are in the Appendix.
Theorem Let A (w) be defined by (2) for any u E [n - 1]. For any constant E (0,1), we can choose a sequence of u1.... uM from (n - 1] with M = (In (n) (n)/p²) /²²) and construct the D-EquiStatic weight matrix W as in (3) such that the consensus rate of W is p. i.e.
II W æ S |
Væ I="
(4)
The graph G W) has degree at most M. In the following, we will just say that the degree is ((I(n))). constant, e.g., p 0.5. A method of constructing D-EquiStatic
As p is tunable, choose weight matrix W can be found in Appendix A.1
Remark Compared to all common topologies listed in Table 7 D D-EqiiStatic achieves a better balance between degree and consensus rate. Moreover, D-EquiStatic works for any size 2 Different from the Enlos-Renyy random gruph and the geometric random graph, whose degree cannot be predefined before the implementation, can easily specify the degree M for D- A-EqqiStatic.
3.3 One-peer directed EquiTopo graphs (OD-EquiDyn)
While D-EquiStatic achieves a size-independent consensus rate with (II(()) degree, we develop one-peer dynamic variant further reduce its degree. Given weight matrix W of form (3) and its associated basis matrix {
(wx) ) /== the one-peer directed variant, or OD-EquiDyn for short, samples a random A (w) per iteration and utilizes it as the one-pes on-ppeer weight matrix, see Alg. Since each node in G ((A% (a)) has exactly one neighbor, the graph G w(() (9) has degree one for every iteration t.
Note that W (4) is random time-varying weight matrix. Its consensus rate (in expectation) can be characterized as below.
Algorithm 1: OD-EquiDyn weight matrix generation at iteration
Input:
constant 7) E (0, 1); basis index {w1, U2,..., uM) from a weight matrix W of form Pick 2y from uniform distribution over the basis index (M1, "2....,,MM.
Produce basis matrix A (*)) according to (2)
Output: (t)) (1 I + n (o))
Theorem Let the one-peer directed weight matrix W be generated by Alg. 1 It holds that
|
[ (1- 27((1 - 7)) p)) ||]x|| Vo R
E
where p the consensus rate of the weight matrix W (which can be tuned freely as Theorem 7
Remark The OD-EquiDyn graph has a degree of 1 no matter how dense the imput matrix W is. When 1) 1/2, which is used in our implementations, holds that I W (t) xl|2 < (1 p)/2 |T 2| for any a E R Thus, the OD-EquiDyn graph maintains the same ((1) degree as ring. grid, and the one-peer exponential graph but with a faster iize-independent consensus rate.
Remark For basis index {1. n 1} (W- J), Alg. 7 returns a sequence of OD-EquiDyn
graphs with BI[TI W/ x: 1|2 < |I when vi = 2 because [IJ] = 0 implies =
Remark Although the Erdos--eed Renyi random graph also enjoys O11) consensus rate (In(n)) average degree (see Table 7). its maximum degree could be as large ((n) which implies that
5

---

1
1 =
==1,=
1,u -
Figure A few realizations of the OU-EquiDyn graphs for n = 6, 8 1. and a (1,2,3.4,5)
Erdos-Renyi Renyi random graphs could be highly unbalanced. Moreover, Brdos-Renyy random graphs are undirected graphs, while EquiStatic graphs can be both directed (Section 3 and undivected (Section(4), In addition, the structure of EquiStatic allows simple construction of one-peer random graphs which preserve ((1) consensus, while it is still an open problem on whether Erdos-Renyi random graphs admit one-peer variants with (11) consensus rate.
4 Undirected EquiTopo Graphs
The implementation of many important algorithms such as EXTRA 228 Exact-Diffusion 40
NIDS [6], decentralized ADMM [29]. and the dual-based optimal algorithms 27 33 rely on symmetric weight matrices. Moreover, devices in full-duplex communication systems can communicate with one another in both directions, and undirected networks are natural be utilized. These motivate us to study undirected graphs.
4.1 Undirected static EquiTopo graphs (U-EquiStatic)
Given a D-EquiStatic weight matrix W and its associated basis matrices {A (4 construct an undirected weight matrix name U-EquiStatic by
Ji= we directly
W
W + W = 2M ΣM (A (w.) + (((1)))
(5)
whose basis index are fu,, uz M
1 because A (-w) [A ("IT.
Since W is built upon W and IIW- = WII, the following theorem follows directly from
1 nW III m 2
1 (Inllll 2
[II ||(
IIW
||II 1l2
Theorem Let W be D-EqqiStatic matrix with consensus rate p and W be the U-EquiStatic matrix defined by (5) It holds that
IW x s [I]|] Va Rd.
(6)
4.2 One-peer undirected EquiTopo graphs (OU-EquiDyn)
Constructing one-peer undirected graph OU-EquiDyn is not direct U-EquiStatic because ] (AA()) (1) [[A (1)TT) admits graph with degree 2, Appendix B.1 for illustration.
Alg. shows a method to construct a series of OU-EquiDyn matrices with degree 1. Starting from
node we connect a node with the th node after it, as long as both of them have not been connected any other nodes. Fig. 2 iillustrates the process when s 1 and u I.... 5 for a network of size 6. Some nodes have no neighbors at realizations = 2 and the restriction that each node has no more than one neighbor. For instance, when 2, node wants to connect with node but node has already been connected to node 3. Thus, there exist node pairs that are never connected when s = 1. To resolve this issue, we let the starting index s be sampled randomly from [n). Fig. 8 8lin Appendix B. illustrates the scenarios when = 3. It is observed that the pairs (3. 5} and (4, 6) are now connected each other. The node version OU-EquiDyn
4. This phenomenon is caused by
illustrated in Alg. 4 of Appendix. B.2

---

Algorithm 2: OU-EquiDyn weight matrix generation at iteration
Input: 7) E (0, 1); basis index {Ui, -u; i== from symmetric weight matrix W Ruxx of form 5
Pick ey [u;, -= and 8, [n]] uniformly at random;
Initialize A = [asg] = and b; = 0, vi E [n];
for j = ( :8: +
mod n2) do
i == [j+ (++4) mod m
b; = and b = then
0ij aji = (n - 1)/n;
an ajj 1/n;
b; = 1. bj = 1;
end
end
Output: W (4)
(1 1)) + nA
Let W be U-EquiStatic matrix with consensus rate p. and W (3) be an DU-EquiDyn
Theorem
matrix generated by Alg. 2 holds that
E
2 51- 51- p))
| Vo ER.
Remark Theorem CheoremAinng Himplies that the OU-EquiDyn graph can achieve a size-independent consensus
rate with degree at most 1. When v = 1/2, holds that T (1),, x: < + p
When W = JJ and the basis index (1,
1} are input to Alg. we obtain an OU-EquiDyn
W (t) 2=1 S (2/3)
sequence W such that I
Remark An alternative OU-EquiDyn matrix construction that relies on the Euclidean algorithm in Appendix B.4
5 Applying EquiTopo Matrices to Decentralized Learning
We consider the following distributed problem network of computing nodes:
min f(z) aERd
Σ f((z)
where fi(w) :- [Fx; The function f(( is kept node i, and & denotes the local
data that follows the local distribution D, Data heterogeneity exists if local distributions {D;) are identical. Throughout this section, we let x be node i's local model iteration and a (t) = - a
Assumptions. We make the following standard assumptions facilitate analysis.
A.1 Each local cost function f((x)) differentiable, and there exists constant L > such that [V) f.))l) < L for all x. y Rdd
A.2 Let g:¹ (F(a(") 19 (.))) There exists o² > 0 such that for any and i
Vfi(=!">\l s E BD a Vf((a((), and Eelh 99 (
A.3 (For DSGD only) There exists b² such that Σ [v)) [ < 12 for all Rd.
5.1 Decentralized stochastic gradient descent
The decentralized stochastic gradient descent (DSGD) 6 12
given by
x ((+1)
Σド=
w
(1)
(z) -9
(0) (0)
(8)
7

---

where the weight matrix W = [
can be time-varying and random. Applying the EquiTopo matrices discussed in we achieve the following convergence results, whose proof follows Theorem 2 in [12 directly, and is omitted here. More results for DSGD are given in Appendix C.1
[0]
Theorem Consider the DSGD algorithm 8
Under Assumptions A.I-A.3, it holds that
Bio
3513
T+1 Σ B V B
=0
VnT
T B)3
Tă 3)
T(1 3)
where 3 p with D-EquiStatic W or U-EquiStatic W;
where 3 = v(1+ (1++0) for OD-EquiDyn ( (Alg. with = 1/2),. and = p)/3
OU-EquiDyn W (0) (Alg. with v 1/2).
For sufficiently large T, the term O(L/VnI) dominates the rate, and we say the algorithm reaches the linear speedup stage. The transient iterations are referred to as those iterations before an algorithm reaches the speer-speedup stage. We compare the per-iteration communication, convergence rate, and transient iterations of DSGD over various topologies in Tables and a of the Appendix. It is observed that OD/OU-EquiDy endows DSGD with the lightest communication, fastest convergence rate, and smallest transient iteration complexity.
5.2 Decentralized stochastic gradient tracking algorithm
The decentralized stochastic gradient tracking algorithm (DSGT) 23 25
36
35
is given by
(6) (2) - 1 ))) ((+1) = -ド= wi (x)
a
= -Ø wi y + gi (++1)
(t) (e)
y g: (0)
(0)
The following result of DSGT does not appear the literature since it admits an improved convergence rate for stochastic decentralized optimization over asymmetric Existing works on DSGT assume weight matrix to be either symmetric [1 or static 35
varyvig weight matrices.
Theorem Consider DSGT algorithm in 9 If W (6) f620 have consensus rate 3, then under Assumptions A. A-12, holds for T T-3 that
T
1 T+1
Σ E L=
[0] o VnT (1 - Byr3 (1 - 1
When utilizing the EquiTopo matrices, the corresponding is specified in Theorem 5 Note that DSGT achieves linear speedup for large T. The per-iteration communication and convergence rate comparison of DSGT over different topologies in Table OD/OU-FquiDyn endows DSGT with the lightest communication, fastest convergence rate, and smallest transient iteration complexity.
6 Numerical Experiments
This section presents experimental results validate EquiTopo's wwwtwork-size-iddeeee consensus rate and its comparison with other commonly-used topologies in DSGD on both strongly-conve problems and non-convex deep learning tasks. More experiments for EquiTopo in DSGT and all
implementation details are referred to Appendix D
Network-size independent consensus rate. This simulation examines the consensus rates of all
four EquiTopp graphs. We recursively run the gossip averaging ar (++1) (0)) with (0) T
initialized arbitrarily and (t) [ generated as D-EquiStatic (Eq. ), OD-EquiDyn (Alg.
U-EquiStatic (Eq. (5)) and OU-EquiDyn (Alg. 2) respectively. Fig. 3 depicts how the quantity
[(x)(() - (o) evolves when ranges from 1000 to 10, 000 with D-FEuiSttati topology. See
Appendix D for all other EquiTopo graphs, which also achieve network-size independent consensus
rates when n varies. These results are consistent with Theorems -

---

Table 2: Per-iteration communication and computation complexity of DSGT under different topologies.
Topology
Per-iter Comm.
Convergence Rate
Trans. Iters.
Ring
@(1)
n
O(n16)
VnT
T
Torus
((1)
0
na3
n²
Onr))
VnT
73
Static Exp.
(Im(n))
In(n) 8
(n)
O In))
VnT
T
T
O.-P. Exp.
In(n)a 3
In
O(
Vnl
73
D(U)-EquiStatic
((n(n))
+
0
O(18)
VnT
7
7
OD (OU)-EquiDyn
+
O(n))
vnT
7
DiEquiStatic
10a
10a
1000
10
2000
3000
10-
1 xx
10-3
4000
5000
10
10000
Ring
10
Grd
10
0. Exp.
10-11
OU-EquiDyn
20
40
60
80
100
120
25
50
75
100
125
150
175
200
Iteration
Figure 4: EquiDyn faster than other topologies (i.e., ring, grid, and one-peer exponen- tial graph) with @(1) degree in consensus rate.
Figure 3: The D-EquiStatic topology can achieve
network-size independent consensus rate.
Comparison with other topologies. We now compare EquiTopp's consensus rate with other commonly-used topologies. Fig. illlsstrates the performance of several graphs with O degree when runming gossip averaging. We set n = 4900 so that the grid graph can be organized as 70 x 70. OD/OU-EquiDyn is much faster than other topologies. Note that each node in OD-EquiDyn, OU- EquiDyn, and O.-P. Exp. has exactly one neighbor per iteration. More experiments on graphs with (In(n)) degrees and on scenarios with smaller network sizes are in Appendix D
DSGD with EquiTopo: least-square. We next apply D/U-EquiStatic graphs to DSGD when solving the distributed least square problems. In the experiment, we let D/U-EquiStatic has the same degree as the exponential graph. Fig. | dldppcts that D/U-EquiStatic converges much faster than static exponential graph, especially in the initial stages when the learning rate is large. The U-EquiStatic performs slightly better than D-EquiStatic since its bi-directional communication enables the graph with better connectivity.
300 and set M 9 so that
DSGD with EquiTopo: deep learning. We consider the image classification task with ResNet- 20 model [9] over the CIFAR- 10 dataset [1]. We utilize BlueFog (38 to support decentralized communication and topology setting in a cluster 17 Tesla P100 GPUs. Fig. 6 fiillustrates how D/U- EquiStatic compares with static exp., ring, and centralized SGD in training loss and test accuracy. It observed that D/U-EquiStatic has strong performance. They achieve competitive training losses to centralized SGD but slightly better test accuracy. Meanwhile, they also outperform static exponential graphs in test accuracy by a visible margin (D-FquiStatic: 92%. U-EquiStatic: 91.7%, Static Exp.: 91.5%) Experiments with EquiDyn topologies and results MNIST dataset [15] are in Appendix

---

16a
Static Exp. xp -0.80
E-EqiSttatic 00 06
CquiStatic A,
10
10
60
100
Iterationn
Figure D/U-EquiStatic DSGD. Xa the second largest eigenvalue.
Centraiize SGD
Ring Exp.
1.75
1.50
U-LquiStatic
0.8
EquiStatic
Rest Accuracy
1.25
0.7
0.91
train
1.00
0.6
100
120
0.100
0.75
Centrelieed SGD
0.50
0.075
Ring
0.4
Static Exp.
U-EquiStatic
EquiStatic
0.3
0
20
40
60
80
100
120
0
20
40
60
80
100
120
Figure 6: Train loss and test accuracy comparisons among diffcrent topologies for ResNet-20 CIFAR-10.
7 Conclusion
This paper proposes EquiTopo graphs that achieve a state-of-the-art balance between the maximum degree and consensus rate. The EquiStatic graphs are with (In(n)) degrees and n-independent consensus rates, while their one-peer variants, EquiDyn, maintain roughly the same consensus rates with degree
EquiTopo enables decentralized learning with light communication and fast convergence. To the best of our knowledge, we are not aware of any negative social impacts in our results.
Acknowledgement
We thank the anonymous reviewers for suggesting updated literature on E.-R. graphs. Ming Yan was partially supported by the NSF award DMS-201 201499.. Lei Shi was partially supported by Shanghai Science and Technology Program under Project No. 21JC1400600 and No. 20JC1412700 and National Natural Science Foundation of China (NSFC) under Grant No. 12171093, supported by Alibaba Research Internship Program.
Kexin Jin was
References
[1] Sulaiman A Alghunaim and Kun Yuan. A unified and refined convergence analysis for non- convex decentralized learning. arXiv preprint arXiv:2/ 10. 10.09993, 2021.
[2] 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.
[3] Itai Benjamini, Gady Kozma, and Nicholas Wormald. The mixing time of giant component of random graph. Random Structures & Algorithmss, 45(3):383-407, 2014.
10

---

[4] Andrew Beveridge and Jeanmarie Youngblood. The best mixing time for random walks on trees. Graphs and Combinatorics, (116):2211223333 2016.
[5] Stephen Boyd, Arpita Ghosh, Balaji Prabhakar, and Devavrat Shah. Mixing times for random walks on geometric random graphs. In ALENEX/ANALCO, pages 240-249, 2005.
[6] Jianshu Chen and Ali H. Sayed. Diffusion adaptation strategies for distributed optimization and
learning over networks. IEEE Transactions on Signal Processing, 60(8):4289 0200424989444,,, 2012.
[7] Di Lorenzo and G. Scutari. Next: In-network nonconvex optimization. IEEE Transactions on Signal and Information Processing over Networks, 102):120-136, 2016.
[8] John C Duchi, Alekh Agarwal, and Martin Wainwright. Dual averaging for distributed optimization: Convergence analysis and network scaling. IEEE Transactions on Automatic control, 57(3):992-606, 2011.
[9] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In IEEE Conference on Computer Vision and Puttern Recognition (CVPR), pages 770-778, 2016.
[10] Yerlan Idelbayev. Proper ResNet implementation for CIFARIO/CIFAR 100 in PyTorch. https:
/ //github. wtw. akamaster/pyttorch wwwereeeeeiaateeeeeeeeeeeeeeeeee Accessed: 2022-05.
[11] Anastasiaa Koloskova, Tao Lin, and Sebastian U Stich. An improved analysis of gradient tracking for decentralized machine learning. Advances in Neural Information Processing Systems, 34, 2021.
[12] 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.
[13] Dmitry Kovalev, Egor Shulgin, Peter Richtárik, Alexander V Rogozin, and Alexander Gas- nikov. Adom: accelerated decentralized optimization method for time-varying networks. In International Conference on Machine Learning, pages 5784-5793, PMLR, 2021.
[14] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[15] Yann LeCun, Corinna Cortes, and CJ Burges. MNIST handwritten digit database. ATT Labs [Online]. Available: http://yann.eecue wwcun.com/exd///niiii 2, 2010.
[16] 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 170.:17707777.
[17] 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.
[18] Xiangru Lian, Wei Zhang, Ce Zhang, and Ji Liu, Asynchronous decentralized parallel stochastic gradient descent. In International Conference on Machine Learning (ICML), pages 3043-30 3052,, 2018.
[19] 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), pages 315-321. IEEE, 2019.
[20] Asaf Nachmias and Yuval Peres. Critical random graphs: diameter and mixing time. The Annals of Probability. 36(4):1267-122)
2008
[21] Angelia Nedić and Alex Olshevsky. Distributed optimization over time-varying directed graphs.
IEEE Transactions on Automatic Control, 60(3):601-61 2014.
[22] 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.
[23] 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.
[24] Angelia Nedic and Asuman Ozdaglar. Distributed subgradient methods for multi-agent opti- mization. IEEE Transactions on Automatic Control, 54(1):48-66 61, 2009.
[25] G. Qu and N. Li. Harnessing smoothness to accelerate distributed optimization. IEEE Transac- tions on Control of Network Systems, 1235-1200. 2018.
[26] Ali H Sayed. Adaptive networks. Proceedings of the IEEE, 400 2014.
11

---

[27] Kevin Scaman, Francis Bach, Sébastien Bubeck, Yin Tat Lee, and Laurent Massoulié. Optimal algorithms for smooth and strongly convex distributed optimization networks. In International Conference Machine Learning (ICML), pages 3027-3036, 2017.
[28] 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):444-666, 2015.
[29] 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.
[30] 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.
[31] Luca Trevisan. Lecture notes on graph partitioning, expanders and spectral methods. University of California, Berkeley, hilps://people. cecs. berkeley. edu/" lucahookssexpundes=-0000
pdf.
2017.
[32] Joel Tropp. User-friendly tail bounds for sums of random matrices. Foundations of computa- tional mathematics, 12(4):389-434, 2012.
[33] 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.
[34] Jianyu Wang, Anit Kumar Sahu, Zhouyi Yang, Gauri Joshi, and Soummya Kar. MATCHA: Speeding up decentralized SGD via matching decomposition sampling. arXiv preprint 1905.9995 2019.
[35] Ran Xin, Usman Khan, and Soummya Kar. An improved convergence analysis for decen- tralized online stochastic non-convex optimization. IEEE Transactions on Signal Processing, 2020.
[36] Jinming Xu, Shanying Zhu, Yeng Chai Soh, and Lihua Xie. Augmented distributed gradi- ent methods for multi-agent optimization under uncoordinated constant stepsizes. In IEEE Conference on Decision and Control ( (CDC), pages
Osaka, Japan, 2015.
[37] 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.
(38] Bicheng Ying, Kun Yuan, Hanbin Hu, Yiming Chen, and Wotao Yin. Bluefog: Make decentral- ized algorithms practical for optimization and deep learning. arXiv preprint arXiv:21 1.04287, 2021.
[39] Kun Yuan, Qing Ling, and Wotao Yin. On the convergence of decentralized gradient descent. SIAM Journal on Optimization, 26(3):1835-1844 2016.
[40] Kun Yuan, Bicheng Ying. Xiaochuan Zhao, and Ali Sayed. Exact dffusion for distributed optimization and learning- Part I: Algorithm development. IEEE Transactions on Signal Processing, 67(3):708 723, 2019.
12

---

Checklist
1. For all authors...
(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] At the end of Section 1.2
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
(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]
(b) Did you include complete proofs of all theoretical results? [Yes] They are in the Appendix (Supplemental material).
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main ex- perimental results (either in the supplemental material as URL)? [Yes] They are included the supplemental material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] The details
the Appendix.
(c) Did you report error bars (e-g., with respect the random seed after running experi- ments multiple times)? [No] We have repeated some experiments with different seeds and reported the averaged performance. See the Appendix for details.
(d) Did you include the total amount of computer and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes]
4. If you using existing assets (e.g., code, data, models) or curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material URL? [No]
(d) Did you discuss whether and how consent obtained from people whose data you's '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 or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "pnk7pryFjuE", "reviewer": "Reviewer_fyHE", "summary": "This article discusses network structure for decentralized consensus and optimization. The authors propose EquiTopo, a family of network structures with $O(1)$ consensus rates, i.e., network-independent rates. For both directed and undirected topologies, the authors present static network structures with degrees $O(\\ln n)$ and propose counterpart dynamic (time-varying) networks to relax connection degrees to $O(1)$. Lastly, the authors apply their proposed network topologies to decentralized stochastic gradient descent as well as decentralized stochastic gradient tracking algorithms and provide a comparison of the number of rounds required for convergence.", "questions": "- Which of the following terms in the convergence rate describes transient iterations (Trans. Iters.)? This needs to be clarified in the description.\nIt is often necessary to use push-sum algorithms (gradient-push algorithms) for directed networks (static or dynamic). There are, however, no differences between the algorithms proposed for directed and undirected networks in this study. Does this only apply to the network design (EquiTopo) proposed here? In that case, please elaborate in the manuscript.\n- Do the theoretical results for DSGD and DSGT presented (Theorem 5 and Theorem 6) represent new results? If not, it is best to present them as propositions and to properly cite the seminal work.", "limitations": "We have limited control over the network design in decentralized optimization, which is the main limitation of this work. The authors of this paper have pointed out that their work is primarily concerned with defining the communication structure on a central machine with multiple GPUs, i.e., high-throughput scenarios with the capability of making arbitrary connections between entities. However, this challenges robustness extensions where entities may fail to communicate synchronously.", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- A novel result is presented for network design in decentralized optimization problems where the consensus rate is independent of the size of the network.\n- By reducing the connection degree from $O(\\ln n)$ to $O(1)$, constant communication can be achieved per iteration.\n\nWeakness:\n- As shown in Theorem 5 and Theorem 6, the convergence rate improvement for DSGD and DSGT only occurs in transient terms.", "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": "hX5tlVKBG9H", "reviewer": "Reviewer_CH48", "summary": "The paper proposes a new family of topologies which has a constant degree and a network-size-independent consensus rate and can be used to accelerate decentralized optimization and learning algorithms. ", "questions": "I expect in real applications, the communication topologies are given or constrained.  Does the topology design require each pair of nodes are allowed to communicate?  Is there any examples in which such a topology design is feasible? ", "limitations": "NA", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper has a very novel idea. The paper is well written. The results are very interesting. \n\nThe only concern is whether it is feasible to design topologies in this way in real world applications. ", "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": "JpMstWkvMls", "reviewer": "Reviewer_7t7T", "summary": "This work  introduces new families of graph topologies having (almost) constant degree and network size independent mixing rates. This has the advantage that each node needs to exchange information with relatively few neighbors while achieving fast mixing rates. The authors propose directed and undirected version of static graphs with desired properties and then propose dynamic graphs for which the degree of each agent is always 1. As expected, the price to pay for this is a degradation in the mixing rate. Finally, the authors incorporate the families of graph topologies into distributed optimization schemes and analyze the graphs impact on the algorithms' performances. ", "questions": "I would like the authors to provide some clarification on the topic discussed on the first paragraph in ``Strengths and Weaknesses.'' above.  ", "limitations": "see above", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The main weakness lies in the comparison with  the Erd\\H{o}s-R'{e}nyi (ER) random graph. While in Table 1 it is stated that ER graphs yield a consensus rate of $1-\\Theta(1/\\ln(n)),$ this result seems to have been  improved in the literature.  See for instance Proposition 5 in \n\n```Network Topology and Communication–Computation Tradeoffs in Decentralized Optimization'' by A. Nedich, et. al., in IEEE Proceedings 2018, \n\nwhere it is established that if $p = (1+a)\\ln (n)$ one achieves a solution $\\varepsilon$ away from consensus in time $\\mathcal{O}(\\log(\\varepsilon^{-1}))$, implying that the rate is invariant with respect to the network size (this is done for undirected graphs). Note that ER random graphs have the additional advantage of guaranteeing that the consensus time will scale as stated above, with a probability $p$ that goes to $1$ as $n \\to \\infty$. This is in contrast with the families D-EquiStatic and U-EquiStatic  which can be generated algorithmically using Algorithm 3 in Appendix A with the understanding that one can generate a graph with the desired properties with probability $p,$ where $p$ does not improve (go to 1)   as $n$ increases.  \n\nOn the other hand, the main strength of the paper lies in the use of the structure of the families D-EquiStatic and U-EquiStatic to build the classes OD-EquiDyn and OU-EquiDyn wherein  all agents are connected via a time-varying graph whose each instance has  degree 1. This naturally leads to a loss in the consensus rate, which is still related to the consensus rate of the ``base''  graph of the D-EquiStatic or U-EquiStatic family.   \n\nThat said, given the discussion in the previous paragraph, I would request the authors to highlight the shortcomings of having each agent randomize transmissions to one of its neighbors over a ``base'' ER graph.", "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