PaperlayerView exact revision on arXiv

Source-linked AI summary

Exponential Graph is Provably Efficient for Decentralized Deep Training

Bicheng Ying, Kun Yuan, Yiming Chen, Hanbin Hu, Pan Pan, Wotao Yin

arXiv:2110.13363v1cs.LGmath.OC

TL;DR

Decentralized SGD reduces communication through partial averaging, but the resulting aggregation inefficiency increases the iterations needed to reach linear speedup. This paper studies exponential graphs and proves connectivity and averaging properties, then applies them to decentralized momentum SGD. The authors report that these graphs balance per-iteration communication and transient iteration complexity, with one-peer graphs achieving periodic exact averaging under stated conditions.

  • Problem

    Decentralized SGD uses less communication per iteration than global averaging, but its less effective partial averaging requires more iterations to reach linear speedup, and topology choice for balancing these costs is under-studied.

    Source: §1 · p. 2

  • Method

    The paper analyzes static and one-peer exponential graphs and applies them to decentralized momentum SGD.

    Source: §1 · p. 2, §2 · p. 3

  • Results

    The authors report that exponential graphs balance per-iteration communication and transient iteration complexity, and that log2(n) consecutive one-peer graphs achieve exact averaging when n is a power of 2.

    Source: §1 · p. 2, §7 · p. 10

  • Takeaways & Limitations

    One-peer exponential graphs provide a sparse topology with the same best-known DmSGD convergence-rate bounds as the static counterpart.

    Source: §1 · p. 2

    The cited analysis gap is DmSGD over time-varying topologies with non-convex costs; the paper reports no such analysis to the authors’ knowledge.

    Source: §2 · p. 4

Abstract

from arXiv · show

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.

1 Introduction

Decentralized SGD lowers communication through local averaging, but its weaker aggregation increases the iterations needed before linear speedup. The paper studies exponential-graph topologies to balance communication cost and averaging effectiveness.

1 Introduction

  • Partial averaging reduces communication relative to global averaging, but less effective aggregation requires more transient iterations before decentralized SGD reaches linear speedup.Transient iterations are the iterations before the linear-speedup stage.Source: §1 · pp. 1–2
  • Exponential graphs are proposed to balance per-iteration communication and transient iteration complexity, a topology-design problem described as under-studied.The paper considers static and one-peer variants and applies them to decentralized momentum SGD.Source: §1 · p. 2
  • Static exponential graphs use ⌈log2(n)⌉ neighbors per node, whereas one-peer graphs communicate with one neighbor per iteration while cycling through neighbors.The paper reports that log2(n) consecutive one-peer graphs achieve exact averaging when n is a power of 2.Source: §1 · p. 2
  • The paper establishes that exponential graphs offer a balance of communication and transient iteration complexity among commonly used topologies.Table 1 compares decentralized methods over commonly used topologies under homogeneous data distributions across nodes.Source: §1 · p. 2, Table 1 · p. 2

2 Revisit Decentralized Momentum SGD and Related Works

The section sets out decentralized momentum SGD and the network-weight assumptions used in its analysis, then reviews related algorithms and topology research. It also identifies a gap in convergence analysis for momentum SGD over time-varying topologies with non-convex costs.

2 Revisit Decentralized Momentum SGD and Related Works

  • The weight matrix encodes neighborhood communication, and its spectral gap 1 − ρ measures topology connectivity.The analysis assumes doubly-stochastic weight matrices; for a static matrix, the non-unit eigenvalues have magnitudes below 1.Source: §2 · p. 3
  • The paper focuses on decentralized momentum SGD that partially averages momentum as well as model information, and permits the topology to change across iterations.When the weight matrix is fixed, the topology is static.Source: §2 · p. 3
  • To the authors’ knowledge, existing literature provides no analysis of DmSGD over time-varying topologies with non-convex costs.The cited prior work on time-varying topologies does not directly extend to the momentum SGD studied here.Source: §2 · p. 4, §2.1 · p. 4

