DecentLaM: Decentralized Momentum SGD for Large-batch Deep Training
Kun Yuan1 *, Yiming Chen1* , Xinmeng Huang2* , Yingya Zhang1 , Pan Pan1 , Yinghui Xu1 , Wotao Yin1
1
DAMO Academy, Alibaba Group 2 University of Pennsylvania

Abstract
The scale of deep learning nowadays calls for efficient
distributed training algorithms. Decentralized momentum
SGD (DmSGD), in which each node averages only with
its neighbors, is more communication efficient than vanilla
Parallel momentum SGD that incurs global average acrossall computing nodes. On the other hand, the large-batch
training has been demonstrated critical to achieve runtime
speedup. This motivates us to investigate how DmSGD performs in the large-batch scenario.
In this work, we find the momentum term can amplify theinconsistency bias in DmSGD. Such bias becomes more evident as batch-size grows large and hence results in severe
performance degradation. We next propose DecentLaM, anovel decentralized large-batch momentum SGD to remove
the momentum-incurred bias. The convergence rate for bothstrongly convex and non-convex scenarios is established.
Our theoretical results justify the superiority of DecentLaM
to DmSGD especially in the large-batch scenario. Experimental results on a a variety of computer vision tasks andmodels show that DecentLaM promises both efficient andhigh-quality training.

1. Introduction
Efficient distributed training across multiple computing
nodes is critical for large-scale deep learning tasks nowadays. As a principal training algorithm, Parallel SGD computes a globally averaged gradient either using the Parameter Server (PS) [24] or the All-Reduce communication primitive [38]. Such global synchronization across all nodes either incurs significant bandwidth cost or high latency, whichhampers the training scalability.
Decentralized SGD [36, 7, 25, 26, 4, 10] based on partial averaging has become one of the major approaches
in the past decade to reduce communication overhead in
distributed optimization. Partial averaging, as opposed to
global averaging used in Parallel SGD, requires every node
compute the average of the nodes in its neighborhood, see* Equal contribution. Correspondence can be addressed to Kun Yuan
<kun.yuan@alibaba-inc.com>

5#
12
1#
4

1

2

W=

3

0
1#
3
0
0

1#
4
1#
4
1#
4
0
1#
4
0

0
1#
4
5#
12
0
0
1#
3

1#
3
0
0
5#
12
1#
4
0

0
1#
4
0
1#
4
1#
4
1#
4

0
0
1#
3
0
1#
4
5#
12

Figure 1. Illustration of decentralized methods. Nodes receive
information from neighbors; they do not relay information. For
example, nodes 4 and 6 collect information from their neighbors{1, 5} and {3, 5}, respectively. Other nodes do the same but not
depicted. Topology connectivity can be represented in a matrix, as
shown in the right figure, see more details in Sec. 3.

Fig. 1. If a sparse topology such as one-peer exponential
graph [4] is utilized to connect all nodes, each node only
communicates with one neighbor each iteration and hence
saves remarkable communications. Decentralized SGD cantypically achieve 1.3 ∼ 2× training time speedup without
performance degradation [25, 4, 23].
Existing Decentralized SGD methods [25, 26, 47, 27, 4]
and their momentum accelerated variants [56, 44, 15, 5]
primarily utilize small-batch in their algorithm design.
However, recent hardware advances make it feasible tostore large batches in memory and compute their gradients timely. Furthermore, the total batch size naturally
grows when more computing nodes participate into training. These two primary reasons lead to the recent exploration of large-batch deep training algorithms.
In fact, large-batch training has been extensively studied
in Parallel SGD. Pioneering works [17, 52, 54] find largebatch can significantly speed up Parallel SGD. First, thecomputation of a large-batch gradient can fully utilize thecomputational resources (e.g., the CUDA cores and GPU
memories). Second, large-batch gradient will result in a reduced variance and hence enables a much larger learning
rate. With newly-proposed layer-wise adaptive rate scaling(LARS) [52] and its variant [54], large-batch Parallel momentum SGD (PmSGD) can cut down the training time of
BERT and Resnet-50 from days to hours [55].
This naturally motivates us to study how Decentralized
momentum SGD (DmSGD) performs with large batch-size.

3029

2. Related Works
DatasetBatch-size

Cifar-10
2K
8K

ImageNet
2K
32K

PmSGD
DmSGD

91.6%
91.5%

76.5%
76.5%

89.2%
88.3%

75.3%
74.9%

Table 1. Top-1 validation accuracy comparison between PmSGD
and DmSGD under the small-batch and large-batch settings. No
layer-wise adaptive rate scaling is used in any of these algorithms.
All hypter-parameters are exactly the same. More experimental
details can be referred to Appendix G.1

To this end, we compared PmSGD and DmSGD over Cifar10 (Resnet-20) and ImageNet (Resnet-50) with both small
and large batches. Their performances are listed in Table 1.
While DmSGD achieves the same accuracy as PmSGD withsmall batch-size, it has far more performance degradation in
the large-batch scenario. This surprising observation, which
reveals that the extension of DmSGD to large-batch is nontrivial, raises two fundamental questions:• Why does DmSGD suffer from severe performancedegradation in the large-batch scenario?
• How to enhance the accuracy performance of large-batch
DmSGD so that it can match with or even beat PmSGD?
This paper focuses on these questions and provides affirmative answers. In particular, our main contributions are:
• We find large-batch DmSGD has severe performancedegradation compared to large-batch PmSGD and clarify
the reason behind this phenomenon. It is discovered thatthe momentum term can significantly amplify the inconsistency bias in DmSGD. When batch-size is large and thegradient noise is hence dramatically reduced, such inconsistency bias gets dominant and thus degrades DmSGD’s
performance notably.
• We propose DecentLaM, a novel decentralized largebatch momentum SGD to remove the momentumincurred bias in DmSGD. We establish its convergence
rate for strongly convex and non-convex scenarios. Our
theoretical results show DecentLaM has superior performance to existing decentralized momentum methods, andsuch superiority gets more evident as batch size grows.
• Experimental results on a variety of computer vision tasks
and models show that DecentLaM outperforms DmSGD,
DA/QG/D2 -DmSGD, PmSGD, and PmSGD with LARS
in terms of both training speed and accuracy.
The rest of this paper is organized as follows: We briefly
summarize related works in Sec. 2 and review DmSGD in
Sec. 3. We identify the issue that causes performance degradation in DmSGD (Sec. 4) and propose DecentLaM to resolve it (Sec. 5). The convergence analysis and experiments
are established in Sec. 6 and Sec. 7.

