Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: The paper proposes a simple method (SALR) to encourage the SGD to converge to flatter minima for better generalization. The basic idea is that it increases the learning rate when the sharpness is high, vice versa, such that SGD can escape sharp regions quickly. The sharpness is measured by the difference between the maximum and minimum found by a local SGD with a few fixed steps.

The paper is well written and easy to follow, and shows some interesting observations, such as:
1. SALR can achieve a comparable accuracy using 5 times less epochs in the outer SGD. It will be interesting to see if increasing the epochs can achieve higher accuracy or not;
2. The learning dynamics shown in Figure 4 (Right), indicating SGD escapes some local optima.

However, there are following issues in the paper:

1. discussion on connections to previous works

  1.1. the sharpness in "Definition 1" is highly correlated to gradient magnitude. When the region is smooth, we can loosely say a larger sharpness means a larger gradient magnitude (see Figure 3). Therefore, SALR uses a larger learning rate when the gradient is large. This is contradictory to Adam/AdaGrad, which decreases the learning rate when the accumulated gradients are large. Please explain.

  1.2. the motivation of increasing learning rate in SALR is to increase noise to escape sharp regions. SmoothOut [1] also injects noise to escape sharp regions, by averaging over the same neural network under different small perturbations of parameters. Please clarify the difference.

2. experiments

  2.1. the baselines in Table 1-3 are underperforming than expected. For LeNet, any SGD can achieve above 99% easily. The accuracy (88.44%) of ResNet-50 on Cifar-10 is also unexpectedly low [2].

  2.2. Assuming SALR converges to flatter and flatter regions as it learns, we should expect the sharpness drops as the iteration goes. This is not observed in Figure 4 Right.

Minor:
The bold highlight should go to "5.33 (0.60)" in the 4th row in Table 4.


[1] https://arxiv.org/abs/1805.07898
[2] https://benchmarks.ai/cifar-10
review_title: review

final_score: rating: 4: Ok but not good enough - rejection
review_content: 
This paper proposes SALR, a new optimization algorithm which adapts the learning rate to avoid sharp local minimas. This is achieved by computing/approximating the sharpness at different iterations and increasing the learning rate when the sharpness is high.

Empirical tests are performed on MNIST, and CIFAR-10, showing that the proposed method works better as compared to naive SGD, and entropy SGD.

Strong Points:
+ The problem being studied is very important and can have high impact for cases such as large batch training in which getting "trapped" in sharp minima is a problem
+ The paper does a good job of intuitively explaining their algorithm which adds noise in sharp regions by increasing learning rate.



Major Comments:

While the proposed algorithm is interesting but the theoretical and empirical results provided need to be strengthened further to support the claims. In particular, please note the following:

1- The empirical results are very limited. Given that the theoretical results are only for simple convex settings, a much more thorough empirical analysis would be needed to evaluate the proposed method.

2- What happens if you have negative curvature?


3- The theoretical proof provided is for simple convex problems. It is not clear how these results would extend to non-convex settings.

4- What is the overhead of the proposed method in terms of wall clock time?

5- How does the proposed approach compare with existing methods such as cyclical learning rate?

I will look for the rebuttal and will adjust my score accordingly. 

Suggestions for improvement:

There needs to be a more thorough evaluation of the paper for more challenging learning tasks such as ImageNet classification, and language modeling with transformers. There also needs to be tests to show when the proposed method fails (for example strict saddle points) and how this can be avoided. 
review_title: Paper Requires More Improvement

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper proposes a method called SALR, which adeptly updates the learning rate based on the local sharpness of the loss function to escape the sharp local minimum. By doing this, the author shows that their method can enhance the generalization and converge speed during the training procedure by encouraging the network to converge to a flat minimum.

The paper provides theoretical analysis as well as empirical results to support their claim.  For the theory part, the paper gives the evidence to prove that SALR can get a better converge rate while in the empirical part, the authors test SALR on MNIST and CIFAR10 using several different network structures.

Here are the pros and Cons I think in these parts. 

Pros:
1. The analysis of the converge rate part looks good for me. Though I do not check the proof one-by-one.
2. The experiment covers different networks and different optimizers, which greatly shows the algorithms generalization ability in most of the gradient-based optimizer.

Cons:
1. When calculating stochastic sharpness in empirical using algorithm 2, it seems that we need additional n1 and n2 steps. What is the value of n1 and n2 in empirical? This can slow down the gradient calculation speed a lot, I am worrying this can cause the algorithm very expensive to apply in many cases.

2. The empirical experiment result still seems limited. 
    (1). The author only tests several large networks on MNIST and CIFAR10, which makes its generalization statement weak. Moreover, I notice that the author actually does not even test CIFAR10 on MobileNetV2. 
    (2). For the statement of faster converge speed, I can not actually see the obvious change from the empirical result from figure 4.

