Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper develops a density diffusion theory (DDT) to reveal how minima selection quantitatively depends on the minima sharpness and the hyperparameters. In particular, this paper theoretically and empirically prove that SGD favors flat minima exponentially more than sharp minima, while gradient descent (GD) with injected white noise favors flat minima only polynormially more than sharp minima.

This paper is the first to theoretically and empirically prove that SGD favors flat minima exponentially more than sharp minima, which is novel. Furthermore, the paper is well written.

Some shortcomings are listed as follows:

First, the concept “valley” is frequently used in this paper, but it seems that no formal definition has been given for “valley”.

Second, Assumption 1 assumes that the function value near $\theta^*$ can be estimated from the second order Taylor approximation. But when the Hessian matrix changes fast, the second order Taylor approximation will have large error and hence Assumption 1 will not be reasonable. Similarly, in Theorem 3.2, when the Hessian matrices $H_a$, $H_b$ and $\Delta L$ change fast, they cannot well reflect the flatness of minima. 

----------------------
After rebuttal:
I thank the authors'  clarification. I keep my rating.
review_title: The proof is novel, but some assumptions need further discussion.

final_score: rating: 6: Marginally above acceptance threshold
review_content: The paper develops a density diffusion theory to reveal how minima selection quantitatively depends on the minima sharpness and the hyperparameters. It shows theoretically and empirically that SGD favors flat minima exponentially more than sharp minima. In particular, the paper analyzed the dependence of mean escape time from the valley with the Hessians on local minima and saddle points for both SGD and SGLD, and revealed the exponential dependence of the mean escape time with the sharpness. Experiments on real-world data have verified the theoretical results on the mean escape time. 


1. The main contribution of the paper is the exact characterization of the dependence of mean escape time with Hessians. And the exponential dependence on the sharpness seems to be new, with good experimental validations. Could the authors compare their theoretical results with that in the asymmetric valley paper? Are we sure the eigenvalues of Hessians are the right quantities to look at here? 


2. Assumption 3 appears very vague to me: what is the mathematical formulation for a small gradient noise? Is there a threshold to determine when it is small enough such that the theory can be applied? With this simplification, the authors can greatly simplify the integration using second-order Taylor expansion around the critical points. However, the conclusion only depends on the Hessian on the minima and the saddle point instead of the Hessian information along the optimization path, which is counter-intuitive to me. I would like to see some discussion on why it is the case for mean escape time.


3. Proposition 1 seems to be an interesting result in the distribution of stationary points. However, in high dimension cases when we have multiple valleys around, how do we define the saddle point exactly? Is it the closest saddle point for all neighborhoods? It would also be interesting to see experiments that validate the distribution of stationary points.

The writing a bit sloppy; in some \sum the indices below the sum and in the expression are not consistent, and there are also weird notations such as Fisher(theta). 

I read the authors' feedback and appreciate the clarifications. I keep my score. 
review_title: Interesting toy model and experiments, though theory is a bit far away from practice

final_score: rating: 7: Good paper, accept
review_content: The authors analysed the behavior of stochastic gradient descent (SGD) algorithm in non-convex settings and compare the results with Langevin dynamics, namely gradient descent with additional isotropic noise. 
In the paper the problem of escaping from a minimum (the old Kramers escape problem) is analysed in the light of SGD, characterizing the SGD dynamics using stochastic differential equations. 

This approach has already been analysed in the literature and the authors give a good introduction to previous works. 

The main result of the paper is the characterization of mean escape time from the basin for SGD (Thm.3.2) and Langevin dynamics (Thm.3.1). The result shows how SGD exploits the anisotropicity of the landscape to favor flat minima.

**Points that needs to be clarified :**

The authors comments on the effect of large(er) learning rate on the overall escape rate, but in that case the analysis that is based on continuous time equations will not generalize straightforwardly. 

It is known in the literature that gradient descent evolves in a tiny subspace dominated by the largest eigenvectors. In the final remarks ("Low dimensional diffusion") it seems that this is a feature of SGD, but actually in the paper that they mention [Gur-Ari et al. 2018] the result shows that also gradient descent have the same feature. 

**Additional comments :**

In the paper it seems that there is no dependence on the space dimension. Is that really so or is it hidden in some of the variables? I find surprising that probability of escaping from a high-dimensional basin is the same as in the low dimensional case.

The images needs larger fonts. It is impossible to read them in the printed paper and even in the pdf one needs to zoom very closely to the image to read them.

In Fig.5 and 6, the authors make experiments using neural networks. The details on the network are reported on the appendix but should be reported (maybe schematically) in the main paper instead. They are very relevant and the reader should not be forced to look and the end of the appendix to find them.

Typo after : "The mean escape time analysis of SGLD"

review_title: A good submission with some clarifications needed

final_score: rating: 7: Good paper, accept
review_content: Overview: The paper aims to explain how SGD converges to flatter minima using density diffusion theory and shows the effects of Hessian-dependent covariance noise versus injected white noise. Clearly, the direction is very interesting and relevant and I think this is a good paper with a clear analysis and numerics which validate the theory. 

Questions, comments and ideas:
- I like the fact that this work shows how Hessian-dependent covariance noise compares to white noise. I had seen some empirical results on this (as you also mention), so it is very nice to see some theoretical validation for this. I also think this paper improves on previous related other research (e.g. the Levy noise analysis). 
- The analysis and assumptions are clear. Assumptions 1-3 are of course a bit restrictive but as you also mention classical and needed to facilitate the analysis. 
- What are the implications of Assumption 1? How does it depend on the network architecture?
- How does this work relate to the idea that Hessians can be rescaled to create arbitrarily sharp/flat minima? More generally, is flatness still the right concept to describe generalizability of the model? 
- The numerical results are for a two-layer network? What happens if we were to increase depth or width? 
- Perhaps I missed this but how are the multiple possible escape paths accounted for in the numerical results? Also what is the effect of having multiple escape paths and how does this depend on the model?
- In your opinion, do the results hold across different loss functions? In my own experience I have observed differences in MSE loss and classification loss. 
review_title: Decent paper with good theory and numerics

Meta-review: The paper analyzes the behavior of SGD using diffusion theory. They focus on the problem of escaping from a minimum (Kramers escape problem) and derive the escape time of continuous-time SGD and Langevin dynamics. The analysis is done under various assumptions which although might not always hold in practice do not seem completely unreasonable and have been used in prior work. Overall, this is a valuable contribution which is connected to some active research questions regarding the flatness of minima found by SGD (with potential connections to generalization). I would advise the authors to improve the quality of the writing and address other problems raised by the reviewers. I think this would help the paper maximize its impact.
Decision: Accept (Poster)