Asynchronous stochastic gradient descent with decoupled backpropagation and layer-wise updates

## Abstract

Abstract The increasing size of deep learning models has created the need for more efficient alternatives to the standard error backpropagation algorithm, that make better use of asynchronous, parallel and distributed computing.
One major shortcoming of backpropagation is the interlocking between the forward phase of the algorithm, which computes a global loss, and the backward phase where the loss is back-propagated through all layers to compute the gradients, which are used to update the network parameters.
To address this problem, we propose a method that parallelises SGD updates across the layers of a model by asynchronously updating them from multiple threads.
Furthermore, since we observe that the forward pass is often much faster than the backward pass, we use separate threads for the forward and backward pass calculations, which allows us to use a higher ratio of forward to backward threads than the usual 1:1 ratio, reducing the overall staleness of the parameters.
Thus, our approach performs asynchronous stochastic gradient descent using separate threads for the loss (forward) and gradient (backward) computations and performs layer-wise partial updates to parameters in a distributed way.
We show that this approach yields close to state-of-the-art results while running up to 2.97 × 2.97\times 2.97 × faster than Hogwild! scaled on multiple devices (Locally-Partitioned-Asynchronous-Parallel SGD). We theoretically prove the convergence of the algorithm using a novel theoretical framework based on stochastic differential equations and the drift diffusion process, by modeling the asynchronous parameter updates as a stochastic process.

## 1 Introduction

Scaling up modern deep learning models requires massive resources and training time.
Asynchronous parallel and distributed methods for training them using backpropagation play a very important role in easing the demanding resource requirements for training these models.
Backpropagation (BP) (Werbos, ) has established itself as the de facto standard method for learning in deep neural networks (DNN).
Although BP achieves state-of-the-art accuracy on literally all relevant machine learning tasks, it comes with a number of inconvenient properties that prohibit an efficient implementation at scale.

BP is a two-phase synchronous learning strategy in which the first phase (forward pass) computes the training loss, $\mathcal{L}$, given the current network parameters and a batch of data.
In the second phase, the gradients are propagated backwards through the network to determine each parameter’s contribution to the error, using the same weights (transposed) as in the forward pass (see Equation 1).
BP suffers from update locking, where a layer can only be updated after the previous layer has been updated. Furthermore, the computation of gradients can only be started after the loss has been calculated in the forward pass.

Moreover, the backward pass usually requires approximately twice as long as the forward pass (Kumar et al., ).
The bulk of the computational load comes from the number of matrix multiplications required during each phase.
If we consider a DNN with $M$ layers, then at any layer $m\leq M$ with pre-activations
$\boldsymbol{z_{m}}=\boldsymbol{\theta}_{m}\boldsymbol{y_{m-1}}$ and post-activations $\boldsymbol{y_{m}}=f(\boldsymbol{z_{m-1}})$,
the computations during the forward pass are dominated by one matrix multiplication $\boldsymbol{\theta}_{m}\boldsymbol{y_{m-1}}$.
During the backward pass, the computations at layer $m$ are dominated by two matrix multiplications:

$$ $\frac{\partial\mathcal{L}}{\partial\boldsymbol{\theta}_{m}}=f^{{}^{\prime}}( \boldsymbol{\theta}_{m}\boldsymbol{y_{m-1}})\times\boldsymbol{y_{m-1}}^{\top} \quad\text{and}\quad\frac{\partial\mathcal{L}}{\partial\boldsymbol{y_{m-1}}}=f ^{{}^{\prime}}(\boldsymbol{\theta}_{m}\boldsymbol{y_{m-1}})\times\boldsymbol{ \theta}_{m}^{\top}\;,$ (1) $$

approximately doubling the compute budget required for the backward pass compared to the forward pass.
In Eq. 1, $\boldsymbol{\theta}_{m}$ denotes the network weights at layer $m$ and $f^{\prime}$ the partial derivative with respect to $\boldsymbol{\theta}_{m}$.
This imbalance between forward and backward phase further complicates an efficient parallelization of BP, particularly in heterogeneous settings.

In this work, we propose a new approach to parallelize training of deep networks on non-convex objective functions by asynchronously performing the forward and backward passes at a layer-wise granularity in multiple separate threads that make lock-free updates to the parameters in shared memory.
The lock-free updates address the locking problem, performing layer-wise updates mitigates the issue of conflicts between parameter updates, and performing the backward pass and updates using more threads than the forward pass mitigates the staleness problem. Specifically, the imbalance in execution time between forward and backward passes is taken care of by having twice as many backward threads than forward threads, breaking the 1:1 ratio of vanilla Backpropagation, therefore significantly speeding-up the training process.

In summary, the contributions of this paper are as follows:

- 1.
We introduce a novel asynchronous formulation of Backpropagation which allows the forward pass and the backward pass to be executed separately and in parallel, which allows us to run more backward than forward threads.
This approach accounts for the unequal time required by the forward and backward passes.
- 2.
We propose to asynchronously update the model’s parameters at a layer-wise granularity without using a locking mechanism which reduces staleness.
- 3.
We give convergence guarantees of the algorithm to a stationary distribution centered around the local optima of conventional BP.
- 4.
We show that the algorithm can reach state-of-the-art performances while being significantly faster than competing asynchronous algorithms.

## 2 Related Work

Asynchronous stochastic gradient descent (SGD).
Asynchronous SGD has a long history, starting from Baudet (); Bertsekas & Tsitsiklis ().
Hogwild! (Recht et al., ) allows multiple processes to perform SGD without any locking mechanism.
Kungurtsev et al. () proposed to partition the models parameters across the workers on the same device to perform SGD on the partitions.
Chatterjee et al. () decentralizes Hogwild! and PASSM+ to allow parameters or their partitions to be located on multiple devices and perform Local SGD on them. Zheng et al. () compensated the delayed gradients with a gradient approximation at the current parameters.
Unlike these methods, we don’t run multiple forward passes in parallel and don’t need any gradient compensation scheme.

Nadiradze et al. () provides a theoretical framework to derive convergence guarantees for a wide variety of distributed methods.
Mishchenko et al. () proposes a method of “virtual iterates” to provide convergence guarantees independent of delays.
More recently, Even et al. () proposed a unified framework for convergence analysis of distributed algorithms based on the AGRAF framework.
There have been lots of other analysis methods proposed for deriving convergence guarantees for asynchronous distributed SGD (see Assran et al. () for a survey).
In our work, we propose an entirely novel framework that hasn’t been used before based on stochastic differential equations, and provide convergence guarantees of the algorithm to a stationary distribution centered around the local optima of conventional BP.

Communication-efficient algorithms. One of the bottlenecks when training on multiple devices or nodes in parallel is the synchronization step. The bigger or deeper the models get, the more time is consumed by synchronization.
PowerSGD computes low-rank approximations of the gradients using power iteration methods.
Poseidon (Zhang et al., ) also factorizes gradients matrices but interleaves their communication with the backward pass.
Wen et al. () and Alistarh et al. () quantize gradients to make them lightweight for communication.
Like Zhang et al. (), we interleave the backward pass with gradients communication but without gradients averaging.