Decentralized deep training. Decentralized optimization
algorithms can be tracked back to [49]. Decentralized gradient descent [36, 59], diffusion [7, 42] and dual averaging[13] are among the first decentralized algorithms that target
on general optimization problems arise from signal processing and control community. In the context of deep learning,
Decentralized SGD (DSGD) have gained a lot of attentions
recently. DSGD will incur model inconsistency among
computing nodes. However, it is established in [25] that
DSGD can reach the same linear speedup as vanilla Parallel
SGD in terms of convergence rate. After that, [4] comes out
to extend DSGD to directed topology. A recent work [21]proposes a unified framework to analyze DSGD with changing topologies and local updates. [26, 35] extended DSGD
to the asynchronous setting, and [47, 51, 57] proposed decentralized stochastic primal-dual algorithms to remedy the
influence of data heterogeneity. Various communicationefficient techniques can be further integrated into DSGD
such as periodic updates [45, 21, 56], communication compression [3, 6, 22, 20, 48], and lazy communication [9, 32].
Momentum SGD training. Momentum SGD methods
have been extensively studied due to their empirical successin deep learning. The works [33, 60, 16, 31, 56] establishthat momentum SGD converges at least as fast as SGD. Momentum SGD for overparameterized models are shown toconverge faster than SGD asymptotically [43]. The exploration in decentralized momentum SGD (DmSGD) is relatively limited. [4] proposes a widely-used DmSGD approach in which a local momentum SGD step is updated
first before the partial averaging is conducted (see Algorithm 1). This approach is later extended by [44, 15] to
involve communication quantization and periodic local updates. Another work (Doubly-averaging DmSGD, or DADmSGD) [56] imposes an additional partial averaging overmomentum to increase stability. [5] proposes a new variant in which the partial-averaging step is mixed up with thelocal momentum SGD update. All these decentralize momentum methods were studied with small batch sizes.
Large-batch training. The main challenge to use largebatch lies in the generalization performance degradation.
Recent works in large-batch training centered on adaptive
learning rate strategies to enhance accuracy performance.
For example, Adam and its variants [19, 39] adjust thelearning rate based on the gradient variance, and [17] utilizes learning rate warm-up and linear scaling to boost theperformance in large-batch scenario. The layer-wise adaptive rate scaling [52, 53] can reduce the training time ofResnet-50 and BERT from days to hours. However, thestudy of large-batch training in decentralized algorithms isquite limited. This paper does not propose any adaptive rate
strategy for decentralized algorithms. Instead, we will de-3030

sign an optimization method that can reduce the intrinsic
convergence bias in decentralized algorithms and hence improve their performance in the large-batch scenario.
Decentralized methods on heterogeneous data. Decentralized large-batch training within data-centers shares thesame essence with decentralized training with heterogeneous data for EdgeAI applications. In large-batch training, the stochastic bias caused by gradient noise gets significantly reduced and the inconsistency bias caused bydata heterogeneity will become dominant. [47, 34, 57, 51]
proposed decentralized stochastic primal-dual algorithms toremedy the influence of data heterogeneity. However, noneof these algorithms show strong effective empirical performances in commenly-used deep learning models such
as ResNet-50 or EfficientNet. A concurrent work [27]proposes Quasi-Global momentum, which locally approximates the global optimization direction, to mitigate the affects of heterogeneous data. It is worth noting that while
DecentLaM is proposed for the large-batch setting within
data-centers, it is also suitable for EdgeAI applications.

3. Decentralized Momentum SGD
Problem. Suppose n computing nodes collaborate to solve
the distributed optimization problem:
 \label {dist-opt} \min _{x \in \mathbb {R}^d}\ f(x)=\frac {1}{n}\sum _{i=1}^n [f_i(x): = \mathbb {E}_{\xi _i \sim D_i} F(x;\xi _i)] \vspace {-1mm}(1)Algorithm 1: DmSGD
(0)

(0)

Require: Initialize γ, xi ; let mi = 0, β ∈ (0, 1)
for k = 0, 1, 2, ..., T − 1, every node i do(k)(k)(k) (k)Sample ξi and update gi =∇F (xi ; ξi )
(k+1)

mi

(k)

= βmi

(k)

+ gi

(k+ 21 )(k)(k+1)= xi − γmixiP(k+ 1 )
(k+1)
xi
= j∈Ni wij xj 2

▷ momentum update▷ local model update▷ partial average

Partial averaging. With weights {wij } and the set ofneighbors Ni , the neighborhood partial averaging operationof node i can be expressed as
 \label {partial-ave} \mbox {Partial averaging:}\quad x_i^{+} \leftarrow \sum _{j\in \mathcal {N}_i}w_{ij} x_j.

(3)

Partial averaging has much lower communication overheads. When the network topology is sparse, partial averaging typically incurs O(1) latency plus O(1) bandwidth cost,which are independent of the number of computing nodes n.
Consequently, decentralized methods are more communication efficient than those based on global averaging.
Decentralized SGD (DSGD). Given a connected network
topology and weights {wij }, each node i in DSGD will iterate in parallel as follows:
  x_i^{(k+\frac {1}{2})} &= x_i^{(k)} - \gamma \nabla F(x_i^{(k)}; \xi _i^{(k)})\quad \mbox {(local update)} \label {dsgd-1}\\ x_i^{(k+1)} &= \sum _{j\in \mathcal {N}_i} w_{ij}\, x_j^{(k+\frac {1}{2})} \hspace {0.65cm} \mbox {(partial averaging)} \label {dsgd-2}

where fi (x) is local to node i, and random variable ξidenotes the local data that follows distribution Di . Eachnode i can locally evaluate stochastic gradient ∇F (x; ξi ); it
must communicate to access information from other nodes.
Notation. We let [n] := {1, · · · , n}, and 1 ∈ Rd be avector with each element being 1.
Network topology and weights. Decentralized methods
are based on partial averaging within neighborhood that isdefined by the network topology. We assume all computing nodes are connected by a undirected network topology.
Such connected topology can be of any shape, but its degreeand connectivity will affect the communication efficiency
and convergence rate of the decentralized algorithm. For agiven topology, we define wij , the weight to scale information flowing from node j to node i, as follows:
 \label {wij} w_{ij} \begin {cases} > 0 & \mbox {if node $j$ is connected to $i$, or $i=j$;} \\ = 0 & \mbox {otherwise.}\vspace {-2mm} \end {cases}(2)

We further define Ni := {j|wij > 0} as the set of neighbors of node i which also includes node i itself. We define
weight matrix W := [wij ]ni,j=1 ∈ Rn×n to stack all weights
into a matrix. Such matrix W will characterize the sparsity
and connectivity of the underlying network topology. An
example of the topology and its associated weight matrix
W is illustrated in Fig. 1.