2.1 Related Works

  • Prior topology research examines connectivity effects and communication-efficient alternatives, while random edge activation can produce unbalanced node degrees.The review contrasts algorithmic methods for reducing topology dependence with work on communication-efficient topologies.Source: §2.1 · p. 4
  • Matcha [60] does not cover one-peer exponential graphs because it analyzes independent random undirected symmetric matchings, unlike their directed cyclic sampling.The paper also notes that this distinction matters when momentum is used.Source: §2.1 · p. 5
  • The paper concerns deep training in data-center clusters with controllable topologies, not wireless settings where topology cannot be freely changed.Source: §2.1 · p. 5

3 Spectral Gap of Static Exponential Graph

This section analyzes the connectivity of the static exponential graph through its spectral gap. It gives an upper bound that corrects earlier claims and numerically compares the gap with those of ring and grid topologies.

3 Spectral Gap of Static Exponential Graph

  • In the static graph, each node communicates with nodes at hop distances 2^0, 2^1, …, 2^⌊log2(n−1)⌋, giving maximum degree ⌈log2(n)⌉.The associated weight matrix assigns equal weights to a node and its connected neighbors.Source: §3 · p. 5
  • The static exponential graph’s spectral gap is upper bounded by 2/(1 + ⌈log2(n)⌉) for odd n, correcting prior claims of an O(1) upper bound.The paper states the bound is tight and exactly matches the numerical gap when n is even.Source: §3 · p. 5
  • The hypercube has a spectral gap of the same order, but requires an undirected symmetric graph and a node count that is a power of 2.The exponential graph is more flexible in graph size.Source: §3 · p. 5
  • Numerical results for n from 4 to 290 show the derived gap matches exactly when n is even and is much smaller than ring or grid gaps.The derived expression is ρ = 1 − 2/(1 + ⌈log2(n)⌉).Source: §3 · p. 6

4 One-Peer Exponential Graph Achieves Periodic Exact-Averaging

One-peer exponential graphs use a single communication per node per iteration yet can achieve periodic exact averaging when the number of nodes is a power of two. The paper proves this property and contrasts it with averaging behavior under other graph choices and sampling schemes.

4 One-Peer Exponential Graph Achieves Periodic Exact-Averaging

  • Each one-peer realization is sparse: every node communicates with one neighbor, with one nonzero off-diagonal entry per row and column.This decomposition reduces per-iteration communication relative to the static exponential graph.Source: §4 · p. 6
  • For n a power of two, every sequence of log2(n) consecutive one-peer exponential-graph weight matrices achieves exact averaging.The result holds for any starting iteration k and any sequence length ℓ ≥ log2(n).Source: §4 · p. 6
  • The periodic exact-averaging result assumes log2(n) is an integer; numerical tests with non-integer log2(n) did not exhibit the property.Sampling each realization without replacement preserves the property, whereas sampling with replacement generally does not unless all realizations are occasionally sampled without repeating.Source: §4 · p. 6
  • Unlike the directed, asymmetric one-peer exponential graph, the one-peer hypercube graph is undirected and symmetric.The cited hypercube variant also achieves exact averaging in log_n(n) steps.Source: §4 · p. 6
  • Numerically, one-peer exponential graphs reach exact average after log2(n) steps, while static exponential and bipartite random match graphs approach it only asymptotically.The comparison is illustrated by the decay of consensus residue.Source: §4 · p. 7

5 DmSGD with Exponential Graphs

The section analyzes decentralized momentum SGD (DmSGD) with static and one-peer exponential graphs. It reports matching convergence-rate bounds and transient iteration complexity for the two variants, while one-peer graphs require less communication per iteration and contribute to a favorable communication–convergence balance.

5 DmSGD with Exponential Graphs

  • One-peer exponential graphs give DmSGD the same established convergence rate and transient iteration complexity as static exponential graphs.The analysis assumes log2(n) is a positive integer and uses the stated assumptions for DmSGD.Source: §5 · p. 7
  • Setting β = 0 gives decentralized SGD without momentum, which the paper states can converge as fast with one-peer graphs as with static exponential graphs.Source: §5 · p. 7
  • The analysis extends to general time-varying topologies and is presented as the first result for momentum-accelerated decentralized SGD in non-convex settings.The authors note that prior analyses considered either decentralized SGD without momentum or momentum SGD with static topologies.Source: §5 · p. 8
  • For sufficiently large n, exponential graphs achieve the reported state-of-the-art balance: ˜Ω(1) per-iteration communication and ˜Ω(n^3) transient iterations.The notation ˜Ω(·) hides logarithmic factors; the paper reports smaller transient iteration complexity than ring or grid graphs.Source: §5 · p. 8
  • One-peer exponential graphs retain the static counterpart’s convergence rate while incurring strictly less communication overhead per iteration.The paper recommends the one-peer variant for decentralized deep training.Source: §5 · pp. 7–8

