Stochastic gradient descent (SGD) forms the core optimization method for deep neural networks. While some theoretical progress has been made, it still remains unclear why SGD leads the learning dynamics in overparameterized networks to solutions that generalize well. Here we show that for overparameterized networks with a degenerate valley in their loss landscape, SGD on average decreases the trace of the Hessian of the loss. We also generalize this result to other noise structures and show that isotropic noise in the non-degenerate subspace of the Hessian decreases its determinant. In addition to explaining SGDs role in sculpting the Hessian spectrum, this opens the door to new optimization approaches that may confer better generalization performance. We test our results with experiments on toy models and deep neural networks.
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.