(5)
(k)

(k)

where xi is the local model of node i at iteration k, ξi isthe realization of ξi at iteration k, and γ is the learning rate.
When the network topology is fully connected and wij =1/n, DSGD will reduce to the Parallel SGD algorithm.
Decentralized momentum SGD (DmSGD). Being the
momentum accelerated extension of DSGD, DmSGD has
been widely-used in existing literatures [26, 4, 44, 15, 56,
5]. The primary version of DmSGD is listed in Algorithm 1.
When small-batch is used, DmSGD will achieve 1.3 ∼ 2×
speedup in training time compared to PmSGD without visibly loss of generalization performance.
Assumptions. We introduce several standard assumptions
to facilitate future analysis:
A.1 Each fi (x) is L-smooth, i.e., ∥∇fi (x) − ∇fi (y)∥ ≤L∥x − y∥ for any x, y ∈ Rd .
(k)

A.2 The random sample ξi is independent of each otherfor any k and i. We also assume each stochastic gradientis unbiased and has bounded variance, i.e., E[∇F (x; ξi )] =∇fi (x) and E∥∇F (x; ξi ) − ∇fi (x)∥2 ≤ σ 2 .
A.3 The network topology is strongly connected, and theweight matrix is symmetric and satisfies W 1 = 1.

3031

P
Assumption A.3 indicates j∈Ni wij = 1 for i ∈ [n],which is critical to guarantee the partial averaging (3)to converge to the global averaging asymptotically. The
weight matrix satisfying Assumption A.3 can be easily constructed, see [42, Table 14.1].

Relative Erros100

4. DmSGD Incurs Severe Inconsistency Bias
Table 1 shows that large-batch DmSGD has a severe performance degradation compared to PmSGD. This section
targets to explore the reason behind this phenomenon. Tohighlight the insight, we assume each fi (x) to be strongly
convex, and x⋆ to be the global solution to problem (1).
Limiting bias of decentralized methods. The convergenceof decentralized methods such as DSGD and DmSGD will
suffer from two sources of bias: Stochastic bias is causedby the utilization of stochastic gradient in algorithms; Inconsistency bias is caused by the data inconsistency between nodes.
In addition, these two bias are orthogonal to each other, i.e.,  \boxed {\lim _{k\to \infty } \sum _{i=1}^n \mathbb {E}\|x_i^{(k)} - x^\star \|^2 = \mbox {sto. bias} + \mbox {inconsist. bias}} \nonumber

An example illustrating the stochastic and inconsistency
bias of DSGD is established in Appendix C.1.
Inconsistency bias dominates large-batch scenario. In
the large-batch scenario, the gradient nosie will be notably
reduced. In an extreme case where a full-batch gradient isutilized, the stochastic bias becomes zero. This leads to
Proposition 1. The inconsistency bias dominates the convergence of large-batch decentralized algorithms.
DmSGD’s inconsistency bias: intuition. The inconsistency bias can be achieved by letting gradient noise be zero.
(k)(k) (k)(k)
To this end, we let gi = E[∇F (xi ; ξi )] = ∇fi (xi )be the full-batch gradient. Note that both model xi andgradient gi are deterministic due to the removal of gradient noise. By substituting the momentum update and local
model update into the partial averaging step in Algorithm 1,
we can rewrite DmSGD (see Appendix B.1) as
 \label {xsdhs7} x_i^{(k+1)} &= \underbrace {\sum _{j\in \mathcal {N}_i} w_{ij} \Big ( x_j^{(k)} - \gamma \nabla f_j(x_j^{(k)}) \Big )}_{\rm DSGD} \quad \mbox {(DmSGD)}\nonumber \\ &\quad + \underbrace {\beta \Big ( x_i^{(k)} - \sum _{j\in \mathcal {N}_i} w_{ij} x_j^{(k-1)} \Big )}_{\rm momentum},\ \forall i\in [n].

(6)node:8, learning-rate:0.001, momentum:0.8

DSGD
DmSGD

10 1

10 2

10 3
0

200

400

600

800

Iterations

1000 1200 1400

Figure 2. Convergence comparison between DSGD and DmSGD
for a full-batch linear regression problem. Detailed experimental
setting is in Appendix G.2.

linear regression problem confirms such conclusion. It isobserved in Fig. 2 that DmSGD converges faster but suffersfrom a larger bias than DSGD.
DmSGD’s inconsistency bias: magnitude. The following proposition quantitatively evaluates the magnitude of
DmSGD’s inconsistency bias:
Proposition 2. Under Assumptions A.1 and A.3, if eachfi (x) is further assumed to be strongly-convex, and thefull-batch gradient ∇fi (x) is accessed per iteration, then
DmSGD (6) has the following inconsistency bias:
 \label {DmSGD-hb} \lim _{k\to \infty } \sum _{i=1}^n \|x_i^{(k)} - x^\star \|^2 = O\Big ( \frac {\gamma ^2 b^2}{(1-\beta )^2} \Big ),(7)

Pnwhere b2 = (1/n) i=1 ∥∇fi (x⋆ )∥2 denotes the data inconsistency between nodes, and β is the momentum coefficient. (Proof is in Appendix C.2)
Pn(k)
Note that we do not take expectation over i=1 ∥xi −⋆ 2
x ∥ in (7) because no gradient noise exists in recursion(6). Recall from Appendix C.1 that DSGD has an inconsistency bias on the order of O(γ 2 b2 ). Comparing it with
(7), it is observed that the momentum term in DmSGD isessentially amplifying the inconsistency bias by a marginof 1/(1 − β)2 . This can explain why DmSGD converges
less accurate than DSGD as illustrated in Fig. 2. Notingthat β is typically set close to 1 in practice, DmSGD cansuffer from a significantly large inconsistency bias. Since
inconsistency bias dominates the large-batch scenario (seeProposition 1), DmSGD is thus observed to have a severely
deteriorated performance as illustrated in Table 1.

5. Improving Inconsistency Bias: DecentLaM
To improve large-batch DmSGD’s accuracy, we have to
reduce the influence of momentum on inconsistency bias.

Since the momentum term in DmSGD (6) cannot vanish
as k increases, it will impose an extra inconsistency bias
to DSGD. A simple numerical simulation on a full-batch

Intuition. The amplified inconsistency bias suffered by
DmSGD is caused by the non-vanishing momentum termin (6). An intuitive remedy is to replace the partial averag-

3032

ing

P

j∈Ni wij xj with xi inside the momentum, i.e.,

100

