Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: This paper studies the behavior of SGD after it has reached a steady state and settled in a minimal valley. The authors show that even if SGD has reached a minimal valley, the noisy updates provided by a minibatch of samples result in the trace of the Hessians reducing with further SGD iterations. The authors also show that by changing the type of noise that is added to GD, one can get different functions of the Hessian to reduce with SGD iterations. The theoretical conclusions are then verified empirically with synthetic examples and real deep learning examples

In my opinion this is an interesting paper and research direction that helps us understand how SGD biases solutions towards "flatter" minima as measured by the trace norm of the Hessian of the loss function. I have a few concerns though:

1. Is the steady state assumption valid for neural network training? Especially when training on exponential losses (like cross entropy) which drives the parameters towards large norm solutions? This seems to be an important yet unsupported assumption in the analysis.

2. Does the Hessian-noise covariance alignment exist for squared loss functions as well? Is this specific to log-likelihood models?

3. In the experiments to delineate how different types of noise can result in regularization of different quantities, is there a reason only a synthetic example is used? Can this be replicated for deep networks, or are the two quantities (trace vs determinant) closely related? It would be nice to see how this behavior extends to deep networks.

Additional questions/comments:
1. While overparameterization seems to be important to the analysis (the parameters move in the degenerate subspace but not in the non-degenerate one), is there anyway one can amend this framework to analyze different levels of overparameterization? Is there any difference in the rates of decrease in the trace norms for highly overparameterized models vs lightly overparameterized ones?

2. This paper talks about how SGD has a bias towards flatter minima. Is there a reason to prefer flatter solutions over sharper ones to get better generalization? Can one prove this connection?

3. In the Densenet experiments in Figure 4a, it seems as though this relationship between flatness and generalization might not hold? There are points along the optimization trajectory where the validation loss seems to be better than at the last few points along the optimization path. However at the former set of points the trace norm of the hessian is larger than at the latter points. Is this from a stray experiment, or are the plots averaged over a number of different runs? Please add these details as well as other details such as learning rates, criteria to decide when steady state was reached, whether or not batch norm was used, etc.

4. The Fluctuation-Dissipation Relations need to be explained more clearly. For people unfamiliar with statistical physics (and Yaida 2019) the notation and formulation is not immediately clear and that makes the paper harder to read.

Overall I believe this paper explains an important phenomenon. I am willing to update my score if my concerns are addressed/if there is any misunderstanding.
review_title: Official Blind Review #2

final_score: rating: 3: Weak Reject
review_content: This paper proves that under certain conditions, SGD on average decreases the
trace of the Hessian of the loss. The paper is overall clear and the topic addressed in the paper is relevant in machine learning but I don’t think this paper is ready for publication. There are numerous assumptions that are made in the paper, but not properly stated or backed up. In my view, the experimental results are also not sufficient to compensate for the shortcomings of the theoretical part.

Lemma 1
This is a corollary of Morse lemma, which is also used in Dauphin et al: https://arxiv.org/pdf/1406.2572.pdf (see Equation 1). I don’t see why you would need to re-derive it in your paper and most importantly this should be clearly stated in your paper.

Page 2: existence stationary state?
What are the conditions for the existence of a stationary state? Is bounded noise sufficient?

Equation 4 and local approximation
Regarding the standard decomposition of the Hessian in eq 4 (sometimes referred to as Gauss-Newton decomposition), the discussion is not precise. The authors claim “Empirically, negative eigenvalues are exponentially small in magnitude compared to major positive ones when a model is close to a minimum“
But clearly from the formula itself, one needs to differentiate between minima with low and high function values. For local minima that are high in the energy landscape, the second term might have a large function value. If of course all **depends on the size of the approximation region**. This is extremely important and it is not properly characterized in the paper. The authors simply claim that the loss can be locally approximated while I think these assumptions should be clearly stated. Note that similar types of analyses are usually done in dynamical systems where the behavior of a system is linearized around a critical point. In some cases, one can however characterize the size of a basin of attraction, see e.g. the book Nonlinear Systems (3rd Edition): Hassan K. Khalil.

Assumption on timescale separation
This section makes numerous claims that are not properly backed up.
1) “This assumption is because there is a timescale separation between
the dynamics of \theta_bar, which relax quickly and the dynamics of \theta_hat, which evolve much more slowly as the minimal valley is traversed.“
Are you claiming the absolute value of the eigenvalue of the non-degenerate space are much smaller than the degenerate space? Why would that be so?
2) Ornstein-Uhlenbeck: OU processes require the noise to be Brownian motion. This assumption needs to be clearly stated. Note that there is actually evidence that the noise of SGD is heavy-tail:
Simsekli, Umut, Levent Sagun, and Mert Gurbuzbalaban. "A tail-index analysis of stochastic gradient noise in deep neural networks." arXiv preprint arXiv:1901.06053 (2019).

Take away
I am unsure what the added value of this paper is. Second-order methods can already be shown to decrease the maximum eigenvalue, see e.g. convergence results derived in Cubic regularization of Newton method and its global performance by Nesterov and Polyak. These methods have also been analyzed in stochastic settings where similar convergence results hold as well. What particular insight do we gain from the results of Theorem 2? The authors claim this could “potentially improve generalization” but this is not justified and no reference is cited.

“This indicates that the trace itself is not sufficient to describe generalization (Neyshabur et al., 2017).“
I do not see what aspect of Neyshabur et al. justifies your claim, please explain.

Experiments
All the experiments performed in the paper are on very small models. Given the rather strong assumptions made in the paper, I feel that the paper should provide stronger empirical evidence to back up their claims.

review_title: Official Blind Review #1

final_score: rating: 6: Weak Accept
review_content: This paper considers the problem of how noise coming from the gradient-based update affects the geometry of the hessian matrix when training a neural network. 

The paper makes an interesting claim that around a local minimum, if the noise in SGD is aligned with the hessian matrix of the network, then doing SGD update is implicitly minimizing the trace of the hessian matrix, biasing the current point towards a wide valley. 

The paper also makes a very interesting observation that isotropic noise will decrease the determinate of the hessian while the SGD noise will decrease the trace of the hessian matrix. 

I find the theorem in the paper quite interesting, especially Lemma 1 stating that the loss function can be locally approximated by a quadratic function whose variables are the non-degenerate directions and the coefficients only depends on the degenerate directions. This Lemma appears to be quite novel to me. With this Lemma, it is then easy to see that as long as the noise is aligned with the non-degenerate directions, then the trace of the Hessian is decreasing in expectation at every step. 

The main question I have about this paper is the clarity: First of all, the main concept "noise covariance matrix aligned with the hessian" is not mathematically defined anywhere. I can intuitively understand the term from the explanation in section 2.1.2 but I can not formally justify the correctness. Second, where is the timescale separation used? Is it for justifying the assumption of the local stationary point approximation or for Lemma 1 or something else? At the current level of writing in the paper, I can not formally verity the theorems. 

Missing citation: "an alternative view, when does SGD escape local minimal."



After Rebuttal: I have read the authors' responses and acknowledge the sensibility of the statement.




review_title: Official Blind Review #3

Meta-review: The study of the impact of the noise on the Hessian is interesting and I commend the authors for attacking this difficult problem. After the rebuttal and discussion, the reviewers had two concerns:
- The strength of the assumptions of the theorem
- Assuming the assumptions are reasonable, the conclusions to draw given the current weak link between Hessian and generalization.

I'm confident the authors will be able to address these issues for a later submission.
Decision: Reject