Suggestions:
1. Could you add more experiments on other benchmarks like CIFAR100 and even ImageNet? If it is hard, could you clarify what is the bottleneck?

2. It should be good to see more ablation studies towards the converging speed in the empirical experiment.


Overall, I think this paper gives interesting points with the theoretical analysis. However, I still think the algorithm is hard to convince me in the empirical parts. 

============================== Update after author's response ==============================

The additional experiments look good to me, it solves most of my concern, I would like to lift the score to 6.
review_title: Official Blind Review #4

final_score: rating: 6: Marginally above acceptance threshold
review_content: This work proposes an algorithm that aims at finding a flat minimizer. The high-level strategy in the design of the proposed algorithm is increasing the learning rate when the iterate is in the region of a sharp minimizer. The authors claim that by increasing the learning rate, the iterate can get out of the undesired region. To estimate the local landscape (local sharpness), the authors provide a heuristic, which requires running gradient descent and gradient ascent for some number of iterations. The proposed algorithm has a promising result empirically, compared to entropy SGD (Chaudhari et al.) which also aims at finding a solution that generalizes well.

Strength:

(1) Paper is written well. The motivation is clearly explained. 

(2) The algorithm is easy to implement.

(3) The algorithm seems to work well in practice.

Weakness:

(1) Compared to the empirical results shown in the paper, the theoretical result is relatively weak. My concern is that Theorem 5 does not differentiate between flat and sharp local minima. Specifically, it could be the case that the conditions of the theorem are satisfied and that the iterate generated by the proposed algorithm escapes flat minima eventually.

The paper will be in a much better shape if the theoretical result shows that the iterate escapes sharp local minima while attracts to flat minima.

(2) (Computational overhead) Since the algorithm has a subroutine to estimate the local landscape, it incurs computational overhead compared to the baselines. I hope the authors can discuss this issue.

Minor:

(1) (Assumption 1) What are the examples that satisfy the assumption?

(2) (Remark 3 and normalization in Definition 1) 
I agree with Remark 3, but the argument made in Remark 3 also implies that the normalization will reduce the sharpness value when the gradient is large, which might be an undesired effect.

===
Overall, I think this is a reasonable paper and I am happy to increase the score if the authors respond well. 

=== after rebuttal ===

I thank the authors for the feedback. 

Regarding the proposed theorem, I was hoping to see if the iterate can stay in the flat minima instead of leaving the region eventually, as the constant of the local strong convexity is inside the log's, which is not very sensitive to the value (the landscape) and might be tricky to provide useful guidance to differentiate flat and sharp minima.

I decided to maintain my score, but I still recommend a weak accept of this paper.

review_title: showing some nice empirical results

Meta-review: This paper proposes a method to update the learning rate dynamically by increasing it in areas with higher sharpness and decreasing it otherwise. This would the hopefully leads to escaping sharp valleys and better generalization. Authors further provide some related theoretical results and several experiments to show effectiveness of their models.

All reviewers find the proposed method well-motivated, novel and interesting. The paper is well-written and easy to follow. However, both theoretical results and empirical evaluations could be improved significantly:

1- The theoretical results as is provides little to no insight about the algorithm and unfortunately, authors do not discuss the insights from the theoretical results adequately in the paper. See for eg. R1's comments about this.

2- Given that the theoretical results are not strong, the thoroughness in empirical evaluation is important and unfortunately the current empirical results is not convincing. In particular, there are two main areas to improve:

a) Based on the Appendix D, the choice of hyper-parameters seem to be made in an arbitrary way and all models are forced to use the same hyper-parameters. This way, the choice of hyper-parameters could potentially favor one method over the other. A more principled approach is to tune hyper-parameters separately for each method.

b) It looks like the choice of #epochs has been made in an arbitrary way. For all experiments, it would be much more informative to have a figure similar to the left panel of Fig. 4 but with much more #epochs so that reader can clearly see if the benefit of SALR would disappear with longer training or not.

c) Based on the current results, SALR's performance  is on par with that of Entropy-SGD on CIFAR-100 and WP and there is a very small gap between them on CIFAR-10 and PTB. I highly recommend adding ImageNet results to make the empirical section stronger. The other option is to compare against other methods in fine-tuning tasks. That is, take a checkpoint of a trained model on ImageNet and compare SALR with other methods on several fine-tuning tasks.

Given the above issues, my final recommendation is to reject the paper. I want to thank authors for engaging with reviewers during the discussion period and adding several empirical results to the revision. I hope authors would address the above issues as well and resubmit their work.
Decision: Reject