Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper aims at gaining more understanding of the Edge of Stability phenomenon. Some theoretical understanding was obtained via Theorem 1, which assumes a quadratic loss function. Although EoS does not manifest for quadratic loss, this theorem was then used to motivate empirical claims. Such claims are backed by experiments.
strength_and_weaknesses: Strengths:

(1) Problems studied in this paper are very interesting.

(2) Empirical investigations are detailed.

Weaknesses:

The demonstration is still largely empirical, and I wish the theoretical component could be stronger. Some reasons are: 

(1) some of the claims appear to be rather general, but it is actually known that EoS does not occur for all loss functions. I’d appreciate it very much if the authors could be more specific about their conjectures (which I nevertheless found interesting), such as the hypothesized conditions under which they could be true.

(2) The abstract suggests the question of “why the sharpness is somewhat larger than 2/(learning rate)” will be answered. Could the answer be more explicitly and concisely provided? Is there any quantification of how much larger it is than 2/(learning rate)? Is it loss function dependent? In fact, I wonder how the authors relate this claim (and other empirical observations) to the recent line of analytical work based on matrix factorization, e.g., [Wang et al. Large Learning Rate Tames Homogeneity. ICLR 22], [Zhu et al. Understanding Edge-of-Stability Training Dynamics with a Minimalist Example. arXiv]. The latter is concurrent so it is not a missing reference, but I’m curious if there is any contradiction: for example, these results seem to give sharpness not larger than 2/(learning rate). Although the authors seem unaware, theories in these papers do seem to be aligned with many of the empirical observations made here. However, do they align with all observations? It could be that neither is wrong, and instead it is just a matter of different loss functions. I wish these aspects could be explored more.
clarity,_quality,_novelty_and_reproducibility: Empirical results are of good quality and originality, although related work from 2021 on might have been missed. Clarity overall is okay, but I recommend the authors to itemize and specify their main findings and contributions in a concise but quantitative fashion.
summary_of_the_review: Overall, this is an interesting paper and a helpful contribution toward an understanding of EoS. I have some concerns at this moment, but my score can be changed.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper provides a fine-grained analysis of the edge of stability (EoS) phenomenon and in particular, their characterization also applies to SGD. In my understanding, the new characterization not only uses the largest eigenvalue of Hessian, which corresponds to the sharpest direction but also considers the curvature along other directions. To this end, an interaction-aware sharpness is defined. The numerical experiments show that the characterization is quite "accurate" and the authors provide an interesting application in explaining the linear and saturating scaling rule in large-batch training. 
strength_and_weaknesses: ### Strong point

The derivation of new characterization is simple but powerful. The new sharpness also seems to capture the EoS phenomenon more precisely. The application of explaining the learning rate rescaling in large-batch training is consistent with empirical observations, which might be practically relevant. In general, I think this paper makes some interesting observations and I believe they are useful for further study on relevant topics. 


----
### Weak point

However, I feel that this paper is written in a hurry and the work is still somewhat preliminary at this stage. Listed below are a few concerns in my mind. 

1. **The discussions of prior works are unfair**

   The phenomenon of  EoS was first observed by (Wu et al., 2018) at the end of training; (Jastrze ̨bski et al., 2020) further observed the progressive sharpening phenomenon in training neural nets. (Cohen et al., 2021) followed these works by providing a systematical investigation of these phenomena and also additionally found the non-monotonic convergence at EoS.  All three works are crucially important in this line of research. Only attributing the discovery of EoS to (Cohen et al., 2021) is unfair (at least in my opinion). 		

2.  **The explanation of implicit interaction regularization is quite hand-waving and not convincing**
   - First, the definition of $\rho_b$ (a concentration measure of batch gradient)  is the same as the gradient diversity defined in (Yin et al., 2018)  and is never mentioned. 
   - I find equation  (16) misleading since both sides depend on where the iterate locates. In iterations, both sides keep changing. The statement that *$\|H\|_{S_b}$ is implicitly regularized and bounded to be less than $2\rho_b/\eta$* is technically correct. But it implies nothing since both sides keep changing. For example, we cannot claim that SGD tends to find solutions with smaller $\|H\|_{S_b}$ since $\rho_b$ is not a constant. 

 	3. In Section 5, I do not understand why keeping $2\rho_b/\eta$ to be constant is a good choice for generalization. This is never explained. 



### Other comments

1.  In the second paragraph, the authors ask three questions. But it seems that this paper only answers the third one. Therefore, claiming "we provide a new characterization of the EoS for SGD, which can serve as an answer to the above questions" is not appropriate. 

2.  In Section 2, I suggest focusing on the case of sampling with replacement for simplicity. Otherwise, the statement is much more complicated and no new insights are brought. 

3.  In Section 3, the authors claim that existing works using tr(HS_b) make some additional assumptions, but they do not. In my opinion, this claim is quite misleading, since this paper also needs to make some assumptions, e.g., the validity of local quadratic approximation. In my opinion, the real difference is that this paper uses this quantity to analyze EoS, which is not carried out previously.  

