Stochastic Gradient Descent (SGD) with Nesterov's momentum is a widely used optimizer in deep learning, which is observed to have excellent generalization performance. In this work, we propose Amortized Nesterov's Momentum, which is a special variant of Nesterov's momentum. Compared with Nesterov's momentum, our new momentum has more robust iterates and higher efficiency. Our empirical results show that it achieves faster early convergence and comparable final generalization performance with little-to-no tuning. Just like Nesterov's method, the new schemes are also proved optimal in general convex setting. Our analysis sheds light on the understanding of the new variant.
%% Post Author Response comments %%
Thank you for your detailed response/revision. 
1 - Introducing “m-times” larger momentum: Somehow, this is not a particularly intuitive statement or one that reflects clearly in a theoretical bound. Since we are getting to issues surrounding the use of momentum with stochastic optimization, I would like to make a note that the performance of these algorithms more broadly aren't quite sketched out for their use in broader stochastic optimization. In particular, despite broad use in practice, it is unclear if standard variants of Nesterov acceleration/Heavy Ball method achieve "acceleration" in stochastic optimization. See for e.g., the work of Kidambi et al ICLR 2018 (“On the insufficiency of existing momentum schemes for stochastic optimization”) - where, the argument was that these methods were designed for deterministic optimization (where we get exact gradients) - in fact, that paper empirically as well as theoretically shows that these schemes do not offer acceleration in a precise sense compared to specialized algorithms for stochastic optimization. It is unclear if the proposed algorithms can offer a similar improvement over SGD in a provable sense, even for the specific examples described in their paper.
2 - The point about theory (just as you mention) is that it doesn’t directly apply towards the simulations, nor, do they improve on already known algorithms - so I am unable to see the point that these results present broader implications that can guide practice.
3 - The response doesn’t address the fact that for the theory bounds presented in the paper to hold (even in the convex settings described), one requires knowledge of parameters that are not known a-priori, and are often fairly difficult to estimate. So the performance of the algorithm in practice may quite significantly be away from the bounds described in the paper.
While I appreciate the points and revision made by the authors, I still believe the paper requires some rethinking to present their results (and this includes more detailed comparisons to existing works) in order to make a case towards broader practical applications.
%%. %%
This paper considers robustness issues faced by Nesterov’s Acceleration used with mini-batch stochastic gradients for training Deep Models. In particular, the paper proposes amortized momentum, an algorithm that offers a way to handle these issues. The paper in general is well written and easy to follow. 
The paper proposes algorithms AM-SGD1 and AM-SGD2 and presents extensive results regarding their complexity analysis on convex problems and their performance when training neural networks. The algorithms require storing one more model’s worth of storage compared to standard momentum based methods (which can be viewed as a drawback in certain cases).
Comments:
[1] I am concerned about the motivation behind this paper - which, according to the paper is that Nesterov’s accelerated gradient method with stochastic gradients has huge initial fluctuations. The issue with regards to more fluctuations of the initial performance is natural given how aggressive these accelerated methods work. As long as this is not a reason/cause for worse terminal performance (which doesn’t seem to be the case), I am unable to see why large initial fluctuations are concerning.
[2] Theory: The theory bounds for this problem setting do not appear to improve over known bounds in the literature. As a side note, the work of Hu et al. “Accelerated Gradient Methods for Stochastic Optimization and Online Learning” is highly related to this paper’s theoretical aspects, setup and bounds. Furthermore, this bounded variance noise model for stochastic gradients, while being theoretically useful (and important), is often very detached from practice (as this implies that the domain is bounded and we perform projections of iterates whenever they go outside the set - such aspects hardly reflect on practical SGD implementations). Using this as a means to reason about robustness of the proposed algorithm (for e.g. remarks for theorem 1a. and in conclusions) appears to be a big leap that may lead to potentially misleading conclusions.
[3] In order to run the algorithm to achieve the theoretical bounds claimed (in theorems 1 and 2), it appears that the stepsize \alpha_s depends on unknown quantities such as initial distance to opt, noise variance etc.
[4] The claim in page 2 about comparing SGD and M-SGD says that the stepsize in deterministic and stochastic optimization is constrained to be O(1/L) is rather misleading. In realistic practical implementation of SGD with a multiplicative noise oracle, one really has to use a much smaller stepsize than 1/L. This in a sense leads back to point[2] about the unrealistic nature of bounded variance assumptions for understanding SGD based methods used in the context of Machine Learning. They are better suited for understanding stochastic methods in black-box optimization (as opposed to considering Machine Learning problems).
My take is that even if the authors justify novelty in terms of theory results (which, to my knowledge is limited compared to existing literature), rewriting the paper by considering its theoretical merit and presenting empirical results (even as considered in this paper) of this algorithm (without attempting to make very strong connections to explain issues experienced in non-convex training of neural networks, since the theory works in vastly different settings under restrictive assumptions) can be appreciated by appropriate sections of audience (both in theory as well as optimization for deep learning communities).