Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper studies the (non)convergence of gd on general 1d function, $f(x)=\frac{1}{4}(x^2-\mu)^2$, two-layer single-neuron homogeneous network and matrix factorization, and shows a similar patten among then, i.e. GD converges to a period-2 orbit around the minimizer when step size slightly exceed the critical value for establishing local stability at the minimizer.
strength_and_weaknesses: Strength:

Although it has been known that GD on a function with non-uniform curvature (or specifically, step size guarantee local stability on some region but not for other region) could lead to period-2 orbit, e.g. in Ma et al. (2022), this paper provide a more detailed analysis on several specific examples.

Weakness:

1. I cannot verify the soundness of Theorem 4/14 due to confusing notation and missing definition.

The first conflict I observe is that authors define $\Delta \mathbf{Y}_t=\mathbf{Y}_t-\mathbf{Y}_0$ below eq.(218), which implies $\Delta \mathbf{Y}_0=0$, but in the statement of Theorem 4/14, authors require $u_1^{\top} \Delta \mathbf{Y}_0 v_1 \neq0$.

The second difficulty is that $\widetilde{\mathbf{Y}}_t$, which shows up multiple times in the proof, is not defined.

Maybe these problems are just due to some typos, and I am willing to re-check the proof if authors could fix it during review process.

2. The writing need to be improved.

Theorem 3 doesn't directly state anything about edge of stability. Although the oscillating behaviors is discussed later informally, it would be better to express them rigorously in a theorem.

$\sigma_1$ is used in Section 6 without definition. Although in appendix J.2, authors relate it with SVD, it is better to give an explicit definition in the main paper.

> we study non-asymptotic properties of GD beyond EoS

It is not clear to me why this paper is "beyond" EoS.

3. The EoS in this paper is established by carefully selecting a step size that slightly break the local stability at the flattest minimizer. This is not how EoS works in DNN, where progressive sharpening drives curvature up until local stability is violated. Thus it is not clear how the results in this paper could contribute to the understanding of EoS in deep learning.

4. Figure 2 right shows oscillating w_y. However, according to Theorem 3, $w_y^{(t)}$ should exponentially decay to 0. Why they are different? Is it a consequence of finite number of points instead of explicit expectation?
clarity,_quality,_novelty_and_reproducibility: The writing of this paper could be improved.
Although not practical, I find the results in this paper interesting and not present in previous work.
summary_of_the_review: This paper demonstrate EoS phenomenon in several specific examples. Some confusing notations, missing definitions and unclear writing affect the quality of the article, but I believe they could be fixed by a slight revision and I am willing to re-evaluate during review process.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper studies the dynamics of gradient descent with a large step size.  In particular, the authors are interested in the study beyond the edge of stability, i.e., the step-size regime above the inverse of the Lipschitz constant. 
In that regime, local convergence is not guaranteed anymore. However, they show that under some additional assumptions on the higher derivative, one can actually show convergence to a cycle close to the optimum. They then apply the techniques to a one hidden neuron student teach problem and to a matrix factorization problem, showing that such a notion of convergence to a cycle can be obtained in that situation. 

strength_and_weaknesses: ## strenght: 
- This paper tries to tackle a complex and important problem: explaining the experimental evidence that GD convergence for NN training even with a step-size that is too large according to the optimization literature. 
- The presentation is relatively clear, and the (simple) experiments illustrate the theory. 
## Weaknesses:
- The setting is simplistic. It is unclear whether such a setting captures the phenomenon that occurs in deep learning. 
- Lemma 1 and Theorem 1 seem very weak results, relatively disconnected from the rest of the paper. (the key 1D result seems to be Theorem 2).

clarity,_quality,_novelty_and_reproducibility: Quality: The quality of the work is okay. There is some issues: 
1. I have a question regarding equation (40) in the appendix. I do not think you can ignore the higher order term and eventually give a precise bound on $\eta$. If you want to give a precise bound on $\eta$ such as $\eta \mu <\sqrt{5}-1$ you need not to neglect the higher order terms. Otherwise, you will just be able to say that $\eta \mu$ can be larger than $1$ without explicitly giving the upper bound. I would like the author to address this point in the discussion. 
2. Regarding Theorem 1 and Lemma 1:
- First I do not understand the notation $f^{(3)}(\bar x)/f''(\bar x) = \mathcal{O}(1)$. It seems that everything is fixed here. Why do you use an asymptotic notation? 
- Second, it seems that these results say that for specific initialization there exists **one** step-size for which the optimization oscillates. It is a very weak result since this phenomenon can be very brittle (you need to find the exact step-size that corresponds to your initialization). The important question (which is addressed in Theorem 2) is: Is there a range of step-size for which the method is stable?
- Around Theorem 3 some statements are unclear:
- The connection between $\lambda_1 = \frac{\|w\|^2+ v^2}{d}$ and  $\lambda_1 = \frac{(\|w\|- v)^2 + 2 \|\tilde w\|^2}{d}$ is unclear. 