4.  In Figure 1, I do not understand why the authors only mark the endpoint with 'x' for cross-entropy loss. Also, it should be clarified in the caption the meaning of MSE and CE. 

5. In Theorem 1, the batch gradient never follows a normal distribution, thus the Gaussian assumption is too strong. Also, I do not understand why  (8) and (9) are interesting.

6. In the definition of the new edge (11), I think the author should explain the intuitive difference between $||H||_{S_n}$ and $||H||$. In my understanding, the former considers the curvatures in typical directions but the latter only considers the curvature in the sharpness direction:

$$
\qquad ||H||_{S_n} = \frac{\theta^TH^2\theta}{\theta^T H \theta}, \qquad ||H|| = \sup \frac{\theta^TH^2\theta}{\theta^T H \theta},
$$
where the supremum is taken wrt the direction theta.

8. In Figure 2, what do you mean by **overestimation**? In addition, are the "iteratre enter the EoS" and "in the unstable region" the same thing?

9. In Equations (13) and (14) and Theorem 2, suddenly momentum GD is studied. I do not understand why? Do the authors want to say the EoS is the same as vanilla (S)GD? Theorem 2 is also repeatedly referred to argue the convergence of directions, but it is stated for momentum GD.  In addition, in Theorem 2, what is $\lambda_i$? What do you mean by quadratic $L$? Is each sample loss also quadratic?




---
### Reference

[1] Yin et al., Gradient diversity: a key ingredient for scalable distributed learning

[2] Wu et al., How SGD selects the global minima in over-parameterized learning: A dynamical stability perspective

[3] Jastrzebski et al.,The break-even point on optimization trajectories of deep neural networks
clarity,_quality,_novelty_and_reproducibility: The paper is hard to read and the material is not well-organized. The analysis is interesting but not well explained 
summary_of_the_review: The more precise characterization of EoS and the empirical findings are interesting, but this work is still somewhat preliminary and more work is needed. 


=====
The author's response partially addressed my concern. I generally think that the analysis and numerical experiments are useful for future study on relevant topics. Hence, I increased my score to 6.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: In this paper, the authors proposed a novel characterization of the "edge of stability (EoS)" phenomenon, referred to as the "interaction-aware-sharpness",  for both gradient descent (GD) and its stochastic variant SGD.
The proposed theory is of particular interest in its ability to provide novel and more precise insight into the EoS of SGD. Based on the theory, the authors further proposed a novel scaling rule (Linear and Saturation Scaling rule, LSSR) on the learning rate and SGD batch size, which extends the popular linear scaling rule (LSR).
Numerical experiments on a few (not so deep) neural networks and across a few widely used datasets were provided to empirically support the theoretical results.
strength_and_weaknesses: **Strength**: the paper is in general well written and the main ideas are easy to follow. The problem under study is important and the proposed theory provides novel insights and is of interest. The numerical experiments look compelling.

**Weaknesses**: the theoretical/technical depth of the paper is somewhat limited, the empirical contribution is rather significant, though. The limitations of the proposed theory/analysis are not sufficiently discussed.


clarity,_quality,_novelty_and_reproducibility: **Clarity**: the paper is in general well written and easy to follow. (It is a bit awkward to first discuss SGD in Theorem 1 and then generalized momentum GD in Theorem 2, though)

**Quality and Novelty**: novel and significant enough to be published, from both theoretical and empirical perspectives.

**Reproducibility**: good
summary_of_the_review: The paper is in general well written and proposes an interesting and novel viewpoint of the EoS for SGD.
I do not see any major flaws in the paper. 

Detailed comments:
* Definition 2: the term "concentration measure" is used without providing more context. This can be misleading to some readers with probability or statistics background who may be more familiar with the term "concentration of measure".
* It would be helpful to discuss the limitation of the proposed analysis (including the LSSR), from both theoretical and empirical perspectives possibly.
* can one go beyond SGD to more involved settings? It would be of interest to have a short discussion on this point.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper proposes a new edge of stability phenomenon that applies to mini-batch stochastic gradient descent. This is achieved through a sharpness measure defined as Interaction-Aware Sharpness which measures the sharpness with respect to the batch gradient covariance. The reviewers discussed the paper in detail and while there were questions regarding the sufficiency of the experiments in terms of proving the hypothesis of the paper, the reviewers eventually agreed upon that while they can be improved they seem sufficient to support the claims. The reviewers also appreciated the core hypothesis of the paper and felt that it advances the community's knowledge in the newly emerging idea of the edge of stability. Overall I recommend acceptance based on the scores of the reviewers.
justification_for_why_not_higher_score: The reviewers agree that the paper is a borderline paper however all three reviewers agreed unanimously that the positives going for the paper outweigh the negatives in the paper. The paper's experimentation can be more thorough and the presentation could be a lot more cogent. 
justification_for_why_not_lower_score: The reviewers agreed unanimously that the paper will be useful to the community especially expanding our understanding of the emerging phenomenon of edge of stability in the minibatch regime.
Decision: Accept: poster