Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The work aims to understand the phenomena of edge of stability along with progressive sharpening (rising of leading eigenvalues of the Hessian). As a foundation, it provides an interesting observation wrt the correlation between sharpness and the output layer's norm. Then it divides the analysis into four stages where the behavior of the leading eigenvalue is studied. Moreover, it proves the theorems in the setting of two-layer linear neural networks.  Some assumptions are verified with numerical experiments.


strengths_and_weaknesses: Pros:

1. The analysis is clear and convicing generally, with a detailed investigation into the four stages.
2. The observation of the correlation between the sharpness and output layer's norm is quite interesting, which makes it a good start point for the following analysis.

Concerns:

1. How to handle several eigenvalues close to $2/\eta$? This phenomena is observed by Cohen et al., but the assumption 3.6 and 4.1 rule it out.

Generally speaking, I would like to recommend an acceptance score for the complete analysis to resolve the problem of EoS.
questions: Please see the above concerns.

Typo:

1. Shall the fraction in Eq(3) be $\frac{4}{n}$?
limitations: No. But it is a pure theoretical work in a standard setting of optimization, so there is no significant need to do so.
review_title: null

final_score: rating: 3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
review_content: summary: This paper proposes a theoretical explanation for the progressive sharpening and edge of stability phenomena observed in Cohen et al (2021). Specifically, this paper claims that the gradient descent dynamics can be divided into four stages based on the value of the sharpness. For a general neural network, the paper gives a heuristic derivation for the four stages, where the proxy for sharpness is the last layer weight. It also gives a more rigorous derivation for a two-layer linear neural network.
strengths_and_weaknesses: Strengths: 

The edge of stability phenomenon contradicts much of classical optimization, and as of yet does not have a satisfactory theoretical explanation. Therefore I find this work to be an important research direction. Furthermore, the four stage division of dynamics proposed here appears to be novel.

Weaknesses:

My central issue with this paper is that the derivations are far too heuristic. As a result, I do not find the claims to be theoretically sound or a convincing explanation of the edge of stability phenomenon. Some specific instances are the following (all page references are for the version in the supplementary material):

Section 3:
- Rather than tracking the sharpness, this paper tracks $\|A(t)\|^2$, where $A(t)$ is the last layer weight. I don’t believe that in general the last layer weight is an accurate proxy for sharpness. The justification given here is that the difference in norms is usually the same sign as the change in sharpness; however, the empirical justification in Figure 2 is unconvincing as this correlation is only strong for the two layer linear network. Furthermore, while the analysis in Section 3 shows that $\|A(t)\|^2$ increases or decreases, this does not necessarily imply that the sharpness will decrease below $2/\eta$, which is a central component of the empirical analysis in Cohen et al (2021).
- This analysis does not track the full GD dynamics, but rather a first order Taylor expansion of the gradient. Appropriately dealing with the full dynamics seems far more challenging. This should also be stated explicitly as an assumption.
- Assumption 3.2 is very strong, and changing eigenvectors could have a nontrivial effect on the dynamics.
- I don’t find the argument for why the dynamics eventually return to stage I convincing. This argument is given at the bottom of page 8 + top of page 9 and is quite handwavy / unrigorous.
- Lemma 3.5 claims to explain the non-monotonic loss decrease, by saying $R(t)$, the dynamics with the $v_1$ direction projected out, approximately follows $R’(t)$. However, it seems that the error term in this Lemma can be very large, since $\eta$ is small and $\lambda_r$ can be very small as well.

Section 4:
- I don’t find Assumption 4.3 to be realistic. First, the fact that $\Gamma(t)$ is bounded during the progressive sharpening phase does not mean it will stay bounded during the EOS phase. In fact, Figure 18 clearly shows that $\|\Gamma(t)\|$ spikes during the edge of stability. Another issue is that assumption 4.3 amounts to the weights $W(t)$ changing very little during training, which is essentially equivalent to saying the network is in the lazy training/NTK regime. It is known that neural networks in practice don’t follow lazy training and weights do more far from initialization, and since edge of stability is inherently a non-quadratic phenomenon, I thus find it unreasonable to assume that weights do not move far from initialization. This assumption appears to be key to the claims in section 4, and therefore I do not find the main claims of this section to be convincing.

Furthermore, the supplementary material contains an alternate version of the paper where the main text is much longer (13 pages). I am not sure if this is allowed under the submission guidelines.
questions: As mentioned in the weaknesses section, I find a number of the assumptions to be unrealistic, and don’t find the empirical justification sufficient. Can you please elaborate on why these assumptions are reasonable? In particular, why the last layer norm is a good proxy for sharpness, and why one can assume $W(t)$ changes very little for the two-layer linear network?

Furthermore, can you please explain why the argument in section 3 guarantees a return to phase I?

From a clarity perspective, I find the assumptions and heuristic derivations being stated within the main theorems hard to follow. One suggestion is to have an explicit assumption section before the main results in section 3.
limitations: The paper does admit that the analysis is highly heuristic, which is the main limitation of this work.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper takes some steps towards theoretically understanding the "Edge of Stability" (EoS) phenomenon.  Two big open questions are: (1) why does the sharpness tend to rise whenever gradient descent is stable, and (2) once gradient descent is destabilized, why does the sharpness go back down / stop rising?

