Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper proposes power-law dynamic of SGD which considers state-dependent noise. The power-law distributed derived from this  dynamic explains the heavy-tailed distribution of parameters trained by SGD. Besides, this dynamic also shows efficiency of escaping local minima.

Concerns:
1. The proof of theorem 2 is not provided in the appendix. But I doubt if C(w) is well-defined. It is not clear how w* is selected considering there are multiple local minima. It does not make sense to me if w* is fixed when taking x-->\infty, as the quadratic approximation should be used in the neighborhood of w*. 

2. The escaping efficiency of the power-law dynamic is only analyzed in low-dimension case. I wonder how if performs in high-dimensional space. Does it provide more benefits than Langevin/alpha-stable dynamic in the expense of calculating sigma_g and sigma_H.

Minor comments:
1. I think  [Li et al., 2017] also proposed state-dependent noise in Theorem 1.
review_title: Review of Dynamic of Stochastic Gradient Descent with State-dependent Noise 

final_score: rating: 6: Marginally above acceptance threshold
review_content: ### Summary
This paper proposes an analysis for an approximate dynamic of SGD which captures the heavy-tailed noise distributions seen practically at local minima. The authors derive this new dynamic (which they call Power-law dynamic) using basic principles and the assumption that the noise variance depends on the state. The dynamics becomes a modified Langevin equation. They prove also that the expected time to escape a barrier is polynomial in the parameters, as well as a generalization error bound.

### Strong/Weak points
- The paper is built up on simple principles
- It first gives a one-dimensional analysis then generalize, helping the reader to understand
- Except a few points, in general the paper is well-written.
- The assumptions made are somewhat strong and may not hold in some cases, see below.

In general I have a tendency to accept this paper. Even though there are crucial assumptions that are made, it can be considered as a first step towards a more rigorous and general argument.  

Here are a few points that I have problems with in the paper:
- On page 3, paragraph 2, it is written that the solution of Langevin equation is Gaussian distribution. What does it mean? The solution of a SDE is a Markov process, and considering the distribution of the process at time $t$, it is not necessarily Gaussian; the Fokker-Planck equation governs the change of distribution, having the Gibbs distribution as its stationary distribution, which is not Gaussian in general.
- The whole argument is made through assuming that near the basin, everything is quadratic (not approximately, equal!). This is completely reflected in Proposition 1 and the further analysis.
- In Theorem 4, it is not stated that $H = H(w^*)$, and I don't see why should one be interested when $w\to\infty$? This is because we are talking about an $\epsilon$ ball around $w^*$ and tending $w \to \infty$ has no meaning.... Maybe I am missing something here? Also, it seems that the distribution is defined only for positive $w$.
- In the argument for Section 4 (escaping), it is assumed that the basin is quadratic and __stays__ quadratic, even when it reaches the saddle point. I find this assumption flawed, or I am missing something.
- At the bottom of page 3, it is said "in this case, .... is satisfied", while I think it should be "not satisfied".
- On page 4, the notion $\rightarrow_p$ is used for convergence in distribution, which is not usual and is reserved for convergence in probability.
review_title: Official Review of Reviewer #3

final_score: rating: 6: Marginally above acceptance threshold
review_content: Summary: the paper studies the effect of SGD noise near a local minimum of the loss by using a novel Taylor expansion to estimate the distribution of gradient noise in the neighborhood of that minimum. They use this to derive closed-form equations describing the distribution of the iterates, which they use to characterize properties such escaping times and generalization. 

Pros: 
- To my knowledge, the mathematical analysis appears to be quite novel and insightful. It is particularly interesting that the authors show that the second order effect of the SGD noise in the Hessian induces a power law distribution over the iterates. 
- Some empirical support is provided for the theory.

Cons:
- In general, a clearer statement (and justification) of the assumptions is required. For example, it appears to be implicit throughout the paper that we only consider the neighborhood of a local minimum, so the analysis is essentially for a quadratic in this neighborhood. This should be stated more explicitly. 
- I also have some concerns about mathematical precision in the theorem statements. It is sometimes unclear which computations are rigorous equalities and which are not - for example, in Lemma 6 about escaping times, exact equality is used. However, the proof relies on Taylor expansion and uses approximate equalities in the steps. This is potentially misleading. 

In general, the results seem interesting, and it is understandable that certain assumptions/heuristics must be used because this area of research is technically challenging. However, I would like to see the clarity of the presentation improved before recommending acceptance. 

