From Promise to Practice: Realizing High-performance Decentralized Training

## Abstract

Abstract Decentralized training of deep neural networks has attracted significant attention for its theoretically superior scalability over synchronous data-parallel methods like All-Reduce. However, realizing this potential in multi-node training is challenging due to the complex design space that involves communication topologies, computation patterns, and optimization algorithms. This paper identifies three key factors that can lead to speedups over All-Reduce training and constructs a runtime model to determine when, how, and to what degree decentralization can yield shorter per-iteration runtimes. Furthermore, to support the decentralized training of transformer-based models, we study a decentralized Adam algorithm that allows for overlapping communications and computations, prove its convergence, and propose an accumulation technique to mitigate the high variance caused by small local batch sizes. We deploy the proposed approach in clusters with up to 64 GPUs and demonstrate its practicality and advantages in both runtime and generalization performance under a fixed iteration budget.

## 1 Introduction

With the rapid advancement of deep neural networks (DNNs), distributed training has become the mainstream approach for efficiently scaling up models. Among the various parallelization strategies, data parallelism has emerged as the most straightforward and commonly used approach for distributing training across multiple devices. One of the most popular algorithms used in data-parallel training is All-Reduce (Li et al., ), known for its simplicity and its ability to maintain consistency with single-machine training.

However, All-Reduce training relies on high-speed network connections and homogeneous computational devices to ensure its efficiency (Zhang et al., , Tandon et al., ). Large companies with abundant resources address these challenges by investing in specialized high-performance computing (HPC) clusters optimized for large-scale distributed training (Shoeybi et al., ). These clusters are equipped with cutting-edge uniform hardware and high-speed interconnects, making them ideal for All-Reduce-based training. Unfortunately, such resources are often inaccessible to the broader research community. Most researchers rely on self-built servers or shared clusters by universities or cloud service providers, which may lack the high-speed networking infrastructure necessary to fully leverage All-Reduce, thereby limiting the potential of the available computational resources.

Decentralized algorithms, which originally gained attention in the fields of consensus algorithms (Johansson et al., , Shi et al., ) and privacy-preserving techniques (Yan et al., ), have recently been explored as alternatives to All-Reduce in distributed training, especially in environments with suboptimal network conditions. By replacing the costly All-Reduce operations with decentralized communication patterns, these algorithms can significantly reduce communication overhead. Over the past few years, decentralized algorithms have demonstrated promising practical speedup in setups with poor network performance (Lian et al., , Assran et al., , Yuan et al., ). Research in this area has focused on the convergence properties of gossiping on different communication topologies (Ying et al., , Takezawa et al., ), decentralized optimization algorithms (Lin et al., , Yuan et al., ), and alternative communication patterns (Cattivelli & Sayed, ). Despite this growing interest, decentralized approaches have yet to achieve the same level of popularity as All-Reduce-based methods in distributed training.

We believe there are several reasons for this: (1) Simply combining the best of each line of work does not necessarily lead to an effective overall system. The potential speedup of decentralized algorithms in real-world environments remains underexplored and poorly understood (Assran et al., ). (2) The generalization performance of models trained with decentralized methods often falls short compared to those trained with All-Reduce under the same iteration budget, raising concerns about the effectiveness of decentralized training (Lian et al., , Assran et al., ). (3)
Despite the growing interest in large language models (LLMs), there is still no well-suited decentralized version of the Adam optimizer, which is crucial for efficiently training transformer-based models in a decentralized setting.

This paper aims to develop a deeper understanding of decentralized training in practical setups and includes the following key contributions:

- 1.
We propose a simple yet accurate runtime model that quantifies key environmental parameters and estimates potential speedups. This model is designed to optimize decentralized training configurations to achieve the best performance in different settings.
- 2.
We design and analyze a decentralized variant of the Adam optimizer. Our algorithm leverages a collective gossip communication mechanism, enabling parallelism between computation and communication. In addition, it introduces a novel accumulation technique that enhances performance and delivers promising experimental results.
- 3.
We implement a PyTorch extension for decentralized training across multiple GPUs and nodes. Our implementation demonstrates strong performance on typical machine learning workloads, including image classification, machine translation, and GPT-2 pre-training. Extensive experiments highlight the empirical evidence of the feasibility and practical benefits of decentralized training.

### 1.1 Related Work

##### Decentralized training

The combination of SGD updates with gossip communication (Lin et al., , Yuan et al., ) has gained significant attention for its theoretical benefits: it retains the convergence rate as centralized/synchronous mini-batch SGD at a reduced communication cost. One line of work (Neglia et al., , Ying et al., , Takezawa et al., ) focuses on the design of the communication topology to improve the guaranteed convergence rate in terms of the number of iterations. However, these papers demonstrate improvements in terms of the number of iterations but do not show if these results translate into speedups in terms of total training time. A handful of more practical studies, *e.g.*, (Lian et al., , Assran et al., ) report actual speedups of decentralized training with multiple workers, but they do not isolate system-level bottlenecks or bound the potential speedups. Moreover, Lian et al. () focuses on low-bandwidth scenarios, and the implementation in Assran et al. () groups GPUs in a node as a single unit for decentralization, which can suffer from intra-node stragglers. Another line of work that is orthogonal to decentralized data parallelism is the slow momentum (Wang et al., , Lin et al., ), which maintains an outer-loop momentum to improve the training loss. However, the method introduces additional communication costs and parameters to tune.

##### Variance in computation time

In the training of language models, one way to preprocess the input data is to group samples with similar lengths (Vaswani et al., ), but this may introduce the straggler effect because non-uniform batches lead to an imbalanced workload. To solve this problem, one system-level way is to increase the number of local mini-batches to reduce the variance (Ott et al., ) or to drop samples on stragglers (Giladi et al., ), but this may worsen the generalization performance since it alters the effective global batch size (Keskar et al., ). To alleviate the straggler problem in pre-training LLMs, it is common to pack the sequences from different documents and insert a special token between them (Raffel et al., ) to create uniform batches. However, the sequence pack technique has a negative influence on the training quality (Ding et al., ). Another possibility is to simply pad sequences to a fixed length (Smith et al., ), but this leads to lower resource utilization in the training. Moreover, the methods are not compatible with other tasks like video processing and seq-to-seq tasks. As for the performance of the decentralized training on imbalanced workloads, in Assran et al. (), the authors argued that decentralized training is more resilient to computation time variance by showing a smaller runtime variance. However, they did not explore whether decentralized training can also gain a speedup advantage.

##### Orthogonal scalability techniques

There are many other ways to improve scalability that are orthogonal to this work. This includes compression of gradients (Vogels et al., ) and models (Tang et al., ) to reduce the communication time, as well as model parallelism (Xu & You, ) and pipeline parallelism (Li & Hoefler, ) to scale up distributed training. These approaches could potentially be combined with our work to improve its scalability further.

## 2 Important aspects of multi-node decentralized training

The basic idea behind many decentralized optimization algorithms is to replace the global model parameter $x\in\mathbb{R}^{\scriptscriptstyle D}$ by local copies $x_{i}\in\mathbb{R}^{\scriptscriptstyle D}$ at each worker $i=1,2,\dots,N$ and require that the local models reach consensus. In this spirit, a decentralized learning problem can be written as

$$ $\underset{\{x_{1},\ldots,x_{N}\}}{\mbox{minimize}}\quad\frac{1}{N}\sum\nolimits_{i=1}^{N}F_{i}(x_{i}),\quad\mbox{subject to}\;x_{i}=x_{j},\;\forall i,j,$ (1) $$

where $F_{i}(x_{i})$ is the expected training loss of the local model $x_{i}$ on the data held by worker $i$. In our theoretical analysis, we let $F_{i}(x)=\mathbb{E}_{\xi_{i}\sim\mathcal{D}}[\ell(x;\xi_{i})]$ where $\xi_{i}$ is a local data point of worker $i$ drawn from the distribution ${\mathcal{D}}$, and $\ell(\cdot)$ is a non-convex but smooth function. The assumption that each worker can draw samples from the same distribution $\mathcal{D}$ is reasonable if not for the privacy-preserving purpose (Ying et al., , Lian et al., ).