6 Experiments

The experiments compare decentralized training across graph topologies, then test whether one-peer exponential graphs retain static exponential graphs’ performance across models, algorithms, and tasks. Results indicate that one-peer graphs offer efficient communication while maintaining strong training performance.

6 Experiments

  • The experiments examine training time and validation accuracy, using time as a communication-efficiency measure and accuracy as a rough measure of convergence.The study also tests convergence curves on ImageNet with ResNet-50 at 8 × 8 GPUs.Source: §6 · p. 8, Figure 5 · p. 9

6.1 Setup

  • The study evaluates ImageNet-1K classification for 90 epochs across 32–256 GPUs, measuring training time and validation accuracy.The setup uses mixed precision, momentum SGD, and a warmed-up, decayed learning rate.Source: §6.2 · p. 8, §6 · p. 8

6.2 Exponential graphs enable efficient and high-quality training

  • One-peer and static exponential graphs rank among the fastest and most accurate topologies, while bipartite matching is fast but less accurate.For 32 × 8 GPUs, one-peer is approximately tied with bipartite random matching for training time; its accuracy is approximately tied with static exponential and random graphs.Source: §6.2 · p. 9, Table 2 · p. 9

6.3 One-peer exponential graph v.s. static exponential graph

  • In object detection, static and one-peer exponential graphs enable decentralized algorithms with almost the same performance in each scenario.Table 4 compares methods and models on PASCAL VOC and COCO.Source: Table 4 · p. 10, §6.3 · p. 10

7 Conclusion and Future Works

The paper concludes that exponential graphs combine efficient communication with effective averaging, and that one-peer graphs match their static counterparts’ convergence rate. Its appendix illustrates how the static graph’s weights encode incoming and outgoing neighbors.

7 Conclusion and Future Works

  • One-peer exponential graphs achieve the same DmSGD convergence rate as static exponential graphs, while a sequence of log2(n) graphs achieves exact averaging when n is a power of 2.The paper also reports nearly minimum per-iteration communication time and transient iteration complexity for large n.Source: §7 · p. 10

A.1 Weight matrix example

  • In the six-node static exponential graph, node 0’s weight-matrix column marks its outgoing neighbors and itself, while its row marks incoming neighbors and itself.Figure 6 illustrates the graph and its associated weight matrix.Source: §A.1 · p. 14, Figure 6 · p. 14

A.2 Spectral gap of static exponential graph

The appendix uses Fourier analysis of circulant matrices to establish a spectral-gap bound for static exponential graphs, then compares common and random topologies by degree, connectivity, and communication. It also describes example graph constructions and their weight matrices.

A.2 Spectral gap of static exponential graph

  • For n = 2^τ, the proof excludes eigenvalue magnitudes between (τ − 1)/(τ + 1) and 1, using DFT diagonalization of circulant matrices.The proof treats the special power-of-two case and then extends its argument to arbitrary n.Source: §A.2 · pp. 15–16
  • For odd n, the numerical bound is not attained, and the authors report no closed-form spectral gap or identity for the second-largest eigenvalue.The passage describes these as unresolved characterizations.Source: §A.2 · p. 17

A.3.1 Details of each graph and the associated weight matrix

  • The 1/2-random graph uses independently present edges with probability 1/2; its maximum degree concentrates around (n − 1)/2 and its spectral gap is 1 − ρ = O(1).The appendix characterizes this realization as rather dense.Source: §A.3.1 · p. 19
  • A bipartite random match graph randomly pairs nodes each iteration, so every node exchanges information with one neighbor; its spectral gap is reported as unknown in the literature.Source: §A.3.1 · p. 19