Block local learning.
Dividing the network across multiple devices and performing local updates is a widely recognized approach in distributed learning.
The backward passes of the different blocks can be done simultaneously.
The global loss is used to provide feedback only to the output block while the remaining blocks get learning signals from auxiliary networks which each compute local targets.
Ma et al. () uses a shallower version of the network as the auxiliary network at each layer.
Gomez et al. () allows gradients to flow to k-neighboring blocks.
Nøkland & Eidnes () don’t allow gradients to flow to neighboring blocks, and instead use an auxiliary matching loss and a local cross-entropy loss to compute the local error.
Decoupled Parallel Backpropagation (Huo et al., ) does full Backpropagation but uses stale gradients in the blocks to avoid update locking.
Kappel et al. () take a probabilistic approach by interpreting layers outputs as parameters of a probability distribution. Auxiliary networks provide local targets, which are used to train each block individually.
Similar to these distributed paradigms, we mimic the execution of multiple backward passes in parallel by reordering the training sequence but without splitting the network explicitly during forward and backward propagation.

## 3 Methods

Figure: Figure 1: Illustration of decoupled backpropagation with separate threads for the forward and backward passes and the layer-wise updates. For each thread, the order of computations for a sample network with three layers denoted L1, L2 and L3, are shown. Arrows denote dependencies across threads. Within each thread, the computations for each layer are performed sequentially, whereas across threads, the dependencies are layer-wise. Interactions for 2 backward threads and a single forward thread are shown. This asynchronous interaction, along with layer-wise updates, reduces the staleness of parameters.
Refer to caption: extracted/5909862/images/async.png

### 3.1 Asynchronous formulation of Backpropagation

We introduce a new asynchronous stochastic gradient descent method where, instead of performing the forward and backward phases sequentially, we execute them in parallel and perform layer-wise parameter updates as soon as the gradients for a given layer are available.
The dependencies between forward and backward phases are illustrated in Figure 1.

Since the gradient computation in the backward pass tends to consume more time than the loss calculation in the forward pass, we decouple these two into separate threads and use one forward thread and two backward threads to counterbalance the disproportionate execution time.

Figure 1 illustrates the interaction among threads based on one example. Initially, only the first forward pass, $F_{0}^{(0)}$, is performed. The resulting loss is
then used in the first backward pass $B^{(1)}_{0}$, which starts in parallel to the second forward pass $F_{1}^{(1)}$. Once $F_{1}^{(1)}$ ends, its loss is used by $B^{(2)}_{1}$ running in parallel to the next forward pass and $B^{(1)}_{0}$.

### 3.2 Layer-wise updates

Parallelizing the forward and backward passes can speed up training, but it violates several key assumptions of Backpropagation leading to sub-optimal convergence observed in different studies (Keuper & Preundt, ; Zheng et al., ).
This happens because the losses and gradients are often calculated using inconsistent and outdated parameters.

To alleviate this problem, we update the layers as soon as the corresponding gradients are available from the backward pass.
$F_{1}^{(1)}$ receives partial parameter updates from $B^{(1)}_{0}$ as soon as they are available.
Therefore, the parameters used in $F_{1}^{(1)}$ will differ from those used in $F_{0}^{(0)}$ because some layers of the model would have been already updated by the thread $B^{(1)}_{0}$.
On average, we can expect that the second half of the layers use a new set of parameters.
It is important to note that the updates happen without any locking mechanism and asynchronous to the backward pass as done by Zhang et al. ().

### 3.3 Speed-up analysis

Before discussing experimental results, we study the potential speed-up of the asynchronous with layer-wise updates formulation over standard Backpropagation.
To arrive at this result, we make the following assumptions to estimate the performance gain

- •
We assume that there are no delays between the end of a forward pass, the beginning of its corresponding backward pass and the next forward pass. This implies for example that as soon as $F_{0}^{(0)}$ ends, $F_{1}^{(1)}$ and $B^{(1)}_{0}$ begin immediately. Multiples backward threads are therefore running in parallel.
- •
Vanilla Backpropagation performs $\displaystyle b$ forward passes. We assume that this number also corresponds to the number of backward passes and the number of batches of data to be trained on.
- •
A forward pass lasts $T$ units of time and a backward pass $\beta T$ units of time, with a scaling factor $\beta>1$ (expected to be at around 2 as show in appendix A.3).

The speed-up factor $\lambda$ observed can be express as the fraction between the estimated time taken by the standard over the Async version of BP. Let $T_{1}$ be the time taken by BP to be trained on $b$ batches of data. Because the forward and backward passes are sequential for each batch of data, we have:

$$ $\displaystyle T_{1}$ $\displaystyle=Tb+b\beta T$ $\displaystyle=(b+\beta)T\;.$ $$

Now let $T_{2}$ be the time taken by the asynchronous algorithm to be trained on $b$ batches of data, and $n$ be the number of remaining backward passes to be executed after all the forward passes have been performed.

We have $n=\beta$ and $T_{2}=bT+nT=Tb+\beta T$.
The speed-up factor $\lambda$ is the ratio of $T_{1}$ by $T_{2}$, which by inserting the results above gives

$$ $\displaystyle\lambda=\frac{(1+\beta)b}{(b+\beta)}\;.$ $$

By taking the limit of large number of batches, $b\to\infty$, we have

$$ $\lambda=1+\beta\;.$ $$

Hence, the maximum achievable speedup is expected to be $1+\beta$, where $\beta$ is the scaling factor of the backward pass time.
In practice, the speed-up factor $\lambda$ can be influenced by multiples factors like data loading which is sometimes a bottleneck (Leclerc et al., ; Isenko et al., ), or the system overhead, which reduce the achievable speedup.

### 3.4 Staleness Analysis

Here, we demonstrate the advantage of applying layer-wise updates (LU) compared to block updates (BU).
BU refers to performing updates only after the entire backward pass is complete, a technique used in various previous asynchronous learning algorithms, e.g. (Recht et al., ; Chatterjee et al., ; Zheng et al., ). We use the same notation as in section 3.3.

To express this formally, we define the relative staleness $\tau$ of BU compared to LU
as the time delay between when the gradients
become available and when they are used to update the model weights. The intuition behind this lies in the fact that the more the updates are postponed, the more likely the gradients will become stale. The staleness will only increase with with time and accumulate across the layers.
Assuming that the time required to compute the gradients for each layer is uniform and equal to $\frac{\beta T}{M}$, the relative staleness is expressed as $\tau=\frac{\beta T(M-1)}{2}$.

To see this, we use that by definition, the staleness increases as we approach the output layer. At any layer $m$, the layer-wise staleness $\tau_{m}=\frac{\beta T}{M}m$.
Averaging over the layers, we have

$$ $\displaystyle\tau$ $\displaystyle\;=\;\sum_{m=1}^{M}\tau_{m}\;=\;\frac{\beta T}{M}\sum_{m=1}^{M}m \;=\;\beta T\frac{(M-1)}{2}$ $$

Clearly, $\tau$ increases with the network’s depth and the time required to perform one backward pass. Thus, the speedup is expected to scale approximately linearly with the network depth, showing the advantage of LU over BU for large $M$.

### 3.5 Algorithm

The Async BP algorithm is illustrated in Figure 1 and described in Algorithm listing 1.
The algorithm consists of two components: a single forward thread and multiple backward threads. All threads work independently and asynchronously without any locking mechanism.

The forward thread is solely responsible for computing the loss $\mathcal{L}_{i}(\boldsymbol{\theta}^{u},\boldsymbol{x}_{i},\boldsymbol{y}_{i})$, given the current mini batch of data $(\boldsymbol{x}_{i},\boldsymbol{y}_{i})\in\mathcal{D}$ and the latest set of updated weights $\boldsymbol{\theta}^{u}$.
Since the algorithm works asynchronously, the weights $\boldsymbol{\theta}^{u}$ can be updated by any backward thread even while forward pass progresses. Once the forward pass is done, $\mathcal{L}_{i}$ is sent to one of the backward threads and the forward thread moves to the next batch of data.

