How noise affects the Hessian spectrum in overparameterized neural networks
Authors: Mingwei Wei
David Schwab
Venue:  (2020)
Keywords: noise
optimization
loss landscape
Hessian

Abstract: 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.

Under review as a conference paper at ICLR 2020
HOW NOISE AFFECTS THE HESSIAN SPECTRUM IN OVERPARAMETERIZED NEURAL NETWORKS
Anonymous authors
Paper under double-blind review
ABSTRACT
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 degenerate valley in their loss landscape, SGD 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. addition to explaining SGDs role in sculpting the Hessian spectrum, this opens the door new optimization approaches that may confer better generalization performance. We test our results with experiments on toy models and deep neural networks.
INTRODUCTION
Deep neural networks have achieved remarkable success in the past decade on tasks that were out of reach prior to the era of deep learning. Yet fundamental questions remain regarding the strong performance over-parameterized models and optimization schemes that typically involve only first-order information, such as stochastic gradient descent (SGD) and its variants.
Regarding generalization, it has been noted that flat minima with small curvature tend to generalize better than sharp minima (Hochreiter & Schmidhuber 1997: Keskar et al. (017). This has been argued by nonvacuous PAC-Bayes bounds (Dziugaite & Roy 2017) and Bayesian evidence (Smith &
&Le Le. 2018). But why does SGD bias learning towards flat minima? One possible explanation was proposed by Zhang et al.] (2018) in terms of emergy-entropy competition. Dastrzbski et al. (2018) also suggests that isotropic noise SGD helps networks escape sharp minima with large Hessian determinant. However, previous theoretical analyses assume that minima are isolated and non-singular. In contrast, Sagun al. (2017b) finds that most of the eigenvalues of the Hessian of the loss function at minimum are close to zero, indicating highly degenerate minima. The degeneracy is further supported by results on mode connectedness (Garipov al. 2018 Draxter al. 2018). Furthermore, it is shown that minima found from different initializations and the same optimization scheme are connected with essentially no barriers between them. Nguyen (2019) also shows theoretically that for class of deep overparameterized neural nets with piecewise linear activation functions, all of the global minima are connected within a unique and potentially very large global valley.
In this paper, we prove that for models whose loss has "minimal valley" structure, defined below, optimization via SGD decreases the trace Hessian of the loss, by utilizing recent fluctuation- dissipation relations (Yaida) 2019). Furthermore, result the reduction of other potentially desired quantities such as the Hessian determinant, leading towards the design of new optimization algorithms. We present experiments toy models and deep neural networks to confirm our predictions.
derive the noise covariance matrix that would
2
MAIN THEOREM
In this section, present main theorem- how noise during optimization affects the Hessian of the loss function when the loss landscape locally takes the shape of degenerate valley. More specifically, let N and be the dimension of the total parameter space and non-degenerate space, respectively, and

---

Under review as a conference paper at ICLR 2020
consider general loss function [(w) where E RN the model parameters Since the curvature around the minima can vary, we approximate the loss function in such a valley around a degenerate minimum with modified quadratic form L(w) L + Y/2 (w P ((w))² (P()))( where P a function that projects a point w in parameter space to the nearest minimum, and H is the Hessian, function of the location of the projected minimum. We have the following lemma:
P(w))
Lemma 1. For an arbitrary point w and its neighborhood in the valley, there exists an orthogonal transformation Q and a translation vector a such that the loss function in the new coordinate system 0 Qu v has the following form,
L( L' + 2 (
where 2as are the positive eigenvalues of the loss function Hessian for the non-degenerate space and depend on the position in the degenerate space. Also, note that the gradient descent equation is invariant under this transformation.
A detailed, constructive proof of this lemma can be found in Appendix A.1 Notice that this is a generalization of Morse's Lemma [Callahan 2010). In the rest of this section, we denote the nondegenerate and degenerate subspaces by = (0,,..., On and 0 = (On+1, 0N)" respectively, Similarly, the gradients of 0 and 0 are denoted by V and V, respectively. Notice that at minimum where 0 = 0, the À; are the only nonzero Hessian eigenvalues.
Next we provide quick review of the relevant fluctuation-disspaal relation formalism for stochastic gradient descent (Yaida) 2019). We denote the loss for a random batch of training sample as L (0). Clearly have
[O))(()) = VI(0)
(2)
where [m]m. represents the average over all mini-batch realizations. If there exists a stationary state for 0, Pss (0) and the auttionar-aaverage is defined as (O(0)) = f d0p. where (00) is any
observable of 0, it straightforward to derive the following master equation:
(O(0) = [[O - (0)]mm()
We denote the two-point noise matrix as (i) = [0,, L (0)0,, ance matrix (0) = (0) 0n, (((0) T.(0).
L (0)]m.b. and the noise covari-
Now we present our main theorem: Theorem 1.
When the loss can be locally approximated as in Equation 7 assuming that the non- degenerate space is in a stationary state at time t and that the noise covariance matrix is aligned with the Hessian, have
{[T++1 - Telmmbb) 5
where T Di=1& > the trace of the Hessian and T, represents the trace training step t. Equality holds when VL (() or (T( 0.
Theorem indicates that the change of the Hessian trace during SGD optimization is non- non-positive on average. A trivial condition for equality is optimization with gradient descent (GD) instead of its stochastic variant because the stationary state for noiseless optimization is constant state with vanishing gradient. An alternate condition for equality is that the trace function of 0 reaches a minimum or saddle point.
Before proving Theorem I we will first analyze the assumptions made. We emphasize at the outset that we expect our assumptions be valid only after an early phase of training corresponding to 10 epochs in our experiments.
2.1 EVIDENCE FOR THE ASSUMPTIONS MADE
In this subsection, we will analyze the assumptions Theorem I and present some experiments that support their validity.
Here the non-degenerate space corresponds to the subspace of the Hessian with non-zero eigenvalues. Note that we do not require any specific relationship hetween and N, e.g. < N.
2

---

Under review as a conference paper at ICLR 2020
2.1.1 MINIMAL VALLEY
Our theory relies on the existence of a degenerate valley in the loss function defined previously via Equation[]] In addition to degeneracy, we furthermore assume that there exists region of connected degenerate minima in the landscape of the loss function, in particular for overparameterized models. SGD or its variants then selects one of the degenerate solutions. Such degeneracy has been observed empirically where most of the cigenvalues of the loss Hessian from various models and tasks are zero or close to zero (Sagun et al. 2 b). Furthermore, the connectedness further supported by results of mode connectedness (Garipov et al. 2018 Draxler et al., 2018). Nguyen (2019) also shows theoretically that for class of deep overparameterized neural nets with piecewise linear activation functions, all of the global minima are connected within a unique and potentially very large global valley.
Here we present additional experiments support the existence of such minimal valleys, i.e. basins of attraction of connected, degenerate minima that can be locally described by Equation I These experiments will be also used to analyze and confirm our theory later. We consider classification of CIFARIO I0 with label-smoothing cross entropy (Szegedy et al. 2016 constant learning rate of 0.1, momentum 0.9, batch size 500 and total training epochs 150. The network architectures are Preact-ReNNet1s 8 (He et al. 2016) and VGG16 (Simonyan & Zisserman (015). The training and validation loss are shown in Figure (inset). After 150 training epochs, the networks fluctuates with small training loss, and the minimal training loss for both case is ~ 0.005.
In order to confirm the existence of minimal valleys, we would like to project each point along the training path to the corresponding closest minimum [ and check whether the projected path crosses any barriers. To determine whether two minima can be connected by line segment in a minimal valley implying no barriers in between, we use line interpolation to connect these two minima and measure the training loss along the interpolating line. In practice, we call it line connectedness we sample evenly 10 points in the line segment between consecutive minima and the training loss is smaller than a threshold for all 10 points.
To project a state to closest minimum, the model is trained from that state with the same hyperpa- rameters except using GD instead of SGD to remove noise. The stopping criterion for these auxiliary training tasks is that the training loss is less than the minimal training loss, which is ~ 0.005.
Ideally, we would project states after each iteration and check for line connectedness, but this involves large unnecessary calculations. In practice, if state B is obtained from training iterations after state A, and A and B are not line connected, we insert C which is obtained from n. n training iterations after A and check for line connectedness between A and C and between C and B. This process stops when there is no extra iteration between A and B or they are line connected. Starting from each pair of consecutive epochs A and B, obtain the projected path recursively. The training and validation losses on these two projected paths are shown in Figure (main plot). The left path has 2700 projected points and the right has 4020. We that after few epochs, the training loss along the path remains close to zero (and hence minimal), which means that there exists a least one minimal valley connected to the model state found by regular SGD. Also SGD optimization happens within such a valley after the first few epochs. Furthermore, the validation loss varies along the valley.
More experiments can be found in Appendix A.2 Further discussion of violation of this minimal valley assumption can be found in Appendix A.6
2.1.2 THE HESSIAN-NOIE COVARIANCE ALIGNMENT
Empirical observations have found that the noise covariance matrix is aligned with the Hessian (Zhang et al., 20188) Zhu et al. 2019 Jastrzbski et al., 2018). In fact, was shown in Hoffer et al.
(017)) that
(1 (1 M Ci S
S
1
M
Σ
o, 00, ((0,
M
'The label-smoothing technique is used here to make a true minimum of the cost function exist. Regular cross entropy gives similar results. We use minimum here hut specifically we mean point with training loss less than a threshold.
3

---

Under review as a conference paper at ICLR 2020
1.50
1.50
train
train
1.25
validation
1.25
validation
1.00
Mm w monnt
1.00
Loss
0.75
50
100
150
0.75
100
150
Epoch
Epoch
0.50
0.50
0.25
0.00
0.00
20
40
60
80
100
120
140
20 40
80
80
100
120
140
Epoch
Epoch
Figure 1: CIFARIO trained on & (left) and VGG16 (right). Main plots show training and validation loss of projected paths. Projected paths are obtained by projecting each model state during optimization to a corresponding state found by GD with small training loss. Each pair of consecutive projected states are then connected by line interpolation. The inset shows training and validation loss of training paths.
where S is the log- ongliikelhhod loss functions, which is also the loss function in our experiments for classification, M the loss L can be written as L M Di= log f 0) where f is the output of the network and [(rx. 0) = log f (Ik, 0). Notice that
size and M is the total number of training samples. Considering negative
M M Σ
M
0,,00, 0, L(0)
1
Do, 00 1)0 0)
Σ M k=1 f(a 0) 0o,00,
1
1
0o (Ix. 0)
(4)
where the left-hand side is the positive Hessian matrix for i,j S n and the first on the right- hand side is the positive matrix proportional to the noise covariance matrix. Empirically, negative eigenvalues are exponentially small in magnitude compared major positive ones when model is close to a minimum (Sagun et al., 2017b) and negative eigenvalues can only come from the contribution the second term on the right-hand side of equation Therefore unless the second term is extremely asymmetrical, we can assume that its contribution is small compared to the first term. We will return to this in Section[4.] and show that eigenvalues with small magnitude arise from higher-order curvature in the degenerate space even when the Hessian with respect to the bottom of the valley is characterized by the positive A, for i = I, I,,.. n or zero directions. Ignoring the second term the right hand side, Equation 4 becomes
C.j - (
S M
Has
We emphasize that this assumption will only be valid after the early phase of training, not from initialization. Further discussion and experimental support can be found in Appendix A.4
2.1.3 TIMESCALE SEPARATION
The final assumption is that the dynamics relaxes stationary state in the non-degenerate space but not in the degenerate space. This assumption is because there is a timescale separation between the dynamics of 0, which relax quickly and the dynamics of θ, which evolve much more slowly as the minimal valley is traversed.
Considering simplified optimization problem where parameter directions undergo independent Levy-driven
processe as for quadratic loss with noise, the decay to stationary state is exponential with decay rate proportional the corresponding eigenvalues (Abdelrazeq et al.) 2014). Since the 9 correspond to the leading order eigenvalues, their relaxation time is exponentially shorter than the evolution in the degenerate space. Therefore it is reasonable to assume stationary state the non-degenerate space when studying the degenerate Ô dynamics. Further discussion and experimental support of this assumption using Appendix A.5
relations can be found in
Simsekli al. 2019) proposes analyze SGD an SDE driven by Levy motion.
4

---

Under review as a conference paper at ICLR 2020
2.2 PROOF OF THEOREM
Proof. The stochastic gradient descent update for 0 0.+1 - L (c). If we consider the average evolution of the eigenvalues X; for i 1, 1,.,. from step to + we have
(De,++1 Actlm.b..) = ([A:(0++1) - (=()).mmm.b))
<[>,(0: ,).I.9(())) (0.))
(6)
= (
+ 0
-0, ( 0
where we performed Taylor expansion from the second to the third equality and the fourth equality holds from equation (2).
Notice that (L( = = E V By keeping the leading order term, we have
n
(Da.+1 - Am..lm..)) =
"
"
Σ
(
2 j=1
Considering the observables 0(0) = 0f for i 1,.,, n, the master equation
becomes
(0,0a. L) 2 (0is)
Notice that 0o, L - (0), we thus have
(((a))
2x,
By the definition of the two-point noise matrix C and the noise covariance matrix C, we also have Č₁ = Ct + 0o, (())o, L(0)
Ci, + (0)
Based on the assumption that the noise covariance matrix is aligned with the Hessian and scales as where is the mini-batch size and is the total number of training samples (Hoffer
S.
77
et al.
2017
we have
(
S M
Ci
(0)
(10)
Together with Eq. and we have for S n,
(0?)
1
1 5
S(2 - n771) 1)
M
(11)
+ +0(P)
25
M
Now Eq.
becomes
112
(1
S
(Di,t1 At..mm...))
0
45
M
Ø=1
Next consider the evolution of the trace of the Hessian T Σn d, We have
1
S
([T++1 T.Jm.hh)
1
(O.) + 0
45
M
i,==1
11²
S
)
2
1
Σ
4S
M
0
'Refer Assumption 2.1.2 for details.
5

---

Under review as a conference paper at ICLR 2020
Thus have shown that the trace of Hessian decreases average during SGD optimization. Notice that equality holds when either one of the following conditions is satisfied: first, if S = M so that SGD becomes full-batch GD, and second that >; ()e(O)) = 0, which implies VT(@) = 0.
OPTIMIZATION DYNAMICS WITH NOISE BEYOND SGD
In Section 2 we concluded that, to leading order in the learning rate 7), SGD dynamics reduces the Hessian trace. This result originates from the noise introduced by SGD with covariance given by (TO). Interestingly, other forms of noise can be introduced into gradient descent in order to decrease other desired quantities instead of the trace. Here we present a theorem that relates the expected decrease of certain functions of the Hessian spectrum
corresponding noise covariance. And (+) represents an average over the stationary state and [+] averages the quantity over the corresponding noise.
Theorem 2. In a minimal valley with loss approximation in Equation [ assuming that there exists a stationary state in the non-degenerate space 0, for any quantity f() satisfying 0f(A)
dd; 2 0 for T if the loss is optimized with gradient descent along with
i L..... n, where À (A1...,, AT) external noise with diagonal covariance matrix
Qf(2)
O₁, X 04,
(12)
have
([++1 - fcT) S
where f. represents f(A) evaluated at training step t. Equality holds when v)(((()) = 0.
Proof. Similar to the proof of Theorem
! we have
(1++1 - A1])
_
Σ
VO + +012)
(13)
04
With the imposed noise with covariance matrix (12). the master equation (3) and the relation between noise covariance matrix and two-point noise matrix in equation (9, we have
(0F)
11
0f
(2 n)a2) 0A;
(14)
0f
+ 00
2 07
Plugging in Equation 13 have
112 n 0s (x) +0(7))
([i+1 - (i))
11²
(()())) |
(15)
0
Thus we have shown that f decreases on average during optimization. Equality holds when (f(A(0)) = Notice that Thcorem is special case with f(A) = Em= A
Furthermore, we have the following corollary:
Corollary 2.1 Siterminant-Decrraaate Noise). With the same assumptions in Theorem f()) log I[ A and C, C where C is arbitrary positive constant, we have
let
(Dett++ - Det,]) 0
where Det. M X is the non-degenerate determinant.

---

Under review as a conference paper at ICLR 2020
Sum of DE.gnneell. mesvelless.
Traco Exeldton
2.5
-32-4
-0-
4
4E44
Traaning Loca
6.820
SG0 No66
batk-opic No
4.130
lactlopic Noie SGD
Nose
Dxtmmbar
4.125
4.100
4.075
0.305
0.300
4.05
2500
5000
7500
10000
12500
15000
17500
20000
2500
9000
7500
10200
12500
15000
17500 20000
Deendtoo
(eeniton
Figure 2: (a) The training loss v.s. the sum of negative eigenvalues. Red is the best fit line, wxz with wt = -00.07 and 1.22 10-5. The data is nearly a straight line and the y-intercept is almost zero, consistent with our prediction in Appendix [A.3] (b) The trace evolution learning rate. The result shows linear relation. Red is best fit line. (c)-(d) Change of the Hessian trace and determinant during training using isotropic (blue) and SGD noise (red).
the squared
Corollary 2.1 indicates that the non-degenerate determinant will decrease on average during optimiza- tion if we introduce isotropic noise in the non-degenerate space. It is known (Smith & Le 2018) that the Bayesian evidence, minimization of which minimizes a MAC-Bayes generalization bound, has a contribution from the hon-degenerate determinant. This contribution is also called the Occam factor. Our result thus leads to a new algorithm where one introduces isotropic noise into the non-degenerate will allow future work to add designed noise that applies entropic force other
space. Theorem Wwill properties of the Hessian yet to be determined.
EXTENDED ANALYSIS AND EXPERIMENTS
4.1 NEGATIVE EIGENVALUES OF THE HESSIAN
Empirically, small negative eigenvalues arise even with small training loss, which seems to indicate that the model is at saddle point instead a minimum (Sagun et al.) [017b]] Ghorbani et al.) 2019). This however is consistent with the loss in Equation 1 The loss minimal when 0 f S n. However, when we use a trained instance to estimate the eigenvalues of the Hessian, we only guarantee that 0g is close zero (and thus nonzero training loss) for < n. Therefore, there could exist negative eigenvalues which originate from the second derivative of 0, for > n. They are originally zero the minimum with 0, for i < n,, and their magnitude suppressed by 0f for d < n. which is related to the small training loss.
In Appendix A.3 we predict that the negative eigenvalues on average are proportional to the training loss. To confirm this, we set up a simple experiment to classify MNIST data with small training set of 500 randomly selected samples, with a single hidden layer fully-connecter network with 6220 parameters and loss given by label-smoothed cross entropy, again to make genuine minimum. We first obtain a minimum with gradient descent optimization at learning rate 0.1 and 10k training epochs and use this as initialization for later. The model is then further trained from this initialization with different batch sizes from 5 to 250 and learning rates from 0.001 to 1 in order to equilibrate to various training losses. Then the negative cigenvalues are calculated and the result is shown in Fig. 2(.). The result shows a linear relationship between training loss and the sum of negative eigenvalues, predicted.
7

---

Under review as a conference paper at ICLR 2020
16
3.25
8.5
1.4
Validation Logs
Trace (lag scaak))
3.00
1.0
Validation Loss
1.2
2.75
1.0
2.50
Trass
0,8
2.25
0.6
2.0
2.00
0.4
0.4
20
40
60
80
100
20
40
80
80
100
Epoch
Epoch
Figure 3: Hessian Trace estimation of projected paths found in Section 2 with network architecture of 8 (left) and VGG16 (right). Red bars represent the errors in trace estimation. The decreasing trace during SGD optimization confirms our theory prediction.
4.2 THE EVOLUTION OF TRACE AND DETERMINANT WITH TOY MODEL
In this section, we use two toy models to test our previous theoretical analysis. In Section 2 we showed that the trace evolution rate is proportional to r7². Notice that the two factors of 7) have different origins. One is from the expansion of À and the gradient descent step as in Eq. The other contribution is the equilibrium statistics in the non-degenerate directions as in Eq. g Furthermore, the coefficient of the proportionality relation also depends on VA. Therefore to test this prediction for train model multiple times with different rys. When
how learning rate affects the trace evolution, doing this, the initialization for each run is in equilibrium in the non-degenerate space, and we choose a loss function for which V is constant. We design simple four-dimensional toy model with the loss L(Ø)= = 10g + l + [83 + 20g to test this effect. We initialize the model make sure that 10g + 44l and 8g + 284 don't i change sign during a few iterations of training. For each we first train for 1000 iterations with SGD noise to equilibrate the model and calculate the trace. Then the model is trained for another 1000 iterations and we calculate the trace evolution. The result is shown in Fig (b), which shows a linear relation as predicted.
Next, measure the evolution of the Hessian trace and determinant after introducing noise with different covariance structure. Our theory predicts that SGD noise decreases the trace while isotropic noise in the non non-degene subspace decreases the determinant. To test this, design toy model where the behavior of these two quantities is anti-correlated. The loss can be written as L()) = (4 2e 03 18-07 0f )0 + +e (03---04) 02. We train the model with the same initialization and with the two different noise structures. The result shown Fig. 2 cd), consistent with our analysis.
4.3 TRACE EVOLUTION ALONG PROJECTED PATH
In Section 2 presented two experiments support the existence of minimal valley. Recall that the projected paths follow along the bottom of the valley associated with the SGD dynamics. Our theory predicts that the Hessian trace along the projected paths should decrease during optimization. To confirm this, we use method in Bai et al. (199) to estimate the Hessian trace and the results are shown in 33 in which the values and error bars are calculated by the mean and standard deviation of 10 different initializations. As seen in the figure, the Hessian trace indeed decreases on average in both cases, which consistent with our theoretical prediction. Notice that test performance does not monotonically improve during optimization. Indeed the trace continues decreasing slightly even when validation loss goes up, indicating that the trace itself is not sufficient to describe generalization.
CONCLUSION
In this paper, we showed that within a minimal valley, the trace of the loss function Hessian decreases on average. We also demonstrated how to design the covariance structure of added noise during optimization to affect other properties of the Hessian's 's evolution, opening the door to new algorithms. The analysis in this paper be extended and generalized to models trained much larger data sets.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Ibrahim Abdelrazeq, B. Gail Ivanoff, and Rafal Kulik. Model verification for levy-driven ornstein- uhlenbeck processes. Electronic Journal of Statistics, 2014.
Zhaojun Bai, Gark Fahey, and Gene Golub. Some large-scale matrix computation problems. Journal of Computational and Applied Mathematics, 74:71 14.71-89, 1996.
James J. Callahan. Advanced Calculus. Springer, 2010.
Felix Draxler, Kambis Veschgini, Manfred Salmhofer, and Fred Hamprecht. Essentially no barriers in neural network energy landscape. ICML, 2018.
Simon S. Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In ICMI,, 2019.
Gintare Karolina Dziugaite and Daniel M Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. In UAI, 2017.
Timur Garipov, Pavel Izmailov, Dmitrii Podoprikhin, Dmitry P Vetrov, and Andrew G Wilson. Loss surfaces, mode connectivity, and fast ensembling of dnns. In NIPS, 2018.
Behrooz Ghorbani, Shankar Krishnan, and Ying Xiao. An investigation into neural net optimization via hessian cigenvalue density, arXiv preprint arXiv:1901.10152 2019.
Guy Gur-Ari, Daniel A. Roberts, and Ethan Dyer. Gradient descent happens a tiny subspace. arXiv preprint arXiv: 2018.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Identity mappings in deep residual networks. In ECCV, 2016.
S. Hochreiter and J. Schmidhuber. Flat minima. Neural Computation, 9(1):1-42, 1997.
Elad Hoffer, Itay Hubara, and Daniel Soudry. Train longer, generalize better: closing the generaliza- tion gap in large batch training of neural networks. In NIPS, 2017.
Gao Huang, Zhuang Liu, Laurens van der Maaten, and Kilian Q. Weinberger. Densely connected convolutional networks. In CVPR, 2017.
Stanisaw Jastrzbski, Zachary Kenton, Devansh Arpit, Nicolas Ballas, Asja Fischer, Yoshua Bengio, and Amos Storkey. Three factors influencing minima in sgd. arXiv preprint arXiv:1711.04623 2018.
Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Peter Tang. On large-batch training for deep learning: Generalization gap and sharp minima. In ICLR. 2017.
Quynh Nguyen. On connected sublevel sets in deep learning. In ICML, 2019.
Levent Sagun, Leon Bottou, and Yann LeCun. Eigenvalues of the hessian in deep learning: Singularity and beyond. arXiv preprint arXiv:1611.07476, 2017a
Levent Sagun, Utku Evei, V. Ugur Guney, Yann Dauphin, and Leon Bottou. Empirical analysis of the hessian of over-parametrized neural networks. arXiv preprint arXiv:1803.00195. 2017b.
K. Simonyan and A. Zisserman. Very deep convolutional networks for large-scale image recognition. In ICLR, 2015.
Umut Simsekli, Levent Sagun, and Mert Gurbuzbalaban. A tail-index analysis stochastic gradient noise in deep neural networks. arXiv preprint httt:::99000005.3. 2019.
Samuel L. Smith and Quoc V. Le. A bayesian perspective generalization and stochastic gradient descent. In ICLR, 2018.
Christian Szegedy, Vincent Vanhoucke, Sergey Ioffe, Jonathon Shlens, and Zbigniew Wojna. Re- thinking the inception architecture for computer vision. In CVPR, 2016.

---

Under review as a conference paper at ICLR 2020
Sho Yaida. Fluctuation-dissipatio relations for stochastic gradient descent. In ICLR, 2019.
Chiyuan Zhang, Samy Bengio. Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. ICLR, 2017.
Yao Zhang, Andrew M. Saxe, Madhu S. Advani, and Alpha A. Lee. Energy-entropy competition and the effectiveness of stochastic gradient descent machine learning. Molecular Physics, 116, 2018.
Zhanxing Zhu, Jingfeng Wu, Bing Yu, Lei Wu, and Jinwen Ma. The anisotropic noise stochastic gradient descent: Its behavior of escaping from sharp minima and regularization effects. In ICML, 2019.
A APPENDIX
A.1 PROOF OF LEMMA
To study the dynamics of SGD, we investigate the model behavior starting from O; to 0 by one-step training and assume that 0,+1 close to 0,. In this subsection, we derive the property the loss function in small neighbourhood, B(0,), ). of 0,, which includes 0z+1. We consider the model in a minimal valley with a set M of minima and define projection that maps any point B(0,) to the minimum in M that is closest to 0, i.e.
P(0) argmin 1-
(16)
M.EM
Because M is connected by definition of minimal valley, we assume that P also continuous in B(O,). We denote the dimension of whole parameter space and M by N and N - respectively. can then make quadratic approximation to the loss function in B(O,).
[( = I.- 1 10 (P0))
(17)
where we expand the loss function at the minimum that is closest to O, and HP((O)) is the Hessian depending on the position P()) the valley. L is a constant by definition minimal valley and will be ignored in the following derivations.
We define minimal path to be a smooth path in a minimal valley where every point on the path is a minimum. For any path passing through minimum 0*, we have the tangent line of the minimal path at H* being in the null space of the Hessian at 8" by definition. Precisely, for an arbitrary minimal path 0* (p): [0, 1] + M, have
d0 (p) H ((0
0
(18)
du
Next we have the following lemma,
Lemma 2. Let J(O) be the N N Jacobian matrix of function P defined Jıj dP(O),
We
d8,
have
H(P(O))(())0- =0
(19)
Proof. Notice that (*) +00++p20 forms a minimal path through 0 where μ E [0, 1] and A0 is an arbitrary direction in the parameter space. We have
d0 (11)
J(0)20
(20)
du ==0
By Eq. we have
18
(21)
Since A0 is arbitrary, we have Eq.
19
n
10

---

Under review as a conference paper at ICLR 2020
Next consider the diagonalizaaion of the Hessian
(22)
where ()) diag A (P(O)). An (P(O)), gested by Gur-Ari et al. 2018), we assume that the cigenspace change negligible in the small neighbourhood ((,,) and denote constant orthogonal matrix V = V(P(O.)) V(P(0)).
and X 0 for 1 < 2 n. As sug-
We then perform the coordinate transformation
Φ = V0
(23)
and the loss function becomes
Σ (0: - (P(())))) [(Ø) = 2 i=1
(24)
where (()) is the same projection map as P(0) but in the coordinate of Φ. Notice here that p(Φ) is the projection to the minimum with the least L-2 distance Φ, because the coordinate transformation is orthogonal and distance preserved. We have
P(Φ) = VP(
(25)
We have the following theorem, Proposition 3. (()) is constant for i S n.
Proof. In d-coordinate, by Eq. 23 and 25 the Jacobian of P(Φ), J(Ø);
dP(0), do, is related to (0)
J(Ø) = VJ
(26)
Therefore Lemma becomes
((P()))(()) =0
(27)
Notice that [S(P(O)) = EEn Av where 6 is the Kronecker delta function, we have
[S(P()))(()); = {T)( isn.
(28)
From Eq. 27 and A > we have
J(Ø) 0 isn
(29)
Notice that J(Ø);j
dP(bl do,
for S and all j. we have that P()); is constant for i S
define global translation vector s" (ib,..., .... 64 0). and consider a new set of coordinate sp Φ o² and have
We denote P(Φ); of for i Therefore
1 L(bb) 1 Σ (FA(
(30)
where P(b) is also the projection to the minimum with the least L-2 distance to 1b.
Clearly we have the set of minima of the loss function 30 as { 2b = 0, S n) and the closest minimum to 2b in the L-2 distance is xb" (0,.., ..., O, th+ l.... vN) Therefore we have P(tb) = (0, O, wn+1 NN)
(31)
and
1 2 Σ (e
b(b)-
(32)
Notice that the coordinate transformations from 0 to Lb only involve orthogonal rotation and transla- tion. the SGD rule is conservative. To see this, we first have
Ve = VTV V'V.
(33)
And the SGD on 0 becomes
0 O, VV ((bb)
2++1 = Φ: L(bb)
(34)
1h+1 +h L(b
In the main text, replace the notation 1b with 0 for symbol simplicity.
11

---

Under review as a conference paper at ICLR 2020
A.2 ADDITIONAL EXPERIMENTS
To further support our assumption of connected minima, we conducted extra experiments including DenseNet (Huang et al. 2017) CIFAR100, and explored the landscape by introducing randomized labels on subset of the training data to initialize subsequent training on purely clean data (details in Section A.2.2).
A.2.1 DENSENET ON CIFARIO 100
We trained DenseNet with batch normalization (number of blocks [6.12,24,16] and growth rate=12) on CIFAR 100 and followed the same pipeline as described in the main text experiments. The learning rate is 0.1 and the batch size is 512. The result is shown in Figure a a) which supports the connectedness assumption well as the result of the Hessian trace decreasing under SGD.
A.2.2 4-LAYER CONVNET ON MNIST AND RESNET18 8 ON CIFARIO WITH RANDOMIZED LABELS
The setup of these experiments is as follows: we randomly split the training set into two sets, A and For MNIST and CIFARIO we let the number of samples in A be 40000. Then we shuffle the labels in set B. For the rest of this section, we call the training set and B the shuffle set. The loss minimum, Hessian trace, etc. are all with respective to the training set A.
First we will obtain minima with worse generalization than the minima found by regular SGD. To do so, train the model with the union of the training set A and shuffle set B until convergence. Then we further train the model with only A using gradient descent so the model reaches a minimum. This minimum corresponds the left end point of the path in Figure (b) and (c).
We then train the model from this minimum with training set A alone using SGD. We find that the model starts diffuse and validation loss becomes smaller even though it is at minimum already. Using the same method described in main text, we project this path to minimal and the results are shown in Figure (b) and (c).
In both cases, we found that minima found by SGD are connected, and we further estimated the trace along both paths and found that is decreasing on average. These results support the connectedness and degeneracy assumption and our result of SGD decreasing Hessian on average. It also illustrates how SGD helps model explore the loss landscape and escape bad minima.
A.3 THE SUM OF NEGATIVE EIGENVALUES
In fact, if consider equilibrium of 0g for S n, we have (L) = L" + X and -==
(0,0gL) = CE O, for j, from Eq. 11 where C 11 8 Thus change learning rate or batch size, and hence C. (0) because both are proportional nearby in the minimal valley. Usually in deep neural networks training loss can go to nearly zero with large number of training iterations and small learning rate (Zhang et al. 2017 Du et al. 2019 so we ignore L and have that (0,0,L) x (L). This result is tested and verified in Figure a).
L for states nearby in the minimal valley C' and Σn X and a Ar are approximately constant for states
A.4 EXPERIMENTS ON THE HESSIAN- NOISE COVARIANCE ALIGNMENT ASSUMPTION
To further support our assumption of the Hossi covariance alignment, we trained 2-layer neural networks on the CIFARIO dataset with label-smoothed cross-entropy loss and mean-squared loss (MSE) and calculated the cosine similarity between the Hessian of the loss (H) and the noise covariance (C).
The cosine similarity between two matrices A and B is defined as
Tr(ABT) CS(A,B) V "TT(AA")TT(BB)
(35)
where Tr is the trace operator. It easy to show that and B are aligned as A = kB, if and only if (S(A, B) 1.
12

---

Under review as a conference paper at ICLR 2020
(a)
validation
train
Trace (log scale)
Loss
2
0
10
50
Epoch
0.150
validation train
0.125
Trace (log scale)
0.100
Loss
0.075
2
0.050
0.025
0.000
Path
4,50
2.5
validation
4.25
train
2.0
4.00
Trace (log scale)
Loss
1.5
3.75
3.50
1.0
3.25
0.5
3,00
0.0
2.75
Path
Figure 4: (a) Experiments performed as in the main text with DenseNet on CIFARI00, (b) Ex- periments performed as described in Section 1.2 using 4-layer ConvNet on MNIST and (c) Preact- ResNet18 on CIFAR10.
In order to make calculate of the Hessian and covariance tractable, the networks were chosen to have one hidden layer with 70 nodes, and the dataset is transformed into grey scale and resized to x pixels and normalized. The network with label-smoothed cross-entroys loss is trained with SGD optimization with learning rate 0.001 and batch size 512 and the network with mean-squared loss is trained with SGD optimization with learning rate 0.1 and batch size 512.
13

---

Under review as a conference paper at ICLR 2020
CONl06 Santarry
16
0.93
cozine
075
15
100
180
300
400
500
100
200
200
400
500
Epoch
Epoch
Figure 5: The cosine similarity between H and C and training curve of 2-layer networks trained on CIFAR10 with smoothin cross-entropy loss (left) and mean meean-squared loss (right).
As shown in Figure 5 in both cases the cosine similarity between the Hessian and noise covariance is larger than 0.9 after several epochs of initial training. Notice that two random matrices with the same size as H and in these experiments are almost orthogonal with the cosine similarity of O. These experiments
consistent with assumption of Hessian-noise covariance alignment-after the early phase of training-in the main text.
A.5 EXPERIMENT ON THE TIMESCALE SEPARATION ASSUMPTION
In this section, we provide support for our assumption of timescale separation through experiments with small convolutional neural network trained on CIFAR1O. In order to observe relaxation to steady-state, we adopt the method in Yaida 2019)), which shows that
17(1 + 12) 0 VL)
(v²)
(FDR)
2(1
is satisfied when the model is at stationarity, where μ and SGD optimization, respectively, and v is the velocity. It is easy to show that
the momentum and dampening in
(P()) P(VL)) = 17(1 + p))
2) (P(v)?)
(FDR')
when there exists a stationary state in subspace S and P is the projection operator to S. We use O and On to denote the quantities of the left and right side respectively Ff and FDR Therefore the quantity OOr/OR 1/ can be used criterion to verify how close the model is stationary state a specific subspace.
To show the existence of timescale separation, train small CNN on CIFARIO. This network has 3 convolutional layers with kernel size and output channel number 15, 20, 10 respectively. Throughout training, estimate Or/OR on the raw parameter space and top-1 eigenspace of the Hessian. The result is shown in Figure
sshows that the criterion in top-1 eigenvalue decays much faster than in the raw parameter space. After several epochs. |O,/O 1| in top-1 subspace already less then 10 which is a threshold set in Yaida (209) indicate sufficient closeness the whole parameter space is still far from equilibrium after 50 epoch of training. This experiment fully supports our assumption of timescale separation in the main text.
stationary state, while the state in
A.6 EXTENSION TO NON-DEGENERATE LANDSCAPE
This section explores the situation where the minimal valley assumption slightly violated, which case the bottom of the landscape is not completely degenerate but has a small slope. The loss function
can then be written as
L( = L Σe
A 0N) + (fn Ox).).
(36)
14

---

Under review as a conference paper at ICLR 2020
raw parameter
10a
projection top-1 eigenvalue
10
[ōL1O 1|
10-2
10
10-
Epoch
Figure 6: 1OL/OR plots along training. The smaller this quantity is, the closer a state cquilibrium. This shows that a state in the top-1 eigenspace of the Hessian decays much faster to equilibrium then in the raw parameter space and supports the assumption of timescale separation.
where the function describes how the bottom of the valley varies in the previously degenerate directions. Following the same proof as Section 2.2 easy to obtain
n72 (
s M
([Ti+1 - T..mm..) =
Σ 1=1
Σ (
(37)
45
At the end of training, the model reaches equilibrium, where
([T++1 - -T.lm.b.) =
Thus, from Equation we have
0 (
27 45
5 M
Σ A (0)
|
(38)
This reveals explicitly the effect of SGD noise as an entropic force during training. The training of gradient descent and its variant drives the model to states with 0 0 and g 0 according to the energy function 36 This exert energetic force to the model moving forward to the lowest energy (smallest loss). However when training with noise, gg(0) = 0 may not be satisfied when the
locations with smallest trace and ( do not coincide because the right hand side of Equation 38 is always greater equal zero. That being said the model is pushed away from ( 0 as entropic competitor to the energetic force.
We use toy model to visualize this effect. Consider loss function of L(01,02) = (0 +1)00++++00
We train this function by GD and SGD with 10 4, learning rate 17 0.01. noise strength 3 37 and initialization (0,, = 0.1). The result is shown in Figure The left column corresponds training with gradient descent where O drops
very fast and 0 continues decreasing to negative infinity. As when noise is introduced, 0g stops decrease after equilibrium between entropic and energetic force. From 38 it is easy show that (02) 0002, which is consistent with the right column of Figure
15

---

Under review as a conference paper at ICLR 2020
E005
01:00
0105
0A8
pm11
6012
0404
34000
M802
323-04 beretion
LIVEE
AMOID
130000 Rermtton
0100
03
02
030
/600
1803
X:0M
30300 Leretion
12483
19:85
ARG
34000
PABS
10000 Rerstion
0189
210
0.35
0409
2.54
3.
-3872
-002
0
7200
1003
7700
103/0)
17223
150000
135306
30030
22000
5000
7000
130000
17/253
153005
175000
200030
Beration
Figure 7: Toy model L(01,02) = (03 + 1)0? + a 0g trained with gradient descent (left) and noisy gradient descent (right).
16


Reviews:
[{"review_id": "H1lum-xpYr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proves that under certain conditions, SGD on average decreases the\ntrace 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.\n\nLemma 1\nThis 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.\n\nPage 2: existence stationary state?\nWhat are the conditions for the existence of a stationary state? Is bounded noise sufficient?\n\nEquation 4 and local approximation\nRegarding 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“\nBut 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.\n\nAssumption on timescale separation\nThis section makes numerous claims that are not properly backed up.\n1) “This assumption is because there is a timescale separation between\nthe dynamics of \\theta_bar, which relax quickly and the dynamics of \\theta_hat, which evolve much more slowly as the minimal valley is traversed.“\nAre 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?\n2) 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:\nSimsekli, Umut, Levent Sagun, and Mert Gurbuzbalaban. \"A tail-index analysis of stochastic gradient noise in deep neural networks.\" arXiv preprint arXiv:1901.06053 (2019).\n\nTake away\nI 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.\n\n“This indicates that the trace itself is not sufficient to describe generalization (Neyshabur et al., 2017).“\nI do not see what aspect of Neyshabur et al. justifies your claim, please explain.\n\nExperiments\nAll 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.\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "BkermuA2tS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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. \n\nThe 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. \n\nThe 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. \n\nI 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. \n\nThe 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. \n\nMissing citation: \"an alternative view, when does SGD escape local minimal.\"\n\n\n\nAfter Rebuttal: I have read the authors' responses and acknowledge the sensibility of the statement.\n\n\n\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BJxOztS89r", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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\n\nIn 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:\n\n1. 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.\n\n2. Does the Hessian-noise covariance alignment exist for squared loss functions as well? Is this specific to log-likelihood models?\n\n3. 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.\n\nAdditional questions/comments:\n1. 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?\n\n2. 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?\n\n3. 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.\n\n4. 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.\n\nOverall 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.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

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