Momentum based stochastic gradient methods such as heavy ball (HB) and Nesterov's accelerated gradient descent (NAG) method are widely used in practice for training deep networks and other supervised learning models, as they often provide significant improvements over stochastic gradient descent (SGD). Rigorously speaking, fast gradient methods have provable improvements over gradient descent only for the deterministic case, where the gradients are exact. In the stochastic case, the popular explanations for their wide applicability is that when these fast gradient methods are applied in the stochastic case, they partially mimic their exact gradient counterparts, resulting in some practical gain. This work provides a counterpoint to this belief by proving that there exist simple problem instances where these methods cannot outperform SGD despite the best setting of its parameters. These negative problem instances are, in an informal sense, generic; they do not look like carefully constructed pathological instances. These results suggest (along with empirical evidence) that HB or NAG's practical performance gains are a by-product of minibatching.

 Furthermore, this work provides a viable (and provable) alternative, which, on the same set of problem instances, significantly improves over HB, NAG, and SGD's performance. This algorithm, referred to as Accelerated Stochastic Gradient Descent (ASGD), is a simple to implement stochastic algorithm, based on a relatively less popular variant of Nesterov's Acceleration. Extensive empirical results in this paper show that ASGD has performance gains over HB, NAG, and SGD. The code for implementing the ASGD Algorithm can be found at https://github.com/rahulkidambi/AccSGD.
 First order optimization methods, which access a function (to be optimized) through its gradient or an unbiased approximation of its gradient, are the workhorses for modern large scale optimization problems, which include training the current state-of-the-art deep neural networks. Gradient descent (Cauchy, 1847) is the simplest first order method that is used heavily in practice. However, it is known that for the class of smooth convex functions as well as some simple non-smooth problems (Nesterov, 2012a) ), gradient descent is suboptimal BID1 and there exists a class of algorithms called fast gradient/momentum based methods which achieve optimal convergence guarantees. The heavy ball method BID5 ) and Nesterov's accelerated gradient descent (Nesterov, 1983 ) are two of the most popular methods in this category.On the other hand, training deep neural networks on large scale datasets have been possible through the use of Stochastic Gradient Descent (SGD) BID10 , which samples a random subset of training data to compute gradient estimates that are then used to optimize the objective function. The advantages of SGD for large scale optimization and the related issues of tradeoffs between computational and statistical efficiency was highlighted in Bottou & Bousquet (2007) .The above mentioned theoretical advantages of fast gradient methods BID5 Nesterov, 1983) (albeit for smooth convex problems) coupled with cheap to compute stochastic gradient estimates led to the influential work of BID16 , which demonstrated the empirical advantages possessed by SGD when augmented with the momentum machinery. This work has led to widespread adoption of momentum methods for training deep neural nets; so much so that, in the context of neural network training, gradient descent often refers to momentum methods.But, there is a subtle difference between classical momentum methods and their implementation in practice -classical momentum methods work in the exact first order oracle model BID1 , i.e., they employ exact gradients (computed on the full training dataset), while in practice BID16 , they are implemented with stochastic gradients (estimated from a randomly sampled mini-batch of training data). This leads to a natural question:"Are momentum methods optimal even in the stochastic first order oracle (SFO) model, where we access stochastic gradients computed on a small constant sized minibatches (or a batchsize of 1?)"Even disregarding the question of optimality of momentum methods in the SFO model, it is not even known if momentum methods (say, BID5 ; Nesterov (1983) ) provide any provable improvement over SGD in this model. While these are open questions, a recent effort of Jain et al. (2017) showed that improving upon SGD (in the stochastic first order oracle) is rather subtle as there exists problem instances in SFO model where it is not possible to improve upon SGD, even information theoretically. Jain et al. (2017) studied a variant of Nesterov's accelerated gradient updates BID2 for stochastic linear regression and show that their method improves upon SGD wherever it is information theoretically admissible. Through out this paper, we refer to the algorithm of Jain et al. (2017) as Accelerated Stochastic Gradient Method (ASGD) while we refer to a stochastic version of the most widespread form of Nesterov's method (Nesterov, 1983) as NAG; HB denotes a stochastic version of the heavy ball method BID5 . Critically , while Jain et al. (2017) shows that ASGD improves on SGD in any information-theoretically admissible regime, it is still not known whether HB and NAG can achieve a similar performance gain.A key contribution of this work is to show that HB does not provide similar performance gains over SGD even when it is informationally-theoretically admissible. That is, we provide a problem instance where it is indeed possible to improve upon SGD (and ASGD achieves this improvement), but HB cannot achieve any improvement over SGD. We validate this claim empirically as well. In fact, we provide empirical evidence to the claim that NAG also do not achieve any improvement over SGD for several problems where ASGD can still achieve better rates of convergence.This raises a question about why HB and NAG provide better performance than SGD in practice BID16 , especially for training deep networks. Our conclusion (that is well supported by our theoretical result) is that HB and NAG's improved performance is attributed to mini-batching and hence, these methods will often struggle to improve over SGD with small constant batch sizes. This is in stark contrast to methods like ASGD, which is designed to improve over SGD across both small or large mini-batch sizes. In fact, based on our experiments, we observe that on the task of training deep residual networks (He et al., 2016a) on the cifar-10 dataset, we note that ASGD offers noticeable improvements by achieving 5 − 7% better test error over HB and NAG even with commonly used batch sizes like 128 during the initial stages of the optimization. In this paper, we show that the performance gain of HB over SGD in stochastic setting is attributed to mini-batching rather than the algorithm's ability to accelerate with stochastic gradients. Concretely, we provide a formal proof that for several easy problem instances, HB does not outperform SGD despite large condition number of the problem; we observe this trend for NAG in our experiments. In contrast, ASGD (Jain et al., 2017) provides significant improvement over SGD for these problem instances. We observe similar trends when training a resnet on cifar-10 and an autoencoder on mnist. This work motivates several directions such as understanding the behavior of ASGD on domains such as NLP, and developing automatic momentum tuning schemes BID18 .A SUBOPTIMALITY OF HB: PROOF OF PROPOSITION 3Before proceeding to the proof, we introduce some additional notation. Let θ DISPLAYFORM0 t+1 denote the concatenated and centered estimates in the j th direction for j = 1, 2. DISPLAYFORM1 , j = 1, 2.Since the distribution over x is such that the coordinates are decoupled, we see that θ (j) t+1 can be written in terms of θ (j) t as: DISPLAYFORM2 t+1 denote the covariance matrix of θ DISPLAYFORM3 with, B (j) defined as DISPLAYFORM4 We prove Proposition 3 by showing that for any choice of stepsize and momentum, either of the two holds:• B (1) has an eigenvalue larger than 1, or,• the largest eigenvalue of B (2) is greater than 1 − 500 κ . This is formalized in the following two lemmas.Lemma 4. If the stepsize δ is such that δσ DISPLAYFORM5 (1) has an eigenvalue ≥ 1.Lemma 5. If the stepsize δ is such that δσ DISPLAYFORM6 (2) has an eigenvalue of magnitude DISPLAYFORM7 Given this notation, we can now consider the j th dimension without the superscripts; when needed, they will be made clear in the exposition. Denoting x def = δσ 2 and t def = 1 + α − x, we have: DISPLAYFORM8 The analysis goes via computation of the characteristic polynomial of B and evaluating it at different values to obtain bounds on its roots.Lemma 6. The characteristic polynomial of B is: DISPLAYFORM9 Proof. We first begin by writing out the expression for the determinant: DISPLAYFORM10 expanding along the first column, we have: DISPLAYFORM11 Expanding the terms yields the expression in the lemma.The next corollary follows by some simple arithmetic manipulations. Corollary 7. Substituting z = 1 − τ in the characteristic equation of Lemma 6, we have: DISPLAYFORM12 Proof of Lemma 4. The first observation necessary to prove the lemma is that the characteristic polynomial D(z) approaches ∞ as z → ∞, i.e., lim z→∞ D(z) = +∞.Next, we evaluate the characteristic polynomial at 1, i.e. compute D(1). This follows in a straightforward manner from corollary (7) by substituting τ = 0 in equation (2), and this yields, DISPLAYFORM13 As α < 1, x = δσ 2 > 0, we have the following by setting D(1) ≤ 0 and solving for x: DISPLAYFORM14 Since D(1) ≤ 0 and D(z) ≥ 0 as z → ∞, there exists a root of D(·) which is ≥ 1.Remark 8. The above characterization is striking in the sense that for any c > 1, increasing the momentum parameter α naturally requires the reduction in the step size δ to permit the convergence of the algorithm, which is not observed when fast gradient methods are employed in deterministic optimization. For instance, in the case of deterministic optimization, setting c = 1 yields δσ 2 1 < 2(1 + α). On the other hand, when employing the stochastic heavy ball method with x (j) = 2σ 2 j , we have the condition that c = 2, and this implies, δσ DISPLAYFORM15 We now prove Lemma 5. We first consider the large momentum setting. Lemma 9. When the momentum parameter α is set such that 1 − 450/κ ≤ α ≤ 1, B has an eigenvalue of magnitude ≥ 1 − 450 κ .Proof. This follows easily from the fact that det(B ) DISPLAYFORM16 Remark 10. Note that the above lemma holds for any value of the learning rate δ, and holds for every eigen direction of H. Thus, for "large" values of momentum, the behavior of stochastic heavy ball does degenerate to the behavior of stochastic gradient descent.We now consider the setting where momentum is bounded away from 1.Corollary 11. Consider B (2) , by substituting τ = l/κ, x = δλ min = c(δσ 2 1 )/κ in equation (2) and accumulating terms in varying powers of 1/κ, we obtain: DISPLAYFORM17 Substituting the value of l in equation (3) , the coefficient of DISPLAYFORM18 We will bound this term along with (3 DISPLAYFORM19 2 to obtain: DISPLAYFORM20 where, we use the fact that α < 1, l ≤ 9. The natural implication of this bound is that the terms that are lower order, such as O(1/κ 4 ) and O(1/κ 5 ) will be negative owing to the large constant above. Let us verify that this is indeed the case by considering the terms having powers of O(1/κ 4 ) and O(1/κ 5 ) from equation (3) : DISPLAYFORM21 κ 4 The expression above evaluates to ≤ 0 given an upperbound on the value of c. The expression above follows from the fact that l ≤ 9, κ ≥ 1.
Existing momentum/acceleration schemes such as heavy ball method and Nesterov's acceleration employed with stochastic gradients do not improve over vanilla stochastic gradient descent, especially when employed with small batch sizes.