In parallel, a backward thread $k$ receives a loss $\mathcal{L}_{j}$ and performs the backward pass. At each layer $m$, the gradients $G(\boldsymbol{\theta}_{m,k}^{v})=\frac{\partial\mathcal{L}_{j}}{\partial
\boldsymbol{\theta}_{m,k}^{v}}$ are computed, after which $\boldsymbol{\theta}_{m,k}^{v}$ is immediately used to update the forward thread parameters.
Note that the backward thread here can potentially calculate the gradients for a different values of parameters $\boldsymbol{\theta}_{m,k}^{v}$ than the ones used for the forward pass $\boldsymbol{\theta}^{u}$.
In Section 5 and appendix B we show that this algorithm closely approximates conventional stochastic gradient descent, if asynchronous parameter updates arrive sufficiently frequent.

Figure: Algorithm 1 Async BP with decoupled partial updates

## 4 Results

We evaluate our method on three vision tasks, CIFAR-10, CIFAR-100 and Imagenet, and on one sequence modeling task: IMDb sentiment analysis.
We use Resnet18 and Resnet50 architectures for vision tasks and a LSTM network for sequence modelling.
These networks are trained on a machine with 3 NVIDIA A100 80GB PCIe GPUs with two AMD EPYC CPUs sockets of 64 cores each.
The experiment code is based on the C++ frontend of Torch (Paszke et al., ) - Libtorch.

The Performance of these tasks is compared to Locally-Asynchronous-Parallel SGD (LAPSGD) and Locally-Partitioned-Asynchronous-Parallel SGD (LPPSGD) (Chatterjee et al., ). These methods extend the well-known Hogwild! algorithm and Partitioned Asynchronous Stochastic Subgradient (PASSM+) to multiple devices, respectively.

We record the achieved accuracy on the tasks and the wall-clock time to reach a target accuracy (TTA). If not stated otherwise, this accuracy is chosen to be the best accuracy achieved by the worst performing algorithm.
We used the code made available by Chatterjee et al. () which uses Pytorch Distributed Data-Parallel API.

### 4.1 Asynchnous training of vision tasks

We follow the training protocol of LAPSGD and LPPSGD and chose the number of processes per GPU to be 1 since the GPU utilization was close to 100%. We trained them with a batch size of 128 per-rank.
We used Stochastic gradient descent (SGD) for both Async BU and LU, with an initial learning rate of 0.005 for 5 epochs and 0.015 after the warm-up phase, a momentum of 0.9 and a weight decay of $5\crossproduct 110^{-2}$. We use a cosine annealing schedule with a $T_{max}$ of 110.
We trained Resnet-50 on Imagenet-1K task (Table 5) for a total of 300 epochs with the same learning rate but with a cosine schedule with $T_{max}$ of 250 and weight decay of $3.5\crossproduct 110^{-2}$ .
Although, the simulations were run with cosine annealing scheduler, implying the ideal number of training epochs, early stopping was applied, i.e. training was stopped if no improvement of the accuracy was achieved for 30 epochs.

As shown below,
Async LU achieves the highest accuracies while Async BU converges the fastest in terms of time to reach the target accuracy.
The CIFAR-10 and CIFAR-100 results are presented in Tables 1, 2 and Tables 3, 4 respectively.
In Tables  1 and 3, the time to target accuracy (TTA) is chosen to be the time taken to achieved the best accuracy reached by the worst algorithm.
Whereas in Tables 2 and 4, it represents taken by an algorithm achieve its best accuracy.
Async BU achieves a speed-up of up to $2.97\times$ over LPPSGD on CIFAR100 (see Table 3).
The poor performance of both LAPSGD and LPPSGD can be explained by the influence of staleness, thus requiring large number of training epochs.

We also achieved promising results on the ImageNet-1k dataset (see Table 5). Async LU achieved 73% accuracy $\crossproduct 3$ faster than Backpropagation on single GPU, showing potential of ideal linear scaling. An extensive comparison of Async LU with multi-GPU Backpropagation (Data Distributed Parallel) is provided in appendix A.2.

Although Async BU converges quicker than Async LU, it reaches lower accuracy. This is particularly visible on CIFAR100, a harder task than CIFAR10 (see Figures 2 and 3).
Overall, Async BU showed a good balance between convergence speed and reduction of staleness.

**Table 1: Comparison of Async LU, Async BU, LAPSGD and LPPSGD based on time to reach accuracy (TTA): 87% for ResNet18 and 89% for ResNet50, and the number of epochs to reach the target for 3 runs on CIFAR10.**
| Network architecture | Training method | TTA (in seconds) | Epochs |  |  |
| --- | --- | --- | --- | --- | --- |
|  |  | mean $\pm$ | std | mean $\pm$ | std |
| ResNet-18 | Async LU | 223.8 $\pm$ | 28 | 65 $\pm$ | 10 |
|  | Async BU | 173.4 $\pm$ | 2 | 64 $\pm$ | 2 |
|  | LAPSGD | 706.3 $\pm$ | 13 | 104 $\pm$ | 2 |
|  | LPPSGD | 461.0 $\pm$ | 7 | 86 $\pm$ | 1 |
| ResNet-50 | Async LU | 737.9 $\pm$ | 24 | 86 $\pm$ | 6 |
|  | Async BU | 700.6 $\pm$ | 20 | 86 $\pm$ | 1 |
|  | LAPSGD | 999.5 $\pm$ | 38 | 117 $\pm$ | 3 |
|  | LPPSGD | 863.4 $\pm$ | 35 | 119 $\pm$ | 1 |

**Table 2: Comparison of Async LU, Async BU, LAPSGD, and LPPSGD based on best accuracy, time to reach accuracy (TTA), and epoch at the accuracy is achieved for 3 runs on CIFAR10.**
| Network architecture | Training method | Best accuracy | TTA (in seconds) | Epochs |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- |
|  |  | mean $\pm$ | std | mean $\pm$ | std | mean $\pm$ | std |
| ResNet-18 | Async LU | 93.7 $\pm$ | 0.28 | 380.7 $\pm$ | 33 | 114 $\pm$ | 9 |
|  | Async BU | 92.7 $\pm$ | 0.16 | 308.5 $\pm$ | 14 | 115 $\pm$ | 2 |
|  | LAPSGD | 88.2 $\pm$ | 0.43 | 799.5 $\pm$ | 20 | 118 $\pm$ | 2 |
|  | LPPSGD | 87.8 $\pm$ | 0.09 | 523.4 $\pm$ | 15 | 97 $\pm$ | 1 |
| ResNet-50 | Async LU | 93.9 $\pm$ | 0.10 | 1038.8 $\pm$ | 61 | 121 $\pm$ | 6 |
|  | Async BU | 93.2 $\pm$ | 0.25 | 953.7 $\pm$ | 73 | 116 $\pm$ | 8 |
|  | LAPSGD | 89.7 $\pm$ | 0.27 | 1098.9 $\pm$ | 30 | 117 $\pm$ | 3 |
|  | LPPSGD | 89.3 $\pm$ | 0.43 | 888.4 $\pm$ | 37 | 119 $\pm$ | 1 |

