Beyond Exponential Graph: Communication-Efficient Topologies for Decentralized Learning via Finite-time Convergence
Authors: Yuki Takezawa
Ryoma Sato
Han Bao
Kenta Niwa
Makoto Yamada
Venue: NeurIPS 2023 poster (2023)
Keywords: decentralized learning
distributed optimization
network topology
consensus rate
TL;DR: In this study, we propose the novel topology, Base-(k+1) Graph, which enables Decentralized SGD to more successfully reconcile accuracy and communication efficiency than the existing topologies.

Abstract: Decentralized learning has recently been attracting increasing attention for its applications in parallel computation and privacy preservation. Many recent studies stated that the underlying network topology with a faster consensus rate (a.k.a. spectral gap) leads to a better convergence rate and accuracy for decentralized learning. However, a topology with a fast consensus rate, e.g., the exponential graph, generally has a large maximum degree, which incurs significant communication costs. Thus, seeking topologies with both a fast consensus rate and small maximum degree is important. In this study, we propose a novel topology combining both a fast consensus rate and small maximum degree called the Base-$\left(k+1\right)$ Graph. Unlike the existing topologies, the Base-$\left(k+1\right)$ Graph enables all nodes to reach the exact consensus after a finite number of iterations for any number of nodes and maximum degree $k$. Thanks to this favorable property, the Base-$\left(k+1\right)$ Graph endows Decentralized SGD (DSGD) with both a faster convergence rate and more communication efficiency than the exponential graph. We conducted experiments with various topologies, demonstrating that the Base-$\left(k+1\right)$ Graph enables various decentralized learning methods to achieve higher accuracy with better communication efficiency than the existing topologies. Our code is available at https://github.com/yukiTakezawa/BaseGraph.

