Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
review_content: summary: The paper studies the instability in SGD optimization dynamics (edge of stability) and how that impacts generalization. In particular, the authors propose the idea of interaction-aware sharpness, which I believe is original. Based on a definition of implicit interaction regularization, the authors propose the linear and saturation learning rate scaling rule (LSSR). Most of the findings are supported by empirical evidences but theoretical support is at an intuitive level.
strengths_and_weaknesses: Strengths:
 * The idea of interaction-aware sharpness seems to be original.
 * Empirical evidence to support the self-regulation of interaction-aware sharpness around the edge of stability.
 * Intuituive argument for learning rate scaling.

Weaknesses:
 * Learning rate scaling only supported by a vague argument and empirical evidence.
 * Weak connection between the concepts proposed in the paper and generalization.
 * Nothing in the theory related to neural networks.
questions: * My feeling is that the current theoretical setup may explain the gap between batch optimization and minibatch optimization but that is not the same as explaining generalization because generalization depends on the model class size. Can you agree or disagre?
* More specifically, do I understand correctly that the theoretical setup does not assume anywhere that the model is a neural network? Then why are all the experiments on neural networks?
* Can we motivate the linear and saturation scaling rule better? I am not sure why keeping the right-hand side of Eq. (11) constant leads to optimal scaling.
limitations: N/A
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: The authors explore the notion of edge of stability for SGD dynamics, they introduce some quantities and explain / illustrate why they make sense for the understanding of the dynamics. They then propose a novel "linear and saturation scaline rule" and provide experimental support.
strengths_and_weaknesses: Overall I believe there are some interesting ideas and observations. For example Figure 5 (right) (which illustrates the linear and saturation scaling rule) is rather convincing. Some quantities which are introduction seem to make sense. However the paper and the claims are not at all convincing enough. The abstract and introduction are very superficial and it is not even clear what the authors want to prove / show. The related work is neglected. 

I am also bothered by some very vague and imprecise claims and sentences. The title to start with: "Implicitly regularized interaction between SGD and the loss landscape geometry". I don't understand what this means: what is a "regularised interaction" ? 
Then in the text: "we find that SGD induces an implicit regularization on the interaction between the gradient distribution and the loss landscape geometry.", "we find that SGD implicitly regularizes the interaction-aware sharpness". I do not manage to understand these sentences, they are very vague and the meaning is not clear at all. 