**Table 3: Comparison of Async LU, Async BU, LAPSGD and LPPSGD based on time to reach accuracy (TTA): 60% for ResNet18 and 63% for ResNet50, and the number of epochs to reach the target for 3 runs on CIFAR100.**
| Network architecture | Training method | TTA (in seconds) | Epochs |  |  |
| --- | --- | --- | --- | --- | --- |
|  |  | mean $\pm$ | std | mean $\pm$ | std |
| ResNet-18 | Async LU | 226.4 $\pm$ | 10 | 69 $\pm$ | 7 |
|  | Async BU | 155.4 $\pm$ | 10 | 57 $\pm$ | 4 |
|  | LAPSGD | 667.1 $\pm$ | 8 | 99 $\pm$ | 2 |
|  | LPPSGD | 672.9 $\pm$ | 11 | 100 $\pm$ | 2 |
| ResNet-50 | Async LU | 622.7 $\pm$ | 32 | 70 $\pm$ | 5 |
|  | Async BU | 641.8 $\pm$ | 16 | 81 $\pm$ | 3 |
|  | LAPSGD | 1006.6 $\pm$ | 13 | 107 $\pm$ | 1 |
|  | LPPSGD | 1016.0 $\pm$ | 6 | 107 $\pm$ | 1 |

**Table 4: Comparison of Async LU, Async BU, LAPSGD and LPPSGD based on best accuracy, time to reach accuracy (TTA), and epoch at the accuracy is achieved for 3 runs on CIFAR100.**
| Network architecture | Training method | Best accuracy | TTA (in seconds) | Epochs |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- |
|  |  | mean $\pm$ | std | mean $\pm$ | std | mean $\pm$ | std |
| ResNet-18 | Async LU | 73.9 $\pm$ | 0.38 | 339.0 $\pm$ | 10 | 114 $\pm$ | 9 |
|  | Async BU | 71.8 $\pm$ | 0.08 | 277.2 $\pm$ | 17 | 103 $\pm$ | 5 |
|  | LAPSGD | 61.3 $\pm$ | 0.23 | 762.5 $\pm$ | 15 | 114 $\pm$ | 3 |
|  | LPPSGD | 61.0 $\pm$ | 0.17 | 742.0 $\pm$ | 19 | 110 $\pm$ | 2 |
| ResNet-50 | Async LU | 76.2 $\pm$ | 0.57 | 1071.0 $\pm$ | 80 | 122 $\pm$ | 6 |
|  | Async BU | 73.7 $\pm$ | 0.23 | 956.2 $\pm$ | 28 | 123 $\pm$ | 4 |
|  | LAPSGD | 63.7 $\pm$ | 0.33 | 1110.1 $\pm$ | 27 | 118 $\pm$ | 3 |
|  | LPPSGD | 63.5 $\pm$ | 0.10 | 1122.1 $\pm$ | 24 | 119 $\pm$ | 2 |

**Table 5: Classification accuracy (% correct) for Async LU (3 GPUs) and vanilla backpropagation (single GPU) on the ImageNet task.**
| Network architecture | training method | test-accuracy | train-accuracy | TTA (in 1000 seconds) |
| --- | --- | --- | --- | --- |
| ResNet-50 | Async LU | 73.42 | 93.08 | 134.24 |
|  | BP (single GPU) | 73.40 | 91.90 | 403.77 |

### 4.2 Asynchronous training of sequence modelling task

For demonstrating Async BP training on sequence modelling, we evaluated an LSTM networks on the IMDb dataset (Maas et al., ).
Sentiment analysis is the task of classifying the polarity of a given text.
We used a 2-Layer LSTM network with 256 hidden dimensions to evaluate this task.
We trained the network until convergence using the Adam optimizer with an initial learning rate of $1\crossproduct 10^{-2}$.
Results are shown in Table 6.

We observe that although both Async LU and Async BU achieve the same accuracy, performing layer-wise updates reduces the training time and number of steps to convergence almost by half (see Figure 4 in Appendix A) highlighting again the importance of this strategy.

**Table 6: Comparison of Async LU, Async BU based on best accuracy, time to reach accuracy (TTA), and epoch at the accuracy is achieved for 3 runs on IMDb**
| Network architecture |  | best accuracy | TTA(in seconds) | epoch |
| --- | --- | --- | --- | --- |
|  |  | mean$\pm$std | mean$\pm$std | mean$\pm$std |
| LSTM | Async LU | 85.15$\pm$0.15 | 49.3$\pm$9.46 | 6$\pm$1 |
|  | Async BU | 85.06$\pm$0.59 | 83.41$\pm$12.56 | 12$\pm$2 |

Figure: Figure 2: Learning curves of Asynchronous SGD with layer-wise updates (Async LU) and Block updates (Async BU) on the CIFAR100 dataset. 3 independent runs shown for each class.
Refer to caption: x1.png

## 5 Theoretical analysis of convergence

Here, we theoretically analyse the convergence behavior of the algorithm outlined above.
For the theoretical analysis, we consider the general case of multiple threads, acting on the parameter set $\boldsymbol{\theta}$, such that the threads interact asynchronously and can work on outdated versions of the parameters.
We model the evolution of the learning algorithm as a continuous-time stochastic process (Bellec et al., ) to simplify the analysis.
This assumption is justified by the fact that learning rates are typically small, and therefore the evolution of network parameters is nearly continuous.

In the model studied here, the stochastic interaction between threads is modelled as noise induced by random interference of network parameters.
To arrive at this model, we use the fact that the dynamics of conventional stochastic gradient descent (SGD) can be modelled as the system of stochastic differential equations that determine the dynamics of the parameter vector $\boldsymbol{\theta}$

$$ $d\theta_{k}=-\eta\frac{\partial}{\partial\theta_{k}}\mathcal{L}(\boldsymbol{ \theta})dt\;+\;\frac{\eta\,\sigma_{\text{SGD}}}{\sqrt{2}}~{}d\mathcal{W}_{k}\,\;,$ (2) $$

with learning rate $\eta$ and where $d\mathcal{W}_{k}$ are stochastic changes of the Wiener processes.

Eq. 2 describes the dynamics of a single parameter $\theta_{k}$. The dynamics is determined by the gradient of the loss function $\mathcal{L}$, and the noise induced by using small mini-batches modelled here as idealized Wiener process with amplitude $\sigma_{\text{SGD}}$. Because of this noise, SGD does not strictly converge to a local optimum but maintains a stationary distribution $p^{*}(\boldsymbol{\theta}_{k})\propto e^{-\frac{1}{\eta}\mathcal{L}(
\boldsymbol{\theta}_{k})}$, that assigns most of the probability mass to parameter vectors that reside close to local optima (Bellec et al., ).

In the concurrent variant of SGD studied here, however, the dynamics is determined by perturbed gradients for different stale parameters.
When updating the network using the described asynchronous approach without locking, we potentially introduce noise in the form of partially stale parameters or from one thread overwriting the updates of another. This noise will introduce a deviation from the ideal parameter vector $\boldsymbol{\theta}$. We model this deviation as additive Gaussian noise $\boldsymbol{\xi}\sim\mathcal{N}(0,\sigma_{\text{STALE}})$ to the current parameter vector with variance $\sigma_{\text{STALE}}$. To approximate the noisy loss function, we use a first-order Taylor expansion around the noise-free parameters:

$$ $\displaystyle\mathcal{L}(\boldsymbol{\theta}+\boldsymbol{\xi})$ $\displaystyle\;=\;\mathcal{L}(\boldsymbol{\theta})+\nabla_{\theta}\mathcal{L}( \boldsymbol{\theta})^{\top}\boldsymbol{\xi}+\mathcal{O}(\sigma^{2})$ (3) $\displaystyle\;\approx\;\mathcal{L}(\boldsymbol{\theta})+\nabla_{\theta} \mathcal{L}(\boldsymbol{\theta})^{\top}\boldsymbol{\xi}\,,$ $$

and thus the gradient can be approximated as