Beyond Exponential Graph: Communication-Effiii Topologies for Decentralized Learning via Finite-time Convergence
Yuki Takezawa's 1.2 Ryoma Sato -Han B Kenta Niwa², Makoto Yamada²
Kyyoto University, POIST, "NTT Communication Science Laboratories
Abstract
Decentralized learning has recently been attracting increasing attention for its applications in parallel computation and privacy preservation. Many recent studies stated that the underlying network topology with a faster consensus rate (a.k.a. spectral gap) leads to a better convergence rate and accuracy for decentralized Iearn- ing. However, a topology with fast consensus rate, e.g., the exponential graph, generally has a large maximum degree, which incurs significant communication costs. Thus, seeking topologies with both fast consensus rate and small maximum degree is important. In this study, we propose novel topology combining both a fast consensus rate and small maximum degree called the BASE- (k: + 1) GR GRAPH. Unlike the existing topologies, the BASE-(K + 1) GRAPH enables all nodes to reach the exact consensus after a finite number of iterations for any number of nodes and maximum degree k. Thanks to this favorable property, the BASE- (k 1) GRAPH endows Decentralized SGD (DSGD) with both faster convergence rate and more communication efficiency than the exponential graph. We conducted experiments with various topologies, demonstrating that the BASE-(K 1) GRAPH enables various decentralized learning methods achieve higher accuracy with better communication efficiency than the existing topologies. Our code available at htttps://github com/ htt/yyukiTaaezzaaaa Baasaarapaaaaeahh
Introduction
Distributed learning, which allows training neural networks in parallel multiple nodes, has become an important paradigm owing to the increased utilization of privacy preservation and large- scale machine learning. In centralized fashion, such All-Reduce and Federated Learning [ 16 26 (27] all or some selected nodes update their parameters by using their local dataset and then compute the average parameter of these nodes, although computing the average of many nodes is To reduce communication costs, decentralized Because decentralized learning allows nodes to exchange parameters only with few neighbors in the underlying network topology, decentralized learning is more communication efficient than All-Reduce and Federated Learning.
the major bottleneck in the training time 18
19
23
learning gains significant attention [
18
24
While decentralized learning can improve communication efficiency, it may degrade the convergence rate and accuracy due its sparse communication characteristics [1] 48). Specifically, the smaller the maximum degree of an underlying network topology is. the fewer the communication cost becomes 33 39 meanwhile, the faster the consensus (a.k.a. spectral gap) of a topology is, the faster the convergence rate of decentralized learning becomes [11. Thus, developing a topology with both fast consensus rate and small maximum degree is essential for decentralized learning. Table T summarizes the properties of various topologies. For instance, the ring and exponential graph are
Equual Contribution
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Table 1: Comparison among different topologies with n nodes. The definition of the consensus rate and finite-time convergence is shown in Sec.
Topology
Consensus Rate
Connection
Maximum Degree
#Nodes
Ring (28
1 Onn
Undirected
2
Vi E N
Torus 228
1 O(n
Undirected
4 [log(()]]
Vn E N
Exp. [43
1- -0((lgg(n)))
Directed
Vn E N
1-peer Exp. 43
(1lgg((r))) (-fnitee time conv.
Directed
A power of 2 power of va E N
1-peer Hypercube
31
(1ogg(()) i-intte time conv.
Undirected
Base- + 1) Graph (ours)
O Olog (n))) time conv.
Undirected
commonly used I 3 12 23). The ring is communication-efiin
topology because its maximum
degree is two but its consensus rate quickly deteriorates as the number of nodes n increases [28]. The exponential graph has fast consensus rate, which does not deteriorate much as increases, but it incurs significant communication costs because its maximum degree increases as n increases [3 Thus, these topologies sacrifice either communication efficiency consensus rate.
Recently, the 1 1pperr exponential graph 43 and 1-peer hypercube graph [31] were proposed as topologies that combine both a small maximum degree and fast consensus rate (see Sec. Sec.C..4 for examples). As Fig. [ shows, in the ring and exponential graph, node parameters only reach the con- sensus asymptotically by repeating exchanges of parameters with neighbors. Contrarily, in the 1-peer exponential and 1-peer hypercube graphs, parameters reach the exact consensus after a finite number of iterations when is power of 2 (see Fig. 2T in Sec. F22. Thanks to this property of finite-time convergence, the 1- 1-peer exponential and 1-peer hypercube graphs enable Decentralized SGD (DSGD) 18 to converge the same convergence rate as the exponential graph when n is power of 2, even though the maximum degree of the 1-peer exponential and 1-peer hypercube graphs is only one 43
However, this favorable property only holds when is a power of 2. When n. is not a power of 2, the 1- peer hypercube graph cannot be constructed, and the 1-peer exponential graph only reaches the consensus asymptotically as well as the ring and exponential graph, as Fig. [ illlustrates. Thus, the 1-peer expo- nential and 1-peer hypercube graphs cannot enable DSGD to converge as fast as the exponential graph when n is not a power of Moreover, even if is power of 2, the 1-peer hypercube and 1-peer expo- nential graphs still cannot enable DSGD to converge faster than the exponential graph.
1500
Exp. (11)
10-1
Ring (2)
Consensus error
20
Torus
1-peer Exp. (1)
1ppee D-EquiDyn (1)
12
1-peer U.EquiDyn (1)
13-19
Base-2 Graph (1)
Graph (2)
Base-4 Graph (3)
10-1h
Base Graph (4)
10
20
50
40
Iterations
Figure 1:
Comparison of consensus rate. See
Sec. for detailed experimental settings. The number in the bracket is the maximum degree.
In this study, we ask the following question: Can we construct topologie that provide DSGD with both a faster convergence rate and better communication efficiency than the exponential graph for any number of nodes? Our work provides the affirmative answer by proposing the BASE-(K + 1) GRAPH 2 which is finite-time convergence for any number of nodes n and maximum degree k (see Fig. Thanks to this favorable property, the BASE-2 GRAPH enables DSGD to converge faster than the ring and torus and as fast as the exponential graph for any 71 while the BASE-2 GRAPH is more communication-effe efficient than the ring. torus, and exponential graph because its maximum degree is only one. Furthermore, when 2 < k- < [log)(n)], the BASE- + 1) GRAPH enables DSGD to converge faster with fewer communication costs than the exponential graph because the maximum degree of the (k + 1) GRAPH is still less than that of the exponential graph. Experimentally, we compared the BASF-(K + 1) GRAPH with various existing topologies, demonstrating that the BASE- + 1) GRAPH enables various decentralized learning methods to more successfully reconcile accuracy and communication efficiency than the existing topologies.
2 Related Work
Decentralized Learning. The most widely used decentralized learning methods are DSGD [8]
and its adaptations 2 19.. Many researchers have improved DSGD and proposed DSGD with momentum 4 20
45
communication compression methods 6 10 23
35
38
etc. While
DSGD is simple and efficient method, DSGD is sensitive to data heterogeneity 36 To mitigate this
issue, various methods have been proposed, which can eliminate the effect of data heterogeneity on
the convergence rate, including gradient tracking [2] 29 30
D 36 etc.
[17 37 46
Note that the maximum degree of the BASE- (I + 1) GRAPH is not & 1, but at most k.

---

Effect of Topologies. Many prior studies indicated that topologies with a fast consensus rate 39]. For instance, DSGD and gradient
improve the accuracy of decentralized learning tracking converge faster as the topology has a faster consensus rate 18 Zhu et al. [88 revealed
34
that topology with fast consensus rate improves the generalization bound of DSGD. Especially when the data distributions are statistically heterogeneous, the topology with fast consensus rate prevents the parameters of each node from drifting away and can improve accuracy [4]. However, communication costs increase as the maximum degree increases [33 43 Thus, developing a topology with fast consensus rate and small maximum degree important for decentralized learning.
3 Preliminary and Notation
Notation. A graph G is represented by (V, where V is a set of nodes and E' is set of edges. If G graph, ((G (resp. E(G) denotes the set of nodes (resp. edges) of G. For any d1, ans (01. an) denotes the ordered set. An empty (ordered) set is denoted by 0. For any n E N, let [n] m (1. ... n). For any n, a E N, mod(a, n.) is the remainder of dividing by n. || || denotes Frobenius norm, and 1, denotes an n--dimensional vector with all ones.
Topology. Let G be an underlying network topology with nodes, and W 10, 1|ax= be mixing matrix associated with G. That is, Wij is the weight of the edge (i.j), and Waj > 0 if and only if (i.j) E EGG). Most of the decentralized learning methods require W be doubly stochastic (i.e.. 36). Then, the consensus rate of G is defined below.
W1, 1, and W 1, 1,,) [18 20 29
Definition 1. Let W be a mixing matrix associated with a graph G with n nodes. Let w; E Rd a parameter that node has. Let X = (I In) Ædx= and X = x1111 The consensus
rate 3 E [0,1) 1) is the smallest value that satisfies
x W
X
[|
S 32 X
X || for any X.
Thanks to 3 E [0, 1). I; asymptotically converge to consensus Σー= by repeating parameter exchanges with neighbors. However, this does not mean that all nodes reach the exact consensus within finite number of iterations except when / = 0, that is, when G' is fully connected. Then, utilizing tlmevaryiing topologies, Ying et al. 43 and Shi et al. BI aimed to obtain sequences of graphs that can make all nodes reach the exact consensus within finite iterations and proposed the 1-peer exponential and 1-peer hypercube graphs respectively (see Sec. C.4 for illustrations).
Definition 2. Let (G(1), ..... G(m)) be a sequence of graphs with the same set of nodes (i.e. V(GU)
V(G(m))). Let be the number of nodes. Let W(1) .... W(() be mixing matrices associated with G(1), .... ...,G(m) respectively. Suppose that W(I).... (()) satisfy X (wWw(() ... (m)) = X for any X E BRdxn, where X = called m-finite time convergence or an m-finite time convergent sequence of graphs.
= 4X1,1, Then, (G G(m))
Because Definition 2 assumes that V(G =.... =.. V(G(m) =((())))))) holds, we often write sequence of
graphs (G (m)) as (E(G()) (..())))))..(( using slight abuse of notation, Additionally, in the following section, we often abbreviate the weights of self-loops because they are uniquely
determined due to the condition that the mixing matrix is doubly stochastic.
4 Construction of Finite-time Convergent Sequence of Graphs
In this section, we propose the BASE-(K + 1) GRAPH, which is finite-time convergence for any number of nodes E N and maximum degree & E [n - 1]. Specifically, we consider the setting where node has parameter 2; and propose a graph sequence whose maximum degree is at most that makes all nodes reach the exact consensus n -.-- x;. To this end, we first propose the k- K-PEER HYPER- HYYPER-YYPERCT HYPCCUBB GRAPH, which is finite-time convergence when does not have prime factors larger than + 1. Using it, we propose the SIMPLE BASE-(K + GRAPH and BASE- + 1) GRAPH, which are unite-time convergence for any n.
1
(b) 12 3) Figure 2: Illustration of the 2-PEER HYPER-HYPERCUUT GRAPH.
6(= 2
3

---

Algorithm 1 k-PEER HYPER-HYPERCUBE GRAPH (v(V)
1: Input: the set of nodes V ("1,'.. 2n and number of nodes
2: Decompose n. as n2 = R4 x ... x n2 with minimum L such that E [A + 1] for all I e [4].
3: for E [4] do
4: Initialize b, zero for all i [m]] and EO) to 0.
5: for i E [n] do
6: for m E [ni] do
7:
j + mod(i + m x P= np - 1.n) +
8:
if < n and bj
n then
9:
Add edge (vt, 1/) with weight to E and by t b, + 1.
10:
return (E()) E B(L).
4.1 k-peer Hyper-hypercube Graph
Before proposing the BASE-(K+ 1) GRAPH, we first extend the L-peer hypercube graph [3] the k- peer setting and propose the k-PEER HYPER-HYPERCUS
GRAPH, which is finite-time convergence when the number of nodes n does not have prime factors larger than + and used as a component in the BASE-(K- + 1) GRAPH. Let V be a set of n nodes. We assume that all prime factors of are less than or equal to ++ 1. That is, there exists R4, 112 n, E [k [ 1] such that n = ni X ..... X nl,, In this case, we can construct the L-finite time convergent sequence of graphs whose maximum degree is at most k. Using Fig. 2a] we explain how all nodes reach the exact consensus. Let G(1) and ((2) denote the graphs in Fig. [2 from left to right, respectively. After the nodes exchange parameters with neighbors in G( nodes 1 and nodes 3 and and nodes 5 and have the same parameter respectively. Then, after exchanging parameters in G(²), all nodes reach the exact consensus. We present the complete algorithms for constructing the K-PEER -PPERREEEERUUBE GRAPH in Alg.
4.2 Simple Base-(k 1) Graph
As described in Sec. 1.1 when n do not have prime factors larger than k + 1, we can easily make all nodes reach the exact consensus by the k-PEER HYPER-HYPERCUEE GRAPH. However, when n has prime factors larger than k + 1, c.g., when (k: n) = (1, 5), the k-PEER HYPER-HYPERCUBL GRAPH cannot be constructed, In this section, we extend the k-PEER HYPER-HYPERCUUE GRAPH and propose the SIMPLE BASE- (A: + 1) GRAPH, which is finite-time convergence for any number of nodes and maximum degree k. Note that the maximum degree of the SIMPLE BASE-(K 1)
GRAPH is not k + 1, but at most k.
We present the pseudo-code for constructing the SIMPLE BASE-(K + 1) GRAPH in Alg. For
simplicity, here we explain only the case when the maximum degree l: is one. The case with k 2 2 explained in Sec. B The SIMPLE BASE-(K 1) GRAPH mainly consists of the following four steps. The key idea is that splitting V into disjoint subsets to which the K-PEER GRAPH is applicable.
Step 1. As in the base-2 number of n. decompose n. as 2P +... 2P in line 1, and then split V into disjoint subsets Vi, Vz such that [V] = 2n for all l E [Z] in line 3
Step 2. For all E [Z], we make all nodes in Vi obtain the average of parameters in Vi using the 1-PBER HYPER-IYYPERCUB GRAPHI Hi (Vi) in line 11. Then, we initialize I' as one.
Step 3. Each node in Vr41 .... U Vr. exchanges parameters with one node in Vi such that the average in Vy becomes equivalent to the average in V. We increase I' by one and repeat step 3 until I' = L. This procedure corresponds to line 15.
Step 4. For all / [4]. we make all nodes in Ví obtain the average in V12 using the 1-PEER HYPER- HYPERCUBE GRAPH H, (Vi). Because the average in V, is equivalent to the average in V after step 3, all nodes reach the exact consensus. This procedure corresponds to line 25.
Using the example presented in Fig. we explain Alg. 2 in more detail. Let ((1) ,... ((5) denote the graphs in Fig. from left to right, respectively. In step 1, we split V = {1.-.. 5) into
SSplitting Vi into Vi,1, Vi,a, becomes crucial when A 2 2 (see Sec. B

---

=1, ,4) and V/2 == {5}. In step 2, nodes in V1 obtain the average in Vi by exchanging parameters in G and G In step 3, the average in V1 becomes equivalent to the average in V by exchanging parameters in G In step 4, nodes in Vi can get the average in V by exchanging parameters GK4) and GO Because node also obtains the average in V after exchanging parameters in G(3), all nodes reach the exact consensus after exchanging parameters in ((5)
Note that edges added in lines 20 and 27 are not necessary if we only need to make all nodes reach the exact consensus. Nonetheless, these edges are effective in keeping the parameters of nodes close in value to each other in decentralized learning because the parameters are updated by gradient descent before the parameter exchange with neighbors. For instance, edge (1,2) 2) in G which is added in line 20, is necessary for finite-time convergence because nodes and 2 already have the same parameter after exchanging parameters in G()) and ((2) We provide examples in Sec. C
Figure 3: SIMPLE BASE-2 GRAPH with n 5(= 2 + +1). The value on the edge is the edge weight, and the edges are colored in the same color as the line in Alg. 2 where they were added.
Algorithm 2 SIMPLE BASE-(K + 1) GRAPH A
Asimll (V)
1: Input: the set of nodes V and number of nodes nt= a1 (k: + (k +1 (k+(k)))
such that
P2 > ... > 2 O and a E [k] for all / E [4].
2: If all prime factors of are less than or equal k: + then return (V).
3: Split V into disjoint subsets V,,.. Vy. such that [V] ar (u(k+11)) 1) P for all E [L]. Then, for all
I E [L], split Vi into disjoint subsets Vi.1.... Vi.a, such that [Viaal
(k: 1) for all a E [a:].
4: Construct k-PEER HYPER- HEPPER-YYPERUBE GRAPH H₂ for all | E [L] and m2 = (H())
5: Construct PPEE HYPER-HYPERCURT
GRAPH H4(Vi, (V,a) for all I [L] and [ai].
6: Initialize by as zero for all E [L]. and initialize m as zero.
7: while bj < [744(V (Vi,1) do
8: m + 17 + 1 and (mm) f- 0.
9: for 1 {L, L 1,
do
10:
m S m2 then
Add E7H (V)) to F(m) where mn' mod(m (7Hx(VV))) + 1.
12:
else if m < Mi - then
for v E Vı do
14:
Select isolated node u1," Mhe myg
from Vn Vm-my.l,"..
Vm m1 my
15:
Add edges (u, u1), (v, Uam-m,) with weight
[V
(mm)
Σ -/=m-on =mmm VVr
16:
else m = m1 + and * L then
17:
while There two more isolated nodes in Vi do e the number isolated nodes in V/.
18:
19:
Select min c) isolated nodes V in V/.
20:
Add edges with weights ग
E(m) such that V compose the complete graph.
else
22:
6t + bi +
23:
pt + 0 then
24:
for E [ai] do
Add E(H
(Vi,a) (Vi,))Via)) (mm1) to ((m) where m' mod(b; 1, (V14((V.)))
26:
else
Add (V))((V)(mm))) ((m) where m' mod(b; 1, 176x (Vi))) + return (E(), E(2)... ,.., E(m)). ((m)))
28:
5

---

Algorithm 3 BASE- + 1) GRAPH As(V)
1: Input: the set of nodes V and number of nodes
2: Decompose n as n = p x q such that a multiple of 2,3, -. , + 1) and q is prime to
2,3, .(k + 1).
3: Split V into disjoint subsets V1, ... Vi such that [V] = for all l.
simple 4: Construct SIMPLE BASE- (k + 1) GRAPH A (Vi) for all E [p]-
5: for m {1,2.
1.4 m (Vi) do
E(m) + UiEtp) E simple (Vi)
6:
7: Split V into disjoint subsets U Ug such that [Ui] = p and [0 Vyl 1 for all 1, GRAPH (Ui) for all / [g].
8: Construct k-PEER
9: for m E {1,2, .... ,14,, (U:)1} do
F Smme (V:))) < Useigl R(H+ (Ui)(m).
& (F(L), E222, ... E A (VU))))
12: If [
simple (V) < |g| then return A
simple (V) else return E.
(a) BASE-2 GRAPH with n = 6( 2 x 1))
NEW
MI
mm
PE
(b) SIMPLE BASE-2 GRAPH with n 6(= 2 +
Figure 4: Comparison SIMPLE BASE-2 GRAPH and BASE-2 GRAPH with n 6. The value on the edge indicates the edge weight. The edges added in line 10 in Alg. 3 are colored black, and the edges added in line 6 are colored the same color as the line in Alg. where they are added.
4.3 Base-(k + Graph
The SIMPLE BASE-(A: + 1) GRAPH finite-time convergence for any n and k. while the SIMPLE BASE- (k: + 1) GRAPH contains graphs that are not necessary for the finite-time convergence and becomes redundant sequence of graphs in some cases, c.g., (k, n) = (1, 6) (see the example in Fig. 4b and detailed explanation in Sec. C.2h. To remove this redundancy, this section proposes the BASE- + GRAPH that can make all nodes reach the exact consensus after fewer iterations than the SIMPLE BASE-(K + GRAPH
The pseudo-code for constructing the BASE-(K: + 1) GRAPH is shown Alg. GRAPH consists of the following three steps.
The BASE-(K + 1)
Step We decompose n as p x g such that is a multiple of 2, ... + 1) and q is prime to
2,
1), and split V into disjoint subsets Vi,-.. Vp such that [Vil = q for all / [p].
Step 2. For all / E [p]. we make all nodes in Vi reach the average in Vi the SIMPLE BASE- (k: + 1) GRAPH Asimple (Vi). Then, we take p nodes from Vi. Vp respectively and construct set U2. Similarly, we construct U2 ... Ug such that U, ... Ug are disjoint sets.
Step 3. For all 1 [g], we make all nodes in U, reach the average in U, by the k- EEPER HYPER- HYPERCUBE GRAPH (U,). Because the average U, equivalent to the average V after step 2, all nodes reach the exact consensus.
Using the example in Fig. 4a explain the BASE- (k++1) GRAPH in more detail. Let (())
((4)
denote the graphs in Fig. from left to right, respectively. In step 1, we split into Vi = (1,2,3) and V/2 {4. 5, 6). In step 2, nodes in Vi and nodes in V2 have the same parameter respectively by

---

exchanging parameters on G(!), G because the subgraphs composed on V1 and 1/2 are same
as the SIMPLE BASE-(K + 1) GRAPH (see Fig. 14a.. Then, we construct U₁ == [1,4], U2 (2. 5). and U3 == (3, 63. Finally, in step 3, all nodes reach the exact consensus by exchanging parameters in
G(4).
Fig- 5 and Sec. F. compare the BASE- + 1) GRAPH with the SIMPLE BASE-1 ( K 1) GRAPH, demonstrating that the length of the BASE- (k: + 1) GRAPH is less than that of the SIMPLE BASE-(k: + 1) GRAPH in many cases. Moreover, Theorem show the upper bound of the length of the SIMPLE BASE- GRAPH and BASE-(K (k+ + +) GRAPH. The proof is provided in Sec.
12
10
Length
c
Simple Base-2 Graph (1)
Base 2 Graph 111
Theorem 1. For any number of nodes n E N and maximum degree & E [n 11, the length of the SIMPLE BASE-(K 1) GRAPH and BASE-(K + 1) GRAPH is less than or equal to
Simple Base Graph
150
Number nodes
2 logg+11 (n) 2
Figure 5: Comparison of length.
Corollary 1. For any number of nodes n E and maximum degree k [n - 11, the SIMPLE BASE-(K + GRAPH and BASE- (K: + GRAPH ( (1)) (n))-ffnite time convergence.
Therefore, the BASE-(K + GRAPH is powerful extension of the 1-peer exponential 43 and 1-peer hypercube graphs 31 because they are O (loga -finite time convergence only if is power of and their maximum degree cannot be any number other than 1.
5 Decentralized SGD on Base- + 1) Graph
In this section, we verify the effectiveness of the BASE-(K (k + 1) GRAPH for decentralized learning, demonstrating that the BASE-(K 1) GRAPH can endow DSGD with both faster convergence rate and fewer communication costs than the existing topologies, including the ring, torus, and exponential graph. We consider the following decentralized learning problem:
min =ER
f(x) = Σ f((x))
f((x) = BE,DD (F (a)
where n is the number of nodes, f: the loss function of node i, D; is the data distribution held by node i, Far;:; {.) is the loss of node i at data sample &,, and V F (z; &,) denotes the stochastic gradient.
Then, we assume that the following hold, which are commonly used for analyzing decentralized
learning methods [18 20 23 43
Assumption 1. There exists 1 -oo that satisfies [(x)) 1 for any x E Rd.
Assumption 2. ft is L-smooth for all i E [n]]. Assumption 3. There exists o² that satisfies Wg DD (F((;; vf(22)11 S 02 for all Rd. Assumption 4. There exists Ç² that satisfies Σ D Vz)( fx < < for all Rd.
We consider the case when DSGD [18]. the most widely used decentralized learning method, is used as optimization method. Let WI),.... ((m) be mixing matrices of the BASE-(K 11) GRAPH. In DSGD on the BASE-(K (k: + 1) GRAPH, node updates its parameter 2; as follows:
(r+1) W (1+mmd((r.m)
w
VV (a ((5)))
where y7 is the learning rate. In this case, thanks to the property of finite-time convergence, DSGD the BASE-(K (I: + GRAPH converges at the following convergence rate.
Theorem 2. Suppose that Assumptions 4 hold. Then, for any number of nodes E N and maximum degree k [m- 1), there exists 1j such that
E. 1 a. generated by Eq. satisfies
E (r)))) S e after
0²
$loge+1 (n) o 1
loge41(1)
R O
+
LFo
(2)
ne
e3/2
iterations, where Fo == f()(1)) f

---

The above theorem follows immediately from Theorem stated in Koloskova et al. [1] and Corollary The convergence rates of DSGD over commonly used topologies are summarized Sec. E From 2 and Sec. F. we can conclude that for any number of nodes the BASE-2 2 GR APH enables DSGD to converge faster than the ring and torus and as fast as the exponential graph, although the maximum degree of the BASE-2 GRAPH is only one. Moreover, if we set the maximum degree le to the value between 2 to [loga (n)], the BASE-(K + 1) GRAPH enables DSGD to converge faster than the exponential graph, even though the maximum degree of the BASE-(K + 1) GRAPI remains less than that of the exponential graph. It worth noting that we increase the maximum degree of the 1 1-peer exponential and 1-peer hypercube graphs (i.e., k-peer exponential and k-peer hypercube graphs with
I
Theorem
2). these topologies cannot enable DSGD to converge faster than the exponential graph because these topologies longer time convergence even when the number of nodes a power of 2.
6 Experiments
In this section, we validate the effectiveness of the BASE-(K GRAPH. First, we experimentally verify that the BASE-(k 1) GRAPH is finite-time convergence for any number of nodes in Sec. 6. and we verify the effectiveness of the BASE-(K + 1) GRAPH for decentralized learning in Sec. 6.2
1000
500
1000
Exp. (7.9.10)
Ring
Torus
Consensus
10
Consensus
Consensus
20
1-peer Exp.
1-peer D-EquiDyn (1)
10-04
1-peer U-EquiDyn (1)
Base-2 Graph (1)
Base-3 Graph (2)
Base-4 Graph (3)
30
20
10
Base-5 Graph (4)
Figure 6: Comparison consensus rates among various topologies. The number in the bracket indicates the maximum degree of topology. Because the maximum degree of the exponential graph depends on n, the three numbers the bracket indicate the maximum degree for each n.
Fashion MNIST
CIFAR-10
CIFAR-100
90
60-
Exp. (5)
Ring (2)
80
80-
50
1-peer Exp. (1)
Accurscy
Accurrry
70
Accuracy
40
1-peer U-EquiDyy
1-peer D-EquiDyn (1)
8
Base 2 Graph
Base-3 Graph (2)
00.
00.
20
Base Graph (3)
Graph
40
14
20c
522
10
50
100 Epoch
150
200
100
200
300
400
500
0
100
200
300
400
500
Epoch
Epoch
(a) a
10
Fashion MNIST
CIFAR-10
CIFAR-100
90
60
Exp. (5)
Ring (2)
80.
50-
Torus
1-peer Exp. (1)
Accuracy
70
Accuraty
40
1-peer E-EquiDyn
70
1-peer D-EquiDyn (1)
8
Graph
Base-3 Graph (2)
Base 4 Graph (3)
20:
Base. Graph
40
64
320
50
100
150
200
100
200
300
400
500
100
200
300
400
500
Epoch
Epoch
Epoch
(b)
0.1
Figure 7: Test accuracy (%) of DSGD on various topologies with = 25. The number in the bracket
indicates the maximum degree of a topology. We also compared with dense variants of the 1-peer (U, D) -y-uqiDy (33 in Sec. F.3.1 showing the superior performance of the BASE-(K + 1) GRAPH.

---

6.1 Consensus Rate
Setup. Let 2; E R be the parameter that node has, and let σ == " 2i- For each i, the initial value of 24 was drawn from Gaussian distribution with mean 0 and standard variance 1. Then, we evaluated how the consensus error n - - =)² decreases when z; is updated as Dy + Ej= Wiy where W is the mixing matrix associated with a given topology.
Results. Figs. [ Tand 6 present how the consensus errors decrease on various topologies. The results indicate that the BASE- 1) GRAPH reaches the exact consensus after a finite number of iterations, while the other topologies only reach the consensus asymptotically. Moreover, as the maximum degree k increases, the BASE-(K + 1) GRAPH reaches the exact consensus with fewer iterations. We also present the results when n is power of 2 Sec. F.2 demonstrating that the 1-peer exponential graph can reach the exact consensus well as the BASE-2 GRAPH,, but requires more iterations than the BASE-4 GRAPII.
6.2 Decentralized Learning
Next, we examine the effectiveness of the BASE-(K 1) GRAPH in decentralized learning.
Setup. We used three datasets, Fashion MNIST 41 CIFAR-(10, 100} [14] and used LeNet [1] for Fashion MNIST and VGG-11 32
for CIFAR-(1O, 100). Additionally, we present the results using ResNet-18 18 [5] in Sec. G The learning rate tuned by the grid search and
used the cosine learning rate scheduler [22]. We distributed the training dataset to nodes by using Dirichlet distributions with hyperparametter 77. conducting experiments in both homogencous and heterogeneous data distribution settings. As a approaches zero, the data distributions held by each node become more heterogeneous. We repeated all experiments with three different seed values and reported their averages. See Sec. Ho more detailed settings.
Results of DSGD on Various Topologies. We compared various topologies combined with DSGD with momentum 4 [8,, showing the results Fig. 7 From Fig. 7 the accu- racy differences among topologies are larger as the data distributions are more heterogeneous. From Fig. 7b the BASE-(2, 3, 4, 5} GRAPH reach high accuracy faster than the other topolo- gies. Furthermore, comparing the final accuracy, the final accuracy of the BASE-2 GRAPH is comparable to or higher than that of the existing topologies, including the exponential graph.
Moreover, the final accuracy of the BASE- 5) 90 GRAPH is higher than that of all existing topologies. From Fig. 7a the accuracy differences among topolo- gies become small when = 10; however, the BASE- GRAPH still outperforms the other topologies. In Fig. we present the results in cases other than n = 25, demonstrating that the BASE-2 GRAPH outperforms the 1-peer exponential graph and the BASE- 5 GRAPH can consistently outperform the exponential and 1-peer exponential graphs for all n. In Sec. F.3.2. we show the learning curves and the comparison of the consensus rate when is 21, 22, 23, 24, and 25.
Exp. (5)
ppper Exp. (1)
Graph
Accuracy
Base Graph (2)
Base-4 Graph (3)
87
Graph
86.
Base-6 Graph
85-
22
22
23
24
25
Number of nodes
Figure 8: Test accuracy (%) of DSGD with CIFAR-10 and a 0.1.
Results of D2 and QG-DSGDM Various Topologies. The above results demonstrated that the BASE-(K: + 1) GRAPH outperforms the existing topologies, especially when the data distributions heterogeneous. Hence, we next compared the BASE-(K +1+1)
D2
QG-DSGDm
Exp. (5)
GRAPH with the existing topolo- gies in the case where 1)2 [36]
80
B0
1-peer Exp. (1)
Base-2 2 Graph
Accuracc
Accuracy
Base 3 Graph (2)
and QG-DSGDm [20]. which are robust to data heterogeneity, are used as decentralized learning methods. From Fig. / the BASE- 2 GRAPH can achieve compara- ble or higher accuracy than the 1-peer exponential graph, and the BASE-5 GRAPH consistently out-
90
50
Base 4 Graph (3)
B Graph
30
40
100
200
300
400
500
100
200
500
Epoch
Epocch
Figure 9: Test accuracy (%) of 2 and QG-DSGDm with CIFAR- 10, n = 25, and a = 0.1.

---

performs the exponential graph. Thus, the BASE-(K ( GRAPH is useful not only for DSGD but also for D and QG-DSGDm and then enables these methods to achieve reasonable balance between accuracy and communication efficiency.
7 Conclusion
In this study, we propose the BASE-(k + 1) GRAPH, a novel topology with both a fast consensus rate and small maximum degree. Unlike the existing topologies, the BASE-(K: 1) GRAPH is finite-time convergence for any number of nodes and maximum degree k. Thanks to this favorable property, the BASE-(K 1) GRAPH enables DSGD obtain both faster convergence rate and more communication efficiency than the existing topologies, including the ring, torus, and exponential graph. Through experiments, we compared the BASE-(K-1) GRAPH with various existing topologies, demonstrating that the BASE-(K + GRAPII enables various decentralized learning methods to more successfully reconcile accuracy and communication efficiency than the existing topologies.
Acknowledgments
Yuki Takezawa, Ryoma Sato, and Makoto Yamada were supported by JSPS KAKENHI Grant Number 23KJ1336, 21J22490, and MEXT KAKENHI Grant Number 20H04243, respectively.
References
[1] Assran, M., Loizou, N., Ballas, N., and Rabbat, M. (2019). Stochastic gradient push for distributed deep learning. In International Conference Machine Learning.
[2] Chen, Y., Yuan, K., Zhang, Y., Pan, P., Xu, Y., and Yin, W. (2021). Accelerating gossip sgd with periodic global averaging. In International Conference on Machine Learning.
[3] Cyffers, E., Even, M., Bellet, A., and Massoulié, L. (2022). Muffliato: amplification for decentralized optimization and averaging. In Advances in Neural Information Processing Systems.
Peer-to-peer privacy
[4] Gao, H. and Huang, H. (2020). Periodic stochastic gradient descent with momentum for decentralized training. arXiv.
[5] He, K., Zhang, X., Ren, S., and Sun, J. (2016). Deep residual learning for image recognition. In IEEE Conference on Computer Vision and Pattern Recognition.
[6] Horváth, and Richtarik, P. (2021). better alternative to error feedback for communication- efficient distributed learning. In International Conference on Learning Representations.
[7] Hsu, T.-M. H., Qi, and Brown, M. (2019). Measuring the effects of non-identical data distribution for federated visual classification. In arXiv.
[8] Kairouz, P., McMahan, H. B., Avent, B., Bellet, A., Bennis, M., Bhagoji. A. N., Bonawitz, K., Charles, Z., Cormode, G., Cummings, R., D' D'Olveiira, R. G. L., Eichner, H., Rouayheb, S. E.. Evans, D., Gardner, J., Garrett, Z., Gascón, A., Ghazi, B., Gibbons, P. B., Gruteser, M., Harchaoui, Z., He, C., He, L.,, Huo, Z., Hutchinson, B., Hsu, J., Jaggi. M., Javidi, T., Joshi, G., Khodak, M., Konecný, J., Korolova, A., Koushanfar, F., Koyejo, S., Lepoint, T., Liu, Y., Mittal, P., Mohri, M., Nock, R., Özgür, A., Pagh, R., Qi. H., Ramage, D., Raskar, R., Raykova, M., Song, D., Song, W., Stich. S. U.. Sun, Z.. Suresh, A. T., Tramèr, F., Vepakomma, P., Wang, J., Xiong, L., Xu, Z., Yang, Q. Yu, F. X., Yu, H., and Zhao, (2021). Advances and open problems federated learning. In Foundations and Trends in Machine Learning.
[9] Karimireddy, S. P. Kale, S., Mohri, M., Reddi, S.. Stich, S., and Suresh, A. T. (2020). SCAF- FOLD: Stochastic controlled averaging for federated learning, In International Conference on Machine Learning.
[10] Koloskova, A., Lin, T., Stich, U., and Jaggi, M. (2020a). Decentralized deep learning with arbitrary communication compression. In International Conference on Learning Representations.
10

---

[11] Koloskova, A., Loizou, N., Boreiri, S., Jaggi, M., and Stich, S. (2020b). A unified theory of decentralized SGD with changing topology and local updates. In International Conference on Machine Learning-
[12] Koloskova, A., Stich, S., and Jaggi. M. (2019). Decentralized stochastic optimization and gossip algorithms with compressed communication. In International Conference on Machine Learning.
[13] Kong, L.,, Lin, T., Koloskova, A., Jaggi, M., and Stich, S. (2021). Consensus control for decentralized deep learning. In International Conference on Machine Learning.
[14] Krizhevsky, A. (2009). Learning multiple layers of features from tiny images. Technical report.
[15] LeCun, Y., Bottou, L., Bengio, Y., and Haffner, P. (1998). Gradient-based learning applied to document recognition. In IEEE.
[16] Li, T., Sahu, A. K., Zaheer, M., Sanjabi, M., Talwalkar, A., and Smith, V. (2020). Federated optimization in heterogeneous networks. In arXiv.
[17] Li, Z.. Shi, W., and Yan, M. (2019). A decentralized rroiiaa--grddien method with net- work independent step-sizes and separated convergence rates. In IEEE Transactions on Signal Processing.
[18] Lian, X., Zhang, C.,, Zhang, H., Hsieh, C.-.., Zhang, W., and Liu, J. (2017). Can decentralized algorithms outperform centralized algorithms? case study for decentralized parallel stochastic gradient descent. In Advances in Neural Information Processing Systems.
[19] Lian, X., Zhang, W. Zhang, C., and Liu, J. (2018). Asynchronous decentralized parallel stochastic gradient descent. In International Conference on Machine Learning.
[20] Lin, T., Karimireddy, S. P., Stich, S., and Jaggi, M. (2021). Quasi-global momentum: Accelerat- ing decentralized deep learning on heterogeneous data. In International Conference on Machine Learning.
[21] Lorenzo, P. D. and Scutari, G. (2016). Next:
In-network nonconvex optimization. In IEEE Transactions on Signal and Information Processing over Networks.
[22] Loshchilov, I. and Hutter, F. (2017). SGDR: International Conference on Learning Representations.
Stochastic gradient descent with warm restarts. In
[23] Lu, Y. and De Sa, C. (2020). Moniqua: Modulo quantized communication in decentralized SGD. In International Conference on Machine Learning.
[24] Lu, Y. and De Sa, C. (2021). Optimal complexity in decentralized training. In International Conference on Machine Learning.
[25] Marfoq, O., Xu, C., Neglia, G., and Vidal, R. (2020). Throughput-optimal topology design for cross-silo federated learning. In Advances in Neural Information P Processing Systems.
[26] McMahan, B., Moore, E., Ramage. D.,, Hampson, S., and Arcas, B. A. y. (2017). communication-eeficcen learning of deep networks from decentralized data. In International Conference on Artificial Intelligence and Statistics.
[27] Murata, T. and Suzuki, T. (2021). Bias-variance reduced local sgd for less heterogeneous federated learning. In International Conference on Machine Learning.
[28] Nedié, A., Olshevsky, A., and Rabhat, M. G. (2018). Network topology and communication- computation tradeoffs in decentralized optimization. In IEEE.
[29] Nedić, A., Olshevsky, A., and Shi, W. (2017). Achieving geometric convergence for distributed optimization over -ireingy graphs. In SIAM Journal Optimization.
[30] Pu, and Nedic, A. (2021). Distributed stochastic gradient tracking methods. In Mathematical Programming.
11

---

[3] Shi, G., Li, B.. Johansson, M., and Johansson, K. H. (2016). Finite-time convergent gossiping. IEEE Transactions on Networking.
[32] Simonyan, K. and Zisserman, A. (2015). Very deep convolutional networks for large-scale image recognition. In International Conference on Leurning Representations.
[33] Song, Z., Li, W., Jin, K., Shi, L., Yan, M., Yin, W., and Yuan, K. (2022). Communication- efficient topologies for decentralized learning with ((1) consensus rate. In Advances in Neural Information P Processing Systems.
[34] Takezawa, Y., Bao, H., Niwa, K., Sato, R., and Yamada, M. (2023). Momentum tracking: Momentum acceleration for decentralized deep learning on heterogeneous data. In Transactions on Machine Learning Research.
[35] Tang, H., Gan, S., Zhang, C., Zhang, T., and Liu, J. (201 8a). Communication compression for decentralized training. In Advances in Neural Information Processing Systems.
[36] Tang, H., Lian, X., Yan, M., Zhang, C.,, and Liu, J. (2018b). D²: Decentralized training over decentralized data. In International Conference on Machine Learning.
[37] Vogels, T., He, L., Koloskova, A., Karimireddy, S. P., Lin, T., Stich, S. U., and Jaggi, M. (2021). Relaysum for decentralized deep learning heterogeneous data. In Advances in Neural Information Processing Systems.
[38] Vogels, T., Karimireddy, S. P., and Jaggi, M. (2020). Practical low-rank communication compression in decentralized deep learning. In Advances Neural Information Processing Systems.
[39] Wang, J., Sahu, A. K., Yang, Z., Joshi, G., and Kar, S. (2019). Matcha: Speeding up decentral- ized sgd via matching decomposition sampling. In Indian Control Conference.
[40] WU, Y. and He, K. (2018). Group normalization. In European Conference on Computer Vision.
[41] Xiao, H., Rasul, K., and Vollgraf, R. (2017). Fashion-mnist: novel image dataset for benchmarking machine learning algorithms. In arXiv.
[42] Xin, R. and Khan, U. A. (2020). Distributed heavy-ball: generalization and acceleration of first-order methods with gradient tracking. In IEEE Transactions on Automatic Control.
[43] Ying, B., Yuan, K., Chen, Y., Hu, H., Pan, P., and Yin, W. (2021). Exponential graph is provably efficient for decentralized deep training. In Advances in Neural Information Processing Systems.
[44] Yu, H., Jin, R., and Yang. S. (2019). On the linear speedup analysis communication efficient momentum SGD for distributed non-conver optimization. In International Conference on Machine Learning.
[45] Yuan, K., Chen, Y., Huang, X., Zhang, Y., Pan, P., Xu, Y., and Yin, W. (2021). DecentLaMe Decentralized momentum sgd for large-batch deep training. In International Conference on Computer Vision.
[46] Yuan, K., Ying, B., Zhao, X., and Sayed, A. H. (2019). Exact diffusion for distributed optimization and learning part Algorithm development. In IEEE Transactions on Signal Processing.
[47] Zhao, H., B., Li, Z., Richtárik, P., and Chi, Y. (2022). BEER: Fast O(1/T) rate for decentralized nonconvex optimization with communication compression. In Advances Neural Information Processing Systems.
[48] Zhu, T., He, F., Zhang, L.,, Niu, Z.,, Song, M., and Tao, D. (2022). aopology-aware generalization geneeraiioa of decentralized SGD. In International Conference on Machine Learning.
12

---

A Detailed Explanation of k-peer Hyperhypereube Graph
In this section, we explain Alg. in more detail. The k-PEER HYPER-HYPERCUBA GRAPH mainly consists of the following five steps.
Step Decompose n as n ni x
ny with minimum L such that ny E [k + for all E [Z].
Step
1, we make all nodes obtain the average of parameters in by using the complete graph. If L 2 2, we split V into disjoint subsets Vi,-. Vnz such that [V] __ for all
E [mx..] and continue to step 3.
Step 3. For all / E [nr.]. we make all nodes in Vi obtain the average of parameters in V by using the k-PEER HYPER-HYPERCUBE GRAPH Hg (Vi).
Step 4. We take n& nodes from V1,... Vn, respectively and construct set U1. Similarly, construct U2 ... Un, such that U1. ,Un, are disjoint sets.
Step For all [nr.]. we make all nodes in U₁ obtain the average of parameters in U/ by using complete graph. Because the average of parameter U/ is equivalent to the average in V after step 4, all nodes reach the exact consensus.
When S + 1, the R-PEER SEPPE--HYPERCUT GRAPH becomes the complete graph because of step 2. When n > + 1, we decompose n in step 1 and construct the k-PEER HYPER-HH HERRUUBEE GRAPH recursively in step 3. Thus, the k-PEER
GRAPH make all nodes
reach the exact consensus by the sequence of graphs.
Using the example provided in Fig. 10 we explain the k-PEER detailed manner. When
GRAPH in more 3. In step we split == {1, ... 12] into V1 := {1,-... 4). 1/2 := {5, ... .8). and 1/3 := 1....... ... 12). Step corresponds to the first two as
12, we decompose
graphs in Fig. TOb As shown in Fig. 10a the subgraphs consisting of Vi, V2, and V3 in the first two graphs in Fig. Tob are equivalent the k-PEER HYPER-HYYPECCUB GRAPH with the number of
nodes 4. Thus, all nodes reach the exact consensus by exchanging parameters in Fig. 10b
(a) n 1(= x
(b) n 12 2 2 3)
Figure 10: Illustration of the 2-PEER HYPER-HYPERCCE GRAPIL In Fig. 10a all edge weights are
2. Fig. 10b edge weights are the first two graphs and in the last graph.
13

---

B Detailed Explanation of Simple Base-(k + 1) Graph with k 2 2
2 only in the case where maximum degree k one. In this section, explain the details of Alg. 2 in the case with h 2 2.
In Sec. 4.2, we explain Alg.
The SIMPLE BASE- (A + 1) GRAPH mainly consists of the following five steps.
Step 1. As in the base-(k++) 1) number of n. we decompose as n a1 (k+ 1))) - (k+ in line 1, and then split V into disjoint subsets Vi.-.., Vy, such that [Vi] at (k: 1) for
all E [L].
Step For all E [L] we split Vi into disjoint subsets Vi,,. Vi,a, such that VVial = (A: + 1) for all [ax] in line 3.
Step 3. For all E [Z], we make all nodes in Vi obtain the average of parameters in Vú using the k-PEER HYPER-HYPERCCN
GRAPH Ha (Vi) line 11. Then, we initialize I' as one.
Step Each node in V U.+1U.--VV exchange parameters with or nodes in (=-(= Vir, U...UUUV..... such that the average in Vira becomes equivalent to the average in for all a E [ar]] We increase !' by one and repeat step until I' This procedure corresponds to line 15.
Step 5. For all 1 [L] and [ai]. make all nodes in V1,a obtain the average in Vi.a using the k- PEER HYPER-HYPERCUPE average in V after step all nodes reach the exact consensus. This procedure corresponds to line 25.
GRAPH H4 (Vi.)) Since the average Vi, is equivalent to the
The major difference compared with the case where node in Vi+1U- J---UUU -UV, exchange parameters with one node in Vy such that the average in V/2 becomes equivalent that in V. while in the case where k 2 each node Vi .... V2 exchange parameters such that the average in Vr.a becomes equivalent to that in V for all a E [ar]. Thanks this step, we can make all nodes reach the exact consensus using k-PEER HYPER-BR HYPRRCUBE GRAPH Hy (V,a) instead of H4 (Vi) in step 5, and we can reduce the length of graph sequence.
is step In the case where A: each
Using the example provided in Fig. I1 we explain Alg. in more detailed manner. Let G(), (4)) denote the graphs depicted in Fig. II from left to right, respectively. First,
split V = (1.... 7} into V1 = (1, 6} and V2 = {7), and then split V1 into V1,1 = [1,2,3) and V1 (4,5, 6). In step all nodes in Vn obtain the
parameter by exchanging parameters in G()) and G(2), In step the average in Vi, that in V1,2, and that in 1/2 become the same as the average in all nodes V by exchanging parameters in G33), Thus, in step all nodes reach the exact consensus by exchanging parameters in (4))
Figure 11: k = 2, = 7(= 2 x x 1). The value on the edge indicates the edge weight. For simplicity, we omit the edge value when it is J.
14

---

C Illsttaaion of Topologies
C.1
Examples
Fig. 12 shows the examples of the SIMPLE BASE- 1) GRAPH. Using these examples, we explain how all nodes reach the exact consensus.
We explain the case depicted in Fig. 12a Let G(1), G( ( G( denote the graphs depicted in Fig. 12a
from left to right, respectively. First, split V == {1, 5] into V == {1, 2,33, 3) and V22
5).
and then split V2 into V2,1 {4} and V2, {5}. After exchanging parameters in G nodes in Vi and nodes in 2/2 have the same parameter respectively. Then, after exchanging parameters in G(2), the average in V1, that in V2. and that in 22, become same as the average in V. Thus, by exchanging parameters in G all nodes reach the exact consensus. Note that edge (4, 5) in G which is added in line 27 in Alg. 2 is not necessary for all nodes to reach the exact consensus because nodes 4 and already have the same parameter after exchanging parameters in G however, it is effective decentralized learning as we explained Sec. 4.2
! (a)
1
2, n 5 3+2
4
(b) k = 1, 7(= 2 + 2211
Figure 12: Illustration of the SIMPLE BASE-(K 1) GRAPH. The edge is colored in the same color as the line of Alg. 12 where the edge is added. The value on the edge indicates the edge weight. For simplicity, we omit the edge value when it }
C.2 Illustrative Comparison between Simple Base-(k (k + 1) and Base-(k + 1) Graphs
In this section, we provide example of the SIMPLE BASE- + 1) GRAPHI, explaining the reason why the length the BASE-(K 1) GRAPH is less than that the SIMPLE BASE-(K + GRAPII.
Let G(1) (()) denote the graphs depicted in Fig. 13 from left right, respectively. (GU), g(),g(()) G(4), G(5) is finite-time convergence, but (GL), G(() G(3), G(O) is also finite- time convergence because after exchanging parameters in (3), nodes 3 and 4 already have the same parameters. Then, using the technique proposed in Sec. 4.3 we can remove such unnecessary graphs contained in the SIMPLE BASE-(K 1) GRAPH (see Fig. 4ab. Consequently, the BASB-(K 1)
GRAPH can make all nodes reach the exact consensus faster than the SIMPLE BASE-(K: + 1) GRAPH.
MEN
Figure 13: Illustration of the SIMPLE BASE-2 GRAPH with 6(= 2 + 2). The edge is colored in the same color as the line of Alg. where the edge added.
15

---

C.3 Additional Examples
C.3.1 Simple Base-(k 1) Graph
(6) 4
(d)
( m 8
(h) 10
Figure 14: Illustration of the SIMPLE BASE-2 GRAPH with the various numbers of nodes.
16

---

(a) 3
8
(c) =
(d)
(c) = 7
(I) n1)==88
9
(h) 10
Figure 15: Illustration of the SIMPLE BASE-3 GRAPH with the various numbers of nodes.
17

---

C.3.2 Base-(k + 1) Graph
(a) 3
(6) 1
(c) 5
(1)
8
(h) 10
Figure 16: Illustration of the BASE-2 GRAPH with the various numbers of nodes.
18

---

(a) 3
8
(c)
(d)
(c) = 7
(1) n
(g) n== 9
(h) 10
Figure 17: Illustration of the BASE-3 GRAPH with the various numbers of nodes.
19

---

C.4 1-peer Hypereube Graph and 1-peer Exponential Graph
For completeness, we provide examples of the 1-peer hypercube 31 and 1-peer exponential graphs 43 in Figs.
19 and 18 respectively.
(a) n
(b)
Figure 18: Illustration of the 1-peer hypercube graph. All edge weights are 0.5.
(8) n
(b) n 5
(c) n 6
(d) = 7
(e) 8
Figure 19: Illustration of the 1-peer exponential graph. All edge weights are 0.5.
20

---

D Proof of Theorem 1
GRAPH). Suppose that all prime factors of the number of nodes nt are less than or equal to k + 1. Then, for any number of nodes E N and maximum degree k [n 11, the length of the k-PEER HYPER-HYPERCUBE GRAPH less than or equal to 2 (1)g
Lemma (Length of k-PEER HYPER-HYPERCUUT
Proof. We assume that n is decomposed as n = nn x nt with minimum where ny [| + for all I E [T.]. Without loss of generality, we suppose n S 12 I .... S Rg, Then, for any + j. holds that n, X n 2 + because n, x nj Σ k + for some and j. this contradicts the assumption that L is minimum.
When L is even, we have
n == (n1 x n2) x ... x (NL-1 x xn) 2 (k: + 2)
Then, we get L S 2 (0)
Next, we discuss the case when is odd. When L 1.23 nz 2 V + holds because n X n Z k + 2. Thus, get
n = (ni x 12) x ... x (RL-2 x n x nr 2 (k: 22+ x xn (I: 2)
Then, we get I. S 22 (n) when 1, 1.23. 3. 3.
Thus, given the case when L = 1, the length of the k-PEER HYPER-HYPERCUBE GRAPH is less than or equal to max 1ogx+2(n)).
Lemma 2 (Length of SIMPLE BASE-(K + 1) GRAPH). For any number of nodes N and maximum degree & E [n - 1), the length of the SIMPLE BASE- (k + 1) GRAPH is less than or equal logg++1 (n) + 2.
Proof. When all prime factors of n are less than or equal to k +++ 1, the SIMPLE BASE- + 1) GRAPH equivalent to the PEER HYPER-HYPERCUU HYPERCUBE GRAPH and the statement holds from Lemma [ In the following, we consider the case when there exists a prime factor of n that is larger than k 1. Note that because when L (i.e., a (k 1))),, all prime factors of n less than equal to k + 1, we only need to consider the case when L 2 2. We have the following inequality:
log++1(n)
log (0g (A: + 1)Pt + + az + 1)pb)
2 P1 1
2 p1.
Then, because 1/1 01 (k + 1)P1, it holds that m (v1) < 1+ Pl logk (n)
Similarly, it holds that [H (Vi.1) p1 S log (n) because |V,11 = (k + 1)Pi, In Alg. 2 the
update rule by b1 + in line 22 executed for the first time when -m -m--11 because L > Thus,
the length of the SIMPLE BASE- 1) GRAPH is at most m. + 174 (V1..)) + 1 < 2 log (n) + 2. This concludes the statement.
Lemma 3 (Length of BASE-(K 1) GRAPH). For any number of nodes N and maximum degree
E [n - 1). the length of the BASE-(K: + 1) GRAPH is less than or equal to 2 2oog (n) + 2.
Proof. The statement follows immediately from Lemma and line 12 in Alg. 3
21

---

E Convergence Rate of DSGD over Various Topologies
Table 2 lists the convergence rates of DSGD over various topologies. These convergence rates can be immediately obtained from Theorem 2 stated in Koloskova et al. [i] and consensus rate of the topology. As seen from T the BASE-2 GRAPH enables DSGD to converge faster than the ring and torus and as fast as the exponential graph for any number of nodes, although the maximum degree of the BASE-2 GRAPHI is only one. Moreover, for any number of nodes, the BASE-(K + 1) GRAPH with 2 < k < flog2 (n)] enables DSGD to converge faster than the exponential graph, even though the maximum degree the BASE- 1) GRAPH remains be less than that of the exponential graph.
Table 2: Convergence rates and maximum degrees of DSGD over various topologies.
Topology
Convergence Rate
Maximum Degree
#Nodes
o²
Cn
Ring
1.%
2
Vo
3/2
CA
+ov
Torus
L.fo
4
ReZ
6/22
d²
(log((n)
(x)
(og)(1))
Exp.
LFf
[1og(n)]]
Vo
2/2
d²
(logg(n) (og
(og)(1)
1 peer Exp. 4
ne2
2/2
-Ff
1
power of
0²
(logg(n) a Toggin
logg(())
1-peer Hypercube
-Fo
1
power 2
ne2
2/2
(loges (rt) + loge (x)
(0)++1())
Base-(k 1) Graph (ours)
-LF
A
ne2
3/2
22

---

Additional Experiments
F.1 Comparison of Base-(k k + and Simple Base-(k + 1) Graphs
Fig. 20 shows the length of the SIMPLE BASE-(K + 1) GRAPH and BASE-(K + 1) GRAPH. The results indicate that for all k. the length of the BASE-(k + 1) GRAPII is less than the length of the SIMPLE BASE-(K 1) GRAPII in many cases.
Simple Dase:3 Graph 12)
Simple Base-4 Graph
Base-3 Graph (2)
Base-4 Graph
Length 5
Length
Length
Simple B Graph (1)
Base-2 Graph (1)
125 130 Number of nodes
Number nodes
Number nodes
Simple Base-5 Graph 14)
Simple Baso-6 Graph (5)
Simple Base-7 Graph 16) Base-7 Graph
Baase55 Graph (4)
Base-6 Graph (5)
Lengts
Length
Length
40
* 'ttt 15 15a 175 200
18t 1y red 105 700
THE 15 765
Number of nodes
Number of nodes
Number of nodes
Simple Base-8 Graph Base 8 Graph (7)
Simple Dase-9 Graph (8)
Simple
Base 9 Graph (B)
Base 10 Graph (9)
Length
Length
Length
LOS
123
130
Number
Figure 20: Comparison of the length of the SIMPLE BASB- +1) GRAPH and BASE- (ASE-((-- 1) GRAPH.
F.2 Consensus Rate
we demonstrate how consensus error decreases on various topologies when the number of nodes power of 2. The results indicate that the BASE-2 GRAPH and 1-peer exponential graph can reach the exact consensus after the same finite number of iterations and reach the consensus faster than other topologies. Note that the BASE-2 GRAPH is equivalent to the 1-peer hypercube graph when n is power of 2.
Fig. 21
n 128
0= 512
A- 1024
Exp. (7,9,10)
Ring
Torus
Consensus
Consensus
Consensus
30
1-peer Exp.
1-peer D-EquiDyn (1)
10
1-peer U U-EquiDyn (1)
20
Base-2 Graph (1)
Base-4 Graph (3)
10
36
50
Iterations
Iterations
Iterations
Figure 21: Comparison consensus rates among different topologies when the number of nodes is power of 2. Because the BASE-(3.5) 5) GRAPH are the same as the BASE-(2,4) GRAPH, respectively, when n is power of 2, we omit the results of the BASF- 5) GRAPH.
23

---

F33 Decentralized Learning
F.3.1 Comparison of Base-(k + 1) Graph and EquiStatic
In this section, compared the BASE-(K + 1) GRAPH with the (U. DJ-EuiSttatic [33 The (U,
DJ-EquiStatic are dense variants of the 1-peer (U. DJ-EquiDyn, and their maximum degree can be set as hyperparameters. We evaluated the fU, D) DJ-EquiStatic varying their maximum degrees; the results are presented in Fig. [2 In both cases with a = 10 and a = 0.1, the BASE-2 GRAPH can achieve comparable or higher final accuracy than all (U. DJ-EquiStatic, and the [3 4,5) GRAPH outperforms all (U, DJ-EquiStatic. Thus, the BASE-(k (k: + 1) GRAPH is superior to the (U, DJ-EqtiStitic from the perspective of achieving a balance between accuracy and communication efficiency.
1=10.0
a=0.1
D-EquiStatic (2)
D-EquiStatic (3)
80
D-EquiStatic
U-EquiStatic (2)
Accuracy 70-
70
U-EquiStatic
Base-2 Graph (1)
Base-3 Graph (2)
Base-4 Graph (3)
89
Base Graph (4)
500
100
400
Epoch
Epoch
Figure 22: Test accuracy (%) of DSGD with CIFAR-10 and n 25. The number in the bracket is the maximum degree of topology.
F.3.2 Comparison with Various Number of Nodes
In this section, we evaluated the effectiveness of the BASE-(K + 1) GRAPHI when varying the number of nodes n. Fig. 24 presents the learning curves, and Fig 23 shows how consensus error decreases when is 21, 22, 23, 24, and 25. From Fig. 24 the BASE-2 GRAPH consistently outperforms the 1-peer exponential graph and can achieve a final accuracy comparable to that of the exponential graph. Furthermore, the BASE- (3, 4, 5) GRAPH can consistently outperform the exponential graph, though the maximum degree of the BASE- (3, 4, 5} GRAPH is less than that the exponential graph.
In Fig. 25 presents the learning curve for = 16. When the number of nodes is power of two, the 1-peer exponential graph also finite-time convergence, and the 1-peer exponential graph and BASE-2 GRAPH achieve competitive accuracy.
Condensus omer
Consensus error
n= 24
0 n=25
10/4
1-peer Exp. (1)
Corsenaus crrar
Consensuus enror
Base:2 Graph
Base-3 Graph
Base-4 Graph (3)
Base-5 Graph
25
22
Rerations
Iterations
Figure 23: Comparison of consensus rates among different topologies. The number in the bracket denotes the maximum degree of topology. We omit the results of the BASE-5 GRAPH when n 24 because the BASE-5 GRAPH and BASE-4 GRAPH are equivalent when n = 24.
24

---

n-22
90
Exp. (5)
1-peer Exp. (1)
80
Base-2 Graph (1)
Graph
Accuracy
70
Base Graph (3)
Base Graph (4)
60-
60
Base-6 Graph (5)
40
100
200
300
400
500
100
200
300
400
500
Epoch
Epach
n=
2=
n=
90-
80
70
Accuracy
70
50
50
64
04
457
500
6.75
427 500
400
100
200
500
300
Epoch
Epach
Epoch
Figure 24: Test accuracy (%) of DSGD with CIFAR-10 10 and a = 0.1. The number the bracket
denotes the maximum degree of a topology. When 24, we omit the results of the BASE-5 GRAPHI because the BASE-5 GRAPH and BASE-4 GRAPHI are equivalent, When n 25, we omit the results of the BASE-6 GRAPH because the BASE-6 GRAPH and BASE-5 GRAPH are equivalent.
n=16
Exp. (5)
1-peer
Base-2 Graph (1)
Base Graph (3)
70
50
85
08
475
Epach
Figure 25: Test accuracy (%) of DSGD with CIFAR-10 and 16. The number in the bracket is the maximum degree topology. We omit the results the BASE-3 GRAPH and BASE-5 GRAPH because these graphs are equivalent to the BASE-2 GRAPH and BASE-4 GRAPH, respectively.
25

---

G Results with Other Neural Network Architecture
In this section, we evaluate the effectiveness of the BASE-(K 1) architecture. Fig. shows the accuracy when we use ResNet- 18 the results with VGG-11 shown in Sec.
GRAPH with other neural network
S
The results are consistent with
am100.0
a=0.1
90
Exp. (5)
1-peer
Base-2 Graph (1)
Base: Graph (2)
Accuracy
Accuracy
70-
Graph
Base:5 Graph (4)
50
4.%
</c
1.0
200
500
Epoch
Figure 26: Test accuracy (%) of DSGD with n = 25, CIFAR-10, and ResNet. The number in the
bracket denotes the maximum degree of topology.
H Hyperparameter Setting
list detailed hyperparameter settings used in Secs. and F33 on server with eight Nvidia RTX 3090 GPUs.
We ran all experiments
Table 3: Hyperparameter settings for Fashion MNIST with LeNet.
Dataset
Fashion MNIST
Neural network architecture
LeNet [SS]
with group normalization 40
Data augmentation
RandomCrop of PyTorch
Step size
Grid search over (0.1, 0.01, 0.001}.
Momentum
0.9
Batch size
32
Step size scheduler
Cosine decay
Step size warmup
10 epochs
The number of epochs
200
Table 4: Hyperparameter settings for CIFAR-(10,100) with (VGG-11, ResNet-18).
Datasct
CIFAR-(10, 100)
Neural network architecture
{VGG-11 11 332, R8 5 with group normalization 40
Data augmentation
Random Crop, RandomHorizontalFilp RandomErasing of Py Torch
Step size
Grid search over 0.001).
Momentum
0.9
Batch size
32
Step size scheduler
Cosine decay
Step size warmup
10 epochs
The number of epochs
500
26


Reviews:
[{"review_id": "qRq7omImXS", "reviewer": "Reviewer_pdDT", "summary": "The paper considers the problem of decentralized optimization and proposes a novel time-varying communication topology that has better properties than prior topologies, especially when the number of nodes n is not a power of 2 i.e. (i) it is sparse, and (ii) has good spectral properties, translating to the good optimization behavior. Paper provides a description of the proposed topology, its properties, and evaluates its effectiveness in practice. \n", "questions": "1. If the number of nodes n is a power of two, is it still beneficial to use your proposed topologies ? Including the larger range of n in figure 8 that covers power of 2 might be good. \n2. Why did you not include the gradient tracking in comparison in figure 9? \n3. When reading Figure 3, I got confused why the number of averaging steps is 5, while log_2(5) < 3.\n4. In the Experiments section (Fig. 6, 7, 8, 9), having a Base-6 graph might still potentially be better than the Exponential graph, as its maximum degree would be the same, but it would lead to the faster convergence. Why did you not include the Base-6 graph in the comparison? \n\nMinor suggestions: \n\n5. It might be good to provide the open-source code of generating proposed topologies.\n6. Might be helpful for the reader to indicate how large is log_2(n) for each of the experiments.\n7. When giving an example in Figures 3 & 4, I felt it might be better to have the same number of nodes n in both cases, so that the reader can see how is the Base-(k + 1) graph can reduce the number of steps from the Simple Base-(k + 1) graph", "limitations": "yes", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "- The paper is very well written and clear\n- Proposed topology clearly improves over the previously known topologies, especially when the number of nodes n is not a power of 2.\n", "weaknesses": "1. Paper gives consensus rate (in e.g. Table 1) in O-notation, i.e. hiding the constants. However, actual constants do matter a lot. If we allow the use of O-notation, then expander graphs would be the best theoretical graphs, as they have constant consensus rate, as well as constant maximum degree. However, expanders do not work well in practice for relatively small graphs as the constants are quite large. Therefore, I believe it is important to get good constants while designing a new communication topology. \n\n2. Description of the algorithm for Base-(k + 1) graph is not fully clear. In step 1. of the algorithm (line 181), it was not clear why n can always be decomposed in this way? What if n is a prime number ? \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> Paper gives consensus rate (in e.g. Table 1) in O-notation, i.e. hiding the constants. However, actual constants do matter a lot. If we allow the use of O-notation,\nthen expander graphs would be the best theoretical graphs, as they have constant consensus rate, as well as constant maximum degree. However, expanders do\nnot work well in practice for relatively small graphs as the constants are quite large. Therefore, I believe it is important to get good constants while designing a\nnew communication topology.\n\nTheorem 1 provides the upper bound of the length of the Base-$(k+1)$ Graph without using O-notation,\nshowing that the Base-$(k+1)$ Graph is $(2 \\log_{k+1} (n) + 2)$-finite time convergence.\nThus, the constant factors are small,\nand the experimental results also demonstrate that the Base-$(k+1)$ Graph enables decentralized learning methods to more successfully reconcile accuracy and communication efficiency than the existing topologies.\n\n> Description of the algorithm for Base-(k + 1) graph is not fully clear. In step 1. of the algorithm (line 181), it was not clear why n can always be decomposed in this\nway? What if n is a prime number ?\n\nWhen the number of nodes $n$ is a prime number, $(p, q)$ in line 2 in Alg. 3 becomes $(1, n)$ or $(n, 1)$,\nand then the Base-$(k+1)$ Graph becomes equivalent to the Simple Base-($k+1$) Graph.\nFor instance, when $(p, q)=(1,n)$, $\\mathcal{E}$ in line 11 is the graph sequence consisting of the Simple Base-$(k+1)$ Graph $A^{\\text{simple}}_k (V)$ and an empty graph.\nThen, thanks to the condition in line 12, the Base-($k+1$) Graph becomes equivalent to the Simple Base-($k+1$) Graph.\nSec. B.3 shows examples when the number of nodes is a prime number.\n\n> If the number of nodes n is a power of two, is it still beneficial to use your proposed topologies ? Including the larger range of n in figure 8 that covers power of 2\nmight be good.\n\nThe $1$-peer hypercube and $1$-peer exponential graphs are finite-time convergence only when the maximum degree is one,\nwhereas the Base-($k+1$) Graph is finite-time convergence for any maximum degree $k$.\nThus, if we need to use the topology with a fast consensus rate due to the high data heterogeneity,\nit is still beneficial to use the Base-$(k+1)$ Graph even when the number of nodes is a power of two.\n\nIn the camera-ready version, we will add the experimental results to evaluate the Base-$(k+1)$, $1$-peer hypercube, and $1$-peer exponential graphs in the setting where the number of nodes is a power of two.\n\n> Why did you not include the gradient tracking in comparison in figure 9?\n\nCommunication costs are one of the most important factors in decentralized learning,\nand Gradient Tracking requires twice as large communication costs as Decentralized SGD, $D^2$, and QG-DSGDm.\nThus, we evaluated our proposed methods with Decentralized SGD, $D^2$, and QG-DSGDm instead of Gradient Tracking.\n\n> When reading Figure 3, I got confused why the number of averaging steps is 5, while $\\log_2(5) < 3$.\n\nAs shown in Theorem 1, the upper bound of the length of the Simple Base-($k+1$) and Base-($k+1$) Graphs are not $\\log_{k+1} (n)$, but $2 \\log_{k+1} (n) + 2$.\n\n> In the Experiments section (Fig. 6, 7, 8, 9), having a Base-6 graph might still potentially be better than the Exponential graph, as its maximum degree would be\nthe same, but it would lead to the faster convergence. Why did you not include the Base-6 graph in the comparison?\n\n\nWe evaluated the Base-$6$ Graph with CIFAR-10, $\\alpha=0.1$, and $n=24$,\nshowing the results in the following table.\nNote that when $n=25$, the Base-$6$ Graph becomes equivalent to the Base-$5$ Graph.\nThe results indicate that the Base-$6$ Graph can further improve the accuracy.\nWe will evaluate the Base-$6$ Graph with other $n$ and add the experimental results in the camera-ready version.\n\n| Topology     | Accuracy        |\n|--------------|-----------------|\n| Exp.         | $86.3 \\pm 1.14$ |\n| 1-peer Exp.  | $85.5 \\pm 1.10$ |\n| Base-2 Graph | $87.2 \\pm 0.53$ |\n| Base-3 Graph | $88.1 \\pm 0.23$ |\n| Base-4 Graph | $88.8 \\pm 0.07$ |\n| Base-5 Graph | $88.8 \\pm 0.07$ |\n| Base-6 Graph | $89.7 \\pm 0.34$ |\n\n\n> It might be good to provide the open-source code of generating proposed topologies.\n\nOur code is contained in the supplementary material. We promise to make it public and add the GitHub repository URL in the camera-ready version.\n\n\n> When giving an example in Figures 3 \\& 4, I felt it might be better to have the same number of nodes n in both cases, so that the reader can see how is the Base-\n(k + 1) graph can reduce the number of steps from the Simple Base-(k + 1) graph.\n\nWe will add the illustration of the Simple Base-$2$ Graph with $n=6$ in Figs. $3$ or $4$ in the camera-ready version."}, {"review_id": "LCjXj2EnYq", "reviewer": "Reviewer_BhdZ", "summary": "This paper introduces the BASE-(k+1) GRAPH, a new way of designing topology for decentralized learning that is shown to enjoy a fast consensus rate while maintaining small maximum degree. The authors validate the effectiveness of the BASE-(k+1) GRAPH through experiments, demonstrating its finite-time convergence for certain number of nodes and its effectiveness for decentralized learning. Overall, the BASE-(k + 1) GRAPH offers improved communication efficiency and convergence rate for decentralized learning methods.", "questions": "- The reviewer would also like to know how the method can be extended to heterogeneous networks where the topology may not exhibit regular structures. \n\n- There are several other topologies that can also achieve fast consensus rate and small maximum degree; how the proposed method compares with them?\n\n- For a given number of nodes n, there exists several ways of decomposition, and different way of decomposition will lead to different maximum degree and consensus rate. The reviewer would like to know how one can find the optimal decomposition method to properly balance the maximum degree and consensus rate.\n", "limitations": "- The paper could benefit from a more detailed discussion of the limitations of the proposed approach, such as its sensitivity to certain types of data heterogeneity or its applicability to heterogeneous networks.\n\n- A more detailed description of the algorithm and its implementation (such as the decomposition method of node number n) would be helpful for readers who want to replicate the experiments or apply the method to their own problems.\n\n- The BASE-(k + 1) GRAPH should be compared with a wider range of existing topologies.\n\n- The derivation of Theorem 2 should be shown to help readers better understand the influence of BASE-(k + 1) GRAPH on the convergence of decentralized SGD.\n", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper proposes a new way of designing topology for decentralized learning, the BASE-(k + 1) GRAPH, which allows for a fast consensus rate while maintaining small maximum degree to enable more communication-efficient decentralized learning. \n\n- The authors provide a theoretical analysis of the proposed method which ensures the property of small maximum degree and several experiments are conducted to validate their claims.\n\n- The paper is well written and organized, with a logical flow of ideas. The authors provide a clear explanation of the proposed approach, and also includes helpful figures and tables to illustrate the concepts and results.\n\n", "weaknesses": "- The numerical experiments are still not sufficient; it would be more convincing if they compared the BASE-(k + 1) GRAPH with a more comprehensive set of topologies to demonstrate its superiority. As far as the reviewer know, there are several other topologies that can also achieve fast consensus rate and small maximum degree, such as Ring All-Reduce where maximum degree is 1 [a] , Tree All-Reduce where maximum degree is 2 [b] which and optimization-based topology [c].\n\n- The paper does not explain how to decompose n, whether different decomposition methods will produce different results and how to decompose n to get the best results.\n\n- The paper assumes a homogeneous network, which may not be practical in some real-world scenarios, where communication bandwidth and underlying topology constraints may affect the communication between nodes.\n\n[a] Alexander Sergeev and Mike Del Balso. Horovod: fast and easy distributed deep learning in tensorflow. arXiv preprint arXiv:1802.05799, 2018.\n\n[b] https://developer.nvidia.com/blog/massively-scale-deep-learning-training-nccl-2-4/\n\n[c] Sun, Chuangchuang, Ran Dai, and Mehran Mesbahi. \"Weighted network design with cardinality constraints via alternating direction method of multipliers.\" IEEE Transactions on Control of Network Systems 5.4 (2018): 2073-2084.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> The numerical experiments are still not sufficient; it would be more convincing if they compared the BASE-(k + 1) GRAPH with a more comprehensive set of\ntopologies to demonstrate its superiority. As far as the reviewer know, there are several other topologies that can also achieve fast consensus rate and smal\nmaximum degree, such as Ring All-Reduce where maximum degree is 1 [a] , Tree All-Reduce where maximum degree is 2 [b] which and optimization-based\ntopology [c].\n\nRing All-Reduce and Tree All-Reduce can also be regarded as the finite-time convergent sequence of graphs whose maximum degree is one and two, respectively.\nSpecifically, Ring All-Reduce can be regarded as the sequence of $n$ graphs,\nwhere $n$ is the number of nodes.\nHowever, as mentioned in line 97, most of the decentralized learning methods require the mixing matrix $\\mathbf{W}$ to be doubly stochastic (i.e., $\\mathbf{W} \\mathbf{1}_n = \\mathbf{1}_n$ and $\\mathbf{W}^\\top \\mathbf{1}_n = \\mathbf{1}_n$,\nand the average parameters that nodes have are the same before and after the communication).\nThen, the entire sequence of Ring All-Reduce satisfies this condition, but each graph in Ring All-Reduce does not satisfy this condition.\nTherefore, the sequence of graphs associated with Ring All-Reduce and Tree All-Reduce can not be used as the underlying network topology of decentralized learning methods.\n\n> The paper does not explain how to decompose n, whether different decomposition methods will produce different results and how to decompose n to get the\nbest results.\n\nThe main proposed method is the Base-($k+1$) Graph,\nand Sec. 4 and Algs. 1, 2, and 3 explain how to construct the Base-($k+1$) Graph.\nThe $k$-peer hyper-hypercube and Simple Base-$(k+1)$ Graphs are topologies introduced to illustrate the key ideas of the Base-$(k+1)$ Graph.\nThen, in Sec. B.3, we compare the Base-($k+1$) Graph with the Simple Base-($k+1$) Graph by showing many illustrations.\nIn Figs. 5 and 19, we demonstrate that the length of the Base-($k+1$) Graph is less than that of the Simple Base-($k+1$) Graph.\n\n> The paper assumes a homogeneous network, which may not be practical in some real-world scenarios, where communication bandwidth and underlying\ntopology constraints may affect the communication between nodes.\n\nThe prior works showed that communication efficiency is determined by the maximum degree of underlying network topologies in the homogeneous network setting (Neglia et al., 2019; Ying et al., 2021; Wang et al., 2019).\nFollowing these prior works,\nour work proposed novel topologies that can more successfully reconcile the convergence rates and communication efficiency than the existing topologies.\nIt is beyond the scope of our paper to address the heterogeneous network,\nbut the key idea of the Base-($k+1$) Graph may also be used to address the heterogeneous network setting \nbecause our key idea of splitting the set of nodes into subsets is a simple and fundamental method.\n\n> The reviewer would also like to know how the method can be extended to heterogeneous networks where the topology may not exhibit regular structures.\n\nThe Base-$(k+1)$ Graph is constructed with the constraint that its maximum degree is less than or equal to $k$.\nTo address the heterogeneous bandwidth network, \nit is interesting future research to extend the Base-($k+1$) Graph such that the degree of each node is less than the given hyperparameter, which can differ for each node.\nIt is not trivial to extend the Base-$(k+1)$ Graph to such heterogeneous network settings.\nHowever, the key idea of the Base-$(k+1)$ Graph may also be applicable \nbecause our key idea of splitting the set of nodes into subsets is a simple and efficient method.\n\n\n> There are several other topologies that can also achieve a fast consensus rate and small maximum degree; how the proposed method compares with them?\n\nPlease see the first response.\n\n> For a given number of nodes n, there exists several ways of decomposition, [...] The reviewer would like to know how one can find the optimal decomposition method to properly balance the maximum degree and consensus\nrate.\n\nPlease see the second response.\n\n> A more detailed description of the algorithm and its implementation (such as the decomposition method of node number n) would be helpful for readers who want to replicate the experiments or apply the method to their own problems.\n\nWe will make our implementation public and include the GitHub repository URL in the camera-ready version so that readers can reproduce our proposed method.\n\n> The derivation of Theorem 2 should be shown to help readers better understand the influence of BASE-(k + 1) GRAPH on the convergence of decentralized SGD.\n\nLet $\\mathbf{W}^{(1)}, \\cdots, \\mathbf{W}^{(m)}$ be mixing matrices of the Base-($k+1$) Graph.\nThese mixing matrices satisfy the following for any $\\mathbf{X} \\in \\mathbb{R}^{d \\times n}$:\n\n$$\n    \\| \\mathbf{X} \\prod_{k=1}^m \\mathbf{W}^{(k)} - \\bar{\\mathbf{X}} \\|^2_F = 0,\n$$\nwhere $\\bar{\\mathbf{X}} = \\frac{1}{n} \\mathbf{X} \\mathbf{1}_n \\mathbf{1}_n^\\top$.\nKoloskova et al. (2020) derived the convergence rate of Decentralized SGD with time-varying topologies.\nThus, substituting the above equation into Theorem 2 in (Koloskova et al. (2020)) yields our Theorem 2.\n\n### Reference \nKoloskova et al., (2020). A unified theory of decentralized SGD with changing topology and local updates. In International Conference on Machine Learning\n\nNeglia et al., (2019). The role of network topology for distributed machine learning. In IEEE Conference on Computer Communications.\n\nWang et al., (2019). Matcha: Speeding up decentralized sgd via matching decomposition sampling. In Indian Control Conference.\n\nYing et al., (2021). Exponential graph is provably efficient for decentralized deep training. In Advances in Neural Information Processing Systems"}, {"review_id": "f14RWrCO7O", "reviewer": "Reviewer_hhaz", "summary": "This paper introduces time-varying communication topologies to tackle the problem of communication efficiency in decentralized learning. These topologies, inspired by the idea of the 1-peer exponential graph, achieve finite-time exact consensus, meaning that the exact average of values is obtained after a finite number of steps. \n\nThe graph is obtained through an iterative process: starting from the k-peer hyper-hypercube graph (an extension of the 1-peer hypercube graph), the simple-(k+1) graph is introduced to handle the case when $n$ has large prime factors, using k-peer hyper-hypercube graph as a subroutine. Finally, the base-(k+1) algorithm is developed based on the two previous graphs to remove redundancy and obtain exact consensus in fewer iterations. \n\nThen, a convergence result is given based on the bound from Koloskova et al. (2020b), and experimental results suggest that the base-(k+1) graph improves over the (1-peer) exponential graph indeed. Unsurprisingly, more connected topologies lead to better accuracies in heterogeneous settings. ", "questions": "- Can you clarify how your method compares with optimized allreduce methods? For instance if you use it until exact consensus each time. What are the bandwidth/latency trade-offs achieved? How do they compare to existing results?   \n- How robust is the Base-(k+1) graph approach to failures/packet drops? Finite-time exact consensus would be lost in this case, but can we recover good approximation properties or is everything lost in this case? \n", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- Finite-time consensus for any number of nodes. \n- The bandwidth / speed trade-off can be controlled through parameter k (max degree at each iteration). \n- Great efforts are made to make the constructions understandable (though they still remain quite hard to grasp), through figures and step-by-step introduction. ", "weaknesses": "- I find the state of the art is not discussed in enough details. While decentralized methods are discussed in details, the finite-time consensus aspect calls to comparing with efficient allreduce methods as well, that are used to scale modern deep learning algorithms. I am not an expert in this domain, but a quick search led me to, e.g., refs [A,B,C] (but there are probably many relevant others). \n\nThe advantage of finite-time consensus is that updates can be done after each iteration, which is not necessarily the case with allreduce methods. At the same time, there are no guarantee on how close to the mean the iterates are before finite-time convergence, so several SGD steps without communication could also be performed between allreduce SGD for instance (local SGD style), which would not be too different. This could / should also be compared against. \n\nMinor comment: One can always have a number of nodes equal to a power of 2 by introducing some nodes with value 0 (and upweighing the other nodes), and making it so that each actual node owns at most 1 virtual node, thus at most doubling the effective degree. It's an easy way to use 1-peer exponential graphs for all n. \n\n[A] Rabenseifner, Rolf. \"Optimization of collective reduction operations.\" Computational Science-ICCS 2004: 4th International Conference, Kraków, Poland, June 6-9, 2004, Proceedings, Part I 4. Springer Berlin Heidelberg, 2004.\n\n[B] Mikami, Hiroaki, et al. \"Massively distributed SGD: ImageNet/ResNet-50 training in a flash.\" arXiv preprint arXiv:1811.05233 (2018).\n\n[C] Ueno, Yuichiro, and Rio Yokota. \"Exhaustive study of hierarchical allreduce patterns for large messages between gpus.\" 2019 19th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing (CCGRID). IEEE, 2019.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> [...] While decentralized methods are discussed in details, the finite-time consensus aspect calls to\ncomparing with efficient allreduce methods as well, [...] The advantage of finite-time consensus is that updates can be done after each iteration, which is not necessarily the case with allreduce methods. At the same time, there are no guarantee on how close to the mean the iterates are before finite-time convergence, so several SGD steps without communication could also be performed between allreduce SGD for instance (local SGD style), which would not be too different. This could / should also be compared against.\n\nOne potential advantage of the Base-$(k+1)$ Graph over All-Reduce with local steps is that\nwhen communication failures occur between nodes,\nAll-Reduce with local steps fails to converge to the stationary point, whereas the Base-$(k+1)$ Graph remains to converge.\nMore specifically, as we mentioned in line 97, most of the decentralized learning methods require the mixing matrix $\\mathbf{W}$ to be doubly stochastic (i.e., $\\mathbf{W} \\mathbf{1}_n = \\mathbf{1}_n$ and $\\mathbf{W}^\\top \\mathbf{1}_n = \\mathbf{1}_n$, \nand the average parameters that nodes have are the same before and after the communication.). \nIntermediate steps of All-Reduce do not entail doubly-stochastic mixing matrices, though the entire sequence of All-Reduce communication does.\nHence, even a single communication failure prevents us from guaranteeing convergence because the average parameters change before and after the communication.\nOn the other hand, even if communication failures occur, the Base-$(k+1)$ Graph satisfies this condition\nand enable decentralized learning methods to converge.\n\nAlthough it is beyond the scope of our paper to propose topologies that are robust to communication failures, \nour work will be an important step in the research to create topologies with high communication efficiency, fast convergence rate, and robustness to communication failures.\n\n> One can always have a number of nodes equal to a power of 2 by introducing some nodes with value 0 (and upweighing the other nodes), and\nmaking it so that each actual node owns at most 1 virtual node, thus at most doubling the effective degree. It's an easy way to use 1-peer exponential graphs for all\nn.\n\nThank you for the comments.\nThe reviewer's idea is also finite-time convergence for any number of nodes,\nbut servers need to have two parameters, the parameters of the actual and virtual nodes.\nThus, the Base-$(k+1)$ Graph is more memory efficient than the reviewer's idea.\nAdditionally, the $1$-peer exponential graph is finite-time convergence only when the maximum degree is one, \nwhereas the Base-$(k+1)$ Graph is finite-time convergence for any maximum degree.\nIt is also an important advantage of the Base-($k+1$) Graph over the reviewer's idea.\n\n> Can you clarify how your method compares with optimized allreduce methods? For instance if you use it until exact consensus each time. What are the\nbandwidth/latency trade-offs achieved? How do they compare to existing results?\n\nPlease see the first response.\n\n> How robust is the Base-(k+1) graph approach to failures/packet drops? Finite-time exact consensus would be lost in this case, but can we recover good\napproximation properties or is everything lost in this case?\n\nEven if communication failures occur,\nthe Base-$(k+1)$ Graph makes Decentralized SGD converge to the stationary point if there exists a path between any two nodes.\nHowever, if communication failures occur, the Base-($k+1$) Graph is no longer finite-time convergence\nand cannot make Decentralized SGD converge with the rate shown in Theorem 2.\nIt is an interesting future work to propose the topologies that are finite-time convergence even if communication failures occur,\nbut it is beyond the scope of our paper.\n"}, {"review_id": "tsZqMEzACc", "reviewer": "Reviewer_UfzT", "summary": "This paper studies communication-efficient topologies for decentralized learning. The proposed topology has four merits: (1) finite-time exact consensus; (2) fast consensus rate (having exact consensus using $O(\\log_{k+1} n)$ graphs); (3) arbitrary maximum degree ($1 \\leq k \\leq n-1$); (4) arbitrary number of nodes. The most related works to this paper are 1-peer exponential graphs, 1-peer hypercube graphs.  Given the existing algorithms, to the best of my knowledge, this paper is the first to get exact consensus using graphs of length $O(\\log_{k+1} n)$ instead of $O(\\log_2 n)$ with arbitrary number of nodes, where $k$ is the maximum degree. The main algorithm relies on k-peer hyper-hypercube graph. and simple base-(k+1) graph. The k-peer hyper-hypercube graph is a generalization of the 1-peer hypercube graph.  The simple base-(k+1) graph is constructed by dividing the graph into subgraphs with node numbers being a power of k, and then applying the 1-peer hypercube graphs, and using the communication between subgraphs.  The base-(k+1) graphs are constructed by decomposing $n = p\\times q$, where $p$ is prime to $q$ and the factors of $q$ are larger than k+1, and then, apply the sub-algorithms respectively.\n\nThe paper is generally well-written. The authors provide sufficient illustrations to show how the algorithms work and some numerical experiments to demonstrate the efficiency of their topologies. ", "questions": "* Is it possible to give theoretical guarantees for the claim that base-(k+1) graphs have shorter lengths than simple base-(k+1) graphs?\n\n* Are there efficient methods for each node to know its neighbors in each graph instead of generating the entire graph by each node?\n\n* Is it possible to extend the algorithm to more restricted topologies where each node can only communicate with a subset of nodes directly?", "limitations": "I would suggest the authors provide formal proof, or at least a sketch of proof, for the exact consensus of algorithm 1 (k-peer hyper hypercube graph).", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "* the length of graphs needed to have exact consensus is $O(\\log_{k+1} n)$, which improves upon the length $O(\\log_2 n)$ of the 1-peer exponential graphs. \n\n* the authors use lots of illustrations to show the implementation of the algorithms, which are very clear.", "weaknesses": "* The proof for the exact consensus of Algorithm 1 (k-peer hyper hypercube graph) is lacking.\n\n* Considering that the algorithm often divides the graph into many subgraphs, while the nodes do not have equal status, the topologies proposed in this paper are relatively complicated. The intricate graph structures could possibly limit its applications in practice, like delayed communication, compressed communication, and information loss. \n\n* The descriptions of the algorithm are only from a panoramic view. It is not clear whether there is a simple way for each node to know its neighbor in each graph efficiently.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\n> The proof for the exact consensus of Algorithm 1 (k-peer hyper hypercube graph) is lacking.\n\nIt is explained that the $k$-peer hyper-hypercube graph is the finite-time convergence in Sec. 4.1.\nIn the camera-ready version, we will add rigorous proof to show that the $k$-peer hyper-hypercube graph is finite-time convergence.\n\n\n> Is it possible to give theoretical guarantees for the claim that base-(k+1) graphs have shorter lengths than simple base-(k+1) graphs?\n\nThank you for pointing this out.\nThanks to line 12 in Alg. 3, the length of the Base-($k+1$) Graph is guaranteed to be less than or equal to that of the Simple Base-($k+1$) Graph. \nTo guarantee that the Base-$(k+1)$ Graph has the shorter or same length as the Simple Base-($k+1$) Graph,\nline 12 is necessary.\nIf we omit line 12, there exists the case where the Base-$(k+1)$ Graph is longer than the Simple Base-$(k+1)$ Graph, e.g., $(n, k) = (22, 4)$. \n\n> Are there efficient methods for each node to know its neighbors in each graph instead of generating the entire graph by each node?\n\nIt is possible to rewrite Algs. 2 and 3 as in Alg. 1,\nand if we rewrite Algs. 2 and 3 as in Alg. 1, the neighbors' indexes can be written as in line 7 in Alg. 1.\n\n> Is it possible to extend the algorithm to more restricted topologies where each node can only communicate with a subset of nodes directly?\n\nExtending the Base-$(k+1)$ Graph to the setting the reviewer mentioned is not trivial.\nHowever, we believe that the key idea of the Base-$(k+1)$ Graph can be used to construct such restricted topologies\nbecause the idea of splitting the set of nodes into subsets where the $k$-peer hyper-hypercube graph is applicable is a simple and efficient method."}]

Author rebuttal:

Meta-review: This paper delves into a significant inquiry concerning the design of communication graphs, with a focus on the "Base-k" graph, which facilitates swift consensus convergence through a finite number of gossip iterations. All reviewers acknowledge the paper's clarity and results. I'd like to emphasize the value of the comparison suggested by reviewer BhdZ, involving standard communication topology, and recommends its incorporation into the final version of this paper.
Decision: Accept (poster)