Asynchronous distributed gradient descent algorithms for training of deep neural
 networks are usually considered as inefficient, mainly because of the Gradient delay
 problem. In this paper, we propose a novel asynchronous distributed algorithm
 that tackles this limitation by well-thought-out averaging of model updates, computed
 by workers. The algorithm allows computing gradients along the process
 of gradient merge, thus, reducing or even completely eliminating worker idle time
 due to communication overhead, which is a pitfall of existing asynchronous methods.
 We provide theoretical analysis of the proposed asynchronous algorithm,
 and show its regret bounds. According to our analysis, the crucial parameter for
 keeping high convergence rate is the maximal discrepancy between local parameter
 vectors of any pair of workers. As long as it is kept relatively small, the
 convergence rate of the algorithm is shown to be the same as the one of a sequential
 online learning. Furthermore, in our algorithm, this discrepancy is bounded
 by an expression that involves the staleness parameter of the algorithm, and is
 independent on the number of workers. This is the main differentiator between
 our approach and other solutions, such as Elastic Asynchronous SGD or Downpour
 SGD, in which that maximal discrepancy is bounded by an expression that
 depends on the number of workers, due to gradient delay problem. To demonstrate
 effectiveness of our approach, we conduct a series of experiments on image
 classification task on a cluster with 4 machines, equipped with a commodity communication
 switch and with a single GPU card per machine. Our experiments
 show a linear scaling on 4-machine cluster without sacrificing the test accuracy,
 while eliminating almost completely worker idle time. Since our method allows
 using commodity communication switch, it paves a way for large scale distributed
 training performed on commodity clusters. Distributed training of deep learning models is devised to reduce training time of the models. Synchronous distributed SGD methods, such as BID0 and BID7 , perform training using mini-batch size of several dozens of thousands of images. However, they either require expensive communication switch for fast gradient sharing between workers or, otherwise, introduce a high communication overhead during gradient merge, where workers are idle waiting for communicating gradients over communication switch.Distributed asynchronous SGD methods reduce the communication overhead on one hand, but usually introduce gradient delay problem on the other hand, as described in BID0 . Indeed, usually in an asynchronous distributed approach, a worker w obtains a copy of the central model, computes a gradient on this model and merges this gradient back into the central model. Note, however, that since the worker obtained the copy of the central model till it merges its gradient back into the central model, other workers could have merged their gradients into the central model. Thus, when the worker w merges its gradient into a central model, that model may have been updated and, thus, the gradient of the worker w is delayed, leading to gradient delay problem. We will refer to algorithms that suffer from gradient delay problem as gradient delay algorithms, e.g. Downpour SGD BID1 .As our analysis reveals in Section 3, the quantity that controls the convergence rate of an asynchronous distributed algorithm, is maximal pairwise distance -the maximal distance between local models of any pair of workers at any iteration. Usually gradient delay algorithms do not limit this distance and it may depend on the number of asynchronous workers, which may be large in large clusters. This may explain their poor scalability, convergence rate and struggle to reach as high test accuracy as in synchronous SGD algorithms, as experimentally shown in BID0 .While Elastic Averaging SGD Zhang et al. (2015) is also a gradient delay algorithm, it introduces a penalty for workers, whose models diverge too far from the central model. This, in turn , helps to reduce the maximal pairwise distance between local models of workers and, thus, leads to better scalability and convergence rate. In contrast, our analysis introduces staleness parameter that directly controls the maximal pair distance of the asynchronous workers.Our analysis builds on the work of BID10 , who studied convergence rate of gradient delay algorithms, when the maximum delay is bounded. They provided analysis for Lipschitz continuous losses, strongly convex and smooth losses. While they show that bounding staleness can improve convergence rate of a gradient delay algorithm, in their algorithm each worker computes exactly one gradient and is idle, waiting to merge the gradient with PS model and download the updated PS model back to the worker.The main contributions of this paper are the following. We present and analyze a new asynchronous distributed SGD method that both reduces idle time and eliminates gradient delay problem. Our main theoretic result shows that an asynchronous distributed SGD algorithm can achieve convergence rate as good as in sequential online learning. We support this theoretic result by conducting experiments that show that on a cluster with up to 4 machines, with a single GPU per machine and a commodity communication switch, our asynchronous method achieves linear scalability without degradation of the test accuracy. We presented a new asynchronous distributed SGD method. We show empirically that it reduces both idle time and gradient delay. We analyze the synchronous part of the algorithm, and show theoretical regret bounds.The proposed method shows promising results on distributed training of deep neural networks. We show that our method eliminates waiting times, which allows significant improvements in run time, compared to fully synchronous setup. The very fact of efficient hiding of communication overhead opens opportunity for distributed training over commodity clusters. Furthermore, the experiments show linear scaling of training time from 1 to 4 GPU's without compromising the final test accuracy.Proof. We start with RHS of (8) DISPLAYFORM0 By the definition of average parameter vector (1), the first summand in RHS of (29) equals x iβ+t , while the last two summands cancel each other.Proof of Lemma 3.3.Proof. At iteration (i − 1)β after reset operation FORMULA7 , workers w and w start updating their local parameter vectors for β iterations, so that at the end of the cycle before the reset operation (7), DISPLAYFORM1 The reset operation FORMULA7 at iteration iβ adds the updates of workers w and w , computed at iterations (i − 1)β + 1, . . . , iβ, to the common copy of PS model, so that x (i−1)β,w − x (i−1)β,w = 0. Thus, after the reset operation DISPLAYFORM2 Finally, from (31), our assumption on the size of the gradient ∇f t (x) and from decreasing learning rate, during this cycle that started at iteration (i − 1)β, the distance between workers w and w grows at most by DISPLAYFORM3 Proof of Lemma 3.4.Proof. We decompose our progress as follows DISPLAYFORM4 To prove (33) from (32), we used (12) Dividing both sides by η iτ +t and moving < x iτ +t − x * ,g iτ +t > to the LHS completes the proof.Proof of Theorem 3.5.Proof. First we state a useful inequality: For n vectors a i , i = 1, . . . , n (by induction on n): DISPLAYFORM5 Also we will use the following sum bounds: DISPLAYFORM6 and DISPLAYFORM7 We start with summing (13) along iterations: DISPLAYFORM8 Next, we borrow the derivation of expressions (38) and (39) from the proof of Theorem 2, BID9 . Note, however, that we added a new term to (37) -the last term that is specific to Algorithm 2. This term does not appear in the proof of Theorem 2, BID9 . By the Lipschitz property of gradients and the definition of η t , we can bound the first summand of the above regret expression via DISPLAYFORM9 Also DISPLAYFORM10 We omit the negative factor − DISPLAYFORM11 . Now we start the analysis of the last term in (37), which is new and specific to Algorithm 2. Using (34), we bound the last summand of (37) DISPLAYFORM12 Substituting FORMULA3 , FORMULA3 and FORMULA4 into FORMULA3 , we get DISPLAYFORM13 We use (14) in the above expression DISPLAYFORM14 Now, note that the last summand in (50) corresponds to the summand in (18) for k = j − 1. This completes the proof.Proof of Lemma 3.7.Proof. First note that from (19) it follows that η t βH ≤ 0.1 .Since η i shrinks down, as i grows up, and η t H + 1 > 1, (18) yields ||x iβ+j,w − x iβ+j,w || ≤ (η iβ H + 1) β · ||x iβ,w − x iβ,w || + η iβ β−1 k=0 ||e iβ+k,w − e iβ+k,w || .After the expansion of (η iβ H + 1) β in (52) into Taylor sequence and applying a simple algebra DISPLAYFORM15 From FORMULA1 we can bound DISPLAYFORM16 Assigning FORMULA4 into FORMULA2 , ||x iβ+j,w − x iβ+j,w || ≤ 1.2 · ||x iβ,w − x iβ,w || + 1.2 · η iβ β−1 k=0 ||e iβ+k,w − e iβ+k,w || .Since e iτ +k,w and e iτ +k,w are i.i.d. with mean 0, E||e iβ+k,w − e iβ+k,w || = var(e iβ+k,w − e iβ+k,w ) = 2var(e iβ+k,w ) .Taking expectation of the both sides of (55), substituting (56) into the resulting inequality and using the assumption on variance of random variables e t,w , we complete the proof.Proof of Lemma 3.8.Proof. From Lemma 3.3, ||x i0β,w − x i0β,w || ≤ 2Lτ η (i0−1)β .From FORMULA2 , each cycle j after iteration i 0 β, reduces the distance between w and w by factor of 0.2, while adding to the distance the value of 1.2 · η iβ+j τ s. This means that after the number of cycles j 0 j 0 = log 1.2 · η i0β τ s 2Lτ η (i0−1)β = log s L , for any i ≥ i 0 + j 0 , the first summand in (22) gets bounded by 0.8 · η iβ τ s.Proof of Theorem 3.9.Proof. To prove this theorem , we follow the proof of Theorem 3.5 and develop an alternative bound on ||x t,w − x t || in (42).We will split the sum in (40) into two ranges of t: t < t 0 + j 0 β and t ≥ t 0 + j 0 β for t 0 , j 0 , defined in FORMULA1 and FORMULA2 respectively. To simplify notation, from (23), we can assume that j 0 is a constant and we can assume that t 0 + j 0 ≤ 2t 0 . For t < 2t 0 , we use (48) to show 2t0−1 t=1 ||x t − x * || · ||g t −g t || ≤ 2τ F LH(2τ + 2σ DISPLAYFORM17 For t ≥ 2t 0 , we first observe DISPLAYFORM18 Next we use (24) to bound the above expression.E||x t,w − x t || ≤ 2η t−τ τ s .Substituting this bound into (42), we get E||g t −g t || ≤ 2Hη t−τ τ s .Using FORMULA1 Combining FORMULA5 and FORMULA2 in FORMULA4 and using the definition (19) of t 0 DISPLAYFORM19 Using the assumption (25), and substituting into (41) we prove (26). Finally we use value σ = F L to prove (27).
A method for an efficient asynchronous distributed training of deep learning models along with theoretical regret bounds. The paper proposes an algorithm to restrict the staleness in asynchronous SGD and provides theoretical analysis Proposes a hybrid-algorithm to eliminate the gradient delay of asynchronous methods.