Stochastic gradient descent (SGD) is the backbone of stateof-the-art supervised learning, which is revolutionizing inference and decision-making in many diverse applications. Classical SGD was designed to be run on a single computing node, and its error-convergence with respect to the number of iterations has been extensively analyzed and improved via accelerated SGD methods. Due to the massive training data-sets and neural network architectures used today, it has became imperative to design distributed SGD implementations, where gradient computation and aggregation is parallelized across multiple worker nodes. Although parallelism boosts the amount of data processed per iteration, it exposes SGD to unpredictable node slowdown and communication delays stemming from variability in the computing infrastructure. Thus, there is a critical need to make distributed SGD fast, yet robust to system variability.
Wall-clock Time. The convergence speed of distributed SGD is a product of two factors: 1) the error in the trained model versus the number of iterations, and 2) the number of iterations completed per second. Traditional single-node SGD analysis focuses on optimizing the first factor, because the second factor is generally a constant when SGD is run on a single dedicated server. In distributed SGD, which is often run on shared cloud infrastructure, the second factor depends on several aspects such as the number of worker nodes, their local computation and communication delays, and the protocol (synchronous, asynchronous or periodic) used to aggregate their gradients. Hence, in order to achieve the fastest convergence speed we need: 1) optimization techniques (eg. variable learning rate) to maximize the error-convergence rate with respect to iterations, and 2) scheduling techniques (eg. straggler mitigation, infrequent communication) to maximize the number of iterations completed per second. These directions are inter-dependent and need to be explored together rather than in isolation. While many works have advanced the first direction, the second is less explored from a theoretical point of view, and the juxtaposition of both is an unexplored problem.
A popular distributed SGD implementation is the parameter server framework (Dean et al., 2012;Cui et al., 2014;Li et al., 2014;Gupta et al., 2016;Mitliagkas et al., 2016) where in each iteration, worker nodes compute gradients on one mini-batch of data and a central parameter server aggregates these gradients (synchronously or asynchronously) and updates the parameter vector x. The constant communication between the parameter server and worker nodes in each iteration can be expensive and slow in bandwidthlimited computed environments. Recently proposed distributed SGD frameworks such as Elastic-averaging (Zhang et al., 2015;Chaudhari et al., 2017), Federated Learning (McMahan et al., 2016;Smith et al., 2017b) and decentralized SGD (Lian et al., 2017;Jiang et al., 2017)
Figure 1. This work departs from the traditional view of considering error-convergence with respect to the number of iterations, and instead considers the true convergence in terms of error versus wall-clock time. Adaptive strategies that start with infrequent model-averaging and increase the communication frequency can achieve the best error-runtime trade-off. communication cost by allowing worker nodes to perform local updates to the parameter x instead of just computing gradients. The resulting locally trained models (which are different due to variability in training data across nodes) are periodically averaged through a central server, or via direct inter-worker communication. This local-update strategy has been shown to offer significant speedup in deep neural network training (Lian et al., 2017;McMahan et al., 2016).
Error-Runtime Trade-offs in Local-Update SGD. While local updates reduce the communication-delay incurred per iteration, discrepancies between local models can result in an inferior error-convergence. For example, consider the case of periodic-averaging SGD (PASGD) where each of m worker nodes makes τ local updates, and the resulting models are averaged after every τ iterations (Moritz et al., 2015;Su & Chen, 2015;Chen & Huo, 2016;Seide & Agarwal, 2016;Zhang et al., 2016;Zhou & Cong, 2017;Lin et al., 2018). A larger value of τ leads to slower convergence with respect to the number of iterations as illustrated in Figure 1. However, if we look at the true convergence with respect to the wall-clock time, then a larger τ , that is, less frequent averaging, saves communication delay and reduces the runtime per iteration. While some recent theoretical works (Zhou & Cong, 2017;Yu et al., 2018;Wang & Joshi, 2018;Stich, 2018) study this dependence of the error-convergence with respect to the number of iterations as τ varies, achieving a provably-optimal speed-up in the true convergence with respect to wall-clock time is an open problem that we aim to address in this work.
Need for Adaptive Communication Strategies. In the error-runtime in Figure 1, we observe a trade-off between the convergence speed and the error floor when the number of local updates τ is varied. A larger τ gives a faster initial drop in the training loss but results in a higher error floor. This calls for adaptive communication strategies that start with a larger τ and gradually decrease it as the model reaches closer to convergence. Such an adaptive strategy will offer a win-win in the error-runtime trade-off by achieving fast convergence as well as low error floor. To the best of our knowledge, this is the first work to propose an adaptive communication frequency strategy.
Main Contributions. This paper focuses on periodicaveraging local-update SGD (PASGD) and makes the following main contributions:
1. We first analyze the runtime per iteration of periodic averaging SGD (PASGD) by modeling local computing time and communication delays as random variables, and quantify its runtime speed-up over fully synchronous SGD. A novel insight from this analysis is that periodic-averaging strategy not only reduces the communication delay but also mitigates synchronization delays in waiting for slow or straggling nodes.
2. By combining the runtime analysis error-convergence analysis of PASGD (Wang & Joshi, 2018), we can obtain the error-runtime trade-off for different values of τ . Using this combined error-runtime trade-off, we derive an expression of the optimal communication period, which can serve as a useful guideline in practice. 4. We present a convergence analysis for PASGD with variable communication period τ and variable learning rate η, generalizing previous work (Wang & Joshi, 2018). This analysis shows that decaying τ provides similar convergence benefits as decaying learning rate, the difference being that varying τ improves the true convergence with respect to the wall-clock time. Adaptive communication can also be used in conjunction with existing learning rate schedules.
Although we focus on periodic simple-averaging of local models, the insights on error-runtime trade-offs and adaptive communication strategies are directly extendable to other communication-efficient SGD algorithms including Federated Learning (McMahan et al., 2016), Elastic-Averaging (Zhang et al., 2015) and Decentralized averaging (Jiang et al., 2017;Lian et al., 2017), as well as synchronous/asynchronous distributed SGD with a central parameter server (Dean et al., 2012;Cui et al., 2014;Dutta et al., 2018).
Empirical Risk Minimization via Mini-batch SGD. Our objective is to minimize an objective function F (x), the empirical risk function, with respect to model parameters denoted by x ∈ R d . The training dataset is denoted by S = {s 1 , . . . , s N }, where s i represents the i-th labeled data point. The objective function can be expressed as the empirical risk calculated using the training data and is given by
where f (x; s i ) is the composite loss function at the i th data point. In classic mini-batch stochastic gradient descent (SGD) (Dekel et al., 2012), updates to the parameter vector x are performed as follows. If ξ k ⊂ S represents a randomly sampled mini-batch, then the update rule is
where η denotes the learning rate and the stochastic gradient is defined as: g(x; ξ) = 1 |ξ| si∈ξ ∇f (x; s i ). For simplicity, we will use g(x k ) instead of g(x k ; ξ k ) in the rest of the paper. A complete review of convergence properties of serial SGD can be found in (Bottou et al., 2018).
Periodic-Averaging SGD (PASGD). We consider a distributed SGD framework with m worker nodes where all workers can communicate with others via a central server or via direct inter-worker communication. In periodicaveraging SGD, all workers start at the same initial point x 1 . Each worker performs τ local mini-batch SGD updates according to (2), and the local models are averaged by a fusion node or by performing an all-node broadcast. The workers then update their local models with the averaged model, as illustrated in Figure 2. Thus, the overall update rule at the i th worker is given by
where
k denote the model parameters in the i-th worker after k iterations and τ is defined as the communication period. Note that the iteration index k corresponds to the local iterations, and not the number of averaging steps.
Special Case (τ = 1): Fully Synchronous SGD. When τ = 1, that is, the local models are synchronized after every iteration, periodic-averaging SGD is equivalent to fully synchronous SGD which has the update rule
= 3 local steps at each worker The analysis of fully synchronous SGD is identical to serial SGD with m-fold large mini-batch size.
Local Computation Times and Communication Delay.
In order to analyze the effect of τ on the expected runtime per iteration, we consider the following delay model. The time taken by the i th worker to compute a mini-batch gradient at the k th local-step is modeled a random variable Y i,k ∼ F Y , assumed to be i.i.d. across workers and minibatches. The communication delay is a random variable D for each all-node broadcast, as illustrated in Figure 3. The value of random variable D can depend on the number of workers as follows.
where D 0 represents the time taken for each inter-node communication, and s(m) describes how the delay scales with the number of workers, which depends on the implementation and system characteristics. For example, in the parameter server framework, the communication delay can be proportional to 2 log 2 (m) by exploiting a reduction tree structure (Iandola et al., 2016). We assume that s(m) is known beforehand for the communication-efficient distributed SGD framework under consideration.
Convergence Criteria. In the error-convergence analysis, since the objective function is non-convex, we use the expected gradient norm as a an indicator of convergence following (Ghadimi & Lan, 2013;Bottou et al., 2018). We say the algorithm achieves an -suboptimal solution if:
When is arbitrarily small, this condition can guarantee the algorithm converges to a stationary point.
We now present a comparison of the runtime per iteration of periodic-averaging SGD with fully synchronous SGD to illustrate how increasing τ can lead to a large runtime speedup. Another interesting effect of performing more local update τ is that it mitigates the slowdown due to straggling worker nodes.
Runtime Per Iteration of Fully Synchronous SGD. Fully synchronous SGD is equivalent to periodic-averaging SGD with τ = 1. Each of the m workers computes the gradient of one mini-batch and updates the parameter vector x, which takes time Y i,1 at the i th worker 1 . After all workers finish their local updates, an all-node broadcast is performed to synchronize and average the models. Thus, the total time to complete each iteration is given by
where Y i,1 are i.i.d. random variables with probability distribution F Y and D is the communication delay. The term Y m:m denotes the highest order statistic of m i.i.d. random variables (David & Nagaraja, 2003).
Runtime Per Iteration of Periodic-Averaging SGD (PASGD). In periodic-averaging SGD, each worker performs τ local updates before communicating with other workers. Let us denote the average local computation time at the i th worker by
Since the communication delay D is amortized over τ iterations, the average computation time per iteration is
The value of the first term Y m:m and how it compares with Y m:m depends on the probability distribution F Y of Y .
1 Instead of local updates, typical implementations of fully synchronous SGD have a central server that performs the update.
Here we compare PASGD with fully synchronous SGD without a central parameter server.
Speed-up over fully synchronous SGD. We evaluate the speed-up of periodic-averaging SGD over fully synchronous SGD for different Y and D to demonstrate how the relative value of computation versus communication delays affects the speed-up. Consider the simplest case where Y and D are constants and define α = D/Y , the communication/computation ratio. Besides systems aspects such as network bandwidth and computing capacity, for deep neural network training, this ratio α also depends on the size of the neural network model and the mini-batch size. See Figure 8 for a comparison of the communication/computation delays of common deep neural network architectures. Then Y , Y m:m , Y m:m are all equal to Y , and the ratio of E[T sync ] and E[T P-Avg ] is given by
Figure 4 shows the speed-up for different values of α and τ . When D is comparable with Y (α = 0.9), periodicaveraging SGD (PASGD) can be almost twice as fast as fully synchronous SGD. Straggler Mitigation due to Local Updates. Suppose that Y is exponentially distributed with mean y and variance y 2 . For fully synchronous SGD, the term E[Y m:m ] in ( 8) is equal to y m i=1 1/i, which is approximately equal to y log m. Thus, the expected runtime per iteration of fully synchronous SGD (8) increases logarithmically with the number of workers m. Let us compare this with the scaling of the runtime of periodic-averaging SGD (11). Here, Y (9) is an Erlang random variable with mean y and variable y 2 /τ . Since the variance is τ times smaller than that of Y , the maximum order statistic 5 shows the probability distribution of T sync and T P-Avg for exponentially distributed Y . Observe that T P-Avg has a much lighter tail. This is because the effect of the variability in Y on T P-Avg is reduced due to the Y in (8) being replaced by Y (which has lower variance) in (11).
In this subsection, we combine the runtime analysis with previous error-convergence analysis for PASGD (Wang & Joshi, 2018). Due to space limitations, we state the necessary theoretical assumptions in the Appendix; the assumptions are similar to previous works (Zhou & Cong, 2017;Wang & Joshi, 2018) on the convergence of local-update SGD algorithms.
Theorem 1 (Error-runtime Convergence of PASGD).
For PASGD, under certain assumptions (stated in the Appendix), if the learning rate satisfies ηL+η 2 L 2 τ (τ -1) ≤ 1, Y and D are constants, and all workers are initialized at the same point x 1 , then after total T wall-clock time, the minimal expected squared gradient norm within T time interval will be bounded by:
where L is the Lipschitz constant of the objective function and σ 2 is the variance bound of mini-batch stochastic gradients.
The proof of Theorem 1 is presented in the Appendix. From the optimization error upper bound (13), one can easily observe the error-runtime trade-off for different communication periods. While a larger τ reduces the runtime per iteration and let the first term in ( 13) become smaller, it also adds additional noise and increases the last term. In Figure 6,
we plot theoretical bounds for both fully synchronous SGD (τ = 1) and PASGD. It is shown that although PASGD with τ = 10 starts with a rapid drop, it will eventually converge to a high error floor. This theoretical result is also corroborated by experiments in Section 5. Another direct outcome of Theorem 1 is the determination of the best communication period that balances the first and last terms in (13). We will discuss the selection of communication period later in Section 4.1.
Inspired by the clear trade-off in the learning curve in Figure 6, it would be better to have an adaptive communication strategy that starts with infrequent communication to improve convergence speed, and then increases the frequency to achieve a low error floor. In this section, we are going to develop the proposed adaptive communication scheme.
The basic idea to adapt the communication is to choose the communication period that minimizes the optimization error at each wall-clock time. One way to achieve the idea is switching between the learning curves at their intersections. However, without prior knowledge of various curves, it would be difficult to determine the switch points.
Instead, we divide the whole training procedure into uniform wall-clock time intervals with the same length T 0 . At the beginning of each time interval, we select the best value of τ that has the fastest decay rate in the next T 0 wall-clock time.
If the interval length T 0 is small enough and the best choice of communication period for each interval can be precisely estimated, then this adaptive scheme should achieve a winwin in the error-runtime trade-off as illustrated in Figure 7.
After setting the interval length, the next question is how Training loss
Choose the best τ for each time interval. to estimate the best communication period for each time interval. In Section 4.1 we use the error-runtime analysis in Section 3.3 to find the best τ at each time.
From Theorem 1, it can be observed that there is an optimal value τ * that minimizes the optimization error bound at given wall-clock time. In particular, consider the simplest setting where Y and D are constants. Then, by minimizing the upper bound ( 13) over τ , we obtain the following.
Theorem 2. For PASGD, under the same assumptions as Theorem 1, the optimization error upper bound in (13) at time T is minimized when the communication period is
The proof is straightforward by setting the derivative of (13) to zero. We present the details in the Appendix. Suppose all workers starts from the same initial point x 1 = x t=0 where subscript t denotes the wall-clock time. Directly applying Theorem 2 to the first time interval, then the best choice of communication period is:
Similarly, for the l-th time interval, workers can be viewed as restarting training at a new initial point x t=lT0 . Applying Theorem 2 again, we have
Comparing ( 15) and ( 16), it is easy to see the generated communication period sequence decreases along with the objective value F (x t ) when the learning rate is fixed. This result is consistent with the intuition that the trade-off between error-convergence and communication-efficiency varies over time. Compared to the initial phase of training, the benefit of using a large communication period diminishes as the model reaches close to convergence. At this later stage, a lower error floor is more preferable to speeding up the runtime.
Remark 1 (Connection to Decaying Learning Rate). Using a fixed learning rate in SGD leads to an error floor at convergence. To further reduce the error, practical SGD implementations generally decay the learning rate or increase the mini-batch size (Smith et al., 2017a;Goyal et al., 2017).
As we saw from the convergence analysis Theorem 1, performing local updates adds additional noise in stochastic gradients, resulting in a higher error floor convergence. Decaying the communication period can gradually reduce the variance of gradients and yield a similar improvement in convergence. Thus, adaptive communication strategies are similar in spirit to decaying learning rate or increasing minibatch size. The key difference is that here we are optimizing the true error convergence with respect to wall-clock time rather than the number iterations.
Although ( 15) and ( 16) provide useful insights about how to adapt τ over time, it is still difficult to directly use them in practice due to the Lipschitz constant L and the gradient variance bound σ 2 being unknown. For deep neural networks, estimating these constants can be difficult and unreliable due to the highly non-convex and high-dimensional loss surface. As an alternative, we propose a simpler rule where we approximate F inf by 0, and divide ( 16) by ( 15) to obtain the basic communication period update rule:
where a is the ceil function to round a to the nearest integer ≥ a. Since the objective function values (i.e., training loss) F (x t=lT0 ) and F (x t=0 ) can be easily obtained in the training, the only remaining thing now is to determine the initial communication period τ 0 . We obtain a heuristic estimate of τ 0 by a simple grid search over different τ run for one or two epochs each.
The communication period update rule (17) tends to give a decreasing sequence {τ l }. Nonetheless, it is possible that the best value of τ l for next time interval is larger than the current one due to random noise in the training process. Besides, when the training loss gets stuck on plateaus and decreases very slowly, (17) will result in τ l saturating at the same value for a long time. To address this issue, we borrow a idea used in classic SGD where the learning rate is decayed by a factor γ when the training loss saturates for several epochs (Goyal et al., 2017). Similarly, in the our scheme, the communication period will be multiplied by γ < 1 when the τ l given by ( 17) is not strictly less than τ l-1 . To be specific, the communication period for the l th time interval will be determined as follows:
In the experiments, γ = 1/2 turns out to be a good choice.
One can obtain a more aggressive decay in τ l by either reducing the value of γ or introducing a slack variable s in the condition, such as
So far we consider a fixed learning rate η for the local SGD updates at the workers. We now present an adaptive communication strategy that adjusts τ l for a given variable learning rate schedule, in order to obtain the best errorruntime trade-off. Suppose η l denotes the learning rate for the l th time interval. Then, combining (15) and ( 16) again, we have
Observe that when the learning rate becomes smaller, the communication period τ l increases. This result corresponds the intuition that a small learning rate reduces the discrepancy between the local models, and hence is more tolerant to large communication periods.
Equation ( 19) states that the communication period should be proportional to (η 0 /η l ) 3/foot_0 . However, in practice, it is common to decay the learning rate 10 times after some given number of epochs. The dramatic change of learning rate may push the communication period to an unreasonably large value. In the experiments, we observe that when applying (19), the communication period can increase to τ = 1000 which causes the training loss to diverge.
To avoid this issue, we propose the adaptive strategy given by ( 20) below. This strategy can also be justified by theoretical analysis. Suppose that in l th time interval, the objective function has a local Lipschitz smoothness L l . Then, by using the approximation η l L l ≈ 1, which is common in SGD literature (Balles et al., 2016), we derive the following adaptive strategy:
Apart from coupling the communication period with learning rate, when to decay the learning rate is another key design factor. In order to eliminate the noise introduced by local updates, we choose to first gradually decay the communication period to 1 and then decay the learning rate as usual. For example, if the learning rate is scheduled to be decayed at the 80 th epoch but at that time the communication period τ is still larger than 1, then we will continue use the current learning rate until τ = 1.
In this subsection, we are going to provide a convergence guarantee for the proposed adaptive communication scheme by extending the error analysis for PASGD. Without loss of generality, we will analyze an arbitrary communication period sequence {τ 0 , . . . , τ R }, where R represents the total communication rounds 2 . It will be shown that a decreasing sequence of τ is beneficial to the error-convergence rate.
Theorem 3 (Convergence of adaptive communication scheme). For PASGD with adaptive communication period and adaptive learning rate, suppose the learning rate remains same in each local update period. If the following conditions are satisfied as R → ∞,
then the averaged model x is guaranteed to converge to a stationary point:
where s r = r-1 j=0 τ j .
The proof details and a non-asymptotic result (similar to Theorem 1 but with variable τ ) are provided in Appendix. In order to understand the meaning of condition ( 21), let us first consider the case when τ 0 = • • • = τ R is a constant. In this case, the convergence condition is identical to mini-batch SGD (Bottou et al., 2018):
As long as the communication period sequence is bounded, it is trivial to adapt the learning rate scheme in mini-batch SGD (23) to satisfy (21). In particular, when the communication period sequence is decreasing, the last two terms in (21) will become easier to be satisfied and put less constraints on the learning rate sequence.
Platform. Dataset. We evaluate our method for image classification tasks on CIFAR10 and CIFAR100 dataset (Krizhevsky, 2009), which consists of 50,000 training images and 10,000 validation images in 10 and 100 classes respectively. Each worker machine is assigned with a partition which will be randomly shuffled after every epoch.
We choose to train deep neural networks VGG-16 (Simonyan & Zisserman, 2014) and ResNet-50 (He et al., 2016) from scratch 3 . These two neural networks have different architectures and parameter sizes, thus resulting in different performance of periodic-averaging. As shown in Figure 8, for VGG-16, the communication time is about 4 times higher than the computation time. Thus, compared to ResNet-50, it requires a larger τ in order to reduce the runtime-per-iteration and achieve fast convergence. Similar high communication/computation ratio is common in literature, see (Lin et al., 2018;Harlap et al., 2018).
Hyperparameter Choice. Mini-batch size on each worker is 128. Therefore, the total mini-batch size per iteration is 512. The initial learning rates for VGG-16 and ResNet-50 are 0.2 and 0.4 respectively. The weight decay for both networks is 0.0005. In the variable learning rate setting, we decay the learning rate by 10 after 80 th /120 th /160 th /200 th epochs. We set the time interval length T 0 as 60 seconds (about 10 epochs for the initial communication period).
Metrics. We compare the performance of proposed adaptive 3 The implementations of VGG-16 and ResNet-50 follow this GitHub repository: https://github.com/meliketoy/ wide-resnet.pytorch communication scheme with following methods with a fixed communication period: (1) Baseline: fully synchronous SGD (τ = 1); (2) Extreme high throughput case where τ = 100; (3) Manually tuned case where a moderate value of τ is selected after trial runs with different communication periods. Instead of training for a fixed number of epochs, we train all methods for sufficiently long time to convergence and compare the training loss and test accuracy, both of which are recorded after every 100 iterations.
We first validate the effectiveness of ADACOMM which uses the communication period update rule (18) combined with (20) on original PASGD without momentum.
Figure 9 presents the results for VGG-16 for both fixed and variable learning rates. A large communication period τ initially results in a rapid drop in the error, but the error finally converges to higher floor. By adapting τ , the proposed ADACOMM scheme strikes the best error-runtime trade-off in all settings. In Figure 9a, while fully synchronous SGD takes 33.5 minutes to reach 4 × 10 -3 training loss, ADA-COMM costs 15.5 minutes achieving more than 2× speedup. Similarly, in Figure 9b, ADACOMM takes 11.5 minutes to reach 4.5 × 10 -2 training loss achieving 3.3× speedup over fully synchronous SGD (38.0 minutes).
However, for ResNet-50, the communication overhead is no longer the bottleneck. For fixed communication period, the negative effect of performing local updates becomes more obvious and cancels the benefit of low communication delay (see Figures 10b and10c). It is not surprising to see fully synchronous SGD is nearly the best one in the error-runtime plot among all fixed-τ methods. Even in this extreme case, adaptive communication can still have a competitive performance. When combined with learning rate decay, the adaptive scheme is about 1.3 times faster than fully synchronous SGD (see Figure 10a, 15.0 versus 21.5 minutes to achieve 3 × 10 -2 training loss).
Table 1 lists the test accuracies in different settings; we report the best accuracy within a time budget for each setting. The results show that adaptive communication method have better generalization than fully synchronous SGD. In the variable learning rate case, the adaptive method even gives the better test accuracy than PASGD with the best fixed τ .
The adaptive communication scheme is proposed based on the joint error-runtime analysis for PASGD without momentum. However, it can also be extended to other SGD variants, and in this subsection, we show that the proposed method works well for SGD with momentum.
Before presenting the empirical results, we describe how to introduce momentum in PASGD. A naive way is to apply the momentum independently to each local model, where each worker maintains an independent momentum buffer, which is the latest change in the parameter vector x. However, this does not account for the potential dramatic change in x at each averaging step. When local models are synchronized, the local momentum buffer will contain the update steps before averaging, resulting in a large momentum term in the first SGD step of the each local update period. When τ is large, this large momentum term can side-track the SGD descent direction resulting in slower convergence.
To address this issue, a block momentum scheme was proposed in (Chen & Huo, 2016) and applied to speech recognition tasks. The basic idea is to treat the local updates in each communication period as one big gradient step between two synchronized models, and to introduce a global momentum for this big accumulated step. The update rule can be written as follows in terms of the momentum u j :
where
jτ +k ) represents the accumulated gradients in the j th local update period and β glob denotes the global momentum factor. Moreover, workers can also conduct momentum SGD on local models, but their local momentum buffer will be cleared at the beginning of each local update period. That is, we restart momentum SGD on local models after every averaging step. The same strategy was also suggested in Microsoft's CNTK framework (Seide & Agarwal, 2016). In our experiments, we set the global momentum factor as 0.3 and local momentum factor as 0.9 following (Lin et al., 2018). In the fully synchronous case, there is no need to introduce the block momentum and we simply follow the common practice setting the momentum factor as 0.9.
In Figure 11, we apply our adaptive communication strategy in PASGD with block momentum and observe significant performance gain on CIFAR10/100. In particular, the adaptive communication scheme has the fastest convergence rate with respect to wall-clock time in the whole training process. While fully synchronous SGD gets stuck with a plateau before the first learning rate decay, the training loss of adaptive method continuously decreases until converging.
For VGG-16 in Figure 11b, ADACOMM is 3.5× faster (in terms of wall-clock time) than fully synchronous SGD in reaching a 3 × 10 -3 training loss. For ResNet-50 in Figure 11a, ADACOMM takes 15.8 minutes to get 2 × 10 -2 training loss which is 2 times faster than fully synchronous SGD (32.6 minutes).
The design of communication-efficient SGD algorithms that are robust to system variability is vital to scaling machine learning training to resource-limited computing nodes. This paper is one of the first to analyze the convergence of error with respect to wall-clock time instead of number of iterations by accounting for the effect of computation and communication delays on the runtime per iteration. We present a theoretical analysis of the error-runtime trade-off for periodic-averaging SGD (PASGD), where each node performs local updates and their models are averaged after every τ iterations. Based on the joint error-runtime analysis, we design the first (to the best of our knowledge) adaptive communication strategy called ADACOMM for distributed deep learning. Experimental results using VGGNet and ResNet show that the proposed method can achieve up to a 3× improvement in runtime, while achieving the same error floor as fully synchronous SGD.
Going beyond periodic-averaging SGD, our idea of adapting frequency of averaging distributed SGD updates can be easily extended to other SGD frameworks including elasticaveraging (Zhang et al., 2015), decentralized SGD (e.g., adapting network sparsity) (Lian et al., 2017) and parameter server-based training (e.g., adapting asynchrony).
In the 8 worker case, the communication among nodes is accomplished via Nvidia Collective Communication Library (NCCL). The mini-batch size on each node is 64. The initial learning rate is set as 0.2 for both VGG-16 and ResNet-50. In Figure 12a, while fully synchronous SGD takes 17.5 minutes to reach 10 -2 training loss, ADACOMM only costs 6.0 minutes achieving about 2.9× speedup.
It is worth noting there is an interesting phenomenon about the convergence of periodic averaging SGD (PASGD). When the learning rate is fixed, PASGD with fine-tuned communication period has better test accuracy than both fully synchronous SGD and the adaptive method, while its training loss remains higher than the latter two methods (see Figure 9, Figure 10).
In particular, on CIFAR100 dataset, we observe about 5% improvement in test accuracy when τ = 5. To investigate this phenomenon, we evaluate the test accuracy for PASGD (τ = 15) in two frequencies: 1) every 135 iterations; 2) every 100 iterations. In the former case, the test accuracy is reported just after the averaging step. However, in the latter case, the test accuracy can come from either the synchronized/averaged model or local models, since 100 cannot be divided by 15.
From Figure 14, it is clear that local model's accuracy is much lower than the synchronized model, even when the algorithm has converged. Thus, we conjecture that the improvement of test accuracy only happens on the synchronized model. That is, after averaging, the test accuracy will undergo a rapid increase but it decreases again in the following local steps due to noise in stochastic gradients. Such behavior may depend on the geometric structure of the loss surface of specific neural networks.
The observation also reveals that the local updates are inefficient as they reduces the accuracy and makes no progress. In this sense, it is necessary for PASGD to reduce the gradient variance by either decaying learning rate or decaying communication period.
The convergence analysis is conducted under the following assumptions, which are similar to the assumptions made in previous work on the analysis of PASGD (Zhou & Cong, 2017;Yu et al., 2018;Wang & Joshi, 2018;Stich, 2018).
In particular, we make no assumptions convexity of the objective function. We also remove the uniform bound assumption for the norm of stochastic gradients. Assumption 1 (Lipschitz smooth & lower bound on F ). The objective function F (x) is differentiable and L-Lipschitz smooth, i.e., ∇F (x) -∇F (y) ≤ L xy . The function value is bounded below by a scalar F inf .
Assumption 2 (Unbiased estimation). The stochastic gradient evaluated on a mini-batch ξ is an unbiased estimator of the full batch gradient E ξ|x [g(x)] = ∇F (x). Assumption 3 (Bounded variance). The variance of stochastic gradient evaluated on a mini-batch ξ is bounded as
where β and σ 2 are non-negative constants and in inverse proportion to the mini-batch size.
Firstly, let us recall the error-analysis of PASGD. We adapt the theorem from (Wang & Joshi, 2018).
Lemma 1 (Error-Convergence of PASGD (Wang & Joshi, 2018)). For PASGD, under Assumptions 1 to 3, if the learning rate satisfies ηL + η 2 L 2 τ (τ -1) ≤ 1 and all workers are initialized at the same point x 1 , then after K iterations, we have
where L is the Lipschtiz constant of the objective function, σ 2 is the variance bound of mini-batch stochastic gradients and x k denotes the averaged model at the k th iteration.
From the runtime analysis in Section 2, we know that the expected runtime per iteration of PASGD is
Accordingly, the total wall-clock time of training K iteration is
Then, directly substituting K = T /E[T P-Avg ] in (26), we complete the proof.
Taking the derivative of the upper bound ( 14) with respect to the communication period, we obtain
When the derivative equals to zero, the communication period is
Since the second derivative of ( 14) is 4
then the optimal value obtained in (30) must be a global minimum.
In order to faciliate the analysis, we would like to first introduce some useful notations. Define matrices X k , G k ∈ R d×m that concatenate all local models and gradients:
Besides, define matrix J = 11 /(1 1) where 1 denotes the column vector [1, 1, . . . , 1] . Unless otherwise stated, 1 is a size m column vector, and the matrix J and identity matrix I are of size m × m, where m is the number of workers.
Let us first focus on the j-th local update period, where j ∈ {0, 1, . . . , R}. Without loss of generality, suppose the local index of the j th local update period starts from 1 and ends with τ j . Then, for the k-th local step in the interested period, we have the following lemma.
Lemma 2 (Lemma 1 in (Wang & Joshi, 2018)). For PASGD, under Assumptions 1 to 3, at the k-th iteration, we have the following bound for the objective value:
where x k denotes the averaged model at the k th iteration.
Taking the total expectation and summing over all iterates in the j-th local update period, we can obtain
Next, we are going to provide an upper bound for the last term in (35). Note that
where (39) follows the fact that all workers start from the same point at the beginning of each local update period, i.e., X 1 (I -J) = 0. Accordingly, we have
where the inequality (41) is due to the operator norm of (I-J) is less than 1. Furthermore, using the fact (a+b) 2 ≤ 2a 2 +2b 2 , one can get
For the first term T 1 , since the stochastic gradients are unbiased, all cross terms are zero. Thus, combining with Assumption 3, we have
For the second term in (43), directly applying Jensen's inequality, we get
Substituting the bounds of T 1 and T 2 into (43),
Recall the upper bound (35), we further derive the following bound: 2 F [2β(τ j -1) + τ j (τ j -1)] + η 2 j mσ 2 τ j (τ j -1).
(54)
Note that when the learning rate satisfies:
we have
Adaptive Communication Strategies to Achieve the Best Error-Runtime Trade-off in Local-Update SGD Suppose l j = j-1 r=0 τ r + 1 is the first index in the j-th local update period. Without loss of generality, we substitute the local index by global index:
E ∇F (x lj +k-1 ) 2 + η 2 j Lσ 2 τ j 2m + η 3 j L 2 σ 2 τ j (τ j -1) 2 .
(59)
Summing over all local periods from j = 0 to j = R, one can obtain
η 3 j τ j (τ j -1).
(60)
After minor rearranging, it is easy to see In order to let the upper bound (62) converges to zero as R → ∞, a sufficient condition is
Here, we complete the proof of Theorem 3.
We can obtain a simplified result when the learning rate is fixed. To be specific, we have
If we choose the total iterations K = R j=0 τ j , then
Note that in the error analysis, the subscripts of communication period and learning rate represent the index of local update periods rather than the index of the T0-length wall-clock time intervals as considered in Sections 4.1-4.3.