Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper aims to understand the recently discovered "Edge of Stability" phenomena in a second-order regression model. The authors consider second-order NTK models and show for simple settings, under proper conditions,  one can observe progressive sharpening close to initialization. Finally, the authors simulate the simple models to observe the EoS phenomena.
strength_and_weaknesses: The major strength of the paper is to show that second-order NTKs can show the Edge of stability behavior close to initialization, under proper conditions. 


However, I feel the main messages of sections 2.2.2, 3.2, and 3.3 are not clear at all. I have the following questions.
a) How should one be reading the plot in Figure 2 (middle)?

When the authors mention "For small, the dynamics show the distinct phases described in (Li et al., 2022): an initial increase in $T(0)$, a slow increase in $\tilde{z}$, then a decrease in $T(0)$, and finally a slow decrease of $\tilde{z}$ while $T(0)$ remains near 2 (Figure 2, middle)", how should one read this phenomenon in Figure 2 (middle)?

Moreover, what are the blue lines in figure 2 (middle)?

b) How does the result of theorem 3.1 imply progressive sharpening? The theorem statement simply says that the expected time derivative of $\lambda_{\max}$ is $0$ at initialization, while the expected double derivative of $\lambda_{\max}$ depends on the initial scale of output. How does this imply that $\lambda_{\max}$ will increase to $2/\eta$ after few steps? 

Furthermore, the jacobian $J = G + Q(\theta, .)$, how do the authors initialize $J$ with variance $\sigma_J^2$? Or are the authors initializing both $G$ and $Q$ such that the condition on $J$ holds true? Same question for $z$, how do the authors make sure $z$ has variance $\sigma_z$?


c) In theorem 2.1, the authors require the second eigenvalue to be much smaller than $1$, otherwise, the bound on $\lim_{t \to \infty} \lambda_{\max}$ gets very loose. Can the authors comment on whether such a big gap between the eigenvalues is necessary for EoS to hold in practice? Or do the authors need such a gap to make sure the EoS occurs near initialization?

Furthermore, Cohen et al. [2020] observe that the EoS phenomenon is robust to the scale of the learning rate. However, in theorem 2.1, we require the learning rate to stay in a range $[\eta_1, \eta_2]$. Can the authors comment on this necessity in the proof?


d) Is the main message behind section 3.3 that we need the second-order term in NTK for the EoS phenomena? Can the authors comment on how the ratio D/P matters affect theorem 3.1? How will the plots in Figure 3 and Figure 4 change with different D/P values?

Furthermore, in theorem 2.1, we needed a large gap between the top two eigenvalues of Q. Is that somehow related to $\sigma_z$ and $\sigma_J$?

clarity,_quality,_novelty_and_reproducibility: The work is original and of high quality. However, the paper involves a lot of mathematical jargon, which makes it difficult for the reader to understand the main message behind different theorems and experiments. I have pointed out some in the previous section.

summary_of_the_review: Overall, my scores are on the borderline. The mathematical jargons in the paper make it really difficult to understand the main message (and the underlying idea) behind the important sections. Please find my questions above.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper consider a class of predictive models that are quadratic in parameters (equation 1 and 19),  and prove progressive sharpening (section 2.1) and edge of stability (ESO, section 2.2) in two dimension.  The paper also claims that the two properties could be general property in high dimensional non-linear models. 
strength_and_weaknesses: Strength
[+] The paper studied a second order regression models and analyze the progressive sharpening and ESO in details.

Weakness
[-] The paper takes time to follow and some of the organization could be better.
(a) \title{z} is used before the definition, before and after equation (3)
(b) curvature (JJ^\top)  could be defined after the definition of JJ^\top after (3)

clarity,_quality,_novelty_and_reproducibility: The paper study some fundamental property of second order regression.
summary_of_the_review: The paper study some fundamental property of second order regression.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper made an effort towards understanding the edge of stability phenomenon. I think their major observation is that second order approximation is needed to analyze the gradient flow (the prediction is a quadratic function so the loss is a 4-th order function). Then they also propose a simplified quadratic regression model to capture the edge of stability behavior. 

I feel the paper is answering a quite important question but I am unable to get the big picture intuition --- the only two messages i got was (i) looking at 2nd order approximation is the right way to explain edge of stability, and (ii) it requires very heavy computation to even get some simplified case out. 
strength_and_weaknesses: Strength: I believe the authors tackle a quite important open problem related to SGD and the key message of looking at quadratic regression is valuable. 
Weakness: one of those papers you need to sit down and parse the paper multiple times to get the intuition of the technical detail part. 
clarity,_quality,_novelty_and_reproducibility: it is mostly clear. 
summary_of_the_review: it is a strong result but I have low confidence.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper studies the Edge-of-Stability effect using a second order regression model. The authors start with a scalar-valued quadratic model and show that in the case of two-dimensional input it has the EoS behavior in the non-symmetric eigenvalue scenario. After that the authors consider a more general, vector-valued second order regression model. They prove that in the high-dimensional limit and under appropriate random initialization, this model shows progressive sharpening at initialization. Then, the paper discusses the scaling at which the EoS behavior occurs. Finally, the paper shows experiments with CIFAR10 and relates them to preceding theoretical findings.     
strength_and_weaknesses: I like this paper. It is clearly written, gives a concise demonstration of the EoS effect on a toy model, proposes a natural general class of models shown to exhibit EoS, and the theoretical results are connected to the real world CIFAR data.  