3. (Minor) Around Theorem 4 many notations are missing:
- Who are $\simga_1$, $u_1$ , $v_1$
- $Y_0$ and $Z_0$ are not defined. 

Clarity: The results are clearly presented. However, I feel that Theorem 1 and Lemma 1 are a distraction from the main results. (see my points about quality)
Novelty: I am not an expert in the very recent topic of optimization with step-size larger than the inverse Lipschitz constant, so it is hard for me to address precisely the novelty of this work. However, from the perspective of an expert in optimization for neural networks, these results seem quite novel. 
Question: In the introduction, you mention that "We estimate our learning rate is at least 3× theirs (Wang et al., 2021)." but you do not expand on this when you present your results. Could you be more precise on that claim?
Reproducibility: These results seem reproducible. 

summary_of_the_review: This paper is providing results regarding an important question in our field. 
The quality and clarity of the paper are okay, but they could be improved.

My main concern is the significance of the results which are very toyish to a certain extent. It is not clear that these results can be related to the behavior of neural network training
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper is concerned with gradient descent beyond the so-called Edge of Stability (EoS). That is, the step size is large than what standard theory would suggest (using the Lipschitz constant of the loss function).  The EoS is interesting to the (theoretical) deep learning community because very often neural networks are trained in this regime.

This paper studies this regime by focusing on the following three simple settings.

1. One-dimensional functions
2. Learning a single neutron
3. Non-convex matrix factorization

Several results are established. For example: In Setting 1 it is shown that there exists a step size in the EoS regime such that gradient descent converges to an 2-periodic orbit. In Setting 2 it is shown that even for large learning rate, the single neuron can be learned. In the symmetric matrix factorization setting, it is shown that the gradient descent iterates converge to a 2-periodic orbit.

Moreover, there are several numerical experiments provide which support the theoretical findings.

strength_and_weaknesses: Strengths: The topic is very interesting and important to the theoretical deep learning community and has not been addressed properly. The paper contains several interesting observations. The numerical experiments support the theoretical findings and are presented in a clear manner.

Weaknesses: 
1. The paper misses a clear storyline. It feels that the paper presents several examples in the EoS regime but it is not clear how they are connected.
2. It is not clear how the findings or the setting under consideration is important to understand deep learning theoretically. The high-learning rate is often used in the early stages of neural network training and then the step size is decreased. It is not at all clear to me how this connects to the findings in the paper which seem rather to appear very locally, i.e. in the later stages of training.

Furthermore, I have the following list of specific comments.

1. page 4: "$x_0$ will back to $x_0$ in two steps"; Can you make this statement more formal
2. page 5, Lemma 1: "stably oscillate" has not been defined yet
3. page 5, Lemma 1: "except the $f''$"; what is meant by that?
4. page 6: $v^{(t)}=v^{(t)}$; Is this a typo?!
5. page 6; proof sketch; I cannot find where $\Delta w_y$ is defined. 
6. page 7: typo: "...condition holds around (the) minimum"
7. page 7: "period-$2$ orbit $\gamma_\eta$; I cannot find the definition of a period-$2$ orbit
8. page 7: What is $Z_0$ in eq. (11)?
clarity,_quality,_novelty_and_reproducibility: 1. The presentation could be more clear. Some notions are not properly introduced (see specific comments above). Also, as already mentioned, in my opinion the paper lacks a clear storyline which makes the main message a bit unclear.
2. To the best of my knowledge, the results are novel.
3. I did not have the time to check the proofs in the appendix. However, the results and the proof sketches look very reasonable to me.
summary_of_the_review: It is not clear how the theoretical results can amplify our current understand of the EoS regime in deep learning practice. Moreover, the paper misses a clear storyline and the quality of writing should be improved in my opinion. For this reason,  I cannot recommend acceptance.