The paper has two parts: (1) a rigorous mathematical analysis of the two-layer linear network case (section 4), and (2) a nonrigorous mathematical analysis of the general neural net case combined with thorough experiments (section 3).

**Rigorous analysis of two-layer linear network**:   For a two-layer linear network, the NTK is the sum of two terms: (a) a term originating from the gradients w.r.t the first layer, and (b) a term originating from the gradients w.r.t the second layer.  Term (a) has a simple form: it is the product of the second-layer weight norm ( a scalar) and the input data Gram matrix.  Sharpness is defined as the maximum eigenvalue of the NTK (rather than the Hessian).

The authors first prove (in Lemma C3) that term (b) of the NTK will barely change during the first phase of training (the initial sharpening phase) -- rigorously, they prove that the delta of this term will be O(1/m) where m is the width of the network.  This implies that the NTK will approximately stay diagonalizable by the eigenvectors of the input data Gram matrix, and also that the sharpness is essentially totally determined by the second-layer weight norm.  Thus, to prove that progressive sharpening occurs, it suffices to prove that the second-layer weight norm increases during gradient descent.  In the update equation of the second-layer weight norm, the first-order term is the negative inner product between the predictions and the residual.  The authors are able to rigorously prove that the higher-order terms don't matter, and thus to prove progressive sharpening it suffices to prove that the inner product between the predictions and residual is always negative.  This is proved in Lemma C5.

The authors next prove that after becoming destabilized, gradient descent will move to a flatter region where the sharpness is below 2 / eta.  To use the authors' own words, the proof is "long and tedious," so I didn't attempt to parse the proof; but I assume that the intuition is similar to that of Proposition 3.2, which is that if the residual ever grows too big, then the last-layer weight norm will automatically decrease.  

**Beyond two-layer linear networks** The authors next attempt to show experimentally that the insights from the two-layer linear NN analysis  carry over in a very literal way to the general neural network case.  (Here, I write "next," but in the current draft this section occurs first chronologically.)  In particular, they demonstrate experimentally that in many networks, the dynamics of the sharpness correlate well with those of the last-layer weight norm: when the sharpness rises, so does the last-layer weight norm, and when the sharpness drops, so does the last-layer weight norm.   This seems to be more true in the initial phase of training, and becomes less true towards the end.  To their credit, the authors admit that there are counterexamples to this trend.

strengths_and_weaknesses: - Strength: this paper is the first to prove that some architecture (in this case, a two-layer linear network) undergoes progressive sharpening.  Indeed, this is the first paper to even give any kind of explanation for why progressive sharpening might occur.  (Actually, it was not even previously known that 2-layer linear nets can exhibit progressive sharpening.)

- Strength: I think that this paper is the first to prove that for some architecture (in this case, a two-layer linear network), instability causes the sharpness to decrease.  (The catapult paper includes a handwavy explanation for this phenomenon, but not a literal proof.)

- Weakness: the paper is at its weakest when it attempts to argue that its EoS analysis for two-layer linear networks carries over in a very literal manner to general neural networks.  First, I would point out that the correlation between sharpness and last-layer weight norm is not very robust: in Appendix B.1.2, we see that after the first few cycles of instability, there are a huge number of 'anomaly points' (steps where the change in the sharpness is not positively correlated with the change in last-layer weight norm).  Second, I would point out that "all layers seem to work together to influence the sharpness," as the authors write.

Overall, I would recommend framing this paper very differently.  I suggest centering the two-layer linear network analysis rather than the debatable claims about general neural networks.  If the authors are concerned that this analysis is very tedious, I would recommend just providing the intuition in the main paper (e.g. the fact that the leading term in the change in the sharpness is the inner product between the residual and the predictions) while deferring the complete proofs to the appendix.  Then, _after_ discussing the two-layer linear network analysis, you could mention that some of the patterns might carry over to general networks.  The authors are of course free to take or leave this advice, but I think that this restructuring would make the paper more compelling.

questions: For the two-layer NN:
 - does the degree of sharpening depend on the input dataset?  If we trained on random Gaussian data, would there still be sharpening?
 - does the degree of sharpening depend on the last-layer initialization (which is much larger in scale than the standard initialization)?


limitations: The paper is honest about its limitations.
review_title: null

Meta-review: metareview: While there is a rather large gap between the reviewers' scores, all the reviewers agreed that the paper is novel and the contributions are significant, especially given the little knowledge about the EoS phenomenon. While one of the reviewers raised important concerns about the appropriateness of the assumptions, I do believe that in a field without a rich enough literature, initial theoretical results with potentially strong assumptions are still valuable. Hence I am recommending an acceptance for the paper. 

Please implement all the changes that have been requested by the reviewers. On the other hand please avoid using gender pronouns like "he" when addressing the reviewers.  
confidence: Less certain
Decision: Accept