$$ $\displaystyle\nabla_{\theta}\mathcal{L}(\boldsymbol{\theta}+\boldsymbol{\xi}, \boldsymbol{X},\boldsymbol{Y})$ $\displaystyle\;\approx\;\nabla_{\theta}\mathcal{L}(\boldsymbol{\theta})+\nabla _{\theta}^{2}\mathcal{L}(\boldsymbol{\theta})^{\top}\boldsymbol{\xi}\,.$ (4) $$

Based on this, we can express the update rule as a Stochastic Differential Equation (SDE) and model the various noise terms using a Wiener Process $\mathcal{W}$.
The noise sources in the learning dynamics come from two main sources, (1) noise caused by stochastic gradient descent, and (2) noise caused by learning with outdated parameters. We model the former as additive noise with amplitude $\sigma_{\text{STALE}}$ and the latter using the Taylor approximation Eq. (4). Using this, we can write the approximate dynamics of the parameter vector $\boldsymbol{\theta}$ as the stochastic differential equation

$$ $\displaystyle d\theta_{k}=\mu_{k}(\boldsymbol{\theta},t)+\sqrt{D_{k}( \boldsymbol{\theta})}~{}d\mathcal{W}_{k}\;,$ (5) $$

with

$$ $\displaystyle\mu_{k}(\boldsymbol{\theta})$ $\displaystyle=-\eta\frac{\partial}{\partial\theta_{k}}\mathcal{L}(\boldsymbol{ \theta})$ (6) $\displaystyle D_{k}(\boldsymbol{\theta})$ $\displaystyle=\frac{\eta^{2}\sigma^{2}_{\text{SGD}}}{2}+\frac{\eta^{2}\sigma^{ 2}_{\text{STALE}}}{2}\sum_{l}\frac{\partial^{2}}{\partial\theta_{k}\partial \theta_{l}}\mathcal{L}(\boldsymbol{\theta})\;,$ $$

where $\mu_{k}$ is the drift and $D_{k}$ the diffusion of the SDE.

In Appendix B we study the stationary distribution of this parameter dynamics. We show that the stationary distribution is a close approximation to $p^{*}$ of SGD, which is perfectly recovered if $\sigma_{\text{STALE}}$ is small compared to $\sigma_{\text{SGD}}$, i.e. if the effect of staleness is small compared to the noise induced by minibatch sampling.

## 6 Discussion

In this work, we introduced a novel asynchronous approach to train deep neural networks that decouples the forward and backward passes and performs layer-wise parameter updates. Our method addresses key limitations of standard backpropagation by allowing parallel execution of forward and backward passes and mitigating update locking through asynchronous layer-wise updates.

The experimental results demonstrate that our approach can achieve comparable or better accuracy than synchronous backpropagation and other asynchronous methods across multiple vision and language tasks, while providing significant speedups in training time. On CIFAR-10 and CIFAR-100, we observed speedups of up to $2.97\times$ compared to asynchronous SGD covering a broad range of paradigms. The method also showed promising results on a sentiment analysis task and the ImageNet classification task where it reached close to ideal scaling.

Our theoretical analysis, based on modeling the learning dynamics as a continuous-time stochastic process, provides convergence guarantees and shows that the algorithm converges to a stationary distribution closely approximating that of standard SGD under certain conditions. This offers a solid foundation for understanding the behavior of our asynchronous approach.

While our implementation using C++ and LibTorch demonstrated the potential of this method, we also identified some limitations related to GPU resource allocation in SIMT architectures. Future work could explore optimizing the implementation for more efficient GPU utilization, or investigating hybrid CPU-GPU approaches to fully leverage the benefits of asynchronous execution.

Overall, this work presents a promising direction for scaling up deep learning through asynchronous, decoupled updates. The approach has the potential to enable more efficient training of large-scale models, particularly in distributed and heterogeneous computing environments. Further research could explore extensions to even larger models, additional tasks, and more diverse hardware setups to fully realize the potential of this asynchronous training paradigm.

## Reproducibility

We ensure that the results presented in this paper are easily reproducible using just the information
provided in the main text as well as the supplement.
Details of the models used in our simulations are presented in the main paper and further elaborated in the supplement.
We provide additional details and statistics over multiple runs in the supplement section A.4.
We use publicly available libraries and datasets in our simulations.
We will further provide the source code to the reviewers and ACs in an anonymous repository once the discussion forums are opened.
This included code will also contain “readme” texts to facilitate easy reproducibility.
The theoretical analysis provided in section 5 is derived in the supplement.

## Acknowledgements

Cabrel Teguemne Fokam and Khaleelulla Khan Nazeer are funded by the German Federal Ministry of Education and Research (BMBF), funding reference 16ME0729K, joint project ”EVENTS”. Lukas König and David Kappel are funded by the German Federal Ministry for Economic Affairs and Climate Action (BMWK) project ESCADE (01MN23004A).
The authors gratefully acknowledge the Gauss Centre for Supercomputing e.V. (www.gauss-centre.eu) for funding this project by providing computing time on the GCS Supercomputer JUWELS at Jülich Supercomputing Centre (JSC).

## Appendix A Futher results

### A.1 Learning curves

Here, we provide additional details to the CIFAR10 and IMDb results provided in the main text.
Figures 3 and 4 show the learning dynamics of Asynchrounous Backpropagation with blocks updates (Async BU) and with layer-wise updates (Async LU) on CIFAR10 and IMDb respectively. The difference in convergence speed and accuracy observed with CIFAR100 2 is less noticeable on CIFAR10, probably because it is a simpler task. However, we clearly see the advantage of Async LU on the IMDb, where it not only converges faster but also to similar accuracy.

Figure: Figure 3: Learning curves of Asynchronous SGD with layer-wise updates (Async LU) and Block updates (Async BU) for ResNet18 (top plots) and ResNet50 (bottom plots) on the CIFAR10 dataset.
Refer to caption: x2.png

Figure: Figure 4: Learning curves of Asynchronous SGD with layer-wise updates (Async LU) and Block updates (Async BU) on the IMDb dataset.
Refer to caption: x3.png

### A.2 Speed-up comparison with Multi-GPU Backpropagation

Here we do a comparison of Asynchronous Backpropagation with layer-wise updates (Async LU) and multi-GPU Data Distributed Parallel(DDP) both trained on 3 GPUs residing on the same machine (described in section 4) to achieve their accuracies. Since Async LU uses only one forward pass, we set its batch size to be 128 and that of BP to $3\times$ higher (384). Async LU was implemented on the c++ library of Pytorch, Libtorch, and implemented using Pytorch DataDistributedParallel (DDP) API. The hyperparameters used are the same as described in section 4.
To make the comparison fair, the relative speed-up is calculated with respect of the single GPU implementation of Backpropagation on Libtorch for Async LU and Pytorch for DDP.

In this Settings, DDP should clearly the advantages since it uses a bigger batch size and all the GPUs are on the same machine, reducing considerably the communication bottleneck, hence making the synchronization step faster. However with observe that Async LU achieves comparable relative speed-up over single GPU compared to DDP on both CIFAR10 and CIFAR100. This shows the effectiveness of our asynchronous formulation (figure 1). We can expect Async LU to have some advantage in a multi-node or heterogeneous setting because the synchronization barrier becomes problem.

**Table 7: Comparison of Async LU and DDP both trained on 3GPUs based on their relative speed-up to single GPU implemention for 3 runs on CIFAR10**
| Network architecture | Training method | Relative speed-up |  |
| --- | --- | --- | --- |
|  |  | mean $\pm$ | std |
| ResNet-18 | Async LU | 1.86 $\pm$ | 0.21 |
|  | DDP | 1.90 $\pm$ | 0.08 |
| ResNet-50 | Async LU | 2.02 $\pm$ | 0.10 |
|  | DDP | 2.38 $\pm$ | 0.19 |

