Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 1: Reject
review_content: 

This paper proposes two variants of Nesterov momentum that maintains a buffer of recent updates. The paper proves optimal convergence in the convex setting and makes nice connections to mirror descent and Katyusha.

I vote to reject the submission, with my main concerns being with the experimental results. I would consider raising my score if my concerns are addressed.

Concerns
-The learning rate schedule on the CIFAR experiments is unconventional. The original ResNet paper trains for 64k iterations (roughly 160 epochs). It’s standard to train for at least 200 epochs (see schedule from Smith et al.). Do the results hold under the standard schedule with careful tuning for the baselines?  
-The discussion on “Train-batch loss vs. Full-batch loss” in Section 2 is unclear. On smaller datasets, it is feasible to perform evaluation at the end of the epoch on the entire batch. Furthermore, reporting test accuracy couples optimization and generalization, and I am not sure what is meant by the statement ``test accuracy is too informative.”
-Reporting the peak test accuracy is strange. In general, we do not have access to the test set. It’s more natural to report the final test accuracy or have a holdout set to determine an iteration for evaluation.
-It’s not clear how significant the results on ImageNet and PTB are. Namely, a comparison to AggMo and/or QHM would be good, since the flavor of these algorithms is quite similar. Experiments in the AggMo paper suggest that AggMo performs better on PTB. In the comparison given in Appendix A3, it seems like AggMo performs slightly better throughout training. SGD should also attain better performance with learning rate tuning on ImageNet.
-I’m not sure how useful “Test Accuracy STD%” is useful as a metric since it is influenced heavily by the learning rate and its schedule. Tail averaging schemes in general seem like they would increase “robustness.” In addition, there seem to be situations where a higher final variance is beneficial (just run the method for longer and you can find a better solution). It would be nice to expand the discussion on the notion of robustness defined in the paper.

Minor Comments
-The dashed line in figure 1b) is hard to read. I would recommend removing the grid lines and make the colors more differentiable.
-Algorithm 1: use of both assignment and equality operator? Whereas other boxes use equality
-Spacing looks a bit off in parts of the paper. 1) after the first sentence in the introduction 2) “generic optimization layer (Defazio, 2018) . However”)
-M-SGD and M-SGD2 can be potentially confusing and are not too informative as acronyms.
-Remark on Theorem 1b: depicts does not seem like the right word

Smith, S. L., Kindermans, P. J., Ying, C., & Le, Q. V. (2017). Don't decay the learning rate, increase the batch size. arXiv preprint arXiv:1711.00489.
review_title: Official Blind Review #4

final_score: rating: 3: Weak Reject
review_content: The authors proposed Amortized Nesterov’s Momentum, a variant of Nesterov’s momentum that utilizes several past iterates, instead of one iterate, to provide the momentum.  The goal is to have more robust iterates, faster convergence in the early stage and higher efficiency. The authors designed two different realizations, AM1-SGD and AM2-SGD.

Comments:

My major concern for this paper is its unconvincing motivation and experiment results, especially when the approach is designed for deep learning.

The motivation for the proposed approach is not quite convincing. The authors said that “due to the large stochasticity, SGD with Nesterov’s momentum is not robust...This increased uncertainty slows down its convergence especially in the early stage of training and makes its single run less trustworthy” For image classification, Nesterov momentum is very popular and the final convergence values of different trails seems to be similar. It would be more convincing if the authors can provide practical evidence for supporting this claim.

It was claimed that Amortized Nesterov’s Momentum has “higher efficiency and faster convergence in the early stage without losing the good generalization performance”. What is the benefit or advantage for having faster early convergence without improving the final generalization performance?

The authors claim that “M-SGD2 is more robust and achieves slightly better performance”, in Figure 1a, however, it is really hard to tell the difference between M-SGD2 and M-SGD from Figure 1a.

The efficiency improvement in page 4 is really hard to follow for comparison with Algorithm 1 in page 3. Though m > 2 could reduce the number of operations in step 5 and 6, I don’t think this is a computational bottleneck. I believe these updates should be very fast in comparison with forward and gradient calculation. Making the 1% computation 50% faster does not mean more efficient. I would like to know how much computation cost can be saved with this modification. On the other hand, adding one more auxiliary buffer (scaled momentum) could significantly impact the training as the memory is often the limit. 


