Venue: ICLR 2018 conference

Reviews:

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: I only got access to the paper after the review deadline; and did not have a chance to read it until now. Hence the lateness and brevity.

The paper is reasonably well written, and tackles an important problem. I did not check the mathematics. 

Besides the missing literature mentioned by other reviewers (all directly relevant to the current paper), the authors should also comment on the availability of accelerated methods inn the finite sum / ERM setting. There, the questions this paper is asking are resolved, and properly modified stochastic methods exist which offer acceleration over SGD (and not through minibatching). This paper does not comment on these developments. Look at accelerated SDCA (APPROX, ASDCA), accelerated SVRG (Katyusha) and so on.

Provided these changes are made, I am happy to suggest acceptance.




review_title: Accept

final_score: rating: 7: Good paper, accept
review_content: 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. 


review_title: Nice idea, Like the paper

final_score: rating: 7: Good paper, accept
review_content: I wonder how the ASGD compares to other optimization schemes applicable to DL, like Entropy-SGD, which is yet another algorithm that provably improves over SGD. This question is also valid when it comes to other optimization schemes that are designed for deep learning problems. For instance, Entropy-SGD and Path-SGD should be mentioned and compared with. As a consequence, the literature analysis is insufficient. 

Authors provided necessary clarifications. I am raising my score.





review_title: Good paper, accept

Meta-review: The reviewers unanimously recommended that this paper be accepted, as it contains an important theoretical result that there are problems for which heavy-ball momentum cannot outperform SGD. The theory is backed up by solid experimental results, and the writing is clear. While the reviewers were originally concerned that the paper was missing a discussion of some related algorithms (ASVRG and ASDCA) that were handled in discussion.

Decision: Accept (Oral)