Beyond spectral gap: the role of the topology in decentralized learning
Authors: Thijs Vogels
Hadrien Hendrikx
Martin Jaggi
Venue: NeurIPS 2022 Accept (2022)
Keywords: decentralized optimization
distributed training
convex optimization
stochastic optimization
learning rate
spectral gap

Abstract: In data-parallel optimization of machine learning models, workers collaborate to improve their estimates of the model: more accurate gradients allow them to use larger learning rates and optimize faster. We consider the setting in which all workers sample from the same dataset, and communicate over a sparse graph (decentralized). In this setting, current theory fails to capture important aspects of real-world behavior. First, the ‘spectral gap’ of the communication graph is not predictive of its empirical performance in (deep) learning. Second, current theory does not explain that collaboration enables larger learning rates than training alone. In fact, it prescribes smaller learning rates, which further decrease as graphs become larger, failing to explain convergence in infinite graphs. This paper aims to paint an accurate picture of sparsely-connected distributed optimization when workers share the same data distribution. We quantify how the graph topology influences convergence in a quadratic toy problem and provide theoretical results for general smooth and (strongly) convex objectives. Our theory matches empirical observations in deep learning, and accurately describes the relative merits of different graph topologies.

Beyond spectral gap: The role of the topology in decentralized learning
Thijs Vogels" EPFL
Hadrien Hendrikx" EPFL
Martin Jaggi EPFL
Abstract
In Mata-parallel optimization of machine learning models, workers collaborate to improve their estimates of the model: more accurate gradients allow them use larger learning rates and optimize faster. We consider the setting in which all workers sample from the same dataset, and communicate over a sparse graph (decentralized). In this setting, current theory fails to capture important aspects of real-world behavior. First, the 'spectral gap" of the communication graph not pre- dictive of its empirical performance in (deep) learning. Second, current theory does not explain that collaboration enables larger learning rates than training alone. fact, it prescribes smaller learning rates, which further decrease graphs become larger, failing to explain convergence in infinite graphs. This paper aims to paint an accurate picture of sparsely-comnected distributed optimization when workers share the same data distribution. We quantify how the graph topology influences conver- gence in quadratic toy problem and provide theoretical results for general smooth and (strongly) convex objectives. Our theory matches empirical observations deep learning, and accurately describes the relative merits of different graph topolo- gies. Code: gi thub. com/ http/pffll//etee topoloyy htapi///toooloo---deeeeeeeeee in-decentral ized- leizzeddeeaainng
Introduction
Distributed data-pa aata-parallel optimization algorithms help tackle the increasing complexity of machine learning models and of the data on which they are trained. We can classify those training algorithms as either centralized decentralized, and we often consider those settings have different benefits over training 'alone'. the centralized setting, workers compute gradients on independent mini-batches of data, and they average those gradients between all workers. The resulting lower variance in the updates enables larger learning rates and faster training. In the decentralized setting, workers average their models with only a sparse set of 'neighbors' in graph instead of all-to-all, and they may have private datasets sampled from different distributions. As the benefit of decentralized learning, we usually focus only on the (indirect) access other worker's datasets, and not of faster training.
While decentralized learning is typically studied with heterogeneous datasets across workers, sparse (decentralized) averaging between is also useful when worker's data is identically distributed (i.i.d.) [15]. As an example, sparse averaging is used data centers to mitigate communication bottle- necks [1]. In fact the D-SGD algorithm [11], which focus in this work, performs well mainly in this setting, while algorithmic modifications [14, 1, 22) are required to yield good performance on heterogeneous objectives. When the data is i.i.d., the goal of sparse averaging is optimize faster, just like in centralized (all-to-all) graphs.
Yet, current decentralized learning theory poorly explains the i.i.d. case. Analyses typically show that, for small enough learning rates, training with sparse averaging behaves the same as with all-to-all averaging [11, 8]. Compared to training alone with the same small learning rate, all-to-all averaging
"Equal contribution. Corresponding authors thijs. wwgelseepll...commoooooo ch and hadrien. hendr i 1xxeppl. ch.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Steps until loss 0.01
Alone (disconnected)
Hing (spectral gap 1)
1000
Ring
2-ing (spectral gap
4 4-ing (spectral gap 0.67)
8-ring (s.g. 0.20)
Current theory uses lower learning rates
Fully connected
oc-fing (a.g
100
but decentralized averaging ertablles higher learning rates
Insteac of speecup,
current theory predicts a slowdown with ring size
10
0.001
000
Harning rate
leamnngg rate
Figure 1: "Time to target' for D-SGD [11] with constant learning rates on an i.i.d. isotropic quadratic dataset (Section 3). The noise disappears the optimum. Compared to optimizing alone, 32 workers in ring (left) are faster for any learning rate, but the largest improvement comes from being able to use large learning rate. This benefit is not captured by current theory, which prescribes smaller learning rate than training alone. On the right, we see that rings of increasing size enable larger learning rates and faster optimization. Because a ring's 's spectral gap goes to zero with the size, this cannot be explained by current theory.
reduces the gradient variance by the number of workers. In practice, however, such small learning rates would never be used. In fact, a reduction in variance should allow us to use a larger learning rate than training alone, rather than imposing a smaller one. Contrary to current theory, we show that averaging reduces the variance from the start, instead of just asymptotically. Lower variance increases the maximum learning rate, which directly speeds up convergence. We characterize how much averaging with various communication graphs reduces the variance, and show that centralized performance is not always achieved when using optimal large learning rates. The behavior we explain is illustrated in Figure 1.
In current convergence rates, the graph topology appears through the spectral gap of its averaging (gossip) matrix. The spectral gap poses conservative lower bound on how much one averaging step brings all worker's models closer together. The larger, the better. If the spectral gap is small, significantly smaller learning rate is required to make the algorithm behave close to SGD with all-to-all averaging with the same learning rate. Unfortunately, we experimentally observe that, both in deep learning and in convex optimization, the spectral gap of the communication graph is not predictive of its performance under realistically tuned learning rates.
The problem with the spectral gap quantity is clearly illustrated in a simple example. Let the communication graph be a ring of varying size. As the size of the ring increases infinity, its spectral gap goes to zero, since it becomes harder and harder to achieve consensus between all the workers. This leads to the optimization progress predicted by current theory to go to zero as well. Yet, this behavior does not match the empirical behavior of the rings with i.i.d. data. As the size of the ring increases, the convergence rate actually improves (Figure 1), until it saturates at point that depends on the problem.
In this work, aim to accurately describe the behavior of i.i.d. distributed learning algorithms with sparse averaging, both in theory and in practice. We quantify the role of the graph in a quadratic toy problem designed to mimic the initial phase of deep learning (Section 3), showing that averaging notion of
enables a larger learning rate. From these insights, we derive a problem-independee "effective number of neighbors' in a graph that is consistent with time-varying topologies and infinite graphs, and is predictive of a graph's empirical performance in both convex and deep learning. We provide convergence proofs for convex and (strongly) convex objectives that only mildly depend on the spectral gap of the graph (Section 4), and consider the whole spectrum instead. At its core, our analysis does not enforce global consensus, but only between workers that are close to each other in the graph. Our theory shows that sparse averaging provably enables larger learning rates and thus speeds up optimization. These insights prove to be relevant in deep learning, where we accurately describe the performance of a variety of topologies, while their spectral gap does not (Section 5).

---

2 Related work
Decentralized SGD This paper studies decentralized SGD. Koloskova et al. [8] obtain the tightest bounds for this algorithm in the general setting where workers optimize heterogeneous objectives. Contrary to their work, we focus primarily on the case where all workers sample i.i.d. data from the same distribution. This important case is not described in a meaningful way by their analysis: while they show that gossip averaging reduces the asymptotic variance suffered by the algorithm, the fast initial linear decrease term in their convergence rate depends on the spectral gap of the gossip matrix. This key term does not improve through collaboration and gives rise to smaller learning rate than training alone. Besides, as discussed above. this implies that optimization is not possible in the limit of large graphs, even in the absence of heterogeneity: for instance, the spectral gap of an infinite ring is zero, which would lead to a learning rate of zero as well.
These rates suggest that decentralized averaging speeds up the last part of training (dominated by variance), at the cost of slowing down the initial (linear convergence) phase. Beyond the work of Koloskova et al. [8], many papers focus on linear speedup (in the variance phase) over optimizing alone, and prove similar results in a variety of settings [11, 20, 12]. All these results rely on the following insight: while linear speedup is only achieved for small learning rates, SGD eventually requires such small learning rates anyway (because of, e.g., variance, or non-smoothness). This observation leads these works to argue that "topology does not matter". This is the case indeed, but only for very small learning rates, as shown in Figure 1. In practice, averaging speeds up both the initial and last part of training. This is what we show in this work, both in theory and in practice.
Another line of work studies D-(S)GD under statistical assumptions on the local data. particular, Richards and Rebeschini [18) show favorable properties for D-SGD with graph-dependent implicit regularization and attain optimal statistical rates. Their suggested learning rate does depend on the spectral gap of the communication network, and goes to zero when the spectral gap shrinks. Richards and Rebeschini [17] also show that larger (constant) learning rates can be used in decentralized GD, but their analysis focuses on decentralized kernel regression. It does not cover stochastic gradients, and relies on statistical concentration of local objectives rather than analysis on local neighborhoods.
Gossiping in infinite graphs An important feature of our results is that they only mildly depend on the spectral gap, and so they apply independently of the size of the graph. Berthier et al. [3] study acceleration of gossip averaging in infinite graphs, and obtain the same conclusions as we do: although spectral gap is useful for asymptotics, it fails to accurately describe the transient regime of averaging. This is especially limiting for optimization (compared to of just averaging). as new local updates need to be averaged every step. The transient regime of averaging deeply matters. Indeed, it impacts the quality of the gradient updates, and so it rules the asymptotic regime of optimization.
The impact of the topology Some works on linear speedup [1 I] argue that the topology of the graph does not matter. This is only true for asymptotic rates in specific settings, as illustrated in Figure 1. Neglia et al. [16] investigate the impact of the topology on decentralized optimization, and contradict this claim. Compared to us. they make different noise assumptions, which in particular depend on the spectral distribution of the noise over the eigenvalues of the Laplacian (thus mixing computation and communication aspects). Although they show that the topology has an impact the early phases of training (just like we do), they still get an unavoidable dependence on the spectral gap of the graph. Our results are different in nature, and show the benefits of averaging and the impact of the topology through the choice of large learning rates.
Another line of work studies the interaction of topology with particular patterns of data heterogene- ity [4, 2]. and how to optimize graphs with this heterogeneity in mind. These works "only" show a benefit from one-step gossip averaging and this is thus what they optimize the graph for. In contrast, we show that it is possible to benefit from distant workers beyond direct neighbors, too. This is an orthogonal direction, though the insights from our work could be used to strengthen their results.
Time-varying topologies Time-varying topologies are popular for decentralized deep learning in data centers due to their strong mixing [1, 23). The benefit of varying the communication topology over time is not easily explained through standard theory, but requires dedicated analysis [25]. While our proofs only cover static topologies, the quantities that appear in our analysis can be computed for time-varying schemes, too. With these quantities, we can empirically study static and time-varying schemes in the same framework.
3

---

3 A toy problem: D-SGD on isotropic random quadraties
Before analyzing decentralized stochastic optimization through theory for general convex objectives and deep learning experiments, we first investigate a simple toy example that illustrates the behavior we want explain the analysis. In this setting, we can exactly characterize the convergence of decentralized SGD. We also introduce concepts that will be used throughout the paper.
We consider workers that jointly optimize an isotropic quadratic (d-1v((0.)) {ddxx)²= |x| with a unique global minimum x" = 0. The workers access the quadratic through stochastic gradients of the form g(x) dd x, with d ~ (0, 1). This corresponds to linear model with infinite data, and where the model can fit the data perfectly, so that stochastic noise goes to zero close to the optimum. We empirically find that this simple model a meaningful proxy for the initial phase of (over-po parameterized) deep learning (Section 5). A benefit of this model is that we can compute exact rates for it. These rates illustrate the behavior that we capture more generally in the theory of Section 4. Appendix C contains a detailed version of this section that includes full derivations.
The stochasticity in this toy problem be quantified by the noise level
Ea Ralldd x
Ç - sup
|x|
XE
which is equal to Ç = d 2, due the random normal distribution of d.
The workers run the D-SGD algorithm [11]. Each worker has its own copy x; E Rd of the model, and they alternate between local model updates x; X; ng(x.) and averaging their models with others: x; f Dj=1 WiyXj. The averaging weights wij are summarized the gossip matrix W E R=xa A non-zero weight wij indicates that i and j are directly connected. In the following, we assume that W symmetric and doubly stochastic: Σÿ=1 Wij Vi.
On our objective, D-SGD either converges or diverges linearly. Whenever it converges, i.e. when the learning rate small enough, there a convergence rate r such that
E 11 s (1 r)]lx((-1)
with equality as + oo (proofs in Appendix C). When the workers train alone (W = D), the convergence rate for given learning rate 77 reads:
Falone
1- - (1 - n)) (C - 1)m².
(2)
The optimal learning rate 1/" = 1 balances the optimization term (1 - w) and the stochastic term (C- - 1)m² In the centralized (fully connected) setting (Wi, = 1 Vi, the rate is simple as well:
(1 1) (C 1)m²
Feemtralized
Averaging between n workers reduces the impact of the gradient noise, and the optimal learning rate grows to 17" n D-SGD with general gossip matrix W interpolates those results.
To quantify the reduction of the (c- 1)n? term in general, we introduce the notion of effective number of neighbors nw (r)) of the gossip matrix W and decay parameter T
Variy.
Definition A. The effective number of neighbors (w( = lim D Varlz
measures the
ratio of the asymptotic variance of the processes
y((+1) = / y(()) + g(t), where (1)) E R and {(9) (1 (0,1)
(4)
and
(+1) = -WW)= (() (()), where (0)) E R and ( ~ ~m 1).
(5)
We call y and random walks because workers repeatedly add noise to their state, somewhat like SGD's s parameter updates. This should not be confused with a 'random walk' over nodes in the graph.
Since averaging with W decreases the variance of the random walk by at most the effective number of neighbors a number between and n. The decay 7 modulates the sensitivity to communication delays. If 0, workers only benefit from averaging with their direct neighbors. As y increases,

---

Effective number of neighbors [variance reduction in 'randmm walk)
Fully connected
24
10 oliques
lime-varying exponential
Ring
Alone (disconnected)
Decay of the "random walk
(1hink "lower learning rate' "derates moving slower')
The effective number of neighbors for several topologies (Appendix B) measured by their variance reduction in Equation 5. The point 7 on the r-axis that matters depends on the learning rate and the task. Which topology is 'best' varies from problem problem. For large decay rates ? (corresponding small learning rates), all connected topologies achieve variance reduction close to a fully connected graph. For small decay rates (large learning rates), workers only benefit from their direct neighbors (e.g. 3 in ring). These curves can be computed explicitly for constant topologies, and simulated efficiently for the time-varying exponential scheme [1].
Figure 2:
multi-hop connections play an increasingly important role. As y approaches 1, delayed and undelayed noise contributions become equally weighted, and the reduction tends for any connected topology.
For regular doubly-stochastic symmetric gossip matrices W with eigenvalues . An. TW (7)
has closed-form expression
now (7)
(6)
A2 1E
The notion of variance reduction in random walks, however, naturally extends to infinite topologies or time-varying averaging schemes as well. Figure 2 illustrates nww for various topologies.
In our exact characterization of the convergence of D-SGD on the isotropic quadratic toy problem (Appendix C), find that the effective number of neighbors appears in place of the number of workers n in the fully-comnected rate of Equation 3. The rate is the unique solution to
(S 1)m²
(1 11)²
70W (1-1)
For fully-connected and disconnected W. nw (7) Equation recovers Equations and 3. For other graphs, the effective number of workers depends on the learning rate. Current theory only considers the case where nw n, but the small learning rates this requires can make the term (1 172 too large, defeating the purpose of collaboration.
or respectively, irrespective of y, and
Beyond this toy problem, we find that the proposed notion of effective number of neighbors is also meaningful in the analysis of general objectives (Section 4) and in deep learning (Section 5).
Theoretical analysis
In the previous section, we have derived exact rates for specific function. Now present convergence rates for general (strongly) convex functions that are consistent with our observations in the previous section. We obtain rates that depend the level of noise, the hardness of the objective, and the topology of the graph. We will assume the following randomized model for D-SGD:
V (x
(t)
with probability 2:
1
(8)
Σー= w
otherwise,
where fgge represent sampled data points and the gossip weights way are elements of W. This ran- domized model yields clean analysis, but similar results hold for standard D-SGD (Appendix D.4).
5

---

Assumption B. The stochastic gradients are such that: (1) 5 and 5,0) are independent for all I, E and i + j. (1I) 1E [f = for all i, (II) E || f (x*)] I a² for all t, i, where x* is minimizer of f. (IV) fge is convex and Ç-smooth for all t, d. (V) f is p-strongly-convex for 2 0 and L-smooth.
The smoothness Ç of the stochastic functions f& defines the level of noise in the problem (the lower, the better). The ratio </ compares the difficulty of optimizing with stochastic gradients to the difficulty with the true global gradient (before reaching the 'variance region' of distance ( the optimum). Assuming better smoothness for the global average objective than for the local functions key to showing the benefit of averaging between workers. Without communication, convergence to the variance region is ensured for learning rates !i S 1/5. If Ç ~ L, there is little noise and cooperation does not help before ||x(() - -x112 ~ o². Yet, in noisy regimes (C > L), such as in Section 3 in which Ç = d + 2 > = L, averaging enables larger step-sizes up to min(1 L, n/C). greatly speeding up the initial training phase. This is precisely what we prove in Theorem I.
If the workers always remain close (x; (x1 ... + X,) Vi, or equivalently ! x),
D-SGD behaves the same as SGD on the average parameter 1
n Ei=1 X,, and the learning rate depends x", however, we
on max(Ç/n, n, I.), showing a reduction of variance by n. To maintain " 11 require a small learning rate. This is common starting point for the analysis of D-SGD, in particular for the proofs in Koloskova et al. [8]. On the other extreme, if we do not assume closeness between workers, "Ix R x" always holds. In this case, there is no variance reduction, but no requirement for a small learning rate either. In Section 3, we found that, at the optimal learning rate, workers are not close to all other workers, but they are close to others that are not too far away in the graph.
We capture the concept of 'local closeness' by defining an averaging matrix M. It allows us to consider semi-local averaging beyond direct neighbors, but without fully averaging with the whole graph. We ensure that "Mx Rs x", leading to some improvement in the smoothness between Ç and C/n, interpolating between the two previous cases. Each matrix M implies a requirement on the learning rate, as well as an improvement in smoothness. Based on Section 3, we therefore focus on specific family of matrices that strike good balance between the two: We choose M as the covariance a decay-y 'random walk process' with the graph, meaning that
M = (1
Σ
W
(1 - 7) W (--
(9)
Varying 7 induces a spectrum of averaging neighborhoods from M = W (7 = 10 L11 (7 1). y also implies effective number of neighbors niw (7): the larger 7, the larger nw(())
Theorem I provides convergence rates for any value of but the best rates are obtained for a specific ? that balances the benefit of averaging with the constraint it imposes on closeness between neighbors. In the following theorem, we assume that M,; M for all j, so that M = nw( the effective number of neighbors defined in (6) is equal to the inverse of the self-weights of matrix M. Otherwise, all results hold by replacing nw (7) with min; M,;"
Theorem I. If Assumption B holds, and the learning rate satisfies
1
1- 72222
< min
(10)
8(C/nw (7) +) 2nw(1))
then the iterates obtained by (8) verify
(x() 112 + (7) |xx 1 S
1
m (1-%) Co + nw mw(?))
2nj²
(11)
The bound on the learning rate (10) represents the tension between (1) reducing the noise ( by averaging with more people (larger (7)). which is the first term in the minimum, and (II) staying close to all of them. A large spectral gap 1 A₂( (W) reduces the second constraint, but allow non-trivial learning rates 17 > 0 even when A₂ W) = 1 (infinite graphs) as long as Y < 1.
\2(W)
Theorem I gives rate for each parameter 7 that controls the local neighborhood size. The task that remains is to find the 7 parameter that gives the best convergence guarantees (the largest learning rate). As explained before, one should never reduce the learning rate in order to be close to others,

---

Learning rate given Theorem (Z = 1005 2000)
Hyperoube
Restricted by noise
Restricted py consensus
Torus (4x8)
0.002
0.004
Ring
0.001
0.002
0.000
0.000
15
20
25
30
10
15
20
25
Fffective number of neighbors (w(s)
Flfective number of neightbors wow
M
Figure 3: Maximum learning rates prescribed by Theorem I, varying the parameter y that implies an effective neighborhood size (I-axis and an averaging matrix M (drawn as heatmaps). On the left, show the details for a 32-worker ring topology, and the right, compare topologies. Increasing 7 (and with it niw (7)) initially leads to larger learning rates thanks to noise reduction. At the optimum, the cost of consensus exceeds the benefit of further reduced noise.
connected
because the goal of collaboration is to increase the learning rate. We should therefore pick such that the first term in Equation (10) dominates. This intuition is summarized in Corollary II, which compares the performance of D-SGD with centralized SGD with fewer workers.
Corollary II. D-SGD is as fast as centralized mini-batch SGD with ((1w(>)) workers, assuming 2nw(>)"
that Ç 2 nL, and that the parameter is the highest y such that I- (-T I 32 This corresponds to learning rate 1) nw (7)/16Ç.
The typical D-SGD learning rates [8] are of order than the learning rate of Corollary II when X2 (W) large the number of iterations large. We use the condition < 2 nL only to present results in simpler way. The condition 2nw(n) I-T only depends the size and topology of the graph, and can easily be computed in many cases. Thus, to obtain the best guarantees, we start from = 0 and then increase until either (7) z n, the total size of the graph, the two terms in the minimum match. This is how we obtain Figure 3.
which are much smaller
Proof sketch (Theorem I). The proof relies on simple argument: rather than bounding ||x(*) x11
or || 111"1 Tx(" (t) 1=2 we analyze ||x(*) x=1 I This term better captures the benefit of averaging than ||x(*) - x* 1|2, thus leading to better smoothness constants, as long as [Ix is not too large. This yields fast rates without the need to guarantee that iterates between very distant workers remain close, which would be prohibitively expensive.
Theorem I is a special case of more general theorem presented Appendix D. This version, among other things, covers different choices of parameters, unbalanced communication and computation probabilities (thus allowing for local steps), and the convex (μ4 0) case.
5 Experimental analysis
While in the previous sections we have discussed isotropic quadratics or convex and smooth functions, the initial motivation for this work comes from observations in deep learning. First, it is crucial in deep learning to use a large learning rate in the initial phase of training [10]. Contrary to what current theory prescribes, we do not use smaller learning rates in decentralized optimization than when training alone (even when data is heterogeneous.) And second, we find that the spectral gap of topology is not predictive of the performance of that topology in deep learning experiments.
In this section, we experiment with variety of 32-worker topologies on Cifar-10 [9] with a VGG-1 model [19]. Like other recent works [13, 22], opt for this older model, because it does not
7

---

Cifar 10 training loss after 2:5k steps (</25 epochs)
Solo
Star
1.5
Binary tree
Ring
Two cliques
Social network
Time-varying exponential
0.6
Torus (4x8)
Hypercube
Fully connected
0.001
0.01
0.1
Learning rate
Figure 4: Training loss reached after 2.5 SGD steps with variety of graph topologies. In all cases, averaging yields small increase in speed for small learning rates, but a large gain over training alone comes from being able to increase the learning rate. While the star has better spectral gap (0.031) than the ring (0.013), 3), it performs worse, and does not allow large learning rates. For reference, similar curves for fully fully-connected graphs of varying sizes are in Appendix
Two cliques
Torus (4x8)
Star
Social network
Ring
Hypercube
Binary tree
Gossip mairix
on Cifar-10
Covariance Massured random walk
(ww 0.948)
==(? 0.993)
0.986) 1w 0.982)
Pw 0.983)
nw(1 0.997)
mw 0.984)
= 17.8
29.4 = 5.1
27.3
13.9
= 31.3
12.3
Figure 5: Measured covariance in Cifar-10 10 (second row) between workers using various graphs (top row). After 10 epochs, store checkpoint of the model and train repeatedly for 100 SGD steps, yielding 100 models for workers. We show normalized covariance matrices between the workers. These very well approximated by the covariance in the random walk process of Section (third row). We print the fitted decay parameters and corresponding 'effective number of neighbors'.
include BatchNorm [6] which forms orthogonal challenge for decentralized SGD. Please refer to Appendix E for full details on the experimental setup. Our set topologies (Appendix B) includes regular graphs like rings and toruses, but also irregular graphs such as binary tree [22] and social network [5], and a time-varying exponential scheme [1]. We focus on the initial phase training, 25k steps in case, where both train and test loss converge close to linearly. Using large learning rate in this phase is found to be important for good generalization [10].
Figure shows the loss reached after the first 2.5k SGD steps for all topologies and for dense grid of learning rates. The curves have the same global structure as those for isotropic quadratics Figure (sparse) averaging yields a small increase in speed for small learning rates, but a large gain over training alone comes from being able to increase the learning rate. The best schemes support almost the same learning rate as 32 fully-connected workers, and get close in performance.

---

Cifar 10 training loss after 2:5k steps
(+25 epoons)
14
12
08
0.6
04
X
122
52
02
0.3
0.4
0.5
3.5
0.7
0.0
Effective num. neighbors (1 0.951, runec)
Spectral gap
Figure 6: Cifar- 10 training loss after 2.5k steps for all studied topologies with their optimal learning rates. Colors match Figure 4, and x indicates connecco graphs with varying number of workers. After fitting decay parameter = 0.951 that captures problem specifics, the effective number of neighbors (left) measured by variance reduction in random walk (like in Section 3) explains the relative performance of these graphs much better than the spectral gap of these topologies (right).
We also find that the random walks introduced in Section are good model for variance between workers in deep learning. Figure 5 shows the empirical covariance between the workers after 100 SGD steps. Just like for isotropic quadratics, the covariance accurately modeled by the covariance in the random walk process for certain decay rate 7
Finally, we observe that the effective number of neighbors computed by the variance reduction in random walk (Section 3) accurately describes the relative performance under tuned learning rates of graph topologies on our task, including for irregular and time-varying topologies. This is in contrast to the topology's 8 spectral gaps, which we find to be not predictive. We fit decay rate 7 0.951 that seems to capture the specifics of our problem, and show the correlation in Figure 6.
In Appendix F.1, we replicate the same experiments in different setting. There, we use larger graphs (of 64 workers), different model and data set MLP on Fashion MNIST [24]), and momentum or weight decay. The results in this setting are qualitatively comparable to the ones presented above.
6 Conclusion
We have shown that the sparse averaging in decentralized learning allows larger learning rates to be used, and that it speeds up training. With the optimal large learning rate, the workers' models are not guaranteed remain close to their global average. Enforcing global consensus is unnecessary in the i.i.d. setting and the small learning rates it would require are counter-productive. With the optimal learning rate, models do remain close some local average weighted neighborhood around them. The workers benefit from a number of 'effective neighhors', smaller than the whole graph, that allow them to use large learning rate while retaining sufficient consensus within the 'local neighborhood",
Based on our insights, we encourage practitioners of sparse distributed learning to look beyond the spectral gap of graph topologies. and to investigate the actual 'effective number of neighbors' that used. We also hope that our insights motivate theoreticians to be mindful of assumptions that artificially limit the learning rate.
We show experimentally that our conclusions hold in deep learning, but extending our theory to the non-convex setting an important open direction that could reveal interesting new phenomena. Furthermore, an extension our semi-local analysis to the heterogeneous setting where workers optimize different objectives could shed further light the practical performance of D-SGD.

---

Acknowledgments and Disclosure of Funding
This project was supported by SNSF grant 200020 2002002000442.
We thank Lie He for valuable conversations and for identifying the discrepancy between topology's spectral gap and its empirical performance. We also thank Raphaël Berthier, Aditya Vardhan Varre and Yatin Dandi for their feedback on the manuscript.
10

---

References
[1] Mahmoud Assran, Nicolas Loizou, Nicolas Ballas, and Michael G. Rabbat. Stochastic gradient push for distributed deep learning. In Proc. ICML, volume 97, pages 344-353, 2019.
[2] B. Le Bars, Aurélien Bellet, Marc Tommasi, and Anne-Marie Kermarrec. Yes, topology matters decentralized optimization: Refined convergence and topology learning under heterogeneous data. CoRR, abs/2204.04l 004452, 2022.
[3] Raphaël Berthier, Francis R. Bach, and Pierre Gaillard. Accelerated gossip in networks of given dimension using jacobi polynomial iterations. SIAM Math. Data Sci., 2(1):24 47, 2020.
[4] Yatin Dandi, Anastasia Koloskova, Martin Jaggi. and Sebastian U. Stich. Data-bettrogeneiity aware mixing for decentralized learning. CoRR, Abs/2204.064777, 2022.
[5] Allison Davis, Burleigh Bradford Gardner, and Mary R Gardner. Deep South: A social anthropological study of caste and class. Univ of South Carolina Press, 1930.
[6] Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In Proc. ICML, volume 37, pages 448-456, 2015.
[7] Sham Kakade, Shai Shalev-Shwartz, Ambuj Tewari, et al. On the duality of strong convexity and strong smoothness: Learning applications and matrix regularization. Unpublisked Manuscript, 2(1):35, 2009.
[8] 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 Proc. ICMI., volume 119, pages 5381-5393, 2020.
[9] Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. Cifar- 10 (Canadian Institute for Advanced Research).
[10] Yuanzhi Li, Colin Wei, and Tengyu Ma. Towards explaining the regularization effect of initial large learning rate in training neural networks. In NeurIPS, pages 11669-1 1680, 2019.
[11] Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsieh, Wei Zhang, and Ji Liu. Can decentralized algorithms outperform centralized algorithms? A case study for decentralized parallel stochastic gradient descent. In NeurIPS, pages 5330-5340, 2017.
[12] Xiangru Lian, Wei Zhang, Ce Zhang, and Ji Liu. Asynchronous decentralized parallel stochastic gradient descent. In Proc. ICML, volume 80, pages 3049-3058, 2018.
[13] Tao Lin, Sai Praneeth Karimireddy, Sebastian U. Stich, and Martin Jaggi. Quasi-global momentum: Accelerating decentralized deep learning on heterogeneous data. In Proc. ICML, volume 139, pages
2021.
[14] Paolo Di Lorenzo and Gesualdo Scutari. NEXT: in-network nonconvex optimization. IEEE Trans. Signal Inf. Process. over Networks, 2(2):120-136, 2016.
[15] Yucheng Lu and Christopher De Sa. Optimal complexity in decentralized training. In Proc. ICML, volume 139, pages 7111-7123, 2021.
[16] Giovanni Neglia, Chuan Xu, Don Towsley, and Gianmarco Calbi. Decentralized gradient methods: does topology matter? In AISTATS, volume 108, pages 2348-2358, 2020.
[17] Dominic Richards and Patrick Rebeschini. Optimal statistical rates for decentralised non- parametric regression with linear speed-up. In NewrlPS, pages 1214-1225, 2019.
[18] Dominic Richards and Patrick Rebeschini. Graph-dependent implicit regularisation for dis- tributed stochastic subgradient descent. J. Mach. Learn. Res., 21:34:1-34:44 2020.
[19] Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. In ICLR, 2015.
[20] Hanlin Tang, Xiangru Lian, Ming Yan, Ce Zhang, and Liu. d:: Decentralized training over decentralized data. In Proc. ICML, volume 80, pages 4855-4863, 2018.
11

---

[21] Hanlin Tang, Xiangru Lian, Ming Yan, Ce Zhang, and Ji Liu. D2: Decentralized training over decentralized data. In Proc. ICML, volume 80, pages 4855-4863, 2018.
[22] Thijs Vogels, Lie He, Anastasia Koloskova, Sai Praneeth Karimireddy. Tao Lin, Sebastian U. Stich, and Martin Jaggi. Relaysum for decentralized deep learning on heterogeneous data, In NeurIPS, pages
2021.
[23] Jianyu Wang, Anit Kumar Sahu, Zhouyi Yang. Gauri Joshi, and Soummya Kar. MATCHA: speeding up decentralized SGD via matching decomposition sampling, CoRR, Abs//905.004355 2019.
[24] Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist novel image dataset for benchmarking machine learning algorithms. CoRR, abs/1708.07747, 2017.
[25] Bicheng Ying, Kun Yuan, Yiming Chen, Hanbin Hu, Pan Pan, and Wotao Yin. Exponential graph is provably efficient for decentralized deep training. In NeurlPS, pages 13975-13987, 2021.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [No]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [No]
(c) Did you include any assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsoureing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
12


Reviews:
[{"review_id": "vUrouopdKk", "reviewer": "Reviewer_WZhq", "summary": "This paper deeply investigated the role of topology in decentralized learning. Instead of the commonly adopted spectral gap in the literature, it proposed the \"effective number of neighbors\" concept and further revealed that the benefits of \"good\" topology are enabling larger learning rates so that it speeds up optimizations. The paper provides a sound proof of the convex case and observed similar behavior in deep learning.", "questions": "1.  The D-SGD update adopted the uncommonly used probability update rule, i.e. execute the local gradient update with some probability and gossip communication with the rest case. It makes the analysis simplified since the expectation of Lyapunov becomes the convex combination of two steps independently instead of coupling them together. What about the case that one local gradient always followed by one gossip communication? How to modify the proof framework to cover this case?\n\n2. Can we rewrite $M = (1-r)\\sum_{k=1}^\\infty\\gamma^{k-1}W^{2k}$ into the form $M = (1-\\gamma) W^{2}(I-\\gamma W^2)^{-1}$ (assuming the inverse exists), since it looks closer to toy example Eq. (3). Also, personally feel the Definition I (effective number of neighbors) in the appendix is better moved to the main context so that the reader is easier to understand what the intuition of effective neighbors means.\n\n3. The toy example use an isotropic quadratic function $\\mathbb{E} \\frac{1}{2}(d^Tx)^2 = \\frac{1}{2}\\\\|x\\\\|^2$, which has a special property that the gradient noise at the optimal point $w^\\star$ vanish so that the linear speedup is established. It is more common to use Least-Mean-Square as the toy example, which is closer to the later theorem form. ", "limitations": "The nice detailed analysis is based on homogenous data and all workers shared the same loss function. I don't think heterogonous data or different minimizer cases should be covered by the theorem in this paper. But it will be nice to use some experiments to show the sensitivity of the conclusion when that assumption is not valid.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality: The role of the topology can influence the step-size choice in decentralized learning is not a surprisingly new observation, but this is the first time I saw a well-quantified way to describe it and show it in rigorous proof.\nQuality & Clarity: The presentation is clear and well organized. I can follow the logic and proof easily. The proof looks sound to me.\nSignificance: The work is a theoretical explanation work, which can be quite useful. However, the conclusion and the proof technique seem to rely on several strict assumptions. Not sure how easy to extend this framework to more general or complicated settings.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "isgveAfLAA6", "reviewer": "Reviewer_9GNP", "summary": "In this paper, the authors showed that decentralized learning allows a larger learning rate compared to centralized learning, which can accelerate the training process. The effective number of neighbors is defined in the paper which measures the ratio of the asymptotic variance of the iterations. As a main result, the authors provided the theorem about the larges learning rate that gives the best convergence guarantees based on the local neighborhood size. The authors also provided the results of the experiment based on the CIFAR10 dataset. ", "questions": "(1) Same as the second point in weaknesses, is there any theoretical direction for the non-convex problems. It's maybe hard to get the same results as the convex case, but there is possible to get some upper bound or lower bound for the learning rate.\n(2) In the theory part, the authors use randomized D-SGD defined in equations (4). However, in practice, the standard D-SGD is used widely, which will average the parameters of neighbors and update the parameters every step without probability. It would be better to extend the current theory to the standard D-SGD.\n(3) For disconnected cases, it is more reasonable to look at batch size = batch size of decentralized case * num of workers rather than use the same batch size as the decentralized case. In the current setting, the larger stepsize mainly comes from a larger batch size compared to the decentralized case. If we use batch size * num of workers, would these results still hold?", "limitations": "Yes, the authors have adequately addressed the limitations and potential negative societal impact of their work.", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n(1) Equations are written in a clear and reader-friendly way.\n(2) Visualizations are useful to convey the authors' main idea.\n(3) Paper is well-written and easy to follow.\n\nWeaknesses:\n(1) The related work section should discuss more related works.\n(2) Although the theory of this paper is solid, it would be better to give some theoretical direction for the non-convex problems. Since data-parallel optimization is widely used in deep learning regimes rather than strongly convex problems.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "58ZUzTsND67", "reviewer": "Reviewer_nMZQ", "summary": "The paper analyzes the D-SGD algorithm where workers (nodes) in a graph collaboratively perform stochastic gradient descent of an objective function. While the existing convergence rates of D-SGD mostly depend on the spectral gap of the adjacency matrix (assuming small learning rate), this paper suggests an alternative analysis based on the \"effective number of neighbors,\" which is defined through specific random walks on the communication graph.\n\nIn Section 3, the authors define the notion of effective number of neighbors $n_W(\\gamma)$, which is roughly the variance reduction rate of random walks (with decay $\\gamma$) on the graph $W$ compared to $W = I$. They derive a convergence rate depending on $n_W$, not the spectral gap of $W$, on a quadratic toy problem. They also extend this result to strongly convex functions. This analysis can explain the convergence of D-SGD even when the spectral gap is zero.\n\nFinally, they verify their theory by training VGG-11 on CIFAR-10. They argue that $n_W$ is better aligned with empirical training performance than the spectral gap.", "questions": "- Could you provide a high-level motivation for introducing the decay $\\gamma$? I understand a parameter is technically needed to fit the random walk model, but is there a good interpretation of it?\n- Is it possible to compare the maximum learning rate in Theorem I with learning rate in other literatures?\n- How exactly are the $\\gamma$'s in the experiment chosen? From Figure 2, it seems that the ordering of $n_W$ of different graphs depends a lot on $\\gamma$. Can you also show what happens to Figure 5&6 if we use different $\\gamma$? Are those results still true?\n- Is it possible to relax Assumption B (IV)? The toy problem of Section 3 does not satisfy it since the spectrum of $\\mathbf{d} \\mathbf{d}^\\top$ can be arbitrary for $\\mathbf{d} \\sim \\mathcal{N}^d(0, 1)$. Maybe some sort of average case definition is needed (just like Definition C)?\n\n\n", "limitations": "The authors have well addressed the limitations of their work.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n- The paper captured a weakness of current theories on D-SGD and provided an improved explanation on its convergence. Now, their theory can explain the convergence when the spectral gap is zero and also better align with empirical performance of neural networks trained with D-SGD.\n- The paper introduced an interesting random walk model on a graph as a proxy for the training dynamics of D-SGD. Based on this, they define a novel concept of $n_W$, which is a key in their analysis.\n- The paper performed exhaustive experiments on various types of graph (including time-varying topology) to confirm the theory.\n\nWeaknesses\n- I believe the writing of the paper can be much improved. There were notations (e.g. $\\zeta$, $\\bar{\\mathbf{P}}$) that are used before defined, so I had to go between the main text and appendix back and forth. \n- In line 149, the paper is giving the rate in terms of $n_W$, which is not yet defined. I think it is logically better to move the result after Section 3.2 (after $n_W$ is defined).\n- There were many typos and some of them slowed down my reading significantly.\n\nTypos\n- line 193, page 6: $\\zeta = d + 2$ instead of $\\zeta = d + 1$\n- displayed equation below line 471, page 17: $\\gamma^{\\frac{k - 1}{2}}$ instead of $\\gamma^{\\frac{k}{2}}$ (think about $\\mathbf{z}^{(1)}$)\n- displayed equation below line 473, page 17: $\\gamma^{k - 1}$ instead of $\\gamma^k$ (same reason)\n- line 476, page 17: assumptions of \"Lemma\" 2\n- proof of Lemma 4, page 18: Missing subscript of $\\mathbf{b}^{(t)}$. Result is correct, but the proof has a wrong scaling. The second line leads to $\\gamma (1 - r) \\mathbf{b}_{ni + j}^{(t)} + (1 - r)^t$ -- should be fixed.\n- line 501, page 18: the inequality is in the wrong direction. Should be $\\mathbf{b}^{(t + 1)} \\geq ...$.\n- line 521, page 19: $\\nabla h(x)$\n- Figure 13, page 27: the figure and caption say different $\\gamma$", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept