Title: INEFFICIENCY OF STOCHASTIC GRADIENT DESCENT WITH LARGER MINI-BATCHES (AND MORE LEARNERS)

Abstract: Stochastic Gradient Descent (SGD) and its variants are the most important optimization algorithms used in large scale machine learning. Mini-batch version of stochastic gradient is often used in practice for taking advantage of hardware parallelism. In this work, we analyze the effect of mini-batch size over SGD convergence for the case of general non-convex objective functions. Building on the past analyses, we justify mathematically that there can often be a large difference between the convergence guarantees provided by small and large mini-batches (given each instance processes equal number of training samples), while providing experimental evidence for the same. Going further to distributed settings, we show that an analogous effect holds with popular Asynchronous Gradient Descent (ASGD): there can be a large difference between convergence guarantees with increasing number of learners given that the cumulative number of training samples processed remains the same. Thus there is an inherent (and similar) inefficiency introduced in the convergence behavior when we attempt to take advantage of parallelism, either by increasing mini-batch size or by increase the number of learners.

1. INTRODUCTION:

Stochastic gradient descent (SGD) and its parallel variants form the backbone of most popular deep learning applications. Consequently, there has been a significant interest in investigating their convergence properties. SGD has been shown to satisfy an asymptotic convergence rate of O(1/S) for convex objective functions [Nemirovski et al. (2009) ] and an asymptotic convergence rate of O(1/ √ S) for general non-convex objective functions with mini-batch size 1 in [Ghadimi & Lan (2013) ] or with arbitrary mini-batch sizes in [Dekel et al. (2012) ].

Although SGD converges asymptotically with the same rate irrespective of mini-batch size, it has been reported that for large mini-batch sizes, often it is slower to converge -for example, see Wilson & Martinez (2003) for the detailed graphical illustrations therein for the effect of increasing batchsize or see Bottou (2010) for the comments on the tradeoffs of mini-batching. In this work, we are interested in using theoretical analysis for justifying such practical observations or comments. In particular, we show the following:

• We consider general non-convex objective functions and show that prior to reaching asymptotic regime, SGD convergence could get much slower (inferred from the difference in the convergence rate guarantees from Theorem 2) with using higher mini-batch size, assuming a constant learning rate. Here, to evaluate the convergence rate guarantee we use the measure of average gradient norm since we are considering general non-convex objectives.

As a consequence of slower convergence, the number of training samples required to attain a certain convergence guarantee (in terms of average gradient norm) increases as the mini-batch size increases. We build the analysis based on the framework in Ghadimi & Lan (2013) . • Further, we investigate Asynchronous Stochastic Gradient Descent (ASGD) which is one of the most popular asynchronous variants of SGD [Dean et al. (2012) ; Li et al. (2014a) ; Chilimbi et al. (2014) ]. Recently, Lian et al. (2015) extended the results of SGD convergence to ASGD and showed that it converges asymptotically with a convergence rate of O(1/ √ S). In our analysis we show that prior to the asymptotic regime, with using higher number of learners ASGD convergence could get much slower in terms of average gradient norm attained after cumulatively processing a fixed number of training samples (this slow-down is inferred from the difference in the convergence guarantees from Theorem 4).

• This suggests that there is an inherent limit on harnessing parallelism with SGD either by increasing mini-batch size or increasing the number of learners (even when we do not take into account overheads such as communication cost). The difference in convergence behavior caused by increasing mini-batch size for SGD and by increasing the number of learners with ASGD was found to be similar (See Theorem 2, Theorem 4 and the discussion at the end of Section 4).

For rest of the paper, we use the following notation: Let F (x, z i ) denote a non-convex function of a parameter vector x and a training sample z i selected from the training set {z 1 , z 2 , . . . , z n }.

Our aim is to find a parameter vector that minimizes the objective function

f (x) = E z F (x, z).

Towards this, we use mini-batch SGD, where in k th iteration, we select a random mini-batch z k = {z 1 k , z 2 k , . . . , z M k } of size M and perform the following update:

EQUATION

In the above equation, γ denotes the learning rate and we have

G(x, z k ) = M i=1 G(x, z i k ) where G(x, z i k ) denotes the gradient of the objective function f (x) with respect to a training sample z i k ∈ z k . We define D f := f (x 1 ) -f (x * )

where x 1 is the initial parameter vector and x * is a local optima towards which SGD proceeds. We also denote by S the total number of training samples to be processed.

Additionally, we make the following standard assumptions, see e.g., [Lian et al. (2015) , Ghadimi & Lan (2013) ]:

A.1 Unbiased estimator: We assume that the expectation of G(x, z) equals to the true value of the gradient, i.e., E z G(x, z) = ∇f (x) ∀x.

A.2 Bounded variance::

We assume that there exists a constant σ 2 such that E z ( G(x, z) -∇f (x)

2 ) ≤ σ 2 ∀x.

A.3 Lipschitzian Gradient: We assume f (x) to satisfy Lipschitzian smoothness, i.e., there exists a constant L such that ∇f (x) -∇f (y) ≤ L • x -y ∀x, y.

The paper is organized as follows: Section 2 discussed some related work. We follow it up by analyzing impact of mini-batch size on SGD in Section 3. Later we extend the analysis to ASGD in Section 4. We provide experimental evidence regarding our analysis in Section 5 and conclude by discussing future directions in Section 6.

2. RELATED WORK:

In recent years, there have been several works analyzing convergence properties of SGD and its variants. In Nemirovski et al. (2009) , SGD has been shown to have a convergence rate of O(1/S) for convex objective functions, where S is the number of samples seen, and this rate is in terms of distance of objective function from the optimal value. When the objective cost functions are non-convex, as is the case with most deep learning applications, the rate of convergence of SGD in terms of average gradient norm has been shown to be O(1/ √ S) asymptotically by Ghadimi & Lan (2013) . The results in Dekel et al. (2012) can be interpreted as showing the applicability of this convergence rate also for the mini-batches of size in M , where now S takes form of M K with K being the number of mini-batches processed.

Among the distributed variants of SGD, ASGD has been the most popular variant Dean et al. (2012) ; Li et al. (2014a) ; Chilimbi et al. (2014) . Practically it has been observed that ASGD is often slower to converge with increasing number of learners [Seide et al. (2014) ; Chan & Lane (2014) ; Dean et al. (2012) ]. Although these works did not ignore communication overhead, in Section 4 we investigate the inherent inefficiency in ASGD without communication overhead costs. In Lian et al. (2015) , it was proved that in the asymptotic regime the convergence rate of O(1/ √ S) can be extended to ASGD when the "age" of updates was bounded by the number of learners.

There exist several other sequential and distributed variants of SGD. For example, SGD with variance reduction techniques to mitigate the effects of gradient variance have been discussed in [Johnson & Zhang (2013) ; Xiao & Zhang (2014) ]. SGD with co-ordinate descent/ascent and its distributed variants has been studied in [Hsieh et al. (2008) ; Richtárik & Takác (2013) ; Fercoq et al. (2014) ; Konečnỳ et al. (2014) ; Qu & Richtárik (2014) ; Liu et al. (2015) ; Jaggi et al. (2014) ; Nesterov (2012) ]. The convergence properties of asynchronous stochastic coordinate descent have been analyzed in Liu & Wright (2015) . More recently, the authors in Meng et al. (2016) have studied combining variance reduction techniques, randomized block co-ordinate descent [Richtárik & Takáč (2014) ] and Nesterov acceleration methods [Nesterov (2013) ] and analyzed its theoretical properties.

There have been several recent works which attempt to mitigate the effect of degrading convergence for large mini-batches (e.g., see [Li et al. (2014b) ] where in each mini-batch a regularized objective function is optimized to compute updated parameter vector), or there are works which attempt to select mini-batch dynamically for better performance, for example see [Byrd et al. (2012) ; Tan et al. (2016) ; De et al. (2016) ], or there have been works which attempt to improve SGD performance by intelligent selection of training samples, e.g., [Needell et al. (2014) ; Bouchard et al. (2015) ].

3. THE IMPACT OF MINIBATCH SIZE ON SGD:

In this section, we build on the SGD convergence analysis in Ghadimi & Lan (2013) . In particular, we consider the convergence guarantees from Theorem 2.1 in Ghadimi & Lan (2013) restricted to constant learning rate. However, we first modify their analysis to allow mini-batches of arbitrary sizes. Building on, we show that SGD with smaller mini-batches can have better convergence guarantees than with using larger mini-batches. As a consequence, we observe that for larger mini-batches, a larger number of samples is needed for the convergence rate to fall below a certain threshold. Lemma 1. With mini-batches of size M and a constant learning rate γ, after K iterations of SGD, we have

K k=1 E( ∇f (x k ) 2 ) K ≤ 1 γ -LM γ 2 2 • D f S + Lσ 2 γ 2 2 (2)

Proof outline. Using the property of Lipschitzian gradient, we get

f (x k+1 ) ≤ f (x k ) + ∇f (x k ), x k+1 -x k + L 2 x k+1 -x k 2 = f (x k ) -γ k • ∇f (x k ), M i=1 G(x k , z i k ) + γ 2 k L 2 M i=1 G(x k , z i k ) 2 (3) Let us define δ i k = G(x k , z i k ) -∇f (x k ) and δ k = M i=1 δ i k .

Using it, the above equation can be rewritten as

f (x k+1 ) -f (x k ) ≤ -γ k • ∇f (x k ), δ k + M • ∇f (x k ) + γ 2 k L 2 δ k + M • ∇f (x k ) 2 ⇒ f (x k+1 ) -f (x k ) ≤ -γ k • ∇f (x k ), δ k -M γ k • ∇f (x k ) 2 + γ 2 k L 2 δ k 2 + 2M δ k , ∇f (x k ) + M 2 ∇f (x k ) 2

Rest of the proof involves adding such inequalities over first K -1 updates and bounding the δ k 2 using assumption A.2 and δ k , ∇f (x k ) using assumption A.1 from Section 1. Finally, we use f (x K ) -f (x * ) ≤ D f and rearrange the terms to get the desired bound.

In the following theorem, we justify that given a fixed number of samples S to be processed, SGD with smaller mini-batches SGD can have better convergence guarantees than with using larger minibatches. Note that α used in the theorem statement is a measure of (the square root of) the number of training samples processed.

Theorem 2. Let α := Sσ 2 LD f . Let 4M l ≤ α ≤ M h /4.

Then the convergence guarantee for SGD for mini-batch size M h after processing S training samples can be worse than the convergence guarantee for mini-batch size M l by a factor of 2M h /(α √ 2 + M l ).

Proof outline. For a fixed number S of training samples to be processed, we now minimize the right hand side of Equation 2 to find the best convergence guarantee supported by Lemma 1. Let

γ = c • D f /(SLσ 2 )

, where c is a scalar multiplier. Substituting it in Equation 2 and after some algebraic manipulations, we get

K k=1 E( ∇f (x k ) 2 ) K ≤ 1 c + c 2 1 -cM 2α • D f Lσ 2 S (4)

By applying simple calculus, it can be shown that the value c * of c which minimizes right hand side of the above equation is given by

c * = M α • -1 + 1 + 2α 2 M 2 (5)

In appendix, we show that with M = M l ≤ α/4, we have c * ≈ √ 2 -M l /α and consequently the coefficient of D f Lσ 2 /S from Equation 4evaluates to approximately √ 2 + M l /α. Whereas for M = M h ≥ 4α, we show that in the appendix using that c * = α/M h and the coefficient of D f Lσ 2 /S from Equation 4evaluates to approximately 2M h /α. Combining these observations, we get that the convergence guarantees for M l and M h can differ by a factor of 2M h /(α √ 2 + M l ) after processing S training samples. See the appendix for complete proof.

Note that while it could be possible to show that in general smaller mini-batches converge faster than larger mini-batches in theory, we used 4M l ≤ α ≤ M h /4 in Theorem 2 for the sake of simplicity. Also, although we theoretically justified faster convergence smaller mini-batches in Theorem 2, the exact factors by which bigger mini-batches can be worse can vary in practice. Here our purpose is to give theoretical support to the practical observations of smaller mini-batches being faster. Theorem 3. The number of samples needs to be processed in order for SGD achieve the same convergence guarantee increases as the mini-batch size increases.

Proof. For the same values of γ and S, the value of the bound from Equation 2 becomes worse (i.e., increases) as M increases. This is because for a fixed γ the quantity γ -LM γ 2 /2 must decrease as M increases. Consequently for given S, the best value of convergence guarantee (i.e., smallest average gradient norm) attained by varying γ must become worse (i.e., higher) as M increases. Thus in order to reach the same convergence guarantee, SGD must process more training samples with increasing mini-batch size. Now we will proceed to the next section, where we will show that with ASGD (which is one of the most popular distributed variants of SGD) increasing number of learners can lead to slower convergence given a fixed total number of samples to be processed, and the effect is similar to that of increasing mini-batch size for SGD.

4. ASYNCHRONOUS STOCHASTIC GRADIENT DESCENT:

ASGD typically has a parameter server maintaining the parameters (i.e., the weights in the neural network) and multiple learners. Each learner asynchronously repeats the following:

• Pull: Get the parameters from the server.

• Compute: Compute the gradient with respect to randomly selected mini-batch (i.e., a certain number of samples from the dataset). • Push and update: Communicate the gradient to the server. Server then updates the parameters by subtracting this newly communicated gradient multiplied by the learning rate.

We assume that the update performed by the server is atomic, i.e., the server does not send or receive parameters while it updates the parameters. Now we express k th update step of the ASGD algorithm in terms of our notation. Note that for k th update, the partial gradient computed by a learner can be with respect to an older parameter vector. This is because while computing the partial gradient, the parameter vector could have been updated because of the partial gradients sent in by other learners. Let x k-τ be the parameter vector used by a learner to compute the partial gradient to be used in k th update. Then the equation for k th update of ASGD becomes:

EQUATION

Lian et al. (2015) showed that when the age of the updates τ is bounded by the number of learners N , then ASGD asymptotically converges with a rate of O(1/ √ S) where S is the cumulative number of training samples processed. From Theorem 1 in Lian et al. (2015) , the convergence rate guarantee (expressed in the terms of average gradient norm) for ASGD with N learners after processing K updates becomes

EQUATION

The terms independent of the number of updates K in Equation 7indicate that with a constant learning rate, there is a limit on how close the algorithm can reach to the optimum without lowering the learning rate. Although asymptotically, it can be shown that Equation 7-8 lead to O(1/ √ S) convergence (see Lian et al. (2015) ), we now investigate the convergence behavior prior to such a regime. We have the following theorem about the effect of increasing the number of learners on ASGD convergence guarantee: Theorem 4. Let N > 1 be the number of learners and let α = Kσ 2 M LD f ≤ N , then the optimal ASGD convergence rate guarantee for 1 learner and N learners can differ by a factor of approximately N α .

The proof of above theorem is in the same spirit as that of Theorem 2 and can be found in the appendix. Note that without asynchronous nature of ASGD, the analysis for synchronous distributed SGD would be the same as the analysis for SGD from Section 3. This is because synchronous SGD, where each of the N learners compute the gradient for a random mini-batch of size M , equivalently represents SGD with mini-batch size M N . The asynchronous nature of ASGD introduces extra factors to be taken into account such as the "age" of the updates (i.e., the situation where the gradient returned by a learner may have been computed by an older parameter vector). Theorem 5. For a constant mini-batch size M , the number of samples needs to be processed in order to achieve the same convergence guarantee increases as the number of learners increases.

Proof outline. The range of γ permissible by Equation 8 becomes smaller as N increases. Rest of the proof combines the observations that the minimum attained by the convergence guarantee by Equation 7 must become worse if the range of γ decreases and N increases. For complete proof, please see the appendix.

Discussion: From Theorem 2, for sequential SGD, there could be a difference of 2M h /(α √ 2 + M l ) between the convergence guarantee of mini-batch sizes M l , M h with 4M l ≤ α ≤ M h /4. Assuming M l to be far smaller than α, this factor becomes approximately √ 2M h /α. This is comparable with the difference N/α between ASGD convergence guarantee of 1 learner and N learners. Although exact numerical multipliers may differ depending on the tightness of the original convergence bound, it points to the similarities between slow-down caused by bigger mini-batch sizes with SGD and larger number of learners with ASGD. At a high level, ASGD with higher number of learners (with bounded age/staleness of updates) can be thought of SGD with some effective mini-batch size. This effective mini-batch size could be dependent on the number of learners as well as the age/staleness of updates.

5. EXPERIMENTS:

Experiment setup: We carry our experiments with CIFAR-10 dataset [cif (accessed January 11, 2016a) ] which contains 50, 000 training samples and 10, 000 test samples, each associated with 1 out of 10 possible labels For the CIFAR-10 dataset, our aim is to predict the correct label the input images. For our experiments, we train convolutional neural network shown in Table 1 , which is taken from [cif (accessed January 11, 2016b) ]. It is a fairly standard convolutional network design consisting of a series of convolutional layers interspersed by max-pooling layers. The convolutional layers outputs are filtered with rectified linear unit before applying max-pooling. Additionally, it also uses Dropout layers which act as regularization [Srivastava et al. (2014) ]. At the end, it has a fully connected layer with 10 outputs (equal to the number of labels). The number of parameters to be learned for CIFAR-10 network is ≈ 0.5 million.

We use cross-entropy between the input labels and the predicted labels in the final output layer, i.e., F (x, z) (see Section 1 for the notation) is the cross-entropy error and f (x) is the average crossentropy error over all training samples. The implementation of neural network was done using Torch. The target platform for our experiments is a Magma system with 16 GPUs connected to an IBM Power8 host. In our ASGD Downpour implementation, the learners are run on the GPUs, while the parameter server is run on the CPU. We carried our experiments for 100 epochs, here by an epoch we mean a complete pass of the training data. We chose the learning rate to be 0.01 as it was seen to be performing well at the end of our experiments with respect to test accuracy (i.e., classification accuracy on the test data). For ASGD part of experiments, we randomly partitioned the training data between all N learners in the beginning of each epoch. At the end of each epoch we measured the test accuracy. See Figure 1 for the results of our SGD experiments. We can observe that as the mini-batch size increases, the test error converges slower with respect to the number of epochs. See Figure 2 for the result of our experiments with ASGD experiments. Again, we can observe that as the number of learners increases, the convergence of test error becomes slower.

These observations agree with our justifications from Section 3 and 4. Moreover, they show that there are similarities between the slow-down caused by increasing mini-batch size with SGD and increasing the number of learners with ASGD. Thus, exploiting parallelism, either by increasing mini-batch size or by increasing the number of learners introduces an inherent inefficiency in the convergence behavior, even after disregarding other overheads such as communication time when we increase the number of learners.

6. CONCLUSION AND FUTURE DIRECTIONS:

In this paper, we theoretically justified faster convergence (in terms of average gradient norm attained after processing a fixed number of samples) of SGD with small mini-batches or that of ASGD with smaller number of learners. This indicates that there is an inherent inefficiency in the speed-up obtained with parallelizing gradient descent methods by taking advantage of hardware. It would be interesting to see if such a conclusion holds for more advanced update methods than vanilla SGD, for example methods using momentum and its variants.

A APPENDIX Lemma 1. With mini-batches of size M and a constant learning rate γ, after K iterations of SGD, we have

K k=1 E( ∇f (x k ) 2 ) K ≤ 1 γ -LM γ 2 2 • D f S + Lσ 2 γ 2 2 (2)

Proof. Using the property of Lipschitzian gradient, we get

f (x k+1 ) ≤ f (x k ) + ∇f (x k ), x k+1 -x k + L 2 x k+1 -x k 2 = f (x k ) -γ k • ∇f (x k ), M i=1 G(x k , z i k ) + γ 2 k L 2 M i=1 G(x k , z i k ) 2 (9) Let us define δ i k = G(x k , z i k ) -∇f (x k ) and δ k = M i=1 δ i k .

Using it, the above equation can be rewritten as

f (x k+1 ) -f (x k ) ≤ -γ k • ∇f (x k ), δ k + M • ∇f (x k ) + γ 2 k L 2 δ k + M • ∇f (x k ) 2 ⇒ f (x k+1 ) -f (x k ) ≤ -γ k • ∇f (x k ), δ k -M γ k • ∇f (x k ) 2 + γ 2 k L 2 δ k 2 + 2M δ k , ∇f (x k ) + M 2 ∇f (x k ) 2

Generating such inequalities over K mini-batches and adding them, we get

-D f ≤ f (x K+1 ) -f (x 1 ) ≤ K k=1 -γ k • ∇f (x k ), δ k -M γ k ∇f (x k ) 2 + γ 2 k L 2 δ k 2 + 2M δ k , ∇f (x k ) + M 2 ∇f (x k ) 2

Simple rearrangement of terms gives us

EQUATION

Now we observe that E(

δ k 2 ) = E( M i=1 δ i k 2 ) ≤ M • M i=1 E( δ i k

2 ) ≤ M σ 2 , using Assumption A.2. From the assumption of the stochastic gradient being unbiased estimator of the true gradient (Assumption A.1), we also know that

E( δ k , ∇f (x k ) ) = M i=1 E( δ i k , ∇f (x k ) ) = M i=1 E(δ i k ), ∇f (x k ) = 0.

Taking the expectation of both sides in Equation 10 with respect to randomly selected samples and using these observations we get the following equation:

K k=1 M γ k - LM 2 γ 2 k 2 • E( ∇f (x k ) 2 ) ≤ D f + LM σ 2 2 K k=1 γ 2 k

The above equation is equivalent to Equation 2.11 from Ghadimi & Lan (2013) modified to allow arbitrary mini-batch sizes. Restricting ourselves to allow constant learning rate and after simplifying the above equation, we get

K k=1 E( ∇f (x k ) 2 ) K ≤ 1 γ -LM γ 2 2 • D f S + Lσ 2 γ 2 2 (11) Theorem 2. Let α := Sσ 2 LD f . Let 4M l ≤ α ≤ M h /4.

Then the convergence guarantee for SGD for mini-batch size M h after processing S training samples can be worse than the convergence guarantee for mini-batch size M l by a factor of 2M h /(α √ 2 + M l ).

Proof outline. For a fixed number S of training samples to be processed, we now minimize the right hand side of Equation 2 to find the best convergence guarantee supported by Lemma 1. Let γ = c • D f /(SLσ 2 ), where c is a scalar multiplier. Substituting it in Equation 2 and after some algebraic manipulations, we get

EQUATION

)

By applying simple calculus, it can be shown that the value c * of c which minimizes right hand side of the above equation is given by

c * = M α • -1 + 1 + 2α 2 M 2 (13) • Consider the case of M = M l ≤ α/4. Denote c * by c * l for this case. With M = M l ≤ α/4, we have 1 + 2α 2 /M 2 l ≈ √ 2α/M l . Thus we get c * l ≈ √ 2-M l /α.

Further, we can write the following using M l is little compared to α and other simple known approximations:

EQUATION

EQUATION

Using Equation 14, 15, 16, we get that the coefficient of D f Lσ 2 /S from Equation 12evaluates to approximately √ 2 + M l /α. M LD f ≤ N , then the optimal ASGD convergence rate guarantee for 1 learner and N learners can differ by a factor of approximately N α .

Proof. We have γ = c • D f /(M KLσ 2 ) = c αM L from the definition of α. Substituting this in Equation 7, we get

K k=1 E( ∇f (x k ) 2 ) K ≤ 2D f M Kc • D f M KLσ 2 + σ 2 L • c • D f M KLσ 2 + 2σ 2 L 2 M N • c αM L • c • D f M KLσ 2 = 2 c + c + 2N c 2 α • D f Lσ 2 M K (17)

From the definition of α, we have K = α 2 M LD f /σ 2 . Using it in the above equation, we get

K k=1 E( ∇f (x k ) 2 ) K ≤ 2 c + c + 2N c 2 α • 1 α • σ 2 M (18)

Similarly, given γ = c • D f M KLσ 2 = c αM L , the condition in Equation 8 can also be expressed as:

c α + 2N 2 c 2 α 2 ≤ 1 ⇒ 2N 2 c 2 + αc -α 2 ≤ 0

Since learning rate (and hence c) is always positive, the above equation gives us

0 ≤ c ≤ α 4N 2 • (-1 + 1 + 8N 2 )

Thus finding the optimal learning rate (within the regime of Equation 7 and 8) is equivalent to solving the following:

minimize 2 c + c + 2N c 2 α • 1 α • σ 2 M (19) s.t. 0 ≤ c ≤ α 4N 2 • (-1 + 1 + 8N 2 ) (20)

Now, by means of solving the above optimization, we will investigate how much the convergence guarantee can differ as the number of learners increase. In particular, we will look at the difference in the guarantee for 1 learner and N learners where N ≥ 16. Taking the derivative of Equation 19with respect to c and setting it to 0, we get the following:

EQUATION

Let c * 1 and c * N denote the solutions to the above equation for 1 and N learners respectively. Notice that for N = 1 and for α ≥ 16, the square term dominates in Equation 21 and c * 1 ≈ √ 2 (which also satisfies the constraint in Equation 20). Thus we get For N = 1:

K k=1 E( ∇f (x k ) 2 ) K 2 √ 2 • σ 2 αM (22)

However, for N = N and 16 ≤ α ≤ N , the cubic term dominates in Equation 21. Thus the value of c which satisfies Equation 21 is approximately 3 α/(2N ). However, the upper bound in Equation 20 for large N becomes c α/( √ 2N ). For the range of α under consideration, this is smaller than 3 α/(2N ), thus we get c * N = α/( √ 2N ). Thus for 16 ≤ α ≤ N , Equation 18 becomes For N = N :

EQUATION

)

Thus comparing Equation 22and 23, we see that the ASGD convergence guarantee for N = 1 and N = N learners can differ by a factor of N α for 16 ≤ α ≤ N .

:



Figures and Tables:

Input: mini-batch of M RGB images ↓ Convolution: (nfeat, nkern, height, width) = (3, 64, 5, 5) Rectified Linear Unit (ReLU) Max-Pooling: (height, width) = (2, 2) Dropout: prob. = 0.5 ↓ Convolution: (nfeat, nkern, height, width) = (64, 128, 3, 3) Rectified Linear Unit (ReLU) Max-Pooling: (height, width) = (2, 2) Dropout: prob. = 0.5 ↓ Convolution: (nfeat, nkern, height, width) = (128, 256, 3, 3) Rectified Linear Unit (ReLU) Max-Pooling: (height, width) = (2, 2) Dropout: prob. = 0.5 ↓ Convolution: (nfeat, nkern, height, width) = (256, 128, 2, 2) Rectified Linear Unit (ReLU) Max-Pooling: (height, width) = (2, 2) Dropout: prob. = 0.5 ↓ Fully connected layer: 128 × 10 ↓ Cross-entropy error

Figure 1: SGD experiments with CIFAR-10: convergence becomes slower as mini-batch M size increases.

Convolutional Neural Network for CIFAR10. For convolutional layers nfeat denotes the number of input feature maps and nkern denotes the number of kernels.

Table content: <table/>

≈ α/M h . Since α is much smaller than M h , we can approximate 1/c * h +c * h /2 ≈ 1/c * h ≈ M h /α and we also have 1 -c * h M/(2α) = 1/2. Thus the coefficient of D f Lσ 2 /S from Equation 12 evaluates to approximately 2M h /α.Combining the above observations, we get that the convergence guarantees for M l and M h can differ by a factor of 2M h /(α √ 2 + M l ) after processing S training samples.Theorem 4. Let N > 1 be the number of learners and let α =

Table content: <table><tr><td>4, we have 1 + ≈ 1+ /2 for small . Thus h Kσ 2 1 + 2α 2 /M 2 h ≈ 1+α 2 /M 2 √ h , using the approximation c  *</td></tr></table>

Peer review (iclr2017):
This paper theoretically justified a faster convergence (in terms of average gradient norm attained after processing a fixed number of samples) of using small mini-batches for SGD or ASGD with smaller number of learners. This indicates that there is an inherent inefficiency in the speed-up obtained with parallelizing gradient descent methods by taking advantage of hardware. This paper looks good overall and makes some connection between algorithm design and hardware properties. My main concern is that Lemma 1 looks incorrect to me. The factor D_f / S should be D_f/ (S*M) for me. Please clarify this and check the subsequent theorem.