A.3.2 Comparison with commonly-used topologies

  • Table 5 compares commonly used topologies by maximum degree and spectral gap; cited gap results for ring, star, grid, and torus come from [43].Source: Table 5 · p. 19, §A.3.2 · p. 19

A.3.3 Comparison with random topologies

  • Table 6 reports that Erdos-Renyi and geometric random graphs are equivalent to or worse than exponential graphs on communication or transient iteration complexity; their communication costs are expected values.The authors note that realized maximum degrees can exceed expected degrees, further increasing communication cost.Source: Table 6 · p. 20, §A.3.3 · p. 20

B.1 Weight matrix example

  • Figure 9 illustrates the weight matrix for the six-node one-peer exponential graph.Source: §B.1 · p. 20

B.2 Periodic exact averaging of one-peer exponential graph

This section characterizes periodic exact averaging in one-peer exponential graphs, including how graph size and sampling schedules affect it. It also develops DmSGD convergence analysis by bounding the historical average gradient and consensus residue under stated conditions.

B.2 Periodic exact averaging of one-peer exponential graph

  • For n = 2^τ, the one-peer exponential weight matrices are doubly stochastic, and applying each of the τ distinct matrices at least once yields an exact consensus average.The matrices need not be applied in a particular order; their indices modulo τ must cover 0 through τ−1.Source: §B.2 · pp. 20–21

B.3.1 One-peer exponential graph with the size that is not power 2

  • When n is not a power of 2, one-peer exponential graphs achieve only asymptotic, not periodic, exact averaging; for n = 3, periodic exact averaging is impossible.The three-node case has period ⌈log2(3)⌉ = 2.Source: §B.3.1 · p. 23

B.3.2 One-peer exponential graph with uniform sampling and random permutation

  • Random-permutation one-peer graphs retain exact averaging, whereas uniform sampling may miss a matrix within τ steps but includes all matrices with probability one over sufficiently long runs.The passage reports that Figure 11 validates these claims.Source: §B.3.2 · pp. 23–24, Figure 11 · p. 24

C Deriving transient iteration complexity for DmSGD

  • DmSGD reaches linear speedup after Ω(n^3/(1 − ρ)^2) iterations with homogeneous data, versus Ω(n^3/(1 − ρ)^4) with heterogeneous data when b^4 and σ^4 are ignored.The homogeneous case assumes identical data distributions across nodes; the heterogeneous complexity omits the influences of b^4 and σ^4.Source: C Deriving transient iteration… · p. 24

D.1 Notations and preliminaries

  • The analysis rewrites DmSGD in matrix form with periodic-exact-averaging weights, derives its averaged recursion and auxiliary momentum sequence, and proves the theorem using descent and consensus lemmas.The auxiliary sequence is defined from the averaged iterates and momentum parameter β.Source: §D.1 · pp. 25–26

D.2 Descent lemma

  • Under smoothness and independent gradient-noise assumptions, the descent analysis bounds the averaged gradient norm using objective decrease plus noise and momentum terms.The derivation averages the one-step bound over iterations.Source: §D.2 · pp. 28–29
  • The descent lemma bounds the historical average gradient at the average trajectory by initial excess risk, gradient noise, and average consensus residue.The supplied passages do not expose the complete bound formula.Source: §D.2 · p. 30

D.3 Consensus lemma

  • With τ = ln(n) an integer, periodic exact averaging lets the recursion reference a prior period at mτ, where τ ≤ k − mτ < 2τ.The period reference is used to transform the recursion into a consensus-residue form.Source: §D.3 · p. 31
  • Under Assumptions A.1–A.4 and γ ≤ (1−β)/(6Lτ), Lemma 6 gives a bound on the consensus residue.The excerpt identifies σ² and b² as gradient-noise and data-heterogeneity constants, respectively, but does not show the full bound.Source: §D.3 · p. 32
  • An all-reduce warm-up during the first τ iterations sets initial iterate disagreement to zero, eliminating the initial-phase term in the consensus-residue bound.Without warm-up, the initial-phase contribution is diminished by T and becomes almost negligible when T is large enough.Source: §D.3 · p. 35

D.4 Proof of the convergence Theorem 1

