Exponential Graph is Provably Efficient for Decentralized Deep Training
Authors: Bicheng Ying
Kun Yuan
Yiming Chen
Hanbin Hu
Pan Pan
Wotao Yin
Venue: NeurIPS 2021 Poster (2021)
Keywords: Decentralized optimization
distributed and parallel algorithms
stochastic optimization
deep learning

Abstract: Decentralized SGD is an emerging training method for deep learning known for its much less (thus faster) communication per iteration, which relaxes the averaging step in parallel SGD to inexact averaging. The less exact the averaging is, however, the more the total iterations the training needs to take. Therefore, the key to making decentralized SGD efficient is to realize nearly-exact averaging using little communication. This requires a skillful choice of communication topology, which is an under-studied topic in decentralized optimization.

In this paper, we study so-called exponential graphs where every node is connected to $O(\log(n))$ neighbors and $n$ is the total number of nodes. This work proves such graphs can lead to both fast communication and effective averaging simultaneously. We also discover that a sequence of $\log(n)$ one-peer exponential graphs, in which each node communicates to one single neighbor per iteration, can together achieve exact averaging. This favorable property enables one-peer exponential graph to average as effective as its static counterpart but communicates more efficiently. We apply these exponential graphs in decentralized (momentum) SGD to obtain the state-of-the-art balance between per-iteration communication and iteration complexity among all commonly-used topologies. Experimental results on a variety of tasks and models demonstrate that decentralized (momentum) SGD over exponential graphs promises both fast and high-quality training. Our code is implemented through BlueFog and available at https://github.com/Bluefog-Lib/NeurIPS2021-Exponential-Graph.

