Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper shows that a large learning rate can provably escape local minima and reach global minima for smooth and one-point-strongly-convex functions, while a small learning rate would not work. The paper further shows that a higher stochastic noise is not enough to close the gap with the model trained with a large learning rate.  Some experiments are conducted to disentangle the effects of stochastic noise and learning rate, to compare small and learning rates when training neural networks.
strength_and_weaknesses: Strength:

1. The paper is clearly-written and the main message is clear.
2. The literature review is sufficient.

Weaknesses:
1. The large learning rate is indeed important in neural network training, but the authors did not analyze the neural network training trajectory of gradient descent theoretically: instead, the authors simply assumed the function is smooth and one-point-strongly-convex, and there are exactly two minima. I am not sure the insight obtained in this paper can be generalized in neural networks since some arguments are made over some contrived functions (e.g., the function plotted in Figure 5).

2. I am wondering what is the real technical contribution of this paper. It seems to be that the proof technique is standard: it uses standard proof roadmaps for smooth functions and combines with the one-point-strong-convexity to obtain the relationship between two consecutive iterates. 

3. The experiments are not well-designed. In Section 5.1, to disentangle the effects of learning rate and the stochastic noise, the authors should consider noiseless case instead of noisy case with different scale: the reason is that the noise does not only affect the current solution but also affects the whole trajectory of gradient descent. Why the authors turns off batch normalization? 

4. The insight of Section 5.2 is very similar to Figure 1 in [Li et al. NeurIPS 2019]. Although [Li et al. NeurIPS 19] did not plot the principal component but it is clear that small and large learning rate gradient descent have different trajectories (Please refer to Section 4 in [Li et al. NeurIPS 2019]).





clarity,_quality,_novelty_and_reproducibility: Clarity: Good. The paper is very clear about their findings and contribution.

Quality and Novelty: Low to Medium. The authors only considered an oversimplified case of nonconvex optimization with smooth and one-point-strongly-convex loss functions. The authors did not compare their results with some formal studies on large learning rates in neural networks, such as [Li et al. NeurIPS 2019].

Reproducibility: Medium. The code is provided, but there are not multiple runs based on different random seed. In addition, the experiment design has some issues which I mentioned in the Weaknesses section.
summary_of_the_review: The paper considered the effects of a large learning rate and showed that under smooth and one-point-strong-convex assumptions large learning rate is better than a small learning rate. However, it is unclear that how relevant these results are because the authors did not analyze the trajectory of a certain neural network but some contrived functions (e.g., Proposition 3). The experimental design has some issues. Overall the insight is not significant compared with previous work, such as [Li et al. NeurIPS 2019], which formally analyzed the effect of the learning rate in a certain neural network.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper tries to  explain why large learning rate is important in non-convex optimiztion.
This paper shows that  GD with large step size—on
certain non-convex function classes—follows a different trajectory than GD with
a small step size, which can lead to convergence to a global minimum instead of a
local one.
The intuition behind this paper is direct and easy to follow.
The proofs in this paper are solid.
strength_and_weaknesses: Pros: The inituition of this paper is easy to follow and it can explain why a large learning rate is preferred in a class of non-convex functions. The proofs in this paper are solid and easy to understand.

Cons: The writing seems a little messy. Lemma 1 is not easy to read. I also doubt  whether the claim in this paper holds for training neural networks. 
clarity,_quality,_novelty_and_reproducibility: This paper has some good insights for explaining why one should large learning in optimizing non-convex function.
The writing seems a little messy.
summary_of_the_review: This paper tries to  explain why large learning rate is important in non-convex optimiztion.
This paper shows that  GD with large step size—on
certain non-convex function classes—follows a different trajectory than GD with
a small step size, which can lead to convergence to a global minimum instead of a
local one.
The intuition behind this paper is direct and easy to follow.
The proofs in this paper are solid.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This work considers the effect of large stepsize for GD in non-convex optimization. It shows theoretically that, under certain conditions, with a large stepsize GD can escape/avoid undesirable minimum, and in comparison, GD/SGD with small stepsize might converge into the undesirable minimum. 

