Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper considers the rate at which the SGD iterations will escape the valley around a local minimum. Under some approximation assumptions, this paper shows that the SGD noise covariance is highly structured as it aligns with the Hessian at the local minimum in the immediate vicinity. By considering the Ito SDE with the approximate SGD noise covariance and through a random change of time scale, the the Langevin equation on the loss landscape is transformed to that on the logarithmic loss landscape, but with a simpler additive noise. Such a logarithmized loss landscape is then exploited to derive the escape rate of SGD from a local minimum.
main_review: Strengths:
1. Overall, this paper is well written and easy to follow. The contribution of this paper is clearly presented.
2. To the best of my knowledge, the escape rate analysis of the SGD under the logarithmized loss landscape is novel as it partially explains why SGD prefers ﬂat minima with low effective dimensions.

Weakness:
1. There is a lack of clear definition of "escape rate". While I can somewhat guess the meaning of this quantity, I would prefer this critical concept to the explicitly and rigorously defined. 
2. I also did not see a clear statement/reference of the escape rate (16). Maybe it is trivial to the authors, but I think for the broader audience, it would be very helpful if more reference/discuss could be included. I could not follow the discussion for the multidimensional case as well for the same reason.
3. In section 3.2, when the change of time scale is performed, are we still analyzing the (continuous time limit of) SGD iterates? I could not understand the meaning of the random time change from $t$ to $\tau$ as the loss $L$ is involved in (14). If we understand the variable $t$ as time, what is the variable $\tau$?

I think this paper is potentially important to the understanding of the bias of SGD, but I cannot fully comprehend the discussion in section 4.
summary_of_the_review: A potentially novel perspective for understanding the bias of SGD, but more discussion on the preliminary results are needed for non-expert readers to understand the derivation.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper characterizes the escape rate of SGD for the mean-square loss via the perspective of SDE. 
main_review: The paper gives an interesting characterization of the covariance matrix of SGD (note the noise due to data subsampling is structured) and uses a SDE persective, with the corresponding covariance to dervie power-law escape rates of SGD. The paper provides an intuitive introduction to the theoretical understanding of the papers and good sectional clarity in the way main concepts are presented.

However, the paper does not clearly define a lot of the variables used (such as the covariance matrix Sigma, which is a central quantity and deserves its own line) and much approximations are justified via empirical (and not mathematical) reasons. It's hard to understand what exactly is the novelty and main contribution of the paper, since many steps in the derivations are cited. It seems like the application of existing techniques on a restrictive class of functions (with mean-squared loss) may be somewhat interesting, but I'm unclear why (it's not clearly stated in the introduction).  Furthermore, the escape rate of SGD is with respect to a local minima, theta^*, so it is unclear how you define theta^* when it is not a global minima.


summary_of_the_review: Due to the lack of novelty and the use of empirical justifications/lack of rigorous definitions, I would recommend a significant rewrite.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies the behavior of SGD around the minimum. Unlike many other works that simply treat SGD noise as a fixed noise, the authors characterizes the location-dependence of SGD noise, which gives drastically different escaping behavior. By some simplification of the noise covariance matrix, the authors are able to formulate an SGD with isotropic noise with a time change. The new SDE is a dynamics on the log-loss landscape with a simple additive noise. With this result, the escape rate and stationary distributions are derived, depending polynomially on the loss, instead of exponentially. Numerical experiments are conducted to justify the assumptions made in the analysis, and verify the theoretical conclusions in the case of linear regression.
main_review: This paper studies the linear dependency of SGD noise with the loss. Theoretically, this linear dependency comes from a simplification of the noise covariance matrix. Numerically, it is verified for neural network models. With the linear dependency, SGD is formulated as a process with isotropic noise on the landscape of log-loss. Thus, the escape of SGD from minimum no longer depends exponentially on the barrier height. Rather, it depends polynomially on the height. Further, the escape rate depends on the effective non-vanishing dimension of the landscape. The connection of the stability of SGD around minima with the effective dimension is novel. 

This paper is well written and well organized. Though the idea of studying the location-dependent, anisotropic noise of SGD is not new, this paper proposes a new approach to the problem by smartly simplify the noise covariance. The major concern of the reviewer is the lack of numerical support to the power law escape rate and stationary distribution for nonlinear models. Currently, models used in figure 3 is a linear regression. Is it possible to conduct similar experiments for nonlinear models such as neural networks? Will the results be different? I am willing to increase the score if strong numerical results are provided. 

Some minor comments are:
1. In page 4, below equation (11), the authors mentioned "the last term in equation (11) does not contribute to outliers of Hessians". Could the authors provide some explanations? Also, it is good to explain what is an outlier of the Hessian. (though later we will know it means nonzero eigenvalues of the Hessian).

2. In page 6, above equation (20), it says "we assume anisotropy of the SGD noise within this n-dimensional space is not relevant". Why it is not relevant? The nonzero eigenvalues of Hessian can vary a lot, giving quite different noise strength along different directions. Could the authors provide justifications (either theoretically or numerically), that the behavior is not changed by considering an isotropic noise here. 
summary_of_the_review: This paper gives more realistic mathematical characterization of SGD's behavior around minima, by studying the location-dependence of SGD noise. The noise covariance is simplified in a smart way (with numerical justification) so that SGD dynamics can be formulated as a simple diffusion process on a log-loss landscape. Then, escape rate and stationary distribution are derived depending on a power law, instead of an exponential law.
review_title: null

Meta-review: The paper studies rate at which SGD escapes local minima and provides a potential justification for the "flat minima" observation. 
Reviewers agree that the paper studies an interesting problem and provides a nice result. But it seems like that paper in it's current shape is not ready for publication at ICLR. Issue is that the paper's writing is not up to bar, and requires a fair bit of work. In particular, the paper doesn't define the key quantities formally, doesn't provide all the assumptions in one place and justify why they might be reasonable. Finally, it would be great if the final result about escape rate is provided clearly with a self contained theorem/lemma that define/describe most of the key quantities in the rate.
Decision: Reject