Exponential Graph is Provably Efficient for Decentralized Deep Training
Bicheng Ying 1. Kun Yuan?*, Yiming Chen Hanbin Hu', Pan Pan', Wotao Yin? University of California, Los Angeles 2 DAMO Academy, Alibaba Group Google Inc. University of California, Santa Barbara ybc edu, (kun yuan, charles. cym hanbinhu@ucsb.cc edu, (panpan. pp, wotao yin Calibababbbbbbbaaaa inc. com
com,
Abstract
Decentralized SGD is an emerging training method for deep learning known for its much less (thus faster) communication per iteration, which relaxes the averaging step in parallel SGD to inexact averaging. 'he less exact the averaging is, however, the more the total iterations the training needs to take. Therefore, the key to making decentralized SGD) efficient is to realize nearly-exact averaging using little communication. This requires a skillful choice of communication topology, which is under-studied topic in decentralized optimization.
In this paper, we study so-called exponential graphs where every node is con- nected to (log((n) neighbors and n is the total number of nodes. This work proves such graphs can lead to both fast communication and effective averaging simultaneously. We also discover that sequence of log(n) one-peer exponential graphs, in which each node communicates to one single neighbor per iteration, can together achieve exact averaging. This favorable property enables one-pez exponential graph to average as effective as its static counterpart but commu- nicates more efficiently. We apply these exponential graphs in decentralized (momentum) SGD to obtain the state-of-the-art balance between per-iteration topologies.
communication and iteration complexity among all commonly Experimental results on a variety of tasks and models demonstrate that decen- tralized (momentum) SGD over exponential graphs promises both fast and high- quality training. Our code is implemented through BlucFog and available https://gitaie httpg//ttuu...ooBll.. Liweeroooobb/NeeurrP522222 Exponnntiiiipnniiall..... Graph.
Introduction
Efficient distributed training methods across multiple computing nodes are critical for large-scale modern deep learning tasks. Parallel stochastic gradient descent (SGD) is widely-used approach, which, at each iteration, computes globally averaged gradient either using Parameter-Sent All-Reduce [47] Such global coordination across all nodes in parallel SGD results in either significant bandwidth cost or high latency, which can notably hamper the training scalability.
[28]
30 based on partial averaging has been one of the promising alternatives to parallel SGD in distributed deep training. Partial averaging, as opposed to the global averaging exploited in parallel SGD, only requires each node compute the locally averaged model within its neighborhood. Decentralized SGD does not involve any global operations, so has much lower communication overhead per iteration. The fewer neighbors each node needs to communicate, the more efficient the per-iteration communication is in decentralized SGD.
Decentralized SGD 45
Equal Contribution. Corresponding Author: Wotao Yin
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Table 1: Comparison between decentralized (momentum) SGD over (some) various commonly topologes. The table assumes homogeneous data distributions across all nodes (which is practical for deep training within a data-center). The comparison for heterogegggg scenarios, and with more other topologies. is listed in
Appendix [
The smaller the transient iteration complexity is, the faster decentralized algorithms will converge.
Topology
Ring
Grid
Rand-Grapp Rand-Match
Static Exp
One-peer Exp
Per-iter Comm.
(2(2)
(44)
((2)
2(1))
((log((n)) 12(n log3(n)) I(n logg(n)
2(1)
Trans. Iters.
2(n²)
((n
(2()))
The reduced communication in decentralized SGD comes with a cost: slower convergence. While it can asymptotically achieve the same convergence linear speedup as parallel SGD [3 3 25 64] i... the training speed increases proportionally to the number of computing nodes (see the definition in Sec. decentralized SGD requires more iterations to reach that stage due to the ineffectivenness to aggregate information using partial averaging. We refer those iterations before decentralized SGD reaches its linear speedup stage as transient iterations (see the definition in Sec. 2 which an important metric to measure the influence of partial-averaging of decentralized SGD, The less effective the partial averaging is, the more transient iterations decentralized SGD needs to take. Fig. Tillustrates the transient iterations of decentralized SGD for the logistic regression problem. It is observed that decentralized SGD can asymptotically converge as fast as parallel SGD, but requires more iterations (i.e., transient iterations) to reach that stage.
48 65 on convergence rate
Per-iteration communication and transient iterations in de- centralized SGD are determined by the network topology (we also use graph interchangeably with topology). The maximum degree of the graph decides the communication cost while the connectivity influences the transient itera- tion complexity. Generally speaking, a sparsely-connected topology communicates cheaply but endows decentralized SGD with more transient iterations due to the less effec- tive information aggregation. A skillful choice of network topology, which is critical to achieve balance between per- iteration communication and transient iteration complexity, is under-studied in literature.
10
Decentralized SGD Parallel SGD
Mean-Squre Error
10
10-1
10-2
Transient Iterations
10-3
2000
4000
6000
8000
Iberationn
Figure 1: Illustration of transient iters. Experimental setting is in Appendix D.3
This work studies exponential graphs which are empiri- cally successful B 61 (2
14 67 but less theoretically understood in deep training. Exponential graphs have two variants. In static exponential graph, each node communicates to floga (n)) neighbors (see Sec. and Fig. 2). In one-peer exponential graph, however, each node cycles through all its neighbors, communicating, only, to single neighbor per iteration (see Sec. a Fig. (2) This paper will first clarify the connectivity and averaging effectiveness of these exponential graphs, and then apply them to decentralized momentum SGD to obtain the state-of-ther balance between per-iteration communication and transient itcration complexity among all commonly-used topologies. Our main results (as well as our contributions) are:
We prove that the spectral gap, which is used to measure the connectivity of the graph (see the definition in Sec. 2) of the static exponential graph is upper bounded by 0(1 (1//log((n)). Before us, many literatures (e.g. (27) claimed its upper bound to be ((1) incorrectly.
Since one-peer exponential graphs are tireenarying, it is difficult to derive their spectral gaps. However, we establish that any (n) consecutive sequence of one-peer exponential graphs can together achieve exact averaging when n is power of 2.
With the above results, we establish that one-peer exponential graph, though much sparser than its static counterpart, surprisingly endows decentralized momentum SGD with the same convergence rate as static exponential graph in terms of the best-known bounds.
We derive that exponential graphs achieve 52(1 P per-iteration communication and 2(2²) tran- sient iterations, both of which are nearly the best among other known topologies, see Table The one-peer exponential graph is particularly recommended for decentralized deep training.
We conduct extensive industry-level experiments across different tasks and models with various decentralized methods, graphs, and network size to validate our theoretical results.
Notation (2-)) hides all logarithm factors.
2

---

static exp.
Binnaiion
obe-pocr repeat period-wise
Figure Illustration the static and one-peer exponential graph.
2 Revisit Decentralized Momentum SGD and Related Works
This section reviews basic concepts and existing results on decentralized momentum SGD. Problem. Suppose computing nodes cooperate to solve the distributed optimization problem:
min f(x) Σ fi(z) where f((x) ==
(1)
Function fz) is local to node i, and random variable & denotes the local data that follows distribution D,. We do not assume each distribution D, is the same across all nodes.
Network topology and weights. Decentralized methods are based on partial averaging within neighborhood that is defined by the network topology (see the figure an example of six nodes). We assume all computing nodes are connected by (directed or undirected) network topology. We define Wiy, the weight to scale information flowing from node to node i, as follows:
node j is connected to i, or = j:
Wij
(2)
0
otherwise.
Mg (ilua > 0} is defined as the of neighbors of node which also includes node itself and the weight matrix W := [wyy][ E _ax= are denoted as matrix that stacks the weights of all nodes. This matrix W characterizes the sparsity and connectivity of the underlying network topology.
Decentralized momentum SGD (DmSGD). There are many variants of decentralized mo- mentum SGD B 20 32 67]. This paper will
Algorithm 1 DmSGD
Initialize 7, x (0) let m; (0) 0, B (0,
focus on the one proposed by [64] (listed in Al-
For k = 1,2 T - 1, every node i do
gorithm D. which imposes an additional partial- averaging over the momentum achieve further speed up. The topology is allowed to change with iterations. When W W. topology and weight matrix will remain static.
Sample weight matrix ((k;;
FF(x (x) (*)));
Update gradient g.
m (k+1) = EjEN, (1) (Amg (R) + 9] (K)
x (x+1) = =GEN. w (m) ym ym/h)) (k)):
(K) (k)
Assumptions. We introduce several standard assumptions to facilitate future analysis:
A.1 [SMOOTHNESS] Each f<(x)) is L-smooth, i.e., [[V v(((1)) S -|lx-y/l for any x. E I&d.
A.2 [GRADIENT NOISE] The random sample (k) is independent of each other for any is and i. We also assume E[VF(z;;)) = V f((x) and EE|V F(r;;) Vf(x)) < o².
A.3 [DATA HETEROGENEITY] holds that 1 n Σn [ v2 < 6² for any x Rd.
A.4 [WEIGHT MATRIX] The weight matrix ((k) doubly-stochastic, i.e. W 1 and (k) I If (k) = W, assume p(W)= maxx, (1 (0, 1), where (W) is the i-th th eigenvalue of the matrix W
The quantity - which is also referred to as the spectral gap of the weight matrix W, measures how well the topology is connected (53). In the large and sparse topology which most valuable deep training, it typically holds that 1 - 0.
When there is no ambiguity, we simply use instead of p(W). Throughout the paper we do NOT use as spectral radius. Instead, it is the second largest eigenvalue in magnitude. Note we cannot directly sort the eigenvalues since W is not necessarily symmetric and the eigenvalue can be complex number.

---

Communication overhead. According to [S]. global averaging across nodes either incurs (n) bandwidth cost via Parameter-Server, or (2()) latency via Ring-Allreduce. In either way, it takes (2
per-iteration communication time, which is proportional to the network size n. As to decentralized methods, we will similarly assume the per-iteration communication time to be Q2mmximum degree). Convergence. Under Assumptions A.1-A.4, DmSGD with static topology will converge at [64] 25
( o² VnT
no²
nb²2
E
T(1 - p) T(1 - p)
in which x(() Ei=1
x; (8) It is worth noting that no analysis in literature, to our knowledge, exists for DmSGD over time-varying topologies with non-convex costs.
Linear speedup. When 7' is sufficiently large, the first term 1/VnT dominates 33. This also applies to parallel SGD. Decentralized and parall SGDs all require T ((1/(ne)) iterations to reach a desired accuracy e, which is inversely proportional to n. Therefore, an algorithm is in its linear-speedup stage at Tth iteration if, for this T, the term involving nT is dominating the rate.
Transient iterations. Transient iterations are referred to those iterations before an algorithm reaches linear-speedup stage. that is when T is relatively small so non-n? terms still dominate the rate (see illustration in Appendix C To reach linear speedup. T has to satisfy (derivation in Appendix
Homogeneous data: T= (
n
n
Heterogeneous data: T S
p}
p)
(4)
which corresponds to the transient iteration complexity in the homo/hetero-geneon data scenarios.
2.1 Related Works
Decentralized deep training. Decentralized optimization originates from the control and signal processing community. The first decentralized algorithms on general optimization problems include decentralized gradient descent [55) diffusion 51 and dual averaging [18). In the deep learning regime, decentralize SGD, which was established in 30 to achieve the same linear speedup as parallel SGD in convergence rate, has attracted a lot of attentions. Many efforts have been made extend the
algorithm to directed topologies 3 42 time-varying topologies [25] 42), asynchronous settings [1], Techniques such as quantizaton/coopresiinn
and data- hatta-heeerogeeeuur scenarios (57
62
32
2 2,8. 26 24, 588 (3),, periodic updates
55
and lazy communication [37 38 13] were also
integrated into decentralized SGD to further reduce communiation overheads.
Topology influence. The influence of network topology on decentralized SGD was extensively 27]. All these works indicate that a well-connected topology will significantly accelerate decentralized SGD. Two directions have been explored to relieve the influence of network topology. One line of research proposes new algorithms that are less sensitive to topologies. For example, 66
studied in (25 51 66|
45|
57 I removed data heterogeneity with bias-correction techniques in utilized periodic global averaging or multiple partial averaging steps. All these methods have improved topology dependence. The other line is to investigate topologies that enable communication-efien
23
65
68 29
69 and 14
decentralized optimization. 43 [5] examined various topologies (such ring, grid, torus, expander, etc.) on averaging effectiveness, which, however, are either communication-costy or averaging-ineffecnt in this paper. [41 6, 9 10] studied random graphs (such as Erdos-Rent random graph and random geometric graph) in which each edge is activated randomly. The randomness of the edge activation can cause highly unbalanced degrees of each node in the graph, which may significantly affect the efficiency in per-iteration communication.
compared to exponential graphs studied
Algorithms with time-varying topologies. Many previous works have studied decentralized al- gorithms with vimeinarying topologies. 42 and 44 examined the convergence of decentralized (deterministic) gradient descent and gradient tracking under convex scenarios. [17] 52 investigated gradient tracking under non-convex scenarios, but it did not clarify the influence of the time-varying graphs on convergence rate. In the stochastic scenario, [25] illustrates how decentralized SGD is influenced by time-varying topologies in the non-convex scenario. However, its analysis cannot be directly extended to the decentralized momentum SGD studied in this work.

---

Another related work is the Matcha method [60] based on disjoint matching decomposition sampling. Whilesimmlar to Matcha, decentralized SGD over one-peer exponential graphs has several fundamental differences. First, one-peer exponential graph is directed while Matcha only supports undirected and symmetric matching decomposition, Second, the favorable periodic exact-average property of one-peer exponential graphs only holds when sampled cyclicly. However, Matcha only supports independent and random matching samples analysis. For these reasons, Matcha cannot cover one-peer exponential graphs (especially when momentum is utilized in decentralized SGD).
Note. This paper considers deep training within high-performanee data-center clusters, in which channels and the network topology can be fully
all GPUs are connected with controlled. It is not for the wireless network setting which the topology cannot be changed freely.
Spectral Gap of Static Exponential Graph
As discussed above, the graph maximum degree decides the per-iteration communication cost while the spectral gap determines the transient iteration complexity (see 44) is critical to seek topologies that are both sparse and with large spectral gap 1 - simultaneously. In this section, we will establish that the static exponential graph, which was first introduced in 3 30]. one of such topologies.
In static exponential graph, each node is assigned an index from 0 to
1 and will communicate to neighbors that are 20, "",2",... ... "......,,lllee (1 hops away. The left plot in Fig. 2 illustrates a directed
6-node exponential network topology. With maximum degree [logg (n)] neighbors, partial averaging over the static exponential graph will take (((oggg() communication time per iteration. However,
remains unclear what the spectral gap is for this topology.
Weight matrix associated with static exponential graph is defined as follows:
if loga (mod(j i, n)) is an integer or i =
[oga
(5)
otherwise.
An example weight matrix associated with the static exponential graph in Fig. 2 is in Appendix A.1 The following proposition evaluates the spectral gap p for weight matrix in
Proposition 1 (SPECTRAL. GAP OF STATIC EXPO) The spectral gap of matrix 5 which can also
be interpreted as the second largest magnitude of eigenvalues, satisfies (Proof in Appendix A.2)
2
when is even number
1 + flog (n)
1 P-W(W)XP)
(6)
2
when is odd number
1 + [log,
In addition, we have [[Wexp-
1 11 ((Wexp).
Remark For a general non-symmetric matrix W, it typically holds that I[ - 1111 -W.11171 # p(W).
Proposition 1 establishes ||
111 p(Wox)) for exponential graph.
Remark The hypercube graph established in [59 Chapter 16] to have the spectral gap as 1 1- (rpp(((HeeCumse exponential graph, there are two fundamental differences between these two gruphs: (a) the hypercube gruph has to be undirected and the corresponding W is symmetric; (b) the number of vertices of hypercube must be a power of 2, i.e., n = 2 for some positive integer т. In comparision, the exponential graph is more flexible in the size of the graph structure.
2/(1 + logz(n)). While such spectral gap is on the sume order the
Remark Proposition I clarifies the spectral gap of the static exponential graph. Many literatures before this work (such as (27) claimed the spectral gap to be O(1), which is not accurate.
The theoretical analysis of Proposition] is non-trivial. To evaluate the spectral gap, for any network size n. we have derive the analytical expression for each eigenvalue using Fourier transform and calculate the magnitudes. The most tricky part is to assert which eigenvalue expression attains the second largest value.
5

---

We now numerically validate the established spectral gap. In Fig. ]] we plotted the spectral gap of the static exponen- tial graph with ranging from 4 to 290. It is observed that the derived gap p
The second largest magnitude of eigenvalue
1.0
8/10
2/(1 + [n)] (see the black dashed line). In fact, it exactly matches the numerical spectral gap when n is even. Moreover, it is also observed the spectral gap of static exponential graph much smaller than that of ring or grid.
very tight
0.8
5/7
p/s
2/4
Exp.
Finally, we compare the spectral gap and maximum de- gree of the static exponential graph with all other common graphs in Appendix A.3] It is observed that static exponen- tial graph, while with sightly larger maximum degree, has significantly smaller spectral gap than ring and grid.
Ring
Grid
Theoratical Bound
300
Number of nodes
Figure 3: Spectral gap of some topologies.
4 One-Peer Exponential Graph Achieves Periodic Exact-Averaging
Static exponential graph incurs (llogg (n)) communication overhead per iteration. To overcome this issue, [] proposes to decompose the static exponential graph into a sequence of one-peer graphs, in which each node cycles through all its neighbors, communicating, only, to a single neighbor per iteration, the right plot in Fig. 2 Apparently, each one-peer realization incurs (2(1) communication cost, which matches with ring or grid. Since each realization is sparser than the static graph, one may expect DmSGD with one-peer exponential graphs are less effectiive in aggregating information. In the following, we will establish an interesting result: one-peer is very effective averaging.
Time-varying weight matrix. We let [1o] The weight matrix at iteration k: is
if (mod( - i, n)) mod(k;
(k) W
i
otherwise.
The weight matrix for each realization of the one-peer exponential graphs in Fig. 2 Appendix B.I Since each node communicates to one single neighbor per iteration, the resulting weight matrix very sparse, with only one non-zero element the non-diagonal positions per row and column. Periodic exact-averaging. The periodic exact-averaging property, which was observed by Bl without theoretical justifications, is fundamental to clarify the averaging effectiveness of one-peer exponential graphs. The following lemma proves that the property holds when n is power of 2.
Lemma (PERIODIC EXACT AVERAGING) Suppose T = logg(n) is a positive integer. Wf is the weight matrix generated by (7) over the one-peer exponential graphs, it then holds that each W (k) is doubly-stochastic, i.e. W W 1- = 1l and 1 (''(k) = 1s Furthermore, it holds that W(
(((+ p -117
(8)
n
for any integer k 2 0 and E 2 T. And equivalently, the consensus residue form holds that
(W(++)) 11 TT (w(++e-1)_ n - ... (w(k) 1 -11111 = 0
n
(Proof is in Appendix B.2
The assumption that logg(1) (1)) is positive integer seems necessary. We numerically tested various one-peer exponential graphs with non-integer log, (n). None of them is endowed with the periodic exact-average property.
Remark 4
When (ngz(n) is positive integer and each realization of the one-peer exponential graph is sampled without replacement, is easy to verify that the periodic exact-averaging property still holds. However, if each realization is sampled with replacement, the periodic exact-averaging property generally does not hold unless all realizations are occasionally sampled without repeating.
Remark 5
Remark 6 It is worth noting that one-peer variant of the hypercube graph is established to achieve exact averaging with r = log,, (n) steps (54%. Such one-peer hypercube is undirected and symmetric, which is from the one-peer exponential graph which is directed and asymmetric.

---

We now numerically validate Lemma 1 To this end. we initialize vector E R" arbitrarily, and examine how ((Ut)oW n |= decreases with iteration k. The weight matrix (*)) either static or samples from one- peer exponential graph bipartite random match graph. In Fig. 4 it is observed that one-peer exponential graphs achieve exact average after 1og2(1) steps, which incides with the results in Lemma] [ In contrast, the static exponential and bipartite random match graphs can only achieve the global average asymptotically, The justifica- tion for Remarks 4 anddSS in Appendix B.3
Consensus Residue
10-1
10
10
10-7
10-9
0.5 1-0
S.E. hwd
R.H n-6
0. 5-32
S.E. n-:22
R. n-32
0.E 1-128
R.M n-128
0. 5-532
SE ne512
R.M n-512
10 13
10
15
20
25
Iterations
Figure 4: Illustration of how consensus residues decay with iterations for various graphs. O.E. and S.F. denote one-peer and static exponential graphs, and R.M. denotes bipartite random match graph.
5 DmSGD with Exponential Graphs
With the derived property in Sec. 3 and 4 this section will examine the convergence of DmSGD with static and one-peer exponential graphs.
DmSGD with static exponential graph. Based on Proposition I we can achieve the convergence rate and transient iterations, by following analysis in [64], of DmSGD with static exponential graph.
()( B)s VT
Corollary Under Assumptions A. A.I-A.4, if
DmSGD (Algorithm
will converge at
1 T
( k=1
|12 ( BnT
n log, -
+ n21 - -802 1002l)))))))) (10)
T
T
Furthermore, the transient iteration complexity of DmSGD over static exponential graph is (n log for data-homogeneous scenario and (n² (n) for data-heterogeneons scenario.
DmSGD with one-peer exponential graph. With each realization being sparser than its static counterpart, one-peer exponential graph believed to converge slower. However, the periodic exact- averaging property can help DmSGD achieve the same convergence rate as its static counterpart. Note that DmSGD with one-peer exponential graph an one-loop algorithm, see Algorithm | The DmSGD updates start immediately after sampling one weight matrix.
Theorem We assume T = (ogz(n) is positive integer, and the time-varying weight matrix is
(11
generated by 7 over one-peer exponential graphs. Under Assumptions A. 1.A and y /T DmSGD (Algorithm 7) will converge at (Proof is in Appendix
Σ T
T
EIVI((
(V BynT
(
o²
n(1 - -3)a²T
n01 3)b222
(11)
V(I-B)TT
T
T
Furthermore, the transient iteration complexity of DmSGD over one-peer exponential graph is (n log)(n)) for hult-hhomggeeous scenario and O log)(n)) for duta-hhteroggneeuu scenario.
with (10), and noting that = log, (n), ) we conclude that DmSGD with one-peer graphs converge exactly as fast as with the static counterpart in terms of the established rate bounds. In addition, both graphs endow DmSGD with the same transient iteration complexity.
Remark 7 Comparing T1
Remark We can also achieve the convergence rate for decentralized SGD (i.e., DSGD without momentum acceleration) with one-peer exponential graph by setting 3 = 0. It is easy to verify that DSGD with one-peer graphs can also converge as fast as with the static exponential graph.
The convergence rate and transient iteration complexity of DSGD with general mixing matrices sampling strategy are also studied in (25). However, the results in reference (25) does not cover the scenario with momentum acceleration. As we show in the proof details, is highly non-trivial to handle momentum.
Remark
7

---

It is worth noting that the analysis for the above theorem is non-trivial. While it targets on the one- one-peer exponential graph, the analysis techniques can be extended the general time-nrying topologies. To our best knowledge, it establishes the first result for DSGD with momentum acceleration, over the time-varying topologies, and in the non-convex settings. Existing analysis either focuses on DSGI) without momentum [25] or DmSGD with static topologies [64]. In addition, the last two terms in (I), actually, can be further tightened by the spectral gap of one-peer exponential graphs. Since the tightened terms are rather complicated, we leave them to the discussion in Appendix D.4
State-of-the-art balance between communication and convergence. Table I (and tables Ap- pendix D.5) summarize the per-iteration communication time and transient iteration complexity for all commonly-usee topologies. When n is sufficiently large, the term log, (12) can be ignored. In this scenario, the exponential graphs (including both static and one-p variants) achieve state-of-the-art
(11) per-iteration communication and (2(n²) transient iterations, in which f2(-) hides all logarithm factors. In Appendix [ we numerically validate that exponential graphs have smaller transient iteration complexity than ring or grid graph as predicted in Table [ The comparison between ex- ponential graph with random graphs [4]
6 9 [0] (such as the Erdos-Renyi graph and geometric
random graph) is discussed in Appendix A.3.3
One-peer exponential graph is recommended for decentralized deep training. It because one- peer exponential graph endows DmSGD with the same convergence rate as its static counterpart, but incurs strictly less communication overhead per iteration.
6
Experiments
This section will validate our theoretical results by extensive deep learning experiments. First, we evaluate how DmSGD with exponential graphs perform against other commonly-used graphs with varying network size. Second, we examine whether one-peer exponential graphs achieve the same convergence rate and accuracy as its static counterpart across different tasks, models, and algorithms.
Metrics. Training time and validation accuracy are two critical metrics examine the effectiveness of a distributed training algorithm in deep learning. These two metrics are typically evaluated after the algorithm completes a fixed number of epochs (say, 90 epochs). Training time can reflect the communication efficiency while accuracy, though might not be precise, can roughly measure the convergence rate (or iteration complexity). These two metries are used in most of our experiments.
6.1 Setup
We implement all decentralized algorithms with PyTorch [46] 1.8.0 using NCCL 2.8.3 (CUDA 10.1) as the communication backend. For parallel SGD, we used Py Torch's 's native Distributed Data Parallel (DDP) module. For the implementation of decentralized methods, we utilize BlueFog (63. which is a high-performance decentralized deep training framework, to facilitate the topology organization, weight matrix generation, and efficient partial averaging. We also follow DDP's design to enable computation and communication overlap. Each server contains V100 GPUs in our cluster and is treated as one node. The inter-node network fabrics are 25 Gbps TCP as default, which is common distributed training platform setting.
6.2 Exponential graphs enable efficient and high-quality training
In this subsection we evaluate how DmSGD with exponential graphs perform against other commonly- used topologies in the task of image classification.
Implementation. We conduct series of image classification experiments with the ImageNet- K [6], which consists of 1,281,167 training images and 50,000 validation images in 1000 classes. We train classification models with different topologies and numbers of nodes to verify our thcoretical findings. The training protocol in (21] is used. In details, we train total 90 epochs. The learning rate is warmed up in the first 5 epochs and is decayed by a factor of 10 at 30, 60 and 80-th epoch. The momentum SGD optimizer is used with linear learning rate scaling by default. Experiments are trained in the mixed precision using Pytorch native amp module. We implement DmSGD with all graphs listed in T The details of each graph is described in Appendix [E] For each graph, we test the training time and validation accuracy for DmSGD with GPU numbers ranging from 32 to 256.
Experiment results. The comparison between different graphs (with varying size) top-1 validation accuracy and training time after 90 epochs is listed in Table Major observations are:
8

---

Table 2: Comparison top-1 validation accuracy(%) and training time (hours) with different topologies.
NODES
4(4x8 GPUs)
8(8x8 GPUs) ACC.
16(16x8 GPUS)
32(32x8 GPUs)
TOPOLOGY
ACC.
TIME
TIME
ACC.
TIME
ACC.
TIME
RING
76. #0.023
11.6 76.07 #0.013
6.5
76.08
#0.026
3.3
75.58
#0.021
1.8
GRID
76.08 #0.007
11.6
76.35 #0.037
6.7
75.88
#0.011
3.4
75.76
2.0
BI-RAND. MATCH.
75.96 #0.032
11.1 76.26 #0.027
5.7
76.07
#0.012
2.8
75.83 #0.029
1.5
RANDOM GRAPH
75.97 #0.028
11.5 76.01 #0.033
7.1
76.18 #0.008
6.7
76.24 #0.018
4.7
STATIC EXP. 76.21 #0.028
11.6
76.32 #0.037
6.9
76.30
#0.007
4.1
76.28
#0.020
2.5
ONE-PEER 76.28 #0.063
11.1 76.47 #0.035
5.7
76.42
#0.030
2.8
76.30
#0.062
1.5
[1] All graphs (except the random graph) endows DmSGD with training time linear speedup. Among them, bipartite random matching and one-peer exponential graphs achieve the best linear speedup due to their efficient per-iteration communication. However, the accuracy of the matching graph cannot match one- pper exponential graph. The random graph fails to achieve linear speedup because of its extremely expensive communication overheads.
[2] In the 32 8 GPUs scenario, the training time finish all 90 epochs can be sorted as follows: one-peer ~ Bi-RandMatch < Ring < Grid < static exponential < random graph, which coincides with the per-iteration communication time listed in Table
[3] In the 32 8 GPUs scenario, the training accuracy achieved by each graph after 90 epochs is sorted as follows: random graph z static exponential = one-peer > Bi-RandMatch > Grid > Ring, which coincides with the transient iteration complexity listed in Table Note that the random graph rather dense (sce the detail in Appendix A.3.T so it has good accuracy but consumes significant wall-clock time in training.
With the second and third observations, we can find exponential graphs (especially the one-peer exponential graph) can enable both fast and high-quality training performance. We also examined the performance of exponential graphs when n is not a power of 2, see Appendix
6.3 One-peer exponential graph v.s. static exponential graph
In this subsection will focus on the two exponential graphs studied in this paper. In particular, we will validate that one-peer exponential graph endows DmSGD with the same convergence rate as its static counterpart (i.e.. the conclusion in Remark 7 across different tasks, models, and algorithms.
Comparison across models and algorithms. Now we compare one-peer and static exponential graphs with different neural network architectures and algorithms. The task is image classification and the setting is the same as in Sec.[6.22 We test both graphs for ResNet [22). MobileNetv2 (50) and EfficientNet [56]. which are widely-used models in industry. In addition the DmSGD algorithm (Algorithm D studied in this paper, we also examine how exponential graphs perform with other commonly-use decentralized momentum method: the vanilla DmSGD 3 which does not exchange momentum between neighbors, and QG-DmSGD (32 which adds a quasi-global momentum to relieve the influence of data heterogeneity. We do not examine DecentLaM [67] and D2 [57] because both methods require symmetrrc weight matrix during the training process which exponential graphs cannot provide. We also list the performance of parallel SGD using global averaging as one baseline.
Table B] lists the top-1 valida- tion accuracy comparison across all models and algorithms. In all scenarios, is observed that
Pap.
Too1 Accurao
70
Ln C
One peer Exp
60
Train Loss
50
both graphs can lead to roughly
700
the same accuracy across mod- els and algorithms. The accuracy difference (DIFF) is marginal.
0.90
20
Static Exp.
2J
33500
One
We also depict the convergence curves in training loss and ac- curacy for DmSGD with both graphs in Fig. [] It shows both curves evolve closely to each other, indicating that one-peer exponential graph enables DmSGD with the same convergence rate as its static counterpart. This is consistent with Theorem and Remark than static exponential graph (see Table 2. it is
20
40
80
10000 20000 30000 40000 sodop iterations
Epoch
Figure 5: Convergence curves on the ImageNet (ResNet-50) in terms of training loss and validation top-1 accuracy Network size is 8 x 8 GPUs.
7 Since one-peer is more communication-effiee recommended to utilize one-peer exponential graph decentralized deep training. In addition, we observe that decentralized methods, while utilizing partial-averaging during training process, has

---

Table 3: Top-1 validation accuracy and wall-clock time (in hours) comparison with different models and algorithms on ImageNet dataset over static/one- peer exponential graphs (8x8 GPUs).
MODEL
RESNET-50
MOBILENET-V2
EFFICIENTNET
TOPOLOGY
STATIC
ONE-PEER
STATIC
ONE-PEER
STATIC
ONE-PEER
PARALLEL SGD
76.21 (7.0)
70.12 (5.8)
77.63 (9.0)
VANILLA DMSGD
76.14 (6.6) 76.06 (5.5)
69.98 (5.6) 69.81 (4.6)
77.62 (8.4)
77.48 (6.9)
DMSGD
76.50 (6.9)
76.52(5.7)
69.62 (5.7)
69.98
(4.8)
77.44 (8.7)
77.51 (7.1)
QG-DMSGD
76,43 (6.6) 76.35(5.6)
69.83 (5.6) 69.81 (4.6)
77.60 (8.4)
77.72 (6.9)
significant accuracy degradation compared parallel SGD. Decentralized SGD can even be superior sometimes.
Comparison across different tasks. We next compare the aforementioned algorithms with one- peer and static exponential graphs in another well-known task: object detection. We will test the following widely-used models: Faster-RCNN [49] and RetinaNet (34) on popular PASCAL VOC 19 and COCO 35 datasets. We adopt the MMDetection 112 framework as the building blocks and utilize ResNet-50 with FPN (6) as the backbone network. We choose mean Average Precision (mAP) as the evaluation metric for both datesets. We used GPUs (which are connected by the static or dynamic exponential topology) and set the total batch size as 64 in all detection experiments.
Table compares the performance of decentralized training across different object detection models and datasets. Similar to the above experiment, is observed that both graphs enable decentralized algorithms with almost the same performance in each scenario. This again illustrates the value of one-pees exponential graph in deep learning tasks it endows decentralized deep training with both fast training speed and satisfactory accuracy.
Table 4: Comparison of different methods and models on PASCAL VOC and COCO datasets.
DATASET
PASCAL VOC
COCO
MODEL
RETINANET
FASTER RCNN STATIC
RETINANET STATIC
FASTER RCNN
TOPOLOGY
STATIC
ONE-PEER
ONE-PEER
ONE-PEER
STATIC
ONE-PEER
PARALLEL SGD
79.0
80.3
36.2
37.2
VANILLA DMSGD
79.0
79.1
80.7
80.5
36.3
36.1
37.3
37.2
DMSGD
79.1
79.0
80.4
80.5
36.4
36.4
37.1
37.0
QG-DMSGD
79.2
79.1
80.8
80.4
36.3
36.2
37.2
37.1
Conclusion and Future Works
In this paper, we establish the spectral gap of static exponential graph and prove that any loga (n) consecutive one- exponential graphs can together achieve exact averaging when n is power 2f With these results, we reveal that one-peer exponential graphs endow DmSGD with the same convergence rate as their static counterpart. We also establish that exponential graphs achieve nearly minimum per-iteration communication time and transient iteration complexity simultaneously when is large. All conclusions are thoroughly examined with -taandrdll- benchmarks. As the future work, we will investigate symmetric time-varying graphs that can perform well as one-peer exponential graph. Symmetric graphs are critical for D and DecentLaM algorithms.
Acknowledgements
The authors grateful to Dr. Sai Praneeth Karimireddy from EPFL for the helpful discussions the hypercube graph.
References
[1] Sulaiman A Alghunaim and Kun Yuan. A unified and retined convergence analysis for non-convex decentralized learning, arXiv preprint 1 2021.
[2] Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. Qsgd: Communication- efficient sgd via gradient quantization and encoding. In Advances in Neural Information Processing Systems, pages - 1720, 2017.
10

---

[3] Mahmoud Assran, Nicolas Loizou. Nicolas Ballas, and Mike Rabbat. Stochastic gradient push for distributed deep learning. In International Conference on Machine Learning (ICML), pages 344-353. 2019.
[4] Aditya Balu, Zhanhong Jiang, Sin Yong Tan, Chinmay Hedge, Young M Lee, and Soumik Sarkar. De- centralized deep learning using connentum-acceleraan consensus. arXiv preprint arXiv:2010.1116:
2020.
[5] Tal Ben-Nun and Torsten Hoefler. Demystifying parallel and distributed deep learning: An in-depth concurrency analysis. ACM Computing Surveys (CSUR), 52(44:1-43, 2019.
[6] Itai Benjamini, Gady Kozma, and Nicholas Wormald. The mixing time of the giant component of random graph. Random Structures & Algorithms, 45(3):8334077, 2014.
[7] Albert S Berahas, Raghu Bollapragada, Nitish Shirish Keskar, and Ermin Wei. Balancing communication and computation in distributed optimization. IEEE Transactions on Automatic Control, 6415):3141331555 2018.
[8] Jeremy Bernstein, Jiawei Zhao, Kamyar Azizzadenesheli, and Anima Anandkumar. signsgd with majority vote is communication efficient and fault tolerant. arXiv preprint
2018.
[9] Andrew Beveridge and Jeanmarie Youngblood. The best mixing time for random walks on trees. Graphs and Combinatorics, 32(6): 2016.
[10] Stephen P Boyd, Arpita Ghosh, Balaji Prabhakar, and Devavrat Shah. Mixing times for random walks on geometric random graphs In ALENEX/ANALCO, pages 240-249, 2005.
[11] Jianshu Chen and Ali H Sayed. Diffusion adaptation strategies for distributed optimization and learning over networks. IEEE Transactions on Signal Processing, 60(8):4289 43004454,,,,, 2012.
[12] Kai Chen, Jiaqi Wang. Jiangmiao Pang. Yuhang Cao, Yu Xiong, Xiaoxiao Li, Shuyang Sun, Wansen Feng. Ziwei Liu, Jiarui Xu, et al. Mmdetection: Open mmlab detection toolbox and benchmark. arXiv preprint
arXiv:1906.00 0ww.:9900.0715... 2019.
[13] Tianyi Chen, Georgios Giannakis, Tao Sun, and Wotao Yin. LAG: Lazily aggregated gradient for communication-efficin
distributed learning. In Advances in Neural Information Processing Systems, pages 5060- 2018
[14] Yiming Chen, Kun Yuan, Yingya Zhang, Pan Pan, Yinghui Xu, and Wotao Yin. Accelerating gossip SGD with periodic global averaging. In International Conference Machine Learning, 2021.
[15] Yat-Tin Chow, Wei Shi, Tianyu Wu, and Wotao Yin. Expander graph and catuuuniiaatio-fffiiiieooo decentralized optimization. In 2016 50th Asilomar Conference on Signals, Systems and Computers, pages
1715-1720. IEEE, 2016.
[16] Jia Deng. Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 248-255. leee, 2009.
[17] P. Di Lorenzo and G. Scutari. Next: In-network nonconvex optimization. IEEE Transactions on Signal and Information Processing over Networks, 2(2):120-136, 2016.
[18] John C Duchi, Alekh Agarwal, and Martin J Wainwright. Dual averaging for distributed optimization: Convergence analysis and network scaling. IEEE Transactions on Automatic control, 57(3):92 6066 2011. [19] Mark Everingham. Luc Van Gool, Christopher KI Williams, John Winn, and Andrew Zisserman. The pascal visual object classes (voc) challenge. International journal of computer vision. 88(2)3003-338 2010.
[20] Hongchang Gao and Heng Huang. Periodic stochastic gradient descent with momentum for decentralized training. arXiv preprint 2iv: 10435, 2020.
[21] Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, Andrew Tulloch, Yangqing Jia, and Kaiming He. Accurate, large minihatch sgd: Training imagenet I hour, arXiv
preprint Xiv: 706.006777.. 2017.
[22] Kaiming He, Xiangyu Zhang. Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 770-778, 2016.
[23] Kun Huang and Shi Pu. Improving the transient times for distributed stochastic gradient methods. arXiv preprint arXiv:2 10122105004444 10.00451, 2021.
[24] Anastasia Koloskova, Tao Lin, Sebastian Stich, and Martin Jaggi. Decentralized deep learning with arbitrary communication compression. In International Conference on Learning Representations, 2019.
[25] Anastasia Koloskova, Nicolas Loizou. Sadra Boreiri, Martin Jaggi, and Sebastian U Stich. A unified theory of decentralized sgd with changing topology and local updates. In International Conference on Machine Learning (ICML). pages 1-12. 2020.
[26] Anastasia Koloskova, Sebastian Stich, and Martin Jaggi. Decentralized stochastic optimization and gossip algorithms with compressed communication. In International Conference on Machine Learning, pages 3478-3487, 2019.
[27] Lingjing Kong. Tao Lin, Anastasia Koloskova, Martin Jaggi, and Sebastian U Stich. Consensus control for decentralized deep learning. In International Conference on Machine Learning, 2021.
11

---

[28] Mu Li. David G Andersen, Jun Woo Park, Alexander Smola, Amr Ahmed, Vanja Josifovski. James Long, Eugene J Shekita, and Bor- Yiin Su. Scaling distributed machine learning with the parameter server. In 1 1ith { {USENIX) Symposium on Operating Systems Design and Implementation ((OSDI) 14), pages
583-598, 2014,
[29] Z. Li, W. Shi, and M. Yan. A decentralized proximal-gradient method with network independent step-sizes and separated convergence rates. IEEE Transactions on Signal Processing, July 2019, early acces. Also available on (.XXx:1704.078550
[30] Xiangru Lian, Ce Zhang. Huan Zhang, Cho-Jui Hsich, Wei Zhang, and Ji Liu. Can decentralized algorithms outperform centralized algorithms? case study for decentralized parallel stochastic gradient descent. In Advances in Neural Information Processing Systems, pages 5330-5340, 2017.
[31] Xiangru Lian, Wei Zhang, Ce Zhang, and Ji Liu. Asynchronous decentralized parallel stochastic gradient descent. In International Conference on Machine Learning, pages 3043-3052, 2018.
[32] Tao Lin, Sai Praneeth Karimireddy, Sebastian U Stich, and Martin Jaggi. Quasi-global momentum: Accelerating decentralized deep learning on heterogeneous data. In International Conference on Machine
Learning. 2021.
[33] Tsung- Yi Lin, Piotr Dollár, Ross Girshick, Kaiming He, Bharath Hariharan, and Serge Belongic. Feature pyramid networks for object detection. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 21 17-21255, 2017.
[34] Tsung-Y Yi Lin, Priya Goyal, Ross Girshick, Kaiming He, and Piotr Dollár. Focal loss for dense object detection, In Proceedings of the IEEE international conference on computer vision, pages 2980-2988,
2017.
[35] Tsung-Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C Lawrence Zitnick. Microsoft coco: Common objects in context. In European conference on computer vision, pages 740-755. Springer, 2014.
[36] Xiaorui Liu, Yao Li, Rongrong Wang, Jiliang Tang, and Ming Yan. Linear convergent decentralized
optimization with compression. arXiv preprint arXiv:2007.0022 2020.
[37] Yanli Liu, Yuejiao Sun, and Wotao Yin. Decentralized learning with lazy and approximate dual gradients.
IEEE Transactions on Signal Processing, 69:1362 1377, 2021.
[38] Yaohua Liu, Wei Xu, Gang Wu, Zhi Tian, and Qing Ling. Communication-consone admm for decentralized consensus optimization. IEEE Transactions on Signal Processing, 67(10))2565-257) 2019.
[39] Nicolas Loizou and Peter Richtárik. Momentum and stochastic momentum for stochastic gradient, newton, proximal point and subspace descent methods. Computational Optimization and Applications, 77(3)653- 710, 2020.
[40] Songtao Lu and Chai Wah Wu. Decentralized stochastic non-convex optimization over weakly connected time-varying digraphs. In ICASSP 2020-2021 2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 5770-5774, IEEE, 2020.
[41] Asaf Nachmias and Yuval Peres. Critical random graphs: diameter and mixing time. The Annals of Probability, 36(4):126) (664):22671126, 2008.
[42] Angelia Nedić and Alex Olshevsky. Distributed optimization over time-varying directed graphs. IEEE Transactions on Automatic Control, 60(3):601-6155 2014.
[43] Angelia Nedić, Alex Olshevsky, and Michael G Rabbat. Network topology and communication- computation tradeoffss in decentralized optimization. Proceedings of the IEEE, 106(5):953-976, 2018.
[44] A. Nedic, A. Olshevsky, and W. Shi, Achieving geometric convergence for distributed optimization over time-varying graphs. SIAM Journal on Optimization, 27(4):2597-2333, 2017.
[45] Angelia Nedic and Asuman Ozdaglar. Distributed subgradient methods for multi-agent optimization. IEEE Transactions on Automatic Control, 54(1):48-61, 2009.
[46] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. Advances in Neural Information Processing Systems (NeurlPS), pages 8024-8035. 2019.
[47] Pitch Patarasuk and Xin Yuan. Bandwidth optimal all-reduce algorithms for clusters of workstations. Journal of Parallel and Distributed Computing, (9(2):117-12) 2009.
[48] Shi Pu, Alex Olshevsky, and Toannis Ch Paschalidis. A sharp estimate on the transient time of distributed stochastic gradient descent. arXiv preprint arvi:: / 1906. 02702, 2019.
[49] Shaoqing Ren, Kaiming He, Ross Girshick, and Jian Sun. Faster r-cnn: towards real-time object detection with region proposal networks. IEEF transactions on pottern analysis and machine intelligence, (9(6):1133) 137-
144,, 2016.
[50] Mark Sandler. Andrew Howard, Menglong Zhu, Andrey Zhmoginov, and Liang- Chieh Chen. Mobilenetv2: Inverted residuals and linear bottlenecks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 4520- 2018
[51] Ali Sayed. Adaptive networks. Proceedings of the IEEE, 102(4):460-49) 291,
[52] Gesualdo Scutari and Ying Sun. Distributed nonconvex constrained optimization over time-varying digraphs. Mathematical Programming, 176(1):497-5 544, 2019.
12

---

[53]
E. Seneta. Non-negative matrices and markov chains (2nd ed.). 1981.
[54]
Guodong Shi, Bo Li, Mikael Johansson, and Karl Henrik Johansson. Finite-time convergent gossiping. IEEE/ACM Trunsactions on Networking, 24(5):2782-2794, 2015.
[55] Schastian Urban Stich. Local sgd converges fast and communicates little. In International Conference on Learning Reprexentations (ICLR), 2019.
[56] Mingxing Tan and Quoc I.c. Efficientnet: Rethinking model scaling for convolutional neural networks. In International Conference on Machine Learning, pages 6105-6114, 14. PMI.R, 2019.
[57] Hanlin Tang, Xiangru Lian, Ming Yan, Ce 7hang, and Ji Liu. df: Decentralized training over decentralized data. In International Conference on Machine Learning, pages 4848-4856, 2018.
[58] Hanlin Tang. Chen Yu, Xiangru Lian, Tong Zhang,
Liu. Doublesquezze: Parallel stochastic gradient
descent with double-pass error-compensated compression. In International Conference on Machine Learning, pages 0155-61655 PMLR. 2019.
[59] Luca Trevisan. Lecture notes on graph partitioning, expanders and spectral methods. University of Califormia, Berkeley, https://people. eecs. berkeley. edu/ lucdbhoks/expamders22222
pdf. 2017.
[60] Jianyu Wang. Anit Kumar Sahu, Zhouyi Yang. Gauri Joshi, and Soummya Kar. MATCHA: Speeding up decentralized SGD via matching decomposition sampling. arXiv preprint arXiv: (905: 190500550 2019.
[61] Jianyu Wang, Vinayak Tantia, Nicolas Ballas, and Michael Rabbat. Slowmo: Improving communication- efficient distributed sgd with slow momentum. In International Conference on Learning Representations, 2019.
[62] Ran Xin, Usman A Khan, and Soummya Kar. An improved convergence analysis for decentralized online stochastic non-convex optimization. arXiv preprint 2008. /955, 2020.
[63] Bicheng Ying, Kun Yuan, Hanbin Hu, Yiming Chen, and Wotao Yin. Bluefog: Make decentralized
algorithms practical for optimization and deep learning, arXiv preprint a 11.04877 2021.
[64]
Hao Yu, Rong Jin, and Sen Yang. the linear speedup analysis communication efficient momentum sgd for distributed non-convex optimization. In International Conference on Machine Learning, pages
7184-7193. PMLR, 2019.
[65] Kun Yuan and Sulaiman A Alghunaim. Removing data heterogeneity influence enhances network topology
dependence of decentralized sgd. arXiv preprint arXiv:21055. 005.08023, 2021.
[66] Kun Yuan, Sulaiman A Alghunaim, Bicheng Ying, and Ali H Sayed. On the influence of bias-correction
on distributed stochastic optimization. IEEE Transactions on Signal Processing, 2020.
[67] Kun Yuan, Yiming Chen, Xinmeng Huang, Yingya Zhang, Pan Pan, Yinghui Xu, and Wotao Yin. Decent- LaM: Decentralized momentum SGD for large-batch deep training. arXiv preprint arXiv:2 11981, 2021.
[68] K. Yuan, B. Ying, X. Zhao, and A. H. Sayed. Exact dffusion for distributed optimization and learning Part I: Algorithm development. JEEE Transactions on Signal Processing, 67(3):708 723, 2019.
[69] Jiaqi Zhang and Keyou You. Decentralized stochastic gradient tracking for non-convex empirical risk minimization. arXiv preprint arXiv: 1909.0299 2019.
13


Reviews:
[{"review_id": "_1WGzh6WYuA", "reviewer": "Reviewer_nimy", "summary": "This paper studies static exponential and one-peer exponential graphs for Decentralized momentum SGD.  The results show that these two exponential graphs have a better balance between per-iteration communication and iteration complexity compared to the existing communication topology. Especially, they show that one-peer exponential graphs converge as fast as static exponential graphs but require less per-iteration communication. In the end, this paper provides adequate empirical evaluations of the exponential graphs in decentralized (momentum) SGD training.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper is overall technically sound and well written. The advantage of the exponential graphs claimed in this paper are well supported by theoretical analysis. The experimental results show that the one-peer exponential graph for DmSGD is very promising. I think the framework is potentially useful for deep learning training.\n\nComments and questions:\n1.\tHow would these exponential graphs work for decentralized SGD? Is momentum necessary in this decentralized setting?\n2.\thow does the convergence bound in Corollary 1 compare with existing bounds\n3.\tLine 253, ‘Comparing (11) with (1)’, should it be (10) instead of (1)?\n4.\tCould the author comment on why the baseline Bi-RandMatch is competitive compare to the one-peer exponential graph?\n\n\n---------\nAfter reading the authors‘ response, most of my concerns have been addressed. I would like to increase my score to 7.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This paper does not focus on the potential impact. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "SIzKQaZgYoI", "reviewer": "Reviewer_MdPU", "summary": "This paper studies the exponential graph used for decentralized training in theory, and shows it effectively reduces the convergence bound and speeds up the deep learning tasks. A novel analysis for the spectral gap bound on exponential graph is given, which is tighter than the one shown in previous papers. Various experiments on large-scale vision tasks are conducted, the results seem to be aligned with the theory.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper addresses an important topic in decentralized training: how do we construct a communication graph to further improve communication complexity? The main contribution is the derivation and empirical verification on the spectral gap bound of exponential graph, which is novel. \n\nMy main concern is in the baseline comparison. As we know, decentralized training utilizes the gossip algorithm, which is a well-studied topic in the literature especially in wireless network and control theory. Having said this, the main content in this paper is invariant to deep learning, but rather a discussion on the mixing time of the gossip matrix in terms of different graphs. Table 1 (and some in the appendix) in this paper lists some of the graph, but does not include many related algorithms and analysis. For example, [1][2][3][4]; also some optimality analysis is given in [5]. The authors should consider having a detailed discussion on how exponential graph compares to these algorithms and why it should be preferred over them.\n\nIn my experience, usually when we scale up the experiments to hundreds of GPUs, the speedup will become sublinear in terms of number of GPUs since communication gradually becomes the bottleneck. However, in Table 2 we observe nearly perfect linear speed up. This seems interesting and I wonder if the authors have any insights on this.\n\nSome minor comments:\n\n(1) In the complexity expression, constants should be written as $\\Omega(1)$ in Table 2.\n\n(2) In the experiments, std over the accuracy should be provided.\n\n\n== Reference\n\n[1] CRITICAL RANDOM GRAPHS: DIAMETER AND MIXING TIME\nhttps://arxiv.org/pdf/math/0701316.pdf\n\n[2] The mixing time of the giant component of a random graph\nhttps://arxiv.org/pdf/math/0610459.pdf\n\n[3] The best mixing time for random walks on trees\nhttps://arxiv.org/pdf/1410.5112.pdf\n\n[4] Mixing Times for Random Walks on Geometric Random Graphs\nhttps://archive.siam.org/meetings/analco05/papers/07SBoyd2.pdf\n\n[5] Fastest Mixing Markov Chain on a Graph\nhttps://web.stanford.edu/~boyd/papers/pdf/fmmc.pdf", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This paper does not reflect any potential negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "HoPzX4gpJfr", "reviewer": "Reviewer_13Gd", "summary": "The work proposes efficient communication topologies for Decentralized momentum Stochastic Gradient Descent (DmSGD)  algorithms used for training deep learning models. In particular, they focus on exponential graphs, where each nodes is connected to O(log(n)) other nodes. They analyze the spectral gap, which shows the graph connectivity, for exponential graphs and establish a logarithmic bound on it and claim that it was reported incorrectly in the literature to be constant.  Moreover, they propose to communicate over one-peer exponential graphs, in which each node communicates to a single neighbor. They theoretically show that a sequence of O(log(n))  one-peer exponential graphs achieve the same convergence rates, despite being far more efficient in terms of communication. They further confirm the effectiveness of their proposed method by running experiments on real datasets and applications and comparing them to other topologies and methods. ", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper provides efficient communication topologies for running Decentralized  momentum Stochastic Gradient Descent (DmSGD) algorithms. In these algorithms the data is distributed over some nodes, the nodes compute gradients in parallel and the gradients are averaged based on the underlying topology. In particular, they focus on exponential graphs and a one-peer variant. The main motivation for considering such topologies is that they are sparse and lead to efficient communication. They further theoretically show that the sparsity in communication does not hurt the convergence rate. Finally, they show the effectiveness of their proposed method by running experiments on real datasets and real applications and comparing them to other topologies and methods. The paper is well-presented and well-organized and provide generic methods that are highly interesting for the machine learning community. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The work presents strong theoretical and empirical results. Here are few minor issues, I don't believe these should be ground for rejection. \n\n(a) It would be helpful if running times were also reported in Table 3 to understand how using these topologies speed up the running time (if that is the case at all). Also, it would be helpful to see Fig. 3 with respect to time, as well.\n\n(b) The reported metrics are quite close to each other for different methods and topologies. However, the results for the one-peer exponential graphs is generally better. \n\n(c) The functions f_i are defined inside Eq. (1), which is a bit confusing. It would read nicer, if the authors defined the functions f_i below Eq. (1).\n\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper deals with fully decentralized learning with SGD and shows that network topologies in the form of exponential graphs provide fast convergence and accurate models.

The reviews were quite positive and the author response helped to consolidate the scores. Overall, the theoretical and empirical results were found to be strong and relevant for practitioners in a increasingly popular topic. Therefore, the paper is accepted.
Decision: Accept (Poster)