In section 3.1, what is “identical iteration”? It is hard to compare AM2-SGD with AM1-SGD. It would be easier to follow if the side-by-side algorithm comparison can be shown early.

The section 4’s theoretical analysis based on the convex composite problem is not quite convincing. I am not sure how these results are related with the deep learning applications.

In the experiment section, the comparison of AM1/2-SGD with other baselines seems not quite consistent. The authors first state that they use all 0.1 learning rate and 0.9 momentum for all methods, however, the setting for M-SGD is using 0.99 momentum and different learning rate schedule. This makes the comparison not very meaningful, while AM1-SGD and AM2-SGD do not use learning rate restart. With so many differences, the advantage of AM1-SGD and AM2-SGD are not that different with M-SGD.  In the task of ImageNet-152, M-SGD even is better than AM1-SGD. This makes the conclusion that “AM1-SGD has a lightweight design, which can serve as an excellent replacement for M-SGD in large-scale deep learning tasks” not quite valid.

Minor: The author may assume readers maybe familiar Katyusha momentum, I think there may need more background about it. 

review_title: Official Blind Review #2

final_score: rating: 3: Weak Reject
review_content: %% 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).
review_title: Official Blind Review #1

final_score: rating: 8: Accept
review_content: This paper provides a new simple method to incorporate Nesterov momentum into standard SGD for deep learning, with good empirical and theoretical results. Overall I think this paper should be accepted, some minor comments follow.

At no point does Polyak's heavy ball method get mentioned, even though the variant of Nesterov acceleration you are considering is very similar to it (since the momentum parameter is fixed, which is not the usual form of Nesterov except in the strongly convex case). It would be beneficial to delineate how this is or isn't related to heavy ball.

The experiments would benefit from a wall-clock time comparison too, rather than just epochs since these new methods would be slower (but presumably not by much).

The appendix is huge with most of the technical details relegated there which I did not read fully. I think this impacts the readability significantly, though not grounds for rejection. Perhaps it suggests that a conference with a small page limit is not the best venue?

It seems that SGD still has better convergence early on. The authors suggest their method fixes this (relative to standard nesterov SGD) but it doesn't seem to be quite as good as SGD. Can you explain or discuss why this is still the case?

The assumptions require some explanation, they are just listed with no context. What are they and why are they useful?

Step size "should be constrained to O(1/L)" is misleading, you should say explicitly that step-size <= 1/L (or whatever it is depending on the algorithm).

Some of the writing is a bit strange / sloppy, e.g.:
"AM2-SGD is a bit tricky in randomness"
"However, full-batch loss is way too expensive to evaluate."

In Algorithm 1 AM1-SGD:
"xk+1 ← xk+1 + β · (˜x+ − x˜)"
doesn't parse because x_{k+1} appears twice.

Missing references:

Accelerated proximal algorithms:

*) Beck and Teboulle: A Fast Iterative Shrinkage-Thresholding Algorithm
for Linear Inverse Problems

*) Nesterov: Gradient Methods for Minimizing Composite Objective Function,

Restarting (slightly different to your approach but still relevant): 

*) O'Donoghue: Adaptive Restart for Accelerated Gradient Schemes 
review_title: Official Blind Review #3

Meta-review: This paper introduces a variant of Nesterov momentum which saves computation by only periodically recomputing certain quantities, and which is claimed to be more robust in the stochastic setting. The method seems easy to use, so there's probably no harm in trying it. However, the reviewers and I don't find the benefits persuasive. While there is theoretical analysis, its role is to show that the algorithm maintains the convergence properties while having other benefits. However, the computations saved by amortization seem like a small fraction of the total cost, and I'm having trouble seeing how the increased "robustness" is justified. (It's possible I missed something, but clarity of exposition is another area the paper could use some improvement in.) Overall, this submission seems promising, but probably needs to be cleaned up before publication at ICLR.

Decision: Reject