Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: Summary of results: This empirical paper finds that deep neural network "sharpness" (as measured by the top eigenvalue of the Hessian) tends to saturate at or hover just above the value 2/\eta, where \eta is the step size in gradient descent (GD), during the course of optimization. This is accompanied by non-monotonicity in the loss. (Results also hold for gradient descent with momentum.) This phenomena occurs for full-batch GD, a variety of tasks, and two different loss functions (square loss and cross-entropy, although in the latter case late-time dynamics of the sharpness is different, with the sharpness decreasing). The result also holds across a variety of architectures (VGG-11, with and without batch norm, convolutional networks and fully-connected networks with different nonlinearities, a deep linear network, a Transformer model -- although I comment on the architecture dependence below.) The authors refer to this phenomenon of sharpness hovering at or above the 2/\eta bound as optimization on the "edge of stability." The authors posit that this observation goes against our current understanding of optimization in deep learning: (i) theoretical work may use assumptions such as monotonic descent or L-smoothness, which is in violation of the "edge of stability" regime where the loss behavior is not monotonic; (ii) relatedly, it corresponds to a regime of instability in a quadratic Taylor approximation, so this is not a good assumption either. The empirical observations do not appear to straightway carry over to SGD (although there is some discussion of similarities in the appendix) -- the authors leave this is as an open problem.

Quality and clarity: The work is of good quality. The experiments that are presented clearly demonstrate the described phenomenon, attempt to sample from a variety of problems (ranging from a simple 1D regression task to training VGG-11 on CIFAR-10 in Fig.1), and are well-explained. 

Originality: The observed phenomena (of sharpness progressively increasing and then hovering at or near 2/\eta through much of GD dynamics) appears new to the best of my knowledge. (However, prior papers have pointed out that GD optimization can stably proceed for learning rates above 2/\eta and are accompanied with nonmonotonic loss: one example is Lewkowycz, et al. (2020).)

Significance: I think the observations are somewhat important, although perhaps not as much as the authors seem to stress in writing (e.g. in the abstract, "Our results ... shed significant light on the dynamics of gradient descent with a fixed step size ..." -- this paper focuses only on empirical observations rather than explanation of the mechanism behind the stability). The results are for full-batch GD which somewhat limits the applicability of the results to practice where SGD is more common. Nonetheless, I do think understanding how optimization is stabilized in this regime is an interesting problem.