Relative Erros

 \label {decentLaM-2} x_i^{(k+1)} &= \underbrace {\sum _{j\in \mathcal {N}_i} w_{ij} \Big ( x_j^{(k)} - \gamma \nabla f_j(x_j^{(k)}) \Big )}_{\rm DSGD} \quad \mbox {(DecentLaM)}\nonumber \\ &\quad + \underbrace {\beta \Big ( x_i^{(k)} - x_i^{(k-1)} \Big )}_{\rm momentum},\ \forall i\in [n].

(8)node:8, learning-rate:0.001, momentum:0.8

DSGD
DmSGD
DecentLaM

10 1

10 2

10 3
0

In the above recursion, the momentum term will diminish
to zero as k goes to infinity1 . As a result, it is expected thatrecursion (8) will converge to the same solution as DSGD.
We simulate the convergence behaviour of recursion (8) under the same setting as Fig. 2. It is observed in Fig. 3 thatthe proposed algorithm converges as fast as DmSGD but toa more accurate solution. Since recursion (8) is with an improved inconsistency bias, it better fits into the large-batch
scenario than DmSGD. We thus name it as decentralized
large-batch momentum SGD, or DecentLaM for short.
DecentLaM’s inconsistency bias. The following proposition quantitatively evaluates the magnitude of DecentLaM’s
inconsistency bias (Proof is in Appendix C.3):
Proposition 3. Under the same assumptions as Proposition 2, DecentLaM (8) has an inconsistency bias as follows:
 \label {DecentLaM-hb} \lim _{k\to \infty } \sum _{i=1}^n \|x_i^{(k)} - x^\star \|^2 = O\Big (\gamma ^2 b^2\Big ),(9)

Remark 1. Comparing with DmSGD’s inconsistency bias
(7), it is observed that DecentLaM completely removes thenegative effects of momentum; it improves DmSGD’s inconsistency bias by a margin of 1/(1 − β)2 . When b2 is large
or β is close to 1, such improvement is remarkable.
Remark 2. Comparing with DSGD’s inconsistency biasO(γ 2 b2 ), it is observed that DecentLaM has exactly thesame inconsistency bias as DSGD. However, the momentum
term in DecentLaM will significantly speed up its convergence rate. The simulation results in Fig. 3 are consistent
with the conclusions discussed in Remarks 1-2.
Efficient implementation. To apply DecentLaM (8) totrain deep neural networks, we need two additional modifications: (i) the full-batch gradient ∇fi (x) needs to be replaced with the stochastic gradient ∇F (x; ξi ); (ii) recursion(8) needs to be transformed to fit into the momentum SGD
optimizer provided by PyTorch [37] or TensorFlow [2]. To
this end, we introduce an important auxiliary variable:

200

400

600

800

Iterations

1000 1200 1400

Figure 3. Convergence comparison between DSGD, DmSGD anddecentLaM for a full-batch linear regression problem.
Worker 0
ForwardBackward

Neighborhood
Communication
to update !"($)
according to (10)…
ForwardBackward

step

step

WFBP

Worker n

Figure 4. The workflow of DecentLaM in a training iteration.
(k)

Note that the construction of gi involves one round of
back-propagation (to evaluate ∇F ) and one round of neigh(k)borhood communications. With gi in (10), we can rewrite
DecentLaM (8) as in Algorithm 2, see Appendix B.2 fordetail derivation. This implementation is almost the sameas the vanilla momentum SGD within a single computing(k)node, with the exception to construct gi as in (10). The
momentum update and local model update in Algorithm
2 can be conducted via the mSGD optimizer provided by
PyTorch or TensorFlow. As shown in Fig. 4, the dashedpart, which is different from the DmSGD workflow, enables
an efficient wait-free backpropagation (WFBP) implementation that can overlap communication and computation.

6. Convergence analysis of DecentLaM
Sec. 5 proposes a novel algorithm DecentLaM and explains why it better fits into the large-batch scenario. Thissection establishes the formal convergence analysis in thestrongly-convex and non-convex scenarios, respectively.
We let λn denotes the smallest eigenvalue of matrix W .

Algorithm 2: DecentLaM
(0)

(0)

Require: Initialize γ, xi ; let mi = 0, β ∈ (0, 1)
for k = 0, 1, 2, ..., T − 1, every node i do(k)(k)
Sample ξi and update gi according to (10) \label {DecentLaM-gi} g_i^{(k)} \hspace {-0.8mm}=\hspace {-0.8mm} \frac {1}{\gamma } x_i^{(k)} \hspace {-0.8mm}-\hspace {-0.8mm} \frac {1}{\gamma } \sum _{j\in \mathcal {N}_i}w_{ij}\big ( x_j^{(k)} \hspace {-0.8mm}-\hspace {-0.8mm} \gamma \nabla F(x_j^{(k)}; \xi _j^{(k)})\big ) (10)

(k+1)

mi

(k)

= βmi

(k)

+ gi

(k+1)
(k)
(k+1)
xi
= xi − γmi
1 It is because x(k) − x(k−1) → 0 when x(k) converges.
i
i
i

3033

▷ momentum update▷ local model update

6.1. Strongly-convex scenario

Strongly-convex

Assumption A.4 Each fi (x) is µ-strongly convex, i.e.,⟨∇fi (x) − ∇fi (y), x − y⟩ ≥ µ∥x − y∥2 for any x, y ∈ Rd .
Theorem 1. Under Assumption A.1–A.4, if W is further assumed to be positive definite, and the constant learning rate
γ is on the order of O( L1′ min{(1 − β)2 , Lµ′ }), the DecentLaM algorithm in Algorithm 2 will converge as (Proof is in
Appendix E.1):

DmSGD [15]N.A.

DmSGD [44]M
O γ(1−β)62DmSGD (eq.(7))γ bO (1−β)2DA-DmSGD [56]

N.A.

γ b̂
O (1−β)2O(γ 2 b2 )O(γ 2 b̂2 )DecentLaM

5/2

2 2

N.A
2 2



Table 2. Inconsistency bias comparison between various algorithms. Quantity M is the gradient’s upper bound, which is typically much larger than the data inconsistency b or b̂.

 \label {decentLaM-conv-sc} &\ \frac {1}{n}\sum _{i=1}^n\mathbb {E}\|x_i^{(k)} - x^\star \|^2 \nonumber \\ =& O\Big ( \underbrace {(1-\frac {\gamma \mu }{1-\beta })^k}_{\rm convg.\ rate} + \underbrace {\frac {\gamma \sigma ^2}{1-\beta }}_{\rm sto.\ bias} + \underbrace {\gamma ^2 b^2}_{\rm inconsist. bias}\Big )(11)