One very minor drawback that I see is that experiments with real world data are limited to a single network and data set. 
clarity,_quality,_novelty_and_reproducibility: EoS is a recent and popular topic; there are several concurrent submissions also aiming to elucidate the EoS effect, in particular using somewhat related toy models (e.g. https://openreview.net/forum?id=p7EagBsMAEO, https://openreview.net/forum?id=nhKHA59gXz). However, I think that the present submission is sufficiently distinct from the others.  
 
The appendix provides detailed proofs (I glanced over them but didn't check them) and some further comments on the models considered in the paper.
summary_of_the_review: A good paper without any serious issues.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies the dynamics of a quadratic model trained with quadratic loss. 
The effective dynamics of NTK is derived.
Authors argue that edge of stability behavior in neural networks is correlated with the behavior in quadratic regression models.
strength_and_weaknesses: Strength:

The topic should be interesting to optimization community.

Weakness:

This article tampered with the definition of EOS by changing Hessian into NTK. More specific discussion is in following section.

Many claims is not supported. More specific discussion is in following section.

There is mismatch between experiment and theory even in simple quadratic model.
clarity,_quality,_novelty_and_reproducibility: > gradient descent (GD) trajectories where the maximum eigenvalue of the NTK remains close to the critical value 2/η

> we define edge of stability with respect to the maximum NTK eigenvalue

> this is equivalent to the maximum eigenvalue of the loss Hessian used in Cohen et al. (2022a) as the model converges to a stationary point (Jacot et al., 2020).

This argument appears novel to me.
I searched in Cohen et al. (2022a) and (Jacot et al., 2020), but didn't find any statement on equivalence between Hessian and NTK. 

Next I will show the difference between them.

Consider loss $L(\theta)=\sum_{i=1}^n l_i(f_i(\theta))$, where $f_i:\mathbb{R}^d\to\mathbb{R},l_i:\mathbb{R}\to\mathbb{R}$ the Hessian is $H=\sum_{i=1}^n(\nabla f_i(\theta) l_i'' \nabla f_i(\theta)^\top + l_i'\nabla^2 f_i(\theta) )$, where $\nabla f_i(\theta)$ is a column vector and $\nabla^2 f_i(\theta)$ is a $d$ by $d$ matrix.

On the other hand, NTK is defined as a $n$ by $n$ matrix $\Theta_{i,j}=\nabla f_i(\theta)^\top \nabla f_j(\theta)$.

Clearly, Hessian and NTK are different.

Even if authors wish to establish equivalence to spectrum only, heavy assumptions are needed. First, we need to assume $l_i''=1$ for all $i$, which means we can only use square loss. Second, we need to to make sure $\sum_i l_i' \nabla^2 f_i(\theta)=0$. This is not necessarily true at stationary point, because first order stationary condition only guarantees $\sum_i l_i' \nabla f_i(\theta)=0$.

Besides, I don't think stationary condition should be used at all while studying EOS, because EOS only happens before we reach stationary.

> Figure 1 ... The GD trajectories converge to minima with larger curvature than at initialization ...

The figure doesn't show curvature directly.
It only shows loss in log scale, and it hard for me to see which part has larger curvature.
Thus, it is not clear to me whether GD trajectories really converge to minima with larger curvature.


> Figure 1.

What are the initial points of these GD trajectories?

> we can see that $\operatorname{sign}(\Delta T(0))=\operatorname{sign}\left(T_t(0)-4\right)$, as in Lewkowycz et al. (2020)

Could authors point out which part in Lewkowycz et al. (2020) is relevant?

> so convergence requires strictly decreasing curvature

The reason is not totally clear to me. Could authors provide further explanation?

> Figure 2

Figure 2 middle shows that curvature should first increase, and then decrease and converge to a value that is slightly smaller than critical curvature.

However, Figure 1 left shows first oscillation and then monotone increasing curve.

Why there is such mismatch between theory and experiment?

> which reveals that the spectrum does not shift much ... This suggests that Q doesn’t change much as these EOS dynamics are displayed

In order to constitute a sufficient condition, I believe authors also need to show the eigenvectors doesn't change much.
Is there any intuition why eigenvectors don't need to be verified?

> (Section 2) $y_t =T_t(0)-f_{\tilde{z}}\left(\tilde{z}_t\right)$ (Section 4) $y=\lambda_1\eta-2$... we see that the two-step dynamics of $z_1$ is well approximated by $2yz$ (Figure 6, middle). This is the same form that the dynamics of $\tilde{z}$ takes in our simplified model.

The definitions of $y$ in theory and in experiment are very different. Is there any correspondence between two definitions?
summary_of_the_review: This paper focuses on quadratic model with quadratic loss and derive effective dynamics of loss and NTK for the model.
The topic is interesting.
However, there are many unjustified claims. Moreover, the experiments and theory doesn't match well.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The submission is about developing an understanding of the recently observed progressive sharpening and edge of stability phenomena. The authors focus on second-order regression models (i.e. models which are quadratic in their parameters) with two-dimensional input to study the question analytically, and show empirically that these two properties could generally be present in high-dimensional non-linear models.

While the overall question raised can potentially have some impact, unfortunately, the submission in its current form would require significant revision before publication: 'the main messages are not clear at all', the reviewers were 'unable to get the big picture' and to decode the key messages of the work; my own reading also confirms this rather bumpy experience.
justification_for_why_not_higher_score:  
justification_for_why_not_lower_score:
Decision: Reject