{'fraction_non_alphanumeric': 0.04483821263482281, 'fraction_numerical': 0.019915254237288134, 'mean_word_length': 4.094387755102041, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A Distributed Hierarchical SGD Algorithm with Sparse Global Reduction

Reducing communication overhead is a big challenge for large-scale distributed training. To address this issue, we present a hierarchical averaging stochastic gradient descent (Hier-AVG) algorithm that reduces global reductions (averaging) by employing less costly local reductions. As a very general type of parallel SGD, Hier-AVG can reproduce several commonly adopted synchronous parallel SGD variants by adjusting its parameters. We establish standard convergence results of Hier-AVG for non-convex smooth optimization problems. Under the non-asymptotic scenario, we show that Hier-AVG with less frequent global averaging can sometimes have faster training speed. In addition, we show that more frequent local averaging with more participants involved can lead to faster training convergence. By comparing Hier-AVG with another distributed training algorithm K-AVG, we show that through deploying local averaging with less global averaging Hier-AVG can still achieve comparable training speed while constantly get better test accuracy. As a result, local averaging can serve as an alternative remedy to effectively reduce communication overhead when the number of learners is large. We test Hier-AVG with several state-of-the-art deep neural nets on CIFAR-10 to validate our analysis. Further experiments to compare Hier-AVG with K-AVG on ImageNet-1K also show Hier-AVG's superiority over K-AVG.


Introduction
Since current deep learning applications such as video action recognition and speech recognition with large inputs can take days even weeks to train on a single GPU, efficient parallelization at scale is critical to accelerating training of such longtime running machine learning applications.
Instead of using the classical stochastic gradient descent (SGD) algorithm originated from Robbins and Monro [1951] as a solver, a number of parallel and distributed stochastic gradient descent algorithms have been proposed during the past decade (e.g., see Zinkevich et al. [2010], Recht et al. [2011], Dean et al. [2012], Dekel et al. [2012]). The first synchronous parallel SGD Zinkevich et al.
[2010] is a naive parallelization of the sequential SGD algorithm. Global reductions (averaging) after each local SGD step can incur costly communication overhead when the number of learners is large. The scaling of synchronous SGD is fundamentally limited by the batch size. Asynchronous SGD (ASGD) algorithms such as Recht et al. [2011], Dean et al. [2012], Dekel et al. [2012] have recently been popular used for training deep-learning applications. With ASGD, each learner independently computes gradients for their data samples, and updates asynchronously relative to other learners (hence the name ASGD) the parameters maintained at the parameter server (e.g., see Dean et al. [2012], Li et al. [2014]). ASGD algorithms face their own challenges when the number of learners is large. A single parameter server oftentimes does not serve the aggregation requests fast enough. On the other hand, a sharded server though alleviates the aggregation bottleneck but introduces inconsistencies for parameters distributed on multiple shards. It is also challenging for ASGD implementations to manage the staleness of gradients which is proprotional to the number of learners Li et al. [2014].
Many recent studies adopt new variants of synchronous parallel SGD algorithms (see Hazan and Kale [2014], Johnson and Zhang [2013], Smith et al. [2016], , Loshchilov and Hutter [2016], Chen et al. [2016], , Zhou and Cong [2018]). Zhou and Cong [2018] analyzed a K step averaging SGD (K-AVG) algorithm, and their analysis shows that synchrnous parallel SGD with less frequent global averaging can sometimes provide faster traning speed and can constantly result in better test accuracies. Since then a number of variants of K-AVG have been proposed and studied, see Lin et al. [2018], Wang and Joshi [2018] and references therein.
Although K-AVG demonstrates better scaling behavior than ASGD implementations, for a very large number of learners the optimal K for K-AVG may not be large enough to be amortized by the local computation steps, and the cost of global reduction can be high. We propose a new generic distributed, hierarchical averaging SGD algorithm (Hier-AVG) which can reproduce several popular parallel SGD variants by adjusting its parameters. As Hier-AVG is bulk-synchronous, it allows for sparse gradient averaging among learners to effectively minimize the communication overhead just like K-AVG. Instead of using a parameter server, the learners in Hier-AVG communicate their learned gradients with each other at regular intervals through global reductions. The staleness of gradients which can result in divergence of ASGD methods, can be precisely controlled in Hier-AVG. Meanwhile, it maps well to current and future large distributed platforms where a single node typically employ multiple GPUs. Hier-AVG intersperse global averaging with local ones to manage the staleness of gradients and utilize the natural communtication hierarchy in the distributed platforms effectively.
The main contributions of the study are as follows: • In section 3.2, we derive generic non-asymptotic upper bounds on the expected average squared gradient norms for Hier-AVG. These bounds are in a more general form of the classical results for other synchronous parallel SGD variants such as K-AVG. Then we prove its convergence under deminishing step size schedule.
• In section 3.3, we analytically show that Hier-AVG with less frequent global averaging can sometimes have faster convergence for training under the non-asymptotic scenario.
• In section 3.4, we show that the training speed of Hier-AVG can be improved by deploying more frequent local averaging with more participants.
• In section 3.5, we compare Hier-AVG with K-AVG and show that local averaging can be used to reduce global averaging frequency (e.g., by half) without deterioating traning speed and test accuracy.
The experimental results that validate our analysis are shown in section 4 on various popular deep neural nets. To sum up, our analysis and experiments suggest that Hier-AVG with local averaging deployed can use sparser global reduction, which sheds light on an alternative way to effectively reduce communication overhead without deterioating training speed, and oftentimes provide better test accuracy.

Preliminaries and Notations
In this section, we introduce some standard assumptions used in the analysis of non-convex optimization algorithms and key notations frequently used throughout this paper. We use · 2 to denote the 2 norm of a vector in R d ; · to denote the general inner product in R d . For the key parameters we use: • P denotes the total number of learners for global averaging.
• S denotes the number of learners in a local node for local averaging; we further assume that S|P and S ≥ 1.
• K 2 denotes the length of global averaging interval; • K 1 denotes the length of local averaging interval and 1 ≤ K 1 ≤ K 2 .
• B n or B denotes the size of mini-batch for the n-th global update; • γ n or γ denotes the learning rate (step size) for the n-th global update; • ξ j k,s with j = 1, ..., P , k = 1, ..., K 2 , and s = 1, ..., B. are i.i.d. realizations of a random variable ξ generated by the algorithm by different learners and in different iterations.
We study the following optimization problem: where objective function F : R d → R is continuously differentiable but not necessarily convex over X , and X ⊂ R d is a non-empty open subset. Since our analysis is in a very general setting, F can be understood as both the expected risk F (w) = Ef (w; ξ) or the empirical risk F (w) = n −1 n i=1 f i (w). The following assumptions (see Bottou et al. [2018]) are standard to analyze such problems.
Assumption 1. The objective function F : R d → R is continuously differentiable and the gradient function of F is Lipschitz continuous with Lipschitz constant L > 0, i.e.
This assumption is essential to convergence analysis of our algorithm as well as most gradient based ones. Under such an assumption, the gradient of F serves as a good indicator for how far to move to decrease F .
Assumption 2. The sequence of iterates {w j } is contained in an open set over which F is bounded below by a scalar F * .
Assumption 2 requires that objective function to be bounded from below, which guarantees the problem we study is well defined.
Assumption 3. For any fixed parameter w, the stochastic gradient ∇F (w; ξ) is an unbiased estimator of the true gradient corresponding to the parameter w, namely, One should notice that the unbiasedness assumption here can be replaced by a weaker version which is called the First Limit Assumption (see Bottou et al. [2018]) that can still be applied to our analysis. For simplicity, we just assume that the stochastic gradient is an unbiased estimator of the true one.
Assumption 4. There exist scalars M ≥ 0 such that, Assumption 4 characterizes the variance (second order moments) of the stochastic gradients.

Main Results
In this section, firstly we present Hier-AVG as Algorithm 1. Hier-AVG works as follows: each local worker individually runs K 1 steps of SGD; then each group of S workers locally average and synchronize their updated parameter; after a total count of K 2 SGD steps were run by each worker, all P workers globally average and synchronize their parameters and repeat this cycle until convergence. Then we establish the standard convergence results of Hier-AVG and analyze the impact of K 2 , S and K 1 on convergence. Finally, we compare Hier-AVG with K-AVG and show that local averaging can be used to reduce global averaging frequency to achieve communication overhead reduction without deterioating traning speed.

Hier-AVG Algorithm
Assume that K 2 = K 1 * β with β ≥ 1. For simplicity of analysis and presentation, we assume that β is an integer, which means that the length of global averaging interval is multiple of the length of the local one. In practice, it can be implemented at the practitioner's will rather than using β as an integer. The performance and results should be consistent with our analysis in this work.
One should notice that Algorithm 1 is a very general synchronous parallel SGD algorithm. By setting different values of K 2 , K 1 and S, it can reproduce various commonly adopted SGD variants.
Algorithm 1: Hierarchical Averaging Stochastic Gradient Descent Algorithm initialize the global parameter w 1 ; for n = 1, ..., N (global averaging) do Processor P j , j = 1, . . . , P do concurrently: Synchronize the parameter on each local learner w j n = w n ; for b = 0, ..., β − 1 (local averaging) do for k = 1, ..., K 1 (local SGD) do randomly sample a mini-batch of size B n and update: ∇F (w j n+b * K 1 +k−1 ; ξ j n+b * K 1 +k,s ) end Locally average and synchronize the parameters of each worker P jt within each local cluster: end Globally average and synchronize w n+1 = 1 P P j=1 w j n+β * K 1 ; end

On the Convergence of Hier-AVG
In the following theorem, we prove a non-asymptotic upper bound on the expected average squared gradient norms under constant step size and batch size setting, which serves as a cornerstone of our analysis. Bound under such a setting is very meaningful to analyze the convergence behavior in real world applications. Since in practice models are typically trained with only finite many samples, and step size is set as constants during each interation phase on large distributed plantforms.
The proof of Theorem 3.1 can be found in section 5.1. Expected (weighted) average squared gradient norms is used as a typical metric to show convergence for nonconvex optimization problems, see Ghadimi and Lan [2013]. This bound is generic and one can use it to derive classical bounds for different synchronous parallel SGD algorithms by plugging in specific values of K 2 , K 1 and S.
For example, by plugging in K 1 = 1 and S = 1 (or simply K 2 = K 1 , in both cases, K 2 is K in K-AVG), (3.2) reproduce the same bound for K-AVG as in Zhou and Cong [2018].
As we can see, by scheduling only a constant step size, it converges to some nonzero constant as N → ∞. To make it converge to zero, diminishing step size schedule is needed. Take a closer look at bound (3.2), the second is scaled by P , which shows the effectiveness of parallelization.
The impacts of local averaging size S, length of local averaging interval K 1 , and length of global averaging interval K 2 are more complicated. We will have a more detailed discussion in later sections.
In the following theorem, we prove that by scheduling diminishing step size and/or dynamic batch sizes, the expected weighted average squared gradient norms converges to zero.
Theorem 3.2 (diminishing step size and dynamic batch size). Assume that Algorithm 1 is run with diminishing step size γ j and growing batch size B j satisfying The proof of Theorem 3.2 can be found in section 5.2. It shows that with a proper diminishing step size schedule, Hier-AVG converges. Meanwhile, (3.5) also indicates that Hier-AVG can use This benefit is also verified for K-AVG, see Zhou and Cong [2018].

Larger Value of K 2 Can Sometimes Lead to Faster Training Speed
In this section, we study the impact of K 2 under a non-asymptotic scenario. To be more specific, we consider a situation where T = N * K 2 is a constant, which means a fixed amount of data is processed or a fixed number of epoches is run. K 2 denotes the length of global averaging interval, or in other words, K 2 controls the frequency of global averaging under such setting. Larger K 2 means less frequent global averaging thus less frequent updates on parameter w.
In the following theorem, we analytically show that under certain condition, larger value of K 2 can make training process converge faster. This is quite counter intuitive. Since one might think that smaller K 2 (or more frequent global averaging equivalently) should lead to better convergence performance. Especially, when K 2 = 1, Hier-AVG is equivalent to sequential SGD with a large mini-batch size. However, it has been shown both analytically and experimentally by Zhou and Theorem 3.3. Let T = N * K 2 be a constant. Suppose that Algorithm 1 is run under the condition of Theorem 3.1 with fixed K 1 and S. If Then Hier-AVG with some K 2 > 1 can have faster training speed than K 2 = 1. To appreciate why, condition (3.6) implies that larger value of F ( w 1 ) − F * requires some K 2 > 1 thus longer delay to minimize the bound in (3.2). The intuition is that if the initial guess is too far away from F * , then less frequent synchronizations can lead to faster convergence for tranining. Less frequent averaging implies higher variance of the stochastic gradient in general. It is quite reasonable to think that if it is still far away from the solution, a stochastic gradient with larger variance may be preferred. As we mentioned in the proof, the optimal value of K * 2 depends on quantities such as L, M , and (F ( w 1 ) − F * ) which are unknown to us in practice. Therefore, to obtain a concrete K * 2 in practice is not so realistic.
Corresponding experimental results to validate our analysis are shown in section 4.1. In that section, we also empirically show that larger K 2 can constantly provide better test accuracies on various models.

Small K 1 and Large S can Acceletate Training
In this section, we study the behavior of two important parameters K 1 and S, which control the frequency and the scope of local averaging respectively. Apparently, smaller K 1 means more frequent local averaging, and larger S means more number of learners involved in local averaging.
In the following theorem, we show that when K 2 is fixed, smaller K 1 and larger S can lead to faster convergence for traning for Hier-AVG. To better understand the impact of local averaging on convergence, we take a closer look at both bounds (3.2) and (3.4). Both S and K 1 appear in the third term on the right hand side. When the first part in the third term is dominant, S acts as a scaling factor in (K 2 − K 1 )(4K 2 + K 1 − 3)/S, which can be understood as local averaging with more participants amortizes the cost introduced by sparse global averaging represented by K 2 ; when the second term is dominant, one can simply set K 1 = 1 to cancel off this term. These shed light on an alternative way to speed up traning by deploying local averaging. Meanwhile, another lesson we learned here is that one can trade less costly local averaging for even sparser global averaging given that sparse global reduction typically provides better test accuracy and communication overhead can be a major concern in one's budget.
We will have a more detailed discussion on this in the next section. The experimental results that validate our analysis are presented in section 4.2.

Using Local Averaging to Reduce Global Averaging Frequency
From last section, a meaningful lesson we learned about Hier-AVG is that we can use more local averaging to speed up convergence in the sacrifice of less costly local communications. In this section, we compare Hier-AVG with K-AVG, and show that Hier-AVG with sparser global reduction by deploying local averaging can achieve comparable traning speed with K-AVG while has less communication cost.
As we mentioned in last section, a natural idea to think about is that when implementing Hier-AVG, we can use more frequent local averaging and less frequent global averaging to balance one's communication budget. In the following theorem, we compare Hier-AVG with K-AVG in a nonasymptotic scenario where K-AVG is run with K and Hier-AVG with K 2 = (1 + a)K (a ∈ (0, 1]) and K 1 = K. Apparently, after processing certain amount of data, Hier-AVG has much less communication cost than K-AVG due to less frequent global averaging involved. We show that by processing the same amount of data, Hier-AVG with local averaging deployed can converge at least as fast as K-AVG while using less frequent global averaging thus less communication cost. As a result, the real run time of training can be effectively reduced when P is large.
Apparently, too big a and/or too small b will make the condition (

Experimental results
In this section, we present experimental results to validate our analysis of Hier-AVG. 4.1 Impact of K 2 on convergence Theorem 3.3 in Section 3.3 shows that the optimal K 2 for convergence is not necessarily 1, and larger K 2 can sometimes lead to faster convergence than a small one. Fig. 1a, 1b, 1c  For ResNet-18 and GoogLeNet, the training accuracies with three different K 2 are similar.
In fact, the best training accuracy for GoogLeNet is achived with K 2 = 32. For MobileNet and VGG19 , the best training accuracies are achieved with K 2 = 8, and the training accuracy with K 2 = 32 is higher than with K 2 = 16. (d) VGG19 Figure 2: Impact of K 2 on convergence: test accuracy obviously it reduces the frequency of costly global reduction when P increases. For example, the best test accuracy for GoogLeNet is achieved with K 2 = 32. In comparison with K 2 = 8, 4 times fewer global reductions are used. As a result, the real run time for training can be effectively reduced due to much less communication overhead.

Impact of K 1 and S on Convergence
In section 3.4, Thorem 3.4 claims that reducing K 1 and increasing S can speed up training convergence. In practice, with a limited budget in terms of the amount of data samples processed (e.g., a fixed number of training epochs), we can adjust K 1 and S to accelerate training. Recall that K 1 and S determine local communication behavior. They provide deterministic means, at least in theory, for practitioners to fine tune training to achieve the best results within their computational resource and time constraint. we show the training loss for K 1 = 4 and 8, and we set K 2 = 32, S = 4, and P = 16. As we can see, for all networks it is clear that a lower training loss is achieved with K 1 = 4 than with K 1 = 8.

Comparison with K-AVG
As we have mentioned, one of the biggest challenges of distributed training is the communication overhead. In K-AVG, K determines the frequency of global reduction. It is shown by Zhou and Cong [2018], from the perspective of convergence, large P may require small K for faster convergence. We explained in section 3.5 that Hier-AVG provides the option to reduce frequency of global reduction by increasing frequency of local reduction. Since modern architectures typically employ multiple GPUs per node, and the intra-node communication bandwidth is much higher than inter-node bandwith, Hier-AVG is a perfect match for such systems.
We evaluate the performance of Hier-AVG by setting K 2 = 2K opt and S = 4, where K opt is the tuned optimal value of K-AVG implementation. The experimental results is summarized in Table   1. We experiment with P = 16, 32, and 64 learners on ResNet-18 . With 16 learners, K opt = 32 for K-AVG. Thus we set K 2 = 64 for Hier-AVG, and experiment with K 1 = 2, 4, and 16. The corespoinding validation accuracies are 94.01%, 94.11%, and 94.08% respectively. They are all higher than the best accuracy achieved by K-AVG at 94.0%. With 32 and 64 learners, K opt = 4 for K-AVG. Setting K 2 = 8 for Hier-AVG, the accuracies achieved can be 93.90% and 93.17% at Alg.

Performance of Hier-AVG on ImageNet
In this section, we further investigate the performance of Hier-AVG with the ImageNet-1K dataset which is much larger than CIFAR-10 and it contains of 1.28 million training images split across 1000 classes, and 50,000 validation images.
During training, a crop of random size (of 0.08 to 1.5) of the original size and a random aspect ratio (of 3/4 to 4/3) of the original aspect ratio is made. This crop is then resized to 224 × 224.
Random color jittering with a ratio of 0.4 to the brightness, contrast and saturation of an image is then applied. Next a random horizontal flip is applied to the input, and the input is then  learners. Clearly, Hier-AVG achieves higher training accuracy than K-AVG since the first epoch.
After the first 5 epochs, Hier-AVG achieved 6% higher training accuracy than K-AVG, and at the 46-th epoch, Hier-AVG achieved 17.33% higher training accuracy than K-AVG. At the 90-th epoch, the training accuracy of Hier-AVG is 1.15% higher than K-AVG. Fig. 5b shows the test accuracies comparison between K-AVG and Hier-AVG with 16 learners.
As we can see, Hier-AVG also achieves higher validation accuracy than K-AVG since the first epoch. At epoch 5, Hier-AVG achieved 12% higher accuracy than K-AVG, and at the 90-th epoch, Hier-AVG achieved 0.51% higher accuracy than K-AVG.

Proof of Theorem 3.1
Proof. We denotew n as the n-th global update in Hier-AVG, denotew j n+kK 1 +t as t-th local update on learner j after k times local averaging. By the algorithm, ∇F (w j n+kK 1 +t ; ξ j kK 1 +t,s ).
By the definition of SGD, the random variables ξ j kK 1 +t,s are i.i.d. for all t = 0, ..., K 1 −1, s = 1, ..., B, j = 1, ..., P and k = 0, ..., β − 1. Consider Note that here we abused the expectation notation E a little bit. Throughout this proof, E always means taking the overall expectation. For each fixed k and t, the random variables ∇F (w j n+kK 1 +t ; ξ j kK 1 +t,s ) are i.i.d. for over all j and s conditioning on previous steps. As a result, we can drop the summation over s and j in (5.2) due to the averaging factors B and P in the dominator. To be more specific, under the unbiasness Assumption 3, by taking the overall expectation we can immediately get for fixed j and t. Next, we show how to get rid of the summation over j. Recall thatw j α+1 = w α − γ B B s=1 ∇F (w α ; ξ j 0,s ). Obviously,w j α+1 , j = 1, ..., P are i.i.d. condiitoning onw α because ξ j 0,s , j = 1, ..., P , s = 1, ..., B are i.i.d. Similarly,w j α+2 =w j α+1 − γ B B s=1 ∇F (w j α+1 ; ξ j 1,s ), j = 1, ..., P are i.i.d. due to the fact thatw j α+t 's are i.i.d., ξ j 1,s 's are i.i.d., andw j α+t 's are independent from ξ j 1,s 's. By induction, one can easily show that for each fixed t,w j α+t , j = 1, ..., P are i.i.d. Thus for We can therefore get rid of the summation over j as well. We will frequently use the above iterative conditional expectation trick in the following analysis.
Next, we will bound (5.2) and (5.3) respectively. For (5.3), we have ∇F (w j n+kK 1 +t ; ξ j kK 1 +t,s ) where in the last equity, we used the fact that for fixed t and k and conditioning on ∇F (w j n+kK 1 +t ), P j=1 B s=1 E ∇F (w j n+kK 1 +t ; ξ j kK 1 +t,s ) − ∇F (w j n+kK 1 +t ) = 0 under unbiasness Assumption 3. Further, under the bounded variance Assumption 4, we have Thus, we get Note that in the first equity we can change the summation over j and s out of the squared norms without introducing an extra P B factor is due to the fact that conditioning onw j n+kK 1 +t , ∇F (w j n+kK 1 +t ; ξ j kK 1 +t,s ) are all independent with respect to different j and s. In the following, we will use this trick over and over again without further explaination.
where we used the Lipschitz Assumption 1 in the last inequality.
In the following lemma, we derive a general bound on E w j n+kK 1 +t − w n 2 2 .
Proof. Obviously, E ∇F (w j n+1 ) 2 2 has the most copies, we will derive an upper bound on the number of E ∇F (w j n+1 ) 2 2 and then use this bound to uniformly bound the number of terms for Following Lemma 2, we get (5.18) Plug (5.18) into (5.4), we have Under the condition, We can therefore drop the second term on the right hand side in (5.20) and take the summation over n to get Under Assumption 2, we have As a result,
On the other hand, g(K 2 ) is monotone decreasing for K 2 ≥ 1. Therefore, B(K 2 ) is a multiplication of an increasing function and a decreasing one. Thus, a sufficient condition for K * 2 > 1 is that B(2) < B(1), which is equivalent to δα 1 − δ > 2β + 12η S .