--------------------------

I have read all the reviews and the rebuttals by the authors. While the changes made by the authors improve the paper in my opinion, I am still not convinced that the toy examples can give sufficient into the high-dimensional phenomena which appear in modern machine learning. Also the storyline still needs to be more coherent. (Although this would rather amount to a major revision and conference rebuttals are not for major revisions of papers.)

Thus, I can only increase my score to 5.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This work investigates gradient descent with a step size larger than the $\frac{2}{L}$ predicted by the standard theory, a regime known as the edge of stability. The authors provided sufficient conditions for ensuring an oscillatory (instead of diverging) behavior around the local minima for 1-dimensional functions. For higher-dimensional problems, the authors considered two scenarios: a two-layer single-neuron ReLU network in a teacher-student setup, and quasi-symmetric matrix factorization. The main results are that these objectives can still converge or stabilize for some step size $\eta = \frac{2K}{L}$, $K>1$.


strength_and_weaknesses: Strength:

- The authors provided many intersting observations on specific examples.

Weaknesses:

- A major issue is that the work seems like collecting a number of scattered examples where GD can converge with step size larger than $\frac{1}{L}$, without any coherent observation.

- The results on the 1-diemsnional functions are qualitatively different from the high-dimensional ones: In Section 4 (barring the special case of Theorem 2), the statements are "There **exists** a large step size such that XXX happens", whereas for higher-dimensional ones, they change to "**For all** step size in this region, XXX happens." Moreover, the existence proofs in Section 4 produce step sizes that are of Lebesgue measure 0, which shows that it is almost impossible for any practical algorithm to satisfy such conditions. In this sense, contrary to what the authors claimed, there is a disconnection between the low-dimensional and high-dimensional analysis.

- All the proofs, especially that of Theorem 3, rely on tedious and highly-specific calculations that do not reveal much about the general behavior of GD.

- The presentation of Section 5 is quite opaque. Can the authors explain what is meant by *"$\tilde{w}_\perp$ as the unit-length orthogonal residual of $w$ after projecting onto $\tilde{w}$"*? I understood it as the normalized version of $w- \text{proj}_\tilde{w} w$, but then this would violate the followup statement *"it is clear that updates of $w$ always stay in the plane spanned by $\tilde{w}$ and $w^{(0)}$"* since $\tilde{w}_\perp$ is not in the span of these two vectors. In addition, unless I missed something, the meaning of Theorem 3 is not clearly stated: it states that the orthogonal component of $w_t$ will decrease to 0, but it does not prove convergence (i.e., $vw\rightarrow \tilde{w}$). Can the authors provide a more clear interpretation than *"... the dynamics of the single-neuron ReLU network is getting closer to the 2-D case in Section A.1"*?

- Theorem 5 in Appendix A is not correct. The authors seem to have assumed that $xy > \mu$ always happens in the GD process, which is not guaranteed. If the authors wish to investigate the case of only those iterates satisfying $x^{(t)}y^{(t)} > \mu$, then one cannot assume an GD update from $x^{(t)}y^{(t)}$ to $x^{(t+1)}y^{(t+1)}, which the authors implicitly did.
clarity,_quality,_novelty_and_reproducibility: The clarity and novelty are major concerns of the paper: there are no clear takeaways, and some theoretical statements lack rigor. 
summary_of_the_review: This work studies the EoS phenomenon and provides several interesting examples. However, the lack of a global picture, clarity of the presentation, and mathematical rigor makes me feel that a major revision is required before accepting it.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper studies the Edge of Stability (EoS) phenomenon, which has recently attracted a lot of attention in the community. Specifically, the paper focuses on three different problems: one-dimensional functions, learning a single neutron, and non-convex matrix factorization.

The major common concern of the reviewers is the clear lack of a storyline. Instead, the paper presents a set of somewhat disconnected results. It's hard to draw of consistent conclusion and the impact on neural networks is rather weak and not well justified.

On the plus side, the authors are tackling an interesting problem but the paper is currently not ready for publication, all reviewers agree on this point. I strongly encourage the authors to rethink the overall presentation of the paper, making the paper more accessible and above all try to present a coherent story.

justification_for_why_not_higher_score: All reviewers agree this is a clear reject.
Decision: Reject