Squeezing SGD Parallelization Performance in Distributed Training Using Delayed Averaging
Authors: Pengcheng Li
Yixin Guo
Yawen Zhang
Qinggang Zhou
Venue: ICLR 2022 Submitted (2022)
Keywords: SGD
distributed training
hide communication cost
convergence

Abstract: State-of-the-art deep learning algorithms rely on distributed training to tackle the increasing model size and training data. Mini-batch Stochastic Gradient Descent (SGD) requires workers to halt forward/backward propagations, to wait for gradients synchronized among all workers before the next batch of tasks.  The synchronous execution model exposes the overhead of gradient communication among a large number of workers in a distributed training system.

To this end, we propose a new SGD algorithm with delayed averaging, namely DaSGD, which can fully parallelize SGD and forward/backward propagations to hide 100\% of gradient communication. By adjusting the gradient update scheme, this algorithm uses hardware resources more efficiently and reduces the reliance on high-throughput inter-connects. The theoretical analysis and experimental results conducted in this paper both show its convergence rate of $ O (1 / \sqrt {K} )$ stays the same as Mini-batch SGD. A analytical model shows that it enables linear performance scalability with the cluster size.

Under review as a conference paper at ICLR 2022
SQUEEZING SGD PARALLELIZATION PERFORMANCE IN DISTRIBUTED TRAINING USING DELAYED AVER- AGING
Anonymous authors Paper under double-bling review
ABSTRACT
The state-of-the-art deep learning algorithms rely on distributed training systems tackle the increasing sizes of models and training data sets. Minibatch stochas- tic gradient descent (SGD) algorithm requires workers to halt forward/back prop- agations, wait for gradients aggregated from all workers, and to receive weight updates before the next batch of tasks. This synchronous execution model exposes the overheads of gradient/weight communication among large number of work- ers in a distributed training system. We propose a new SGD algorithm, DaSGD (Local SGD with Delayed Averaging), which parallelizes SGD and forward/back propagations to hide 100% of the communication overhead. By adjusting the gradient update scheme, this algorithm uses hardware resources more efficiently and reduces the reliance the low-latency and -hh-thhooughuut inter-connects. The theoretical analysis and the experimental results show its convergence rate O11/VK), the same as SGD. The performance evaluation demonstrates en- ables a linear performance scale-up with the cluster size.
INTRODUCTION
Training deep learning models using data parallelism on large-scale distributed cluster has become an effective method for deep learning model training. The enormous training data set allows huge batch of training tasks on different data samples running in parallel. The pinnacle of this method reduces the training time of the benchmark ResNet-50 from days to couple of minutes (Goyal
ctt al. 2017 You et al.) 2017b Akiba et al.] [017)] You et al. 2017a; Ying et al., 2018 Goodfellow al. 2016 During Mini-batch stochastic gradient descent (SGD), these workers have halt, wait for the computed gradients aggregated from all of the workers and receive a weight update before starting the next batch. The wait time tends worsen when the number of workers increases. As the workloads are spread over a larger cluster, the computation time is greatly shortened and the communication overheads take larger portion of the overall cost.
System designers address this concern by improving inter-chip connects with higher throughput and lower latency and refining network topology (Li et al. 2019), such as NVIDIA DGX-1 (NVI 2017) and NVIDIA DGX-2 (NSS 2018). Additional care has been given to reduce the intermediate steps that would increase communication latency. These methods effectively reduce the wait time during Mini- SGD on large-scale distributed system (Gaul 2019).
Alistarh et al. Wang & Joshi successfully 2018 Lin et al. 2018) are proposed to reduce the communication requirements.
Communication efficient SGD algorithms (Lin al. 2017 Wangni et al. 2018
2018 Dean et al.
2012 Recht et al.) 2011; Zhang et al. 2015 Wang & Joshi 2018
modified SGD algorithm shows their convergence rates comparable to Mini-batch SGD through both theoretical analysis and experimental results. Another challenge is to demonstrate good performance evaluation results based the common large distributed training system setups.
A modern data center design prefers cost-efficient hardware blocks and a balanced configuration for the typical workloads (Barroso al. 2018). Under these workloads, hardware resources utilized in a balanced fashion. A distributed training system works in the opposite manner. During forward/back propagations, the computing resources are fully used while the system inter-connects

---

Under review as a conference paper at ICLR 2022
completely idle. During SGD, the computing resources mostly idle while the system inter- connects are throttled at the peak throughputs. The performance of distributed training systems may be improved in addition to better hardware. That is, training workloads may be re-structured for balanced utilization of the hardware resources.
SGD method, enabling SGD running parallelly with forward/back propagation and balanced utilization of the hardware re- sources. It replaces Mini-batch SGD with Local SGD iterations. In a Local SGD (Lin al. 2018] Wang & Joshi 2018), each worker evolves a local model by performing sequential SGD updates, be- fore synchronizing by averaging models among the workers. DaSGD uses Local SGD to add weight synchronization points and allows weights to be updated between Local SGD iterations. Based on the network throughput and the model size, schedules delayed model averaging for a defined num- ber of Local SGD iterations, which allows workers to compute the next batch while the weights are transferred over a large distributed cluster. The theoretical analysis shows its convergence rate is O(1/v ((, where K the iteration step, same as Mini-batch SGD.
Inspired by the modern system design practices, we propose DaSGD,
The main contributions of this paper are the following.
We present DaSGD as an algorithm-syster co-design method for large-scale distributed training system. It enables designing more balanced and better-utilized system, more than new variant of the SGD algorithm. The discussions and analyses in this paper are organized around its equivalency to the traditional SGD and its benefit from the system design perspective.
We provide the theoretical analysis of its convergence rate. It shows the convergence rate at (L/V/K), the same as Mini-batch SGD.
Our experiments focus the training progresses (in terms of loss and accuracy) at the epoch level. It shows DaSGD allows the training converges at the same rate of SGD) epoch by epoch, which is a good indicator of statistical efficiency and the eventual time-to- convergence. The experiments also explore the proper ranges of these parameters.
A performance evaluation of real-life systems measures many performance issues in a sys- tem, such as the reduction algorithm, GPU interconnect topology and throughputs, network throughputs, which are out of the scope of our discussion. Instead, we abstract an analytical model from the key performance parameters of the system configuration and the training setup. The analytical model demonstrates DaSGD introduces linear performance scale-up with the cluster size.
2 BACKGROUND
2.1 STOCHASTIC GRADIENT DESCENT
Stochastic Gradient Descent (SGD) is the backbone of numerous deep learning algorithms (Ghadimi Lan 2013). Supervised deep learning demands massive training datasets. Training deep learning model needs many epochs for training to converge. A variant of classic SGD, synchronous mini- batch SGD (Bottou| 2010), has become the mainstream due a faster convergence rate., supported by prevalent machine learning frameworks, such as Tensorflow (Abadi et al. 2016), Pytorch (Paszke) al. 2019), MxNet (Chen et al.) 2015).
Mini-batch SGD as a weight update process is shown in Eq
#k+1
VF(
where x E RRd is the weight of a model, 1 is the learning rate, B is the batch size, S is the training (3) S is random sample, V FF is the stochastic gradient given the sample s ())
dataset, 8k
From a system perspective, a distributed training system may compute a batch of gradients on several workers. At the end of batch, reduction operation is performed on the gradients on a worker first and a worker sends out only copy of local averaged gradients. Further reductions are performed on gradients from different workers until final copy of the averaging gradients is obtained. The above
2

---

