SQUEEZING SGD PARALLELIZATION PERFORMANCE IN DISTRIBUTED TRAINING USING DELAYED AVER-
Year: 2021

Abstract:
The state-of-the-art deep learning algorithms rely on distributed training systems to tackle the increasing sizes of models and training data sets. Minibatch stochastic gradient descent (SGD) algorithm requires workers to halt forward/back propagations, to 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 a large number of workers 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 on the low-latency and high-throughput inter-connects. The theoretical analysis and the experimental results show its convergence rate O(1/ √ K), the same as SGD. The performance evaluation demonstrates it enables a linear performance scale-up with the cluster size.

text: √ K), the same as SGD. The performance evaluation demonstrates it en-
ables a linear performance scale-up with the cluster size.

heading: 1 INTRODUCTION
text: Training deep learning models using data parallelism on a large-scale distributed cluster has become an effective method for deep learning model training. The enormous training data set allows a 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 a couple of minutes (Goyal et al., 2017; You et al., 2017b; Akiba et al., 2017; You et al., 2017a; Ying et al., 2018; Goodfellow et al., 2016). During Mini-batch stochastic gradient descent (SGD), these workers have to 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 to 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 a 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 (NVS, 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-batch SGD on a large-scale distributed system (Gau, 2019).
Communication efficient SGD algorithms (Lin et al., 2017; Wangni et al., 2018; Alistarh et al., 2018; Dean et al., 2012; Recht et al., 2011; Zhang et al., 2015; Wang & Joshi, 2018; Wang & Joshi, 2018; Lin et al., 2018) are proposed to reduce the communication requirements. A successfully 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 on 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 et al., 2018). Under these workloads, hardware resources are 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
are completely idle. During SGD, the computing resources are mostly idle while the system interconnects 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.
Inspired by the modern system design practices, we propose DaSGD, a new SGD method, enabling SGD running parallelly with forward/back propagation and balanced utilization of the hardware resources. It replaces a Mini-batch SGD with Local SGD iterations. In a Local SGD (Lin et al., 2018; Wang & Joshi, 2018), each worker evolves a local model by performing sequential SGD updates, before 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, it schedules delayed model averaging for a defined number 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/ √ K), where K is the iteration step, same as Mini-batch SGD.
The main contributions of this paper are the following.
• We present DaSGD as an algorithm-system co-design method for a large-scale distributed training system. It enables designing a more balanced and better-utilized system, more than a 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 O(1/ √ K), the same as Mini-batch SGD.
• Our experiments focus on 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-toconvergence. The experiments also explore the proper ranges of these parameters.
• A performance evaluation of real-life systems measures many performance issues in a system, 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 a linear performance scale-up with the cluster size.

heading: 2 BACKGROUND

heading: 2.1 STOCHASTIC GRADIENT DESCENT
text: Stochastic Gradient Descent (SGD) is the backbone of numerous deep learning algorithms (Ghadimi & Lan, 2013). Supervised deep learning demands massive training datasets. Training a deep learning model needs many epochs for training to converge. A variant of classic SGD, synchronous minibatch SGD (Bottou, 2010), has become the mainstream due to a faster convergence rate., supported by prevalent machine learning frameworks, such as Tensorflow (Abadi et al., 2016), Pytorch (Paszke et al., 2019), MxNet (Chen et al., 2015).
Mini-batch SGD as a weight update process is shown in Eq. 1.
xk+1 = xk − η
B B∑ j=1 ∇F (xk, s (j) k ) (1)
where x ∈ Rd is the weight of a model, η is the learning rate, B is the batch size, S is the training dataset, s(j)k ⊂ S is a random sample,∇F (xk, s (j) k ) is the stochastic gradient given the sample s (j) k .
From a system perspective, a distributed training system may compute a batch of gradients on several workers. At the end of a batch, a reduction operation is performed on the gradients on a worker first and a worker sends out only a copy of local averaged gradients. Further reductions are performed on gradients from different workers until a final copy of the averaging gradients is obtained. The above
equation may be rewritten as
xk+1 = xk − η
M B∑ j=1 g(xk, s (j) k ) (2)
where M is the number of workers, g(xk, s (j) k ) is the stochastic gradient that worker j aggregates locally for that batch.
g(xk, s (j) k
) = M
B B M∑ i=1 ∇(xk, s (i) k ) (3)

heading: 2.2 COMMUNICATION EFFICIENT SGD ALGORITHMS

heading: 2.2.1 ASYNCHRONOUS SGD
text: There are a few asynchronous training methods, such as Downpour SGD (Dean et al., 2012), Hogwild (Recht et al., 2011), Elastic Averaging SGD (Zhang et al., 2015). In these models, every worker has its own copy of weights. A worker performs forward propagation and back propagation on its partition of samples, and then sends the calculated gradients asynchronously to a pool of parameter 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 a performance bottleneck. For non-convex problems, ASGD requires that the staleness of gradients is bounded (Lian et al., 2015) to match the convergence rate O(1/ √ K) of synchronous SGD, where K denotes the total Iteration steps.

heading: 2.2.2 LOCAL SGD
text: 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, 2018; Lin et al., 2018). A worker performs SGD on its local copy of weights for τ times, where τ denotes the local iteration steps. After τ local updates, local copies are synchronously averaged across all workers globally. Several works suggested that Local SGD incurs the same convergence rate O(1/ √ K) as SGD. The total number of steps to train a 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 an increase of batch size. With Local SGD, SGD and forward/back propagations are still blocking while system resources are unbalanced.

heading: 3 DASGD
text: In this paper, we propose a new algorithm, called Local SGD with Delayed Averaging, DaSGD for short. It aggregates gradients and updates weights in a 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 in Section 2). 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 a 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 a deterministic way, DaSGD serializes forward propagations and back propagations for different 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
and synchronization overhead are hidden or overlapped by local computations at the cost of a delayed 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. 1 illustrates the proposed algorithm by showing a wall-clock time diagram of 6 training iterations. There are 2 workers, dividing a batch into 2 local batches. Each worker computes 6 local batches. Each local batch contains Bl samples. Each worker maintains a local copy of model. According to Local SGD, for a local batch, each worker operates Bl forward/backward 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 to average the model weights. In Fig. 1, 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 a key feature by imposing delay update on Local SGD. As shown in Fig. 1, a worker, at local step 3, broadcasts 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/backward propagations of the next local batch.
In DaSGD, we use τ to denote the number of local batches between two consecutive global synchronizations. Therefore, τ 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, as it is not only used to reduce inter-worker 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 execution time. Finally, we discussed the updated rules and the convergence rate in detail.