The fact that the paper is not well written with very unprecise statements and claims makes me heavily doubt on the sanity and significance of the presented results. In the following questions I give a few examples to support my opinion.
questions: - eq (3): over what are you taking the expectation ? if it is the full expectation then you should also have $\mathbb{E}[L_t]$, I guess you are taking the conditional expectation but this is not clear. 
- line 96: a bit weird to name a set a "regime". It would also be clearer to keep the $\theta$ index in $H$: $H_\theta$, to make clear that the hessian depends on $\theta$.
- unclear experiments in fig 1: what is the precise setting ? what dataset ?
- l110: " This result implies that the training loss L(θ) is approximately locally quadratic, i.e., ε ≈ 0, in the early phase." Why and what does this mean ? isn't any twice differentiable function approximately locally quadratic ?
- "We hypothesise that due to this non-quadraticity of the training loss, the iterate is discouraged from staying within the unstable regime." I don't see why this is due to non-quadraticity. If you want to optimise $f(x, y) = |y| x^2$ for example, which is always "locally quadratic": then for a large step-size, the iterates are "discouraged from staying within the unstable regime" too.
- Figure 3: what is $\Delta L$ ?
- Figure 4: very hard to read labels, especially in fig (d)
- equation 12: "if $b$ is small", "if $b$ is large": how small ? how large ?
limitations: N/A
review_title: null

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: This paper makes several contributions:
 1.  The authors propose a new characterization of 'edge of stability' which is said to improve over the original characterization from Cohen et al. (2021) in that it (1) fits full-batch GD better, and (2) generalizes to SGD.  Specifically, whereas the original characterization is that the sharpness (maximum Hessian eigenvalue) hovers **just above** the value $2/\eta$, the authors propose characterizing the EoS as a regime in which the expected loss difference that is predicted by a quadratic taylor approximation hovers **around** the value zero (here, the expectation is wrt randomness in minibatch sampling).  For SGD, this condition comes out to $\frac{\text{tr}(H S_b)}{\|g\|^2} \approx \frac{2}{\eta}$, where g is the (full-batch) gradient, H is the Hessian, and $S_b$ is the second moment matrix of minibatch gradients.  For full-batch GD, the condition reduces to $\frac{g^T H g}{\|g\|^2} \approx \frac{2}{\eta}$.  In the case of full-batch GD, the authors argue that their condition $\frac{g^T H g}{\|g\|^2} \approx \frac{2}{\eta}$ improves over the original condition $\|H\|_2 \gtrapprox 2/\eta $ in that  $\frac{g^T H g}{\|g\|^2}$ empirically hovers right around $2/\eta$ (Figure 4), whereas there is usually a gap between $\|H\|_2$ and  $2/\eta $.  More importantly, it is currently an open question how the 'edge of stability' phenomenon generalizes to SGD, and the authors argue that their condition $\frac{\text{tr}(H S_b)}{\|g\|^2} \approx \frac{2}{\eta}$ holds during SGD. 
  
 2.  The authors investigate the behavior of gradient descent at the EoS (Figures 1-3).   They find, essentially, that gradient descent is leaping back and forth across an asymmetric valley (https://arxiv.org/abs/1902.00744).  At every iteration where  $\frac{g^T H g}{\|g\|^2}$ is above $2/\eta$, it dips below $2/\eta$ on the next step.  At every iteration where $\frac{g^T H g}{\|g\|^2}$ is below $2/\eta$, it rises above $2/\eta$ on the next step.  Note that a similar point has been made (with no experiments) in the contemporaneous work of Chen & Bruna (https://arxiv.org/abs/2206.04172).

 3.  The authors propose a new scaling rule that describes how the linear rate ought to be scaled with the batch size in order to preserve the same implicit regularization.  Namely, the authors suggest that two training runs have the same implicit regularization whenever $\text{tr}(S_b) / [\eta \| g\|^2]$ is the same, and they present evidence (Figure 5) in support of their hypothesis.  Their scaling rule reduces to the well-known linear scaling rule in the limit of small batches, and reduces to "no scaling" in the limit of large batches.
strengths_and_weaknesses: In what follows, I will reference the contributions I listed above by their numbers.

- Weakness of contribution #1: I could be wrong, but I don't think the new EoS characterization will generalize to momentum gradient descent (either with Polyak-style or Nesterov-style momentum).  In the Cohen et al EoS paper, it is intuitively clear why the sharpness should hover just above $2/\eta$: if the training objective is modeled by its quadratic Taylor approximation, we see that gradient descent cannot linger for long in any region where the sharpness exceeds $2/\eta$, because it will oscillate with exponentially growing magnitude in a certain direction until it leaves the region.  The extensions in that paper to Nesterov and Polyak momentum are based on the same reasoning.  By contrast, the underlying logic behind the new proposed EoS characterization (which is based on the idea that the loss is always non-monotonic) is less clear to me, and one consequence is that I don't see how it can be generalized to momentum.

- Strength of contribution #1: the proposed extension of EoS to SGD is interesting (note that it's basically a quadratic Taylor approximation version of the phenomenon reported in Cohen et al (2021) appendix H).  Nothing has been published in the literature addressing the question of how EoS might generalize to SGD, so any experimental result that seems to hold consistently across a wide range of networks is valuable.

- Strength of contribution #2: I think that these experiments will be useful for people interested in how gradient descent manages to remain semi-stable at the EoS.

- Weakness of contribution #3: both $\text{tr}(S_b)$ and $\|g\|^2$ will vary over the course of training, and I don't see any reason why their ratio should remain constant.  Thus, the scaling rule is not even well-defined.


questions: - In Figure 5, where does the yellow dotted line come from? 

- The plots of $||H||$ in Figure 31 look weird to me -- typically, the sharpness along the optimization trajectory is smaller when the batch size is smaller.  Could there be an error here?

limitations: Yes
review_title: null

Meta-review: metareview: While this paper presents a series of interesting observation, e.g., self regularization around the edge of stability and learning rate scaling, in my view it fails to communicate the scientific value of the work in a coherent way. For example, I find it puzzling that the main result of the paper "implicitly regularized interaction" is stated as a definition (Def. 4) instead of a theorem, proposition, or a hypothesis. During the discussion, I realized that the authors use the word "regularization" in a slightly non-standard way. My questions to the authors are: (1) what does it mean to regularize the interaction? and (2) how does it relate to generalization?
confidence: Certain
Decision: Reject