The constant L′ is closely related to the Lipschitz constantL, see the definition in Appendix E.1. Expression (11) indicates that DecentLaM will converge exponentially fast toa limiting bias. The limiting bias (which can be achievedby letting k → ∞) can be separated into the stochastic bias
and the inconsistency bias, which is consistent with our discussion in Sec. 4. In addition, the inconsistency bias in (11)is consistent with the result in (9). Theorem 1 has restrictions on the positive-definiteness of W so that the analysis
can be simplified. However, they are not needed in the realpractice and not used in any of our experiments in Sec. 7.
Theorem 1 establishes the convergence of DecentLaM
with a constant learning rate. When learning rate is decaying, DecentLaM converges exactly to the global solution:
Corollary 1. Under the same assumptions as Theorem 1,
if learning rate γ = Õ( 1−βk ), DecentLaM will converge asfollows (Proof is in Appendix E.2):
 \label {decentLaM-conv-sc-2} \frac {1}{n}\sum _{i=1}^n\mathbb {E}\|x_i^{(k)} \hspace {-0.5mm}-\hspace {-0.5mm} x^\star \|^2 = \tilde {O}\Big ( \frac {1}{k} \Big )Non-convex
γ2M 2
O (1−β)2γ2M 2O (1−β)4(12)∥∇fi (x)∥ ≤ M ) [15, 44, 5]. When data distribution Di ineach computing node i is identical to each other, it holds
that fi (x) = fj (x) for any i and j, which implies b̂ = 0.
Theorem 2. Under the same assumptions as Theorem 1(replacing Assumption A.4 with A.5), the DecentLaM algorithm in Algorithm 2 will converge as follows (Proof is inPn(k)Appendix F.1, and x̄(k) = n1 i=1 xi ): \label {decentLaM-conv-nc} &\ \frac {1}{T}\sum _{k=0}^{T-1}\hspace {-0.5mm}\Big (\mathbb {E}\|\frac {1}{n}\sum _{i=1}^n \nabla f_i(x_i^{(k)})\|^2 \hspace {-0.5mm}+\hspace {-0.5mm} \frac {1}{n}\sum _{i=1}^n\mathbb {E}\|x_i^{(k)} \hspace {-0.5mm}-\hspace {-0.5mm} \bar {x}^{(k)}\|^2\Big ) \nonumber \\ =& O\Big ( \underbrace {\frac {1-\beta }{\gamma T}}_{\rm convg.\ rate} + \underbrace {\frac {\gamma \sigma ^2}{1-\beta }}_{\rm sto.\ bias} + \underbrace {\gamma ^2 \hat {b}^2}_{\rm inconsist. bias}\Big )(13)