I have more specific questions regarding the details in the paper below:
- Could the authors elaborate on the relationship between kappa and generalization? From the paper my understanding was that smaller kappa meant flatter curvature and better generalization, but this doesn't seem to be supported by Figure 3. 
- How is the value of kappa contained in Figure 3? Is it computed via computing the Hessian and its covariance or chosen to best fit the histograms in the figure?
- Eqn 6: It seems like this closed form computation is specifically for the case when the function is quadratic (e.g. we take 2nd order Taylor approximation around a local min. Can the authors confirm?) If this is the case, what happens to the dependency on w - w^* and why is there no such explicit term in eqn 6? It would appear that g(w) should depend on (w - w^*). 
- In the overparameterized regime, it would appear that \sigma_g could go to 0 if each training example is overfit by the model. It appears that plugging in \sigma_g = 0 would introduce some degeneracy in equation 6 and 7, however. Can the authors comment on this?
- Intuition on the term \sigma_H: what do we expect this to look like in practice and do the authors have a sense on whether this term only matters around local minimum?
- The definition of \Sigma_H in the multivariate case: in the first paragraph of section 3, the definition on the LHS has no mention of i, j but the RHS does.
- Assuming the signal to noise ratio of \tilde{H} can be characterized by a scalar - why is this assumption reasonable?

*********
EDIT: Changed my score from 5 to 6 after the author response/revision.
review_title: Interesting theoretical results, though presentation could be improved

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper proposes to use power-law dynamics to approximate the state-dependent gradient noise in SGD, and analyses its escaping efficiency compared with previous dynamics. 

Strength:
1.	To the best of my knowledge, it is novel to use power-law dynamics to analyze the state-dependent noise in SGD. 
2.	Still with strong assumptions on covariance structure, the analytical results based on power-dynamics are interesting. For example, it indicates that so-called kappa distribution highly depends on the fluctuations to the curvature over the training data. This is consistent with following work. So I suggest authors provide some discussion with the following work.
Wu et.al 2018. How sgd selects the global minima in over-parameterized learning: A dynamical stability perspective. In Advances in Neural Information Processing Systems (pp. 8279-8288).

Weakness & Issues 
1.	The analytical results seem that they strongly depend on the covariance structure assumption, i.e. C(w) is diagonally dominant according to empirical observation. Does it have any theoretical justifications, or even in simplified cases? 
2.	The delivered PAC generalization bound and the followed analysis are a little ambiguous.  Firstly, in current deep learning theory community, the relationship between flatness (even how to define a proper flatness) and generalization is still mysterious and controversial, which depends many factors. This work uses one type of flatness measure, the determinant of H, and shows that flatter minima generalize better by only considering the KL term. However, the first term also includes the Hessian and might also affect generalization bound. Thus, the conclusion appears a little problematic. 
The authors said that generalization error will decrease w.r.t. kappa’s increase and infinite kappa results in Langevin dynamics. Then the question is what are the difference between the power-law dynamics and Langevin dynamics in term of generalization? 
My view on the ambiguous analysis is that the authors attempt to answer extremely challenging questions but left with many questionable concerns. 
3.	The experiments might not be sufficient. 
I don’t think fitting the parameter distribution according to limited empirical observations is an appropriate way to make justifications. At least, from visual observation, there are many other alternatives besides power-law distribution to fit, as Fig 3 shows. 
About comparing the escaping efficiency, the result only shows the success rate, and the evidence about the polynomial and exponential difference should be provided. Also, practical networks and datasets should also be considered to provide more strong evidence.

If the authors can resolve these issues carefully, I would raise the score. 

Typos
“Eq. 4” should be “Eq.3” below equation 3

review_title: Novel perspective, but left with much ambiguous analysis and insufficient empirical justifications

Meta-review: The average review rating is 5.5 which means it’s somewhat borderline. One of the reviewers planned to increase the score but apparently didn’t do so formally. A subset of the main pros and cons the reviewers pointed out are: 

Pros: 
“Some empirical support is provided for the theory.”
“ It is particularly interesting that the authors show that the second order effect of the SGD noise in the Hessian induces a power law distribution over the iterates.”

Cons: 
“The escaping efficiency of the power-law dynamic is only analyzed in low-dimension case. ...” The author responded that Theorem 7 proves the multi-dimensional case. But the AC noted that it’s very likely that escaping time is exponential in dimension (because kappa needs to be larger than d as the author noted and the det() might also be exponential in d. The author did say in the revision that the dimension should be considered as the effective dimension of the hessian, but the AC couldn’t find a formal argument about it.)
“The assumptions made are somewhat strong and may not hold in some cases...”

The reviewers also had a few clarity questions which the author addressed in revisions with re-organized writing. The AC weighed the pros and cons and found that the unclarity and potential exponential escaping time in the multi-dimensional case outweigh the pros.   


Decision: Reject