Other comments: I think that a key point not fully understood (at least, as expressed in the writing) or investigated in the experiments is the role of network width (i.e. I'm skeptical that the observations will be "consistent across architectures" as expressed in the opening paragraph in the Introduction if wider networks are also investigated empirically). This is a main reason for not giving the paper a higher score. In Appendix D, the authors try to reconcile the results with existing theory on infinite-width limits. Fig. 11(c) shows that across networks of varying width but trained at the same learning rate, wider networks end up with smaller values of sharpness at the end of training (here, say that all experiments are stopped at the same value of the training loss). Hence if a narrower network saturates the 2/\eta bound at late times in gradient descent, the wider networks will fall below this value. (This is, of course, consistent with no evolution in the curvature in the infinite width limit.) That is to say, whether or not the "edge of stability" regime is reached depends quite strongly on how wide the networks are. 

While some realistic networks are explored (e.g. VGG-11, *narrow* Transformers), which is a positive point, all of the remaining networks used in the experiments (as far as I can gather) are on the narrow side (e.g. layer widths of order 100 or 200). I think a shortcoming of the paper is that the strong width (i.e. architecture) dependence of the phenomenon is not fully appreciated or discussed by the authors (e.g. for instance, by discussing in the main text that it only sets in for narrow networks) or investigated empirically. (Alternatively, noting for readers that all the networks chosen are rather narrow, out of transparency.)  I note that the authors do mention in Appendix D: "...one might hypothesize that progressive sharpening might attenuate as networks (with NTK parameterization) become increasingly wide." However, I don't think that NTK parameterization is necessary for this to be true. In short, I think the width dependence of the phenomenon is an important factor that affects the significance and applicability of the observations and could have been treated with greater transparency (with additional experiments and additions to the main text and abstract).

A comment on relation to prior work: the authors write that Lewkowycz, et al. (2020) imply that "actual progress would occur in regions where the sharpness remains strictly less than 2/\eta. Our experiments demonstrate otherwise." I don't believe this is a conclusion of that paper (progress happens when sharpness is above 2/\eta). (Note also that the paper tends to study wide networks.) Could the authors elaborate on what they mean here?
review_title: Interesting empirical observation but may be missing some key points

final_score: rating: 5: Marginally below acceptance threshold
review_content: 
This paper presents an interesting observation for GD. That is, the sharpness of the learnt model in the final phase of the training (measured by the largest eigenvalue of the training loss Hessian) hovers right at the value 2/\eta while the training loss. At the same time, the loss goes to unstable and non-monotonically decreasing. This pattern is consistent across architecture, activation functions, tasks, loss functions and BN. Comprehensive experiments are conducted to show this common observation. The paper is easy to follow.

Besides the empirical results in the main body, authors give insightful discussions in Intro and related work section. Specifically, authors propose a novel guess, that GD eventually transitions to “Edge of stability”, where GD can finally succeed with non-small enough step size. Although I am not sure how GD can do this, the concept of “Edge of stability” is still attractive. 

I have two concerns for this work. 
1) Authors did not investigate why sharpness finally hover over 2/\eta. Is it a trivial consequence followed by some relationship between the update rule of GD and the definition of sharpness, without any condition? Even if yes, we may further think about how to leverage it along the existing discussions in this paper. Hope to have authors' feedbacks on this later. 
2) Given people use SGD to train neural networks, discussions about the insight from the observation of GD to SGD will enhance the impact of this paper. 

review_title: An interesting observation of GD and insightful discussions

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: This work identifies a new empirical phenomenon in the training dynamics of deep nets: when trained with full-batch GD, the curvature of the train loss increases up to a critical value of 2/(step size), at which point it plateaus for the remainder of training.
This phenomenon is demonstrated robustly for networks trained with MSE loss, across various architectures and datasets, and a slightly weaker version of this holds for cross-entropy loss as well.
This work contributes to our understanding of deep network dynamics -- it is a precise and apparently robust phenomenon that was surprisingly not noticed before (perhaps because of the requirement of GD vs SGD). 
In terms of impact: This work will be instructive for DL optimization theory, since it points out that certain assumptions which are usually made in theoretical works (e.g. step size << curvature) are far from true in practice -- moreover, it guides theory towards more realistic assumptions.
It may also have later impact in practice, by leading to a better understanding of the interaction between optimization algorithm, step size, and architecture. Thus I recommend acceptance.

Weaknesses and desired clarifications:
- It should be mentioned more prominently that these results are primarily for networks trained with MSE loss -- and that a similar but weaker phenomena holds for cross-entropy loss. 
- Why is the main example in Section 3 given for a non-standard network for CIFAR-10? A 2-layer MLP with ELU activation. Why not a standard network with standard activation? (VGG-11 or ResNet-18, etc).
- The distinction between SGD and GD seems crucial for this phenomenon, so more discussion would be good. In particular, as noted in the related works, some papers using SGD claim an opposite effect. This is especially important to clarify since SGD is most often used in practice. If time allows, experiments with increasing batch size could shed light on the importance of GD vs SGD.
- The Related Works is currently written as an account of what previous works do *not* do, as opposed to what they do. It would help contextualize this work to relate it to prior works which are consistent (or inconsistent) with this phenomena -- especially works studying the Hessian of deep nets. Some of the mechanisms proposed in prior works (eg Lewkowycz et al 2020 and works on deep linear networks) may also be helpful to understand the phenomena in this work.



Comments which do not affect the score:

- I wonder if you have measured the 2nd eigenvalue during training as well? In particular, after the 1st eigenvalue has saturated at 2/eta, does the 2nd eigenvalue also "progressively sharpen" up to 2/eta ? (And so on for later eigenvals).
- I am glad to see the experiments on deep linear networks, it suggests that it may be possible to theoretically understand this phenomenon in such simple settings. This would be a nice topic for future work.
review_title: review

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: Summary:

This submission numerically shows that during exploring the neural network landscape,  GD flow keeps increasing the sharpness.  As a result, GD with a fixed learning rate will exhibit two phases during the dynamics.  Denote by $\eta$ the fixed learning rate.  In the first phase, GD follows closely to the GD flow, and it finally converges to a region where the sharpness is roughly $2/\eta$.  Then, it transits into the second phase during which the sharpness hovers right at or above $2/\eta$. In the second phase, GD cannot increase the sharpness anymore due to the dynamical stability constraint. Thus, the authors name it the Edge of Stability phase.  What is interesting is that in the edge of stability phase, the loss is still decreasing steadily although not monotonically. 

Pros:

I enjoy reading this submission. It is clearly written and the numerical evaluation is also sufficient.  To my best of knowledge, the observation that the edge of stability happens during the whole late phase of GD dynamics is new.  It reveals a very complicated dynamical behavior of GD for training neural networks, which has not been systematically investigated before.   Thus, I think this submission made a very important and original contribution to the understanding of GD dynamics  in deep learning. 

Cons:

The relationship with the previous study on the dynamical stability of (S)GD is not sufficient discussed. In my opinion, just saying ''previous works have argued that the stability properties of optimization algorithms could potentially serve as a form of implicit bias in deep learning'' is obviously not precise and enough. A large number of numerical results in [1,2] already showed that the edge of stability happens for the convergent solutions, which implies that the edge of stability must happen at least in the very late phase of GD dynamics.   The new finds of this submission are that the edge of stability actually holds for a large portion of GD dynamics, which is very unexpected.   The authors should explicitly mention that the edge of stability was already observed in these previous works. Giving the right credit to the right references does not harm the contribution of this submission.  Especially, the jargon "Edge of stability" was first used in [1], and the authors even did not mention it. 


[1] Giladi, Niv, et al. "At Stability's Edge: How to Adjust Hyperparameters to Preserve Minima Selection in Asynchronous Training of Neural Networks?." arXiv preprint arXiv:1909.12340 (2019).

[2] Wu, Lei, Chao Ma, and E. Weinan. "How sgd selects the global minima in over-parameterized learning: A dynamical stability perspective." Advances in Neural Information Processing Systems. 2018.
review_title: A very interesting observation about the complicated dynamical behavior of gradient descent in training neural networks.  

Meta-review: The paper demonstrates that Gradient Descents generally operates in a regime where the spectral norm of the Hessian is as large as possible given the learning rate. 

The paper presents a very thorough empirical demonstration of the central claim, which was appreciated by the reviewers.

A central issue to me in accepting the work was its novelty. Prior work has shown very closely related effects for SGD. The reviewers appreciated in discussions the novelty of the precise claim about the spectral norm hovering at around $\frac{2}{\eta}$. R4 and R2 also raised the issue that the related work discussion is not sufficient. Please make sure that you discuss very carefully related work in the paper, including a more detailed discussion in the Introduction.

The two key issues raised by R3, who voted for rejection, were that (1) the work studies Gradient Descent (rather than SGD), and (2) lack of theory. I agree with these concerns. Perhaps the Authors should address (1) by citing more carefully prior work that shows that a similar phenomenon does seem to happen in training with SGD. As for (2), I agree here with R1,R2 and R4 that empirical evaluation is a key strength of the paper. 

Based on the above, it is my pleasure to recommend the acceptance of the paper. Thank you for submitting your work to ICLR, and please make sure you address all remarks of the reviewers in the camera-ready version.
Decision: Accept (Poster)