Corollary 2. Under the same assumptions as Theorem 2,√ ), DecentLaM will converge at
if learning rate γ = O( 1−βT√rate O(1/ T ) (Proof is in Appendix F.2), which is consistent with PmSGD [31].
Remark 3. In the long report [58], we provide an enhanced
version of Theorems 1 and 2, in which DecentLaM is proved
to have a linear speedup in the iteration complexity with theincrease of the number of computing nodes n.

6.3. Comparison with existing methods
where Õ(·) hides all logarithm factors.
Corollary 1 implies that DecentLaM has the same convergence rate O(1/k) as PmSGD in the strongly-convex scenario [31]. However, it saves more communication per iteration due to the partial averaging (see Sec. 3).

6.2. Non-convex scenario
We introduce a standard data inconsistency assumption
for the non-convex scenario:
Assumption
A.5 There exits a constant b̂ > 0 such thatPn
122
i=1 ∥∇fi (x) − ∇f (x)∥ ≤ b̂ for any x, where f (x)nis the global cost function defined in (1).
Assumption A.5 is much more relaxed than the commonlyused assumption that each ∇fi (x) is upper bounded (i.e.,

As we discussed in Sec. 4, the inconsistency bias will
dominate the convergence performance as batch-size getslarge. For this reason, we list the inconsistency bias comparison between DecentLaM and existing DmSGD variants
in Table 2. By removing the influence of momentum, DecentLaM has the smallest inconsistency bias. This implies
DecentLaM can perform better in the large-batch scenario.
After completing this work, we become aware of the
concurrent work QG-DmSGD [27] that can also achieveO(γ 2 b̂2 ) for non-convex scenario. However, QG-DmSGD
is based on a strategy to mimic the global momentum,
which is different from the core idea to develop DecentLaM. Furthermore, our analysis is also different from QGDmSGD. With a delicately designed Lyapunov function,
we can cover the convergence analysis for both non-convex

3034

and strongly-convex scenarios. In contrast, the analysis in
QG-DmSGD is for the non-convex scenario. Finally, wetheoretically uncovered the reason why traditional DmSGD[56, 15, 44] has degraded performance in Sec. 4 while QGDmSGD only justifies it empirically.

METHODP M SGDP M SGD+LARS[52]D M SGD[4, 15, 44]
DA-D M SGD[56]QG-D M SGD[27]
D2 -D M SGD[47]
D ECENT L A M

7. Experiments
In this section, we systematically compare the proposed method, DecentLaM, with well-known state-of-theart methods on typical large-scale computer vision tasks:
image classification and object detection. In particular,
we compare DecentLaM with the following algorithms.
PmSGD is the standard Parallel momentum SGD algorithm in which a global synchronization across all nodes
are required per iteration. PmSGD + LARS exploits alayer-wise adaptive rate scaling strategy [52] to boost performance with large batch-size. DmSGD [4, 15, 44], DADmSGD [56], QG-DmSGD [27] and D2 -DmSGD [47] areamong the state-of-the-art decentralized momentum SGD
methods. The details of these decentralized baselines canbe refereed to our long report [58]. All baseline algorithms
are tested with the recommended hyper-parameters in theirpapers, and comparison with more baselines (such as AWCDmSGD [5] and SlowMo [50]) is listed in [58]. Note that
DecentLaM requires symmetric (but not necessarily positive
definite) weight matrix to guarantee empirical convergence.
We implement all the aforementioned algorithms with
PyTorch [37] 1.6.0 using NCCL 2.8.3 (CUDA 10.2) as
the communication backend. For PmSGD, we used PyTorch’s native Distributed Data Parallel (DDP) module. For
the implementation of decentralized methods, we utilize
BlueFog [1], 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 computationand communication overlap. Each server contains 8 V100
GPUs in our cluster and is treated as one node. The internode network fabrics are 25 Gbps TCP as default, which is acommon distributed training platform setting. To eliminate
the effect of topology with different size in decentralized algorithms, we used 8 nodes (i.e. 8 × 8 = 64 GPUs) in alldecentralized training and changed the batch size of every
single GPU respectively.

7.1. Image Classification
Implementation. We conduct a series of image classification experiments with the ImageNet-1K [12] dataset, which
consists of 1,281,167 training images and 50,000 validation
images in 1000 classes. We train classification models withdifferent batch sizes to verify our theoretical findings. As
suggested in [17], we choose batch size equal or less than
8k as small-batch setting and the training protocol in [17]is used. In details, we train total 90 epochs. The learning

2K
76.32
76.16
76.27
76.35
76.23
75.44
76.43

BATCH S IZE
8K
16 K
76.08
75.95
76.01
76.19
75.96
75.30
76.19

76.27
76.65
76.23
76.62
76.60
76.16
76.73

32 K
75.27
75.63
74.97
75.51
75.86
75.44
76.22

Table 3. Top-1 validation accuracy of aforementioned methods
when training ResNet-50 model with different batch sizes.

rate is warmed up in the first 5 epochs and is decayed by afactor of 10 at 30, 60 and 80 epochs. For large-batch setting (batch size larger than 8K), we train total 120 epochs.
The learning rate is warmed up in the first 20 epochs andis decayed in a cosine annealing scheduler as suggested in[53]. The choice of hyper-parameter setting is not cherrypicked and we try to keep our PmSGD’s baseline around
76% while [17]’s setting has severe performance drop evenfor large-batch PmSGD. The momentum SGD optimizer iswith linear scaling by default. Experiments are trained in
the mixed precision using Pytorch native amp module.
Performance with different batch-sizes. We first compare
the top-1 accuracy of the aforementioned methods whentraining ResNet-50 [18] model (∼25.5M parameters) withdifferent batch-sizes on ImageNet. The network topology
is set as the symmetric exponential topology (see G.3). The
results are listed in Table 3. It is observed that:• DecentLaM always has better accuracy than other decentralized algorithms, and its superiority gets evident asbatch size grows. DecentLaM outperforms DmSGD and
DA-DMSGD by a large margin in the 32K batch size scenario due to its improved inconsistency bias derived in
Proposition 3, Theorems 1 and 2.
• DecentLaM even outperforms PmSGD and PmSGD +LARS in each scenario. One conjecture is that its modelinconsistency between nodes caused by the partial averaging helps the algorithm escape from shallow local minimums. As a result, DecentLaM can be better as well as
faster than DmSGD (with LARS).
• DmSGD and DA-DmSGD have a severe degraded performance in the 32K batch size scenario. It is because
the momentum have amplified their inconsistency bias,
see Proposition 2 and the results listed in Table 2. QGDmSGD has relatively small performance degradation,
but it still performs worse than DecentLaM.
We also depict the training loss and top-1 validation accuracy curves on ResNet-50 with 2K and 16K batch sizes

3035

Train Loss

5
4

0.825

3

0.800
0.775

2

0.750
50000 52500 55000

1
0

20000

70
60
50
40
30
20
10

40000

5

76.25
76.00
70

20

40

Epoch

0.74
0.72
0.70
0.68

4

75.75

0

Iterations

PmSGD
PmSGD+LARS
DmSGD
DecentLaM
DA-DmSGD

6

80
PmSGD
PmSGD+LARS
DmSGD
DecentLaM
DA-DmSGD

60

328750 9000 9250

1
0

80

2000 4000 6000 8000

70
60
50
40
30
20
10
0

Eval Top-1 Accuracy

6

7

Train LossPmSGD
PmSGD+LARS
DmSGD
DecentLaM
DA-DmSGD

Eval Top-1 Accuracy

7

Iterations

76.75
76.50
76.25
110 115PmSGD
PmSGD+LARS
DmSGD
DecentLaM
DA-DmSGD

0

25

50

75

Epoch

100

Figure 5. Convergence results on the ImageNet with respect to training loss and validation top-1 accuracy. The batch size is 2k for left-side
two figures and 16k for right-side two figures.
MODEL

R ES N ET-18
8K
16 K

BATCH S IZE2KP M SGDP M SGD+LARS
D M SGD
DA-D M SGD
QG-D M SGD
D2 -D M SGD
D ECENT L A M

70.0
70.2
69.9
70.2
70.2
69.1
70.3

69.5
69.9
69.3
70.0
70.5
68.9
69.9

68.3
70.6
68.7
70.2
70.3
70.1
70.5

2K

R ES N ET-34
8K
16 K

73.8
73.6
73.1
73.3
73.8
72.7
73.4

72.8
73.2
72.7
73.1
73.1
72.3
73.1

72.9
73.3
72.4
73.1
73.3
73.1
73.4

2K

R ES N ET-50
8K
16 K

76.3
76.2
76.3
76.4
76.2
75.4
76.4

76.1
76.0
76.0
76.2
76.0
75.3
76.2

76.3
76.7
76.2
76.6
76.6
76.2
76.7

M OBILE N ET- V 2
2K
8K
16 K

E FFICIENT N ET
2K
8K
16 K

70.6
70.7
70.5
70.4
70.8
70.2
70.3

77.6
77.7
77.5
77.6
76.8
76.6
77.8

71.1
71.3
71.0
71.4
70.6
70.6
71.4

69.5
72.3
72.1
72.1
72.0
71.8
72.2

77.0
77.2
76.9
77.4
76.5
76.4
77.2

78.1
78.2
77.5
77.8
76.7
76.5
78.3

Table 4. Top-1 validation accuracy comparison with different models and batch sizes on ImageNet dataset.

in Fig. 5. When batch size is 2K, it is observed that DecentLaM achieves roughly the same training loss as DmSGD.
However, as batch size grows to 16K, DecentLaM achieves
visibly smaller training loss than DmSGD. This observation illustrates that DecentLaM improves inconsistency bias
which can boost its convergence when batch-size is large.
For small-batch settings, DA-DmSGD and QG-DmSGD
can also achieve the best accuracy for some models.
Performance with different models. We now validate
whether DecentLaM is effective to different neural networkarchitectures. Table 4 compares the top-1 accuracy withbackbones widely-used in image classification tasks including ResNet [18], MobileNetv2 [41] and EfficientNet [46].
The accuracy of PmSGD is slightly different from those reported in [41, 46] because we do not utilize tricks such as
AutoAugment [11] that are orthogonal to our methods. It isobserved in Table 4 that either PmSGD + LARS or DecentLaM achieves best performance with large batch-size (16K)
across different models. However, DecentLaM has runtime
speedup due to its efficient neighborhood-communication.

7.2. Object Detection
We compared the aforementioned methods with wellknown detection models, e.g. Faster-RCNN [40] and RetinaNet [29] on popular PASCAL VOC [14] and COCO [30]datasets. We adopt the MMDetection [8] framework as thebuilding blocks and utilize ResNet-50 with FPN [28] as
the backbone network. We choose mean Average Precision(mAP) as the evaluation metric for both datesets. We used 8

DATASET
M ODELP M SGDP M SGD+LARS
D M SGD
DA-D M SGD
D ECENT L A M

PASCAL VOC
R-N ET F-RCNN

COCO
R-N ET F-RCNN

79.0
78.5
79.1
79.0
79.3

36.2
35.7
36.1
36.4
36.6

80.3
79.8
80.5
80.5
80.7

36.5
36.2
36.4
37.0
37.1

Table 5. Comparision of aforementioned methods with different
models on PASCAL VOC and COCO datasets. R-Net and FRCNN refer to RetinaNet and Faster-RCNN respectively.

GPUs (which are connected by the symmetric exponential
topology) and set the total batch size as 256 in all detection
experiments. Table 5 shows the performance of each algorithm. Compared with classification tasks, the total batch
size in object detection cannot be set too large (typical object detection task sets batch size as 2 within each GPU).
For this reason, our proposed method just reaches a slightly
higher mAP than other methods.

8. Conclusion
We investigated the performance degradation in largebatch DmSGD and proposed DecentLaM to remove themomentum-incurred bias. Theoretically, we demonstrate
the convergence improvement in smooth convex and nonconvex scenarios. Empirically, experimental results of various models and tasks validate our theoretical findings.

3036

References[1] BlueFog: A High-performance Decentralized Training
Framework for Deep Learning. https://github.com/
Bluefog-Lib/bluefog. 7, 33[2] Martı́n Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen,
Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, et al. Tensorflow: A
system for large-scale machine learning. In 12th {USENIX}
symposium on operating systems design and implementation({OSDI} 16), pages 265–283, 2016. 5[3] Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, andMilan Vojnovic. Qsgd: Communication-efficient sgd via gradient quantization and encoding. In Advances in Neural Information Processing Systems, pages 1709–1720, 2017. 2[4] 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. 1, 2, 3, 7, 33[5] Aditya Balu, Zhanhong Jiang, Sin Yong Tan, Chinmay
Hedge, Young M Lee, and Soumik Sarkar. Decentralized deep learning using momentum-accelerated consensus.
arXiv preprint:2010.11166, 2020. 1, 2, 3, 6, 7
[6] Jeremy Bernstein, Jiawei Zhao, Kamyar Azizzadenesheli,
and Anima Anandkumar.
signsgd with majority voteis communication efficient and fault tolerant.
arXiv
preprint:1810.05291, 2018. 2[7] Jianshu Chen and Ali H Sayed. Diffusion adaptation strategies for distributed optimization and learning over networks.
IEEE Transactions on Signal Processing, 60(8):4289–4305,
2012. 1, 2
[8] 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:1906.07155, 2019. 8[9] Tianyi Chen, Georgios Giannakis, Tao Sun, and Wotao
Yin. LAG: Lazily aggregated gradient for communicationefficient distributed learning. In Advances in Neural Information Processing Systems, pages 5050–5060, 2018. 2[10] Yiming Chen, Kun Yuan, Yingya Zhang, Pan Pan, Yinghui
Xu, and Wotao Yin. Accelerating gossip sgd with periodic
global averaging. In Proceedings of the 38th International
Conference on Machine Learning (ICML), 2021. 1[11] Ekin D Cubuk, Barret Zoph, Dandelion Mane, Vijay Vasudevan, and Quoc V Le. Autoaugment: Learning augmentation
policies from data. arXiv preprint:1805.09501, 2018. 8[12] 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. Ieee, 2009. 7[13] 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):592–606, 2011. 2[14] 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):303–338, 2010. 8[15] Hongchang Gao and Heng Huang. Periodic stochastic gradient descent with momentum for decentralized training. arXiv
preprint:2008.10435, 2020. 1, 2, 3, 6, 7
[16] Igor Gitman, Hunter Lang, Pengchuan Zhang, and Lin Xiao.
Understanding the role of momentum in stochastic gradientmethods. arXiv preprint:1910.13962, 2019. 2[17] Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, Andrew Tulloch, Yangqing Jia, and Kaiming He. Accurate, large
minibatch sgd: Training imagenet in 1 hour.
arXiv
preprint:1706.02677, 2017. 1, 2, 7
[18] 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. 7, 8
[19] Diederik P Kingma and Jimmy Ba. Adam: A method forstochastic optimization. arXiv preprint:1412.6980, 2014. 2[20] Anastasia Koloskova, Tao Lin, Sebastian U Stich, and Martin
Jaggi. Decentralized deep learning with arbitrary communication compression. In International Conference on Learning Representations, 2019. 2[21] 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. 2[22] 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. 2[23] Lingjing Kong, Tao Lin, Anastasia Koloskova, Martin Jaggi,
and Sebastian U Stich. Consensus control for decentralized
deep learning. arXiv preprint:2102.04828, 2021. 1[24] Mu Li, David G Andersen, Jun Woo Park, Alexander J
Smola, Amr Ahmed, Vanja Josifovski, James Long, Eugene J Shekita, and Bor-Yiing Su. Scaling distributed machine learning with the parameter server. In 11th {USENIX}
Symposium on Operating Systems Design and Implementation ({OSDI} 14), pages 583–598, 2014. 1[25] Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsieh, Wei
Zhang, and Ji Liu. Can decentralized algorithms outperform
centralized algorithms? a case study for decentralized parallel stochastic gradient descent. In Advances in Neural Information Processing Systems, pages 5330–5340, 2017. 1,
2[26] 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. 1, 2, 3[27] Tao Lin, Sai Praneeth Karimireddy, Sebastian U Stich, andMartin Jaggi. Quasi-global momentum: Accelerating decentralized deep learning on heterogeneous data. In Proceedingsof the 38th International Conference on Machine Learning(ICML), 2021. 1, 3, 6, 7
[28] Tsung-Yi Lin, Piotr Dollár, Ross Girshick, Kaiming He,
Bharath Hariharan, and Serge Belongie. Feature pyramid networks for object detection. In Proceedings of the3037

