{'fraction_non_alphanumeric': 0.048005961681771195, 'fraction_numerical': 0.018774489771388736, 'mean_word_length': 4.447878470403353, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 6, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 9, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
DecentLaM: Decentralized Momentum SGD for Large-batch Deep Training

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 across all 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 the inconsistency bias in DmSGD. Such bias becomes more evident as batch-size grows large and hence results in severe performance degradation. We next propose DecentLaM, a novel decentralized large-batch momentum SGD to remove the momentum-incurred bias. The convergence rate for both non-convex and strongly-convex scenarios is established. Our theoretical results justify the superiority of DecentLaM to DmSGD especially in the large-batch scenario. Experimental results on a variety of computer vision tasks and models demonstrate that DecentLaM promises both efficient and high-quality training.


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) [22] or the All-Reduce communication primitive [37]. Such global synchronization across all nodes either incurs significant bandwidth cost or high latency that can severely hamper the training scalability.
Decentralized SGD [35, 6, 24, 25, 3] 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 to compute the average of the nodes in its neighborhood, see Fig. 1. If a sparse topology such as one-peer exponential graph [3] is utilized to connect all nodes, each node only communicates with one neighbor each iteration and hence saves remarkable communications. Decentralized SGD can typically achieve 1.3 ∼ 2× training time speedup without performance degradation [24, 3,21]. Existing Decentralized SGD methods [24,25,46,26,3] and their momentum accelerated variants [55,43,13,4] primarily utilize small-batch in their algorithm design. However, recent hardware advances make it feasible to store 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 [15, 51, 53] find large-batch can significantly speed up Parallel SGD. First, the computation of a large-batch gradient can fully utilize the computational resources (e.g., the computing nodes, the CUDA cores and GPU memories within each node). 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) [ This naturally motivates us to study how Decentralized momentum SGD (DmSGD) performs with large batch-size.
To this end, we compared PmSGD and DmSGD over  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 with small 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 performance degradation in the large-batch scenario? • Is there a way to enhance the accuracy performance of large-batch DmSGD so that it can match with or even beat large-batch PmSGD? This paper focuses on these questions and provides affirmative answers. In particular, our main contributions are: • We find large-batch DmSGD has severe performance degradation compared to large-batch PmSGD and have clarified the reason behind this phenomenon. It is discovered that the momentum term can significantly amplify the inconsistency bias in DmSGD. When batchsize is large and the gradient 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 both non-convex and strongly-convex scenarios. Our theoretical results show that DecentLaM has superior performance to existing decentralized momentum methods, and such superiority gets more evident as batch size gets larger. • Experimental results on a variety of computer vision tasks and models show that DecentLaM outperforms various existing baselines such as DmSGD, DA/AWC/D 2 -DmSGD, SlowMo, PmSGD, and PmSGD+LARS in terms of the training 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, respectively.

Related Works
Decentralized deep training. Decentralized optimization can be tracked back to [48]. Decentralized gradient descent [35,57], diffusion [6,41] and dual averaging [11] are among the first decentralized algorithms that target on general optimization problems arise from signal processing and control communities. In the context of deep learning, Decentralized SGD (DSGD) has gained a lot of attentions recently. DSGD will incur model inconsistency among computing nodes. However, it is established in [24] that DSGD can reach the same linear speedup as vanilla Parallel SGD in terms of convergence rate. After that, [3] comes out to extend DSGD to directed topologies. A recent work [19] proposes a unified framework to analyze DSGD with changing topologies and local updates. [25,34] extend DSGD to the asynchronous setting. Various communication-efficient techniques can be further integrated into DSGD such as periodic updates [44,19,55], communication compression [2,5,20,18,47], and lazy communication [8,31].
Momentum SGD training. Momentum SGD have been extensively studied due to their empirical success in deep learning. The works [32, 58, 14, 30, 55] establish that momentum SGD converges at least as fast as SGD. Momentum SGD for overparameterized models are shown to converge faster than SGD asymptotically [42]. The exploration in decentralized momentum SGD (DmSGD) is relatively limited. [3] 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 extended by [43,13] to involve communication quantization and periodic local updates. Another work (Doubly-averaging DmSGD, or DA-DmSGD) [55] imposes an additional partial averaging over momentum to increase stability.
[49] proposes a slow momentum (SlowMo) framework, where each node periodically synchronize and perform a momentum update. [4] proposes a new variant in which the partial-averaging step is mixed up with the local momentum SGD update. All these decentralize momentum methods were studied and tested 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 [17,38] adjust the learning rate based on the gradient variance, and [15] utilizes learning rate warm-up and linear scaling to boost the performance in large-batch scenario. The layer-wise adap-tive rate scaling [51,52] can reduce the training time of Resnet-50 and BERT from days to hours. However, the study of large-batch training in decentralized algorithms is quite limited. This paper does not focus on the adaptive rate strategy for decentralized algorithms. Instead, we target on clarifying why existing momentum methods result in an intrinsic convergence bias, and how to update momentum properly to remove such bias and hence improve the performance in the large-batch scenario. Decentralized methods on heterogeneous data. Decentralized large-batch training within data-centers shares the same essence with decentralized training on heterogeneous data for EdgeAI applications. In large-batch training, the stochastic bias caused by gradient noise gets significantly reduced and the inconsistency bias caused by data heterogeneity will become dominant. [46,33,56,50] proposed decentralized stochastic primal-dual algorithms to remedy the influence of data heterogeneity. However, none of these algorithms, due to their difficulty to be integrated with momentum acceleration, show strong effective empirical performances in commenly-used deep learning models such as ResNet-50 or EfficientNet. A concurrent work [26] proposes Quasi-Global momentum (QG-DmSGD), 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 where inconsistency bias resulted from heterogeneous data dominates.

Decentralized Momentum SGD
Problem. Suppose n computing nodes collaborate to solve the distributed optimization problem: where f i (x) is local to node i, and random variable ξ i denotes the local data that follows distribution D i . Each node 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 ∈ R d be a vector with each element being 1. We let λ i (A) denote the i-th largest eigenvalue of matrix A.
Network topology and weights. Decentralized methods are based on partial averaging within neighborhood that is defined by the network topology. We assume all computing nodes are connected by an undirected network topology. Such connected topology can be of any shape, but its degree and connectivity will affect the communication efficiency and convergence rate of the decentralized algorithm. For a given topology, we define w ij , the weight to scale in- 2 ) j partial average formation flowing from node j to node i, as follows: We further define N i := {j|w ij > 0} as the set of neighbors of node i which also includes node i itself. We define weight matrix W := [w ij ] n i,j=1 ∈ R n×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. Partial averaging. With weights {w ij } and the set of neighbors N i , the neighborhood partial averaging operation of node i can be expressed as Partial averaging: 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 {w ij }, each node i in DSGD will iterate in parallel as follows: is the realization of ξ i at iteration k, and γ is the learning rate. When the network topology is fully connected and w ij = 1/n, DSGD will reduce to the Parallel SGD algorithm.
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: is independent of each other for any k and i. We also assume each stochastic gradient is unbiased and has bounded variance, i.e., E[∇F (x; The network topology is strongly connected, and the weight matrix is symmetric and satisfies W 1 = 1. 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 [41,  Table 1 shows that large-batch DmSGD has severe performance degradation compared to PmSGD in the largebatch scenario. This section targets to explore the reason behind this phenomenon. To highlight the insight, we assume each f i (x) to be strongly convex in this section, and x to be the global solution to problem (1). We let matrix x = [x 1 , · · · , x n ] T ∈ R n×d to stack all local models across the network, and matrix ∇f (x) = [∇f (x 1 ), · · · , ∇f (x n )] T ∈ R n×d to stack all local (accurate) gradients. Limiting bias of decentralized methods. The convergence of decentralized methods such as DSGD and DmSGD will suffer from two sources of bias:

DmSGD Incurs Severe Inconsistency Bias
• Stochastic bias is caused by 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., 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 is utilized, 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.
To this end, we let g i ) be the full-batch gradient. Note that both model x i and gradient g i 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 write DmSGD (see Appendix B.1) into: 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 linear regression problem confirms such conclusion. It is observed in Fig. 2 that DmSGD converges faster but suffers from a larger bias than DSGD. DmSGD's inconsistency bias: magnitude. The following proposition quantitatively evaluates the magnitude of DmSGD's inconsistency bias. We let ρ = max{|λ 2 (W )|, |λ n (W )|}, which characterize how well the network is connected. Since W is doubly stochastic (Assumption A.3), it holds that ρ ∈ (0, 1) (see Appendix A). A well connected network will have ρ → 0.
is further assumed to be strongly-convex, and the full-batch gradient ∇f i (x) is accessed per iteration, then DmSGD (6) has the following inconsistency bias: 2 denotes the data inconsistency between nodes, and β is the momentum coefficient. (Proof is in Appendix C.2) Note that we do not take expectation over (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 b 2 /(1 − ρ) 2 ). Comparing it with (7), it is observed that the momentum term in DmSGD is essentially amplifying the inconsistency bias by a margin of 1/(1 − β) 2 . This can explain why DmSGD converges less accurate than DSGD as illustrated in Fig. 2. Noting that β is typically set close to 1 in practice, DmSGD can suffer from a significantly large inconsistency bias. Since inconsistency bias dominates the large-batch scenario (see Proposition 1), DmSGD is thus observed to have severely deteriorated performance as illustrated in Table 1.

Improving Inconsistency Bias: DecentLaM
To improve large-batch DmSGD's accuracy, we have to reduce the influence of momentum on inconsistency bias. DSGD interprets as standard SGD. Without loss of generality, we assume each node i can access the accurate gradient ∇f i (x) in DSGD recursions (4)- (5). In this scenario, DSGD can be rewritten into a compact form: To simplify the derivation, we assume the weight matrix W , in addition to satisfying Assumption A.3, is positive-definite. With this assumption, W can be eigendecomposed into W = U ΛU T where U is an orthogonal matrix and Λ is a positive definite matrix. We define W In other words, DSGD (8) (with constant γ) can be interpreted as a standard SGD (9) (in terms of s) to solve: and x (k) can be achieved by x (k) = W 1 2 s (k) per iteration. When recursion (9) approaches the solution s o to problem (10), DSGD (8) will achieve the fixed point The inconsistency bias of DSGD is essentially the distance between x o and x = [x , · · · , x ] ∈ R n×d where x is the global solution to problem (1). Since x o = x , such inconsistency bias generally exists in DSGD.  s be the standard gradient of problem (10) at iteration k, the standard momentum SGD approach to solving problem (10) is After achieving s (k+1) , we get x (k+1) = W 1 2 s (k+1) . Recursions (11)-(13) are named as DecentLaM, and we simulate their convergence behaviour under the same setting as in Fig. 2. It is observed in Fig. 3 that the proposed algorithm converges as fast as DmSGD but to a more accurate solution. Since DecentLaM is with an improved inconsistency bias, it better fits into the large-batch scenario. Efficient implementation. To apply DecentLaM (11)- (13) to train deep neural networks, we need two additional modifications: (i) the full-batch gradient ∇f i (x) needs to be replaced with the stochastic gradient ∇F (x; ξ i ); (ii) the matrix W 1 2 should be removed from the algorithm update. To this end, by letting g = W 1 2 g s , m = W 1 2 m s , andg be the stochastic version of g, (11)-(13) can be rewritten as where we have replaced ∇f (x (k) ) with ∇F (x (k) ; ξ (k) ) in (14) to enable the usage of stochastic gradient. The above algorithm is almost the same as the vanilla momentum SGD within a single computing node, with the exception to construct g (k) as in (14). The decentralized implementation of (14)-(16) is listed in Algorithm 2, wherẽ 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 dashed part, which is different from the DmSGD workflow, enables an efficient wait-free backpropagation (WFBP) implementation that can overlap communication and computation. 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 has an inconsistency bias as follows: Remark 2. Comparing with DmSGD's inconsistency bias (7), it is observed that DecentLaM completely removes the negative effects of momentum; it improves DmSGD's inconsistency bias by a margin of 1/(1 − β) 2 . When b 2 is large or β is close to 1, such improvement is remarkable.

Remark 3. Comparing with DSGD's inconsistency bias
, it is observed that DecentLaM has exactly the same 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 2-3.

Convergence analysis of DecentLaM
Sec. 5 proposes a novel algorithm DecentLaM and explains why it better fits into the large-batch scenario. This section establishes the formal convergence analysis in the non-convex and strongly-convex scenarios, respectively.

Non-convex scenario
We introduce a standard data inconsistency assumption for the non-convex scenario: Assumption A.4 There exits a constantb > 0 such that is the global cost function defined in (1). Assumption A.4 is much more relaxed than the commonly used assumption that each ∇f i (x) is upper bounded (i.e., ∇f i (x) ≤ M ) [13,43,4]. When data distribution D i in each computing node i is identical to each other, it holds that f i (x) = f j (x) for any i and j, which impliesb = 0.
positive-definite, and β + (1−β)(1−ρ) 2 ≤ 3+ρ 4 , the De-centLaM algorithm in Algorithm 2 will converge as follows (Proof is in Appendix E, andx (k) = 1 Expression (19) indicates that DecentLaM will converge sublinearly to a limiting bias. The limiting bias (which can be achieved by letting T → ∞) can be separated into the stochastic bias and the inconsistency bias, which is consistent with our discussion in Sec. 4. It is also observed that the inconsistency bias term in (19) is unrelated to the momentum coefficient β, which implies, as discussed in Sec. 5, that DecentLaM has removed the negative affects of momentum. Theorem 1 has restrictions on the positive-definiteness of W and the momentum parameter β so that the analysis can be simplified. However, they are not needed in the real practice and not used in any of our experiments in Sec. 7. We find the concurrent work [26] also imposes a restriction on momentum parameter to simply the analysis.

Strongly-convex scenario
Under Assumption A.5, the global solution to problem (1) is unique. Furthermore, we do need to make the data heterogeneity assumption A.4 in the strongly-convex scenario. Instead, we will use b 2 = 1 n n i=1 ∇f i (x ) 2 to gauge the data heterogeneity where h k is some positive weight (see Appendix F) and The inconsistency bias in (20) is independent of the momentum β, which is consistent with Proposition 3 . It implies that DecentLaM achieves the same O(γ 2 b 2 /(1 − ρ) 2 ) inconsistency bias as DSGD (see (38)).
Theorem 2 establishes the convergence of DecentLaM with a constant learning rate. When learning rate is decaying, DecentLaM converges exactly to the global solution: ), DecentLaM will converge as follows (Proof is in Appendix F): whereÕ(·) hides all logarithm factors.
Corollary 2 implies that DecentLaM achieves the same linear speedup as PmSGD in the strongly-convex scenario [30]. However, it saves more communication per iteration due to the partial averaging (see Sec. 3).

Comparison with existing methods
As we discussed in Sec. 4, the inconsistency bias will dominate the convergence performance as batch-size gets large. For this reason, we list the inconsistency bias comparison between DecentLaM and existing DmSGD variants in Table 2. By removing the influence of momentum, De-centLaM has the smallest inconsistency bias. This implies DecentLaM can perform better in the large-batch scenario.

Strongly-convex Non-convex
DmSGD (eq. (7)) After completing this work, we become aware of the concurrent work QG-DmSGD [26] that can also achieve O(γ 2b2 ) 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 Decent-LaM. Furthermore, QG-DmSGD is designed for highly data-heterogeneous scenario in EdgeAI applications while DecentLaM is for large-batch training within data-centers. As a result, our experimental tasks and algorithm settings are very different. In addition, our analysis is also different from QG-DmSGD. With a delicately designed Lyapunov function, we can cover the convergence analysis for both non-convex and strongly-convex scenarios. In contrast, the analysis in QG-DmSGD is for the non-convex scenario. Finally, we theoretically uncovered the reason why traditional DmSGD [55, 13, 43] has degraded performance in Sec. 4 while QG-DmSGD only justifies it empirically.

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   [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 computation and 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 a common 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 all decentralized training and changed the batch size of every single GPU respectively.

Image Classification
Implementation. We conduct a series of image classification experiments with the ImageNet-1K [10] dataset, which consists of 1,281,167 training images and 50,000 validation images in 1000 classes. We train classification models with different batch sizes to verify our theoretical findings. As suggested in [15], we treat batch size equal or less than 8k as small-batch setting and the training protocol in [15] is used. In details, we train total 90 epochs. The learning rate is warmed up in the first 5 epochs and is decayed by a factor of 10 at 30, 60 and 80 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 and is decayed in a cosine annealing scheduler as suggested in [ 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 as batch size grows. DecentLaM outperforms other baselines by a large margin in the 32K batch size scenario due to its improved inconsistency bias derived in Proposition 3, Theorems 2 and 1.
• DecentLaM even outperforms PmSGD and PmSGD + LARS for each batch-size. One conjecture is that its model inconsistency 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, DA/AWC-DmSGD, and SlowMo 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. D 2 -DmSGD's performance also drops significantly while it can theoretical remove all inconsistency bias. QG-DmSGD 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 in Fig. 5. When batch size is 2K, it is observed that Decent-LaM 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. Performance with different models. We now validate whether DecentLaM is effective to different neural network architectures. The accuracy of PmSGD is slightly different from those reported in [40, 45] because we do not utilize tricks such as AutoAugment [9] that are orthogonal to our methods. It is observed in Table 4 that either PmSGD + LARS or Decent-LaM achieves best performance with large batch-size (16K) across different models. However, DecentLaM has runtime speedup due to its efficient neighborhood-communication. For small-batch settings, DA-DmSGD and QG-DmSGD can also achieve the best accuracy for some models.
Performance with different topologies. We now examine how DecentLaM is robust to different topologies. To this end, we first organize all computing nodes into ring, mesh, symmetric exponential, or the bipartite random match topology, see Appendix G.3 for details of these topologies. Next we test the performance of DecentLaM on ResNet-50 with these topologies and the results are in Table 5. It is observed that DecentLaM has a consistent performance with different topologies. The ring topology is sparser than symmetric exponential topology. Interestly, it is observed to have a better accuracy in the 32K batchsize setting. It is conjectured that the ring topology can help escape from shallow local minimums when batch-size is large. We leave the justification as the future work.
Training time comparison. The end-to-end training speed varies across different models and network bandwidth conditions. For the sake of brevity, we compare the runtime of PmSGD, DmSGD and DecentLaM in training ResNet-50 (ImageNet) with different batch sizes and net-  work bandwidths. The speed-up of DmSGD/DecentLaM over PmSGD is consistent for other backbones and tasks. In Fig. 6, DecentLaM and DmSGD have equivalent runtime because they are based on the same partial averaging operation. However, they can achieve 1.2∼1.9×speed-up compared to PmSGD, which is consistent with [3].

Object Detection
We compared the aforementioned methods with wellknown detection models, e.g. Faster-RCNN [39] and Reti-naNet [28] on popular PASCAL VOC [12] and COCO [29] datasets. We adopt the MMDetection [7] framework as the building blocks and utilize ResNet-50 with FPN [27] as the backbone network. We choose mean Average Precision (mAP) as the evaluation metric for both datesets. We used 8 GPUs (which are connected by the symmetric exponential topology) and set the total batch size as 256 in all detection experiments. Table 6 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.

Conclusion
We investigated the performance degradation in largebatch DmSGD and proposed DecentLaM to remove the momentum-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.
Understanding the role of momentum in stochastic gradient methods. arXiv preprint arXiv:

A. Preliminary
Notation. We first introduce necessary notations as follows.
x is the global solution to problem (1).
• W = [w ij ] ∈ R n×n is the weight matrix.
• Given two matrices x, y ∈ R n×d , we define inner product x, y = tr(x T y), the Frobenius norm x 2 = x, x , and the x 2 as x's 2 norm. Furthermore, for a positive semi-definite matrix A ∈ R n×n , we define x, y A = tr(x T Ay) and x 2 A = x, x A for simplicity.
GmSGD in matrix notation. For ease of analysis, we rewrite the recursion of GmSGD in Algorithm 1 with matrix notation: DecentLaM in matrix notation. We can also rewrite DecentLaM in Algorithm 2 with matrix notation: is also L-smooth. As a result, the following inequality holds for any x, y ∈ R d : Network weight matrix. Suppose a symmetric matrix W ∈ R n×n satisfies Assumption A.3, and λ j denotes its j-th largest eigenvalue. It holds that 1 = λ 1 > λ 2 ≥ · · · ≥ λ n > −1. As a result, it holds that W 2 = 1, and ρ = W − 1 n 11 T 2 = max{|λ 2 |, |λ n |} ∈ (0, 1) If W satisfying Assumption A.3 is further assumed to be positive-definite, it holds that 1 = λ 1 > λ 2 ≥ · · · ≥ λ n > 0. Submultiplicativity of the Frobenius norm. Given matrices W ∈ R n×n and y ∈ R n×d , it holds that To verify it, by letting y j be the j-th column of y, we have W y 2 = d j=1 W y j

B.1. Reformulation of DmSGD
In this section we show how DmSGD algorithm 1 can be rewritten as (6). To this end, we rewrite (23) as Subtracting (30) from (23), we have which is equivalent to When a full-batch gradient is used, the above recursion becomes which is essentially recursion (6) in the matrix notation.

B.2. Reformulation of DecentLaM
In this section we show another formulation of DecentLaM Algorithm 2. To this end, we rewrite (26) as Subtracting (34) from (26), we have which is equivalent to When a full-batch gradient is used, the above recursion becomes C. Limiting Bias of Decentralized Algorithms

C.1. Limiting bias of DSGD
In this section we illustrate the stochastic bias and inconsistency bias in the DSGD algorithm. It is established in [56] that DSGD in the strongly-convex scenario will converge as follows: where σ 2 is the variance of gradient noise, and b 2 is the data inconsistency (see the definition in Proposition 2). When learning rate is constant and iteration k goes to infinity, DSGD will converge with limiting bias. i.e., Limiting bias = lim sup As we discussed in Sec. 4, the limiting bias can be divided into two categories: stochastic bias and inconsistency bias. The stochastic bias is caused by the gradient noise. In the large-batch scenario in which the gradient noise σ 2 gets significantly reduced, the inconsistency bias will dominate the magnitude of DSGD's limiting bias.

C.2. Inconsistency bias of DmSGD (Proof of Proposition 2)
In this section we will prove Proposition 2. To achieve the inconsistency bias, we let x m be the fixed point of x (k) , i.e., x (k) → x m . From recursion (33), it is derived that x m satisfies Since W is symmetric and satisfies W 1 = 1 (see Assumption A.3), we can eigen-decompose it as where U is the orthonormal matrix, and Λ 1 = diag{λ 2 , · · · , λ n } is a diagonal matrix. With (42), we have where (a) and (d) hold because U is orthonormal, and (b) and (c) hold because (41) and (43), we have Left-multiplying 1 n 1 T to both sides of (40), we achieve 1 n 1 T ∇f (x m ) = 0. With this fact we have where (a) holds because 1 n n i=1 f i (x) is L-smooth and µ-strongly convex (see Assumptions A.1 and A.5). We thus have Proof of Proposition 2. Substituting (46) to (44), we achieve , the above inequality becomes With (46) and (48), we have where the last inequality holds because ρ = max{|λ 2 |, |λ n |}. Inequality (49) leads to This concludes the proof of Proposition 2.

C.3. Inconsistency bias of DecentLaM (Proof of Proposition 3)
We let x L be the fixed point of the DecentLaM iterate x (k) , i.e., x (k) → x L . From DecentLaM recursion (37), we have By following the arguments in (41)-(50), we can prove Proposition 3.

D. Fundamental Supporting Lemmas
In this section, we establish the key lemmas to facilitate the convergence analysis in Appendices E and F. This section assumes the weight matrix W to be positive-definite to simplify the derivations.
It is shown in Sec. 5 that DecentLaM can be interpreted as a standard momentum SGD algorithm to solve problem (10). This paper will conduct all analysis based on the recursions (11)- (13). To this end, we define ∇ s F(s; ξ) = W Comparing (11) We introduces (k) = [(s (k) ) T ; · · · ; (s (k) ) T ] ∈ R n×d andm

D.1. Supporting lemmas
In the following lemma, we bound the average of momentumm (k) . Under Assumption A.2, it holds for any random variable y ∈ R n×d that Proof. Since m (0) = 0, we have m Note that where (a) holds because of Assumption A.2 and (b) holds since On the other hand, we can verify for any random variable y that Combining inequalities (59) and (60), we achieve Recalling from (56) thats (k+1) −s (k) = − γ 1−βm (k+1) s , we can derive from Lemma 1 (by setting y = W 1 2 s (k−1) ) that Next we introduce an auxiliary sequencet (k) defined as The introduction oft (k) is inspired from [55]. It is delicately designed to enjoy the following property: Proof. We prove the lemma by direct calculation. When k = 1, where the last equality holds because of recursions (55)-(56). For k ≥ 1, we havē which completes the proof of (64). Moreover, it holds for k ≥ 1 that

D.2. Descent Lemma
The following lemma establishes how E[f (t (k) )] evolves with iteration k.

D.3. Consensus Lemma
It is observed that a consensus error term E s (k) −s (k) 2 exists in (123). In this subsection, we establish its upper bound.
Proof. Recall from (53) and (55) that By taking mean-square-expectation, it holds that where (a) holds by setting η = β.
With the help of Lemmas 4 and 5, we are ready to establish the bound for consensus error term E s (k+1) −s (k+1) 2 .

Lemma 6 (CONSENSUS LEMMA FOR NON-CONVEX SCENARIO). Under Assumptions
If we further take running average over both sides, it holds that Proof. For notation simplicity, we let From Lemmas 4 and 5, it holds that From the above two inequalities, we have (fro a positive constant a): where (a) holds when γ is sufficiently small such that 1 + 3ργ 2 L 2 ≤ 2 (which can be satisfied by setting γ ≤ 1 2 √ ρL ), and (b) holds when a = 1−ρ 16(1−β) . If β satisfies inequality (91) becomes If we keep iterating the above inequality, it holds that where the last equality holds because A (0) = 0 (by setting s (0) = 0) and B (0) = 0 (by settingm (0) s = 0). Since B (k) ≥ 0, we achieve the result in (87). If taking the running average of both sides of (87), we have which completes the proof.

D.3.2 Strongly-convex scenario
Under Assumption A.5, it holds that each function f i (x) is strongly convex. Let x be the unique global solution to problem (1). Since s = W it holds that where Proof. Since f (x) is convex, we have where (a) holds because each f i (·) is L-smooth so that and b 2 is defined as and (c) holds because each f i is convex and L-smooth. With inequality (99), we follow arguments (78)-(94) to achieve Now we introduce weights h k and take the weighted average of both sides in the above inequality to achieve where (a) holds because C =

E. Convergence Analysis for Non-convex Scenario
Inspired by [30], we consider the following Lyapunov function . Proof. Following (123) and the definition of L in (104), we reach where (a) holds because E 1 To bound the last term in the above inequality, we have where (a) holds because we define Substituting (107) and (108) into (106), and supposing γ is sufficiently small such that we achieve Now we decide the values of {c i } to let the last two terms in the above inequality be negative. To this end, it suffices to let Since 1 − β k+1 < 1, it suffices to let so that inequality (112) holds. With recursion (113), we have which indeed yields and c 0 is positive as long as γ < In other words, when γ ≤ (1−β) 2 , there exists a positive sequence {c i } ∞ i=0 such that the last two terms in (111) are non-positive. Substituting (116) into (111) and choosing γ ≤ (1−β) 2 12Lβ 2 , we have Substituting the above relations into (111), we achieve the result in (105). Finally, to guarantee (110), it suffices to let γ ≤ (1−β) 2 (5−β+2β 2 )L .
G. More Experimental Details G.1. Experimental setting for Table 1 Cifar-10 dataset contains 50,000 training samples and 10,000 validating samples. We follow the SOTA training scheme and train totally 200 epochs. The learning rate is linearly scaled and gradually warmed up form a relatively small value (e.g. 0.1) in the first 5 epochs. We decay the learning rate by a factor of 10 at 100, 150 epochs. To eliminate the effect of topology with different size in decentralized algorithms, we used 8 workers (i.e. 8 GPUs) in all decentralized training and changed the batch size of every single GPU respectively. For ImageNet experiments, the training setting is introduced in Sec. 7 in details.

G.2. Experimental setting for linear regression (i.e., Figs. 2 and 3)
In this experiment, we consider a linear regression problem: In the above problem, we set n = 8 and all computing nodes are organized into the mesh topolology, see Fig. 7. The weight matrix is generated from the Metropolis-Hastings rule [41, Table 14.1] so that it satisfies Assumption A.3. Quantities A i ∈ R 50×30 and b i ∈ R 50 are local data held in node i. Each A i is generated from the standard Gaussian distribution N (0, 1), and b i = A x x o + s in which x o ∈ R 30 is a predefined solution, and s is a white noise with magnitude 0.01. For DSGD, DmSGD, and DecentLaM, we set learning rate γ = 0.001 and β = 0.8. To evaluate the inconsistency bias, we let each node i access the accurate gradient ∇f i (x) = A T i (A i x − b i ) rather than the stochastic gradient descent. The y-axis indicates the relative error 1 n n i=1 x (k) i − x 2 / x 2 in which x is the optimal solution to problem (159). Table 5 We empirically investigate a series of undirected deterministic and time-varying topologies. We generate the weight matrix W according to the Metropolis-Hastings rule [41, Table 14.1] so that it is satisfies Assumption A.3. A positive-definite W is not required in any of our experiments. We organize all computing nodes into the following topologies with BlueFog [1].

G.3. Network topologes used in
• Ring. All nodes forms a logical ring topology. Every node communicate with its direct neighbors (i.e. 2 peers).
• Mesh. All nodes forms a logical mesh topology. Every node communicate with its direct neighbors. It is a multi-peer topology. • Symmetric Exponential Graph [1,3]. The node with odd rank i communicates with even ranks i + 2 0 − 1, i + 2 1 − 1, ..., i + 2 log 2 (n−1) by sending a message and waiting for a response.
• Bipartite Random Match. All nodes are evenly divided into two non-overlapping groups randomly per iteration. Communication is only allowed within each pair of the nodes. We keep the same random seed in all nodes to avoid deadlocks.
We also visually illustrate the aforementioned topologies with 8 nodes in Fig. 7.