The proof establishes Theorem 1’s transient-iteration complexity for one-peer exponential graphs. Under both homogeneous and heterogeneous data, static and one-peer exponential graphs balance per-iteration communication with transient complexity better than the compared topologies.

D.4 Proof of the convergence Theorem 1

  • The proof derives Theorem 1’s transient-iteration complexity by combining the descent and consensus lemmas and setting τ = log2(n).The derivation treats homogeneous and heterogeneous data scenarios separately.Source: §D.4 · pp. 35–36

D.5.1 Comparison in per-iteration communication and transient iteration (Homogeneous)

  • With logarithmic terms ignored, both exponential graphs achieve ~Ω(1) per-iteration communication and ~Ω(n^3) transient iteration complexity, nearly best among compared graphs.Table 7 assumes homogeneous data distributions.Source: §D.5.1 · p. 37, Table 7 · p. 37

D.5.2 Comparison in per-iteration communication and transient iteration (Heterogeneous)

  • With logarithmic terms ignored, both exponential graphs achieve ~Ω(1) per-iteration communication and ~Ω(n^3) transient iteration complexity, nearly best among compared graphs.Table 8 summarizes the heterogeneous-data setting.Source: §D.5.2 · p. 37, Table 8 · p. 37

D.5.3 Exponential graphs endow DmSGD with smaller transient iterations: numerical validation

Numerical experiments compare DmSGD over exponential graphs with other topologies, and the paper also examines node counts that are not powers of two. The experiments report shorter transient iterations for exponential graphs than for grid and ring, while one-peer performance remains similar to its static counterpart at non-power-of-two sizes.

D.5.3 Exponential graphs endow DmSGD with smaller transient iterations: numerical validation

  • Static exponential DmSGD converges closely to parallel momentum SGD and has the shortest transient iterations; one-peer is slightly slower but both beat grid and ring.The logistic-regression experiment uses 64 nodes, d = 10, M = 14000, β = 0.8, and averages 20 trials.Source: §D.5.3 · pp. 37–38, Figure 13 · p. 38

E.2 DmSGD with exponential graphs when n is not a power of 2

  • For node counts that are not powers of two, one-peer exponential DmSGD achieves similar or even better training performance than its static counterpart.The comparison uses the same experimental setting as Sec. 6.2.Source: §E.2 · p. 38, Table 9 · p. 38

E.3 Performance with DSGD

Without momentum, DSGD’s accuracy is lower than DmSGD’s across the tested scenarios. Within DSGD, the exponential-graph topologies retain an accuracy advantage over ring.

E.3 Performance with DSGD

  • All DSGD scenarios have accuracy over 7% lower than DmSGD scenarios, highlighting momentum’s critical role in these real deep-learning experiments.The comparison removes momentum by setting β = 0.Source: §E.3 · pp. 38–39, Table 10 · p. 39
  • One-peer and static exponential graphs achieve similar DSGD accuracy, and both outperform ring in accuracy.Table 10 compares top-1 validation accuracy across topologies.Source: §E.3 · p. 39, Table 10 · p. 39
  • DSGD training time across topologies is similar to the DmSGD times reported in Table 2.The paper omits training-time results from the following table.Source: §E.3 · p. 39

E.4 Example code for implementation

The implementation uses BlueFog for topology organization, weight-matrix generation, and partial averaging. One-peer graph utilities update optimizer communication weights, while training overlaps communication with computation.

E.4 Example code for implementation

  • BlueFog facilitates topology organization, weight-matrix generation, and efficient partial averaging for decentralized methods.Source: §E.4 · p. 39
  • neighbor_allreduce uses self_weight for wii and src_weights or dst_weights for wij, depending on pull-mode or push-mode communication.The passage identifies neighbor_allreduce as implementing the displayed equation.Source: §E.4 · p. 39
  • One-peer graph utilities provide each node’s connection information and pass it to neighbor_allreduce by updating optimizer members.The code sets the source and self weights to 0.5.Source: §E.4 · pp. 39–40
  • Training wraps SGD in a decentralized optimizer, updates the one-peer graph each iteration, and overlaps neighbor communication with computation.Communication is triggered during backpropagation; the model update waits for communication to finish.Source: §E.4 · p. 40

Related papers

Loading 2110.13363v1…