IEEE conference on computer vision and pattern recognition, pages 2117–2125, 2017. 8[29] Tsung-Yi Lin, Priya Goyal, Ross Girshick, Kaiming He, andPiotr Dollár. Focal loss for dense object detection. In Proceedings of the IEEE international conference on computer
vision, pages 2980–2988, 2017. 8[30] Tsung-Yi Lin, Michael Maire, Serge Belongie, James Hays,
Pietro Perona, Deva Ramanan, Piotr Dollár, and C Lawrence
Zitnick. Microsoft coco: Common objects in context. In
European conference on computer vision, pages 740–755.
Springer, 2014. 8[31] Yanli Liu, Yuan Gao, and Wotao Yin. An improved analysis of stochastic gradient descent with momentum. arXiv
preprint:2007.07989, 2020. 2, 6, 18[32] Yaohua Liu, Wei Xu, Gang Wu, Zhi Tian, and Qing Ling.
Communication-censored admm for decentralized consensus optimization. IEEE Transactions on Signal Processing,67(10):2565–2579, 2019. 2[33] Nicolas Loizou and Peter Richtárik. Momentum and stochastic momentum for stochastic gradient, newton, proximal
point and subspace descent methods. Computational Optimization and Applications, 77(3):653–710, 2020. 2[34] Songtao Lu, Xinwei Zhang, Haoran Sun, and Mingyi Hong.
Gnsd: A gradient-tracking based nonconvex stochastic algorithm for decentralized optimization. In 2019 IEEE Data
Science Workshop (DSW), pages 315–321. IEEE, 2019. 3[35] Qinyi Luo, Jiaao He, Youwei Zhuo, and Xuehai Qian.
Prague:High-performance heterogeneity-aware asynchronous decentralized training. In Proceedings of theTwenty-Fifth International Conference on Architectural Support for Programming Languages and Operating Systems,
pages 401–416, 2020. 2[36] Angelia Nedic and Asuman Ozdaglar. Distributed subgradient methods for multi-agent optimization. IEEE Transactions on Automatic Control, 54(1):48–61, 2009. 1, 2[37] 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. In Advances in Neural Information Processing Systems (NeurIPS), pages 8024–8035, 2019. 5, 7[38] Pitch Patarasuk and Xin Yuan. Bandwidth optimal all-reduce
algorithms for clusters of workstations. Journal of Paralleland Distributed Computing, 69(2):117–124, 2009. 1[39] Sashank J Reddi, Satyen Kale, and Sanjiv Kumar.
On the convergence of adam and beyond.
arXiv
preprint:1904.09237, 2019. 2[40] Shaoqing Ren, Kaiming He, Ross Girshick, and Jian Sun.
Faster r-cnn: towards real-time object detection with region
proposal networks. IEEE transactions on pattern analysis
and machine intelligence, 39(6):1137–1149, 2016. 8[41] Mark Sandler, Andrew Howard, Menglong Zhu, Andrey Zhmoginov, and Liang-Chieh Chen. Mobilenetv2: Inverted
residuals and linear bottlenecks. In Proceedings of theIEEE conference on computer vision and pattern recognition, pages 4510–4520, 2018. 8[42] Ali H Sayed. Adaptation, learning, and optimization over
networks. Foundations and Trends in Machine Learning,
7(ARTICLE):311–801, 2014. 2, 4, 33[43] Othmane Sebbouh, Robert M Gower, and Aaron Defazio. On
the convergence of the stochastic heavy ball method. arXiv
preprint:2006.07867, 2020. 2[44] Navjot Singh, Deepesh Data, Jemin George, and Suhas Diggavi. Squarm-sgd: Communication-efficient momentum sgd
for decentralized optimization. arXiv preprint:2005.07041,
2020. 1, 2, 3, 6, 7
[45] Sebastian Urban Stich. Local sgd converges fast and communicates little. In International Conference on Learning
Representations (ICLR), 2019. 2[46] Mingxing Tan and Quoc Le. Efficientnet: Rethinking model
scaling for convolutional neural networks. In International
Conference on Machine Learning, pages 6105–6114. PMLR,
2019. 8[47] Hanlin Tang, Xiangru Lian, Ming Yan, Ce Zhang, and Ji Liu.
d2 : Decentralized training over decentralized data. In International Conference on Machine Learning, pages 4848–
4856, 2018. 1, 2, 3, 7
[48] Hanlin Tang, Chen Yu, Xiangru Lian, Tong Zhang, and Ji
Liu. Doublesqueeze: Parallel stochastic gradient descentwith double-pass error-compensated compression. In International Conference on Machine Learning, pages 6155–
6165. PMLR, 2019. 2[49] John Tsitsiklis, Dimitri Bertsekas, and Michael Athans. Distributed asynchronous deterministic and stochastic gradient
optimization algorithms. IEEE transactions on automatic
control, 31(9):803–812, 1986. 2[50] 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. 7[51] Ran Xin, Usman A Khan, and Soummya Kar. An improved
convergence analysis for decentralized online stochastic nonconvex optimization. arXiv preprint:2008.04195, 2020. 2, 3[52] Yang You, Igor Gitman, and Boris Ginsburg.
Largebatch training of convolutional networks.
arXiv
preprint:1708.03888, 2017. 1, 2, 7
[53] Yang You, Jonathan Hseu, Chris Ying, James Demmel, Kurt
Keutzer, and Cho-Jui Hsieh. Large-batch training for lstm
and beyond. In Proceedings of the International Conference
for High Performance Computing, Networking, Storage andAnalysis, pages 1–16, 2019. 2, 7
[54] Yang You, Jing Li, Sashank Reddi, Jonathan Hseu, Sanjiv
Kumar, Srinadh Bhojanapalli, Xiaodan Song, James Demmel, Kurt Keutzer, and Cho-Jui Hsieh. Large batch optimization for deep learning: Training bert in 76 minutes. arXiv
preprint:1904.00962, 2019. 1[55] Yang You, Zhao Zhang, Cho-Jui Hsieh, James Demmel, andKurt Keutzer. Imagenet training in minutes. In Proceedingsof the 47th International Conference on Parallel Processing,pages 1–10, 2018. 1[56] Hao Yu, Rong Jin, and Sen Yang. On the linear speedup
analysis of communication efficient momentum sgd for distributed non-convex optimization. In International Confer-3038

ence on Machine Learning, pages 7184–7193. PMLR, 2019.
1, 2, 3, 6, 7, 18[57] 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. 2, 3, 13[58] Kun Yuan, Yiming Chen, Xinmeng Huang, Yingya Zhang,
Pan Pan, Yinghui Xu, and Wotao Yin. Decentlam: Decentralized momentum sgd for large-batch deep training (longreport). arXiv preprint:2104.11981, 2021. 6, 7
[59] Kun Yuan, Qing Ling, and Wotao Yin. On the convergenceof decentralized gradient descent. SIAM Journal on Optimization, 26(3):1835–1854, 2016. 2[60] Kun Yuan, Bicheng Ying, and Ali H Sayed. On the influenceof momentum acceleration on online learning. The Journalof Machine Learning Research, 17(1):6602–6667, 2016. 2

3039