**Table 8: Comparison of Async LU and DDP both trained on 3GPUs based on their relative speed-up to single GPU implemention for 3 runs on CIFAR100**
| Network architecture | Training method | Relative speed-up |  |
| --- | --- | --- | --- |
|  |  | mean $\pm$ | std |
| ResNet-18 | Async LU | 1.83 $\pm$ | 0.06 |
|  | DDP | 1.86 $\pm$ | 0.21 |
| ResNet-50 | Async LU | 2.02 $\pm$ | 0.13 |
|  | DDP | 2.30 $\pm$ | 0.13 |

### A.3 Time measurements

Here we provide the results of a small scale experiment on the
timing measurement of forward and backward passes for CIFAR-100 with batch size 128 in table 9. As expected, a single backward requires $~{}2\times$ of a single backward pass. Extensive experiments on this is provided by Kumar et al. ()

**Table 9: Timing measurement of forward and backward passes for CIFAR-100 with batch size 128. Averaged over all batches for 15 epochs.**
| Network architecture | Forward pass (s) | Backward pass (s) |  |  |
| --- | --- | --- | --- | --- |
|  | mean $\pm$ | std | mean $\pm$ | std |
| ResNet-18 | 0.0049 $\pm$ | 1E-04 | 0.0102 $\pm$ | 1E-04 |
| ResNet-50 | 0.0166 $\pm$ | 5E-05 | 0.0299 $\pm$ | 4E-05 |

### A.4 Hyperparameters for the experiments

Hyperparameters used in training experiments presented in section 4 are documented in table 10

**Table 10:**
|  | CIFAR-100 | CIFAR-10 | Imagenet | IMDb |  |  |
| --- | --- | --- | --- | --- | --- | --- |
| hyperparameter | Resnet-18 | Resnet-50 | Resnet-18 | Resnet-50 | Resnet-50 | LSTM |
| batch_size | 128 | 128 | 128 | 128 | 300 | 75 |
| lr | 0.015 | 0.015 | 0.015 | 0.015 | 0.015 | 0.001 |
| momentum | 0.9 | 0.9 | 0.9 | 0.9 | 0.9 | 0.9 |
| T_max | 100 | 120 | 105 | 120 | 250 | 150 |
| warm_up_epochs | 5 | 5 | 3 | 5 | 5 | 0 |
| warm_up lr | 0.005 | 0.005 | 0.005 | 0.005 | 0.0035 | - |
| weight_decay | 0.005 | 0.005 | 0.005 | 0.005 | 0.0035 | 0 |

## Appendix B Convergence Proof

Here we provide the proof that the stochastic parameter dynamics, Eq. (5) of the main text, converges to a stationary distribution $p^{*}(\boldsymbol{\theta})$ given by

$$ $p^{\ast}(\boldsymbol{\theta})=\frac{1}{\mathcal{Z}}\exp(\sum_{k}h_{k}( \boldsymbol{\theta})),\;\text{with}\;h_{k}(\boldsymbol{\theta})=\int\frac{\mu_ {k}(\boldsymbol{\theta})}{D_{k}(\boldsymbol{\theta})}\,d\boldsymbol{\theta}- \ln|D_{k}(\boldsymbol{\theta})|+C\;.$ (7) $$

The proof is analogous to the derivation given in Bellec et al. (), and relies on stochastic calculus to determine the parameter dynamics in the infinite time limit. Since the dynamics include a noise term, the exact value of the parameters $\boldsymbol{\theta}(t)$ at a particular point in time $t>0$ cannot be determined, but we can describe the distribution of parameters using the Fokker-Planck formalism, i.e. we describe the parameter distribution at time $t$ by a time-varying function $p_{\mathrm{FP}}(\boldsymbol{\theta},t)$.

To arrive at an analytical solution for the stationary distribution, $p^{\ast}(\boldsymbol{\theta})$ we make the adiabatic assumption that noise in the parameters only has local effects, such that the diffusion due to noise in any parameter $\theta_{j}$ has negligible influence on dynamics in $\theta_{k}$, i.e. $\frac{\partial}{\partial\theta_{j}}D_{k}(\boldsymbol{\theta})=0,\forall j\neq k$. Using this assumption, it can be shown that, for the dynamics (6), $p_{\mathrm{FP}}(\boldsymbol{\theta},t)$ converges to a unique stationary distribution in the limit of large $t$ and small noise $\sigma_{STALE}$. To prove the convergence to the stationary distribution, we show that it is kept invariant by the set of SDEs Eq. (6) and that it can be reached from any initial condition.
Eq. 6 implies a Fokker-Planck equation given by

$$ $\displaystyle\frac{\partial}{\partial t}p_{\mathrm{FP}}(\boldsymbol{\theta},t)=$ $\displaystyle-\sum_{k}\frac{\partial}{\partial\theta_{k}}[\mu_{k}(\boldsymbol{ \theta},t)p_{\mathrm{FP}}(\boldsymbol{\theta},t)]+\frac{\partial^{2}}{\partial \theta_{k}^{2}}[D_{k}(\boldsymbol{\theta},t)p_{\mathrm{FP}}(\boldsymbol{\theta },t)]$ (8) $$

We show that, under the assumptions outlined above, the stochastic parameter dynamics Eq. (6) of the main text, converges to the stationary distribution $p^{*}(\boldsymbol{\theta})$ (Eq. (7)).

To arrive at this result, we plug in the assumed stationary distribution into Eq. (8) and show the equilibrium $\frac{\partial}{\partial t}p_{\mathrm{FP}}(\boldsymbol{\theta},t)=0$, i.e.

$$ $\displaystyle\frac{\partial}{\partial t}p_{\mathrm{FP}}(\boldsymbol{\theta},t)\;=$ $\displaystyle-\sum_{k}\frac{\partial}{\partial\theta_{k}}[\mu_{k}(\boldsymbol{ \theta})p_{\mathrm{FP}}(\boldsymbol{\theta},t)]$ (9) $\displaystyle+\frac{\partial^{2}}{\partial\theta_{k}^{2}}[D_{k}(\boldsymbol{ \theta})p_{\mathrm{FP}}(\boldsymbol{\theta},t)]=0$ $\displaystyle\leftrightarrow$ $\displaystyle-\sum_{k}\frac{\partial}{\partial\theta_{k}}[\mu_{k}(\boldsymbol{ \theta})p_{\mathrm{FP}}(\boldsymbol{\theta},t)]$ $\displaystyle+\frac{\partial}{\partial\theta_{k}}\left[\left(\frac{\partial}{ \partial\theta_{k}}D_{k}(\boldsymbol{\theta})\right)p_{\mathrm{FP}}( \boldsymbol{\theta},t)\right]$ $\displaystyle+\frac{\partial}{\partial\theta_{k}}\left[D_{k}(\boldsymbol{ \theta})\left(\frac{\partial}{\partial\theta_{k}}h_{k}(\boldsymbol{\theta}) \right)p_{\mathrm{FP}}(\boldsymbol{\theta},t)\right]\;,$ $$

where we used the simplifying assumption,
$\frac{\partial}{\partial\theta_{j}}D_{k}(\boldsymbol{\theta})=0,\forall j\neq k$, as outlined above. Next, using $\frac{\partial}{\partial\theta_{j}}h_{k}(\boldsymbol{\theta})=\frac{1}{D_{k}(
\boldsymbol{\theta},t)}\left(\mu_{k}(\boldsymbol{\theta},t)-\frac{\partial}{
\partial\theta_{j}}D_{k}(\boldsymbol{\theta},t)\right)$, we get