Decentralized algorithms for solving ([1](#S2.E1)) allow the local model $x_{i}$ to disagree during the training process but drive them towards the same stationary point of the global training loss. We focus on adaptive momentum versions of decentralized gradient descent,

$$ $\displaystyle x_{i}^{(t)}$ $\displaystyle\leftarrow-\alpha^{(t)}d_{i}^{(t)}+\sum\nolimits_{j\in\mathcal{N}_{i}^{(t)}}w_{ij}^{(t)}x_{j}^{(t-1)}.$ (2) $$

Here, $\alpha^{\scriptscriptstyle(t)}$ is the learning rate, $-d_{i}^{\scriptscriptstyle(t)}$ is an update direction that reduces the value of $F_{i}$ at $x_{i}^{\scriptscriptstyle(t-1)}$ and the final term accounts for the averaged model parameters of neighboring workers and drives the local parameters towards the same first-order stationary point. For decentralized SGD, $d_{i}^{\scriptscriptstyle(t)}=\nabla\ell(x_{i}^{\scriptscriptstyle(t-1)};\xi_{i}^{\scriptscriptstyle(t)})$ while the expression is more complex for the adaptive momentum variations that we develop in § [4](#S4). The weights $w_{ij}^{\scriptscriptstyle(t)}$
satisfy $w_{ij}^{\scriptscriptstyle(t)}>0$ if $i$ and $j$ communicate at iteration $t$ or $i=j$,
and 0 0 otherwise. We define
${\mathcal{N}}_{i}^{\scriptscriptstyle(t)}$ as the set of workers $j$ (including $i$ itself) such that
$w_{ij}^{\scriptscriptstyle(t)}>0$.
The weights are selected so that if $d_{i}^{\scriptscriptstyle(t)}=0$ for all $i$ and all $t$ in ([2](#S2.E2)), the local models will converge to the same value; see § [4](#S4) for details.

Next, we will describe three factors that are essential to consider in order to implement ([2](#S2.E2)) efficiently.

### 2.1 Exploiting overlapping communication and computation

Figure: Figure 1: Timelines and dependency relations of decentralized training. $F$: forward pass, $B$: backward pass, $C$: decentralized communication/aggregation of model parameters with other workers, $U$: update model parameters. An arrow from task $X$ to $Y$ means that task $Y$ can start only after $X$ finishes.

Modern accelerators like Nvidia GPUs are capable of interleaving communications with computations. After deciding which training scheme to use, hiding communication by computation is one of the key optimizations in the design of an efficient distributed training system. For the decentralized implementation of ([2](#S2.E2)), a general idea of achieving it is to restrict the search direction $d_{i}$ to only depend on the local model. While for DNN training, we can take this idea further.

Inspired by the gradient bucketing technique used in data-parallel training in PyTorch (Li et al., ), we divide both gradients and models into buckets corresponding to specific layers or groups of layers. Due to the sequential nature of backpropagation, we can begin communicating the gradients of earlier finished layers while the gradients of later layers are still being computed. As illustrated in Figure [1](#S2.F1), we split the execution of the backward pass into buckets and interleave the corresponding local model updates. After updating a bucket, the corresponding communication can be initiated, and its results are not needed by the worker and its neighbors until the same bucket requires updating in the next iteration. This significant overlap is possible because we have made the decentralized update independent of neighbor information within the same iteration. For All-Reduce training(^1^11We provided the pseudocode of the distributed algorithm using All-Reduce in Appendix [A.1](#A1.SS1) and its timeline in Appendix [9](#A1.F9). All-Reduce is also considered in our experiments for comparison.), which aggregates gradients instead of models, communication cannot overlap with the forward pass and the backward pass of the last bucket. This is because the forward pass needs the complete aggregation of gradients from the last iteration, and no gradient is available before the backward pass of the last bucket. This indicates that decentralized training, using the scheme described in equation [2](#S2.E2), can utilize simultaneous computational resources more efficiently.

Making the update direction calculation independent of the local models at other workers in the same iteration is essential for overlapping computations and communications. Updates on the form
$x_{i}^{\scriptscriptstyle(t)}\leftarrow\sum_{j\in\mathcal{N}_{i}^{\scriptscriptstyle(t)}}w^{\scriptscriptstyle(t)}_{ij}(x_{j}^{\scriptscriptstyle(t-1)}-{\alpha}^{\scriptscriptstyle(t)}d_{j}^{\scriptscriptstyle(t)})$, as used in (Lin et al., , Gao & Huang, ), cannot easily achieve this; see Appendix [B.2](#A2.SS2.SSS0.Px1).

### 2.2 Respecting heterogeneous communication costs

A key advantage of well-designed decentralized training over All-Reduce training is the reduced communication cost due to the sparsity of gossip communication. Unlike All-Reduce, where all workers must participate in each iteration, decentralized training allows workers to communicate only with their immediate neighbors. A drawback with gossiping is that it only provides an approximate average that converges asymptotically to the true global average. Several studies have characterized how the convergence rate of gossiping, affecting both iteration complexity and generalization performance in decentralized training, is influenced by the communication topology (Xiao & Boyd, , Shi et al., , Nedić et al., , Ying et al., , Takezawa et al., ). In practical cluster environments, latency and bandwidth can vary significantly between nodes. While communication between GPUs within a single compute node is very fast, communication between nodes is slower and subject to congestion at switches and other network interfaces. Thus, when designing a communication topology for decentralized training in such environments, it is crucial to consider both the degree of connectivity, which affects the speed of information propagation, and the heterogeneity of networking connections, which impacts the execution time of each communication round.

**Table 1: Communication time of performing averaging operations for 8196 iterations over three 25MB FP32 tensors (selection of 25MB is based on the default bucket size used in PyTorch DDP (Li et al., )). Setup 1: 16 A100 GPUs on 4 nodes inter-connected by 100Gbps Infiniband. Setup 2: 16 A40 GPUs on 4 nodes inter-connected by 25Gbps Ethernet. Here, Complete means global averaging. All other topologies are illustrated in Appendix [A.4](#A1.SS4).**
| Setups \ Topology | Complete | One-peer Exp. | One-peer Ring | Alternating Exp Ring |
| --- | --- | --- | --- | --- |
| 4$\times$4$\times$A100, 100Gbps | 55.31 s | 55.44 s | 32.97 s | 29.55 s |
| 4$\times$4$\times$A40, 25Gbps | 395.99 s | 429.47 s | 217.90 s | 185.93 s |

Figure: Figure 2: Comparison of consensus errors by communication rounds with four 4-GPU nodes.
Refer to caption: /html/2410.11998/assets/x1.png

To demonstrate the practical impact of topology and heterogeneous connections on communication time, we set up an experiment with two scenarios: four nodes, each equipped with four Nvidia GPUs, are interconnected by either 25Gbps Ethernet or 100Gbps Infiniband, Table [1](#S2.T1) shows the communication time of performing averaging operations with different communication topologies. Even though the One-peer Exponential topology enjoys rapid convergence of consensus errors in terms of iterations, it requires more time than the Complete topology in this setup due to frequent inter-node communication. The One-peer Ring topology nearly halves the per-iteration communication time compared to the Complete topology. However, it exhibits a slower convergence rate of consensus errors than both the Complete and the One-peer Exponential topology in terms of communication rounds, which could potentially influence the theoretical generalization guarantees. However, experiments in (Kong et al., ) have shown that as long as the consensus error is below a certain value, it does not negatively affect performance. We have observed the same phenomenon in our practical deployments.

Unlike other implementations of decentralized training, such as those described in Assran et al. (), Lin et al. (), Ying et al. () which perform decentralized communication on the node level, we do not synchronize gradients within nodes. This implementation choice can provide significant resilience to variations in computation time, which will be discussed in § [2.3](#S2.SS3).

To adapt to the communication imbalance in the two clusters used in our experiments, we designed an Alternating Exponential Ring (AER) topology, see Figure [12](#A1.F12) in Appendix [A.4](#A1.SS4). The last column in Table [1](#S2.T1) and the comparison in Figure [2](#S2.F2) demonstrate that the proposed topology offers advantages in both communication time and convergence rate. Additionally, our numerical experiments in Section [5](#S5) demonstrate that it is able to strike a favourable balance between the connectivity of communication topologies and per-iteration runtime while maintaining comparable test accuracy.

It is important to note that the effectiveness of a specific topology may vary depending on the operational environment. By quantifying the communication costs associated with different connections and the congestion caused by concurrent communications, one can formulate an optimization problem that targets both the convergence rate and average runtime as objectives. We leave this as future work.

### 2.3 Reducing the sensitivity to varying computation times

The timeline in Figure [1](#S2.F1) shows a single worker and assumes that all other workers run their corresponding tasks in perfect synchrony. This is certainly not realistic. Even in homogeneous HPC environments, variable computation times appear due to system noise (Hoefler et al., ) and workload imbalance (Ott et al., ). Figure [4](#S2.F4) shows the distribution of actual gradient computation times for two different tasks. For image classification with ResNet-50 (He et al., ), even though all mini-batches are of identical size, the variance still exceeds $0.001$. For neural machine translation, the variance is much higher since mini-batches vary in size even if we batch together sequences with similar lengths (Vaswani et al., , Ott et al., ).

In All-Reduce training, workers have to wait for the slowest one, which makes the approach sensitive to workload variability. If the computation times of workers would be i.i.d. and follow a normal distribution, the expected value of the maximum of the $N$ computation times is asymptotically $\Theta(\sqrt{\log N})$ (Giladi et al., ). Hence, we can expect it to be less efficient as $N$ increases. For decentralized training, as shown in Appendix [A.5](#A1.SS5), it is still possible to hide some (and in some cases all) workload variability. Simulations of the runtimes of All-Reduce and decentralized training, shown in Figure [4](#S2.F4), confirm these predictions. The runtime for All-Reduce increases with $N$, while the runtime for decentralized training remains essentially constant.
This suggests that decentralized training could achieve better strong scaling efficiency (fixed global batch size).

In other decentralized frameworks like SGP (Assran et al., )(^2^22https://github.com/facebookresearch/stochastic_gradient_push), intra-node gradient synchronization is typically performed before the local update, and the parameter communication occurs at node level. However, this design becomes suboptimal in terms of runtime when the variance in computation time is non-negligible, since gradient synchronization is susceptible to intra-node stragglers. To better leverage the resilience of decentralized training to variations in computation time, we decouple the dependency of the local update on the gradient information of its neighbors within the same iteration. To demonstrate the benefits of the new design, we perform transformer experiments under heavy computation workloads (2$\times$4$\times$A100 and 100K tokens as global batch size) and fast network connections (NVLink within the node and 100Gbps Infiniband inter-connecting nodes) to make sure the network is not the bottleneck. The results show that removing the dependency decreases the per-iteration runtime by $10.95\%$ (from 225.09 ms to 200.43 ms). For more comparisons, see § [5.2](#S5.SS2).

Figure: Figure 3: Distributions of normalized computation times of ResNet-50 training for an image classification task and of transformer training for neural machine translation. The variances of the normalized computation time for the image task and the translation task are 0.0017 and 0.0134, respectively.
Refer to caption: /html/2410.11998/assets/x2.png

## 3 Runtime model and design insight

In this section, we propose a runtime model that characterizes how the per-iteration runtime depends on critical system parameters and workload characteristics. The model is simple yet surprisingly accurate when validated against experiments on real systems (see Appendix [A.5](#A1.SS5)), and helps to identify when and with what means we can obtain significant reductions in the per-iteration runtime.

The model considers neural network training in an environment with $N$ workers and assumes that the model parameters are organized into $b$ buckets. It uses the time that a single worker needs to process the forward pass with the global batch size as unit time. In this way, the forward pass of one worker takes $1/N$ time units while the backward pass is assumed to take $2/N$ time units. The time to update a bucket is $\theta$ time units. To characterize the system and the training workload, we introduce three additional parameters: (1) $\gamma\in(0,\infty)$ is the time taken for a global All-Reduce on one bucket; this parameter is large in systems with slow communication or many workers, (2) $\omega\in(0,1]$ is the ratio of the time taken by a decentralized communication round and a global All-Reduce. A small $\omega$ means a sparse decentralized communication topology, and (3) $\sigma^{2}$ is the variance of a truncated normal distribution that models the varying computation time. A large $\sigma^{2}$ means the computation time taken by the forward pass and backward pass may vary significantly. Based on the workload measurements in Figure [4](#S2.F4), we restrict the computation time between 0.5x and 1.5x of its average value.

The model is detailed in Appendix [A.5](#A1.SS5). In brief, it simulates randomly varying forward and backward pass calculation times and respects the dependency relationships between communication and update tasks described in Figure [1](#S2.F1) and Figure [13](#A1.F13).

Figure: Figure 5: Simulation by the runtime model. In the simulation, $N=8$ (8 workers), $b=4$ (4 buckets, from ResNet-50 experiments), $\theta=0.2$ (time taken by updating one bucket is 0.2 unit time), and the communication topology of decentralized training is complete topology(^4^44Here, our decentralized algorithm with a complete topology means $x_{i}^{\scriptscriptstyle(t)}=-\alpha^{\scriptscriptstyle(t)}d_{i}^{\scriptscriptstyle(t)}+\sum_{j\in[N]}w_{ij}x_{j}^{\scriptscriptstyle(t-1)}$ where $w_{ij}=1/N,\forall i,j$. Note that this still allows for overlapping communication and computation of the forward pass, while the All-Reduce algorithm in Appendix [A.1](#A1.SS1) cannot.).
Refer to caption: /html/2410.11998/assets/x4.png

Figure [4](#footnote4) shows some representative results generated by the runtime model. The leftmost figure illustrates how the per-iteration runtime of All-Reduce and decentralized training depends on $\gamma$ when $\omega=1$ and $\sigma^{2}=0$. For decentralized training, the communication time can be completely hidden by the corresponding forward, backward, and bucket update times, as long as the network is fast enough $(\gamma\leq(3+\theta)/N)$. After this point, the per-iteration time increases as $\Theta(b\gamma)$. In All-Reduce training, on the other hand, the last bucket can never be hidden and the per-iteration time increases also for small values of $\gamma$. More importantly, since the All-Reduce time of buckets can only be hidden by the corresponding backward pass, the more rapid increase in runtime starts already at $\gamma=2/N$.

Figure [4](#footnote4) (middle) shows the relative speedup of decentralized training over All-Reduce as a function of $\omega$ for different values of $\gamma N$. For $\omega=1$ and a fixed value of $\gamma N$, the speedup is just the ratio of the two curves shown in the leftmost figure. Decreasing $\omega$ reduces the time for a bucket communication in the decentralized setting, which effectively moves us to the left along the decentralized runtime graph. This leads to increasing speed-ups until $\omega\gamma=(3+\theta)/N$, after which no runtime improvements are obtained by decreasing $\omega$ further. This explains why no effect of $\omega$ is seen when $\gamma N\leq(3+\theta)$, and the speed-ups saturate below $\omega=(3+\theta)/\gamma N$. The model can also be used to estimate the best possible speedup. Specifically, when $\sigma^{2}=0$, we find

$$ $\text{best possible speedup}(\gamma)=\left\{\begin{array}[]{cc}1+\frac{1}{b}\cdot\frac{N\gamma}{3+\theta N}&\gamma\in(0,2/N],\\ 1+\frac{N\gamma-2+2/b}{3+\theta N}&\gamma\in(2/N,\infty).\\ \end{array}\right.$ (3) $$

As $N$ grows large, the second case suggests that the speedup tends towards $1+\gamma/\theta$. Since $\gamma$ increases with $N$, the model suggests that the speedups will increase in larger networks.

Figure [4](#footnote4) (right) shows the resilience of the computation time variance of decentralized training. The three combinations of $\gamma$ and $\omega$ represent the scenarios that (a) computation-bound ($\gamma=1/N$, $\omega=1$) (b) communication-bound ($\gamma=4/N$, $\omega=1$) (c) communication-bound and using a decentralized communication topology ($\gamma=4/N$, $\omega=0.6$). In the three scenarios, increasing $\sigma^{2}$ brings moderate improvement in the speedup of decentralized training.

As for the influence of communication topologies on runtime, they do influence runtime because of the changes in the dependencies of the operations, but the influences caused by adapting decentralized training and reduced communication cost by sparser topologies (see § [A.5.1](#A1.SS5.SSS1) in appendix).

In Figure [4](#S2.F4), we validate the accuracy of the runtime model by comparing the predictions with the actual runtime as $\gamma$ increases. The parameters $b=7$, $N=32$, $\theta=0.364$, $\sigma^{2}=6.95\times 10^{-3}$ measured from the profiling results are used for the predictions, and we manipulate the global batch size to mimic different values of $\gamma$. Given its simplicity, the model is surprisingly accurate.

## 4 Decentralized Adam and convergence

The per-iteration runtime that we have just studied is only part of the story. Equally important is the ability of the decentralized optimization algorithm to converge quickly and reliably toward a solution with good generalization properties. This section introduces a decentralized Adam algorithm (DAdam, described in Algorithm [1](#alg1)) that enables overlapping communications and computations and proves its convergence.
The notations are defined in Appendix [B.1.1](#A2.SS1.SSS1).

Figure: Algorithm 1 Decentralized Adam on worker $i$

Algorithm [1](#alg1) can be cast into the form of equation [2](#S2.E2) with a particular search direction. For simplicity, we use a static topology with mixing matrix $W$, i.e., $W^{(t)}=W$ for all $t$. In every iteration, each worker $i$ first draws a mini-batch from its local data and computes a local stochastic gradient $g_{i}$. Then, it proceeds similarly to the standard Adam scheme to update the local first- and second-order momentum $m_{i}$ and $v_{i}$, respectively. Subsequently, worker $i$ implements the mixing of neighbor models and uses the result to update the local model where $\alpha$ is a step-size and $\epsilon,\beta_{1},\beta_{2}$ are parameters. Note that $m_{i}$, $v_{i}$ and the resulting search direction do not depend on models $x_{j}$ of neighboring workers. Therefore, the algorithm supports overlapping communication and computations as discussed in Section [2.1](#S2.SS1). The comparison of Algorithm [1](#alg1) with other decentralized Adam-based methods is in Appendix [B.2](#A2.SS2.SSS0.Px2).

Next, we establish convergence of Algorithm [1](#alg1), based on the following Assumptions.

###### Assumption 1 .

For each worker $i$, the gradient $\nabla F_{i}$ is $L$-Lipschitz continuous:

$$ $\|\nabla F_{i}(x)-\nabla F_{i}(y)\|_{2}\leq L\|x-y\|_{2},~{}\forall x,y\in\mathbb{R}^{D}.$ $$

###### Assumption 2 .

There exists a constant $R\geq\sqrt{\epsilon}$ such that $\|\nabla\ell(x;\xi_{i})\|_{\infty}\leq R-\sqrt{\epsilon}$ almost surely.

###### Assumption 3 .

The mixing matrix $W=[w_{ij}]$ is symmetric, non-negative, and doubly stochastic. The eigenvalues of $W$ in order satisfies $1=\lambda_{1}>\lambda_{2}\geq\cdots\geq\lambda_{N}>-1$.

Assumptions [1](#Thmassumption1) and [2](#Thmassumption2) are used in Défossez et al. () to provide a simple analysis for centralized Adam.
Assumption [3](#Thmassumption3) is standard in decentralized learning and holds when the underlying communication topology is connected.
Under Assumption [3](#Thmassumption3), we denote
$\lambda=\max\{|\lambda_{2}|,|\lambda_{N}|\}\in[0,1)$.
Fix the number of iterations as $T$. We define ${\tau_{T}}$ as a random index from $\{0,\ldots,T-1\}$ with distribution

$$ $\forall\;\widetilde{t}<T,\ \ \ \mathbb{P}[~{}\tau=\widetilde{t}~{}]\propto 1-\beta_{1}^{T-\widetilde{t}},$ (4) $$

and denote $F(\bar{x}):=\frac{1}{N}\sum_{i=1}^{N}F_{i}(\bar{x})$ where $\bar{x}=\frac{1}{N}\sum_{i=1}^{N}x_{i}$. Then, we have the following theorem.

###### Theorem 4.1 .

Under Assumptions [1](#Thmassumption1)–[3](#Thmassumption3), if $0<\beta_{1}<\beta_{2}<1$, for Algorithm [1](#alg1), we have

$$ $\mathbb{E}\left[\left\|{\nabla F(\bar{x}^{(\tau)})}\right\|_{2}^{2}\right]\leq\frac{4R}{\alpha\tilde{T}}\left(F(\bar{x}^{(0)})-F_{*}\right)+E\left[\frac{1}{\tilde{T}}\ln\left(1+\frac{R}{\epsilon(1-\beta_{2})}\right)-\frac{T}{\tilde{T}}\ln(\beta_{2})\right],$ (5) $$

where $\bar{x}^{(t)}=\frac{1}{N}\sum_{i=1}^{N}x_{i}^{(t)}$, $\tau$ is defined in equation [4](#S4.E4), $\tilde{T}=T-\frac{\beta_{1}}{1-\beta_{1}}$, $F_{*}$ is the optimal value of equation [1](#S2.E1), and
$E=\frac{24DR^{2}\sqrt{1-\beta_{1}}}{\sqrt{1-\beta_{2}}(1-\beta_{1}/\beta_{2})^{3/2}}+\frac{2\alpha DLR(1-\beta_{1})}{(1-\beta_{2})(1-\beta_{1}/\beta_{2})}+\frac{4\alpha^{2}L^{2}D\beta_{1}}{(1-\beta_{1}/\beta_{2})(1-\beta_{2})^{3/2}}+\frac{8\alpha^{2}(1+\lambda^{2})RL^{2}D\sqrt{1-\beta_{1}}}{(1-\lambda^{2})^{2}(1-\beta_{2})(1-\beta_{1}/\beta_{2})\sqrt{\epsilon}}$.

We refer the readers to Appendix [B.4](#A2.SS4) for the proof. Compared to Défossez et al. (, Theorem 4) for the single-machine Adam, the error bound in Theorem [4.1](#S4.Thmtheorem1) only has one additional term – the last term in $E$ which is proportional to $\alpha^{2}$ and can be ignored for sufficiently small values of $\alpha$.

###### Assumption 1 .

###### Assumption 2 .

###### Assumption 3 .

###### Theorem 4.1 .

## 5 Numerical experiments

In this section, we compare decentralized training with All-Reduce training and assess the generalization performance and practical training-time speedups in cluster environments. We consider three large-scale tasks: neural machine translation, image classification, and GPT-2 pretraining. For neural machine translation, following Vaswani et al. (),
we trained the transformer ($\sim$65M parameters for base variant and $\sim$213M parameters for big variant) on the English-German and English-French WMT14 dataset (Bojar et al., ).
In each run, we evaluate the trained model by BLEU (Papineni et al., ) and METEOR (Banerjee & Lavie, ) on the test set. In the image classification task, we trained ResNet-50 (He et al., ) on ImageNet-1K (Deng et al., ). In each run, we evaluate the trained model by Top-1 and Top-5 accuracies on the validation set. For the GPT-2 pretraining task, we trained GPT-2 (small) (Radford et al., ) on OpenWebText Gokaslan et al. (), and we report the training and validation losses of the trained models.
The baseline, All-Reduce training, uses Adam-based optimizers for all experiments.
Detailed descriptions of all tasks and experimental setups can be found in Appendix [A.6](#A1.SS6).

### 5.1 Generalization performance

To make decentralized training useful, it should not compromise the generalization performance of the trained model. As shown in Tables [2](#S5.T2) and [3](#S5.T3), decentralized training can obtain a generalization performance that is comparable with All-Reduce training. In all experiments,
AccumAdam outperforms the others, while DAdam and All-Reduce perform similarly.

|  |  | BLEU $\uparrow$ / METEOR $\uparrow$ |  |
| --- | --- | --- | --- |
| Method | Topology | En-De / Transformer (base) | En-Fr / Transformer (big) |
| AllReduce | Complete | 27.79 ± 0.16 / 0.5465 ± 0.0018 | 45.70 ± 0.30 / 0.6676 ± 0.0017 |
| DAdam | AER | 27.58 ± 0.06 / 0.5440 ± 0.0013 | 45.60 ± 0.12 / 0.6664 ± 0.0014 |
|  | Complete | 27.60 ± 0.18 / 0.5445 ± 0.0021 | 45.65 ± 0.22 / 0.6670 ± 0.0017 |
| AccumAdam | AER | 27.71 ± 0.09 / 0.5481 ± 0.0027 | 46.05 ± 0.03 / 0.6715 ± 0.0029 |
|  | Complete | 27.80 ± 0.34 / 0.5474 ± 0.0027 | 46.18 ± 0.20 / 0.6704 ± 0.0017 |

Table: Table 2: Neural Machine Translation on WMT14 (Bojar et al., ): The results show the generalization performance of training transformer (base) on English-to-German and transformer (big) on English-to-French. The last checkpoint of each method is evaluated by BLEU score (Papineni et al., ) and METEOR (Banerjee & Lavie, ) the corresponding newtest2014 testset. The number of workers is 16 and the number of workers per node is 4 for all experiments. The error bands with $\pm 2\sigma$ based on 3 runs are reported.

| Methods | Top-1 Acc. $\uparrow$ / Top-5 Acc. $\uparrow$ / Train Loss $\downarrow$ |  |
| --- | --- | --- |
| Alternating Exp Ring | Complete |  |
| AllReduce | 76.01 / 93.05 / 1.864 |  |
| DAdam | 75.31 / 92.54 / 1.998 | 75.27 / 92.60 / 1.993 |
| AccumAdam | 76.54 / 93.18 / 1.836 | 76.34 / 93.15 / 1.835 |

Table: Table 3: Image Classification on ImageNet-1K (Deng et al., ): The results are show the generalization of training ResNet-50 on ImageNet-1K for image classification. Top-1 and Top-5 accuracies and averaged training loss in the last epoch are reported, and the accuracies are evaluated on the ImageNet validation set. The number of workers is 32 and the number of workers per node is 8 for all experiments.

### 5.2 Per-iteration Runtime and Scalability

We will now demonstrate the practicality of decentralized training by showing its superior runtime compared to All-Reduce training in various scenarios, including communication-bound, straggler-bound, and computation-bound cases.
For a fair comparison, we report strong scaling performance in Figure [6](#S5.F6). Other works, such as Assran et al. (), Wang et al. (), present weak scaling performance which keeps the worker batch size fixed. However, this results in fewer iterations and a larger effective global batch size for the same number of epochs, which alters the training dynamics.

As shown in Figure [6](#S5.F6), the results align with the proposed runtime model: (1) a sparse communication topology enables more significant speedups in communication-limited scenarios compared to computation-limited scenarios; (2) decentralized training has better resilience to computation time variance; (3) decentralized training is more efficient than All-Reduce training in all tested scenarios. Additionally, we re-implement 1-OSGP (Assran et al., ) (the best asynchronous variant of SGP) with the one-peer exponential graph for comparison. Due to the extra intra-node broadcast required to synchronize the parameters, 1-OSGP may experience longer per-iteration runtimes when the intra-node connection is not significantly faster than the inter-node connection (nodes with 8$\times$T4 GPU with 100Gbps InfiniBand connection, for example). Consistent with the analysis in § [2.3](#S2.SS3), our implementations outperform 1-OSGP in all setups, especially in computation-bound scenarios.

To demonstrate the relationship between generalization performance and runtime, we present training curves for an En-De translation task in Figure [7](#S5.F7), showing a $\sim 60\%$ speedup at the same validation loss.

We also conducted experiments on the pre-training of GPT-2 (small) (Radford et al., ). Compared to All-Reduce training, decentralized training with AccumAdam and the Alternating Exponential Ring graph achieves better training loss (2.8419 vs. 2.8468), validation loss (2.8561 vs. 2.8626), and runtime (30.41 hours vs. 32.461 hours) after 600k training steps on OpenWebText (Gokaslan et al., ) using 4$\times$4$\times$A40 GPUs. Even though the workloads are balanced among the workers, it still achieves a relative speedup of 6.31%. More speedup can be expected by replacing the sequence packing with other batching strategies that may introduce imbalance in workloads.

Due to space limitations, we defer the presentation of other speedup results to § [A.8](#A1.SS8) in the appendix.

Figure: Figure 6: The results show the strong scaling performance (fixed global batch size, 25K tokens) of All-Reduce, SGP (Assran et al., ) and our implementations by reporting the per-iteration runtime with various numbers of workers and network settings. Here, Exp and AER stand for one-peer exponential graph and alternating exponential ring, respectively.
Refer to caption: /html/2410.11998/assets/x5.png

Figure: Figure 7: Training a transformer (base) model on the English-to-German translation task on four 4xA40 nodes with 25Gbps Ethernet connections. AER stands for the alternating exponential ring topology. The error bands of $\pm 2\sigma$ are based on three runs. The red dashed line on the left is the baseline (27.3 BLEU score) from Vaswani et al. ().
Refer to caption: /html/2410.11998/assets/x6.png

## 6 Conclusions

This paper has aimed to address practical and sometimes overlooked aspects of decentralized training, to make it superior to All-Reduce in terms of total training time and generalization performance in practical settings. We identified key sources of speed-up in decentralized training of deep neural networks and developed a simple model to optimize per-iteration runtimes. We introduced a decentralized Adam algorithm that supports overlapping communication and computation and proposed an accumulation mechanism to mitigate the high variance that occurs in small local batch sizes. Numerous deployments of our methods in practical environments validated their effectiveness, achieving a faster training speed than standard All-Reduce training without compromising generalization.

## Appendix A Appendix / Supplementary Material

### A.1 All-Reduce Adam in the comparison of experiments

The All-Reduce Adam is shown as Algorithm [2](#alg2). In contrast to the decentralized algorithms in Section [4](#S4), it averages gradients instead of models and uses All-Reduce instead of gossip communication.

Figure: Algorithm 2 All-Reduce Adam on worker $i$

### A.2 Heterogeneous communications in HPC clusters

Although there is no single HPC architecture, a typical HPC cluster with many GPU nodes includes high-performance CPUs and GPUs, high-speed interconnects, scalable storage solutions, and management and software stack to handle various computational tasks. Figure [8](#A1.F8) shows the typical topology that we have encountered in our experiments on different clusters. Here, the GPUs within a node communicate with high bandwidth and low latency, while communication through the switch is much more limited. While Figure [8](#A1.F8) shows one example of cluster topology, there are many other possible topologies such as (1) fast NVLinks inter-connecting intra-node GPUs (2) star, ring, tree, mesh, or hybrid connection topologies that link nodes together as a cluster. Different topologies impose different limitations on the communication between GPUs in the same and in different nodes.

Figure: Figure 8: In this HPC environment, each of the two nodes comprises four workers interconnected via PCIe (Peripheral Component Interconnect Express) switches and Network Interface Cards (NICs). The nodes are linked to each other through a switch. We use line thickness to indicate the bandwidth of these connections: wider lines represent higher bandwidth, facilitating faster communication within nodes, while thinner lines depict the narrower bandwidth of the switch, resulting in more time-consuming inter-node communication.
Refer to caption: /html/2410.11998/assets/figures/png/cluster_topo.png

### A.3 Timelines and dependency graphs of different Data Parallel schemes

Figure: Figure 9: Timelines and dependency relations of decentralized training. $F$: forward pass, $B$: backward pass, $C$: communication/aggregation of gradients or model parameters, $U$: update model parameters. Arrow from $X$ to $Y$ means that $Y$ can start only after $X$ finishes.

To better illustrate the capability of our scheme in overlapping communication and computation, we consider two comparison schemes, including the vanilla scheme and a well-optimized scheme that is also used in modern distributed training frameworks like PyTorch’s DataDistributedParallel (Paszke et al., ) and Horovod (Sergeev & Balso, ). We visualize the communication&computation of all three schemes in Figure [9](#A1.F9). In the vanilla scheme, a communication operation only begins to aggregate the gradients among all the workers after completing both a forward pass and a backward pass. The update of the model only happens after the aggregation ends, and the computation does not overlap with the communication. Similar to our scheme, in the PyTorch DDP & Horovod scheme, the model parameters are divided into buckets (the parameters are divided into 3 in the example in Figure [9](#A1.F9)). The communication of the bucket can start immediately after its corresponding backward pass finishes. In this scheme, some time of the communication interleaves with the computation, which greatly improves the utilization. However, the communication still can not be interleaved with the computation of the forward pass and the last bucket of the backward pass. In contrast to the two comparison schemes, our decentralized scheme hides all communications by computations.

### A.4 Decentralized communication topologies

We display the One-peer Ring (Figure [10](#A1.F10)), the One-peer Exponential (Figure [11](#A1.F11)), and the Alternating Exponential Ring (Figure [12](#A1.F12)) topologies in this subsection.

Figure: Figure 10: One-peer Ring for a 16-worker example where workers are distributed in four nodes. Dashed lines are the boundaries of the compute nodes.

Figure: Figure 11: One-peer Exponential graph for a 16-worker example where workers are distributed in four nodes. Dashed lines are the boundaries of the compute nodes.

Figure: Figure 12: Alternating Exponential Ring topology (ours) for a 16-worker example where workers are distributed in four nodes. Dashed lines are the boundaries of nodes. The loops mean All-Reduce across workers in the loop.

### A.5 Runtime model

Our runtime model is constructed under some reasonable settings and experimental results. It assumes that there are $N$ workers and that the neural network model parameters are divided into $b$ buckets so that the average computation and communication time of each bucket are all the same. The global batch size is fixed and the time needed to process the forward pass on a single worker takes 1 unit time. According to Kaplan et al. () and our profiling results, the time taken by the backward pass is roughly twice as the forward pass. With the workload evenly distributed on $N$ workers, the time taken by the forward pass is then $1/N$ unit time and the time taken by the backward pass is $2/N$ unit time. We also assume the time that it takes to update one bucket is $\theta$ time units where $\theta$ is the same for All-Reduce training and decentralized training and independent of the number of workers. Three additional factors are introduced to characterize the system setup and workload:

- 1.
$\gamma\in(0,\infty)$ is the time of an All-Reduce communication of one bucket. Note that $\gamma$ is the actual communication time, while the actual time of the All-Reduce operation could be longer due to synchronization across workers. The $\gamma$ parameter is influenced by several factors:
(a)
Network technology. A poor network connection leads to a slower All-Reduce and a larger $\gamma$.
(b)
The number of workers. More workers lead to a slower All-Reduce and a higher value of $\gamma$.
- 2.
$\omega\in(0,1]$ is the ratio of the time of a decentralized communication round and an All-Reduce operation. Note that $\omega$ could exceed one, but in that case it would always be better to use All-Reduce (as discussed in Section [2.2](#S2.SS2)). Using a more sparse communication topology could potentially decrease $\omega$.
- 3.
$\sigma^{2}\in[0,\infty)$ is the variance in the truncated normal distributions used to model the variance in the computation time. For worker $i$ at iteration $t$, a random number $p_{i}^{(t)}$ is sampled from the truncated normal distribution with mean $1$, variance $\sigma^{2}$, and support $[0.5,1.5]$ (chosen to match our experimental results in Figure [4](#S2.F4)). The random number is used as a multiplier for the computation time of worker $i$ at iteration $t$, *i.e.* the time for both forward and backward passes are multiplied by the same $p^{(i,t)}$.

Figure: Figure 13: Timelines of two workers in decentralized training. In the example, worker 1 has uniform computation time across two iterations while worker 2 has a faster iteration and then a slower one. In the first iteration, $C_{3}$ of worker 2 is prolonged because it needs to synchronize with worker 1 to start the communication.

With these quantities, we further take the dependency relationship into consideration. We denote the completion time of task $X$ at worker $i$ in iteration $t$ by $T_{X}^{(i,t)}$. Then, based on the dependency relation of All-Reduce training, we have

$$ $\displaystyle T_{F}^{(i,t)}$ $\displaystyle=T_{U}^{(i,t-1)}+p^{(i,t)}\frac{b}{N}$ (6) $\displaystyle T_{B_{k}}^{(i,t)}$ $\displaystyle=\left\{\begin{array}[]{ll}p^{(i,t)}\frac{2}{N}+T_{F}^{(i,t)}&\text{if }k=b\\ p^{(i,t)}\frac{2}{N}+T_{B_{k+1}}^{(i,t)}&\text{if }k\in\{1,\ldots,b-1\}\end{array}\right.$ $\displaystyle T_{C_{k}}^{(i,t)}$ $\displaystyle=\left\{\begin{array}[]{ll}\gamma+\max_{j\in[N]}\{T_{B_{k}}^{(j,t)}\}&\text{if }k=b\\ \gamma+\max_{j\in[N]}\{T_{B_{k}}^{(j,t)},T_{C_{k+1}}^{(j,t)}\}&\text{if }k\in\{1,\ldots,b-1\}\end{array}\right.$ $\displaystyle T_{U}^{(i,t)}$ $\displaystyle=T_{C_{1}}^{(i,t)}+\theta b$ $$

where all out-of-bound finish times like $T_{U}^{(i,0)}$ are defined to be zero.

To state similar dependency relations for decentralized training, we denote the set of neighbors of worker $i$
in iteration $t$ as ${\mathcal{N}}_{i}^{(t)}$. Then, we have

$$ $\displaystyle T_{F}^{(i,t)}$ $\displaystyle=T_{U_{1}}^{(i,t-1)}+p^{(i,t)}\frac{1}{N}$ (7) $\displaystyle T_{B_{k}}^{(i,t)}$ $\displaystyle=\left\{\begin{array}[]{ll}p^{(i,t)}\frac{2}{N}+T_{F}^{(i,t)}&\text{if }k=b\\ p^{(i,t)}\frac{2}{N}+T_{U_{k+1}}^{(i,t)}&\text{if }k\in\{1,\ldots,b-1\}\end{array}\right.$ $\displaystyle T_{U_{k}}^{(i,t)}$ $\displaystyle=\max\{T_{B_{k}}^{(i,t)},T_{C_{k}}^{(i,t-1)}\}+\theta$ $\displaystyle T_{C_{k}}^{(i,t)}$ $\displaystyle=\left\{\begin{array}[]{ll}\omega\gamma+\max_{j\in{\mathcal{N}}_{i}^{(t)}}\{T_{U_{k}}^{(j,t)},T_{C_{1}}^{(j,t-1)}\}&\text{if }k=b\\ \omega\gamma+\max_{j\in{\mathcal{N}}_{i}^{(t)}}\{T_{U_{k}}^{(j,t)},T_{C_{k+1}}^{(j,t)}\}&\text{if }k\in\{1,\ldots,b-1\}\end{array}\right.$ $$

where all out-of-bound finish times like $T_{U_{1}}^{(i,0)}$ and $T_{C_{k}}^{(i,0)}$ are defined as zeros.

When $\sigma^{2}>0$, we need to simulate the model and perform Monte Carlo simulations to draw conclusions. When the workloads are deterministic, on the other hand, the model can be used to derive closed-form expressions to guide the design; see Section [3](#S3) in the main document.

#### A.5.1 Influence of Communication Topology on Runtime

To demonstrate the influence of the communication topology on the runtime, we conduct simulations under various topologies but keep $\omega=1$, which can exclude the impact of communication topology on reduced communication cost. The simulation result is in Figure [14](#A1.F14).
Compared with the speedup by adapting decentralized training and reduced $\omega$, the simulation result shows that the changes in the event dependencies caused by the communication topology do not have a significant influence. The difference becomes even more insignificant when the communication cost is the bottleneck ($N\gamma>3.3$).

Figure: Figure 14: Simulated runtime under various communication topologies. The parameters are $b=4$, $\theta=0.02$, and the number of workers in one node is 4.
Refer to caption: /html/2410.11998/assets/x9.png

### A.6 Tasks and detailed experiment setups

All of our experiment implementation is based on PyTorch (Li et al., ). As for the implementation of All-Reduce training baselines, we use DistributedDataParallel
(DDP) module. In all our experiments, we use full-precision training and activate tensor cores for devices that support the feature.

Neural machine translation.
Following (Vaswani et al., ),
we trained the base transformer ($\sim$65M parameters) on the WMT14 English-German dataset (Bojar et al., ) using the global batch size which is roughly 25K source and target tokens, and the models were trained for $\sim$130,000 steps (or 24 epochs) in total. We trained the big
transformer ($\sim$213M parameters) on the WMT14 English-French dataset using the same batch size, and the models were trained for $\sim$300,000 steps (or 5 epochs) in total.
The All-Reduce training baselines use Adam optimizer (Kingma & Ba, ). In each run, the last checkpoint is used to be evaluated by BLEU score (Papineni et al., ) on the corresponding test sets.

Image classification.
As for the image classification task, we trained ResNet-50 (He et al., ) on ImageNet-1K ($\sim$1.28M images and 1K classes) (Deng et al., ). Similar to the translation task, All-Reduce training baselines use Adam optimizer. In all experiments, the models were trained for 90 epochs with 1024 as the global batch size. In each run, the last checkpoint is used to be evaluated by top-1 and top-5 accuracies.

Note that, for all experiments, we fix the global batch sizes of tasks. Unlike the experiments in (Lian et al., ) and (Assran et al., ) which keep the local batch sizes fixed, we argue that using fixed global batch sizes yields a more fair comparison with All-Reduce training because (1) increasing the global batch size as scaling up the number of workers may impose negative effects on the generalization performance of All-Reduce training (Keskar et al., ), (2) increasing the global batch size but keeping the total number of epochs fixed leads to speedup in runtime because of the fewer number of updates, and (3) it’s important to have same number of iterations to achieve comparable performance under fixed epoch budget.

#### A.6.1 Neural machine translation

As for the model architecture, we use the transformer implementation provided by PyTorch. We adopt the scripts open-sourced by Fairseq(^5^55https://github.com/facebookresearch/fairseq/tree/main/examples/translation) to prepare and clean the raw data.

##### Transformer(base) on WMT14 En-De

Following the experiments in (Vaswani et al., ), the sentence pairs are encoded using the byte-pair encoder tokenizer, which has a shared vocabulary with size 37056. The global batch size is fixed to around 25k tokens for source tokens and target tokens, respectively. The sentence pairs with similar lengths are batched together in the training. All experiments use $0.1$ as the dropout rate and $0.1$ as the label smoothing. The learning rate schedule is the inversed square root with 1 epoch of linear warmup.
In the experiments of All-Reduce baselines, the learning rate is 0.0007, and the betas for the Adam optimizer are (0.9, 0.98), which are taken from Vaswani et al. ().
In the experiments of decentralized Adam, the betas for the Adam optimizer are set to (0.974, 0.999) where the choice of $\beta_{1}$ is inspired by AccumAdam when setting $s=4$ (defined in Algorithm [3](#alg3)) and the choice of $\beta_{2}$ is from Devlin et al. (). The choice of betas empirically shows much better performance than (0.9, 0.98), so we use the setting for all experiments of decentralized Adam. The base learning rates are 0.0020, 0.0028, and 0.0038 for 8, 16, and 32 workers, respectively.
In the experiments of AccumAdam, the betas for the AccumAdam optimizer are (0.9, 0.999), and the number of accumulation iterations $s$ is $N/4$. The base learning rate is 0.0008 for 8 workers and 0.0012 for 16 and 32 workers.

##### Transformer(big) on WMT14 En-Fr

Following the experiments in Vaswani et al. (), the sentence pairs are encoded using the word-piece encoder tokenizer, which has a shared vocabulary with size 32000. The global batch size is fixed to around 25k tokens for source tokens and target tokens, respectively. The sentence pairs with similar lengths are batched together in the training. All experiments use $0.1$ as the dropout rate and $0.1$ as the label smoothing. The learning rate schedule is the inversed square root with 1 epoch of linear warmup.
In the experiments of All-Reduce baselines, the learning rate is 0.0007, and the betas for the Adam optimizer are (0.9, 0.98) (Vaswani et al., ).
In the experiments of decentralized Adam, the betas for the Adam optimizer are set to (0.974, 0.999). The base learning rate is 0.0012 for 8 workers.
In the experiments of AccumAdam, the betas for the AccumAdam optimizer are (0.9, 0.999), and the number of accumulation iterations $s$ is $N/4$. The base learning rate is 0.0008 for 8 workers.

#### A.6.2 Image classification

##### ResNet50 on ImageNet

For the experiment setup of the image classification task, we follow the training recipe used to train the weights by torchvision(^6^66https://pytorch.org/blog/how-to-train-state-of-the-art-models-using-torchvision-latest-primitives/). To avoid the bottleneck caused by the data loading and preprocessing on CPU, we use DALI(^7^77https://github.com/NVIDIA/DALI) for the pipeline of preprocessing. In the preprocessing and the data augmentation, the images are: (1) randomly cropped (aspect ratio is from 3/4 to 4/3, random area is from 0.08 to 1.0) (2) resized to 224$\times$224 (3) randomly flipped horizontally with 0.5 probability (4) normalized by channel means and variances. In all experiments, the global batch size is fixed to 1024, the learning rate schedule is cosine annealing with 5 epochs of linear warmup, the weight decay is $3\times 10^{-5}$ on non-batch-normalization parameters, and the label smoothing is 0.1.
In the experiments of All-Reduce baselines, the optimizer is Adam, the base learning rate is 0.001, and the betas are (0.9, 0.999). In the experiments of decentralized Adam, the base learning rate is 0.0024, 0.0048, and 0.0070 for 8, 16, and 32 workers, respectively. The betas are (0.974, 0.999). In the experiments of AccumAdam, the base learning rate is 0.002 for all numbers of workers, the betas are (0.9, 0.999), and $s$ is set to $N/4$.

#### A.6.3 GPT-2 Pretraining

##### GPT-2 (small) on OpenWebText

For the experiment setup of the LLM pretraining, we follow the training recipe from nanoGPT(^8^88https://github.com/karpathy/nanoGPT). The batching strategy used in the repository is sequence packing, and the global batch size is around 0.5 million tokens. The hyperparameters of the baseline are the same as in the repository. The baseline uses AdamW optimizer. For the AccumAdam experiments with 16 A100 GPUs, we only change $\beta_{2}$ and $s$ to $0.999$ and $8$, respectively, and keep the other hyperparameters the same as the baseline.

### A.7 PyTorch extension for decentralized training

The implementation of the PyTorch extension facilitates decentralized training (with the same scheme as in Eq. [2](#S2.E2)). The design is inspired by the DistributedDataParallel(DDP) module in PyTorch (Li et al., ).

The main idea of the implementation is as follows. The implementation is a wrapper of the PyTorch models (torch.nn.Module). By using the hook mechanism in PyTorch, we register the backward hook for all weights before the first forward and backward passes. Then, in the first backward pass, the wrapper collects the computation order of weights, groups the weights into buckets by their order, removes the hooks, and registers new hooks on the last weight in the buckets using register_post_accumulate_grad_hook (available from PyTorch 2.1). The post_accumulate_grad_hook indicates the event that the corresponding gradient of one weight is computed and accumulated, which means the weight will no longer be used in this iteration and it’s ready for update. In the hook, the wrapper checks if the decentralized communication for the bucket in the last iteration is finished, updates the weights in the bucket, and launches the decentralized communication for the next iteration. Another module is implemented for scheduling the neighbors of workers in each iteration, and it makes the extension flexible for various topologies.

Subject to the complexity of implementation and limited time, the implemented wrapper only supports one GPU per worker, and it does not support automatic mixed precision and sparse gradients like in DDP, but the improvements are planned for wider applications in the future.

The implementation is based on the Python API provided by PyTorch. We believe that further practical speedups could be achieved by modifying the low-level implementation of the communication to optimize it for gossip communication.
However, for a fair comparison with DDP in PyTorch, our implementation is at the appropriate level of optimization.

The code will be open source upon acceptance.

#### A.7.1 Comparison with implementation in Stochastic Gradient Push

In the implementation of stochastic gradient push (SGP) (Assran et al., ), to utilize the fast connections (NVLinks between GPUs in one node), it groups the GPUs in one node. In each iteration, the workers in one node will aggregate the gradients and update the model shared in the node combining with the received communication messages. Therefore, the communication topology discussed in Assran et al. () is on the node level. One of the advantages is that the design of topology does not involve the significant heterogeneity caused by intra-node and inter-node connections. However, heterogeneity in connections still exists because the characteristics of inter-node connections may differ depending on the cluster topology and congestion caused by concurrent communications.

Compared with our design, it’s different in that workers always exchange the model parameters instead of gradients, and our communication topology is defined on the worker level. As for the topology, we could utilize the connections in the same way as SGP’s implementation as the worker-level topology is a superset of node-level topology. Moreover, we argue that our implementation is more advantageous in the resilience to the variance because aggregating the gradients will cause the straggler problem within the node.

We demonstrate the difference by making one change in the dependency relationship of the update task. In SGP’s implementation, the update on one bucket does not only depend on the corresponding backward and the communication from the last iteration of the work itself but also its local neighbors’ backward pass and communication. Therefore, compared with the runtime model of decentralized training (Eq. [7](#A1.E7)), the finish time of $U_{k}$ is changed to

$$ $T_{U_{k}}^{(i,t)}=\max_{j\in\mathcal{L}(i)}\{T_{B_{k}}^{(j,t)},T_{C_{k}}^{(j,t-1)}\}+\theta$ (8) $$

where $\mathcal{L}(i)$ is the workers that are in the same node as worker $i$.

Note that in this simplified model, we ignore the time taken by the head worker to broadcast gossip updates to other workers in the node. In most cases, the operation does not incur significant cost to the per-iteration runtime, but only when the intra-node connection is comparable with the inter-node connection (the T4 GPU setup in § [5.2](#S5.SS2), for example).

Figure: Figure 15: Comparison with Stochastic Gradient Push
Refer to caption: /html/2410.11998/assets/x10.png

The results of the simulation by the runtime models are shown in Figure [15](#A1.F15). It shows that, with increasing variance in computation time, our implementation has better speedup (hence better resilience to computation time variance) than SGP when it’s computation-bound. In the communication-bound case, since the communication time dominates the runtime, both implementations have the same speedup.

Since the dependency libraries of the open-source code of SGP(^9^99https://github.com/facebookresearch/stochastic_gradient_push) have been deprecated due to the fast updates of dependencies, we can not reproduce the runtime results on our hardware. Instead, we re-implemented 1-OSGP (the best asynchronous version of SGP) in our numerical experiments. The relative comparisons between 1-OSGP and All-Reduce training are as similar as in Assran et al. (). The comparisons of runtime performance in § [5.2](#S5.SS2) justify the advantages of our implementation.

### A.8 Additional experiments

The section presents the experiment results that are not shown in the main text due to space limitation.

#### A.8.1 Generalization performance

Table [A.8.1](#A1.SS8.SSS1) shows the generalization performance of the training transformer (big) on WMT14 English-to-French, and it shows that both DAdam and AccumAdam outperform All-Reduce training baseline, and AccumAdam outperforms DAdam in most of the metrics.

Table: Table 4: Neural Machine Translation on WMT14 (Bojar et al., ): The results show the generalization performance of training transformer (base) on English-to-German and transformer (big) on English-to-French. The last checkpoint of each method is evaluated by BLEU score (Papineni et al., ) and METEOR (Banerjee & Lavie, ) the corresponding newtest2014 testset. The number of workers is 8 and the number of workers per node is 4 for all experiments. The error bands with $\pm 2\sigma$ based on 3 runs are reported. Some entries are empty because of limited resources.

| Method | Topology | En-De / Transformer (base) | En-Fr / Transformer (big) |
| --- | --- | --- | --- |
| AllReduce | Complete | 27.72 ± 0.37 / 0.5476 ± 0.0036 | 45.69 ± 0.30 / 0.6676 ± 0.0017 |
| DAdam | Ring | 27.59 ± 0.61 / 0.5452 ± 0.0054 | - |
|  | AER | 27.83 ± 0.11 / 0.5472 ± 0.0018 | - |
|  | Complete | 27.84 ± 0.59 / 0.5467 ± 0.0062 | 45.90 ± 0.32 / 0.6693 ± 0.0023 |
| AccumAdam | Ring | 27.61 ± 0.20 / 0.5447 ± 0.0014 | - |
|  | AER | 27.78 ± 0.41 / 0.5471 ± 0.0020 | - |
|  | Complete | 27.82 ± 0.13 / 0.5473 ± 0.0015 | 46.20 ± 0.22 / 0.6718 ± 0.0009 |

#### A.8.2 Speedup

In Tables [A.8.2](#A1.SS8.SSS2), we present the per-iteration runtime of both All-Reduce training and decentralized training (both with Adam optimizer) and the relative speedup of decentralized training over All-Reduce training on the image classification task. Since we conducted the experiments with a fixed iteration budget, the relative speedup of per-iteration runtime also reflects the relative speedup of total runtime.

Combined with the results of generalization performance, the experiments demonstrate the practicality of decentralized training.

Table: Table 5: Results of speedup of training ResNet-50 on ImageNet dataset for the image classification task.

| Node Setup /<br>Inter-Connection | Workers | Methods | Comm.<br>Topology | Per-iteration<br>Runtime (ms) | Speedup |
| --- | --- | --- | --- | --- | --- |
| $4\times$A40 Node /<br>25Gbps Ether. | 8 | AllReduce | complete | 344.44 | - |
| Decentralized | complete | 333.07 | 3.30% |  |  |
| 16 | AllReduce | complete | 176.72 | - |  |
| Decentralized | complete | 163.68 | 7.38% |  |  |
| $8\times$T4 Node /<br>100Gbps Infini. | 16 | AllReduce | complete | 645.59 | - |
| Decentralized | complete | 617.75 | 4.31% |  |  |
| 32 | AllReduce | complete | 331.51 | - |  |
| Decentralized | complete | 313.56 | 5.41% |  |  |

## Appendix B Convergence analysis

### B.1 Preliminaries

#### B.1.1 Notation

Our convergence analysis uses the following, relatively standard, notation.

- •
$\|\cdot\|_{2}$ ($\|\cdot\|_{\infty}$ ): the $\ell_{2}$- ($\ell_{\infty}$-) norm.
- •
$N$: the number of workers.
- •
$D$: the number of dimensions of model parameters.
- •
$x_{i}^{(t)},m_{i}^{(t)},v_{i}^{(t)}\in\mathbb{R}^{D}$: the local model and the local momentums of worker $i$ at iteration $t$.
- •
$x_{i,d}^{(t)},m_{i,d}^{(t)},v_{i,d}^{(t)}\in\mathbb{R}$: the $d$-th entry of the local model and the local momentums of worker $i$ at iteration $t$.
- •
$F$, $F_{i}$: the global objective function and the local objective function of worker $i$.
- •
$g_{i}^{(t)}:=\nabla f_{i}(x_{i}^{(t-1)}):=\nabla\ell(x_{i}^{(t-1)};\xi_{i}^{(t)})\in\mathbb{R}^{D}$: the stochastic gradient evaluated by the local model $x_{i}^{(t-1)}$ and the local sample $\xi_{i}^{(t)}$ on the loss function $\ell$.
- •
$\left[g_{i}^{(t)}\right]^{2}$: the entry-wise square of vector $g_{i}^{(t)}$
- •
$\nabla_{d}f_{i}$: the $d$-th entry of $\nabla f_{i}$.
- •
$W=[w_{ij}]\in\mathbb{R}^{N\times N}$: the mixing matrix where $w_{ij}$ is the $ij$-th entry.
- •
$W^{\infty}\in\mathbb{R}^{N\times N}$: a matrix with all entries equal to $1/N$.
- •
$\mathbf{1}_{N}\in\mathbb{R}^{N\times N}$: an $N\times N$ matrix with all entries equal $1$.
- •
$\mathcal{N}_{i}$: the set of neighbours of worker $i$ ($w_{ij}=w_{ji}>0$).
- •
$[N]:=\{1,2,\ldots,N\}$
- •
$\mathbb{E}_{t-1}\left[\cdot\right]$: the conditional expectation given all stochastic gradients before the $t$-th iteration. By assumption, it holds that
$\mathbb{E}_{t-1}\left[g_{i}^{(t)}\right]=\nabla F_{i}(x_{i}^{(t-1)}).$

### B.2 Comparion with related decentralized methods

##### Ability of overlap

To achieve the overlap of communication and computation, we use a combine-then-adapt (CTA) type of decentralized gradient descent (DGD) in Algorithm [1](#alg1). In contrast, another type, adapt-then-combine (ATC) DGD in the form of $x_{i}^{(t)}\leftarrow\sum_{j\in\mathcal{N}_{i}^{(t)}}w^{(t)}_{ij}(x_{j}^{(t-1)}-{\alpha}^{(t)}d_{j}^{(t)})$ cannot straightforwardly achieve this overlap, even though it has been shown faster convergence in terms of communication rounds Cattivelli & Sayed (). Specifically, for worker $i$ to compute $x_{i}^{(t)}$, assume that a neighbor $j\in\mathcal{N}_{i}^{(t)}$ takes a very long time to calculate its direction $d_{j}^{(t)}$ and then take a long time to send $x_{j}^{(t-1)}-{\alpha}^{(t)}d_{j}^{(t)}$ to worker $i$. Worker $i$ must then wait for receiving $x_{j}^{(t-1)}-{\alpha}^{(t)}d_{j}^{(t)}$ from the straggler $j$ before it can compute $x_{i}^{(t)}$. In contrast, with the CTA type algorithm, worker $i$ only needs the previous iterate $x_{j}^{(t-1)}$ from the straggler $j$ which is already on the way, not the $d_{j}^{(t)}$ which is being calculated with $x_{j}^{(t-1)}$. This allows for the overlap of computation of $d_{j}^{(t)}$ and the communication of $x_{j}^{(t-1)}$. In other words, the communication task of the straggler worker $j$, $x_{j}^{(t-1)}$, is hidden within the computation of $d_{j}^{(t)}$.

##### Comparison with state-of-art decentralized Adam-based methods

The authors in Nazari et al. () proposed DADAM for online optimization over a decentralized network, with the algorithm based on the principle of CTA. Following CTA, the authors in Chen et al. () introduced a unifying decentralized adaptive gradient framework, which involves communication not only of the local models but also of the second-order momentums $v_{i}$. While this enhances the convergence accuracy of the algorithm, it also increases the communication cost. The authors in Ying et al. () proposed DAG-Adam, which incorporates consensus constraints as a penalty in the objective function. Based on the gradient of this penalized augmented objective function, the DAG-Adam algorithm is proposed, improving accuracy in non-iid data scenarios for decentralized Adam. Although DAG-Adam theoretically explains that using different $v_{i}$ across workers $i$ can lead to inexact convergence when data are non-iid, our algorithm is applied under the iid assumption, which holds for our HPC environments. Additionally, the paper Lin et al. () introduces QG-ADAM which uses momentum technique to handle non-iid data. Since QG-ADAM uses the ATC approach, each worker must wait to receive all neighboring workers’ local messages before updating its local model, thus limiting the ability to effectively overlap computation and communication.

#### B.2.1 Useful Inequalities

$$ $\forall a,b\in\mathbb{R}^{d}\text{ and }\forall\beta>0,\ \ \ \langle a,b\rangle\leq\frac{\beta}{2}\|a\|_{2}^{2}+\frac{1}{2\beta}\|b\|_{2}^{2}.$ (9) $$

$$ $\forall x_{i}\in\mathbb{R}^{d}\text{ and }n\in\mathbb{N}^{+},\ \ \ \left\|\sum_{i=1}^{n}x_{i}\right\|^{2}_{2}\leq n\sum_{i=1}^{n}\|x_{i}\|^{2}_{2}.$ (10) $$

$$ $\forall A\in\mathbb{R}^{n\times n}\text{ and }x\in\mathbb{R}^{n},\ \ \ \left\|{Ax}\right\|_{2}^{2}\leq\lambda_{\max}^{2}\left\|{x}\right\|_{2}^{2},$ (11) $$

where $\lambda_{\max}$ is largest singular value of $A$.

We first establish the theorem for $\beta_{1}=0$.

###### Theorem B.1 (Without Heavy-ball Momentum) .

Under Assumptions [1](#Thmassumption1)–[3](#Thmassumption3), for Algorithm [1](#alg1), we have

$$ $\frac{1}{T}\sum_{t=1}^{T}\left\|{\nabla_{d}F(\bar{x}^{(t-1)})}\right\|_{2}^{2}\leq\frac{4R}{\alpha T}\left[F\left(\bar{x}^{(0)}\right)-F_{*}\right]+E\left[\frac{1}{T}\ln\left(1+\frac{R^{2}}{\epsilon(1-\beta_{2})}\right)-\ln(\beta_{2})\right]$ $$

where $\bar{x}^{(t)}=\frac{1}{N}\sum_{i=1}^{N}x_{i}^{(t)}$ and

$$ $E:=\frac{8DR^{2}}{\sqrt{1-\beta_{2}}}+\frac{2\alpha DLR}{(1-\beta_{2})}+\frac{8\alpha^{2}(1+\lambda^{2})L^{2}DR}{(1-\lambda^{2})^{2}(1-\beta_{2})^{3/2}\sqrt{\epsilon}}.$ $$

The proof can be found in Appendix [B.3](#A2.SS3).
Compared with (Défossez et al., , Theorem 2) for the single-machine Adam, Theorem [B.1](#A2.Thmtheorem1) shows that our decentralized Adam achieves the same results as Défossez et al. () (ignoring scaled constants), except that there is an additional third term in $E$, which is related to the second largest absolute value eigenvalue of the mixing matrix $\lambda$. Since a $\lambda$ close to 1 indicates poor connectivity of the topology, it increases the third term in $E$. Notably, this term is proportional to the square of the step size, $\alpha$. By selecting a smaller $\alpha$, we can effectively mitigate this term.

###### Theorem B.1 (Without Heavy-ball Momentum) .

### B.3 Proof of Thorem B.1 : Decentralized Adam Without Heavy-ball Momentum

#### B.3.1 Algorithm Update Under Analysis

We set $\beta_{1}=0$, which means that there is no heavy-ball momentum. We have the algorithm update under analysis is

$$ $\displaystyle g_{i}^{(t)}=\nabla\ell(x_{i}^{(t-1)};\xi_{i}^{(t)}),\ \ v_{i,d}^{(t)}=\beta_{2}v_{i,d}^{(t-1)}+\left[g_{i,d}^{(t)}\right]^{2},$ (12) $\displaystyle\alpha_{t}=\alpha\sqrt{\frac{1-\beta_{2}^{t}}{1-\beta_{2}}},\ \ x_{i,d}^{(t)}=-\alpha_{t}\frac{g_{i,d}^{(t)}}{\sqrt{\epsilon+v_{i,d}^{(t)}}}+\sum_{j\in\mathcal{N}_{i}}w_{ij}x_{j,d}^{(t-1)}.$ $$

Taking the average across workers and using the Assumption [3](#Thmassumption3), we get that the (virtual) update of the globally averaged model is

$$ $\bar{x}_{d}^{(t)}=-\frac{\alpha_{t}}{N}\sum_{i=1}^{N}\frac{g_{i,d}^{(t)}}{\sqrt{\epsilon+v_{i,d}^{(t)}}}+\bar{x}_{d}^{(t-1)}.$ (13) $$

We denote $\tilde{v}_{i}^{(t)}:=\beta_{2}v_{i}^{(t-1)}+\mathbb{E}_{t-1}\left[\left(g_{i,d}^{(t)}\right)^{2}\right]$ which differs from $v_{i,d}^{(t)}$ by replacing the last term of $v_{i,d}^{(t)}$ with its conditional expectation.
To simplify the notation, we denote

$$ $\displaystyle\bar{G}_{d}^{(t)}:=\nabla_{d}F\left(\bar{x}^{(t-1)}\right)=\frac{1}{N}\sum_{i=1}^{N}\nabla_{d}F_{i}\left(\bar{x}^{(t-1)}\right)\quad\text{and}\quad G_{i,d}^{(t)}:=\nabla_{d}F_{i}(x_{i}^{(t-1)}).$ (14) $$

#### B.3.2 Technical lemmas

##### Lemma 1 (adaptive update approximately follow a descent direction)

Under Assumption [2](#Thmassumption2), for Algorithm [1](#alg1), we have

$$ $\kappa\geq\frac{1}{4}\sum_{i=1}^{N}\frac{\left[\nabla_{d}F\left(\bar{x}^{(t-1)}\right)\right]^{2}}{\sqrt{\epsilon+\tilde{v}_{i,d}^{(t)}}}-\sum_{i=1}^{N}\frac{\left[\nabla_{d}F_{i}\left(x_{i}^{(t-1)}\right)-\nabla_{d}F\left(\bar{x}^{(t-1)}\right)\right]^{2}}{\sqrt{\epsilon+\tilde{v}^{(t)}_{i,d}}}-2R\sum_{i=1}^{N}\mathbb{E}_{t-1}\left[\frac{\left(\nabla_{d}f_{i}(x_{i}^{(t-1)})\right)^{2}}{\epsilon+v_{i,d}^{(t)}}\right]$ (15) $$

where

$$ $\kappa:=\mathbb{E}_{t-1}\left[\nabla_{d}F\left(\bar{x}^{(t-1)}\right)\left(\sum_{i=1}^{N}\frac{\nabla_{d}f_{i}\left(x_{i}^{(t-1)}\right)}{\sqrt{\epsilon+v_{i,d}^{(t)}}}\right)\right].$ $$

###### Proof.

According to the definition of $\kappa$, we have

$$ $\displaystyle\kappa$ $\displaystyle=\bar{G}_{d}^{(t)}\mathbb{E}_{t-1}\left[\sum_{i=1}^{N}\frac{g_{i,d}^{(t)}}{\sqrt{\epsilon+v_{i,d}^{(t)}}}\right]$ (16) $\displaystyle=\bar{G}_{d}^{(t)}\mathbb{E}_{t-1}\left[\sum_{i=1}^{N}g_{i,d}^{(t)}\left(\frac{1}{\sqrt{\epsilon+v_{i,d}^{(t)}}}\pm\frac{1}{\sqrt{\epsilon+\tilde{v}_{i,d}^{(t)}}}\right)\right]$ $\displaystyle=\bar{G}_{d}^{(t)}\mathbb{E}_{t-1}\left[\sum_{i=1}^{N}\frac{g_{i,d}^{(t)}}{\sqrt{\epsilon+\tilde{v}_{i,d}^{(t)}}}\right]+\mathbb{E}_{t-1}\left[\bar{G}_{d}^{(t)}\sum_{i=1}^{N}\left(\frac{g_{i,d}^{(t)}}{\sqrt{\epsilon+v_{i,d}^{(t)}}}-\frac{g_{i,d}^{(t)}}{\sqrt{\epsilon+\tilde{v}_{i,d}^{(t)}}}\right)\right]$ $\displaystyle=\underbrace{\bar{G}_{d}^{(t)}\sum_{i=1}^{N}\frac{G_{i,d}^{(t)}}{\sqrt{\epsilon+\tilde{v}_{i,d}^{(t)}}}}_{A}+\mathbb{E}_{t-1}\underbrace{\left[\bar{G}_{d}^{(t)}\sum_{i=1}^{N}\left(\frac{g_{i,d}^{(t)}}{\sqrt{\epsilon+v_{i,d}^{(t)}}}-\frac{g_{i,d}^{(t)}}{\sqrt{\epsilon+\tilde{v}_{i,d}^{(t)}}}\right)\right]}_{B}.$ $$

Firstly, for the term $A$, we have

$$ $\displaystyle A=\bar{G}_{d}^{(t)}\left(\sum_{i=1}^{N}\frac{G_{i,d}^{(t)}\pm\bar{G}_{d}^{(t)}}{\sqrt{\epsilon+\tilde{v}_{i,d}^{(t)}}}\right)=\bar{G}_{d}^{(t)}\left(\sum_{i=1}^{N}\frac{G_{i,d}^{(t)}-\bar{G}_{d}^{(t)}}{\sqrt{\epsilon+\tilde{v}_{i,d}^{(t)}}}\right)+\sum_{i=1}^{N}\frac{\left[\bar{G}_{d}^{(t)}\right]^{2}}{\sqrt{\epsilon+\tilde{v}_{i,d}^{(t)}}}.$ (17) $$

By applying the Young’s inequality ([9](#A2.E9)) for $N$ times on the first term on the right hand of equation [17](#A2.E17) and letting

$$ $\gamma=\frac{1}{2\sqrt{\epsilon+\tilde{v}_{i,d}^{(t)}}},\ \ a=\bar{G}_{d}^{(t)},\ \ b=\frac{G_{i,d}^{(t)}-\bar{G}_{d}^{(t)}}{\sqrt{\epsilon+\tilde{v}^{(t)}_{i,d}}},$ $$

we have

$$ $\displaystyle A$ $\displaystyle\geq-\frac{1}{4}\sum_{i=1}^{N}\frac{\left[\bar{G}_{d}^{(t)}\right]^{2}}{\sqrt{\epsilon+\tilde{v}_{i,d}^{(t)}}}-\sum_{i=1}^{N}\frac{\left[G_{i,d}^{(t)}-\bar{G}_{d}^{(t)}\right]^{2}}{\sqrt{\epsilon+\tilde{v}^{(t)}_{i,d}}}+\sum_{i=1}^{N}\frac{\left[\bar{G}_{d}^{(t)}\right]^{2}}{\sqrt{\epsilon+\tilde{v}_{i,d}^{(t)}}}$ (18) $\displaystyle=\frac{3}{4}\sum_{i=1}^{N}\frac{\left[\bar{G}_{d}^{(t)}\right]^{2}}{\sqrt{\epsilon+\tilde{v}_{i,d}^{(t)}}}-\sum_{i=1}^{N}\frac{\left[G_{i,d}^{(t)}-\bar{G}_{d}^{(t)}\right]^{2}}{\sqrt{\epsilon+\tilde{v}^{(t)}_{i,d}}}.$ $$

For the term $B$ in ([16](#A2.E16)), we have

$$ $\displaystyle B$ $\displaystyle=\bar{G}_{d}^{(t)}\sum_{i=1}^{N}\left(\frac{g_{i,d}^{(t)}}{\sqrt{\epsilon+v_{i,d}^{(t)}}}-\frac{g_{i,d}^{(t)}}{\sqrt{\epsilon+\tilde{v}_{i,d}^{(t)}}}\right)$ (19) $\displaystyle=\bar{G}_{d}^{(t)}\sum_{i=1}^{N}\left[\frac{g_{i,d}^{(t)}\left(\tilde{v}_{i,d}^{(t)}-v_{i,d}^{(t)}\right)}{\sqrt{\epsilon+v_{i,d}^{(t)}}\sqrt{\epsilon+\tilde{v}_{i,d}^{(t)}}\left(\sqrt{\epsilon+v_{i,d}^{(t)}}+\sqrt{\epsilon+\tilde{v}_{i,d}^{(t)}}\right)}\right]$ $\displaystyle=\bar{G}_{d}^{(t)}\sum_{i=1}^{N}\left[\frac{g_{i,d}^{(t)}\left[\mathbb{E}_{t-1}\left[\left(g_{i,d}^{(t)}\right)^{2}\right]-\left(g_{i,d}^{(t)}\right)^{2}\right]}{\sqrt{\epsilon+v_{i,d}^{(t)}}\sqrt{\epsilon+\tilde{v}_{i,d}^{(t)}}\left(\sqrt{\epsilon+v_{i,d}^{(t)}}+\sqrt{\epsilon+\tilde{v}_{i,d}^{(t)}}\right)}\right].$ $$

Given the fact that $\sqrt{\epsilon+v_{i,d}^{(t)}}>0$ and $\sqrt{\epsilon+\tilde{v}_{i,d}^{(t)}}>0$, we have

$$ $\displaystyle\sqrt{\epsilon+v_{i,d}^{(t)}}+\sqrt{\epsilon+\tilde{v}_{i,d}^{(t)}}$ $\displaystyle>\sqrt{\epsilon+v_{i,d}^{(t)}}\ \ \ \text{and}\ \ \ \sqrt{\epsilon+v_{i,d}^{(t)}}+\sqrt{\epsilon+\tilde{v}_{i,d}^{(t)}}$ $\displaystyle>\sqrt{\epsilon+\tilde{v}_{i,d}^{(t)}}.$ (20) $$

By taking the absolute value of $B$, we have

$$ $|B|\leq\underbrace{\sum_{i=1}^{N}\frac{\left|\bar{G}_{d}^{(t)}g_{i,d}^{(t)}\right|\mathbb{E}_{t-1}\left[\left(g_{i,d}^{(t)}\right)^{2}\right]}{\sqrt{\epsilon+v_{i,d}^{(t)}}\left(\epsilon+\tilde{v}_{i,d}^{(t)}\right)}}_{C}+\underbrace{\sum_{i=1}^{N}\frac{\left|\bar{G}_{d}^{(t)}g_{i,d}^{(t)}\right|\left(g_{i,d}^{(t)}\right)^{2}}{\sqrt{\epsilon+\tilde{v}_{i,d}^{(t)}}\left(\epsilon+v_{i,d}^{(t)}\right)}}_{H}.$ (21) $$

To bound $C$, by applying the Young’s inequality equation [9](#A2.E9) for $N$ times and let

$$ $\gamma=\frac{\sqrt{\epsilon+\tilde{v}_{i,d}^{(t)}}}{2},\ \ a=\frac{\left|\bar{G}_{d}^{(t)}\right|}{\sqrt{\epsilon+\tilde{v}_{i,d}^{(t)}}},\ \ b=\frac{\left|g_{i,d}^{(t)}\right|\mathbb{E}_{t-1}\left[\left(g_{i,d}^{(t)}\right)^{2}\right]}{\sqrt{\epsilon+v_{i,d}^{(t)}}\sqrt{\epsilon+\tilde{v}_{i,d}^{(t)}}},$ $$

we have

$$ $C\leq\frac{1}{4}\sum_{i=1}^{N}\frac{\left[\bar{G}_{d}^{(t)}\right]^{2}}{\sqrt{\epsilon+\tilde{v}_{i,d}^{(t)}}}+\sum_{i=1}^{N}\frac{\left(g_{i,d}^{(t)}\right)^{2}\mathbb{E}_{t-1}\left[\left(g_{i,d}^{(t)}\right)^{2}\right]^{2}}{\left(\epsilon+v_{i,d}^{(t)}\right)\left(\epsilon+\tilde{v}_{i,d}^{(t)}\right)^{3/2}}.$ (22) $$

Given the fact that $\sqrt{\epsilon+\tilde{v}_{i,d}^{(t)}}\geq\sqrt{\mathbb{E}_{t-1}\left[\left(g_{i,d}^{(t)}\right)^{2}\right]}$, using Assumption [2](#Thmassumption2), and taking the conditional expectation on $C$, we have

$$ $\displaystyle\mathbb{E}_{t-1}[C]$ $\displaystyle\leq\frac{1}{4}\sum_{i=1}^{N}\frac{\left[\bar{G}_{d}^{(t)}\right]^{2}}{\sqrt{\epsilon+\tilde{v}_{i,d}^{(t)}}}+\sum_{i=1}^{N}\mathbb{E}_{t-1}\left[\frac{\left(g_{i,d}^{(t)}\right)^{2}}{\epsilon+v_{i,d}^{(t)}}\right]\frac{\mathbb{E}_{t-1}\left[\left(g_{i,d}^{(t)}\right)^{2}\right]^{2}}{\left(\epsilon+\tilde{v}_{i,d}^{(t)}\right)^{3/2}}$ (23) $\displaystyle\leq\frac{1}{4}\sum_{i=1}^{N}\frac{\left[\bar{G}_{d}^{(t)}\right]^{2}}{\sqrt{\epsilon+\tilde{v}_{i,d}^{(t)}}}+\sum_{i=1}^{N}\mathbb{E}_{t-1}\left[\frac{\left(g_{i,d}^{(t)}\right)^{2}}{\epsilon+v_{i,d}^{(t)}}\right]\sqrt{\mathbb{E}_{t-1}\left[\left(g_{i,d}^{(t)}\right)^{2}\right]}$ $\displaystyle\leq\frac{1}{4}\sum_{i=1}^{N}\frac{\left[\bar{G}_{d}^{(t)}\right]^{2}}{\sqrt{\epsilon+\tilde{v}_{i,d}^{(t)}}}+R\sum_{i=1}^{N}\mathbb{E}_{t-1}\left[\frac{\left(g_{i,d}^{(t)}\right)^{2}}{\epsilon+v_{i,d}^{(t)}}\right].$ $$

Now we focus on $H$ in ([21](#A2.E21)). By applying the Young’s inequality equation [9](#A2.E9) for $N$ times and let

$$ $\gamma=\frac{\sqrt{\epsilon+\tilde{v}_{i,d}^{(t)}}}{2\mathbb{E}_{t-1}\left[\left(g_{i,d}^{(t)}\right)^{2}\right]},a=\frac{\left|\bar{G}_{d}^{(t)}g_{i,d}^{(t)}\right|}{\sqrt{\epsilon+\tilde{v}_{i,d}^{(t)}}},b=\frac{\left(g_{i,d}^{(t)}\right)^{2}}{\epsilon+v_{i,d}^{(t)}},$ (24) $$

we have

$$ $H\leq\frac{1}{4}\sum_{i=1}^{N}\frac{\left[\bar{G}_{d}^{(t)}\right]^{2}}{\sqrt{\epsilon+\tilde{v}_{i,d}^{(t)}}}\frac{\left(g_{i,d}^{(t)}\right)^{2}}{\mathbb{E}_{t-1}\left[\left(g_{i,d}^{(t)}\right)^{2}\right]}+\sum_{i=1}^{N}\frac{\mathbb{E}_{t-1}\left[\left(g_{i,d}^{(t)}\right)^{2}\right]}{\sqrt{\epsilon+\tilde{v}_{i,d}^{(t)}}}\frac{\left(g_{i,d}^{(t)}\right)^{4}}{\left(\epsilon+v_{i,d}^{(t)}\right)^{2}}.$ (25) $$

Given the fact that $\epsilon+v_{i,d}^{(t)}\geq\left(g_{i,d}^{(t)}\right)^{2}$ and $\sqrt{\epsilon+\tilde{v}_{i,d}^{(t)}}\geq\sqrt{\mathbb{E}_{t-1}\left[\left(g_{i,d}^{(t)}\right)^{2}\right]^{2}}$, using Assumption [2](#Thmassumption2), and taking the conditional expectation, we have

$$ $\displaystyle E_{t-1}[H]$ $\displaystyle\leq\frac{1}{4}\sum_{i=1}^{N}\frac{\left[\bar{G}_{d}^{(t)}\right]^{2}}{\sqrt{\epsilon+\tilde{v}_{i,d}^{(t)}}}\frac{\mathbb{E}_{t-1}\left[\left(g_{i,d}^{(t)}\right)^{2}\right]}{\mathbb{E}_{t-1}\left[\left(g_{i,d}^{(t)}\right)^{2}\right]}+\sum_{i=1}^{N}\frac{\mathbb{E}_{t-1}\left[\left(g_{i,d}^{(t)}\right)^{2}\right]}{\sqrt{\epsilon+\tilde{v}_{i,d}^{(t)}}}\mathbb{E}_{t-1}\left[\frac{\left(g_{i,d}^{(t)}\right)^{4}}{\left(\epsilon+v_{i,d}^{(t)}\right)^{2}}\right]$ (26) $\displaystyle\leq\frac{1}{4}\sum_{i=1}^{N}\frac{\left[\bar{G}_{d}^{(t)}\right]^{2}}{\sqrt{\epsilon+\tilde{v}_{i,d}^{(t)}}}+R\sum_{i=1}^{N}\mathbb{E}_{t-1}\left[\frac{\left(g_{i,d}^{(t)}\right)^{2}}{\epsilon+v_{i,d}^{(t)}}\right].$ $$

By plugging ([23](#A2.E23)) and ([26](#A2.E26)) back to ([21](#A2.E21)), we have

$$ $\displaystyle\mathbb{E}_{t-1}[B]$ $\displaystyle\geq-\mathbb{E}_{t-1}[|B|]$ (27) $\displaystyle\geq-\mathbb{E}_{t-1}[|C|]-\mathbb{E}_{t-1}[|H|]$ $\displaystyle\geq-\frac{1}{2}\sum_{i=1}^{N}\frac{\left[\bar{G}_{d}^{(t)}\right]^{2}}{\sqrt{\epsilon+\tilde{v}_{i,d}^{(t)}}}-2R\sum_{i=1}^{N}\mathbb{E}_{t-1}\left[\frac{\left(g_{i,d}^{(t)}\right)^{2}}{\epsilon+v_{i,d}^{(t)}}\right].$ $$

By plugging ([18](#A2.E18)) and ([27](#A2.E27)) back to ([16](#A2.E16)), we have

$$ $\displaystyle\kappa$ $\displaystyle=A+\mathbb{E}_{t-1}[B]$ (28) $\displaystyle\geq\frac{1}{4}\sum_{i=1}^{N}\frac{\left[\bar{G}_{d}^{(t)}\right]^{2}}{\sqrt{\epsilon+\tilde{v}_{i,d}^{(t)}}}-\sum_{i=1}^{N}\frac{\left[G_{i,d}^{(t)}-\bar{G}_{d}^{(t)}\right]^{2}}{\sqrt{\epsilon+\tilde{v}^{(t)}_{i,d}}}-2R\sum_{i=1}^{N}\mathbb{E}_{t-1}\left[\frac{\left(g_{i,d}^{(t)}\right)^{2}}{\epsilon+v_{i,d}^{(t)}}\right]$ $\displaystyle=\frac{1}{4}\sum_{i=1}^{N}\frac{\left[\nabla_{d}F\left(\bar{x}^{(t-1)}\right)\right]^{2}}{\sqrt{\epsilon+\tilde{v}_{i,d}^{(t)}}}-\sum_{i=1}^{N}\frac{\left[\nabla_{d}F_{i}\left(x_{i}^{(t-1)}\right)-\nabla_{d}F\left(\bar{x}^{(t-1)}\right)\right]^{2}}{\sqrt{\epsilon+\tilde{v}^{(t)}_{i,d}}}$ $\displaystyle\ \ \ -2R\sum_{i=1}^{N}\mathbb{E}_{t-1}\left[\frac{\left(\nabla_{d}f_{i}(x_{i}^{(t-1)})\right)^{2}}{\epsilon+v_{i,d}^{(t)}}\right],$ $$

which completes the proof of Lemma [1](#A2.SS3.SSS2.Px1).
∎

###### Proof.

##### Lemma 2 (sum of ratios with the denominator being the sum of past numerators)

Given $0<\beta_{2}<1$ and a non-negative sequence $(a_{t})_{t\in\mathbb{N}^{+}}$, define $b_{t}=\sum_{j=1}^{t}\beta_{2}^{t-j}a_{j}$ for all $t\in\mathbb{N}^{+}$, then we have

$$ $\sum_{j=1}^{T}\frac{a_{j}}{\epsilon+b_{j}}\leq\ln\left(1+\frac{b_{T}}{\epsilon}\right)-T\ln(\beta_{2}).$ (29) $$

###### Proof.

Refer to Lemma 5.2 in Défossez et al. ().
∎

###### Proof.

##### Lemma 3 (averaged consensus error is bounded if sampling from i.i.d. data distribution)

Under Assumptions [1](#Thmassumption1)–[3](#Thmassumption3), for Algorithm [1](#alg1), we have

$$ $\displaystyle\frac{1}{T}\sum_{t=1}^{T}\sum_{i=1}^{N}\sum_{d=1}^{D}\left[\nabla_{d}F_{i}(x_{i}^{(t-1)})-\nabla_{d}F(\bar{x}_{i}^{(t-1)})\right]^{2}$ (30) $\displaystyle\leq$ $\displaystyle\frac{2(1+\lambda^{2})\alpha^{2}NL^{2}D}{(1-\lambda^{2})^{2}(1-\beta_{2})}\left[\frac{1}{T}\ln\left(1+\frac{R^{2}}{\epsilon(1-\beta_{2})}\right)-\ln(\beta_{2})\right].$ $$

###### Proof.

Denote the concatenation of the $d$-th dimension of all local models at $t$-th iteration as

$$ $\mathbf{x}_{d}^{(t)}:=\begin{bmatrix}x_{1,d}^{(t)}&x_{2,d}^{(t)}&\cdots&x_{N,d}^{(t)}\end{bmatrix}^{\top}\in\mathbb{R}^{N}.$ $$

Denote the concatenation of $N$ $d$-th dimension of the (virtual) averaged model as

$$ $\bar{\mathbf{x}}_{d}^{(t)}:=\begin{bmatrix}\bar{x}_{d}^{(t)}&\bar{x}_{d}^{(t)}&\cdots&\bar{x}_{d}^{(t)}\end{bmatrix}^{\top}\in\mathbb{R}^{N}.$ $$

Denote the concatenation of the $d$-th dimension of updates of all local models at $t$-th iteration as

$$ $\mathbf{e}_{d}^{(t)}=-\alpha_{t}\left[\frac{\nabla_{d}f_{1}\left(x_{1}^{(t-1)}\right)}{\sqrt{\epsilon+v_{1,d}^{(t)}}},\cdots,\frac{\nabla_{d}f_{N}\left(x_{N}^{(t-1)}\right)}{\sqrt{\epsilon+v_{N,d}^{(t)}}}\right]\in\mathbb{R}^{N}.$ $$

Denote the concatenation of $N$ $d$-th dimension of updates of the (virtual) averaged model at $t$-th iteration as

$$ $\bar{\mathbf{e}}_{d}^{(t)}=-\frac{\alpha_{t}}{N}\left[\sum_{i=1}^{N}\frac{\nabla_{d}f_{i}\left(x_{i}^{(t-1)}\right)}{\sqrt{\epsilon+v_{i,d}^{(t)}}},\cdots,\sum_{i=1}^{N}\frac{\nabla_{d}f_{i}\left(x_{i}^{(t-1)}\right)}{\sqrt{\epsilon+v_{i,d}^{(t)}}}\right]\in\mathbb{R}^{N}.$ $$

From the update function ([12](#A2.E12)), it can be inferred that

$$ $\bar{\mathbf{x}}_{d}^{(t)}=\bar{\mathbf{x}}_{d}^{(t-1)}+\bar{\mathbf{e}}_{d}^{(t)}=\frac{1}{N}\mathbf{1}_{N}\mathbf{x}_{d}^{(t-1)}+\frac{1}{N}\mathbf{1}_{N}\mathbf{e}_{d}^{(t)}=W^{\infty}\mathbf{x}_{d}^{(t-1)}+W^{\infty}\mathbf{e}_{d}^{(t)}$ (31) $$

The update of $\mathbf{x}_{d}^{(t)}$ can be rewritten as

$$ $\mathbf{x}_{d}^{(t)}=W\mathbf{x}_{d}^{(t-1)}+\mathbf{e}_{d}^{(t)}$ (32) $$

Then we have

$$ $\displaystyle\left\|{\mathbf{x}_{d}^{(t)}-\bar{\mathbf{x}}_{d}^{(t)}}\right\|_{2}^{2}$ $\displaystyle=\left\|{W\mathbf{x}_{d}^{(t-1)}+\mathbf{e}_{d}^{(t)}-\bar{\mathbf{x}}_{d}^{(t-1)}-\bar{\mathbf{e}}_{d}^{(t)}}\right\|_{2}^{2}$ (33) $\displaystyle=\left\|{\left(W-\frac{1}{N}\mathbf{1}_{N}\right)\mathbf{x}_{d}^{(t-1)}+\left(I-\frac{1}{N}\mathbf{1}_{N}\right)\mathbf{e}_{d}^{(t)}}\right\|_{2}^{2}$ $\displaystyle=\left\|{\left(W-\frac{1}{N}\mathbf{1}_{N}\right)\mathbf{x}_{d}^{(t-1)}-\left(W-\frac{1}{N}\mathbf{1}_{N}\right)\bar{\mathbf{x}}_{d}^{(t)}+\left(I-\frac{1}{N}\mathbf{1}_{N}\right)\mathbf{e}_{d}^{(t)}}\right\|_{2}^{2}$ $\displaystyle=\left\|{\left(W-\frac{1}{N}\mathbf{1}_{N}\right)\left(\mathbf{x}_{d}^{(t-1)}-\bar{\mathbf{x}}_{d}^{(t-1)}\right)+\left(I-\frac{1}{N}\mathbf{1}_{N}\right)\mathbf{e}_{d}^{(t)}}\right\|_{2}^{2}$ $\displaystyle=\left\|{\left(W-\frac{1}{N}\mathbf{1}_{N}\right)\left(\mathbf{x}_{d}^{(t-1)}-\bar{\mathbf{x}}_{d}^{(t-1)}\right)}\right\|_{2}^{2}+\left\|{\left(I-\frac{1}{N}\mathbf{1}_{N}\right)\mathbf{e}_{d}^{(t)}}\right\|_{2}^{2}$ $\displaystyle\ \ \ +2\left[\left(W-\frac{1}{N}\mathbf{1}_{N}\right)\left(\mathbf{x}_{d}^{(t-1)}-\bar{\mathbf{x}}_{d}^{(t-1)}\right)\right]^{\top}\left[\left(I-\frac{1}{N}\mathbf{1}_{N}\right)\mathbf{e}_{d}^{(t)}\right].$ $$

Recall the definition of $\lambda$ in Assumption [3](#Thmassumption3). By applying the Young’s inequality equation [9](#A2.E9) and letting

$$ $\gamma=\frac{1-\lambda^{2}}{2\lambda^{2}}>0,\ \ \ a=\left(W-\frac{1}{N}\mathbf{1}_{N}\right)\left(\mathbf{x}_{d}^{(t-1)}-\bar{\mathbf{x}}_{d}^{(t-1)}\right),\ \ \ b=\left(I-\frac{1}{N}\mathbf{1}_{N}\right)\mathbf{e}_{d}^{(t)},$ $$

we have

$$ $\left\|{\mathbf{x}_{d}^{(t)}-\bar{\mathbf{x}}_{d}^{(t)}}\right\|_{2}^{2}\leq\frac{1+\lambda^{2}}{2\lambda^{2}}\left\|{\left(W-\frac{1}{N}\mathbf{1}_{N}\right)\left(\mathbf{x}_{d}^{(t-1)}-\bar{\mathbf{x}}_{d}^{(t-1)}\right)}\right\|_{2}^{2}+\frac{1+\lambda^{2}}{1-\lambda^{2}}\left\|{\left(I-\frac{1}{N}\mathbf{1}_{N}\right)\mathbf{e}_{d}^{(t)}}\right\|_{2}^{2}.$ (34) $$

By using ([11](#A2.E11)), we have

$$ $\left\|{\mathbf{x}_{d}^{(t)}-\bar{\mathbf{x}}_{d}^{(t)}}\right\|_{2}^{2}\leq\frac{1+\lambda^{2}}{2}\left\|{\mathbf{x}_{d}^{(t-1)}-\bar{\mathbf{x}}_{d}^{(t-1)}}\right\|_{2}^{2}+\frac{1+\lambda^{2}}{1-\lambda^{2}}\left\|{\mathbf{e}_{d}^{(t)}}\right\|_{2}^{2}.$ (35) $$

Given that all local models start from the same point $x^{(0)}$, by summing up for all $t\in[T]$ and using telescoping, we have

$$ $\displaystyle\frac{1-\lambda^{2}}{2}\sum_{t=1}^{T}\left\|{\mathbf{x}_{d}^{(t-1)}-\bar{\mathbf{x}}_{d}^{(t-1)}}\right\|_{2}^{2}$ $\displaystyle\leq\frac{1+\lambda^{2}}{1-\lambda^{2}}\sum_{t=1}^{T}\left\|{\mathbf{e}_{d}^{(t)}}\right\|_{2}^{2}.$ (36) $$

Given that $\alpha_{t}\leq\frac{\alpha}{\sqrt{1-\beta_{2}}}$ and using Lemma [2](#A2.SS3.SSS2.Px2), we have

$$ $\displaystyle\frac{1-\lambda^{2}}{2}\sum_{t=1}^{T}\left\|{\mathbf{x}_{d}^{(t-1)}-\bar{\mathbf{x}}_{d}^{(t-1)}}\right\|_{2}^{2}$ $\displaystyle\leq\frac{1+\lambda^{2}}{1-\lambda^{2}}\sum_{i=1}^{N}\sum_{t=1}^{T}\alpha_{t}^{2}\frac{\left(g_{i,d}^{(t)}\right)^{2}}{\epsilon+v_{i,d}^{(t)}}$ (37) $\displaystyle\leq\frac{(1+\lambda^{2})\alpha^{2}}{(1-\lambda^{2})(1-\beta_{2})}\sum_{i=1}^{N}\sum_{t=1}^{T}\frac{\left(g_{i,d}^{(t)}\right)^{2}}{\epsilon+v_{i,d}^{(t)}}$ $\displaystyle\leq\frac{(1+\lambda^{2})\alpha^{2}}{(1-\lambda^{2})(1-\beta_{2})}\sum_{i=1}^{N}\left[\ln\left(1+\frac{v_{i,d}^{(t)}}{\epsilon}\right)-T\ln(\beta_{2})\right].$ $$

By using Assumption [2](#Thmassumption2) on the above inequality, we have

$$ $\frac{1}{T}\sum_{t=1}^{T}\left\|{\mathbf{x}_{d}^{(t-1)}-\bar{\mathbf{x}}_{d}^{(t-1)}}\right\|_{2}^{2}\leq\frac{2(1+\lambda^{2})\alpha^{2}N}{(1-\lambda^{2})^{2}(1-\beta_{2})}\left[\frac{1}{T}\ln\left(1+\frac{R^{2}}{\epsilon(1-\beta_{2})}\right)-\ln(\beta_{2})\right].$ (38) $$

We now focus on the left side of ([30](#A2.E30)). By using iid assumption and Assumption [1](#Thmassumption1), we have

$$ $\displaystyle\frac{1}{T}\sum_{t=1}^{T}\sum_{i=1}^{N}\sum_{d=1}^{D}\left[\nabla_{d}F_{i}(x_{i}^{(t-1)})-\nabla_{d}F(\bar{x}_{i}^{(t-1)})\right]^{2}$ $\displaystyle=\frac{1}{T}\sum_{t=1}^{T}\sum_{i=1}^{N}\sum_{d=1}^{D}\left[\nabla_{d}F(x_{i}^{(t-1)})-\nabla_{d}F(\bar{x}_{i}^{(t-1)})\right]^{2}$ (39) $\displaystyle=\frac{1}{T}\sum_{t=1}^{T}\sum_{i=1}^{N}\left\|{\nabla F(x_{i}^{(t-1)})-\nabla F(\bar{x}_{i}^{(t-1)})}\right\|_{2}^{2}$ $\displaystyle\leq\frac{L^{2}}{T}\sum_{t=1}^{T}\sum_{i=1}^{N}\left\|{x_{i}^{(t-1)}-\bar{x}^{(t-1)}}\right\|_{2}^{2}$ $\displaystyle=\frac{L^{2}}{T}\sum_{t=1}^{T}\sum_{d=1}^{D}\left\|{\mathbf{x}_{d}^{(t-1)}-\bar{\mathbf{x}}_{d}^{(t-1)}}\right\|_{2}^{2}$ $$

Plugging ([38](#A2.E38)) to ([39](#A2.E39)), we have

$$ $\frac{1}{T}\sum_{t=1}^{T}\sum_{i=1}^{N}\sum_{d=1}^{D}\left[\nabla_{d}F_{i}(x_{i}^{(t-1)})-\nabla_{d}F(\bar{x}_{i}^{(t-1)})\right]^{2}\leq\frac{2(1+\lambda^{2})\alpha^{2}NL^{2}D}{(1-\lambda^{2})^{2}(1-\beta_{2})}\left[\frac{1}{T}\ln\left(1+\frac{R^{2}}{\epsilon(1-\beta_{2})}\right)-\ln(\beta_{2})\right],$ (40) $$

which completes the proof of Lemma [3](#A2.SS3.SSS2.Px3).
∎

###### Proof.

#### B.3.3 Main proof of Theorem B.1

From Assumption [1](#Thmassumption1), we have

$$ $F\left(\bar{x}^{(t)}\right)\leq F\left(\bar{x}^{(t-1)}\right)+\nabla F\left(\bar{x}^{(t-1)}\right)^{\top}\left(\bar{x}^{(t)}-\bar{x}^{(t-1)}\right)+\frac{L}{2}\left\|{\bar{x}^{(t)}-\bar{x}^{(t-1)}}\right\|_{2}^{2}.$ (41) $$

By substituting equation [13](#A2.E13) into equation [41](#A2.E41) and taking the conditional expectation on both sides, we have

$$ $\displaystyle\mathbb{E}_{t-1}\left[F\left(\bar{x}^{(t)}\right)\right]$ $\displaystyle\leq F\left(\bar{x}^{(t-1)}\right)-\frac{\alpha_{t}}{N}\sum_{d=1}^{D}\mathbb{E}_{t-1}\left[\nabla_{d}F\left(\bar{x}^{(t-1)}\right)^{\top}\sum_{i=1}^{N}\frac{\nabla_{d}f_{i}\left(x_{i}^{(t-1)}\right)}{\sqrt{\epsilon+v_{i,d}^{(t)}}}\right]$ (42) $\displaystyle\ \ \ +\frac{L\alpha_{t}^{2}}{2}\sum_{d=1}^{D}\mathbb{E}_{t-1}\left[\left\|{\frac{1}{N}\sum_{i=1}^{N}\frac{\nabla_{d}f_{i}(x_{i}^{(t-1)})}{\sqrt{\epsilon+v_{i,d}^{(t)}}}}\right\|_{2}^{2}\right].$ $$

By applying ([10](#A2.E10)) to ([42](#A2.E42)) and letting

$$ $a_{i}=\frac{\nabla_{d}f_{i}(x_{i}^{(t-1)})}{N\sqrt{\epsilon+v_{i,d}^{(t)}}},$ $$

we have

$$ $\displaystyle\mathbb{E}_{t-1}\left[F\left(\bar{x}^{(t)}\right)\right]$ $\displaystyle\leq F\left(\bar{x}^{(t-1)}\right)-\frac{\alpha_{t}}{N}\sum_{d=1}^{D}\mathbb{E}_{t-1}\left[\nabla_{d}F\left(\bar{x}^{(t-1)}\right)^{\top}\sum_{i=1}^{N}\frac{\nabla_{d}f_{i}\left(x_{i}^{(t-1)}\right)}{\sqrt{\epsilon+v_{i,d}^{(t)}}}\right]$ (43) $\displaystyle\ \ \ +\frac{L\alpha_{t}^{2}}{2N}\sum_{d=1}^{D}\mathbb{E}_{t-1}\left[\sum_{i=1}^{N}\frac{\left[\nabla_{d}f_{i}(x_{i}^{(t-1)})\right]^{2}}{\epsilon+v_{i,d}^{(t)}}\right].$ $$

By applying Lemma [1](#A2.SS3.SSS2.Px1) to ([43](#A2.E43)), we have

$$ $\displaystyle\mathbb{E}_{t-1}\left[F\left(\bar{x}^{(t)}\right)\right]$ $\displaystyle\leq F\left(\bar{x}^{(t-1)}\right)\underbrace{-\frac{\alpha_{t}}{4N}\sum_{d=1}^{D}\sum_{i=1}^{N}\frac{\left[\nabla_{d}F\left(\bar{x}^{(t-1)}\right)\right]^{2}}{\sqrt{\epsilon+\tilde{v}_{i,d}^{(t)}}}}_{A}$ (44) $\displaystyle\ \ \ +\frac{\alpha_{t}}{N}\sum_{d=1}^{D}\sum_{i=1}^{N}\frac{\left[\nabla_{d}F_{i}\left(x_{i}^{(t-1)}\right)-\nabla_{d}F\left(\bar{x}^{(t-1)}\right)\right]^{2}}{\sqrt{\epsilon+\tilde{v}^{(t)}_{i,d}}}$ $\displaystyle\ \ \ +\left(\frac{2\alpha_{t}R}{N}+\frac{L\alpha_{t}^{2}}{2N}\right)\sum_{d=1}^{D}\mathbb{E}_{t-1}\left[\sum_{i=1}^{N}\frac{\left[\nabla_{d}f_{i}(x_{i}^{(t-1)})\right]^{2}}{\epsilon+v_{i,d}^{(t)}}\right].$ $$

Now we focus on the term $A$ in ([44](#A2.E44)). From Assumption [2](#Thmassumption2), we have $\sqrt{\epsilon+\tilde{v}_{i,d}^{(t)}}\leq R\sqrt{\frac{1-\beta_{2}^{t}}{1-\beta_{2}}}$, and recall that $\alpha_{t}=\alpha\sqrt{\frac{1-\beta_{2}^{t}}{1-\beta_{2}}}$.
Then we have

$$ $A\leq-\frac{\alpha}{4R}\sum_{d=1}^{D}\left(\nabla_{d}F(\bar{x}^{(t-1)})\right)^{2}=-\frac{\alpha}{4R}\left\|{\nabla_{d}F(\bar{x}^{(t-1)})}\right\|_{2}^{2}.$ (45) $$

Given the fact that $\alpha_{t}\leq\frac{\alpha}{\sqrt{1-\beta_{2}}}$, by plugging ([45](#A2.E45)) into ([44](#A2.E44)), we have

$$ $\displaystyle\mathbb{E}_{t-1}\left[F\left(\bar{x}^{(t)}\right)\right]$ $\displaystyle\leq F\left(\bar{x}^{(t-1)}\right)-\frac{\alpha}{4R}\left\|{\nabla_{d}F(\bar{x}^{(t-1)})}\right\|_{2}^{2}$ (46) $\displaystyle\ \ \ +\frac{\alpha}{N\sqrt{1-\beta_{2}}}\sum_{d=1}^{D}\sum_{i=1}^{N}\frac{\left[\nabla_{d}F_{i}\left(x_{i}^{(t-1)}\right)-\nabla_{d}F\left(\bar{x}^{(t-1)}\right)\right]^{2}}{\sqrt{\epsilon+\tilde{v}^{(t)}_{i,d}}}$ $\displaystyle\ \ \ +\left(\frac{2\alpha R}{N\sqrt{1-\beta_{2}}}+\frac{L\alpha^{2}}{2N(1-\beta_{2})}\right)\sum_{d=1}^{D}\mathbb{E}_{t-1}\left[\sum_{i=1}^{N}\frac{\left[\nabla_{d}f_{i}(x_{i}^{(t-1)})\right]^{2}}{\epsilon+v_{i,d}^{(t)}}\right].$ $$

By taking the total expectation and summing up ([46](#A2.E46)) over $t\in[T]$, we have

$$ $\displaystyle\mathbb{E}\left[F\left(\bar{x}^{(T)}\right)\right]$ $\displaystyle\leq F\left(\bar{x}^{(0)}\right)-\frac{\alpha}{4R}\sum_{t=1}^{T}\left\|{\nabla_{d}F(\bar{x}^{(t-1)})}\right\|_{2}^{2}$ (47) $\displaystyle\ \ \ +\underbrace{\frac{\alpha}{N\sqrt{1-\beta_{2}}}\sum_{t=1}^{T}\sum_{d=1}^{D}\sum_{i=1}^{N}\frac{\left[\nabla_{d}F_{i}\left(x_{i}^{(t-1)}\right)-\nabla_{d}F\left(\bar{x}^{(t-1)}\right)\right]^{2}}{\sqrt{\epsilon+\tilde{v}^{(t)}_{i,d}}}}_{B}$ $\displaystyle\ \ \ +\underbrace{\left(\frac{2\alpha R}{N\sqrt{1-\beta_{2}}}+\frac{L\alpha^{2}}{2N(1-\beta_{2})}\right)\sum_{t=1}^{T}\sum_{d=1}^{D}\mathbb{E}_{t-1}\left[\sum_{i=1}^{N}\frac{\left[\nabla_{d}f_{i}(x_{i}^{(t-1)})\right]^{2}}{\epsilon+v_{i,d}^{(t)}}\right]}_{C}.$ $$

By applying Lemma [2](#A2.SS3.SSS2.Px2) for each $d\in[D]$ on $C$, we have

$$ $\displaystyle C$ $\displaystyle\leq\left(\frac{2\alpha R}{N\sqrt{1-\beta_{2}}}+\frac{L\alpha^{2}}{2N(1-\beta_{2})}\right)\sum_{d=1}^{D}\sum_{i=1}^{N}\left[\ln\left(1+\frac{v_{i,d}^{(t)}}{\epsilon}\right)-T\ln(\beta_{2})\right]$ (48) $\displaystyle\leq\left(\frac{2\alpha R}{N\sqrt{1-\beta_{2}}}+\frac{L\alpha^{2}}{2N(1-\beta_{2})}\right)\sum_{d=1}^{D}\sum_{i=1}^{N}\left[\ln\left(1+\frac{R^{2}}{\epsilon(1-\beta_{2})}\right)-T\ln(\beta_{2})\right]$ $\displaystyle=\left(\frac{2\alpha DR}{\sqrt{1-\beta_{2}}}+\frac{DL\alpha^{2}}{2(1-\beta_{2})}\right)\left[\ln\left(1+\frac{R^{2}}{\epsilon(1-\beta_{2})}\right)-T\ln(\beta_{2})\right].$ $$

Given that $\sqrt{\epsilon+\tilde{v}_{i,d}^{(t)}}>\sqrt{\epsilon}$, by applying Lemma [3](#A2.SS3.SSS2.Px3) on $B$ in ([47](#A2.E47)), we have

$$ $B\leq\frac{2(1+\lambda^{2})\alpha^{3}L^{2}D}{(1-\lambda^{2})^{2}(1-\beta_{2})^{3/2}\sqrt{\epsilon}}\left[\ln\left(1+\frac{R^{2}}{\epsilon(1-\beta_{2})}\right)-T\ln(\beta_{2})\right].$ (49) $$

By plugging ([49](#A2.E49)) and ([48](#A2.E48)) into ([47](#A2.E47)), we have

$$ $\frac{1}{T}\sum_{t=1}^{T}\left\|{\nabla_{d}F(\bar{x}^{(t-1)})}\right\|_{2}^{2}\leq\frac{4R}{\alpha T}\left[F\left(\bar{x}^{(0)}\right)-F_{*}\right]+\frac{1}{T}\zeta\left[\ln\left(1+\frac{R^{2}}{\epsilon(1-\beta_{2})}\right)-T\ln(\beta_{2})\right],$ (50) $$

where

$$ $E:=\frac{8DR^{2}}{\sqrt{1-\beta_{2}}}+\frac{2DLR\alpha}{(1-\beta_{2})}+\frac{8(1+\lambda^{2})\alpha^{2}L^{2}DR}{(1-\lambda^{2})^{2}(1-\beta_{2})^{3/2}\sqrt{\epsilon}}.$ (51) $$

which completes the proof of Theorem [B.1](#A2.Thmtheorem1).

### B.4 Proof of Theorem 4.1 : Decentralized Adam with heavy-ball momentum

#### B.4.1 Algorithm update under analysis

With heavy-ball momentum, we set $0<\beta_{1}<\beta_{2}<1$. We have the algorithm update under analysis is

$$ $\displaystyle g_{i}^{(t)}=\nabla\ell(x_{i}^{(t-1)};\xi_{i}^{(t)}),\ \ m_{i,d}^{(t)}=\beta_{1}m_{i,d}^{(t-1)}+g_{i,d}^{(t)},\ \ v_{i,d}^{(t)}=\beta_{2}v_{i,d}^{(t-1)}+\left[g_{i,d}^{(t)}\right]^{2},$ (52) $\displaystyle\alpha_{t}=\alpha(1-\beta_{1})\sqrt{\frac{1-\beta_{2}^{t}}{1-\beta_{2}}},\ \ x_{i,d}^{(t)}=-\alpha_{t}\frac{m_{i,d}^{(t)}}{\sqrt{\epsilon+v_{i,d}^{(t)}}}+\sum_{j\in\mathcal{N}_{i}}w_{ij}x_{j,d}^{(t-1)}$ $$

It should be noted that there is a modification on $\alpha_{t}$, which should originally be $\alpha_{t}=\alpha\frac{1-\beta_{1}}{1-\beta_{1}^{t}}\sqrt{\frac{1-\beta_{2}^{t}}{1-\beta_{2}}}$. However, $1-\beta_{2}^{t}$ could potentially make the learning rate non-monotonic. Since replacing it by $1$ has little practical influence, to simplify the proof, we replace it by $1$ as in Défossez et al. ().

The (virtual) update of the globally averaged weights is

$$ $\bar{x}_{d}^{(t)}=-\frac{\alpha_{t}}{N}\sum_{i=1}^{N}\frac{m_{i,d}^{(t)}}{\sqrt{\epsilon+v_{i,d}^{(t)}}}+\bar{x}_{d}^{(t-1)}.$ (53) $$

We denote $\tilde{v}_{i}^{(t)}\in\mathbb{R}^{D}$ as $\tilde{v}_{i}^{(t)}=\beta_{2}v_{i}^{(t-1)}+\mathbb{E}_{t-1}\left[\left(g_{i,d}^{(t)}\right)^{2}\right]$ which differs from $v_{i,d}^{(t)}$ by replacing the last term with its conditional expectation.
In addition, we denote

$$ $\displaystyle\bar{G}_{d}^{(t)}:=\nabla_{d}F\left(\bar{x}^{(t-1)}\right)=\frac{1}{N}\sum_{i=1}^{N}\nabla_{d}F_{i}\left(\bar{x}^{(t-1)}\right)\quad\text{and}\quad G_{i,d}^{(t)}:=\nabla_{d}F_{i}(x_{i}^{(t-1)}).$ (54) $$

We denote the $d$-th dimension of the local update of the $i$-th local model at $t$-th iteration without the heavy-ball momentum as

$$ $U_{i,d}^{(t)}:=\frac{g_{i,d}^{(t)}}{\sqrt{\epsilon+v_{i,d}^{(t)}}}.$ $$

We denote the $d$-th dimension of the local update of the $i$-th local model at $t$-th iteration with the heavy-ball momentum as

$$ $u_{i,d}^{(t)}:=\frac{m_{i,d}^{(t)}}{\sqrt{\epsilon+v_{i,d}^{(t)}}}=\frac{1}{\sqrt{\epsilon+v_{i,d}^{(t)}}}\sum_{k=0}^{t-1}\beta_{2}^{k}g_{i,d}^{(t-k)}.$ $$

By replacing the last $k$ terms in $v_{i,d}^{(t)}$ with their expectation, we denote $\tilde{v}_{i,d}^{(t,k)}$ as

$$ $\tilde{v}_{i,d}^{(t,k)}:=\beta_{2}^{k}v_{i,d}^{(t-k)}+\mathbb{E}_{t-k-1}\left[\sum_{j=t-k+1}^{t}\beta_{2}^{t-j}\left(g_{i,d}^{(j)}\right)^{2}\right].$ (55) $$

#### B.4.2 Technical lemmas

##### Lemma 4 (adaptive update with momentum approximately follow a descent direction)

$$ $\displaystyle\kappa$ $\displaystyle\geq\frac{1}{4}\sum_{d=1}^{D}\sum_{k=0}^{t-1}\beta_{1}^{k}\sum_{i=1}^{N}\mathbb{E}\left[\frac{\left(\bar{G}_{d}^{(t-k)}\right)^{2}}{\sqrt{\epsilon+\tilde{v}_{i,d}^{(t,k)}}}\right]-\sum_{d=1}^{D}\sum_{k=0}^{t-1}\beta_{1}^{k}\sum_{i=1}^{N}\mathbb{E}\left[\frac{\left(G_{i,d}^{(t-k)}-\bar{G}_{d}^{(t-k)}\right)^{2}}{\sqrt{\epsilon+\tilde{v}_{i,d}^{(t,k)}}}\right]$ (56) $\displaystyle\ \ \ -\frac{3R}{\sqrt{1-\beta_{1}}}\sum_{k=0}^{t-1}\left(\frac{\beta_{1}}{\beta_{2}}\right)^{k}\sqrt{k+1}\sum_{i=1}^{N}\mathbb{E}\left[\left\|{U_{i}^{(t-k)}}\right\|_{2}^{2}\right]-\frac{\alpha_{t}^{2}L^{2}\sqrt{1-\beta_{1}}}{4R}\sum_{i=1}^{N}\sum_{l=1}^{t-1}\mathbb{E}\left[\left\|{u_{i}^{(t-l)}}\right\|_{2}^{2}\right]\sum_{k=l}^{t-1}\beta_{1}^{k}\sqrt{k},$ $$

where

$$ $\kappa=\mathbb{E}\left[\sum_{d=1}^{D}\bar{G}_{d}^{(t)}\left(\sum_{i=1}^{N}\frac{m_{i,d}^{(t)}}{\sqrt{\epsilon+v_{i,d}^{(t)}}}\right)\right].$ (57) $$

###### Proof.

According to the definition of $\kappa$, we have

$$ $\displaystyle\kappa$ $\displaystyle=\sum_{d=1}^{D}\sum_{k=0}^{t-1}\beta_{1}^{k}\bar{G}_{d}^{(t)}\sum_{i=1}^{N}\frac{g_{i,d}^{(t-k)}}{\sqrt{\epsilon+v_{i,d}^{(t)}}}$ (58) $\displaystyle=\underbrace{\sum_{d=1}^{D}\sum_{k=0}^{t-1}\beta_{1}^{k}\bar{G}_{d}^{(t-k)}\sum_{i=1}^{N}\frac{g_{i,d}^{(t-k)}}{\sqrt{\epsilon+v_{i,d}^{(t)}}}}_{A}+\underbrace{\sum_{d=1}^{D}\sum_{k=0}^{t-1}\sum_{i=1}^{N}\beta_{1}^{k}\left(\bar{G}_{d}^{(t)}-\bar{G}_{d}^{(t-k)}\right)\frac{g_{i,d}^{(t-k)}}{\sqrt{\epsilon+v_{i,d}^{(t)}}}}_{B}.$ $$

Now focus on $B$. By applying the Young’s inequality equation [9](#A2.E9) and letting

$$ $\gamma=\frac{\sqrt{1-\beta_{1}}}{2R\sqrt{k+1}},a=\left|\bar{G}_{d}^{(t)}-\bar{G}_{d}^{(t-k)}\right|,b=\frac{\left|g_{i,d}^{(t-k)}\right|}{\sqrt{\epsilon+v_{i,d}^{(t)}}},$ $$

we have

$$ $|B|\leq\sum_{d=1}^{D}\sum_{k=0}^{t-1}\sum_{i=1}^{N}\beta_{1}^{k}\left[\frac{\sqrt{1-\beta_{1}}}{4R\sqrt{k+1}}\left(\bar{G}_{d}^{(t)}-\bar{G}_{d}^{(t-k)}\right)^{2}+\frac{R\sqrt{k+1}}{\sqrt{1-\beta_{1}}}\frac{\left(g_{i,d}^{(t-k)}\right)^{2}}{\epsilon+v_{i,d}^{(t)}}\right].$ (59) $$

Given the fact that $\epsilon+v_{i,d}^{(t)}\geq\epsilon+\beta_{2}^{k}v_{i,d}^{(t-k)}\geq\beta_{2}^{k}(\epsilon+v_{i,d}^{(t-k)})$, we have

$$ $\sum_{d=1}^{D}\frac{\left(g_{i,d}^{(t-k)}\right)^{2}}{\epsilon+v_{i,d}^{(t)}}\leq\frac{1}{\beta_{2}^{k}}\left\|{U_{i}^{(t-k)}}\right\|_{2}^{2}.$ (60) $$

By using Assumption [1](#Thmassumption1) and ([10](#A2.E10)), we have

$$ $\displaystyle\sum_{d=1}^{D}\left(\bar{G}_{d}^{(t)}-\bar{G}_{d}^{(t-k)}\right)^{2}$ $\displaystyle=\left\|{\bar{G}^{(t)}-\bar{G}^{(t-k)}}\right\|_{2}^{2}$ (61) $\displaystyle=\left\|{\nabla F\left(\bar{x}^{(t)}\right)-\nabla F\left(\bar{x}^{(t-k)}\right)}\right\|_{2}^{2}$ $\displaystyle\leq L^{2}\left\|{\frac{1}{N}\sum_{i=1}^{N}\sum_{l=1}^{k}\alpha_{t-l}u_{i}^{(t-l)}}\right\|_{2}^{2}$ $\displaystyle\leq\frac{\alpha_{t}^{2}L^{2}k}{N}\sum_{i=1}^{N}\sum_{l=1}^{k}\left\|{u_{i}^{(t-l)}}\right\|_{2}^{2}.$ $$

By plugging ([61](#A2.E61)) and ([60](#A2.E60)) back to ([59](#A2.E59)), and given that $k/\sqrt{k+1}\leq\sqrt{k}$ for $k\geq 0$, we have

$$ $\displaystyle|B|$ $\displaystyle\leq\left(\sum_{k=0}^{t-1}\frac{\alpha_{t}^{2}L^{2}\beta_{1}^{k}\sqrt{1-\beta_{1}}\sqrt{k}}{4R}\sum_{l=1}^{k}\sum_{i=1}^{N}\left\|{u_{i}^{(t-l)}}\right\|_{2}^{2}\right)+\left[\sum_{k=0}^{t-1}\frac{R\sqrt{k+1}}{\sqrt{1-\beta_{1}}}\left(\frac{\beta_{1}}{\beta_{2}}\right)^{k}\sum_{i=1}^{N}\left\|{U_{i}^{(t-k)}}\right\|_{2}^{2}\right]$ (62) $\displaystyle=\frac{\alpha_{t}^{2}L^{2}\sqrt{1-\beta_{1}}}{4R}\sum_{k=0}^{t-1}\beta_{1}^{k}\sqrt{k}\sum_{l=1}^{k}\sum_{i=1}^{N}\left\|{u_{i}^{(t-l)}}\right\|_{2}^{2}+\frac{R}{\sqrt{1-\beta_{1}}}\sum_{k=0}^{t-1}\sqrt{k+1}\left(\frac{\beta_{1}}{\beta_{2}}\right)^{k}\sum_{i=1}^{N}\left\|{U_{i}^{(t-k)}}\right\|_{2}^{2}$ $\displaystyle=\frac{\alpha_{t}^{2}L^{2}\sqrt{1-\beta_{1}}}{4R}\sum_{i=1}^{N}\sum_{l=1}^{t-1}\left\|{u_{i}^{(t-l)}}\right\|_{2}^{2}\sum_{k=l}^{t-1}\beta_{1}^{k}\sqrt{k}+\frac{R}{\sqrt{1-\beta_{1}}}\sum_{i=1}^{N}\sum_{k=0}^{t-1}\sqrt{k+1}\left(\frac{\beta_{1}}{\beta_{2}}\right)^{k}\left\|{U_{i}^{(t-k)}}\right\|_{2}^{2}.$ $$

Now focus on $A$ in ([58](#A2.E58)). Temporarily introduce the simplified notation as

$$ $\delta^{2}=\sum_{j=t-k}^{t}\beta_{2}^{t-j}\left(g_{i,d}^{(j)}\right)^{2},\ \ \ r^{2}=\mathbb{E}_{t-k-1}\left[\delta^{2}\right]$ $$

$$ $G:=G_{i,d}^{(t-k)},\ \ \ \bar{G}=\bar{G}_{d}^{(t-k)},\ \ \ g:=g_{i,d}^{(t-k)},\ \ \ v:=v_{i,d}^{(t)},\ \ \ \tilde{v}=\tilde{v}_{i,d}^{(t,k)}.$ $$

Then we have $\tilde{v}-v=r^{2}-\delta^{2}$.

Now focus on $A$ in ([58](#A2.E58)), with the new notation, we have

$$ $\displaystyle\mathbb{E}\left[\bar{G}_{d}^{(t-k)}\frac{g_{i,d}^{(t-k)}}{\sqrt{\epsilon+v_{i,d}^{(t)}}}\right]$ $\displaystyle=\mathbb{E}\left[\bar{G}g\left(\frac{1}{\sqrt{\epsilon+v}}\pm\frac{1}{\sqrt{\epsilon+\tilde{v}}}\right)\right]$ (63) $\displaystyle=\mathbb{E}\left[\mathbb{E}_{t-k-1}\left[\frac{\bar{G}g}{\sqrt{\epsilon+\tilde{v}}}\right]+\bar{G}g\frac{r^{2}-\delta^{2}}{\sqrt{\epsilon+v}\sqrt{\epsilon+\tilde{v}}(\sqrt{\epsilon+v}+\sqrt{\epsilon+\tilde{v}})}\right]$ $\displaystyle=\mathbb{E}\left[\underbrace{\frac{\bar{G}(G\pm\bar{G})}{\sqrt{\epsilon+\tilde{v}}}}_{C}+\underbrace{\bar{G}g\frac{r^{2}-\delta^{2}}{\sqrt{\epsilon+v}\sqrt{\epsilon+\tilde{v}}(\sqrt{\epsilon+v}+\sqrt{\epsilon+\tilde{v}})}}_{H}\right].$ $$

Now focus on $C$ in ([63](#A2.E63)). By applying the Young’s inequality equation [9](#A2.E9) and letting

$$ $\gamma=\frac{1}{2\sqrt{\epsilon+\tilde{v}}},\ \ \ a=\bar{G},\ \ \ b=\frac{G-\bar{G}}{\sqrt{\epsilon+\tilde{v}}},$ $$

then we have

$$ $\mathbb{E}[C]\geq\frac{3}{4}\mathbb{E}\left[\frac{\bar{G}^{2}}{\sqrt{\epsilon+\tilde{v}}}\right]-\mathbb{E}\left[\frac{(G-\bar{G})^{2}}{\sqrt{\epsilon+\tilde{v}}}\right].$ (64) $$

Now focus on $H$ in ([63](#A2.E63)). Given the fact that $\sqrt{\epsilon+v}>0$ and $\sqrt{\epsilon+\tilde{v}}>0$, we have

$$ $\displaystyle\sqrt{\epsilon+v}+\sqrt{\epsilon+\tilde{v}}$ $\displaystyle>\sqrt{\epsilon+v}\ \ \ \text{and}\ \ \ \sqrt{\epsilon+v}+\sqrt{\epsilon+\tilde{v}}$ $\displaystyle>\sqrt{\epsilon+\tilde{v}},$ (65) $$

and given that $|r^{2}-\delta^{2}|\leq r^{2}+\delta^{2}$, we have

$$ $|H|\leq|\bar{G}g|\frac{r^{2}}{\sqrt{\epsilon+v}(\epsilon+\tilde{v})}+|\bar{G}g|\frac{\delta^{2}}{\sqrt{\epsilon+\tilde{v}}(\epsilon+v)}.$ (66) $$

By applying the Young’s inequality equation [9](#A2.E9) to ([66](#A2.E66)) and letting

$$ $\gamma=\frac{\sqrt{1-\beta_{2}}\sqrt{\epsilon+\tilde{v}}}{2},\ \ \ a=\frac{|\bar{G}|}{\sqrt{\epsilon+\tilde{v}}},\ \ \ b=\frac{|g|r^{2}}{\sqrt{\epsilon+\tilde{v}}\sqrt{\epsilon+v}},$ $$

we have

$$ $\displaystyle|\bar{G}g|\frac{r^{2}}{\sqrt{\epsilon+v}(\epsilon+\tilde{v})}$ $\displaystyle\leq\frac{\sqrt{1-\beta_{2}}\bar{G}^{2}}{4\sqrt{\epsilon+\tilde{v}}}+\frac{g^{2}r^{4}}{\sqrt{1-\beta_{2}}(\epsilon+\tilde{v})^{3/2}(\epsilon+v)}$ (67) $\displaystyle\leq\frac{\bar{G}^{2}}{4\sqrt{\epsilon+\tilde{v}}}+\frac{g^{2}r^{4}}{\sqrt{1-\beta_{2}}(\epsilon+\tilde{v})^{3/2}(\epsilon+v)}.$ $$

Given that $\epsilon+\tilde{v}\geq r^{2}$ and taking the conditional expectation, we have

$$ $\mathbb{E}_{t-k-1}\left[|\bar{G}g|\frac{r^{2}}{\sqrt{\epsilon+v}(\epsilon+\tilde{v})}\right]\leq\frac{\bar{G}^{2}}{4\sqrt{\epsilon+\tilde{v}}}+\frac{r^{2}}{\sqrt{1-\beta_{2}}\sqrt{\epsilon+\tilde{v}}}\mathbb{E}_{t-k-1}\left[\frac{g^{2}}{\epsilon+v}\right].$ (68) $$

Now focus on the second term in ([66](#A2.E66)). By applying the Young’s inequality equation [9](#A2.E9) and letting

$$ $\gamma=\frac{\sqrt{1-\beta_{1}}\sqrt{\epsilon+\tilde{v}}}{2r^{2}},\ \ \ a=\frac{|\bar{G}\delta|}{\sqrt{\epsilon+\tilde{v}}},\ \ \ b=\frac{|g\delta|}{\epsilon+v},$ $$

we have

$$ $\displaystyle|\bar{G}g|\frac{\delta^{2}}{\sqrt{\epsilon+\tilde{v}}(\epsilon+v)}$ $\displaystyle\leq\frac{\bar{G}^{2}\delta^{2}\sqrt{1-\beta_{2}}}{4r^{2}\sqrt{\epsilon+\tilde{v}}}+\frac{g^{2}\delta^{2}r^{2}}{\sqrt{1-\beta_{2}}\sqrt{\epsilon+\tilde{v}}(\epsilon+v)^{2}}$ (69) $\displaystyle\leq\frac{\bar{G}^{2}\delta^{2}}{4r^{2}\sqrt{\epsilon+\tilde{v}}}+\frac{g^{2}\delta^{2}r^{2}}{\sqrt{1-\beta_{2}}\sqrt{\epsilon+\tilde{v}}(\epsilon+v)^{2}}.$ $$

Given that $\epsilon+v\geq\delta^{2}$ and $\mathbb{E}_{t-k-1}\left[\frac{\delta^{2}}{r^{2}}\right]=1$, after taking the conditional expectation, we have

$$ $\mathbb{E}_{t-k-1}\left[|\bar{G}g|\frac{\delta^{2}}{\sqrt{\epsilon+\tilde{v}}(\epsilon+v)}\right]\leq\frac{\bar{G}^{2}}{4\sqrt{\epsilon+\tilde{v}}}+\frac{r^{2}}{\sqrt{1-\beta_{2}}\sqrt{\epsilon+\tilde{v}}}\mathbb{E}_{t-k-1}\left[\frac{g^{2}}{\epsilon+v}\right].$ (70) $$

By plugging ([70](#A2.E70)) and ([68](#A2.E68)) back to ([66](#A2.E66)), we have

$$ $\mathbb{E}_{t-k-1}\left[|H|\right]\leq\frac{\bar{G}^{2}}{2\sqrt{\epsilon+\tilde{v}}}+\frac{2r^{2}}{\sqrt{1-\beta_{2}}\sqrt{\epsilon+\tilde{v}}}\mathbb{E}_{t-k-1}\left[\frac{g^{2}}{\epsilon+v}\right].$ (71) $$

Given that $r\leq\sqrt{\epsilon+\tilde{v}}$, and $r\leq\sqrt{k+1}R$ by Assumption [2](#Thmassumption2), we have

$$ $\mathbb{E}_{t-k-1}\left[|H|\right]\leq\frac{\bar{G}^{2}}{2\sqrt{\epsilon+\tilde{v}}}+\frac{2R\sqrt{k+1}}{\sqrt{1-\beta_{2}}}\mathbb{E}_{t-k-1}\left[\frac{g^{2}}{\epsilon+v}\right].$ (72) $$

By recovering the temporarily introduced notation, we have

$$ $\mathbb{E}_{t-k-1}\left[|H|\right]\leq\frac{\left(\bar{G}_{d}^{(t-k)}\right)^{2}}{2\sqrt{\epsilon+\tilde{v}_{i,d}^{(t,k)}}}+\frac{2R\sqrt{k+1}}{\sqrt{1-\beta_{2}}}\mathbb{E}_{t-k-1}\left[\frac{\left(g_{i,d}^{(t-k)}\right)^{2}}{\epsilon+v_{i,d}^{(t)}}\right].$ (73) $$

Given that $\epsilon+v_{i,d}^{(t)}\geq\epsilon+\beta_{2}^{k}v_{i,d}^{(t-k)}\geq\beta_{2}^{k}(\epsilon+v_{i,d}^{(t-k)})$, and by taking the complete expectation, we have

$$ $\mathbb{E}[|H|]\leq\frac{1}{2}\mathbb{E}\left[\frac{\left(\bar{G}_{d}^{(t-k)}\right)^{2}}{\sqrt{\epsilon+\tilde{v}_{i,d}^{(t,k)}}}\right]+\frac{2R\sqrt{k+1}}{\beta_{2}^{k}\sqrt{1-\beta_{2}}}\mathbb{E}\left[\frac{\left(g_{i,d}^{(t-k)}\right)^{2}}{\epsilon+v_{i,d}^{(t-k)}}\right].$ (74) $$

By plugging ([74](#A2.E74)) and ([64](#A2.E64)) back to ([63](#A2.E63)), we have

$$ $\displaystyle\mathbb{E}\left[\bar{G}_{d}^{(t-k)}\frac{g_{i,d}^{(t-k)}}{\sqrt{\epsilon+v_{i,d}^{(t)}}}\right]$ $\displaystyle\geq\frac{1}{4}\mathbb{E}\left[\frac{\left(\bar{G}_{d}^{(t-k)}\right)^{2}}{\sqrt{\epsilon+\tilde{v}_{i,d}^{(t,k)}}}\right]-\frac{2R\sqrt{k+1}}{\beta_{2}^{k}\sqrt{1-\beta_{2}}}\mathbb{E}\left[\frac{\left(g_{i,d}^{(t-k)}\right)^{2}}{\epsilon+v_{i,d}^{(t-k)}}\right]$ (75) $\displaystyle\ \ \ -\mathbb{E}\left[\frac{\left(G_{i,d}^{(t-k)}-\bar{G}_{d}^{(t-k)}\right)^{2}}{\sqrt{\epsilon+\tilde{v}_{i,d}^{(t,k)}}}\right].$ $$

By plugging ([75](#A2.E75)) back to $A$ in ([58](#A2.E58)), we have

$$ $\displaystyle\mathbb{E}[A]$ $\displaystyle\geq\frac{1}{4}\sum_{d=1}^{D}\sum_{k=0}^{t-1}\beta_{1}^{k}\sum_{i=1}^{N}\mathbb{E}\left[\frac{\left(\bar{G}_{d}^{(t-k)}\right)^{2}}{\sqrt{\epsilon+\tilde{v}_{i,d}^{(t,k)}}}\right]-\frac{2R}{\sqrt{1-\beta_{2}}}\sum_{d=1}^{D}\sum_{k=0}^{t-1}\beta_{1}^{k}\sum_{i=1}^{N}\frac{\sqrt{k+1}}{\beta_{2}^{k}}\mathbb{E}\left[\frac{\left(g_{i,d}^{(t-k)}\right)^{2}}{\epsilon+v_{i,d}^{(t-k)}}\right]$ (76) $\displaystyle\ \ \ -\sum_{d=1}^{D}\sum_{k=0}^{t-1}\beta_{1}^{k}\sum_{i=1}^{N}\mathbb{E}\left[\frac{\left(G_{i,d}^{(t-k)}-\bar{G}_{d}^{(t-k)}\right)^{2}}{\sqrt{\epsilon+\tilde{v}_{i,d}^{(t,k)}}}\right]$ $\displaystyle=\frac{1}{4}\sum_{d=1}^{D}\sum_{k=0}^{t-1}\beta_{1}^{k}\sum_{i=1}^{N}\mathbb{E}\left[\frac{\left(\bar{G}_{d}^{(t-k)}\right)^{2}}{\sqrt{\epsilon+\tilde{v}_{i,d}^{(t,k)}}}\right]-\frac{2R}{\sqrt{1-\beta_{2}}}\sum_{k=0}^{t-1}\left(\frac{\beta_{1}}{\beta_{2}}\right)^{k}\sqrt{k+1}\sum_{i=1}^{N}\mathbb{E}\left[\left\|{U_{i}^{(t-k)}}\right\|_{2}^{2}\right]$ $\displaystyle\ \ \ -\sum_{d=1}^{D}\sum_{k=0}^{t-1}\beta_{1}^{k}\sum_{i=1}^{N}\mathbb{E}\left[\frac{\left(G_{i,d}^{(t-k)}-\bar{G}_{d}^{(t-k)}\right)^{2}}{\sqrt{\epsilon+\tilde{v}_{i,d}^{(t,k)}}}\right].$ $$

By plugging ([76](#A2.E76)) and ([62](#A2.E62)) back to ([58](#A2.E58)), we have

$$ $\displaystyle\kappa$ $\displaystyle\geq\frac{1}{4}\sum_{d=1}^{D}\sum_{k=0}^{t-1}\beta_{1}^{k}\sum_{i=1}^{N}\mathbb{E}\left[\frac{\left(\bar{G}_{d}^{(t-k)}\right)^{2}}{\sqrt{\epsilon+\tilde{v}_{i,d}^{(t,k)}}}\right]-\sum_{d=1}^{D}\sum_{k=0}^{t-1}\beta_{1}^{k}\sum_{i=1}^{N}\mathbb{E}\left[\frac{\left(G_{i,d}^{(t-k)}-\bar{G}_{d}^{(t-k)}\right)^{2}}{\sqrt{\epsilon+\tilde{v}_{i,d}^{(t,k)}}}\right]$ (77) $\displaystyle\ \ \ -\frac{3R}{\sqrt{1-\beta_{2}}}\sum_{k=0}^{t-1}\left(\frac{\beta_{1}}{\beta_{2}}\right)^{k}\sqrt{k+1}\sum_{i=1}^{N}\mathbb{E}\left[\left\|{U_{i}^{(t-k)}}\right\|_{2}^{2}\right]-\frac{\alpha_{t}^{2}L^{2}\sqrt{1-\beta_{1}}}{4R}\sum_{i=1}^{N}\sum_{l=1}^{t-1}\mathbb{E}\left[\left\|{u_{i}^{(t-l)}}\right\|_{2}^{2}\right]\sum_{k=l}^{t-1}\beta_{1}^{k}\sqrt{k},$ $$

which completes the proof of Lemma [4](#A2.SS4.SSS2.Px1).
∎

###### Proof.

##### Lemma 5 (sum of ratios of the square of a decayed sum and a decayed sum of square)

Given $0<\beta_{1}<\beta_{2}\leq 1$ and a sequence of real number $(a_{n})_{n\in\mathbb{N}^{+}}$. We define $b_{n}=\sum_{j=1}^{n}\beta_{2}^{n-j}a_{j}^{2}$ and $c_{n}=\sum_{j=1}^{n}\beta_{1}^{n-j}a_{j}$. Then we have

$$ $\sum_{j=1}^{n}\frac{c_{j}^{2}}{\epsilon+b_{j}}\leq\frac{1}{(1-\beta_{1})(1-\beta_{1}/\beta_{2})}\left[\ln\left(1+\frac{b_{n}}{\epsilon}\right)-n\ln(\beta_{2})\right].$ (78) $$

###### Proof.

Refer to A.2 in Défossez et al. ().
∎

###### Proof.

##### Lemma 6 (sum of a geometric term times a square root)

Given $0<a<1$ and $Q\in\mathbb{N}$, we have

$$ $\sum_{q=0}^{Q-1}a^{q}\sqrt{q+1}\leq\frac{1}{1-a}\left(1+\frac{\sqrt{\pi}}{2\sqrt{-\ln(a)}}\right)\leq\frac{2}{(1-a)^{3/2}}.$ (79) $$

###### Proof.

Refer to A.3 in Défossez et al. ().
∎

###### Proof.

##### Lemma 7 (sum of a geometric term times a square root)

Given $0<a<1$ and $Q\in\mathbb{N}$, we have

$$ $\sum_{q=0}^{Q-1}a^{q}\sqrt{q}(q+1)\leq\frac{4a}{(1-a)^{5/2}}.$ (80) $$

###### Proof.

Refer to A.4 in Défossez et al. ().
∎

###### Proof.

##### Lemma 8 (with heavy-ball momentum, averaged consensus error is bounded if sampling from i.i.d. data distribution)

Under Assumptions [1](#Thmassumption1)–[3](#Thmassumption3), if $0<\beta_{1}<\beta_{2}<1$, we have

$$ $\frac{1}{T}\sum_{t=1}^{T}\sum_{i=1}^{N}\sum_{d=1}^{D}\left[G_{i,d}^{(t)}-\bar{G}_{d}^{(t)}\right]^{2}\leq\frac{2(1+\lambda^{2})(1-\beta_{1})\alpha^{2}NL^{2}D}{(1-\lambda^{2})^{2}(1-\beta_{2})(1-\beta_{1}/\beta_{2})}\left[\frac{1}{T}\ln\left(1+\frac{R^{2}}{(1-\beta_{2})\epsilon}\right)-\ln(\beta_{2})\right].$ (81) $$

###### Proof.

Proof of Lemma [8](#A2.SS4.SSS2.Px5) is similar to Lemma [3](#A2.SS3.SSS2.Px3).

Since the heavy-ball momentum is introduced, the definitions of $\mathbf{e}_{d}^{(t)}$ and $\bar{\mathbf{e}}_{d}^{(t)}$ are changed to

$$ $\mathbf{e}_{d}^{(t)}=-\alpha_{t}\left[\frac{m_{1,d}^{(t)}}{\sqrt{\epsilon+v_{1,d}^{(t)}}},\cdots,\frac{m_{N,d}^{(t)}}{\sqrt{\epsilon+v_{N,d}^{(t)}}}\right]\in\mathbb{R}^{N},$ $$

$$ $\bar{\mathbf{e}}_{d}^{(t)}=-\frac{\alpha_{t}}{N}\left[\sum_{i=1}^{N}\frac{m_{i,d}^{(t)}}{\sqrt{\epsilon+v_{i,d}^{(t)}}},\cdots,\sum_{i=1}^{N}\frac{m_{i,d}^{(t)}}{\sqrt{\epsilon+v_{i,d}^{(t)}}}\right]\in\mathbb{R}^{N}.$ $$

The proof is same as Lemma [3](#A2.SS3.SSS2.Px3) until ([36](#A2.E36)). Now we have

$$ $\displaystyle\sum_{t=1}^{T}\left\|{\mathbf{x}_{d}^{(t-1)}-\bar{\mathbf{x}}_{d}^{(t-1)}}\right\|_{2}^{2}$ $\displaystyle\leq\frac{2(1+\lambda^{2})}{(1-\lambda^{2})^{2}}\sum_{t=1}^{T}\left\|{\mathbf{e}_{d}^{(t)}}\right\|_{2}^{2}.$ (82) $$

By applying Lemma [5](#A2.SS4.SSS2.Px2), and given the fact that $\alpha_{T}\leq\alpha\frac{1-\beta_{1}}{\sqrt{1-\beta_{2}}}$, we have

$$ $\displaystyle\sum_{t=1}^{T}\left\|{\mathbf{e}_{d}^{(t)}}\right\|_{2}^{2}$ $\displaystyle=\sum_{i=1}^{N}\sum_{t=1}^{T}\alpha_{t}^{2}\frac{\left(m_{i,d}^{(t)}\right)^{2}}{\epsilon+v_{i,d}^{(t)}}$ (83) $\displaystyle\leq\frac{(1-\beta_{1})^{2}\alpha^{2}}{1-\beta_{2}}\sum_{i=1}^{N}\frac{1}{(1-\beta_{1})(1-\beta_{1}/\beta_{2})}\left[\ln\left(1+\frac{v_{i,d}^{(T)}}{\epsilon}\right)-T\ln(\beta_{2})\right].$ $$

By using Assumption [2](#Thmassumption2), it is given that $v_{i,d}^{(T)}\leq R^{2}/(1-\beta_{2})$. Then we have

$$ $\sum_{t=1}^{T}\left\|{\mathbf{e}_{d}^{(t)}}\right\|_{2}^{2}\leq\frac{(1-\beta_{1})\alpha^{2}N}{(1-\beta_{2})(1-\beta_{1}/\beta_{2})}\left[\ln\left(1+\frac{R^{2}}{(1-\beta_{2})\epsilon}\right)-T\ln(\beta_{2})\right].$ (84) $$

By plugging ([84](#A2.E84)) back to ([82](#A2.E82)) and ([39](#A2.E39)), we have

$$ $\frac{1}{T}\sum_{t=1}^{T}\sum_{i=1}^{N}\sum_{d=1}^{D}\left[G_{i,d}^{(t)}-\bar{G}_{d}^{(t)}\right]^{2}\leq\frac{2(1+\lambda^{2})(1-\beta_{1})\alpha^{2}NL^{2}D}{(1-\lambda^{2})^{2}(1-\beta_{2})(1-\beta_{1}/\beta_{2})}\left[\frac{1}{T}\ln\left(1+\frac{R^{2}}{(1-\beta_{2})\epsilon}\right)-\ln(\beta_{2})\right],$ (85) $$

which completes the proof of Lemma [8](#A2.SS4.SSS2.Px5).
∎

###### Proof.

#### B.4.3 Main proof of Theorem 4.1

Firstly introduce the notation $\Omega_{t}$ as

$$ $\Omega_{t}=\sqrt{\sum_{j=0}^{t-1}\beta_{2}^{j}}\ \ \ \Rightarrow\ \ \ \alpha_{t}=(1-\beta_{1})\Omega_{t}\alpha.$ $$

By using Assumption [1](#Thmassumption1), we have

$$ $F\left(\bar{x}^{(t)}\right)\leq F\left(\bar{x}^{(t-1)}\right)+\nabla F\left(\bar{x}^{(t-1)}\right)^{\top}\left(\bar{x}^{(t)}-\bar{x}^{(t-1)}\right)+\frac{L}{2}\left\|{\bar{x}^{(t)}-\bar{x}^{(t-1)}}\right\|_{2}^{2}.$ (86) $$

By using ([10](#A2.E10)) and taking the complete expectation, we have

$$ $\displaystyle\mathbb{E}\left[F\left(\bar{x}^{(t)}\right)\right]$ $\displaystyle\leq\mathbb{E}\left[F\left(\bar{x}^{(t-1)}\right)\right]-\frac{\alpha_{t}}{N}\mathbb{E}\left[\sum_{d=1}^{D}\nabla_{d}F\left(\bar{x}^{(t-1)}\right)\sum_{i=1}^{N}\frac{m_{i,d}^{(t)}}{\sqrt{\epsilon+v_{i,d}^{(t)}}}\right]+\frac{L\alpha_{t}^{2}}{2N^{2}}\mathbb{E}\left[\left\|{\sum_{i=1}^{N}u_{i}^{(t)}}\right\|_{2}^{2}\right]$ (87) $\displaystyle\leq\mathbb{E}\left[F\left(\bar{x}^{(t-1)}\right)\right]-\frac{\alpha_{t}}{N}\mathbb{E}\left[\sum_{d=1}^{D}\nabla_{d}F\left(\bar{x}^{(t-1)}\right)\sum_{i=1}^{N}\frac{m_{i,d}^{(t)}}{\sqrt{\epsilon+v_{i,d}^{(t)}}}\right]+\frac{L\alpha_{t}^{2}}{2N}\sum_{i=1}^{N}\mathbb{E}\left[\left\|{u_{i}^{(t)}}\right\|_{2}^{2}\right].$ $$

From Assumption [2](#Thmassumption2), we have $\sqrt{\epsilon+\tilde{v}_{i,d}^{(t,k)}}\leq R\Omega_{t}$, and by applying Lemma [4](#A2.SS4.SSS2.Px1), we have

$$ $\displaystyle\mathbb{E}\left[F\left(\bar{x}^{(t)}\right)\right]$ $\displaystyle\leq\mathbb{E}\left[F\left(\bar{x}^{(t-1)}\right)\right]-\frac{\alpha_{t}}{4R\Omega_{t}}\sum_{k=0}^{t-1}\beta_{1}^{k}\mathbb{E}\left[\left\|{\bar{G}^{(t-k)}}\right\|_{2}^{2}\right]$ (88) $\displaystyle\ \ \ +\frac{3R\alpha_{t}}{N\sqrt{1-\beta_{1}}}\sum_{k=0}^{t-1}\left(\frac{\beta_{1}}{\beta_{2}}\right)^{k}\sqrt{k+1}\sum_{i=1}^{N}\mathbb{E}\left[\left\|{U_{i}^{(t-k)}}\right\|_{2}^{2}\right]$ $\displaystyle\ \ \ +\frac{\alpha_{t}^{3}L^{2}\sqrt{1-\beta_{1}}}{4RN}\sum_{i=1}^{N}\sum_{l=1}^{t-1}\mathbb{E}\left[\left\|{u_{i}^{(t-l)}}\right\|_{2}^{2}\right]\sum_{k=l}^{t-1}\beta_{1}^{k}\sqrt{k}$ $\displaystyle\ \ \ +\frac{\alpha_{t}}{N}\sum_{d=1}^{D}\sum_{k=0}^{t-1}\beta_{1}^{k}\sum_{i=1}^{N}\mathbb{E}\left[\frac{\left(G_{i,d}^{(t-k)}-\bar{G}_{d}^{(t-k)}\right)^{2}}{\sqrt{\epsilon+\tilde{v}_{i,d}^{(t,k)}}}\right]+\frac{L\alpha_{t}^{2}}{2N}\sum_{i=1}^{N}\mathbb{E}\left[\left\|{u_{i}^{(t)}}\right\|_{2}^{2}\right].$ $$

By summing over all iterations $t\in[T]$, moving terms, and given that $\alpha_{t}$ is set to be non-decreasing, we have

$$ $\displaystyle\underbrace{\frac{1}{4R}\sum_{t=1}^{T}\frac{\alpha_{t}}{\Omega_{t}}\sum_{k=0}^{t-1}\beta_{1}^{k}\mathbb{E}\left[\left\|{\bar{G}_{d}^{(t-k)}}\right\|_{2}^{2}\right]}_{A}$ $\displaystyle\leq\mathbb{E}\left[F\left(\bar{x}^{(0)}\right)\right]-F_{*}+\underbrace{\frac{L\alpha_{T}^{2}}{2N}\sum_{i=1}^{N}\sum_{t=1}^{T}\mathbb{E}\left[\left\|{u_{i}^{(t)}}\right\|_{2}^{2}\right]}_{B}$ (89) $\displaystyle\ \ \ +\underbrace{\frac{\alpha_{T}^{3}L^{2}\sqrt{1-\beta_{1}}}{4RN}\sum_{i=1}^{N}\sum_{t=1}^{T}\sum_{l=1}^{t-1}\mathbb{E}\left[\left\|{u_{i}^{(t-l)}}\right\|_{2}^{2}\right]\sum_{k=l}^{t-1}\beta_{1}^{k}\sqrt{k}}_{C}$ $\displaystyle\ \ \ +\underbrace{\frac{3R\alpha_{T}}{N\sqrt{1-\beta_{1}}}\sum_{t=1}^{T}\sum_{k=0}^{t-1}\left(\frac{\beta_{1}}{\beta_{2}}\right)^{k}\sqrt{k+1}\sum_{i=1}^{N}\mathbb{E}\left[\left\|{U_{i}^{(t-k)}}\right\|_{2}^{2}\right]}_{H}$ $\displaystyle\ \ \ +\underbrace{\frac{\alpha_{T}}{N}\sum_{d=1}^{D}\sum_{k=0}^{t-1}\beta_{1}^{k}\sum_{i=1}^{N}\sum_{t=1}^{T}\mathbb{E}\left[\frac{\left(G_{i,d}^{(t-k)}-\bar{G}_{d}^{(t-k)}\right)^{2}}{\sqrt{\epsilon+\tilde{v}_{i,d}^{(t,k)}}}\right]}_{I}.$ $$

Now focus on $B$ in ([89](#A2.E89)). By using Lemma [5](#A2.SS4.SSS2.Px2), and given that $v_{i,d}^{(t)}\leq R^{2}/(1-\beta_{2})$ (from Assumption [2](#Thmassumption2)) and $\alpha_{T}\leq\alpha\frac{1-\beta_{1}}{\sqrt{1-\beta_{2}}}$, we have

$$ $B\leq\frac{DL\alpha^{2}(1-\beta_{1})}{2(1-\beta_{2})(1-\beta_{1}/\beta_{2})}\left[\ln\left(1+\frac{R^{2}}{(1-\beta_{2})\epsilon}\right)-T\ln(\beta_{2})\right].$ (90) $$

Now focus in $C$ in ([89](#A2.E89)). By introducing the index $j=t-l$, we have

$$ $C=\frac{\alpha_{T}^{3}L^{2}\sqrt{1-\beta_{1}}}{4RN}\sum_{i=1}^{N}\sum_{j=1}^{T}\mathbb{E}\left[\left\|{u_{i}^{(j)}}\right\|_{2}^{2}\right]\sum_{k=0}^{T-1}\beta_{1}^{k}\sqrt{k}(k+1).$ (91) $$

By applying Lemma [7](#A2.SS4.SSS2.Px4) and then Lemma [5](#A2.SS4.SSS2.Px2) (similar to ([90](#A2.E90))), we have

$$ $\displaystyle C$ $\displaystyle\leq\frac{\beta_{1}\alpha_{T}^{3}L^{2}}{(1-\beta_{1})^{2}RN}\sum_{i=1}^{N}\sum_{j=1}^{T}\mathbb{E}\left[\left\|{u_{i}^{(j)}}\right\|_{2}^{2}\right]$ (92) $\displaystyle\leq\frac{\beta_{1}\alpha_{T}^{3}L^{2}D}{(1-\beta_{1})^{3}(1-\beta_{1}/\beta_{2})R}\left[\ln\left(1+\frac{R^{2}}{(1-\beta_{2})\epsilon}\right)-T\ln(\beta_{2})\right]$ $\displaystyle\leq\frac{\beta_{1}\alpha^{3}L^{2}D}{(1-\beta_{1}/\beta_{2})(1-\beta_{2})^{3/2}R}\left[\ln\left(1+\frac{R^{2}}{(1-\beta_{2})\epsilon}\right)-T\ln(\beta_{2})\right].$ $$

Now focus on $H$ in ([89](#A2.E89)). By introducing the index $j=t-k$ (similar to ([91](#A2.E91))) and applying Lemma [6](#A2.SS4.SSS2.Px3) and then Lemma [2](#A2.SS3.SSS2.Px2), we have

$$ $\displaystyle H$ $\displaystyle=\frac{3R\alpha_{T}}{N\sqrt{1-\beta_{1}}}\sum_{i=1}^{N}\sum_{j=1}^{T}\mathbb{E}\left[\left\|{U_{i}^{(j)}}\right\|_{2}^{2}\right]\sum_{t=j}^{T}\left(\frac{\beta_{1}}{\beta_{2}}\right)^{t-j}\sqrt{1+t-j}$ (93) $\displaystyle\leq\frac{6R\alpha\sqrt{1-\beta_{1}}}{(1-\beta_{1}/\beta_{2})^{3/2}\sqrt{1-\beta_{2}}}\left[\ln\left(1+\frac{R^{2}}{(1-\beta_{2})\epsilon}\right)-T\ln(\beta_{2})\right].$ $$

Now focus on $I$ in ([89](#A2.E89)). Given that $\sqrt{\epsilon+\tilde{v}_{i,d}^{(t,k)}}\geq\sqrt{\epsilon}$, and by introducing index $j=t-k$, we have

$$ $\displaystyle I$ $\displaystyle\leq\frac{\alpha_{T}}{N\sqrt{\epsilon}}\sum_{i=1}^{N}\sum_{d=1}^{D}\sum_{j=1}^{T}\mathbb{E}\left[\left(G_{i,d}^{(j)}-\bar{G}_{d}^{(j)}\right)^{2}\right]\sum_{k=0}^{T-j}\beta_{1}^{k}$ (94) $\displaystyle\leq\frac{\alpha}{N\sqrt{\epsilon}\sqrt{1-\beta_{2}}}\sum_{i=1}^{N}\sum_{d=1}^{D}\sum_{j=1}^{T}\mathbb{E}\left[\left(G_{i,d}^{(j)}-\bar{G}_{d}^{(j)}\right)^{2}\right].$ $$

By applying Lemma [8](#A2.SS4.SSS2.Px5), we have

$$ $\displaystyle I$ $\displaystyle\leq\frac{2(1+\lambda^{2})\sqrt{1-\beta_{1}}\alpha^{3}L^{2}D}{(1-\lambda^{2})^{2}(1-\beta_{2})(1-\beta_{1}/\beta_{2})\sqrt{\epsilon}}\left[\ln\left(1+\frac{R^{2}}{(1-\beta_{2})\epsilon}\right)-T\ln(\beta_{2})\right].$ (95) $$

Now focus on $A$ in ([89](#A2.E89)). By introducing the index $j=t-k$, we have

$$ $\displaystyle A$ $\displaystyle=\frac{1}{4R}\sum_{t=1}^{T}\frac{\alpha_{t}}{\Omega_{t}}\sum_{k=0}^{t-1}\beta_{1}^{k}\mathbb{E}\left[\left\|{\bar{G}_{d}^{(t-k)}}\right\|_{2}^{2}\right]$ (96) $\displaystyle=\frac{\alpha(1-\beta_{1})}{4R}\sum_{j=1}^{T}\mathbb{E}\left[\left\|{\bar{G}_{d}^{(j)}}\right\|_{2}^{2}\right]\sum_{t=j}^{T}\beta_{1}^{t-j}$ $\displaystyle=\frac{\alpha}{4R}\sum_{j=1}^{T}(1-\beta_{1}^{T-j})\mathbb{E}\left[\left\|{\bar{G}_{d}^{(j)}}\right\|_{2}^{2}\right]$ $\displaystyle=\frac{\alpha}{4R}\sum_{j=1}^{T}(1-\beta_{1}^{T-j})\mathbb{E}\left[\left\|{\nabla F(\bar{x}^{(j)})}\right\|_{2}^{2}\right].$ $$

For any $T\in\mathbb{N}^{+}$, we define $\tau$ a random index with value $\{0,\cdots,T-1\}$ with distribution

$$ $\forall j\in\mathbb{N},j<T,\ \ \ \mathbb{P}[\tau=j]\propto 1-\beta_{1}^{T-j}.$ (97) $$

Then we have

$$ $\sum_{j=0}^{T-1}(1-\beta_{1}^{T-j})=T-\beta_{1}\frac{1-\beta_{1}^{T}}{1-\beta_{1}}\geq T-\frac{\beta_{1}}{1-\beta_{1}}.$ (98) $$

By introducing $\tilde{T}=T-\frac{\beta_{1}}{1-\beta_{1}}$, we have

$$ $A\geq\frac{\alpha\tilde{T}}{4R}\mathbb{E}\left[\left\|{\nabla F(\bar{x}^{(\tau)})}\right\|_{2}^{2}\right].$ (99) $$

By putting together ([99](#A2.E99)), ([95](#A2.E95)), ([93](#A2.E93)), ([92](#A2.E92)), and ([90](#A2.E90)) into ([89](#A2.E89)), we have

$$ $\mathbb{E}\left[\left\|{\nabla F(\bar{x}^{(\tau)})}\right\|_{2}^{2}\right]\leq\frac{4R}{\alpha\tilde{T}}\left(F(\bar{x}^{(0)})-F_{*}\right)+E\left[\frac{1}{\tilde{T}}\ln\left(1+\frac{R}{\epsilon(1-\beta_{2})}\right)-\frac{T}{\tilde{T}}\ln(\beta_{2})\right],$ (100) $$

where

$$ $\displaystyle E$ $\displaystyle:=\frac{2DLR(1-\beta_{1})\alpha}{(1-\beta_{2})(1-\beta_{1}/\beta_{2})}+\frac{4L^{2}D\beta_{1}\alpha^{2}}{(1-\beta_{1}/\beta_{2})(1-\beta_{2})^{3/2}}+\frac{24DR^{2}\sqrt{1-\beta_{1}}}{(1-\beta_{1}/\beta_{2})^{3/2}\sqrt{1-\beta_{2}}}$ $\displaystyle\ \ \ +\frac{8(1+\lambda^{2})RL^{2}D\sqrt{1-\beta_{1}}\alpha^{2}}{(1-\lambda^{2})^{2}(1-\beta_{2})(1-\beta_{1}/\beta_{2})\sqrt{\epsilon}},$ $$

which completes the proof of Theorem [4.1](#S4.Thmtheorem1).

## Appendix C Decentralized accumulated Adam

Algorithm [3](#alg3) describes the decentralized accumulated Adam. As is displayed in Section [5](#S5), the decentralized accumulated Adam demonstrates competitive practical performances for several training tasks compared to alternative methods.

Figure: Algorithm 3 Decentralized Accumulated Adam on worker $i$

To understand Algorithm [3](#alg3), let us introduce $\hat{t}$ to divide the sequence of iteration index $t$ into groups of every $s$ iterations:

$$ $\begin{array}[]{ccccc}t\in&\underbrace{1,\ldots,s},&\underbrace{s+1,\ldots,2s},&\ldots,&\underbrace{\left(\frac{T}{s}-1\right)s+1,\ldots,\frac{T}{s}s}\\ \hat{t}\in&1,&2,&\ldots,&\frac{T}{s}\end{array}$ $$

For a given iteration index $t$, it falls in the $\hat{t}=\lceil t/s\rceil$-th group, so that $m_{i}^{(t)}$ in Algorithm [3](#alg3) can be equivalently expressed as

$$ $m_{i}^{(t)}=(1-\beta_{1})\left(\beta_{1}^{0}g_{i}^{(t)}+\beta_{1}^{1}G_{i}^{(\hat{t}-1)}+\cdots+\beta_{1}^{\hat{t}-1}G_{i}^{(1)}\right),$ (101) $$

where $G_{i}^{(\hat{t})}:=\frac{1}{s}\left(g_{i}^{((\hat{t}-1)s+1)}+\cdots+g_{i}^{(\hat{t}s)}\right)$. The update of $v_{i}^{(t)}$ is similar.

Algorithm [3](#alg3) uses accumulated stochastic gradients to construct the first-order momentum $m_{i}^{(t)}$ and second-momentum $v_{i}^{(t)}$, which reduces the variance of the stochastic gradients while does not reduce the number of model updates, i.e., within $T$ stochastic gradient computations at worker $i$, the model $x_{i}^{(t)}$ is updated for $T$ instead of $T/s$ times. To see these, assume the empirically optimal batch size in a single-machine environment is $B$, and we call a batch of size $B$ a global mini-batch. The variance of the global mini-batch gradients for the global gradient $\nabla F$ is $\Sigma^{2}$. Under a decentralized setup, these $B$ batches are evenly distributed to $N$ workers, with each worker receiving $B/N$ samples, which we call a local mini-batch. Then, the variance of each worker’s local mini-batch gradient for the global gradient $\nabla F$ increases to $N\Sigma^{2}$. This increased variance exacerbates the consensus errors among workers. To compensate for the increased variance, a straightforward idea is to have each worker accumulate $s$ (proportional to $N$) local mini-batch random gradients before performing an update, which improves the variance to $\frac{N}{s}\Sigma^{2}$. However, this accumulation leads to a reduction in the number of model update iterations, i.e., within $T$ stochastic gradient computations, the number of model updates is $T/s$ instead of $T$. With a novel accumulation technique, this issue is avoided in Algorithm [3](#alg3). As described in Algorithm [3](#alg3), when a worker computes a local mini-batch $g_{i}^{(t)}$, it assigns it a weight of 1, adds it to the exponential averaging of all historical $G^{(1)}$ to $G^{(\hat{t}-1)}$ to generate $m_{i}^{(t)}$ and $v_{i}^{(t)}$, and updates the local model once. In this way, the number of updates is equal to $T$ instead of $T/s$.

Algorithm [3](#alg3) has close connections with existing well-known algorithms. On one hand, it performs exponential moving averaging over each group of $s$ stochastic gradients, which yields a higher weight of the oldest information compared to the vanilla Adam ($\beta_{1}^{\hat{t}-1}$ versus $\beta_{1}^{t-1}$; see equation [101](#A3.E101)). This technique is similar to SlowMo Wang et al. () that has been shown to be effective for DNN training. On the other hand, Algorithm [3](#alg3) updates the model upon receiving each $g_{i}^{t}$, which is similar to FedAvg Konečnỳ et al. (). It is worth noting that FedAvg does not communicate every iteration and may yield a lower communication cost compared to Algorithm [3](#alg3). Whether this technique can further accelerate Algorithm [3](#alg3) is a worthwhile research direction. We leave it as well as the convergence analysis of Algorithm [3](#alg3) as future work.

Similar to the changes in AdamW Loshchilov () compared with Adam, AccumAdam can also be similarly adapted to AccumAdamW.

## Appendix D Discussion and Limitation

Our analysis of the runtime model in Section [3](#S3) and convergence guarantees in § [4](#S4) show how the communication topology affects both the per-iteration runtime and the convergence. A sparser topology shortens the per-iteration runtime but may result in a topology with slower mixing and worse training results. Consistent with Kong et al. (), we have found that for a limited number of workers (32 or less), we can obtain significant runtime improvements by sparsifying the communication without affecting the quality of the final model. For a network with a large number of workers, the sparse topology plays a more important role and we may need to study the runtime and optimization aspects separately. Although decentralized training may face challenges with a large number of workers ($>64$), data parallelism is not the only approach for scaling up distributed training. For large language models, tensor parallelism and model parallelism are also crucial techniques, and the superiority of decentralized training in interleaving communication and computation can be a great complement to overall efficiency. In Shoeybi et al. (), for example, they used 64-way data parallel and 8-way model parallel to scale up the training to 512 GPUs. Additionally, in common machine learning workloads, too-small local batch size could lead to low utilization for a single GPU, and a 64-way data parallel is already sufficient for most tasks.

As for memory consumption, since the decentralized training has asynchronous communications, it is inevitable to allocate additional memory for the communication buffers to hide the time taken by communications. Similar implementations can be found in Assran et al. (), Wang et al. (). Even though the decentralized training allocates more memory, it is a trade-off between memory and per-iteration runtime if compared with All-Reduce training. Moreover, it should also be noted that more memory is spent on the backward pass and the optimizer states (like Adam Kingma & Ba ()). The additional memory usage can be alleviated by orthogonal techniques like compression.

In our experiments, we used a time-varying mixing matrix, but for ease of convergence analysis, we used a fixed one. Techniques from some works for time-varying topologies Nedic et al. (), Saadatniaki et al. (), Metelev et al. () can be applied here. Our accumulated Adam performs well in practice, but it lacks theoretical analysis. It could be finished by using the analysis techniques of the Adam method Zaheer et al. () and decentralized algorithms Yuan et al. (), Zeng & Yin ().

## Peer Reviews

confidence: 4
contribution: 2
initial_rating: 5
presentation: 3
questions: Detailed comments and questions:

Q1. The paper seems to ignore work on the decentralized setting since late 2020 to early 2021. Here are some of the many references that are missed:

- There is a lot of nice work by Anastasia Koloskova and co-authors on analyzing Gossip variants of SGD, many of which are missed:

1. Koloskova, Anastasia, et al. "A unified theory of decentralized sgd with changing topology and local updates." International Conference on Machine Learning. PMLR, 2020.

2. Koloskova, Anastasiia, Tao Lin, and Sebastian U. Stich. "An improved analysis of gradient tracking for decentralized machine learning." Advances in Neural Information Processing Systems 34 (2021): 11422-11435. 

See also:

Zhang, Jiaqi, and Keyou You. "Fully asynchronous distributed optimization with linear convergence in directed networks." arXiv preprint arXiv:1901.08215 (2019).

"SQuARM-SGD: Communication-Efficient Momentum SGD for Decentralized Optimization" by Navjot Singh et al. (2020)

In addition: 

- Nadiradze, Giorgi, et al. "Asynchronous decentralized SGD with quantized and local updates." Advances in Neural Information Processing Systems 34 (2021): 6829-6842.

This paper seems to be trying to do something similar to what is done here–decoupling communication from computation–but in some sense goes further since it also supports quantization and completely non-blocking reads. Even the experimental setup is very similar to the one presented in this paper, so I am surprised to see that there is no mention of this work whatsoever. 

- Similar work: 
 Li, Shigang, et al. "Breaking (global) barriers in parallel stochastic optimization with wait-avoiding group averaging." IEEE Transactions on Parallel and Distributed Systems 32.7 (2020): 1725-1739.

I would therefore recommend that the authors go over related work more thoroughly, and provide more complete positioning of their work relative to prior art. I don’t think the paper can be accepted in the absence of this. 

Q2: Are the loss improvements quoted in L488 (2.841 vs 2.846) actually statistically significant?

Q3: Is your setup really faster than just setting up large-batch SGD using e.g. FFCV on a single 4-GPU system?
soundness: 2
strengths: Strengths:

1. new perspectives on an “old” problem by today’s standards (decentralized training), from the point of view of modeling and adaptive optimization

2. analytical results are a plus

3. the experiments are fairly thorough
summary: The paper investigates decentralized training of DNNs. This used to be a fairly hot topic a few years ago (e.g. Lian et al 2017 and follow-up work), but has to some extent cooled down recently as models and workloads have changed, and model-parallelism has become more standard. 
The paper focuses on the classic data-parallel setting; its contributions are as follows: 

- An analytical model to understand what are the conditions under which decentralized training can bring gains.

- A decentralized version of Adam, which decouples computation from communication and provides convergence guarantees under fairly standard assumptions (for Adam) 

- An implementation of the algorithm and its technical evaluation. This is done fairly thoroughly, on systems with up to 64 GPUs, showing the method’s potential.
weaknesses: Weaknesses: 

1. unfortunately the paper seems to be completely missed some important related work in the area, which makes it very hard to position the paper properly in terms of its contribution 

2. more broadly, the experimental results are in a system parameter range that has been rendered somewhat obsolete by current-day systems, which are able to e.g. train ImageNet in minutes on a single node https://github.com/libffcv/ffcv

---

confidence: 3
contribution: 3
initial_rating: 8
presentation: 3
questions: The reviewer is curious about the intuition behind the runtime model: were the assumptions behind the model proposed previously by some other work or is this coming solely from the author?
soundness: 3
strengths: - This paper proposes to study an important, impactful problem (practical gap between DP and decentralized training)
- the accuracy of the model (ie how it captures real time speed discrepancies) is well illustrated
- the numerical experiments are extensive and thorough. There is a clear focus on transformer based architectures, making it relevant to challenges posed by modern LLMs.
- the version of decentralized Adam optimizer is thoroughly compared to other decentralized adam based methods
- the papers lists 3 factors that could explain the aforementioned discrepancy  1) overlapping communication and computation 2) heterogeneous communications costs 3) sensitivity to varying computation times. For each factor, an extensive investigation is proposed supported by numerical experiments.
summary: This paper investigates the gap between decentralized training of DNN and data parallel (DP) methods. 
In particularly, although decentralized training is theoretically superior to DP, certain network topologies make the use of this technique challenging. 
The present propose to quantify such gap through the use of a "runtime model".
Moreover, the author introduce a decentralized version of Adam particularly suited to the training of transformer based models.
Extensive numerical experiments illustrate the speedup investigation.
weaknesses: - the explanation/details of the runtime model in Appendix A.5 could be stated more clearly 
(the reviewers would like to respectfully suggest an explanation similar in spirit to the way Algorithm 1 is stated, although this is relatively minor)
- there is no clear link to the reviewer between the decentralized adam optimizer and the runtime model (please correct me if missed anything).

---

confidence: 3
contribution: 2
initial_rating: 8
presentation: 3
questions: Please refer to the weaknesses. 

It would be better to provide training convergence curves of using DAdam and the All-Reduce Adam on OpenWebText. 

Also, it is important to illustrate how the decentralized training is implemented, as the Pytorch and DeepSpeed have conducted many system optimizations on the All-Reduce, there should be some convincing illustrations to show that the implemented decentralized training can outperform the All-Reduce. Specifically, how the communication is launched, using torchrun or MPIRUN or something else? how the synchronization between different nodes is implemented, is there a distributed.barrier()? how the overlapping between communication and computation is implemented? How do you manage the communication topology? The source code with a document may be very helpful.

If these questions are addressed, I'd like to increase my score.
soundness: 3
strengths: 1. The authors provide a runtime model that quantifies key environmental parameters and estimates potential speedups, offering valuable insights into the conditions under which decentralized training is advantageous.
2. There is theoretical analysis to support the proposed algorithm.
3. The experiment consists of 64 GPUs, which is a suitable scale.
4. There is detailed hyper-parameter settings for reproducibility.
summary: The paper explores decentralized training of deep neural networks (DNNs) as an alternative to synchronous data-parallel methods like All-Reduce, which are known for their scalability issues. The authors identify three key factors that can lead to speedups in decentralized training: overlapping communication and computation, respecting heterogeneous communication costs, and reducing sensitivity to varying computation times. They propose a runtime model to optimize decentralized training configurations and design a decentralized variant of the Adam optimizer, called DAdam, which supports overlapping communications and computations. Additionally, they introduce an accumulation technique to mitigate the high variance caused by small local batch sizes.
weaknesses: 1. Some important related works in MLsys [1,2] are missed, in which the dynamic gossip communication topologies are also discussed, and the communication compression is utilized.
2. The novelty of the DAdam is limited. There is no improvements on the Adam itself. The proposed method can be seen as a system optimization instead of the optimizer itself. However, the systematic optimization including the overlapping between communication and computation is largely used in many ML systems [3,4].
3. While the paper presents extensive experiments, it lacks detailed ablation studies to isolate the impact of individual components of the proposed approach.
4. The tested topologies are limited.
5. For training GPT-2 on OpenWebText, it is unclear whether the final convergence of DAdam can match the All-Reduce Adam when training with more iterations. The convergence curves of training on OpenWebText are not provided.
6. There lacks enough details of how the decentralized training is implemented built upon PyTorch.


[1] GossipFL: A Decentralized Federated Learning Framework With Sparsified and Adaptive Communication. In TPDS 2022.
[2] Communication-efficient decentralized learning with sparsification and adaptive peer selection. In ICDCS 2020.
[3] Overlap Communication with Dependent Computation via Decomposition in Large Deep Learning Models. In ASPLOS 2022.
[4] Centauri: Enabling Efficient Scheduling for Communication-Computation Overlap in Large Model Training via Communication Partitioning. In ASPLOS 2024.

Meta-review: The paper studies decentralized training in the classic data parallel setting. It gives an analytical model to understand under what conditions decentralized training can bring gains. It also gives a relevant decentralized version of Adam, with a novel convergence analysis. Finally empirical results are convincing on realistic  settings with up to 64 GPUs.
Some concerns were raised about missing discussions of related work, which we hope authors will resolve in the final version.
All four reviewers ultimately recommend acceptance.

Decision: Accept (Poster)