heading: 3.1 UPDATE FLOW OF DIFFERENT SGD
text: Fig. 2 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 2 workers are distinguished by yellow and green arrows. In the Mini-batch SGD (as shown in Fig. 2(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. 2(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 a global aggregation. A novel change made by the proposed algorithm is to delay weight update from global to local after the global averaging. A worker may delay the update for d steps (i.e., samples) of local weight updates (d = 1 in
this example, as shown in Fig. 2(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.e., forward propagation, 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.

heading: 3.2 CONVERGENCE ANALYSIS
text: In this section, we provide a theoretical analysis of the DaSGD algorithm. We will prove the convergence rate for DaSGD on non-convex problems and show that it converges at the same rate O(1/ √ K) as Mini-batch SGD and Local SGD. To facilitate the convergence analysis, we firstly introduce the assumptions.

heading: 3.2.1 ASSUMPTIONS
text: The convergence analysis is under the assumptions as the following, which are similar to the Local SGD (Wang & Joshi, 2018):
• Lipschitzian gradient: || 5 F (x)−5F (y)|| ≤ L||x− y|| • Unbiased gradients: ESk|x [g(x)] = 5F (x) • Lower bounder: F (x) ≥ Finf • Bounded variance: ESk|x||g(x)−5F (x)||2 ≤ σ2 • Independence: All random variables are independent to each other • Bounded age: The delay is bounded, d < τ
where S is the training dataset, Sk is set { s (1) k , ..., s (M) k } of randomly sampled local batches, L is the Lipschitz constant.
3.2.2 UPDATE RULE
x (m) k+1 =  ξx (m) k − ηξg ( x (m) k ) + (1−ξ) M∑ j=1 [ x (j) k−d−ηg ( x (j) k−d )] M , (k + 1) mod τ = d
x (m) k − ηg ( x (m) k ) , otherwise
(4)
where x(m)k is the weights of worker m at k-th iteration, η the learning rate, M the number of workers, and g(x(m)k ) the stochastic gradient of workerm. For every k that satisfies (k+1) mod τ = d, a 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, we can define the average weight and the average gradient
µk = 1
M M∑ i=1 x (i) k , ḡk = 1 M M∑ i=1 g ( x (i) k ) .
Reformatting it, the update rule for the average weight is
µτ(k+1)+d = µτk+d − η
[ ξ
τ−1∑ i=τ−d ḡτk+d+i + τ−1−d∑ i=0 ḡτk+d+i ] It is observed that the averaged weight µτ(k+1)+d is performing a perturbed stochastic gradient descent. Thus, we will focus on the convergence of the averaged weight µτ(k+1)+d, which is a common approach in the literature of distributed optimization (Wang & Joshi, 2018; Wang & Joshi, 2018). SGD can converge to a 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.

heading: 3.2.3 CONVERGENCE RATE
text: The -suboptimal solution of the algorithm is Ek [ 1 K K∑ k=1 ‖5F (µk)‖2 ] ≤ . The learning rate is usually set as a constant and is decayed only when the training process is saturated. Therefore, we analyze the case of a fixed learning rate and study the lower limit of error at convergence.
Theorem (Convergence of DaSGD). Under assumptions, if the learning rate satisfies 2Lηdξ2 − ξ + 6ξL
2η2d+6L2η2(τ−d) 1−ξ2 + 6ξL 2η2d ≤ 0 and 2Lη(τ − d)− ξ + 6ξL 2η2d+6L2η2(τ−d) 1−ξ2 + 6ξL 2η2d+
6L2η2(τ−d) ≤ 0 at the same time, the average-squared gradient norm afterK iterations is bounded as follows
E  1 K K∑ k=1 ‖5F (µk)‖ 2  ≤ 2 [F (µ1)− Finf ] ηK(ξd + τ − d) + η M 2Lσ2 [ ξ2d + τ − d ] (ξd + τ − d) + η 2 6L 2(1 + ξ) ξd + τ − d τ−1∑ l=τ−d l∑ i=0 σ 2 + η 2 6dξ 2L2τσ2(1 + ξ) (ξd + τ − d)(1− ξ2)
+ η2
K 12dσ2L2ξ2(τ − d)(1 + ξ) (ξd + τ − d)(1− ξ2) + η2 KM 12L2dξ2(τ − d)(1 + ξ) (ξd + τ − d)(1− ξ2) d−1∑ i=1 ‖5F (Xi)‖ 2 F
where Xk = [ x1k, ..., x m k ] , ‖ ‖2F is the Frobenius norm.All proofs are provided in the Appendix.
Corollary. Under assumptions, if the learning rate is η = M+VM √ M K the average-squared gradient norm after K iterations is bounded by
E  1 K K∑ k=1 ‖5F (µk)‖ 2  ≤ 2 [ F (µ1)− Finf ] + 2Lσ2 [ ξ2d + τ − d ] √ MK(ξd + τ − d) + M2 K3 ( 1 + V M )4 6L2(1 + ξ) ξd + τ − d τ−1∑ l=τ−d l∑ i=0 σ 2
+ M2
K3
( 1 + V
M )4 6dξ2L2τσ2(1 + ξ) (ξd + τ − d)(1− ξ2) + M2 K3 ( 1 + V M )4 12dσ2L2ξ2(τ − d)(1 + ξ) (ξd + τ − d)(1− ξ2)
+ M
K3
( 1 + V
M )4 12L2dξ2(τ − d)(1 + ξ) (ξd + τ − d)(1− ξ2) d−1∑ i=1 ‖5F (Xi)‖ 2 F
If the total iterationsK is sufficiently large, then the average-squared gradient norm will be bounded by
E  1 K K∑ k=1 ‖5F (µk)‖ 2  ≤ 2 [ F (µ1)− Finf ] + 2Lσ2 [ ξ2d + τ − d ] √ MK(ξd + τ − d)
Therefore, on non-convex objectives, for the total iterations K large enough, DaSGD converges at rate O(1/ √ K) consistented with the Mini-batch SGD and the Local SGD. Besides, it is worth noting that these three introduced auxiliary parameters (τ , d and ξ) are mostly in the high-order term O(1/K2) and O(1/K3), which has little influence on the convergence of DaSGD.

heading: 3.3 GUIDELINES FOR USING DASGD
text: DaSGD is identical to Local SGD except that the global model is updated for delayed d 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 tc across workers is required to be shorter than the time of d local iterations, that is, tc < d× tp, where tp is the computation time of one iteration. For deep learning systems, the weight transfer time tc across multiple workers is approximately calculated as tc = m × np/BW, where np denotes the number of parameters of the model, m the number of workers, and BW the bandwidth of the device. The computation time tp of one local batch is approximately calculated as tp = Bl×FLOP/FLOPS, where FLOP denotes the floating-point operation counts of local computation, Bl the local batch size, FLOPS denotes the computation speed of the device in terms of floating-point operations per second (FLOPS).
In a nutshell, the delay is given by d > tctp = m×np×FLOPS Bl×BW×FLOP . Note that the delay is highly related to the structure of neural network models, e.g., the number of parameters and FLOP, 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 a result, in most cases, when the delay is one single iteration, i.e. d = 1, the weight transfer can be processed completely in parallel with local updates. In addition, as 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.

heading: 4 EXPERIMENTAL RESULTS
text: 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.

heading: 4.1 EXPERIMENTAL SETUP
text: 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 to 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 a flat minimum, while a smaller learning rate prevents training from diverging and converging to a 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 in the right direction, is 0.9.

heading: 4.2 CONVERGENCE RATE AND ACCURACY COMPARISON
text: We compare DaSGD with Mini-batch SGD and Local SGD in terms of convergence rate and accuracy upon a set of neural network models that are trained for 50 epochs for CIFAR-10 dataset. All models are 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 Bl is 32, which equals to the mini-batch size of Mini-batch SGD 1. For Local SGD and DaSGD, the number of local steps τ is 4. For DaSGD, the delayed update steps d is 1.
TABLE 1 first demonstrates that high validation accuracy up 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-parameters need to be tuned carefully. Large batch size training
1The mini-batch size is a concept in Mini-batch SGD; the local batch size is a concept of Local SGD. They equal to each other and are computed as the batch size divided by the number of workers.
leads to great accuracy loss. The hyper-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/m), which is B in Mini-batch SGD. Thus, without any hyper-parameter 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. 3 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 is 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.

heading: 4.3 PARAMETER EFFECTS OF DASGD
text: 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 Bl, 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, Bl = 32, and ξ = 0.25.
Worker numberm. Fig. 4(a) 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 2 to 256, the convergence rate becomes lower and validation accuracy degrades. Since the local batch size remains unchanged as 32, when the worker number is 256, the total batch size has reached 8192 (32 × 256), which results in a decrease of validation accuracy of around 2% and an increase of training loss of 0.31. Since the number of local steps is 4, DaSGD communicates once for a total number of samples of 32K (32× 256× 4). The CIFAR-10 dataset has only 50000 training samples, so the number of communications is just 2 for this large number of workers.
Local batch size Bl. Fig. 4(b) illustrates that DaSGD exhibits a good convergence rate with moderate local batch sizes. When the local batch size is large as 256 or small as 8, the validation accuracy 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-batch 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. 4(b), 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×Bl. 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 hyper-parameters of large-batch training discussed above. To obtain a good convergence rate for such a large batch size needs careful coordination between multiple impactful hyper-parameters.
Number of local steps τ . Fig. 4(c) 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 τ is large enough to ensure parallel weight communication is totally overlapped by local computation.
Local update percentage. Fig. 4(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. 4(e) 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 0 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.

heading: 4.4 IMAGENET
text: We use Fast.Ai framework for training on 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 is set as 0.01, and the momentum of SGD is 0.9.
As shown in Fig. 5(a), three algorithms, which are Mini-batch SGD, Local SGD, and DaSGD, are trained in 20 epochs to compare the convergence rate and top-1/top-5 validation accuracy in ResNet18. 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 is 1. The top-1/top-5 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 it 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, it is much faster. We also evaluate the effect of worker number in terms of the training/validation loss and top-1/top-5 validation accuracy for the ResNet-18 model based on DaSGD in Fig. 5(b). 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. 5(c) 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.

heading: 5 CONCLUSION
text: In this work, we propose a new SGD algorithm called DaSGD, which parallelizes SGD and forward/back propagation to hide communication time. Just adjusting the update schedule at the software 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 is O ( 1/ √ K )
, which is the same as the mini-batch SGD.

heading: A APPENDIX
text: CONVERGENCE ANALYSIS OF DASGD
A.1 ASSUMPTIONS We define some notations. S is the training dataset, Sk is set { s (1) k , ..., s (M) k } of randomly sampled local batches at M workers in k iteration, L is the Lipschitz constant, d is the number of local iteration that global weight updates are delayed, τ is the number of local steps, x is the weight of devices. The convergence analysis is conducted under the following assumptions:
• Lipschitzian gradient: || 5 F (x)−5F (y)|| ≤ L||x− y|| • Unbiased gradients: ESk|x [g(x)] = 5F (x) • Lower bounder: F (x) ≥ Finf • Bounded variance: ESk|x||g(x)−5F (x)||2 ≤ σ2
• Independence: All random variables are independent to each other • Bounded age: The delay is bounded, d ≤ τ
A.2 UPDATE RULE
The update rule of DaSGD is given by
x (m) k+1 =  x (m) k − ηg ( x (m) k ) , otherwise ξx (m) k − ηξg ( x (m) k ) + 1−ξM M∑ j=1 [ x (j) k−d − ηg ( x (j) k−d )] , (k + 1− d) mod τ = 0
where x(m)k is the weights at m worker in k iteration, η is the learning rate, M is the number of workers, g(x(m)k ) is the stochastic gradient of worker m, ξ is the local update proportion, delayed update is the case (k + 1− d) mod τ = 0. Matrix Representation. Define matrices Xk, Gk ∈ Rd×M that concatenate all local models and gradients in k iteration:
Xk = [ x1k, ..., x m k ] , Gk = [ g ( x (1) k ) , ..., g ( x (m) k )] Then, the update rule is
Xk+1 = { ξ (Xk − ηGk) + (1− ξ) (Xk−d − ηGk−d)J , (k + 1− d) mod τ = 0 Xk − ηGk, otherwise (5)
Update Rule for the Averaged Model. The update rule of DaSGD is given by
x (m) k+1 =  x (m) k − ηg ( x (m) k ) , otherwise ξx (m) k − ηξg ( x (m) k ) + 1−ξM M∑ j=1 [ x (j) k−d − ηg ( x (j) k−d )] , (k + 1− d) mod τ = 0
Here, we set
x̄k = 1
M M∑ i=1 x (i) k , ḡk = 1 M M∑ i=1 g ( x (i) k )
The average weight on different workers is obtained by
x̄k+1 = { x̄k − ηḡk, otherwise ξx̄k + (1− ξ)x̄k−d − ηξḡk − η(1− ξ)ḡ(xk−d), (k + 1− d) mod τ = 0
When z = τ(k + 1) for z mod τ = 0, we have x̄τ(k+1)+d = ξx̄τ(k+1)+d−1 + (1− ξ)x̄τ(k+1)−1 − ξηḡτ(k+1)+d−1 − (1− ξ)ηḡτ(k+1)−1
= ξx̄τk+d + (1− ξ)x̄τk+d − ξη τ−1∑ i=0 ḡτk+d+i − (1− ξ)η τ−1−d∑ i=0 ḡτk+d+i
= x̄τk+d − η [ ξ ( τ−1∑ i=0 ḡτk+d+i − τ−1−d∑ i=0 ḡτk+d+i ) + τ−1−d∑ i=0 ḡτk+d+i ]
= x̄τk+d − η [ ξ
τ−1∑ i=τ−d ḡτk+d+i + τ−1−d∑ i=0 ḡτk+d+i
]
If we set K(k) = τk + d
x̄K(k+1) = x̄K(k) − η
[ ξ
τ−1∑ i=τ−d ḡK(k)+i + τ−1−d∑ i=0 ḡK(k)+i
]
For the ease of writing, we first define some notations. Let Sk denote the set { s (1) k , ..., s (m) k } of mini-batches at m workers in iteration k. Besides, define averaged stochastic gradient and averaged full batch gradient as follows:
GK(k) = 1
M M∑ m=1 [ τ−1∑ i=τ−d ξg ( x (m) τk+d+i ) + τ−1−d∑ i=0 g ( x (m) τk+d+i )] (6)
HK(k) = 1
M M∑ m=1 [ τ−1∑ i=τ−d ξ 5 F ( x (m) τk+d+i ) + τ−1−d∑ i=0 5F ( x (m) τk+d+i )] (7)
µK(k) = 1
M M∑ i=1 x (i) τk+d (8)
Then we have µK(k+1) = µK(k) − ηGK(k)
A.3 CONVERGENCE RATE
Theorem (Convergence of DaSGD). When the learning rate satisfies the following two formulas at the same time
2Lηdξ2 − ξ + 6ξL 2η2d+ 6L2η2(τ − d)
1− ξ2 + 6ξL2η2d ≤ 0
2Lη(τ − d)− ξ + 6ξL 2η2d+ 6L2η2(τ − d)
1− ξ2 + 6ξL2η2d+ 6L2η2(τ − d) ≤ 0
Then the average-squared gradient norm after K iterations is bounded as
EK(k)
[ 1
K K∑ k=1
∥∥5F (µK(k))∥∥2 ]
≤2 [F (µ1)− Finf ] ηK(ξd+ τ − d) + η2Lσ2
[ ξ2d+ τ − d ] M(ξd+ τ − d) + η2 6L2(1 + ξ) ξd+ τ − d τ−1∑ l=τ−d l∑ i=0 σ2 + η2 6dξ2L2τσ2(1 + ξ) (ξd+ τ − d)(1− ξ2)
+ η2
K 12dσ2L2ξ2(τ − d)(1 + ξ) (ξd+ τ − d)(1− ξ2) + η2 KM 12L2dξ2(τ − d)(1 + ξ) (ξd+ τ − d)(1− ξ2) d−1∑ i=1 ‖5F (Xi)‖2F
where µk = 1M ∑M i=1 x (i) τk+d, ‖ ‖ 2 F is the Frobenius norm.
Corollary. Under sumptions, if the learning rate is η = M+VM √ M K the average-squared gradient norm after K iterations is bounded by
EK(k)
[ 1
K K∑ k=1
∥∥5F (µK(k))∥∥2 ]
≤ 2 [F (µ1)− Finf ]√ MK(ξd+ τ − d) + 1√ MK
2Lσ2 [ ξ2d+ τ − d ] (ξd+ τ − d)
+ M2
K3
( 1 + V
M
)4 6L2(1 + ξ)
ξd+ τ − d τ−1∑ l=τ−d l∑ i=0 σ2 + M2 K3 ( 1 + V M )4 6dξ2L2τσ2(1 + ξ) (ξd+ τ − d)(1− ξ2)
+ M2
K3
( 1 + V
M
)4 12dσ2L2ξ2(τ − d)(1 + ξ)
(ξd+ τ − d)(1− ξ2) + M K3
( 1 + V
M )4 12L2dξ2(τ − d)(1 + ξ) (ξd+ τ − d)(1− ξ2) d−1∑ i=1 ‖5F (Xi)‖2F
If the total iterationsK is sufficiently large, then the average-squared gradient norm will be bounded by
E
[ 1
K K∑ k=1
‖5F (µk)‖2 ] ≤ 2 [F (µ1)− Finf ] + 2Lσ2 [ ξ2d+ τ − d ] √ MK(ξd+ τ − d)
.
A.4 PROOF OF CONVERGENCE RATE Lemma 1. If the learning rate satisfies η ≤ min {
1 2Ldξ , ξ 2L(τ−d)
} and all local model parameters
are initialized at the same point, then the average-squared gradient after K iterations is bounded as follows
EK(k)
[ 1
K K∑ k=1
∥∥5F (µK(k))∥∥2 ]
≤2 [F (µ1)− Finf ] ηK(ξd+ τ − d) + 2Lησ2
[ ξ2d+ τ − d ] M(ξd+ τ − d)
+ L2
KM(ξd+ τ − d) K∑ k=1 M∑ m=1 [ τ−1−d∑ i=0 EK(k) ∥∥∥µK(k) − x(m)τk+d+i∥∥∥2 + ξ τ−1∑ i=τ−d EK(k) ∥∥∥µK(k) − x(m)τk+d+i∥∥∥2 ]
Proof.
From the Lipschitzisan gradient assumption || 5 F (x)−5F (y)|| ≤ L||x− y||, we have
F (XK(k+1))− F (XK(k)) ≤ 〈 5F (XK(k)), XK(k+1) −XK(k) 〉 + L
2 ∥∥XK(k+1) −XK(k)∥∥2 =− η 〈 5F (XK(k)),GK(k) 〉 + Lη2
2 ∥∥GK(k)∥∥2 (9) Taking expectation respect to SK(k) on both sides of equation 9, we have EK(k) [ F (XK(k+1)) ] − F (XK(k)) ≤− ηEK(k) [〈 5F (XK(k)),GK(k) 〉] + Lη2
2 EK(k) [∥∥GK(k)∥∥2] From the fact
〈a, b〉 = 1 2
( ||a||2 + ||b||2 − ||a− b||2 )
we have EK(k) [ F (XK(k+1)) ] − F (XK(k)) ≤− ηEK(k) [〈 5F (XK(k)),GK(k) 〉] + Lη2
2 EK(k) [∥∥GK(k)∥∥2] Combining with Lemmas 4 and 5, we obtain
EK(k) [ F (XK(k+1)) ] − F (XK(k))
≤− ηEK(k) [〈 5F (XK(k)),GK(k) 〉] + Lη2
2 EK(k) [∥∥GK(k)∥∥2] ≤− η ξd+ τ − d
2
∥∥5F (XK(k))∥∥2 + Lη2σ2 M [ dξ2 + τ − d ] + [ Lη2dξ2
M − ηξ 2M ] τ−1∑ i=τ−d ‖5F (Xτk+d+i)‖2F + [ Lη2(τ − d) M − ηξ 2M ] τ−1−d∑ i=0 ‖5F (Xτk+d+i)‖2F
+ η
2M M∑ m=1 [ τ−1−d∑ i=0 ∥∥∥5F (XK(k))−5F (x(m)τk+d+i)∥∥∥2 + ξ τ−1∑ i=τ−d ∥∥∥5F (XK(k))−5F (x(m)τk+d+i)∥∥∥2 ]
≤− η ξd+ τ − d 2 ∥∥5F (µK(k))∥∥2 + Lη2σ2 M [ dξ2 + τ − d ] + [ Lη2dξ2
M − ηξ 2M ] τ−1∑ i=τ−d ‖5F (Xτk+d+i)‖2F + [ Lη2(τ − d) M − ηξ 2M ] τ−1−d∑ i=0 ‖5F (Xτk+d+i)‖2F
+ ηL2
2M M∑ m=1 [ τ−1−d∑ i=0 ∥∥∥µK(k) − x(m)τk+d+i∥∥∥2 + ξ τ−1∑ i=τ−d ∥∥∥µK(k) − x(m)τk+d+i∥∥∥2 ]
(10)
where equation 10 is due to the Lipschitzisan gradient assumption ||5F (x)−5F (y)|| ≤ L||x−y||. After minor rearranging and according to the definition of Frobenius norm, it is easy to show
η ξd+ τ − d
2 ∥∥5F (µK(k))∥∥2 ≤F (µK(k))− EK(k) [ F (µK(k+1)) ] + Lη2σ2
M
[ dξ2 + τ − d ] + [ Lη2dξ2
M − ηξ 2M ] τ−1∑ i=τ−d ‖5F (Xτk+d+i)‖2F + [ Lη2(τ − d) M − ηξ 2M ] τ−1−d∑ i=0 ‖5F (Xτk+d+i)‖2F
+ ηL2
2M M∑ m=1 [ τ−1−d∑ i=0 ∥∥∥µK(k) − x(m)τk+d+i∥∥∥2 + ξ τ−1∑ i=τ−d ∥∥∥µK(k) − x(m)τk+d+i∥∥∥2 ]
Taking the total expectation and averaging over all iterates, we have
η ξd+ τ − d
2 EK(k)
[ 1
K K∑ k=1
∥∥5F (µK(k))∥∥2 ]
≤F (µ1)− Finf K + Lη2σ2 M
[ dξ2 + τ − d ] + [ Lη2dξ2
KM − ηξ 2KM ] K∑ k=1 τ−1∑ i=τ−d ‖5F (Xτk+d+i)‖2F + [ Lη2(τ − d) KM − ηξ 2KM ] K∑ k=1 τ−1−d∑ i=0 ‖5F (Xτk+d+i)‖2F
+ ηL2
2KM K∑ k=1 M∑ m=1 [ τ−1−d∑ i=0 ∥∥∥µK(k) − x(m)τk+d+i∥∥∥2 + ξ τ−1∑ i=τ−d ∥∥∥µK(k) − x(m)τk+d+i∥∥∥2 ]
Then, we have
EK(k)
[ 1
K K∑ k=1 ∥∥5F (µK(k))∥∥2 ] ≤2 [F (µ1)− Finf ] ηK(ξd+ τ − d) + 2Lησ2 [ ξ2d+ τ − d ] M(ξd+ τ − d)
+ 2Lηdξ2 − ξ
KM(ξd+ τ − d) K∑ k=1 τ−1∑ i=τ−d EK(k) ‖5F (Xτk+d+i)‖ 2 F
+ 2Lη(τ − d)− ξ KM(ξd+ τ − d) K∑ k=1 τ−1−d∑ i=0 EK(k) ‖5F (Xτk+d+i)‖ 2 F
+ L2
KM(ξd+ τ − d) K∑ k=1 τ−1−d∑ i=0 M∑ m=1 EK(k) ∥∥∥µK(k) − x(m)τk+d+i∥∥∥2
+ ξL2
KM(ξd+ τ − d) K∑ k=1 τ−1∑ i=τ−d M∑ m=1 EK(k) ∥∥∥µK(k) − x(m)τk+d+i∥∥∥2
(11) If the learning rate satisfies η ≤ min {
1 2Ldξ , ξ 2L(τ−d)
} , then
EK(k)
[ 1
K K∑ k=1 ∥∥5F (µK(k))∥∥2 ] ≤2 [F (µ1)− Finf ] ηK(ξd+ τ − d) + 2Lησ2 [ ξ2d+ τ − d ] M(ξd+ τ − d)
+ L2
KM(ξd+ τ − d) K∑ k=1 τ−1−d∑ i=0 M∑ m=1 EK(k) ∥∥∥µK(k) − x(m)τk+d+i∥∥∥2
+ ξL2
KM(ξd+ τ − d) K∑ k=1 τ−1∑ i=τ−d M∑ m=1 EK(k) ∥∥∥µK(k) − x(m)τk+d+i∥∥∥2
Recalling the definition µK(k) = 1M ∑M i=1 x (i) τk+d = XK(k)1M/M and adding a positive term to the RHS, one can get
τ−1∑ i=τ−d M∑ m=1 ∥∥∥µK(k) − x(m)τk+d+i∥∥∥2 = τ−1∑ i=τ−d ‖Xτk+dJ− Xτk+d+i‖2F
We have
EK(k)
[ 1
K K∑ k=1 ∥∥5F (µK(k))∥∥2 ] ≤2 [F (µ1)− Finf ] ηK(ξd+ τ − d) + 2Lησ2 [ ξ2d+ τ − d ] M(ξd+ τ − d)
+ L2
KM(ξd+ τ − d) K∑ k=1 τ−1−d∑ i=0 EK(k) ‖Xτk+dJ− Xτk+d+i‖ 2 F
+ ξL2
KM(ξd+ τ − d) K∑ k=1 τ−1∑ i=τ−d EK(k) ‖Xτk+dJ− Xτk+d+i‖ 2 F
Lemma 2.
∥∥HK(k)∥∥2 ≤ 2dξ2 M τ−1∑ i=τ−d ‖5F (Xτk+d+i)‖2F + 2(τ − d) M τ−1−d∑ i=0 ‖5F (Xτk+d+i)‖2F (12)
Proof. ∥∥HK(k)∥∥2 = ∥∥∥∥∥ξ 1M τ−1∑ i=τ−d M∑ m=1 5F ( x (m) τk+d+i ) + 1 M τ−1−d∑ i=0 M∑ m=1 5F ( x (m) τk+d+i )∥∥∥∥∥ 2
≤ 2dξ 2
M2 τ−1∑ i=τ−d ∥∥∥∥∥ M∑ m=1 5F ( x (m) τk+d+i )∥∥∥∥∥ 2 + 2(τ − d) M2 τ−1−d∑ i=0 ∥∥∥∥∥ M∑ m=1 5F ( x (m) τk+d+i )∥∥∥∥∥ 2
(13)
≤ 2dξ 2
M τ−1∑ i=τ−d M∑ m=1 ∥∥∥5F (x(m)τk+d+i)∥∥∥2 + 2(τ − d)M τ−1−d∑ i=0 M∑ m=1 ∥∥∥5F (x(m)τk+d+i)∥∥∥2 (14)
= 2dξ2
M τ−1∑ i=τ−d ‖5F (Xτk+d+i)‖2F + 2(τ − d) M τ−1−d∑ i=0 ‖5F (Xτk+d+i)‖2F
where equation 13 is due to ‖a+ b‖2 ≤ 2 ‖a‖2 + 2 ‖b‖2, equation 14 comes from the convexity of vector norm and Jensen’s inequality.
Lemma 3. Under assumptions ESk|x [g(x)] = 5F (x) and ESk|x||g(x)−5F (x)||2 ≤ σ2, we have the following variance bound for the averaged stochastic gradient:
EK(k) [∥∥GK(k) −HK(k)∥∥2] ≤ 2σ2
M
[ dξ2 + τ − d ] (15)
Proof. According to the definition of equation 6, equation 7, and equation 8, we have EK(k) [∥∥GK(k) −HK(k)∥∥2]
= 1
M2 EK(k) ∥∥∥∥∥ξ τ−1∑ i=τ−d M∑ m=1 [ g ( x (m) τk+d+i ) −5F ( x (m) τk+d+i )] + τ−1−d∑ i=0 M∑ m=1 [ g ( x (m) τk+d+i ) −5F ( x (m) τk+d+i )]∥∥∥∥∥ 2 
≤ 2 M2 EK(k) ∥∥∥∥∥ξ τ−1∑ i=τ−d M∑ m=1 [ g ( x (m) τk+d+i ) −5F ( x (m) τk+d+i )]∥∥∥∥∥ 2 + ∥∥∥∥∥ τ−1−d∑ i=0 M∑ m=1 [ g ( x (m) τk+d+i ) −5F ( x (m) τk+d+i )]∥∥∥∥∥ 2 
(16)
= 2
M2 EK(k)
[ ξ2
τ−1∑ i=τ−d M∑ m=1 ∥∥∥g (x(m)τk+d+i)−5F (x(m)τk+d+i)∥∥∥2 + τ−1−d∑ i=0 M∑ m=1 ∥∥∥g (x(m)τk+d+i)−5F (x(m)τk+d+i)∥∥∥2 (17)
+ ξ2 τ−1∑ j 6=i M∑ l 6=m 〈 g ( x (m) τk+d+i ) −5F ( x (m) τk+d+i ) , g ( x (l) τk+d+j ) −5F ( x (l) τk+d+j )〉 (18)
+ τ−1−d∑ j 6=i M∑ l 6=m 〈 g ( x (m) τk+d+i ) −5F ( x (m) τk+d+i ) , g ( x (l) τk+d+j ) −5F ( x (l) τk+d+j )〉 (19) = 2ξ2
M2 τ−1∑ i=τ−d M∑ m=1 EK(k) ∥∥∥g (x(m)τk+d+i)−5F (x(m)τk+d+i)∥∥∥2 + 2M2 τ−1−d∑ i=0 M∑ m=1 EK(k) ∥∥∥g (x(m)τk+d+i)−5F (x(m)τk+d+i)∥∥∥2
(20)
where equation 16 is due to ‖a+ b‖2 ≤ 2 ‖a‖2 + 2 ‖b‖2, equation 20 is due to sik are independent random variables and the assumption ESk|x [g(x)] = 5F (x). Now, directly applying assumption
ESk|x||g(x)−5F (x)||2 ≤ σ2 to equation 20. Then, we have
EK(k) [∥∥GK(k) −HK(k)∥∥2] ≤ 2ξ2
M2 τ−1∑ i=τ−d M∑ m=1 σ2 + 2 M2 τ−1−d∑ i=0 M∑ m=1 σ2 = 2σ2 M [ dξ2 + τ − d ]
Lemma 4. Under assumption ESk|x [g(x)] = 5F (x), the expected inner product between stochastic gradient and full batch gradient can be expanded as
EK(k) [〈 5F (XK(k)),GK(k) 〉] =
ξd+ τ − d 2 ∥∥5F (XK(k))∥∥2 + 1 2M
[ ξ
τ−1∑ i=τ−d ‖5F (Xτk+d+i)‖2F + τ−1−d∑ i=0 ‖5F (Xτk+d+i)‖2F
]
− 1 2M M∑ m=1 [ τ−1−d∑ i=0 ∥∥∥5F (XK(k))−5F (x(m)τk+d+i)∥∥∥2 + ξ τ−1∑ i=τ−d ∥∥∥5F (XK(k))−5F (x(m)τk+d+i)∥∥∥2 ]
Proof. EK(k) [〈 5F (XK(k)),GK(k) 〉] = EK(k) [〈 5F (XK(k)), ξ 1
M τ−1∑ i=τ−d M∑ m=1 g ( x (m) τk+d+i ) + 1 M τ−1−d∑ i=0 M∑ m=1 g ( x (m) τk+d+i
)〉]
= ξ 1
M τ−1∑ i=τ−d M∑ m=1 〈 5F (XK(k)),5F ( x (m) τk+d+i )〉 + 1 M τ−1−d∑ i=0 M∑ m=1 〈 5F (XK(k)),5F ( x (m) τk+d+i )〉
= ξ
2M τ−1∑ i=τ−d M∑ m=1 [∥∥5F (XK(k))∥∥2 + ∥∥∥5F (x(m)τk+d+i)∥∥∥2 − ∥∥∥5F (XK(k))−5F (x(m)τk+d+i)∥∥∥2] (21)
+ 1
2M τ−1−d∑ i=0 M∑ m=1 [∥∥5F (XK(k))∥∥2 + ∥∥∥5F (x(m)τk+d+i)∥∥∥2 − ∥∥∥5F (XK(k))−5F (x(m)τk+d+i)∥∥∥2] (22)
= ξd+ τ − d
2
∥∥5F (XK(k))∥∥2 + 1 2M
[ ξ
τ−1∑ i=τ−d ‖5F (Xτk+d+i)‖2F + τ−1−d∑ i=0 ‖5F (Xτk+d+i)‖2F
]
− 1 2M M∑ m=1 [ τ−1−d∑ i=0 ∥∥∥5F (XK(k))−5F (x(m)τk+d+i)∥∥∥2 + ξ τ−1∑ i=τ−d ∥∥∥5F (XK(k))−5F (x(m)τk+d+i)∥∥∥2 ]
where equation 21 and equation 22 come from 〈a, b〉 = 12 ( ||a||2 + ||b||2 − ||a− b||2 ) .
Lemma 5. Under assumptionsEξ|x [g(x)] = 5F (x) andEξ|x||g(x)−5F (x)||2 ≤ σ2, the squared norm of stochastic gradient can be bounded as EK(k) [∥∥GK(k)∥∥2] ≤ 2σ2
M
[ dξ2 + τ − d ] + 2dξ2
M τ−1∑ i=τ−d ‖5F (Xτk+d+i)‖2F+ 2(τ − d) M τ−1−d∑ i=0 ‖5F (Xτk+d+i)‖2F
Proof. EK(k) [∥∥GK(k)∥∥2]
= EK(k) [∥∥GK(k) − EK(k)[GK(k)]∥∥2]+ ∥∥EK(k)[GK(k)]∥∥2
= EK(k) [∥∥GK(k) −HK(k)∥∥2]+ ∥∥HK(k)∥∥2
≤ 2σ 2
M
[ dξ2 + τ − d ] + 2dξ2
M τ−1∑ i=τ−d ‖5F (Xτk+d+i)‖2F + 2(τ − d) M τ−1−d∑ i=0 ‖5F (Xτk+d+i)‖2F
(23)
where equation 23 follows equation 12 and equation 15.
Theorem 1 (Convergence of SGD). Under assumptions, when the learning rate satisfies the following two formulas at the same time
2Lηdξ2 − ξ + 6ξL 2η2d+ 6L2η2(τ − d)
1− ξ2 + 6ξL2η2d ≤ 0
2Lη(τ − d)− ξ + 6ξL 2η2d+ 6L2η2(τ − d)
1− ξ2 + 6ξL2η2d+ 6L2η2(τ − d) ≤ 0
Then the average-squared gradient norm after K iterations is bounded as
EK(k)
[ 1
K K∑ k=1
∥∥5F (µK(k))∥∥2 ]
≤2 [F (µ1)− Finf ] ηK(ξd+ τ − d) + η2Lσ2
[ ξ2d+ τ − d ] M(ξd+ τ − d) + η2 6L2(1 + ξ) ξd+ τ − d τ−1∑ l=τ−d l∑ i=0 σ2 + η2 6dξ2L2τσ2(1 + ξ) (ξd+ τ − d)(1− ξ2)
+ η2
K 12dσ2L2ξ2(τ − d)(1 + ξ) (ξd+ τ − d)(1− ξ2) + η2 KM 12L2dξ2(τ − d)(1 + ξ) (ξd+ τ − d)(1− ξ2) d−1∑ i=1 ‖5F (Xi)‖2F
where µk = 1M ∑M i=1 x (i) τk+d, ‖ ‖ 2 F is the Frobenius norm.
Proof.
Recall the intermediate result equation 11 in the proof of Lemma 1:
EK(k)
[ 1
K K∑ k=1 ∥∥5F (µK(k))∥∥2 ] ≤2 [F (µ1)− Finf ] ηK(ξd+ τ − d) + 2Lησ2 [ ξ2d+ τ − d ] M(ξd+ τ − d)
+ 2Lηdξ2 − ξ
KM(ξd+ τ − d) K∑ k=1 τ−1∑ i=τ−d EK(k) ‖5F (Xτk+d+i)‖ 2 F
+ 2Lη(τ − d)− ξ KM(ξd+ τ − d) K∑ k=1 τ−1−d∑ i=0 EK(k) ‖5F (Xτk+d+i)‖ 2 F
+ L2
KM(ξd+ τ − d) K∑ k=1 τ−1−d∑ i=0 EK(k) ‖Xτk+dJ− Xτk+d+i‖ 2 F
+ ξL2
KM(ξd+ τ − d) K∑ k=1 τ−1∑ i=τ−d EK(k) ‖Xτk+dJ− Xτk+d+i‖ 2 F
(24)
Our goal is to provide an upper bound for the network error term K∑ k=1 τ−1∑ i=τ−d EK(k) ‖Xτk+dJ− Xτk+d+i‖ 2 F . First of all, let us derive a specific expression for
Xτk+dJ− Xτk+d+i. According to the update rule equation 5, one can observe that
Xτk+dJ− Xτk+d+i
= Xτk+d(J− I) + η i∑
j=0
Gτk+d+j
= ξ (Xτk+d−1 − ηGτk+d−1) (J− I) + (1− ξ) (Xτk − ηGτk) J(J− I) + η i∑
j=0
Gτk+d+j
= ξXτ(k−1)+d(J− I)− ξη τ−1∑ i=0 Gτ(k−1)+d+i(J− I) + η i∑ j=0 Gτk+d+j = ξ2Xτ(k−2)+d(J− I)− η 2∑ j=1 τ−1∑ i=0 ξjGτ(k−j)+d+i(J− I) + η i∑ j=0 Gτk+d+j = ξkXd(J− I)− η k∑ j=1 τ−1∑ i=0 ξjGτ(k−j)+d+i(J− I) + η i∑ j=0 Gτk+d+j = ξk (Xd−1 − ηGd−1) (J− I)− η k∑ j=1 τ−1∑ i=0 ξjGτ(k−j)+d+i(J− I) + η i∑ j=0 Gτk+d+j = ξkX1(J− I)− ηξk d−1∑ i=1 Gi(J− I)− η k∑ j=1 τ−1∑ i=0 ξjGτ(k−j)+d+i(J− I) + η i∑ j=0 Gτk+d+j = − ηξk d−1∑ i=1 Gi(J− I)− η k∑ j=1 τ−1∑ i=0 ξjGτ(k−j)+d+i(J− I) + η i∑ j=0 Gτk+d+j (25)
where equation 25 follows the fact that all workers start from the same point at the beginning of each local update period.
Accordingly, we have τ−1∑ i=τ−d EK(k) ‖Xτk+dJ− Xτk+d+i‖ 2 F
= τ−1∑ l=τ−d EK(k) ∥∥∥∥∥∥−ηξk d−1∑ i=1 Gi(J− I)− η k∑ j=1 τ−1∑ i=0 ξjGτ(k−j)+d+i(J− I) + η l∑ i=0 Gτk+d+i ∥∥∥∥∥∥ 2
F
≤3η2EK(k) ξ2kd∥∥∥∥∥ d−1∑ i=1 Gi(J− I) ∥∥∥∥∥ 2
F
+ d ∥∥∥∥∥∥ k∑ j=1 τ−1∑ i=0 ξjGτ(k−j)+d+i(J− I) ∥∥∥∥∥∥ 2
F
+ τ−1∑ l=τ−d ∥∥∥∥∥ l∑ i=0 Gτk+d+i ∥∥∥∥∥ 2
F  ≤3η2EK(k) ξ2kd∥∥∥∥∥ d−1∑ i=1 Gi ∥∥∥∥∥ 2
F
+ d ∥∥∥∥∥∥ k∑ j=1 τ−1∑ i=0 ξjGτ(k−j)+d+i ∥∥∥∥∥∥ 2
F
+ τ−1∑ l=τ−d ∥∥∥∥∥ l∑ i=0 Gτk+d+i ∥∥∥∥∥ 2
F  (26) =3η2
M∑ m=1 EK(k)ξ2kd ∥∥∥∥∥ d−1∑ i=1 g(x (m) i ) ∥∥∥∥∥ 2 + dEK(k) ∥∥∥∥∥∥ k∑ j=1 τ−1∑ i=0 ξjg(x (m) τ(k−j)+d+i) ∥∥∥∥∥∥ 2 + EK(k) τ−1∑ l=τ−d ∥∥∥∥∥ l∑ i=0 g(x (m) τk+d+i) ∥∥∥∥∥ 2 
=3η2d  M∑ m=1 EK(k)ξ2k ∥∥∥∥∥ d−1∑ i=1 g(x (m) i ) ∥∥∥∥∥ 2
︸ ︷︷ ︸ T1
+ M∑ m=1 EK(k) ∥∥∥∥∥∥ k∑ j=1 ξj τ−1∑ i=0 g(x (m) τ(k−j)+d+i) ∥∥∥∥∥∥ 2
︸ ︷︷ ︸ T2
+ 1
d M∑ m=1 τ−1∑ l=τ−d EK(k) ∥∥∥∥∥ l∑ i=0 g(x (m) τk+d+i) ∥∥∥∥∥ 2
︸ ︷︷ ︸ T3  (27)
where the equation 26 is due to the operator norm of J− I is less than 1. For T2, we have
M∑ m=1 EK(k) ∥∥∥∥∥∥ k∑ j=1 ξj τ−1∑ i=0 g(x (m) τ(k−j)+d+i) ∥∥∥∥∥∥ 2
= M∑ m=1 EK(k) ∥∥∥∥∥∥ k∑ j=1 ξj τ−1∑ i=0 [ g(x (m) τ(k−j)+d+i)−5F (x (m) τ(k−j)+d+i) ] + k∑ j=1 ξj τ−1∑ i=0 5F (x(m)τ(k−j)+d+i) ∥∥∥∥∥∥ 2 ≤ 2 M∑ m=1 EK(k) ∥∥∥∥∥∥ k∑ j=1 ξj τ−1∑ i=0 [ g(x (m) τ(k−j)+d+i)−5F (x (m) τ(k−j)+d+i) ]∥∥∥∥∥∥ 2
︸ ︷︷ ︸ T4
+ 2 M∑ m=1 EK(k) ∥∥∥∥∥∥ k∑ j=1 ξj τ−1∑ i=0 5F (x(m)τ(k−j)+d+i) ∥∥∥∥∥∥ 2
︸ ︷︷ ︸ T5
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
T4 = 2 M∑ m=1 k∑ j=1 ξ2j τ−1∑ i=0 EK(k) ∥∥∥g(x(m)τ(k−j)+d+i)−5F (x(m)τ(k−j)+d+i)∥∥∥2
≤ 2 M∑ m=1 k∑ j=1 ξ2j τ−1∑ i=0 σ2 ≤ 2Mτσ 2ξ2 1− ξ2 (28)
where equation 28 according to the summation formula of power k∑ j=1 ξ2j ≤ ∞∑ j=1 ξ2j ≤ ξ 2 1− ξ2
For the second term T5, we get
T5 = 2 k∑ j=1 ξ2j τ−1∑ i=0 E ∥∥∥5F (X(m)τ(k−j)+d+i)∥∥∥2 F = 2 k−1∑ r=0 ξ2(k−r) τ−1∑ i=0 E ∥∥∥5F (X(m)τr+d+i)∥∥∥2 F
Substituting the bounds of T4 and T5 into T2, we have
T2 ≤ 2Mτσ2ξ2
1− ξ2 + 2 k−1∑ r=0 ξ2(k−r) τ−1∑ i=0 E ∥∥∥5F (X(m)τr+d+i)∥∥∥2 F
For T1, we have M∑ m=1 EK(k)ξ2k ∥∥∥∥∥ d−1∑ i=1 g(x (m) i ) ∥∥∥∥∥ 2
= M∑ m=1 EK(k)ξ2k ∥∥∥∥∥ d−1∑ i=1 [ g(x (m) i )−5F (x (m) i ) ] + d−1∑ i=1 5F (x(m)i ) ∥∥∥∥∥ 2 ≤ 2 M∑ m=1 EK(k)ξ2k ∥∥∥∥∥ d−1∑ i=1 [ g(x (m) i )−5F (x (m) i ) ]∥∥∥∥∥ 2
︸ ︷︷ ︸ T6
+ 2 M∑ m=1 EK(k)ξ2k ∥∥∥∥∥ d−1∑ i=1 5F (x(m)i ) ∥∥∥∥∥ 2
︸ ︷︷ ︸ T7
For the first term T6, since the stochastic gradients are unbiased, all cross terms are zero. Thus, combining with Assumption of bounded variance, we have
T6 = 2 M∑ m=1 d−1∑ i=1 EK(k)ξ2k ∥∥∥g(x(m)i )−5F (x(m)i )∥∥∥2 ≤ 2ξ2k M∑ m=1 d−1∑ i=1 σ2 = 2ξ2kMdσ2
For the second term T7, directly applying Jensen’s inequality, we get
T7 = 2 M∑ m=1 EK(k)ξ2k ∥∥∥∥∥ d−1∑ i=1 5F (x(m)i ) ∥∥∥∥∥ 2 ≤ 2d M∑ m=1 EK(k)ξ2k d−1∑ i=1 ∥∥∥5F (x(m)i )∥∥∥2 = 2dξ2k d−1∑ i=1 ‖5F (Xi)‖2F
Substituting the bounds of T6 and T7 into T1, we have T1 ≤ 2ξ2kMdσ2 + 2dξ2k d−1∑ i=1 ‖5F (Xi)‖2F
For T3, we have
T3 = 1
d M∑ m=1 τ−1∑ l=τ−d EK(k) ∥∥∥∥∥ l∑ i=0 g(x (m) τk+d+i) ∥∥∥∥∥ 2
= 1
d M∑ m=1 τ−1∑ l=τ−d EK(k) ∥∥∥∥∥ l∑ i=0 ( g(x (m) τk+d+i)−5F (x (m) τk+d+i) ) + l∑ i=0 5F (x(m)τk+d+i) ∥∥∥∥∥ 2
≤ 2 d M∑ m=1 τ−1∑ l=τ−d EK(k) ∥∥∥∥∥ l∑ i=0 ( g(x (m) τk+d+i)−5F (x (m) τk+d+i) )∥∥∥∥∥ 2 + 2 d M∑ m=1 τ−1∑ l=τ−d EK(k) ∥∥∥∥∥ l∑ i=0 5F (x(m)τk+d+i) ∥∥∥∥∥ 2
≤ 2 d M∑ m=1 τ−1∑ l=τ−d l∑ i=0 EK(k) ∥∥∥g(x(m)τk+d+i)−5F (x(m)τk+d+i)∥∥∥2 + 2d M∑ m=1 τ−1∑ l=τ−d l∑ i=0 EK(k) ∥∥∥5F (x(m)τk+d+i)∥∥∥2
≤ 2 d M∑ m=1 τ−1∑ l=τ−d l∑ i=0 σ2 + 2 d M∑ m=1 τ−1∑ l=τ−d l∑ i=0 EK(k) ∥∥∥5F (x(m)τk+d+i)∥∥∥2
= 2M
d τ−1∑ l=τ−d l∑ i=0 σ2 + 2 d M∑ m=1 τ−1∑ l=τ−d l∑ i=0 EK(k) ∥∥∥5F (x(m)τk+d+i)∥∥∥2
Substituting the bounds of T1, T2 and T3 into equation 27, we have
τ−1∑ i=τ−d EK(k) ‖Xτk+dJ− Xτk+d+i‖ 2 F
≤ 3η2d [ 2ξ2kMdσ2 + 2Mτσ2ξ2
1− ξ2 + 2dξ2k d−1∑ i=1 ‖5F (Xi)‖2F + 2 k−1∑ r=0 ξ2(k−r) τ−1∑ i=0 E ∥∥∥5F (X(m)τr+d+i)∥∥∥2 F
+ 2M
d τ−1∑ l=τ−d l∑ i=0 σ2 + 2 d M∑ m=1 τ−1∑ l=τ−d l∑ i=0 EK(k) ∥∥∥5F (x(m)τk+d+i)∥∥∥2
]
And in the same way, we have
τ−1−d∑ l=0 EK(k) ‖Xτk+dJ− Xτk+d+l‖ 2 F
≤ 3η2(τ − d) [ 2ξ2kMdσ2 + 2Mτσ2ξ2
1− ξ2 + 2dξ2k d−1∑ i=1 ‖5F (Xi)‖2F + 2 k−1∑ r=0 ξ2(k−r) τ−1∑ i=0 E ∥∥∥5F (X(m)τr+d+i)∥∥∥2 F
+ 2M
τ − d τ−1−d∑ l=0 l∑ i=0 σ2 + 2 τ − d M∑ m=1 τ−1−d∑ l=0 l∑ i=0 EK(k) ∥∥∥5F (x(m)τk+d+i)∥∥∥2
]
Then, summing over all periods from k = 0 to k = K, where K is the total global iterations:
K∑ k=1 τ−1∑ i=τ−d EK(k) ‖Xτk+dJ− Xτk+d+i‖ 2 F
≤ 3η2d K∑ k=1
[ 2ξ2kMdσ2 + 2Mτσ2ξ2
1− ξ2 + 2dξ2k d−1∑ i=1 ‖5F (Xi)‖2F + 2 k−1∑ r=0 ξ2(k−r) τ−1∑ i=0 E ∥∥∥5F (X(m)τr+d+i)∥∥∥2 F
+ 2M
d τ−1∑ l=τ−d l∑ i=0 σ2 + 2 d M∑ m=1 τ−1∑ l=τ−d l∑ i=0 EK(k) ∥∥∥5F (x(m)τk+d+i)∥∥∥2
]
≤ 6η2d ξ 2
1− ξ2
[ 2Mdσ2 + 2d
d−1∑ i=1 ‖5F (Xi)‖2F
] + 6η2dτσ2ξ2MK
1− ξ2 + 6η2MK τ−1∑ l=τ−d l∑ i=0 σ2
+ 6η2d K∑ k=1 k−1∑ r=0 ξ2(k−r) τ−1∑ i=0 E ∥∥∥5F (X(m)τr+d+i)∥∥∥2 F + 6η2 K∑ k=1 τ−1∑ l=τ−d l∑ i=0 EK(k) ‖5F (Xτk+d+i)‖ 2
(29)
Expanding the summation, we have
K∑ k=1 k−1∑ r=0 ξ2(k−r) τ−1∑ i=0 E ∥∥∥5F (X(m)τr+d+i)∥∥∥2 F
≤ K∑ r=1 [( τ−1∑ i=0 E ‖5F (Xτr+d+i)‖2F )( K∑ k=r ξ2(k−r) )]
≤ K∑ r=1 [( τ−1∑ i=0 E ‖5F (Xτr+d+i)‖2F )( +∞∑ k=r ξ2(k−r) )]
≤ 1 1− ξ2 K∑ k=1 τ−1∑ i=0 E ‖5F (Xτk+d+i)‖2F (30)
And in the same way, we have
K∑ k=1 τ−1∑ l=τ−d l∑ i=0 E ‖5F (Xτk+d+i)‖2F ≤ d K∑ k=1 τ−1∑ i=0 E ‖5F (Xτk+d+i)‖2F (31)
Plugging equation 30 and equation 31 into equation 29, K∑ k=1 τ−1∑ i=τ−d EK(k) ‖Xτk+dJ− Xτk+d+i‖ 2 F
≤ 6η2d ξ 2
1− ξ2
[ 2Mdσ2 + 2d
d−1∑ i=1 ‖5F (Xi)‖2F
] + 6η2dτσ2ξ2MK
1− ξ2 + 6η2MK τ−1∑ l=τ−d l∑ i=0 σ2
+ 6η2d 1− ξ2 K∑ k=1 τ−1∑ i=0 E ‖5F (Xτk+d+i)‖2F + 6η 2d K∑ k=1 τ−1∑ i=0 E ‖5F (Xτk+d+i)‖2F
And in the same way, we have
K∑ k=1 τ−1−d∑ l=0 EK(k) ‖Xτk+dJ− Xτk+d+l‖ 2 F
≤ 6η2(τ − d) ξ 2
1− ξ2
[ 2Mdσ2 + 2d
d−1∑ i=1 ‖5F (Xi)‖2F
] +
6η2(τ − d)τσ2ξ2MK 1− ξ2 + 6η2MK τ−1∑ l=τ−d l∑ i=0 σ2
+ 6η2(τ − d) 1− ξ2 K∑ k=1 τ−1∑ i=0 E ‖5F (Xτk+d+i)‖2F + 6η 2(τ − d) K∑ k=1 τ−1−d∑ i=0 E ‖5F (Xτk+d+i)‖2F
Recall the intermediate result equation 11 in the proof of Lemma 1:
EK(k)
[ 1
K K∑ k=1
∥∥5F (µK(k))∥∥2 ]
≤2 [F (µ1)− Finf ] ηK(ξd+ τ − d) + η2Lσ2
[ ξ2d+ τ − d ] M(ξd+ τ − d) + η2 6L2(1 + ξ) ξd+ τ − d τ−1∑ l=τ−d l∑ i=0 σ2 + η2 6dξ2L2τσ2(1 + ξ) (ξd+ τ − d)(1− ξ2)
+ η2
K 12dσ2L2ξ2(τ − d)(1 + ξ) (ξd+ τ − d)(1− ξ2) + η2 KM 12L2dξ2(τ − d)(1 + ξ) (ξd+ τ − d)(1− ξ2) d−1∑ i=1 ‖5F (Xi)‖2F
+ 2Lηdξ2 − ξ + 6ξL 2η2d+6L2η2(τ−d) 1−ξ2 + 6ξL 2η2d
KM(ξd+ τ − d)
K∑ k=1 τ−1∑ i=τ−d EK(k) ‖5F (Xτk+d+i)‖ 2 F
+ 2Lη(τ − d)− ξ + 6ξL 2η2d+6L2η2(τ−d) 1−ξ2 + 6ξL 2η2d+ 6L2η2(τ − d) KM(ξd+ τ − d) K∑ k=1 τ−1−d∑ i=0 EK(k) ‖5F (Xτk+d+i)‖ 2 F
When the learning rate satisfies the following two formulas at the same time
2Lηdξ2 − ξ + 6ξL 2η2d+ 6L2η2(τ − d)
1− ξ2 + 6ξL2η2d ≤ 0
2Lη(τ − d)− ξ + 6ξL 2η2d+ 6L2η2(τ − d)
1− ξ2 + 6ξL2η2d+ 6L2η2(τ − d) ≤ 0
And K∑ k=1 τ−1∑ i=0 EK(k) ‖5F (Xτk+d+i)‖ 2 F = Ek K∑ k=1 ‖5F (µk)‖2
Thus, we have
EK(k)
[ 1
K K∑ k=1
∥∥5F (µK(k))∥∥2 ]
≤2 [F (µ1)− Finf ] ηK(ξd+ τ − d) + η2Lσ2
[ ξ2d+ τ − d ] M(ξd+ τ − d) + η2 6L2(1 + ξ) ξd+ τ − d τ−1∑ l=τ−d l∑ i=0 σ2 + η2 6dξ2L2τσ2(1 + ξ) (ξd+ τ − d)(1− ξ2)
+ η2
K 12dσ2L2ξ2(τ − d)(1 + ξ) (ξd+ τ − d)(1− ξ2) + η2 KM 12L2dξ2(τ − d)(1 + ξ) (ξd+ τ − d)(1− ξ2) d−1∑ i=1 ‖5F (Xi)‖2F
Corollary 1. Under sssumptions, if the learning rate is η = M+VM √ M K the average-squared gradient norm after K iterations is bounded by
EK(k)
[ 1
K K∑ k=1
∥∥5F (µK(k))∥∥2 ]
≤ 2 [F (µ1)− Finf ]√ MK(ξd+ τ − d) + 1√ MK
2Lσ2 [ ξ2d+ τ − d ] (ξd+ τ − d)
+ M2
K3
( 1 + V
M
)4 6L2(1 + ξ)
ξd+ τ − d τ−1∑ l=τ−d l∑ i=0 σ2 + M2 K3 ( 1 + V M )4 6dξ2L2τσ2(1 + ξ) (ξd+ τ − d)(1− ξ2)
+ M2
K3
( 1 + V
M
)4 12dσ2L2ξ2(τ − d)(1 + ξ)
(ξd+ τ − d)(1− ξ2) + M K3
( 1 + V
M )4 12L2dξ2(τ − d)(1 + ξ) (ξd+ τ − d)(1− ξ2) d−1∑ i=1 ‖5F (Xi)‖2F
If the total iterationsK is sufficiently large, then the average-squared gradient norm will be bounded by
E
[ 1
K K∑ k=1
‖5F (µk)‖2 ] ≤ 2 [F (µ1)− Finf ] + 2Lσ2 [ ξ2d+ τ − d ] √ MK(ξd+ τ − d)
.

Review summaries:
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.

In this paper, the authors present DaSGD, which overlaps the computation and communication of distributed training.  In a nutshell, the idea is to combine PipeSGD and local SGD, which totally makes sense. The experiment results show good performance.

The paper proposes to combine local sgd with overlapped communication. A convergence analysis is given. The experiments validates the model performance.