ON THE INSUFFICIENCY OF EXISTING MOMENTUM SCHEMES FOR STOCHASTIC OPTIMIZATION
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 mini-batching. 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 implementing the ASGD Algorithm can be found here 1 .
I like the idea of the paper. Momentum and accelerations are proved to be very useful both in deterministic and stochastic optimization. It is natural that it is understood better in the deterministic case. However, this comes quite naturally, as deterministic case is a bit easier ;) Indeed, just recently people start looking an accelerating in stochastic formulations. There is already accelerated SVRG, Jain et al 2017, or even Richtarik et al (arXiv: 1706.01108, arXiv:1710.10737).
I would somehow split the contributions into two parts:
1) Theoretical contribution: Proposition 3 (+ proofs in appendix)
2) Experimental comparison.
I like the experimental part (it is written clearly, and all experiments are described in a lot of detail).
I really like the Proposition 3 as this is the most important contribution of the paper. (Indeed, Algorithms 1 and 2 are for reference and Algorithm 3 was basically described in Jain, right?). 
Significance: I think that this paper is important because it shows that the classical HB method cannot achieve acceleration in a stochastic regime.
Clarity: I was easy to read the paper and understand it.
Few minor comments:
1. Page 1, Paragraph 1: It is not known only for smooth problems, it is also true for simple non-smooth (see e.g. https://link.springer.com/article/10.1007/s10107-012-0629-5)
2. In abstract : Line 6 - not completely true, there is accelerated SVRG method, i.e. the gradient is not exact there, also see Recht (https://arxiv.org/pdf/1701.03863.pdf) or Richtarik et al (arXiv: 1706.01108, arXiv:1710.10737) for some examples where acceleration can be proved when you do not have an exact gradient.
3. Page 2, block "4" missing "." in "SGD We validate"....
4. Section 2. I think you are missing 1/2 in the definition of the function. Otherwise, you would have a constant "2" in the Hessian, i.e. H= 2 E[xx^T]. So please define the function as  f_i(w) = 1/2 (y - <w,x_i>)^2. The same applies to Section 3.
5. Page 6, last line, .... was downloaded from "pre". I know it is a link, but when printed, it looks weird.