$$ $\displaystyle\frac{\partial}{\partial t}p_{\mathrm{FP}}(\boldsymbol{\theta},t) \;=\;0\quad\leftrightarrow$ $\displaystyle-\sum_{k}\frac{\partial}{\partial\theta_{k}}[\mu_{k}(\boldsymbol{ \theta},t)p_{\mathrm{FP}}(\boldsymbol{\theta},t)]$ (10) $\displaystyle+\frac{\partial}{\partial\theta_{k}}\left[\left(\frac{\partial}{ \partial\theta_{k}}D_{k}(\boldsymbol{\theta},t)\right)p_{\mathrm{FP}}( \boldsymbol{\theta},t)\right]$ $\displaystyle+\frac{\partial}{\partial\theta_{k}}\left[\left(\mu_{k}( \boldsymbol{\theta},t)-\frac{\partial}{\partial\theta_{k}}D_{k}(\boldsymbol{ \theta},t)\right)p_{\mathrm{FP}}(\boldsymbol{\theta},t)\right]=0$ $$

This shows that the simplified dynamics, Eq. 6, leave the stationary distribution (7) unchanged.

This stationary distribution $p^{\ast}(\boldsymbol{\theta})$ is a close approximation to SGD. To see this, we study the maxima of the distribution, by taking the derivative

$$ $\frac{\partial}{\partial\theta_{k}}h_{k}(\boldsymbol{\theta})=\frac{\mu_{k}( \boldsymbol{\theta})}{D_{k}(\boldsymbol{\theta})}-\frac{\partial}{\partial \theta_{k}}\ln|D_{k}(\boldsymbol{\theta})|\;,$ (11) $$

which by inserting (6) can be written as

$$ $\frac{\partial}{\partial\theta_{k}}h_{k}(\boldsymbol{\theta})=-\frac{1}{\eta} \frac{\nabla_{\theta}\mathcal{L}(\boldsymbol{\theta})\;+\;\sigma^{2}_{\text{ STALE}}\nabla_{\theta}^{3}\mathcal{L}(\boldsymbol{\theta})}{\sigma^{2}_{\text{ SGD}}\;+\;\sigma^{2}_{\text{STALE}}\nabla_{\theta}^{2}\mathcal{L}(\boldsymbol{ \theta})}$ (12) $$

If $\sigma_{\text{STALE}}$ is small compared to $\sigma_{\text{SGD}}$ we recover the cannonical results for SGD $\frac{\partial}{\partial\theta_{k}}h_{k}(\boldsymbol{\theta})\approx-\frac{1}{
\eta}\frac{\nabla_{\theta}\mathcal{L}(\boldsymbol{\theta})}{\sigma^{2}_{\text{
SGD}}}$, where smaller learning rates $\eta$ make the probability of reaching local optima more peaked. Distortion of local optima, which manifests in the second term in the nominator, only depend on third derivatives, which can be expected to be small for most neural network architectures with well-behaved non-linearities.

## Peer Reviews

