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 paper provides an explanation of the phenomenon of SGD selecting flat minima by relating the noise structure of SGD to its linear stability. In over-parameterized models with the square loss, it shows, exploiting the geometry awareness of SGD noise (that is provable for linear networks and RFMs), that the Hessian of an accessible minimum for SGD is bounded by a term depending only on the batch size an the learning rate.
strengths_and_weaknesses: Strenghts:
- the topic of study is relevant
- the quantitative analysis is extensive, going from simple models s.t. RFMs and linear models to modern deep neural networks
- the paper is well written and clear
questions: - figure 3: are the results robust w.r.t. other flatness notions?
- figure 5, it could be useful to add VGG11 to the right panel
- the paragraph "notion of flatness" at l110 may be made more clear. Also the role of the norm in the flatness notions is not clear. also, size-independence plays an important role

Minors:
- l96: initiated studied 
limitations: The role of overparameterization and the specific loss type (quadratic) are not discussed

potential negative societal impact are not discussed
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The authors of the paper present the following contributions:
- They provide an in-depth study of the importance of the SGD noise both in term of geometry and in terms of scale.
- They show that, if a certain alignment property is satisfied, a global minimum is linearly stable if and only if the Froebinius norm of the Hessian at optimum is upper bounded by constant independent of model and sample size  
strengths_and_weaknesses: ### **Strengths**

- The first thing I have to say is that the paper is very well written. The exposition is clearly conducted and all assumptions and estimations are detailed, announced and commented. One may or may not validate the authors' noise model, but at least it is not hidden (as too often) and keys are given to appreciate the results
- The main strength and difference of the article is the particular attention given on the noise model both in terms of noise and of geometry. From this, even if the results seem easy to prove, the exposition is cristal clear and more convincing with the previous literature.

### **Weaknesses**

- There are a lot of results and approximation stated in the article, but overall, the crux of the paper is two show that the approximations of the equation (2) at the beginning of the paper is valid: that is to say that either $\alpha, \beta$ or $\mu$ are close to $1$. If Figure 1 is  pretty convincing from this point of view, I have to say that Figure 5 is not as the scale of these constant can be (way) smaller than 1. I would really appreciate if the authors comment more on this point because the sentence "*This comparison suggests that the alignment strength significantly depends on the intrinsic complexity of the problem, (nearly) independent of the model size*" is not very convincing.
- This is a minor weakness but overall, even if the paper is not overselling and clear about their study, I am still not convinced by the stability argument of SGD. Indeed, on never see plots like Figure 4 in real training dynamics of neural networks and this suggests -at least to me- that the taking into account the noise is not a stability issue but a dynamical one. Maybe the authors could comment a bit on this fact. 


### **Minor typos**

- lign 65: $\lambda_i$ and not $\lambda_1$
- lign 227: In **the** current paper
- ligns after 235: there is a confusion between $v$ and $\nu$
 

questions: In my opinion, the crux of the paper is to give a precise (or experimental) sense to the approximations of equation (2). Maybe the authors could try to provide estimation of how far each approximation is to the real covariance: 
-  First regarding the influence of the loss
- Second regarding the independence between $\nabla f(x_i, \theta)$ and $L_i$

This corresponds to constants $\mu_1$ and $\mu_2$ defined in the paper but no experiments are shown concerning these variables.
limitations: I use this paragraph to conclude as I already discussed the limitations on the previous boxes. The paper tries to conduct both theoretical and experimental explanations of the wide minima selection of SGD. I'll weakly accept the paper for its clarity and detail about the noise. To raise my score, I would like the authors to justify more the fact that the escaping phenomenon is important and the alignment phenomenon of the covariance structures.
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: Deep learning folklore holds that the gradient noise in SGD causes it to prefer "flat minima."  An important open question in deep learning theory is to make this folklore mathematically precise.  Taking a step in that direction, this paper describes a mechanism by which SGD escapes exponentially quickly from minima where the Frobenius norm of the Hessian is too large.  This mechanism is orthogonal to the curvature-driven process that causes full-batch gradient descent to escape from minima where the Hessian spectral norm exceeds 2 / step size. 
strengths_and_weaknesses: Strengths:

  -- To the best of my knowledge, the idea of an exponentially fast escape that is driven purely by noise is novel.  It is interesting that a required condition for this phenomenon (noise magnitude proportional to loss value) is provably satisfied in linear nets and random feature models.

Weaknesses:

  --  The analysis only yields a sufficient condition for instability, not a necessary-and-sufficient condition.

  -- While in general the stability will depend on both the full-batch component and the noise component, the analysis here considers only the noise component in isolation.  Accounting for both simultaneously is going to be hard, so I don't begrudge the authors for this simplification. 

  -- I think the paper would be clearer if the authors first presented the escape analysis (section 3) before the sufficient conditions (section 2).  When I read section 2, I spent a lot of time scratching my head wondering why alpha, beta, and mu are defined the way they are.  Later, when I got to section 3, I realized that \mu is precisely what is needed to trigger exponentially fast escape.

questions: -- I didn't understand why the submission keeps mentioning that the flatness is independent of model size.  Could the authors clarify why this is an important point?

-- Are the authors sure that the linear stability analysis is only valid near a local minimum?  I ask because in the full-batch case, the curvature-driven escape when sharpness exceeds 2 / (step size) is valid generically, not just near a local minimum.

-- I wonder if the bound would be tighter on the real networks (VGG, ResNet) if you considered a batch size smaller than 64.  Intuitively, I would expect the noise-driven escape to dominate when the batch size is small.
limitations: Yes, the authors adequately addressed the limitations.
review_title: null

Meta-review: metareview: The paper investigates an important topic of why SGD converges to flat minima.
Overall the reviewers felt that this is a nicely written paper with a nice contribution to the state of the art.



confidence: Certain
Decision: Accept