Under review as a conference paper at ICLR 2022
BWU
Fita
EMK
LRM
19/2
FiMEP
Windert
Updata Phrrondage
1 - 11P" a- n 2
Number
Staper
Figure I: A timing diagram of DaSGD.
equation may be rewritten as
"
Σ a( ())
(2)
where M is the number of workers, g(rkk ( is the stochastic gradient that worker j aggregates locally for that batch.
g
(oRI (
2.2
COMMUNICATION EFFICIENT SGD ALGORITTM
2.2.
ASYNCHRONOUS SGD
There are few asynchronous training methods, such as Downpour SGD (Dean et al. 2012). Hog- wild (Recht et al. 2011). Elastic Averaging SGD (Zhang al. 2015). In these models, every worker has its own copy weights. A worker performs forward propagation and back propagation on its partition of samples, and then sends the calculated gradients asynchronously to pool of parame- ter servers that manage a central copy of weights. The parameter servers update the central copy and then send the new weights asynchronously to each worker. While each worker communicates gradients at a different time and avoids congestions at worker inter-connects, the parameter servers might be performance bottleneck. For non-convex problems, ASGD requires that the staleness of gradients is bounded (Lian al. 2015) match the convergence rate O(1/v of synchronous SGD, where K denotes the total Iteration steps.
2.2.2 SGD
Another set of methods targets at reducing the frequency of inter-worker communication and is called periodic averaging or Local SGD (Wang & Joshi 2018 Wang Joshi [018 [in et al, 2018). A worker performs SGD its local copy of weights for times, where denotes the local iteration steps. After 7 local updates, local copies are synchronously averaged across all workers globally. Several works suggested that Local SGD incurs the same convergence rate (11VVK) as SGD. The total number of steps train model remains similar but the total amount of inter-worker communication is reduced by times. This has a similar effect as training with a large batch size, where the number of synchronizations decreases with increase of batch size. With Local SGD, SGD and forward/back propagations are still blocking while system resources are unbalanced.
DASGD
In this paper, we propose new algorithm, called Local SGD with Delayed Averaging, DaSGD for short. It aggregates gradients and updates weights in relaxed manner, which helps parallelize the computation of forward/backward propagation with two other execution components: the execution of global weight averaging and inter-worker data communication.
Our algorithm was initially inspired by the Local SGD algorithm (discussed Section Pp. Although Local SGD was designed to reduce communication and synchronization overhead, it still involves a significant amount of communication overhead. To further decrease communication overhead, even to zero, the proposed algorithm exploits delayed averaging approach that makes two novel improvements based on Local SGD. First, in order to merge remote weights by other workers with local in deterministic way, DaSGD serializes forward propagations and back propagations for dif- ferent samples. Second, workers start with local computations for the next local batch while waiting for the aggregation and synchronization of global weights. In this way, the global communication
3

---

Under review as a conference paper at ICLR 2022
Mini batch 9GD
Local
(6) DasGo
Figure 2:
Loss landscape of (a) Mini-batch SGD, (b) Local SGD, and (c) DaSGD. 12 samples are updated on two workers. The orange and green arrows represent the updated loss function of each sample, and the blue arrows describe the location of the updated loss function on the global model.
and synchronization overhead are hidden overlapped by local computations at the cost of de- layed update of local weights. However, theoretically we will prove that the convergence rate is the same as Mini-batch SGD. Furthermore, DaSGD parameterizes the overlapping degree so that when a large training cluster requires a longer time to synchronize, a worker may perform more iterations of local computations.
Fig. illustrates the proposed algorithm by showing a wall-clock time diagram of 6 training iter- ations. There are 2 workers, dividing batch into 2 local batches. Each worker computes 6 local batches. Each local batch contains Bi samples. Each worker maintains a local copy of model. Ac- cording Local SGD, for local batch, each worker operates Bi forward/backwart propagations and then updates the weights of its local model. After 3 local updates, a worker synchronizes local weights with the other workers, resulting in an AllReduce operation being generated average the model weights. In Fig. | all workers wait for, at local iteration 3, the global synchronization to be finished and then start to operate on the next local batch each, in the scenario of Local SGD.
DaSGD implements key feature by imposing delay update on Local SGD. As shown in Fig. 1 a worker, at local step 3, broadeasts its local weights to the wild and then immediately starts to compute on the next local batch, without waiting for the global synchronization to be finished. Later, at local iteration 4, the worker receives all the other workers' weights and then updates its local weights. This design very efficiently overlaps the communication of weights and forward/backwwar propagations of the next local batch.
In DaSGD, we use denote the number of local batches between two consecutive global syn- chronizations. Therefore, T is a controlling parameter that quantifies the number of propagations between weight averaging globally. During the delay update, both local computation and the global communication of weights are executed in parallel. As long as communication time is no more than the computation time of d local iterations, the communication time can be hidden in the overall model training time. Careful tuning of d and т can realize full parallelism of global averaging and local computations. Unlike Local SGD, does not have to be large, is not only used to reduce workrr communication overhead (Lin et al. 2017).
In the following part of this section, in order to compare the proposed algorithm and traditional SGDs, we start with the update framework of each algorithm, and then qualitatively analyze execu- tion time. Finally, we discussed the updated rules and the convergence rate in detail.
3.1 UPDATE FLOW OF DIFFERENT SGD
Fig. explains the mechanisms of weight update flows of Mini-batch SGD, Local SGD, and DaSGD by taking an example of a 2-worker parallel training process that sets the batch size as 2 samples. The workers are distinguished by yellow and green arrows. In the Mini-batch SGD (as shown in Fig. [a))),, every worker updates its local weights once every mini-batch, which is computed as the batch size divided by the number of workers. When both workers finish local updates for a mini-batch, local weights are merged to compute their average (shown by blue arrows). Next, both workers update their local weights with the average. Local SGD (shown in Fig. ((b)) reduces the weight aggregation times by letting every worker first update weights locally for continuous local batches in a row before a global merge is made. Local batch in the context of Local SGD is just a synonym of the mini-batch in the context of Mini-batch SGD.
Same as the regular periodic averaging method (i.e., Local SGD), in the proposed algorithm, each worker updates local weights for local batches before global aggregation. A novel change made by the proposed algorithm is to delay weight update from global to local after the global averag- ing. A worker may delay the update for d steps (i.e., samples) of local weight updates (d 1 in
4

---

Under review as a conference paper at ICLR 2022
this example, as shown in Fig. c)). With this novel algorithmic design, the time of global weight averaging can be hidden by parallelizing it with local computation by a worker, i.c., forward prop- agation, backward propagation, and local weight update. Large d can be set if the time of global weight aggregation is very long in a large-scale distributed training to shorten overall training time.
3.2 CONVERGENCE ANALYSIS
In this section, we provide theoretical analysis of the DaSGD algorithm. We will prove the con- vergence rate for DaSGD on non-convex problems and show that it converges at the same rate O(1/vK) as Mini-batch SGD and Local SGD. To facilitate the convergence analysis, we firstly introduce the assumptions.
3.2.1 ASSUMPTIONS
The convergence analysis is under the assumptions the following, which similar to the Local SGD (Wang & Joshi 2018):
Lipschitzian gradient: |l V F(x) [F(v)] S L||x yll
Unbiased gradients: Es,lz [g(x)] (F)
Lower bounder: F(x) Finf
Bounded variance: Esglello(z))
Independence: All random variables are independent to each other
Bounded age: The delay is bounded, d <
where S is the training dataset, Sk set { 5k 8 (00) of randomly sampled local batches, L is
(1)
the Lipschitz constant.
3.2.2 UPDATE RULE
12 nn (={2a)
(1-4)
(m)
Ex
(m)
nān (mn)
(4)
2/2 19 x
where (((m) is the weights of worker m at k-th iteration, 1) the learning rate, M the number of workers, and (m) the stochastic gradient of worker m. For every k that satisfies (k+1) mod r d, global average is updated to local weights. Besides, & is an auxiliary parameter to adjust the weight of local weights in contrast to the global average when fusing them together.
From equation 4
can define the average weight and the average gradient
M
M
AA =
M
Ok
M
k
Reformatting it, the update rule for the average weight is
1-d
E Σ
Σ
Pr( Hrktd 7
Irb+d4s +
Ork+dti
i=r-d
is observed that the averaged weight Mr(++1)+d is performing perturbed stochastic gradient descent. Thus, we will focus on the convergence of the averaged weight 1) which is common approach in the literature of distributed optimization (Wang & Joshi [2118] Wang & Joshi] 2018). SGD can converge to local minimum or saddle point due to the non-convex objective function F(x). Therefore, the expected gradient norm is used as an index of convergence.
3.2.3 CONVERGENCE RATE
K Σ [[FF(M))) k=1
The c-suboptimal solution of the algorithm is E&
S The learning rate is usually set as a constant and is decayed only when the training process saturated. Therefore, we analyze the case of fixed leamnng rate and study the lower limit of error convergence.
K
5

---

Under review as a conference paper at ICLR 2022
Theorem (Convergence of DaSGD). Under assumptions, if the learning rate satisfies 2Lmdg²
++ 2 + og < and 2Ly(T - d) - + 6f + 6 + 1- S 0 at the same time, the average-squared gradient norm after K iterations is bounded
1-
as follows
K 19FOW)))
2[(((1) - Funsl nk(Ed dd
n 2L (s'd+-dd
6o (6+ Σ of
M (6d ( sd+r-d
iur-di-
(ed d)(1-3)
r² (T d((++ n² 12 d)(1 +
K 1d++--d(11-)
RM
(Ed d)(1 {?)
where X3 = [ ..., " --]I [| is the Frobenius norm.All proofs are provided in the Appendix.
Corollary. Under assumptions, if the learning rate is 17 norm after K iterations is bounded by
M+V M
M the average-squared gradient
1 K 1
(P(())) M²² K3 1
Pinyl 21,0² (
M²
(1+ M
))
(1+
9-1
Σ Σe
K km
VMKied+
kJ
+d+ 1st-dim0
+
V
12d (+ () +
M
(Ed + r d)(1 (2)
K3
M
(6d + d)(1 {
M
12L de
8)(1 +
(Ed + d)(1
If the total iterations K is sufficiently large, then the average-squared gradient norm will be bounded by
19 [[F(m)) Fine] 21.02 [s"d+r-d
K
VMK(Ed+
Therefore, non-convex objectives, for the total iterations K large enough, DaSGD converges rate ((1/K)) consistented with the Mini-batch SGD and the Local SGD. Besides, it is worth noting that these three introduced auxiliary parameters (r, d and {) are mostly in the high-order term O(I/K²) and O(1/K²), which has little influence on the convergence of DaSGD.
3.3 GUIDELINES FOR USING DASGD
DaSGD identical Local SGD except that the global model is updated for delayed local steps. The tuning of the other parameters is the same as that of Local SGD. Therefore, in this paper, we merely discuss how to set this key delay parameter.
In order to overlap communication with computation in DaSGD, the weight/gradient transfer time to across workers is required to shorter than the time of d local iterations, that is, te < d fp. where tp is the computation time of one iteration. For deep learning systems, the weight transfer time to across multiple workers is approximately calculated as t, m x n.p Rp/BW, where n, denotes the number of parameters of the model, m the number of workers, and BW the bandwidth of the device. The computation time Ip of one local batch is approximately calculated as lp = B₁ x FLOP /FOOPS, where FLOP denotes the floating point operation counts of local computation. B, the local batch size. FLOPS denotes the computation speed of the device in terms of floating point operations per second (FI.OS)).
In nutshell, the delay is given by d 6y B; xBWXF Note that the delay is highly related to the structure of neural network models, e.g., the number of parameters and FLOOP, and the configurations of deep learning training (local batch, worker number, bandwidth of the device and computation speed). With the rapid improvement of the bandwidth and performance of distributed training, the mode size of the neural network grows relatively slowly. As result, in most cases, when the delay is one single iteration, i.e. = 1, the weight transfer can be processed completely in parallel with local updates. In addition, the worker number increases, the transfer time increases, and hence the delay would increase moderately accordingly. The cooperative design of various parameters in DaSGD and hardware is discussed in detail in the following sessions.
mxn, XFLOPS

---

Under review as a conference paper at ICLR 2022
Table 1: Validation Accuracy of DaSGD, Mini-batch SGD and Local SGD on CIFAR-10.
Model
Validation accuracy after 50 epochs
Mini-batch SGD
L*Loca SGD 2*DaDDG
32 batch
1024 batch
GoogleNet (Szegedy (015)
0.9467
0.9409
0.9468
0.9444
VGG-16 Simonyan & Zisserman
2014
0.9362
0.9264
0.9330
0.9343
ResNet-50 (Hc ct al. 2016)
0.9113
0.9037
0.9062
0.9088
ResNeet-101
0.9116
0.9019
0.9061
0.9045
DenseNet-121 (Huang al.
2017
0.9367
0.9332
0.9369
0.9357
MobileNetV2 (Sandler
2018
0.9230
0.9304
0,9241
0.9304
ResNeX129 (Xie et al 2017
0.9475
0.9403
0.9424
0.9415
DPN-92 (Chen el al. 2017
0.9507
0.9354
0.9513
0.9502
3 3 8 8
(4) NoogleNot
Rashel-50
(d)
1.5
T. E E 12 1
8 8
E
2 8 A00U0C
(8) MotsleNatt22
(Q)
DPN-92
Figure 3: Validation loss(dotted line), training loss, and validation accuracy(solid line) of different models on the CIFAR-10 dataset.
EXPERIMENTAL RESULTS
In this section, we will first introduce experimental settings, then the comparison of convergence for different models, and last the effect of different parameters for DaSGD convergence.
4.1 EXPERIMENTAL SETUP
We implemented our system based on the Fast.Ai (Howard 2018) platform upon CIFAR- 10 dataset. The learning rate is linearly increased from 0.0001 0.01 in the first 30% epochs and then decreased from 0.01 to 0.0001 in latter 70% epochs, by respecting One Cycle Policy (Smith 2017 A larger learning rate prevents the model from falling in the steep area of the loss function to find flat minimum, while a smaller learning rate prevents training from diverging and converging to local minimum. The proposed learning rate method assists in realizing high validation accuracy quickly (in a few iterations) so that we could only set total training epochs as 50 for a comparison between DaSGD and two other alternatives, Local SGD and Mini-batch SGD. The weight decay (commonly called L2 regularization) is 0.01. And the momentum of SGD, which accelerates gradients vectors drops the right direction, 0.9.
4.2 CONVERGENCE RATE AND ACCURACY COMPARISON
We compare DaSGD with Mini-batch SGD and Local SGD in terms of convergence rate and accu- racy upon a set of neural network models that are trained for 50 epochs for CIFAR-IO 10 dataset. All models trained with 32 workers. For the three alternatives, the batch size is 1024 and the total number of iterations is 2450. For Mini-batch SGD, according to data parallelism, the mini-batch size of each worker is 32. For Local SGD and DaSGD, the local batch size B, 32, which equals to the mini-batch size of Mini-batch SGD For Local SGD and DaSGD, the number of local steps is 4. For DaSGD, the delayed update steps is 1.
TABLE D first demonstrates that high validation accuracy to 0.9513 can be obtained with only 2450 iterations with 1024 of batch size, even without tuning hyper-parameters. For Mini-batch SGD, due to large batch size, the hyper-parameter need to be tuned carefully. Large batch size training
'The mini-batch size is concept in Mini-batch SGD; the local batch size is concept of Local SGD. They equal each other and are computed the batch size divided by the numher of workers.
7

---

Under review as a conference paper at ICLR 2022
leads to great accuracy loss. The syper-parameter recipe for large-batch training is complex and tedious, and the algorithms based on local update (Local SGD and DaSGD) overcome this problem, since the batch size in local updating is small (B/ //), which is B in Mini-batch SGD. Thus, without any hyper--arameter adjustment for large-batch training, in addition to MobileNetV2, the validation accuracy of Local SGD and DaSGD is higher than that of the Mini-batch SGD. Fig. 33 shows this more clearly. At the beginning of the training, since the batch size is large, the algorithm based on Mini-batch SGD is usually very unstable, and the validation accuracy fluctuates greatly. And, the convergence rate of Mini-batch SGD is slower than that of the Local SGD and DaSGD. At the end of the training. although the training loss of Mini-batch SGD smaller, Local SGD and DaSGD have small test loss and higher validation accuracy. In addition, compared with Local SGD, the validation accuracy of DaSGD is slightly reduced due to delayed averaging.
4.3 PARAMETER EFFECTS OF DASGD
We evaluate the effects of 5 parameters with respect to the convergence rate and validation accuracy for the ResNet-50 model based on DaSGD in Fig. 4 5 parameters are the number of workers m, the local batch size Bj, the number of local steps the local update percentage & and the delay factor d. We study every parameter by only tuning one at a time, with the rest set as the baseline setting: m 32, 4, d 2, Bi- 32, and { = 0.25.
Worker number m. Fig. T aa suggests that DaSGD has a fast convergence rate and high validation accuracy in general for any number of workers tested. As the number of workers increases from to 256, the convergence rate becomes lower and validation accuracy degrades. Since the local batch size remains unchanged as 32, when the worker number 256, the total batch size has reached 8192 (32 x 256), which results in decrease of validation accuracy of around 2% and an increase of training loss of 0.31. Since the number of local steps 4, DaSGD communicates once for a total number of samples of 32K (32 x 256 x 4). The CIFAR-10 10 dataset has only 50000 training samples, so the number of communications is just 2 for this large number of workers.
Local batch size Br. Fig. 4b) illustrates that DaSGD exhibits a good convergence rate with mod- erate local batch sizes. When the local batch size is large as 256 or small as 8, the validation ac- curacy is significantly reduced. Interestingly, the same observation is obtained in Mini-batch SGD, The phenomena are attributed to that large local batch size, though reducing the overall iterations, leads to poor generation ability, while small- size reduces the generalization error due to noise, but requires a large number of iterations. Hence, the selection of the right local batch size is critical to the performance of DaSGD. Based on our tests in Fig. 4b), 32 or 64 of local batch size is the setting of choice, resulting in the best validation accuracy and training loss when comparing to the rest of values.
It is worth noting that the total batch size is computed as B m Bj. When the worker number is 32 and the local batch size is 256, the total batch size rises to 8k, which faces the same challenge of tuning merrmaaraetters of large-batch training discussed above. To obtain a good convergence rate for such a large batch size needs careful coordination between multiple impactful syper-pprameters.
Number of local steps T. Fig. 4 (e) shows that as the number of local steps increases from 4 to 32, the validation accuracy decreases slightly and training loss increases. This concludes that for DaSGD, the number of local steps should be as small as possible, as long as T is large enough to ensure parallel weight communication is totally overlapped by local computation.
Local update percentage. Fig. d) shows that when combining the local weights with the average global weights, different percentages of local updates have little impact on validation accuracy. From the update rule equation 4 the local update proportion shares the same meaning as the momentum in hyper-parameters. One cycle policy in Fast.Ai has shown that different momentum has little effect on validation accuracy [Howard] 2018).
Delay factor d. Fig. 4e) tunes the delay factor from 0 to 7 by fixing the number of local steps as 8, since the delay factor is bounded by the number of local steps. Results show that the delay factor imposes little effect on the convergence rate. When the delay factor increases from to 7, the convergence rate slows down and the validation accuracy slightly decreases. Local SGD is just as the delay factor of 0. Thus, DaSGD incurs slightly worse validation accuracy when using the delay factor of 1, with the same local steps.
8

---

Under review as a conference paper at ICLR 2022
60
80
Ded
10
32
22
Docch Worker Number
Drchh
Creck
Decch
(b) Local Batch Size
Number of Local Steps
(d) Oeleyin Local Step
Figure 4: Effect of different parameters of DaSGD based on ResNet-50. The value in legend is the validation accuracy after 50 epochs.
Top5
PGB Desaa
Top1
25
0.5
20
20
teech
Difforent Algorthhm
tpech
3.
Top5
Top1
Fpoch
(b) Worker Number
looa Mee Leleer
Topp
Top1
3.
10 teech
25
20
20 opecs
25
20
(6) Local Step Delay
Figure 5: validation accuracy (left), training loss (right) and validation loss (right, dotted line) based on ImageNet dataset.
4.4 IMAGENET
We use Fast.Ai framework for training ImageNet. The learning rate increases linearly from 0.0005 to 0.005 in the first 20% epochs and decreases linearly from 0.005 to 0.00005 in the last 80% epochs. The weight decay set as 0.01, and the momentum of SGD is 0.9.
As shown in Fig. a)., three algorithms, which are Mini-batch SGD, Local SGD, and DaSGD, are trained in 20 epochs to compare the convergence rate and top- hop-1/top-5 validation accuracy in ResNet- 18. All models are trained on 8 workers and the batch size is 256. For Local SGD and DaSGD, the number of local steps is 2. For DaSGD, the delayed update steps d The top- 1op-1/to-55 validation accuracy of DaSGD (top-1 accuracy is 0.6461 and top-5 accuracy is 0.8582) is the same as that of Local SGD after 20 epochs, and is better than that of Mini-batch SGD. Although at the beginning of training, the convergence rate of DaSGD is slower than that of Mini-batch SGD, after 15 epochs, is much faster. We also evaluate the effect of worker number terms of the training/validation loss and top- 1/top-5 validation accuracy for the ResNet- 18 model based on DaSGD in Fig. 5t.). It can be found that the increase of worker number has almost no effect on the validation accuracy and convergence rate, which also reflects the application potential of the DaSGD algorithm in large-scale distributed training. Fig. 5ic) shows the results of DaSGD with different local steps and different delays. The larger local steps and the larger delay converge faster at the beginning of training, but the final accuracy is slightly poor.
CONCLUSION
In this work, propose new SGD algorithm called DaSGD, which parallelizes SGD and for- ward/back propagation to hide communication time. Just adjusting the update schedule at the soft- ware level, the DaSGD algorithm makes better use of distributed training systems and reduces the reliance on low latency and high peak throughput communication hardware. Theoretical analysis and experimental results clarify that its convergence rate O (L/VK). which is the same as the mini-batch SGD.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Nvidia dgx-1 with tesla v100 system architecture. arcttecccieeieeuurrreeee ivicia wtt.iia..coo.oo.toooeeoe 2017.
Nvidia nvswitch.
nvswitch- htw.::chhttetcccccccc--eeeeeeeee pdf, April 2018.
GaudiTM training platform white paper.
http:///aaaaa.aa///ooooooo//t//a 2019/06/Habana Gaudi wwwaaniinn-Paaffooooee
http://bannnaaaatta-aaaaaaaaaaaa wht.trope-.iiteppppee..p... 2019.
Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg S. Corrado, Andy Davis, Jeffrey Dean, Matthicu Devin, Sanjay Ghemawat, Ian Goodfellow, Andrew Harp, Geoffrey Irving, Michael Isard, Yangging Jia, Rafal Jozefowicz, Lukasz Kaiser, Manjunath Kudlur, Josh Levenberg, Dan Mane, Rajat Monga, Sherry Moore, Derek Murray, Chris Olah, Mike Schuster, Jonathon Shlens, Benoit Steiner, Ilya Sutskever, Kunal Talwar, Paul Tucker, Vin- cent Vanhoucke, Vijay Vasudevan, Fernanda Viegas, Oriol Vinyals, Pete Warden, Martin Watten- berg, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. Tensorflow: Large-scale machine learning on heterogeneous distributed systems. arXiv preprint 1.Xiv:1603.044666 2016.
Takuya Akiba. Shuji Suzuki, and Keisuke Fukuda. Extremely large minibatch sgd: Training resnet- 50 on imagenct in 15 minutes. arXiv preprint arXiv:1711.0433 2017.
Dan Alistarh, Torsten Hoefler, Mikael Johansson, Nikola Konstantinov, Sarit Khirirat, and Cédric Renggli. The convergence of sparsified gradient methods. In Advances in Neural Information Processing Systems, pp. 5973-5983, 2018.
Luiz André Barroso, Urs Hölzle, and Parthasarathy Ranganathan. The datacenter computer: Designing warchouse-scale machines. Synthesis Lectures on Computer Architecture, 13(3)i-189, 2018.
Léon Bottou. Large-scale machine learning with stochastic gradient descent. In Proceedings of COMPSTAT"2010, pp. 177-186. Springer, 2010.
Tianqi Chen, Mu Li, Yutian Li. Min Lin, Naiyan Wang. Minjie Wang, Tianjun Xiao, Bing Xu, Chiyuan Zhang, and Zheng Zhang. Mxnet: A flexible and efficient machine learning library for heterogeneous distributed systems. arXiv preprint arXiv: 2015.
Yunpeng Chen, Jianan Li, Huaxin Xiao, Xiaojie Jin, Shuicheng Yan, and Jiashi Feng. Dual path networks. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vish- wanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems 30, pp. 4467-4475. Curran Associates, Inc., 2017. URL http::/paae
nips cc/paper/
7033 103--aual-path-neerorre.
Jeffrey Dean, Greg Corrado, Rajat Monga, Kai Chen, Matthieu Devin, Mark Mao, Marc' aurelio Ranzato, Andrew Senior, Paul Tucker, Ke Yang, et Large scale distributed deep networks. In Advances in neural information processing systems, pp. 1223-1231, 2012.
Saeed Ghadimi and Guanghui Lan. Stochastic first-and ordeth methods for nonconvex stochas- tic programming. SIAM Journal on Optimization 23(4):2341-2368, 2013.
Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep leurning. MIT press, 2016.
Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, An- drew Tulloch, Yangqing Jia, and Kaiming He. Accurate, large minibatch sgd: Training imagenet in hour. arXiv preprint IrXiv:1706.0266 2017.
K. He, X. Zhang. S. Ren, and J. Sun. Deep residual learning for image recognition. In 2016 IEEE Conference Computer Vision and Pattem Recognition (CVPR), pp. 770-778, 2016.
Jeremy Howard. Now anyone can train imagenet in 18 minutes. https: www. Fast.ail
20118/8/10/fastaiiaa www.ddiuummageee...m August 2018.
10

---

Under review as a conference paper at ICLR 2022
Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Weinberger. Densely connected convolutional networks. Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 4700-4708, 2017.
Ang Li, Shuaiwen Leon Song, Jieyang Chen, Jiajia Li, Xu Liu, Nathan R Tallent, and Kevin J Barker. Evaluating modern gpu interconnect: Pcie, nvlink, nv-sli, nvswitch and gpudirect. IEEE Transactions on Parullel and Distributed Systems, 31(1):94-110, 2019.
Xiangru Lian, Yijun Huang, Yuncheng Li, and Ji Liu. Asynchronous parallel stochastic gradient for nonconvex optimization. In Advances in Neural Information Processing Systems, pp. 2737-2745, 2015.
Tao Lin, Sebastian U Stich, Kumar Kshitjj Patel, and Martin Jaggi. Don't use large mini-batches, use local sgd. arXiv preprint 1rXiv:1808.072111 2018.
Yujun Lin, Song Han, Huizi Mao, Yu Wang, and William J Dally. Deep gradient compression: Re- ducing the communication bandwidth for distributed training. arXiv preprint arXiv:1712.01887, 2017.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary Vetito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. Advances in Neural Information Processing Systems 32:8024-8035, 2019.
Benjamin Recht, Christopher Re, Stephen Wright, and Feng Niu. Hogwild: A lock-free approach to parallelizing stochastic gradient descent. In Advances in neural information processing systems, pp. 693-701, 2011.
Mark Sandler, Andrew Howard, Menglong Zhu, Andrey Zhmoginov, and Liang- Chich Chen. Mo- bilenetv2: Inverted residuals and linear bottlenecks. Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 451 4510-4520, 2018.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv:14099 1556, 2014.
Leslie N Smith. Cyclical learning rates for training neural networks. In 2017 IEEE Winter Confer- ence on Applications of Computer Vision (WACV), pp. 464-472. IEEE, 2017.
Christian Szegedy, Wei Liu, Yangqing Jia, Pierre Sermanet, Scott Reed, Dragomir Anguelov, Du- mitru Erhan, Vincent Vanhoucke, and Andrew Rabinovich. Going deeper with convolutions. In Computer Vision and Pattern Recognition (CVPR), 2015. URL http:://axxii..t/////// org.abs.. 1409. 4842]
Wang and G. Joshi. Cooperative sgd: A unified framework for the design and analysis of communication-effiiies sgd algorithms. arXiv preprint arXiv:/808.0755 08880007766..... 2018.
Jianyu Wang and Gauri Joshi. Adaptive communication strategies to achieve the best error-runtime trade-off in local-update sgd. arXiv preprint arXiv: 2018.
Jianqiao Wangni, Jialei Wang, Ji Liu, and Tong Zhang. Gradient sparsification for communication- efficient distributed optimization. In Advances in Neural Information Processing Systems, pp. 1299-1309, 2018.
Xie, R. Girshick, P. Dollár, Z. Tu, and K. He. Aggregated residual transformations for deep neural networks. In 2017 IEEE Conference Computer Vision and Pattern Recognition (CVPR), pp. 5987-5995, 2017.
Chris Ying, Sameer Kumar, Dehao Chen, Tao Wang, and Youlong Cheng, Image classification at supercomputer scale. arXiv preprint 1 1.0992,, 2018.
Yang You, Igor Gitman, and Boris Ginsburg. Scaling sgd batch size to 32k for imagenet training. arXiv preprint arXiv: 038888 6, 2017a.
11

---

Under review as a conference paper at ICLR 2022
Yang You, Zhao Zhang. James Demmel, Kurt Keutzer, and Cho-Jui Hsieh. Imagenet training in 24 minutes. arXiv preprint wrXiv:1709.050111 2017b.
Sixin Zhang, Anna Choromanska, and Yann LeCun. Deep learning with elastic averaging sgd. In Advances in neural information processing systems, pp. 685-693, 2015.
A APPENDIX
CONVERGENCE ANALYSIS OF DASGD
A.1 ASSUMPTIONS
We define some notations. is the training dataset, Sy is set { (80) Sk s..)) of randomly sampled local batches at M workers in k iteration, I. is the Lipschitz constant, d is the number of local iteration that global weight updates are delayed, t is the number of local steps, x is the weight of devices. The convergence analysis is conducted under the following assumptions:
(M)]
Lipschitzian gradient: ||
F(x) 4 F(yil & L|a vll
Unbiased gradients: Es,1= [g(x)) FF())
Lower bounder: F(x) Fins
Bounded variance: F=s,1=lo(()) F(=)]| o²
Independence: All random variables are independent to each other
Bounded age: The delay bounded, d S T
A.2
UPDATE RULE
The update rule of DaSGD is given by
k
(m)
179
(m) (m) 1-8
otherwise
(m) (m) Eor
k+11
ng
M
U) F ng (ob2a) (k - d) mod
(m)) is the weights at m worker in & iteration, is the learning rate, M is the number of where de workers, g (m)) is the stochastic gradient of worker m, & is the local update proportion, delayed update is the case (k: + d) mod r O.
Matrix Representation. Define matrices X GR dx that concatenate all local models and gradients in A iteration:
X = [.., x/
G2 = (1 ,.... (m))
Then, the update rule is
(X, G (1- (X G (k 1- d) otherwise
mod T = 0
X
(5)
Update Rule for the Averaged Model. The update rule of DaSGD is given by
[ (mm) (m)
otherwise
k
(m) Te+1
Eor
(m)
ne (m()))
+
1-
M
Σ
M
uk-d
11
() (=
(k + - d) mod =
1=1
Here, we set
M
M Σ
36
M 1=1
k
0k
M
x
im1
12

---

Under review as a conference paper at ICLR 2022
The average weight on different workers is obtained by
Te+1 20+1= {
Tk 19k: {. + (1 E) nkgx 17(1 - =))((xkd))
otherwise
(I: + 1-11 -d) mod ==0 0
When = T(K + 1) for mod = 0, we have
Tr(k+1)+d {d-(k+1)+d-1 (1
=79-(k+1)+d-1- (1 ()1
r-1-d
= Eū+k+d + (1 -)T+A-d En
Orktd+i - (1 (1-E)n
Σ
Ork+dti
1=
I-1-d
I-d
= Trk+d -1
5 Brk+d+ii
Irktdti
+ Σ
Irk-d+t
1=0
Brkid 1)
c Σ
grk+d+i+
Grk+d+i
imr-d
If we set K(k) Th + d
IK(++1) = TK(R)
Σ i=T-d
JK(K)++ +
Σ (K(K)++
For the ease of writing, first define some notations. Let Sy. denote the set { mini-batches at m workers in iteration k. Besides, define averaged stochastic gradient and averaged full batch gradient as follows:
(1)
(m))
sk of
M
I-1-d
9K(R)
Σ
Σ
Eg
(m) (rk+d+t)
+
Σ
(m) x (Tktd++)
(6)
M
1=
1-d
HK(()
1
Σ
F
(Tk+d43)
(mm)
F
I (Tk+
(m)
M
m=
1=0
(k(k)
M
Tkttd
(8)
(8)
Then we have
#K(++]] = PK()) 1/9
A.3 CONVERGENCE RATE
Theorem (Convergence of DaSGD), When the learning rate satisfies the following two formulas at the same time
" + 612
d)
2 - +
GgIL212d 50
1
2d d) dd 0
2L d) E
1 5²
Then the average-squared gradient norm after iterations bounded as
K
1
(x({)
K
k=
2 [F(()) F
+ n2L 2
(1+(1+
Ed+T- Σ
ΣΣ
T-1
Σ 02 12
(1++
M(d + + 11
+ d)
(-r-d 1=
122 222 - -d)(1
v/ 12T.2 d (1+ +
|[FF(X)))
K
(Ed+T-d(1--
KM ( (2)
13

---

Under review as a conference paper at ICLR 2022
(2) where j4 x E== t 7k+dd
|l is the Frobenius norm.
Corollary. Under sumptions, if the learning rate is = M+V M
M
the average-squared gradient
K
norm after K iterations is bounded by
k
(K(
K
k=1
2 (F1) Finsl
2Lo² e CT
+ VMK (Ed+T-0
MM + d)
M
V
Σ ΣΣ
T-1
M
(o
+
1+
1+ M
K
M
{d+T -
K3
(Ed -d--T d)(1
1=r-di=0
M
V
12do ()
M
V
(2 + d-1
Σ
IlFF(X)))1
+
1
K3
M
(Ed+r-d(1--)
K
M
- E?)
the total iterations sufficiently large, then the average-squared gradient norm will be bounded by
2[F(m) Fmnl + 2Lo² T -
E
K
VMK(Ed+T +
A.4 PROOF OF CONVERGENCE RATE
Lemma 1. If the learning rate satisfies 7) S min 2L 2 and all local model parameters are initialized at the same point, then the average-squared gradient after K iterations is bounded as follows
K
Ex(
| (((K(()))
K
k=
2 [F(()) - Finsl
2Ln [52d +
+
(EEd + d)
M(dd d)
+ KM + d)
1
M d K
Bx(() (K(K) Ftktd+i
(m)
+ Σ
[x(() |
I
(m)
k=1
==0
i=7-d
Proof.
From the Lipschitzisan gradient assumption | F(x) -VF()) s A/|x - wl1. we have
F(XK(+1)) F(Xx()) ( (VF((X())))))) XK(+H)) Xx(O) + |x((011) Xx(O)l
= 17 (VF((X())))) (. + Lod
2 ||
Taking expectation respect to SK(K)) on both sides of equation we have
Li
Ex() [F(Xx(+1)] F(Xx(a) S - 7BK() (K))()))))) + Ex(
||
2
From the fact
1 (1la]12 + ||b|| ||a - -)112)
(a, b) =
14

---

Under review as a conference paper at ICLR 2022
have
La Ex(
(K()) [F(Xx(+t)) F(Xx()) S (B ( +
||Sx<o:||
2
Combining with Lemmas 4 and 5, we obtain
BK(() [F(X((+1)]] - F(Xx())
LT2² Bx( [|0
S B))) (VF(Xx()))
Ed + r
LnR²²²
S -
+
[de + d)
2
M
+
Lnp
mh
Σ
|VF (X (x+++++1))1
[Tn (T d)
m/
Σ
|FF (X+++++))1
M
2M
M
2M
i=r-d
==0
M
T I-d Σ
T-1
+
(F((K())) - VF ((imtdss) |1²
+
Σ
(((x(())
-FF
[m) VF
(cfMtd4s) 11
2M
m=1
1=0
1=r-d
Ed + T
d
LaP
|[FF())()
Ide2 TT- d)
1)
M
+
Lnd de?
n
Σ
I (X
+
Lnp d)
ne
r-1-d
Σ 1=
IVF (X (X+++a+:)1f
M
2M
M
2M
i=r-d
T
(m) | - skt+d+i
(m) Tkt+d+i
+
PK(1)
(10)
2M
where equation 10 due to the Lipschitzisan gradient assumption After minor rearranging and according to the definition of Frobenius norm, it easy to show
- v/1-
Ed + r d ((X(()))) 1
2
Inpo²
<F((K())) - EK(() [F(*((+1)] +
<
[de² +
d]
M
DE ne
T-1
Σ
IVF (X+++4+))1
d)
m
7-1-d
|VF (X+++a+))f
+
M
2M
2M
nL
2M
||x000
Tktdtti
(m)
||
2
+
Σ i-T-d
(K(())
Tk+t+++
(m)
2
Taking the total expectation and averaging over all iterates, we have
Ed + - d
K
11
2
EK(()
K
k=1
F(N1)
-Fint
[dg² + d
K
M
+
dEP
mi
K
Σ
T-1
1 (X +
TTp(T - d)
ns
Σ Σ
K T T-1-/ 1-d
l (X,
(X+++d+))11
KM
2KM
KM
2KM
i=r-d
k=
1=0
nI?
3KM
M Σ
T----d
Σ
(K())
Tktd+ii
(m)
2
+
Σ
--1
(K((K)
Fok+d+s
(m)
i=
15

---

Under review as a conference paper at ICLR 2022
Then, have
1
2 (F(())) Pinyl MK(EE +T -dd
2n [5ad + d
(K(
Σ 1I
K
M MEd
d)
2 - KMi + d)
K
BK(8) II (XrR+a+))
k=
2L d)
E KK() II (X (x+++1)))
KM(Ed + d)
I
7-1-d d
M
Ex(R)
[K(()) - x xk+dd+
(m))
KMiEd +T d)
km
1=0
m=1
ET?
K
Σ
M
Ex(e)) (K(K) - 2 +k+d++
(m)
2
KM(Ed+ d)
k=
A=T
m=11
(11)
If the learning rate satisfies 77 S min { 22de + 2L(r-d) }. then
EK(
1
7 F
((FF(())))
2 (FF())) Fingl nK (K(Ed +
2Lmo² + -d
K
M MEd + +T d)
L2
t --1 1-d
M
Ex(K)
(m) [K(()) - 2 7
KMiEd+7 d)
k=1
i=0
ET?
K
M
[k(()) - F+++d++ Ex(e))
KM d)
kum 1. AmT el
m==1
Recalling the definition (.(()
33 Eis
M
I Frttd Xx(e)MM/A /M and adding positive term the
(8)
RHS, one can get
Σ
Σ
[k(()
x! (m)
2
Σ i=r-d
[ Xektatelle
#ktddti
We have
Ex(
1
Σ1
II [[
2 (F( - Finyl
2nno² 2 [52d + T - d)
K Rm
<T(Ed+--o T
M(d + T d)
12
r 7-1 1-d
EK(R) X Xrs4d+ell
KMiEd +T +
d)
k=1
ET?
Ex(a)) [Xyktad - X
KM d)
k= L=
Lemma 2.
2dg² T-1
2(T d)
7-1-d
|
Σ
II (x
(x4+44)))1
Σ
| (X (X+444+))1 (12)
M
i=r-d
16

---

Under review as a conference paper at ICLR 2022
Proof.
|
<
1
Σ
1
M
7F
2
(m)
+
1
1- d M
Σ m=1
F
I (rk+d+t)
(m)
M
M
==
2de2
Σ
M
7F F
I (rk+dti)
(m)
2
+
2(T - d)
T- 1--
Σ m=1
M
7
2 (xb-dtts)
2
2
M
im d
m==
k=
(13)
2dL²
Σ
Σ
M
F
(m) (
1|
2
+
2(T d)
r-1-d
Σ t=0
Σ
7F
2 (
(m)
112
M
M
d m=
(14)
2de2
2(T 2(T- GQT-0 d)
7-1-d 1-d
= M
Σ
lI (X (x+++++)112 +
(X +k
(+++=++))1?
M
where equation 13 is due to ||a + b11 s 2 vector norm and Jensen's is inequality.
||||| + 2 [161] equation 14
comes from the convexity of
Lemma 3. Under assumptions Es.le [s(x)] = F((x) and Es, - the following variance bound for the averaged stochastic gradient:
so², we have
Ex(3)
[|S
- Hx
[1]]
S
202
[de²
+ d]
(15)
M
Proof. According to the definition of equation 6 equation 7 and equation g
we have
|||9K()) - Hx(x ||*]
Ex(a)
T-1 M
T- 1-d M
M [K((K)
Σ
Σ
(m)m))) (xttttds)) - VF (a.m)
(Tk+++s)) ]
+
Σ
9
(n.(m)
(o(ttatt) - VF (a.(m)
(Tr+td+i)
i=r d 1==1 1
1=0
m=1
<
M
2
ER(A)
M
9
(2/kto+s) ) - DF
(m)
-FF (2) (m)
(Tx++d+s) )
+
7 1-d
Σ
9 (Frktd+s) VF
(afm))
(a.(m))
(Tk++d++)
d
1=0
(16)
M22 ER(H)
2
g²
Σ
--1
9 (m)
(nritats) ) - -VF (2))m)
(xk+++t)) )
1|
7 7-1-d M
g
x
(mx)
- VF
(k++++)) 11
(ms)
imr-d d m=1
m=1
(17)
M
x ( - VF (m) (zhetdts) .
(1) (#thtdts) - F (1) (2122ddss)
(18)
j&H La
d M
9 (rk+dtts - 4 (aintati) .9 (1 (aibtetts)
(m))
- V F (1l() (olitttts)
(19)
25a
Σ
M
Ex(e))
lo (m) (aimtats) - -FF (s(mtats) 11²
(m))
+ M
2
7-1-d M
Σ
Ex(M)
| (stxtate) - VF (m))
(m(xtatt))
)(²
||²
M
i - m=1
==0
m=1
(20)
where equation 16 is due to ||a + b112 < 2 ||al|2 + + equation 20 is due to si are independent random variables and the assumption Es le [x(x)] F(.).. Now, directly applying assumption
17

---

Under review as a conference paper at ICLR 2022
[s,1=1l9(2) VFF))]] f 0² to equation
20
Then, have
2
1-1
M
1-1-d
M
20²² M
Ex(x) [|0 - H
Σ
Σ
2
0²
[d5² + T
d
M
M
m==1
==
m=1
Lemma 4. Under assumption Es [g(x)] = F(x), the expected inner product between stochas- tic gradient and full batch gradient can be expanded as
(K(M) (VF((KKO 9x()))
Ed + T d
T-I
r-l-d
(F(X)())
Σ
| (X
I F (X,k+o+s)l
2
2M
i d
T-1-d
Σ Σ
VF(X(())) vF (F(" (cfmm) (Tk++++))
||'+5 Σ
(F(x(()) vF (wiiitatt) 11²
2M
d=T-d
Proof.
Ex(M)
-x(()) (
M Σ
( )
Σ
(m)
(2 (m)
SM
9
9
m=1
M
I-
M
E M 1=
Σ
(FF(X(()))
(ufmtatt))
(m)
+
FF(X(())) VF (m))
M
1=0
m=1
Σ
T-1
Σ
M
|F (2)m)
(zimtett) 1| (X(xx()) - -F (F (m)
(simtate)
12
2M
i= dm=1
(21)
Σ
Σ
|
[F(( /F
(m)) (Trttdts) (1² -1 VF (2.mm)
(m)
11"
(xx++d++))
2M 1=0 m=1
(22)
r-1-d
Ed + d
1
E Σ | (X
Σ
I| (XTR+td+:)1??
+
2M
M
d
FF(XK()) VF
(T
|| +5 Σ
22) (m) F (F(((()) FF
11?
2M m=l
where equation]
21 and equation
22
come from (a, = (1la)12 + ||b112 - -lla - -611)-
Lemma 5. Under assumptions Egiz [s(x)) = V Fxx) and F < d² the squared norm of stochastic gradient can be bounded as
202 M
2de²
2(T d) r-1-d
Ex(3)
||
[d
+
d
Σ
7 (X (X+x+++))l
Σ
A (Xr++4+:)1?
M
18

---

Under review as a conference paper at ICLR 2022
Proof.
Ex(())
||
[|SK(A) - (K [x( + (axco)/xxslll
(x(())
[|@K<(] - -Hx(wol' 11 + +|76x(00)1'
= Ex(A)
20
[dt² + d] + 2dl²
2(T d)
r-1-d
Σ ll (X
Σ
11 (X
M
M
M
i=0
(23)
where equation] 23 follows equation 12 and equation
15
Theorem (Convergence of SGD). Under assumptions, when the learning rate satisfies the follow- ing two formulas at the same time
2Lnd E + -d)
=
1-
2Ln(T d) ++
1177 0
g-
Then the average-squared gradient norm after K iterations is bounded as
K
|FF(K(()))?
(K)
K
2 (F((H) - Finsl
1j2Lo² k d (1)
T-1 Σ 02 n
(oo
Ed+T-d Σ
+ "
+ (K(E++T==
M(dd +T T
t=r-di=0
+ 1/2 12 d) (E) v/2 (T () + d-1
KM d) 52) |VF((
K
(Ed + - -dd(1 - 2
where pa = N E x +k+d || || is the Frobenius norm.
Proof.
Recall the intermediate result equation in the proof of Lemma 1:
||F
2 (F(()) Finyl - d)
2Ta [g2d - - c]
Ex(R)
+
K
M(Ed F -
2Lnd -
Ex(a II (X (X+
KM + d)
k=
2Tm(T d) -
ER() II (X++++4))11
KMiEd + d)
I2
EK(R) X Xrx+d+
KM + + d)
k=1
EL?
Ex(8) X - X 1|
KMiEd + d) k= I=T-
(24)
Our
goal is to provide an upper
bound for the network error term
Ex(K) [ X X First of all, let us derive specific expression for
19

---

Under review as a conference paper at ICLR 2022
Xyk+dJ d According to the update rule equation |
one observe that
Xrk+aJ Xxb+
(e - 1) + E
Grk+d+j
5=0
-X -+d-- (J-I) (1-)) J( 11) + Σ
Grk+d+j
5=
(X+(k-)) - En Σ
G Gr(e-1)+dti + IGG
G
1=
1=
2
= xx -1) 17
G (k) - 1) + 1 Σ
Grktdtj
1=0
1=
c'Xa(J I) 17
Σ
(k-)))) (J I-1)+ -1)+1) +1 Σ
Grk+d+j
j=1 1=0
1=0
T-1
5 - (xax1- I) 11
2 (G 1I)+ Σ Grk+d+j
f=1 i=0
d-1
(1 - I)
5
Σ
G. - 1) -
2 G ( - 1) + Gzk+d+j
i=1
/=1 1=0
1=0
d-1 Σ
= -
G. - G - Σ Σ
e G -1) + Σ
-1)+1)
Grb+d43
(25)
1=1
1= 1=0
1=
where equation follows the fact that all workers start from the same point at the beginning of each local update period.
20

---

Under review as a conference paper at ICLR 2022
Accordingly, we have
EK(R) [X - Xxx+d+ole
d-1
b
= Σ Ek(k)
Σ
-)
Σ
2 -+(k-))+4+60 -1) + Σ
G G+t+d+i
Iar-d
==1
j=1 ==0
1=0
d-1 Σ
2
<31) (x(s)
< d
GJ - 1)
+
G (lk ((a--tati(JJD
Σ
G
k k+d+t
1=1
|=1 1=
1 d 1=0
2
d-1
k Σ
<31 EKI EK(M))
2 d
Σ
G
+
E
G f)ttt
+
Σ
Σ
G k+t+++
(26)
F
j=1
1=0
F
i=0
2
M
d-1 Σ
r-1
-31/² 2
>
22
g(( mm))
dE<(())
ΣΣ
ga (m)
(k (k-
+ EK(R)
Σ
Σ
g(a (m)
+k+
1=7-d
M
M
=31 d
Ex(K)
2k
Σ
(m))
+
Bx(
(m) g
r(k (kk-)))dts)
Bx(R)
Σ
g( (m)
m=1
m=1
m=1 i=r-d
i=0
Ti
Ta
T's
(27)
where the equation 26 due the operator norm of I is less than
For T2, we have
M
k
(K(
g( (m)
7(k- mtddl
m=1
1=0
2
M
EK())
g (mm) (m)
((k- (1)-))+-1) Fz (((=))))+44))
7 F(x (m(m)
(m)
j=1
M
M
2
Ex(()
g ((kkk))))+ti
- F
F(r (m)
((kk)))+d+))
+2
EK(M)
F (m)
(kk-))+
m=1
j=1
t=
TB
For the first term T4, since the stochastic gradients are unbiased, all cross terms are zero Thus, combining with Assumption of bounded variance, we have
M
((k--)+++)) - V F Fx (m) (m)
T4 =
E E(())
m=
j=l
M
2
<
(28)
1
where equation 28 according to the summation formula of power
80
g²
Σ
25
21
e2
1=1
21

---

Under review as a conference paper at ICLR 2022
For the second term T5 we get
1
+d Ie =
k-1
T3 = 2
(m)
= 2(
mrtatt)
{m)
P
j=1
1=0
1=
Substituting the bounds of Ti and T3 into T2. we have
2M
1
T3 R
+
E
mm)
1 g
r=
For T1, we have
ER(AYS 22
Σ glag m))
Σ ERCA)S2R 22
g0(2 m) )
Σ V F((s (m))
2
E E
52
|0(, (m)) v F(0)
+
Ex(
2*
Σ F(
mm)
To
For the first term To. since the stochastic gradients are unbiased, all cross terms are zero Thus, combining with Assumption of bounded variance, we have
M d-1
M d-1
To To= 2 m=
Σ
5
22k ((a(")))-V((((")))
- (mm)))) S 252h
ΣΣd o²= 25
Mdo2
m=1 i=1
For the second term Tr, directly applying Jensen's inequality, we get
M
d-1
M
Th = 2
Σ
E
2k
Σ
(a (m)
< 2d
E E
2k
7 F (cc
(//))//
2d
1 )1
m=1
m=1
Substituting the bounds of To and T? into Ti, we have
Ti < Mdo2 + 2d
For Ts, we have
To
d Σ Σ
1
ERC0
Σ g (m))
1 M
= 7 Σ
Σ
E EK(N)
Σ
- V (((o(rttttt)
(m))
v (
(otd)s)
(m)
m d=r-d
1=0
1=0
2 M
Σ
2 M
1
2
<
Σ
Σ
EK(H)
- (
+
Ex(E)
Σ
V
(
(m)
d -
d m=1 1=
1=0
< 7
2 M 7-1
Σ
Σ
( - F (m)
Tk++++))
1
+
2 M
d
Σ
7-1
Σ
RK(KK)
((r
(m²)
m=
0=
1=0
2 ΣΣ Σ
2
2 D
7F(x (m)
<
E
Ex(3)
7k+dtt))
i=
=
2M 1-1
Σ
2
Σ
M
Σ
Σ
Ex(H)
2
d
d
t=
22

---

Under review as a conference paper at ICLR 2022
Substituting the bounds of Ti, T2 and T3 into equation 27 we have
Σ BK(K) [xr++J- X-x-4+il?
2M
< 31 d 25 25th 2
+
+
2d
2h
+2
(((h-))
E
F
(m)
1-
r=
2M
Σ
T-1
1
2 + d
2
Σ
M
K(() |
12
+
d
i=r-di=0
-=
And in the same way, we have
Σ ER(N) [ X-ktd-Ilf
< 317² d)
26 Mdo
+
2MTO²2²
+
2d
2k
1 F (X.) }F +
- 2(k6-))
k-1
E
V
F
(m)
1
--
1=0
2M
r-l-d
2
2
M
T-1-d
Bx(
VF (m) (ktd
|
d
1=0
1=0
m=1
1=0
==0
Then, summing over all periods from k t = K, where K is the total global iterations:
K
EK(A) [ - Xexta+illE
#=11=r-4
K
2MTo2g²
d-1
A-1
S 317" d
262h Mdo²
+ 2k
1 FX,)) +2
Σ
2(
E
1 1- g2
1=0
+ d
2M
Σ
T-1
Σ
1
2 +
Σ
M T-1
Σ
V EK(K)
F (F
i=0
m=1
-- ==0
S 6nj2 d
2M + 2d
d-1
11
F
+
62
+
2
Σ
T-1
De
1 82
I=r-d i=0
K k-1
+ 2d dd
Σ
2(()-))
Σ E 7
(m)
2
+ 6n7²
Σ
Σ
EK(K)
k=1
==0
k=
(29)
Expanding the summation, we have
K
(m)
I 2
mot+ts)
E |
Σ ((()-))
E
Σ (2(
K
E [|
(30)
23

---

Under review as a conference paper at ICLR 2022
And in the same way, we have
Σ L
K
E
+
(31)
k= 1=
A= 1=0
Plugging equation 30 and equation 31 into equation 29
(x( [ XeRtotill
k= t=
2²
Gn dr
$ 6nj d
dM 2d
| F 11
+ 6r/ MK
Σe
1 6
1
I
6nj² d
K
E |
(X
|1 + 61j2d
E P
2
k=
0
k=1
And in the same way, we have
1-1-d
Σ
E EK(R) [
Xektd+1lf
d-1
61)((T - d)
< 6n/² (T d)
2M + 2d
Σ |VF(())) //
+ 6r7 MK MK
Σo
g²
-
1---d
617 (T d)
K r-1
K r l-d
ΣΣ
E
|| FlIFF(Xaa (XF((x++++))l
607
d)
Σ
1 g2
i=0
Recall the intermediate result equation 1 in the proof of Lemma 1:
1 K
Ex(()
(((()())))
K
k=1
2 (1(1 Fingl
n/2oa² [g2d -
(1((1+
T-1
M(dd - Ed+t-d Σ
0 +1
(((Ed + d)
T d) (
1 12do2L2 d)
v/2 (2 d1 +E) d-1
|VF(()))
K
(Ed + d)(( 52)
KM (Ed+T- d) 22)
2ndds2 + SEL " d461 1 (T- + 1/d22 K
Ex(A) | (X (Xr++++))1
K KM + d)
k=li
2LT(T d) E+ +
d+6l np (r n +
d
K
+
Ex(e) I (X,++4+))1
K KMd +T
When the learning rate satisfies the following two formulas at the same time
2Indg²- E 66 d)
+gTT212 50
E²
- d) (r 00
2Ln(r d) -+
1-
And
K
K Ex(M) || |F (Xr8+d+))11=- Et Σ
ΣV
IVF
24

---

Under review as a conference paper at ICLR 2022
Thus, have
1 K
(K)
A (
K
k=1
2 (F1 Fingl
722 [52 + T d]
17 (1+
T-1 Lo
Ed + Σ
nK(Ed+ + d)
((d + T d)
(Ed+T - -c)+--d)(1-5)) -
n² (2 -d)(++E)
n² (T - +
|VF((
K (Ed -dd[1 -1())) KM
TT d) (2)
Corollary 1. Under sssumptions, if the learning rate is 1) norm after K iterations is bounded by
M+V
M K
the average-squared gradient
K
(X(E)
K 1=1
2 (F41) Finsl + VMK T
2Lo² (2d+T= d
(Md + d)
M
V
61)(1+5)
Σ
2
V
(1o
14
1
K3
M
+d+T- d
K3
M
(Ed -d)(1 E2)
1=T-d 1=0
+
M
(
1+
V
d) 12do -
M
1 +
d2L3dE
d) (T d-1 (Ed - T ( E?)
Σ I[FF(X))
K3
M
K
M
If the total iterations K is sufficiently large, then the average-squared gradient norm will be bounded by
K
4 F(F())) < 2(F(m) Finsl + +Lo= (g2d+ d
E
K
VMK(Ed+T TT
25


Reviews:
[{"review_id": "fWjuw1AA4PH", "reviewer": "Reviewer_NVwg", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "In this paper, authors consider the Distributed SGD with delayed gradients and bounded delays. This assumption on delays allows algorithm to converge with the same rate as Local SGD algorithm.\nFirst of all, I didn't get the problem we try to solve. \nUnfortunately, the algorithm itself is not mentioned in the paper only a single line that corresponds to the update rule. From this rule I conclude that all nodes are interconnected since the second term is dependent on the all neighbors' gradients and points. This questions me if this algorithm is good in practice. Yes, the local update happens much more often than the global update, but what is the reason then to use this step instead of simple averaging?\n\n", "summary_of_the_paper": "In this paper, authors propose the modification of distributed SGD algorithm that combines the ideas of Local SGD and Delayed averaging of updates. ", "summary_of_the_review": "I think that this article is poorly written. \n\nFirst of all, I want to mention that Authors decided to decrease the font size of all important equations and plots to fit the conference size requirements. This makes this article extremely hard to read after printing.\n\nSecond, for me as a colorblind person all the plots are extremely unclear, since the difference between the lines is minimal.\nThird, I missed the main problem formulation. Moreover, the algorithm itself is not mentioned (only update without any details about hyperparameters selection).\n\nSecond thing to mention is a novelty and a practical interest of the algorithm. I understand what is a difference between this algorithm and the local SGD, but I am hesitating in the following. Since during the full update (not local) we communicate completely (M^2) exchanges what is a reason in such a delayed gradient computation. Usually the communication is much more expensive than the gradient computation so the reason on delaying the gradients is not clear for me.  In work (https://arxiv.org/pdf/1806.09429.pdf) authors use delayed gradients almost the same way as in this paper; however it allows to save the total amount of communications. \n\nAbout the experimental part I have no comments since I failed to recognize the lines difference.\n\nAll in all, I find this article in a very draft stage to be published.\n\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "RzPuPGvlgQ3", "reviewer": "Reviewer_1qEJ", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\nThis paper considers a very interesting and relevant problem: reducing communication overhead of distributed deep learning methods. Additionally, the approach of using delayed averaging to hide communication overhead is well motivated.\n\nWeaknesses:\n1) Misses a large body of literature on the problem, including:\n- the whole set of gossip-based methods that have been proposed for this problem\n- the whole set of decentralized asynchronous methods that have been proposed for this problem\n- co-distillation based methods hiding communication overhead by synchronizing predictions via knowledge-distillation\n2) Additionally, the novelty is highly limited. For example, local steps with delayed averaging has already been used in asynchronous decentralized methods. For instance, see \\tau-Overlap Stochastic Gradient Push [a] which combines \\tau local steps with asynchronous delayed averaging over arbitrary directed communication graphs (not necessarily all-to-all).\n3) The proposed method still requires synchronizing workers during forward/backward passes, which does not tolerating variance in inter-processor update times, which even in the case of homogeneous clusters still presents non-trivial slow-downs in the context of machine-learning problems.\n4) Numerical results on ImageNet are not convincing since the benchmarks are non-standard for this literature. Specifically, only using a RN18 in IN1k for 20 epochs with a batch-size of 256, does not provide a good indication on the practical utility of the proposed method relative to related work. Not to mention that a numerical comparison is missed with a large body of related work.\n5) Minor point, but the heuristic approximation used to determine the lower bound on the delay hyper-parameter, d, does not necessarily scale linearly with the number of workers. For instance, all-reduce collective communication implementations using distance-halving-vector-doubling or ring-based all-reduce only scales logarithmically with the number of workers, not linearly.\n\n[a] Assran et al., Stochastic Gradient Push for Distributed Deep Learning, ICML, 2019.\n\n[b] Vogels et al., RelaySum for Decentralized Deep Learning on Heterogeneous Data, NeurIPS, 2021.\n\n[c] Koloskova et al., Decentralized Deep Learning with Arbitrary Communication Compression, ICLR 2020.\n\n[d] Lian et al., Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent, NeurIPS, 2017.\n\n[e] Lian et al., Asynchronous decentralized parallel stochastic gradient descent, ICML 2018.\n\n[f] Tang et al., Decentralized Training over Decentralized Data, ICML 2018.\n\n[g] Assran et al., Advances in asynchronous parallel and distributed optimization, Proceedings of the IEEE, 2020.\n\n[h] Assran and Rabbat, Asynchronous Gradient Push, IEEE Transactions on Automatic Control, 2021.\n\n[i] Assran et al., Gossip-based Actor-Learner Architectures for Deep Reinforcement Learning, NeurIPS, 2020.\n\n[j] Spiridinoff et al., Robust asynchronous stochastic gradient-push: Asymptotically optimal and network-independent performance for strongly convex functions, JMLR,2020.\n\n[k] Pu et al., Asymptotic network independence in distributed stochastic optimization for machine learning: Examining distributed and centralized stochastic gradient descent, IEEE Signal Processing Magazine, 2020.\n\n[l] Sodhani et al., A Closer Look at Codistillation for Distributed Training, arXiv, 2020.\n\n[m] Anil et al., Large scale distributed neural network training through online distillation, ICLR 2018.\n\n- The \"for sufficiently large K\" is standard but is quite vague. The lower bound on K is quantified in related works.", "summary_of_the_paper": "This paper proposed DaSGD, an algorithm for large-scale large-batch training of deep neural networks. The algorithm combines Local SGD with delayed averaging steps to hide the communication overhead. However, workers still synchronize their forward/backward passes in each iteration. A convergence rate of O(1/sqrt(K)) to a stationary is provided for smooth non-convex objectives, with respect to the average parameter set across workers. Numerical experiments provided on CIFAR10 and some brief results on ImageNet-1k with a ResNet18 and a batch-size of 256.", "summary_of_the_review": "It is my opinion that although the problem is quite interesting and relevant, a large body of literature is missed, and the proposed method is not sufficiently novel. Moreover, the theoretical contributions do not provide improvements over the related literature, and could use further specification in certain parts (e.g., although \"for sufficiently large K\" is a common qualifier, a reasonable lower bound is usually made specific in the the theorem statement). Additionally, I do not find the numerical experiments to provide convincing evidence that the proposed method is indeed better suited for large-batch distributed deep learning than existing approaches.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "M-yTqXFxoPc", "reviewer": "Reviewer_MLkr", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "In this paper, the authors present DaSGD, which overlaps the computation and communication of distributed training. The paper is well-written and easy to understand.\nIn a nutshell, the idea is to combine PipeSGD and local SGD, which totally makes sense. The experiment results show good performance.\nHowever, I have the following concerns in the novelty:\n1. The idea of \"fully parallelize SGD and forward/backward propagations to hide 100\\% of gradient communication\" is actually not new. PipeSGD [1] proposed using SGD with 1 step of staleness to overlap communication and computation. However, [1] is not cited or discussed in this paper.\n2. The combination of PipeSGD and local SGD is also not new. [2,3] both uses such a combination. Basically, I think [3] proposes the combination of PipeSGD and local SGD, and [2] adds communication compression to [3]. Please correct me if I'm wrong, and indicate the major difference between the ideas of this paper and [3].\n\n\nReferences:\n\n[1] Li, Youjie et al. “Pipe-SGD: A Decentralized Pipelined SGD Framework for Distributed Deep Net Training.” NeurIPS 2018.\n\n[2] Delay-Tolerant Local SGD for Efficient Distributed Training. https://openreview.net/forum?id=E_U8Zvx7zrf\n\n[3] Wang, Jianyu et al. “Overlap Local-SGD: An Algorithmic Approach to Hide Communication Delays in Distributed SGD.” ICASSP 2020.\n", "summary_of_the_paper": "In this paper, the authors present DaSGD, which overlaps the computation and communication of distributed training. \nIn a nutshell, the idea is to combine PipeSGD and local SGD, which totally makes sense. The experiment results show good performance.", "summary_of_the_review": "In this paper, the authors present DaSGD, which overlaps the computation and communication of distributed training. The paper is well-written and easy to understand. However, I have some concerns in the novelty.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "D72mYagpLlk", "reviewer": "Reviewer_SC8P", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "1. The critical issue is that neither local sgd nor overlapped [1] communication is novel. What's more, combining them is also not novel. As a matter of fact, the proposed method Figure 2 (c) is nearly the same to Fig 2 in [2].\n\n2. I did not find the improvement regarding the wall clock time by hiding the communication in the experiment.\n\nReferences\n\n[1] Li, Y., Yu, M., Li, S., Avestimehr, S., Kim, N.S. and Schwing, A., Pipe-SGD: A Decentralized Pipelined SGD Framework for Distributed Deep Net Training. NeurIPS 2018.\n\n[2] Wang, Jianyu, Hao Liang, and Gauri Joshi. \"Overlap local-SGD: An algorithmic approach to hide communication delays in distributed SGD.\" In ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 8871-8875. IEEE, 2020.", "summary_of_the_paper": "The paper proposes to combine local sgd with overlapped communication. A convergence analysis is given. The experiments validates the model performance.", "summary_of_the_review": "I believe the proposed method is not novel and [2] has proposed a very similar method.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a variant of stochastic gradient descent that parallelizes the algorithm for distributed training via delayed gradient averaging. While the algorithm (DaSGD) proposed is sensible and seems to work, it also seems to miss a lot of related work. As pointed out by one of the reviewers, the class of asynchronous decentralized methods already seem to cover the space of DaSGD, and it's not clear how DaSGD differs from the existing methods in this space. As a result of this lack of comparison to related work, the reviewers recommended that the paper not be accepted at this time, and this evaluation was not challenged by an author response. I agree with this consensus.
Decision: Reject