confidence: 3
contribution: 2
initial_rating: 3
presentation: 2
questions: * In your experiments, how many data parallel replicas are used for Hogwild? And for yours?
* In your experiments, how does the memory usage compare between Hogwild and your method?
soundness: 2
strengths: * **Novel use of multi-threading to hide the backward computations:** to the best of my knowledge, the way multi-threading is used here to hide the backward computation time in a "modularized" version of the back-propagation algorithm is not common. However, it is unfortunately *not* the only way to leverage multi-threading to this end (see the Weaknesses).
* **Theoretical analysis of the method:** convergence guarantees are given by modeling the training dynamic using stochastic processes.
summary: Given the observation that a backward pass usually takes twice as long as a forward computation in the Backpropagation algorithm, this paper proposes to perform the backward and forward passes in parallel threads instead of sequentially. Two parallel threads perform backward passes concurrently, while a third continuously perform forward passes and asynchronously update the model. Given that 2 threads are dedicated to backward passes, the cost of performing those computations is hidden behind the forward passes and the training time for the model simply amount to the time to perform forward computations without stopping on a given number of minibatches.
weaknesses: * **Incomplete literature review, lacking comparison with existing literature:** Update locking is a key subject in model parallel (pipeline parallel) as it leads to GPUs idling instead of computing, yet no mention nor comparison with pipeline parallel methods is done. In model parallel, one thread per module is used, each thread performs a repetition of *“receive activation from previous module, forward pass, send activation to next module, receive gradient from next module, backward pass and update local module, send gradient to previous module”* cycles. See e.g.,[[Qi et al., 2023]]( https://arxiv.org/pdf/2401.10241 ), [[Kosson et al., 2021]]( https://arxiv.org/pdf/2003.11666 ), [[Yang et al., 2020]]( https://arxiv.org/pdf/1910.05124 ), [[Chen et al., 2019]]( https://arxiv.org/pdf/1809.02839 ), [[Huang et al., 2019]]( https://arxiv.org/pdf/1811.06965 ).
* **Idea of performing two backward computations per forward is not new**: in the “zero bubble paper” the same justification as eq (1) is done to reduce the size of the bubble in pipeline parallelism (see Fig.2 and Fig.3 of [[Qi et al., 2023]]( https://arxiv.org/pdf/2401.10241 ) ).
* **No study of the memory requirement of the method is performed:** Where are the activation terms $y_m$ of equation (1) in the Algorithm 1? These are are highly important in the memory footprint of your method, given that storing activations is the reason why the memory footprint is the largest at the end of the forward pass (see e.g., [the pytorch blog article on GPU memory]( https://pytorch.org/blog/understanding-gpu-memory-1/ ) ) and that GPU memory is one of the main bottleneck nowadays to train large models.

* **Weak experimental results:** The accuracies reached on CIFAR10 for ResNet18 are not really state-of the art (they should be $>95\\%$), and experiments with pipeline parallel algorithms are lacking, as well as with Decoupled Parallel Backpropagation [[Huo et al., 2018]]( https://arxiv.org/pdf/1804.10574 ).

* **Writing sometimes unclear or imprecise**:
  * **line 117:** *"Decoupled Parallel Backpropagation does full Backpropagation but uses stale gradients in the blocks to avoid update locking."* Indeed, but so does your method, so where is the problem?
  * **Overly complicated analysis of speedup (Section 3.3)**: the analysis could be made simpler by saying that your method basically performs forward passes back to back, completely hiding backward computation in parallel threads, so the training time is roughly $T_2 = bT$. On the contrary, standard BP performs forward and backward passes back to back, so the training time is $T_1 = (1+\beta )b T$ and the speedup is equal to $1 + \beta$. 

  * **Section 3.4 unclear:** I did not understand the meaning of the staleness. Are you referring to the length of the “pipeline step” (see, e.g. fig 2 of [[Kosson et al., 2021]]( https://arxiv.org/pdf/2003.11666 ) ), or the “bubble size” in pipeline parallel (see, e.g. fig 2. in  [[Huang et al., 2019]]( https://arxiv.org/pdf/1811.06965 ) ).
  * **typos:** *line 221*: “with with”, *line 194:* the second line of equation is incorrect.

---

confidence: 4
contribution: 1
initial_rating: 3
presentation: 3
questions: If the reviewer is not mistaken, the interactions between the threads in figure 1 would indeed lead to the creation of memory buffers.
The reviewers is curious whether the authors have investigated such "communication costs" of the technique.
soundness: 2
strengths: The ideas are clearly explained.
The paper is easy to follow.
The paper covers an important (crucial from the  reviewer's humble opinion) topic with a high potential for impact.
summary: the papers proposes methodology to faster train NN using asynchronous updates
This is tackling the problem known in the literature as forward/backward lock
in particular the authors propose an asynchronous methodology for the training
weaknesses: This work presents a technique that is very close to techniques that have been known to the community for several years now (see https://proceedings.mlr.press/v70/jaderberg17a/jaderberg17a.pdf for instance).
This paper was followed by a long line of work on the topic.
This should be at least mentioned in the literature review.
Moreover, extensive numerical experiments comparing the proposed technique with SOTA asynchronous training techniques should support and highlight the strength/weaknesses of the algorithm. This is currently lacking in the paper.
Last, we would like to note that evaluating the techniques on resnet50 and lstm is not representative of the challenges faced when training modern ml systems (eg llms). The reviewer expects to see numerical results covering more of  such architectures.

---

confidence: 4
contribution: 1
initial_rating: 3
presentation: 1
questions: 1. Could you provide a clear illustration in Figure 2 like Gpipe to show how the forward and backward are pipelined?
soundness: 1
strengths: Various experimental settings are explored, including CIFAR, ImageNet and LSTM.
summary: The authors propose to parallelises backpropagation updates across the layers of a model by asynchronously updating them
from multiple threads.
weaknesses: 1. The authors fail to show the converging model performance in Table 1. It does not validate that the proposed method can achieve similar performance as the backpropagation baseline.
2. The authors fail to show the converging model performance of the backpropagation baseline in Table 2 as well.
3. No training curves are provided.
4. Limited novelty. Decoupled forward and backward is not new. Check pipeline parallelism [1,2]. In particular, [2] provided a convergence analysis for async pipeline.
5. Figure 1 clearly shows that the forward activation and backward gradient does not come from the same training data. Therefore it's intuitionally not sound to show that it could match the performance of backpropagation. Note that [2] makes sure they come from the same data to conduct the convergence analysis.
6. Convergence complexity not provided.

[1] Huang, Y., Cheng, Y., Bapna, A., Firat, O., Chen, D., Chen, M., Lee, H., Ngiam, J., Le, Q.V. and Wu, Y., 2019. Gpipe: Efficient training of giant neural networks using pipeline parallelism. Advances in neural information processing systems, 32.

[2] Xu, A., Huo, Z. and Huang, H., 2020. On the acceleration of deep learning model parallelism with staleness. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (pp. 2088-2097).

---

confidence: 4
contribution: 2
initial_rating: 3
presentation: 2
questions: Please see issues above for major questions. 

Some typos and minor observations: 

- L249: “for *a* different values”

- 250: Appendix B should be capitalized

- 251: sufficiently frequently

- 275: the A100 GPU you are using is an unusual choice for this task: this might be helping your algorithm since it has large computational power, so the degree of asynchrony between threads may be reduced relative to a mid-range GPU. 

- 292: Why did you choose 300 epochs for ImageNet? What happens with a lower (and more standard) number? 

- Please consider moving figures closer to where they are referenced. 

- Why no SGD baselines in tables? 

- Your convergence curves in Figure 2 seem to suggest that in fact there is quite significant noise due to asynchrony (the staircase pattern). Can you show a similar curve for regular training? Can you maybe vary the degree of asynchrony? 

Necessary Changes

1. Comprehensive baseline comparisons including standard SGD
2. Analysis of sample complexity increase and its practical implications, rather than sweeping it under the rug 
3. Validation on more diverse hardware configurations, ablations on key components, detailed scalability analysis
4. Clearer theoretical justification or an alternative, more standard, analysis approach
soundness: 2
strengths: I found the paper’s motivation and its initial discussion, up to Section 3.2, sound, interesting, and worthwhile. If anything, I think the observation that the max speedup factor should be at most 3 (since in standard backprop we are executing 3 matrix multiplies in sequence, and in your loose version they could potentially happen completely in parallel, on average) could be stated earlier and arrived at less circuitously.
summary: The paper is in the general area of parallelization of DNN training, at the intersection of Machine Learning and Systems. Specifically, the paper is motivated by an analysis of backpropagation from the point of view of parallelism. Specifically, the paper starts by observing that backprop through a DNNs is a heavily sequential process (since we have to propagate inputs layer-wise, and then back-propagate the other way). The paper then wonders what would happen if we were to decouple, e.g., the forward-backward processes, by executing them on different threads, in order to allow for strictly increased parallelism relative to the base process.
weaknesses: Weaknesses: 

This point in the paper is unfortunately also pretty much where the quality of the submission starts to degrade. Specifically, I will list my concerns relative to the rest of the paper below, in sequence. (The authors may use this indexing in the discussion period.) 

1. Section 4 jumps directly into the experimental results. Here, the authors seem to meet a few challenges in terms of the viability of their method, which they seem to obscure or completely ignore. 

a. First is the fact that the sample complexity of their asynchronous algorithm (i.e. the number of data samples seen by SGD) is (probably, unless I misunderstand something, this is not discussed clearly) much higher than standard SGD with momentum: by this I mean that, due to asynchrony, their algorithm seems to need a lot more data passes to reach the same level of accuracy. 
For instance, curiously, the authors choose 300 epochs for ImageNet training of ResNet50, which is of only 73% for their algorithm. By comparison, e.g. the FFCV recipe using synchronous SGD+momentum on a single A100 would reach the same level in 30 epochs and probably in lower wall-clock time. A standard accuracy for this network is 76.15 (SGD + momentum, 90 epochs), if memory serves me well. 

The same curious behavior seems to occur for CIFAR10/100 experiments as well, where the accuracies presented significantly underperform what I seem to remember are the “right” values for standard training (e.g. around 93% on CIFAR10). Please see the FFCV examples or even Pytorch pretrained models for reasonably SOTA versions. 

b. More broadly, I find it really quite curious that none of the tables presented contains an SGD baseline. It is great that the authors are able to outperform LAPSGD/LPPSGD–and frankly what they are doing does seem like a better idea for parallelization–but that doesn’t mean that one should ignore any other baseline. Please add baselines. 

c. Generally, it is not so clear to me what are the broad implications of Section 4. OK, the results are better than LPP/LAP in terms of accuracy per time unit, but I thought that the general findings should be that the approach is better than “sequential” SGD? 

2. The theoretical analysis of convergence is under a very non-standard model. 
Specifically, the analysis seems to boil down to modeling SGD dynamics as a continuous process (which is fine), but then assuming that somehow the async SGD noise satisfies conditions which would allow it to be “linearized,” i.e. apply Taylor around the unperturbed parameters. It is really not clear to me why this is OK to do. Moreover, the authors don’t seem to be interested in providing a more standard analysis of SGD, e.g. along the lines of the Nadiraze et al. paper they seem to be well aware of. 
Specifically, the analysis allows us to grok the rationale for why the scheme might work, but seems to be primarily motivated by expediency rather than technical precision.

Meta-review: The paper proposes an asynchronous method for neural network training that decouples forward and backward passes using multiple threads.
The main concerns that remained after the author feedback phase were on two key issues: First, overlap with existing pipeline parallelism literature that wasn't adequately addressed or compared against. Second, there were concerns about experimental rigor, including missing baselines against standard SGD, lower accuracy than standard benchmarks, and insufficient analysis of memory requirements and computational overhead.

While several of the discussions were moving in a positive direction in the feedback phase, unfortunately the main concerns couldn't be fully resolved yet. 

We hope the detailed feedback helps to strengthen the paper for a future occasion.

Decision: Reject