Then the paper turns to present some empirical results. By re-using a mini-batch for multiple times, the work can, approximately, control the stepsize and the gradient noise in SGD in separate. By comparing this SGD variant with small/large stepsize SGD, some insights are drawn that the effect of large stepsize for SGD can go beyond simply a larger gradient noise. The second part of the experimental results are for verifying the provided theory. 
strength_and_weaknesses: # Strength 
1. The work considers a very important topic: understanding the effect of large stepsize in SGD. Despite the caveats in the theory (please see more in below), I (and I believe many others in the community) share somewhat similar understanding as the authors have proved in their theorems. 
2. I find most of the presentation is good. I especially like the cartoon figures, which speak for themself in a very nice way. 
3. The design in Section 5.1 is very interesting to me. I think this design could inspire more follow-up study on SGD (stepsize and noise).

# Weakness
Most of my criticism about this work will be about their theorems.

1. Thm1 could have cited [Wu, et al, 2018]. Note that the "linear stability" in [Wu, et al, 2018] can exactly explain the results in Thm 1. Because for the choice of stepsize, $x\_\\dagger$ is not linear stable but $x\_\*$ is linear stable. Granted, Thm1 discusses the behavior of the GD in an integrated manner, but the techniques are standard, using the assumptions on the one-point-convexity. I strongly suggest to add some discussion on [Wu, et al, 2018]. 

2.  Definition2 could be made more clear by specifying in the condition that $M$ is a fixed set (connected? compact? containing $x\_\*$? ...). 

3. Theorem 1, could define what is $\\mathcal{L}$. I assume it refers to some measure over the randomness of the initialization?

4. Lemma 2 and Theorem 2. The failure probability has a crude, exponential dependence on dimension $d$ and number of iterates $T$. Such an exponential dependence makes the result rather weak and less interesting. I would like to see some discussion on how tight these are. That is, can we improve the dependence on $d$ and $T$ or not? Is the current exponential dependence purely artificial?

5. Both Theorem 1 and 2 put strong assumptions on the landscape of the loss (e.g., exactly two minimum). Moreover, proposition 3 is dedicated for a special example. I am not against to look at special cases for drawing intuition, but the theorems in their current form fail to qualify this work as a solid theory work, in my humble opinion.  

6. I feel the theory and the experiments have only tangential connections. Indeed, the theorems are all for optimization and have little to do with generalization/learning. But crucial in the experiments are the test accuracy for each algorithm. Is it possible to connect the specific loss landscape required for the theorem to some nature learning settings? If not I can hardly see why these losses are important examples for understanding the learning ability of SGD. 

# Missing Literature
In fact, multiple existing works have investigated the effect of large stepsize and discussed their importance for SGD (and are not from the perspective of enlarging the gradient noise). For an incomplete list, please see the following and the references therein:

[1] Wu, Jingfeng, et al. "Direction matters: On the implicit bias of stochastic gradient descent with moderate learning rate." ICLR 2021.

[2] Beugnot, Gaspard, Julien Mairal, and Alessandro Rudi. "On the Benefits of Large Learning Rates for Kernel Methods." COLT 2022.


clarity,_quality,_novelty_and_reproducibility: Clarify is fine.

Quality is OK.

Novelty is OK.

Reproducibility is good. 
summary_of_the_review: Please see above. I will consider re-evaluate based on the authors reply but at this point I do not think this work qualifies being published.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper considers the observation that large learning rates are useful in training of deep learning models. The paper studies this phenomenon and under certain non-convex function classes shows that the large learning rates can help escape local minima and converge to a global minima. The primary contribution of the paper according to the reviewers is to identify these function classes where this phenomenon holds. Overall the reviewers appreciated some aspects of the paper but the major concerns remained (even after a virtual discussion) -- 
1. The model under which the theory presented by the paper holds is still quite a bit further away from what's used in practice. 
2. While point 1 might itself not be enough of a demerit, the reviewers found that the paper's technical contributions are not sufficient to be above the bar for ICLR. This was also coupled with the fact that certain theorems presented in the paper had certain not so immediately quantifiable quantities, in particular one factor whose dependence on the dimension dependence seems to be exponential in d in many cases of interest. 

Overall due to these shortcomings the reviewers in the meeting generally agreed that the paper was below the bar for ICLR. 
justification_for_why_not_higher_score: The paper's scores were clearly below the borderline for acceptance. The reviewers' scores were based on the points highlighted by me in the meta review.
Decision: Reject