A Diffusion Theory For Deep Learning Dynamics: Stochastic Gradient Descent Exponentially Favors Flat Minima
Authors: Zeke Xie
Issei Sato
Masashi Sugiyama
Venue: ICLR 2021 Poster (2021)
Keywords: deep learning dynamics
SGD
diffusion
flat minima
stochastic optimization

Abstract: Stochastic Gradient Descent (SGD) and its variants are mainstream methods for training deep networks in practice. SGD is known to find a flat minimum that often generalizes well. However, it is mathematically unclear how deep learning can select a flat minimum among so many minima. To answer the question quantitatively, we develop a density diffusion theory to reveal how minima selection quantitatively depends on the minima sharpness and the hyperparameters. To the best of our knowledge, we are the first to theoretically and empirically prove that, benefited from the Hessian-dependent covariance of stochastic gradient noise, SGD favors flat minima exponentially more than sharp minima, while Gradient Descent (GD) with injected white noise favors flat minima only polynomially more than sharp minima. We also reveal that either a small learning rate or large-batch training requires exponentially many iterations to escape from minima in terms of the ratio of the batch size and learning rate. Thus, large-batch training cannot search flat minima efficiently in a realistic computational time.

Published as a conference paper at ICLR 2021
A DIFFUSION THEORY FOR DEEP LEARNING DYNAM- ICS: STOCHASTIC GRADIENT DESCENT EXPONEN- TIALLY FAVORS FLAT MINIMA
Zeke Xie!? Issei Sato 1,2, and Masashi Sugiyama?
'The University of Tokyo
RRKEN Center for AlP
xie @is ku-nk...ttkko.cc [sato, @ u-tokyoo.a..jp
ABSTRACT
Stochastic Gradient Descent (SGD) and its variants are mainstream methods for training deep networks in practice. SGD known to find a flat minimum that often generalizes well. However, it is mathematically unclear how deep learning can select a flat minimum among so many minima. To answer the question quantitatively, develop density diffusion theory to reveal how minima selection quantitatively depends on the minima sharpness and the hyperparameters. To the best of our knowledge, benefited from the Hessian- deasednnd covariance of stochastic gradient noise, SGD favors flat minima exponentially more than sharp minima, while Gradient Descent (GD) with injected white noise favors flat minima only polynomially more than sharp minima. We also reveal that either small learning rate or sarge-batch training requires exponentially many iterations to escape from minima in terms of the ratio of the batch size and learning rate. Thus, large-batch training cannot search flat minima efficiently in realistic computational time.
the first theoretically and empirically prove that,
INTRODUCTION
In recent years, deep learning (LeCun et al. (015) has achieved great empirical success in various application areas. Due to the over- pueepaaramettiztioon and the highly complex loss landscape of deep networks, optimizing deep networks is difficult task. Stochastic Gradient Descent (SGD) and its variants are mainstream methods for training deep networks. Empirically, SGD can usually find flat minima among a large number of sharp minima and local minima (Hochreiter & Schmidhuber 1995 More papers reported that learning flat minima closely relate to generalization (Hardt et al.
1997..
2016:
Zhang al. 70 Arpit et al., 2017 Hoffer et al.) 2017 Dinh al.) 2017 Neyshabur et al. koy]2017 Kleinberg et al. 2018). Some researchers specifically study flatness itself. They try measure flatness (Hochreiter & Schmidhuber 1997 Keskar et al.)
2017
et et |
Dziugaite & Roy 2017
2017
Sagun et al. 2017] Yao et al., 2018), rescale flatness (Tsuzuku et al.
2019 Xie et al.) (020b)).
and find flatter minima (Hotfer et al. 2017 Chaudhari al. 2017] al. 2019b Xie et al. (020a).
However, we still lack a quantitative theory that answers why deep learning dynamics selects flat minimum.
The diffusion theory is an important theoretical tool to understand how deep learning dynamics works. It helps us model the diffusion process of probability densities of parameters instead of model parameters themselves. The density diffusion process of Stochastic Gradient Langevin Dynamics (SGLD) under injected isotropic noise has been discussed by (Sato & Nakagawa 2014 Raginsky al. 2017 Zhang et al. 2017b] Xu et al. 2018), Zhu et al. (2019) revealed that anisotropic diffusion of SGD often leads to flatter minima than isotropic diffusion. A few papers has quantitatively studied the diffusion process of SGD under the isotropic gradient noise assumption. Jastrzębski ctt al. (2017) first studied the minima selection probability of SGD, (mith Le (2018) presented Beyesian perspective generalization of SGI). Wu et al. (2018) studied the escape problems of

---

we have four Published as a conference paper at ICLR 2021
SGD from dynamical perspective, and obtained the qualitative conclusion on the effects of batch size, learning rate, and sharpness. [uu et al. (2019) quantitatively showed that the mean escape time of SGD exponentially depends on the inverse learning rate. Achille & Soatto (2099) also obtained a related proposition that describes the mean escape time in terms of a free energy that depends on
the Fisher Information. [Li et al. (2017) analyzed Stochastic Differential Equation (SDE) of adaptive gradient methods. Nguyen et al. (2019) mainly contributed to closing the theoretical gap between continuous-time dynamics and discrete-time dynamies under isotropic heavy-tailed noise.
However, the related papers mainly analyzed the diffusion process under parameter-independdee and isotropic gradient noise, while stochastic gradient noise (SGN) is highly grrameter--eeendeen and anisotropic in deep learning dynamics. Thus, they failed to quantitatively formulate how SGD selects flat minima, which closely depends on the Hessian-dependent structure of SGN. We try to bridge the gap between the qualitative knowledge and the quantitative theory for SGD in the presence of parameter-dependent and anisotropic SGN. Mainly based on Theorem 3.2 contributions:
The proposed theory formulates the fundamental roles of gradient noise, batch size, the learning rate, and the Hessian in minima selection.
The SGN covariance is approximately proportional to the Hessian and inverse batch size.
Either small learning rate or large-batch training requires exponentially many iterations to escape minima in terms of ratio of batch size and learning rate.
To the best of our knowledge, we are the first to theoretically and empirically reveal that SGD favors flat minima exponentially more than sharp minima.
2 STOCHASTIC GRADIENT NOISE AND SGD DYNAMICS
We mainly introduce the necessary foundation for the proposed diffusion theory in this section. We denote the data samples as { the model parameters 0 and the loss function over data samples x as L(0, x)). For simplicity, we denote the training loss as L(0). Following Mandt al. (2017), we may write SGD dynamics as
O((O.) a0;
OL(())
0.+1 0
00, +n((0))&
where f.(0) is the loss of one minibatch, S. No0 T), and C(0) represents the gradient noise covariance matrix. The classic approach is to model SGN by Gaussian noise,N((. C(O)) (Mandt ct al. 2017, Smith & Le. 2018 Chaudhari & Soatto 2018).
Stochastic Gradient Noise Analysis. We first note that the SGN we study is introduced by minibatch
training, C(O,))&G+ aL(0,) af.).) which is the difference between gradient descent and stochastic 09, 00,
gradient descent. According to Generalized Central Limit Theorem (Gnedenko et al. 1954), the mean of many anfinite-variane random variables converges stable distribution, while the mean of many finite-variance random variables converges to Gaussian distribution. As SGN is finite in practice, we believe the Gaussian approximation of SGN reasonable.
Simsekli et al. (2019) argued that SGN is Lévy noise (stable variables), rather than Gaussian noise. They presented empirical evidence showing that SGN seems htave- and the heave-tailed distribution looks closer to stable distribution than a Gaussian distribution. However, this research line (Simsekli al., 2019 Nguyen al.) 2019) relies on hidden strict assumption that SGN must be isotropic and obey the same distribution across dimensions. (Simsekli et al.] (2019) computed "SGN" across n model parameters and regarded "SGN" as samples drawn from single-variant distribution. This is why one tail-index for all parameters arguments in Simseklli et al. (2019) did not necessarily hold for parameter-des depeeder- and anisotropic Gaussian noise. In our paper, SGN computed over different minibatches obeys n-variant Gaussian distribution, which can be parameter- -eepenee-- and anisotropic.
studied in Siimsekli et al. (2019). The
In Figure I empirically verify that SGN is highly similar Gaussian noise instead of heavy-tailed Lévy noise. We recover the experiment of Simsekli et al.] (2019) to show that gradient noise is approximately Lévy noise only if it is computed across parameters. Figure T actually suggests that
2

---

Published as a conference paper at ICLR 2021
016
10
040
0.9
KOT 1OLEOO 441
(a) "SGN" across parame- ters
(b) Lévy noise
(c) SGN
across
mini-
(d) Gaussian noise
batches
Figure 1: The Stochastic Gradient Noise Analysis. The histogram of the norm of the gradient noises computed with the three-layer fully-connected network on MNIST (LeCun) 1998). (a) and (c): the histograms of the norms of two kinds of gradient noise: (a) "SGN" is computed over parameters, which is actually stochastic gradient rather than SGN; (c) SGN is computed over minibatches. (b) and (d): the histograms of the norms of (scaled) Gaussian noise and Lévy noise. Based on (a) and (b), Simsekli et al. (2019) argued that gradient noise across parameters is heavy-tailed Lévy noise. Based on (c) and (d), we show that SGN without the isotropic restriction is approximately Gaussian.
the contradicted observations from the different formulations of gradient noise. Simsekli et al. (2019) studied the distribution SGN as a single-variant distribution, while we relax as a n n-vaiiant distribution. Our empirical analysis in Figure holds well at least when the batch size B is larger than 16, which is common in practice. Similar empirical evidence can be observed for training ResNet18 (He et al. 2016) on CIFAR-10 (Krizhevsky al. 2009). seen in Appendix C
Panigrahi et al. 2019) also observed that for batch sizes 256 and above, the distribution of SGN best described Gaussian at-least in the early phases of training. Comparing our results with Panigrahi et al. (2019), we noticed that the Gaussianity of SGN may depend on more unknown factors. First, SGN on random models more Gaussian than well-trained models. Second, the layer/network matters. Because SGN on some layers/networks is more Gaussian than other layers/networks.
The isotropic gradient noise assumption too rough to capture the Hessian-dependent covariance structure of SGN, which we will study in Figure 2 later. Our theory that focuses on parameter- dependent and anisotropic SGN brings a large improvement over existing parameter-inde inneeeerriddeeedeent and isotropic noise, although Simsekli et al. (2019) brought improvement over more conventional parameter-independen and isotropic Gaussian noise. A more sophisticated theory interesting under independent anisotropic heavy-tailed noise, when the batch size is too small (B 1) to apply Central Limit Theorem. We will leave it as future work.
although/Simsekii
SGD Dynamics. Let us replace by dt unit time. Then the continuous-time dynamics of SGD
(Coffey & Kalmykov 2012) is written as
OL(0) 00 dt + +2D(0))
d0
(2)
where dW, ~ (0, Idt) and D(0) time dynamics is equal to the product of the number of iterations T and the learning rate ry: t = TYT. The associated Fokker-Planck Equation written as
3 (()). We note that the dynamical time t the continuous-
OP(0,1) -V. VL))) + V VD(O)P(O, Ot
(3)
Σ A HA, P(0,t)
OL(O)
82
+ ΣΣ
D Di, (0)
(4)
00,
00:08,
where V a nabla operator, and Dij is the element the ith row and jth column D. standard SGLD, the injected gradient noise is fixed and isotropic Gaussian, D = T.
3

---

Published as a conference paper at ICLR 2021
(a) Pretrained Model
(b) Pretrained Model
(c) Random Model
(d) Random Model
Figure 2: We empirically verified C(O) = H(0) by using three-layer fully-connected network on
MNIST LeCun 1998). The pretrained Models are usually near critical points, while randomly Initialized Models are far from critical points. We display all elements H(..)) E [Le - 4, 0.5] of the Hessian matrix and the corresponding elements C(..) of gradient noise covariance matrix in the space spanned by the eigenvectors of Hessian. Another supplementary experiment on Avila Dataset (De Stefano et al. 2018 in Appendix C reports Cavita s 1.004 H B The small difference factor between the empirical result and the ideal Equation mainly because the pretrained network is perfectly located at critical point.
The next guestion is how to formulate the SGN covariance C(0) for SGD? Based on Smith & Le (2018), we can express the SGN covariance as
1
m
m
((0)
VL(O, By VL),, VL(O)LL(0)
VL(6, (L, x.)
B
m
Bm
The approximation is true near critical points, due to the fact that the gradient noise variance dominates the gradient mean near critical points. We know the observed fisher information matrix satisfies
FIM(0) RJ (0) near minima, referring to Chapter 8 of (Pawitan 2001 Following Jastrzębski et al. (011): Zhu et al. (211)), we obtain
Σ C(I) = Bm 3=1
VL(0,x,)VL0,2))
1 1 FIM(O) = H(O),
(6)
B
B
which approximately gives
D C(0) " H())
2B
near minima. It indicates that the SGN covariance C(0) is approximately proportional to the Hessian H()) and inverse to the batch size B. Obviously, we can generalize Equation 7 by D(0) = *Cte) n (0)} near critical points, when there exist negative eigenvalues in H 2B along some directions. We use [-]+ to denote the positive semidefinite transformation of sym- metric matrix: we have the eigendecomposstion H = U diag(H,, Hn-1, H, H then [H]+= = U diag(| 1|,
11, H..))
We empirically verify this relation in Figure 2 for pretrained fully-connected networks, and a follow- up paper[Xin Xic et al. (200cc) first verified this relation for randomly initialized fully mullecconeected networks on real-world datasets. The Pearson Correlation is up to 0.999 for pretrained networks. We note that, the relation still approximately holds for even the randomly network, which is far from critical points. The correlation is especially high along the flat directions with small-mannitud, eigenvalues of the Hessian (Xie et al. 2020c). We emphasize that previous papers with the isotropic Lévy Gaussian noise approximation all failed to capture this core relation in deep learning dynamics.
3 SGD DIFFUSION THEORY
We start the theoretical analysis from the classical Kramers Escape Problem (Kramers assume there two valleys, Sharp Valley aj and Flat Valley az, seen in Figure Also Col b is the
1940). We
4

---

Published as a conference paper at ICLR 2021
(a) I-Dimensional Escape
(b) High- Sech-Dimensioal Escape
Figure 3: Kramers Escape Problem. d1 and are minima of two neighboring valleys. b is the saddle point separating the two valleys. e llccaee outside of Valley a1
boundary between two valleys. What is the mean escape time for a particle governed by Equation 2 escape from Sharp Valley ai Flat Valley ag? The mean escape time widely used in related statistical physics and stochastic process Van Kampen
1992.
Nguyen et al. (211)).
Lipschutz et al. 2009) states that the surface integral of vector field over closed surface, which is called the flux through the surface, is equal the volume integral of the divergence over the region inside the surface. We respectively denote the mean escape time as the escape rate as y, and the probability current as J. We apply Gauss's Divergence Theorem the Plakck Equation resulting
Gauss's Divergence Theorem (Arfken & Weber 1999
IP(0,1) -..-V-... v((,t).) Ot
[P(O.t)VL(0)) (O(0))((,
The mean escape time is expressed (Van Kampen
1992) as
T P(0 Vo)
Js. J
where P(O Vo) - Jv. P(O)dV is the current probability inside Valley a, J is the probability current produced by the probability source P(0 E Va). = J dS the probability flux (surface integrals of probability current). S, is the surface (boundary) surrounding Valley a, and Va is the volume surrounded by Sa. We have j = J in the case of me--imensioonl escape.
Classical Assumptions. We state three classical assumptions first for the density diffusion theory. Assumption T is the common second order Taylor approximation, which
also used by (Mandt and 3 are widely used in many fields' Kramers
et al. 2017: Zhang et al.) 2019). Assumptions 2
Escape Problems, including statistical physics Kramers 1940 Hanggi 1986). chemistry (Eyring
1935 Hänggi et al. 1990), biology (Zhou) 2010), electrical engineering (Coffey & Kalmykov 2012).
and stochastic process (Van Kampen 1992 Berglund 2013). Related machine learning papers
JJsttzębski et al. 2017 usually used Assumptions 2 and 3 as the background of Kramers Escape
Problems.
Assumption (The Second Order Taylor Approximation). The loss function around critical points O* can be approximately wrilten as
1 -00000000000000000000
L( L(0))
Assumption (Quasi-Equlibriiu) Approximation). The system in quasi- muusi--quilibrium near minima.
Assumption (Low Temperature Approximation). The gradient noise is small (low temperature).
We will dive into these two assumptions deeper than previous papers for SGD dynamics. Assumptions 2 and 3 both mean that our diffusion theory can better describe the escape processes that cost more iterations. As this class of "slow" escape processes takes main computational time compared with "fast" escape processes, this class of "slow" escape process is more interesting for training of deep neural networks. Our empirical analysis in Section 4 supports that the escape processes in the
5

---

Published as a conference paper at ICLR 2021
wide range of iterations (50 to 100,000 iterations) can be modeled by our theory very well. Thus, Assumption 2 and are reasonable in practice. More discussion can be found in Appendix B
Escape paths. We generalize the concept of critical points into critical paths the path where I) the gradient perpendicular to the path direction must be zero, and 2) the second order directional derivatives perpendicular to the path direction must be nonnegative. The Most Possible Paths (MPPs) for escaping must be critical paths. The most possible escape direction at one point must be the direction of one eigenvector of the Hessian at the point. Under Assumption 3 the probability density far from critical points and MPPs is very small. Thus, the density diffusion will concentrate around MPPs. Draxler et al. (2018) 8 reported that minima in the loss landscape of deep networks are connected by Minimum Energy Paths (MEPs) that are essentially flat and Local MEPs that have high-loss saddle points. Obviously, MPPs in our paper correspond to Local MEPs. The density diffusion along MEPs, which are strictly flat, is ignorable according to our following analysis.
The boundary between Sharp Valley d1 and Flat Valley d2 is the saddle point The Hessian at b, Hb. must have only one negative eigenvalue and the corresponding eigenvector is the escape direction. Without losing generality, we first assume that there is only one most possible path through Col b existing between Sharp Valley d₁ and Flat Valley d2-
SGLD diffusion. We first analyze simple case: how does SGLD escape sharp minima? Researchers interested in SGLD, when the injected noise dominates SGN 17 - 0 in final epochs. Because SGLD may work as a Bayesian inference method in this limit (Welling & Tch 20IT). SGLD is usually simplified Kramers Escape Problem with thermo noise in statistical physics. We present Theorem [.1] We leave the proof in Appendix [ We also note that more precise SGLD diffusion analysis should study mixture of injected white noise and SGN.
Gradient Descent with injected white noise, whose behavior is identical to
Theorem 3.1 (SGLD Escapes Minima). The loss function L(0) is of class C2 and n-dimensional.
Only one most possible path exists between Valley a and the outside of Valley If Asssmpttinn / 3 hold, and the dynamics is governed by SGLD, then the mean escape time from Valley a to the outside of Valley is
1
del(Hs)
HHbe) exp (
1
AL
2m
dct(Haa
We denote that Ha and Hy are the Hessians of the loss function at the minimum a and the saddle point b, AL L(b)- L(a) is the loss barrier height, indicates the escape direction, and Hbee is the eigenvalue of the Hessian Hr, corresponding to the escupe direction. The diffusion coefficient D is usually set to 1 in SGLD..
SGD diffusion. However, SGD diffusion is essentially different from SGLD diffusion in several aspects: 1) anisotropic noise, 2) parameter-dependent noise, and 3) the stationary distribution of SGD
far from the Gibs-Bolt distribution, P(0) 1 exp -00 ) These different characteristies make SGD diffusion behave differently from known physical dynamical systems and much less studied than SGLD diffusion. We formulate Theorem 3.2 for SGD. We leave the proof in Appendix The theoretical analysis of SGD can be casily generalized to the dynamics with a mixture of SGN and injected white noise, as long as the eigenvectors of ((0) are closely aligned with the eigenvectors of (0).
Theorem 3.2 (SGD Escapes Minima). The loss function I(O)) is of class C² and n-dimensional. Only one most possible path exists between Valley a and the outside of Valley If Assumption | hold, and the dynamics is governed by SGD, then the mean escape time from Valley to the outside of Valley is
1
2BAL
(
(1 (1-s) [H
2T
H
exp
Hos
where s E (0, 1) is a path-dependent parameter, and Hac and Hoe are, respectively, the eigenvalues of the Hessiann at the minimum a and the saddle point b corresponding to the escupe direction e.
Multiple-path escape. Each escape path contributes to the total escape rate. Multiple paths combined together have a total escape rate. there are multiple parallel from the start valley to the end valley, can compute the total escape rate easily based on the following computation rule. The computation

---

Published as a conference paper at ICLR 2021
Feurce Combiran
Peamas stare
(a) - log(()) =
(b) - log(n) O(B)
(c) - log(1) 0(2)
Figure 4: The mean escape time analysis of SGD by using Styblinski Tang Function. The Pearson Correlation is higher than 0.99. Left Column: Sharpness. Middle Column: Batch Size. Right Column: Learning Rate.
rule is based on the fact that the probability flux integrals are additive. We can easily generalize the mean escape time analysis into cases that there are multiple parallel escape paths indexed by p. As for multiple-valley escape problems, multiple two-valley escape problems. We also note that, while Theorem A.2 does not depend the dimensionality directly, higher dimensionality may increase the number of escape paths and loss valleys, and change the spectrum of the Hessians.
always reduce multiple-valley escape problem into
Rule 1. If there are multiple MPPs between the start valley and the end valley, then Ttotal = Epp Yo
Thus, we only need to find the saddle points that connect two valleys as we analyzed in the paper and analyze the escape rates.
Minima selection. Now, we may formulate the probability of minima selection as Proposition We leave the proof in Appendix A.3] In deep learning, one loss valley represents the landscape contain many good modes and bad modes. SGD transits from one mode to another mode during training. The mean escape time of one mode corresponds to the number of iterations which SGD spends on this mode during training, which is naturally proportional to the probability of selecting this mode after training.
mode and
Proposition Suppose there are two valleys connected by an escape path. all assumptions of Theorem 3.2 hold, then the stationary distribution of locating these valleys is given by
P(0 V.) =
Ta
Σ
where u is the index of valleys, and Ty is the mean escape time from Valley v to the outside of Valley v.
4 EMPIRICAL ANALYSIS
In this section, we try to directly validate the escape formulas on real-world datasets. Fach escape process, from the inside of loss valleys the outside of loss valleys, are repeatedly simulated for 100 times under various gradient noise scales, batch sizes, learning rates, and sharpness.
How to compare the escape rates under the same settings with various minima sharpness? Our method is to multiply a rescaling factor Vk each parameter, and the Hessian will be proportionally rescaled by factor k. If we let L(0) f(0) - L()) = f(Vk0), then H (0) V f()) H (0)
f()) Thus, we can use l/ to indicate the minima sharpness. The theoretical relations of SGD
we try to validate can be formulated as: (1) log(>) O()) (2) log(r) O(B), and (3)
(o) = O
The mean escape time analysis of SGD. Styblinski-Tame Function, which has multiple minima and saddle points, is common test function for nonconvex optimization. We conduct intuitional 10-dimensional experiment, where the simulations start from a given minimum and terminate when reaching the boundary of the loss valley. The number of iterations is recorded for calculating
7

---

Published as a conference paper at ICLR 2021
Cormil 810000
Phanse Gemill 8150000
Peanen Oatre EE 5.03
(a) - log(n)) = +
(b) - log(7) O(B)
(c) - log(n) = 0(2)
Figure 5: The mean escape time analysis of SGD by training neural networks on Avila Dataset. Left Column: Sharpness. Middle Column:Batco Size. Right Column: Learning Rate. We leave the results on Banknote Authentication, Cardiotocography, and Sensorless Drive Diagnosis in Appendix
Penteer Comilation 5.9911
Pratten Came adin 0.2934
Intenaa
Intenaa
(a) 7= 0kk)
(b) - log( = 0
Peasser Cancrranti39333
Pearsen Cemee 0337785
(c) O(k)
(d) - log( 0(
Figure 6: The mean escape time analysis of SGLD. Subfigure (a) and (b): Styblinski -anni Function. Subfigure (c) and (d): Neural Network.
the escape rate. We also train fully connected networks on four real-world datasets, including a) Avila, b) Banknote Authentication, c) Cardiotocography, d) Dataset for Sensorless Drive Diagnosis (De Stefano et al., [2088] Dua & Graff (017). Figure4aand Figure Jigurlyy verifies that the escape rate exponentially depends on the minima sharpness (reflected by k), the batch size, and the learning rate on both test functions and real-world training. which fully supports our theoretical results.
Model architecture and details: We used fully-connected networks with the depth and the width 10 in Figure The experiments using Logistic Regression and Fully-connected networks with the depth 3 are presented in Appendix We leave more experimental details and results in Appendix D. and Appendix B
The mean escape time analysis of SGLD, We try to validate = O(k) and - log(7) = O for SGLD (dominated by injected Gaussian noise). Figure 6 shows that SGLD only favors flat minima polynomially more than sharp minima as Theorem 3.I indicates. Figure also verifies that the injected gradient noise scale exponentially affects flat minima selection.
8

---

Published as a conference paper at ICLR 2021
5 DISCUSSION
SGD favors flat minima exponentially more than sharp minima. We can discover few inter- esting insights about SGD by Theorem 3.2 Most importantly, the mean escape time exponentially depends on the eigenvalue of the Hessian at minima along the escape direction, Hae- Thus, SGD favors flat minima exponentially more than sharp minima. We claim one main advantage of SGD comes from the exponential relation of the mean escape time and the minima sharpness. The measure of "sharpness" has reformed in contexts of SGLD and SGD. In the context of SGLD, the "sharpness" is quantified by the determinant of the Hessian. In the context of SGD, the "sharpness" is quantified by the top eigenvalues of the Hessian along the escape direction. Based on the proposed diffusion theory, recent work (Xie al., 2020c) successfully proved that SGD favors flat minima significantly more than Adam.
The ratio of the batch size and the learning rate exponentially matters. Theorem 3.2 explains
why large-batch training can easily get trapped near sharp minima, and increasing the learning rate proportionally helpful for large-batch training (Krizhevsky 22044] Keskar et al.. 2017 Sagun et al. 20177 Smith et al., 2018 Yao et al. 20188) He et al. 2019a). We argue that the main cause large-batch training expects exponentially longer time to escape minima. Note that, as the mean escape time in the theorems is equivalent to the product of the learning rate and the number of iterations, both the number of iterations and dynamical time exponentially depend on the ratio of the batch size and the learning rate. The practical computational time in large-batch training is usually too short to search many enough flat minima. We conjecture that exponentially increasing training iterations may be helpful for large batch training, while this is often too expensive in practice.
Low dimensional diffusion. Most cigenvalues of the Hessian at the loss landscape of over- parametrized deep networks are close to zero, while only a small number of cigenvalues are large (Sagun et al. 2017] Li et al. 2018). Zero eigenvalues indicate zero diffusion along the corresponding directions. Thus, we may theoretically ignore these zero-eigenvalue directions. This also indicates that the density diffusion is ignorable along an essentially flat MEP in Draxler et al. (2188)
As the escape rate exponentially depends the corresponding eigenvalues, small number of large eigenvalues means that the process of minima selection mainly happens in the relatively low di- mensional subspace corresponding to top eigenvalues of the Hessian. Gur-Ari et al. (2018) also reported a similar finding. Although the parameter space is very high-dimensional. SGD dynamics hardly depends on those "meaningless" dimensions with small second order directional derivatives. This novel characteristic of SGD significantly reduces the explorable parameter space around one minimum into much lower dimensional space.
High-order effects. As we have applied the second-orde order Taylor approximation near critical points, our SGD diffusion theory actually excludes the third-order and higher-order effect. The asymmetric valley in He et al.) 2019b)), which only appears in high-order analysis, is beyond the scope of this paper. However, we also argue that the third-order effect much smaller than the second-orde effect under the low temperature assumption in Kramers Escape Problems. We will leave the more refined high-order theory as future work.
6 CONCLUSION
In this paper, we demonstrate that one essential advantage of SGD is selecting flat minima with an exponentially higher probability than sharp minima. To the best of our knowledge, we are the first to formulate the exponential relation of minima selection to the minima sharpness, the batch size, and the learning rate. Our work bridges the gap between the qualitative knowledge and the quantitative theoretical knowledge on the minima selection mechanism of SGD. We believe the proposed theory not only helps us understand how SGD selects flat minima, but also will provide researchers a powerful theoretical tool to analyze more learning behaviors and design better optimizers in future.
ACKNOWLEDGEMENT
We thanks Dr. Yuanqian Tang for helpful discussion. MS was supported by the International Research Center for Neurointelligence (WPI-IRCN) at The University of Tokyo Institutes for Advanced Study.
9

---

Published as a conference paper at ICLR 2021
REFERENCES
Alessandro Achille and Stefano Soatto. Where is the information in a deep neural network? arXiv preprint arXiv:I905.122 12213, 2019.
George B Arfken and Hans J Weber. Mathematical methods for physicists, 1999.
Devansh Arpit, Stanislaw Jastrzebski, Nicolas Ballas, David Krueger, Emmanuel Bengio, Maxinder Kanwal, Tegan Maharaj. Asja Fischer, Aaron Courville, Yoshua Bengio, et closer look at memorization in deep networks. In International Conference on Machine Learning, pp. 233-242, 2017.
Nils Berglund. Kramers' law: Validity, derivations and generalisations. Markov Processes and Related Fields, 4963)445--49,, 2013.
Pratik Chaudhari and Stefano Soatto. Stochastic gradient descent performs variational inference. converges to limit cycles for deep networks. In 2018 Information Theory and Applications Workshop (ITA), pp- 1-10. IEEE, 2018.
Pratik Chaudhari, Anna Choromanska, Stefano Soatto, Yann LeCun, Carlo Baldassi, Christian Borgs, Jennifer Chayes, Levent Sagun, and Riccardo Zecchina. Entropy-sgd: Biasing gradient descent into wide valleys. In International Conference on Learning Representations, 2017.
William Coffey and Yu P Kalmykov. The Langevin equation: with applications to stochastic problems in physics, chemistry and electrical engineering, volume 27. World Scientific, 2012.
Claudio De Stefano, Marilena Maniaci, Francesco Fontanella, and A Scotto di Freca. Reliable writer identification in medieval manuscripts through page layout features: The "avila" bible case. Engineering Applications of Artificial Intelligence, 72:99-110, 100 2018
Laurent Dinh, Razvan Pascanu, Samy Bengio, and Yoshua Bengio. Sharp minima can generalize for deep nets. In International Conference on Machine Learning, pp. 1019-1028, 2017.
Felix Draxler, Kambis Veschgini, Manfred Salmhofer, and Fred Hamprecht. Essentially no barriers in neural network energy landscape. In International Conference on Machine Learning, pp. 1309-1318 1318, 2018.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. ARLLt:p//arcivve ics. uci edu/ml
Gintare Karolina Dziugaite and Daniel M Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. arXiv preprint arXiv: 10008 2017.
Henry Eyring. The activated complex in chemical reactions. The Journal of Chemical Physics, 3(2): 107-115, 1935.
BV Gnedenko, AN Kolmogorov. BV Gnedenko, and AN Kolmogorov. Limit distributions for sums of independent. Am. Math, 105, 1954.
Guy Gur-Ari, Daniel A Roberts, and Ethan Dyer. Gradient descent happens in a tiny subspace. arXiv preprint 11X1v:1812.04777 2018.
Peter Hanggi. Escape from metastable state. Journal of Statistical Physics, 42(1-2):105 148, 1986.
Peter Hänggi, Peter Talkner, and Michal Borkovee. Reaction-rate theory: fifty years after kramers. Reviews of modern physics, 62(2):251, 1990.
Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International Conference on Machine Learning, pp. 1225-1234, 2016.
Fengxiang He. Tongliang Liu, and Dacheng Tao. Control batch size and learning rate to generalize well: Theoretical and empirical evidence. In Advances Neural Information Processing Systems, pp. 1411-1550 2019a.
10

---

Published as a conference paper at ICLR 2021
Haowei He, Gao Huang, and Yang Yuan. Asymmetric valleys: Beyond sharp and flat local minima. In Advances in Neural Information Processing Systems 32, pp. 2549-256666 2019b.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition. pp. 770-778, 2016.
Sepp Hochreiter and Jürgen Schmidhuber. Simplifying neural nets by discovering flat minima. In Advances in neural information processing systems, pp. 329-536, 1995.
Sepp Hochreiter and Jürgen 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 Advances in Neural Information Processing Systems, pp. 1129-1739, 2017.
Wenging Hu, Chris Junchi Li, Li, and Jian-Guo Liu. On the diffusion approximation of nonconvex stochastic gradient descent. Annals of Mathematical Sciences and Applications, 4(1):3 2019.
Stanislaw Jastrzębski, Zachary Kenton, Devansh Arpit, Nicolas Ballas, Asja Fischer, Yoshua Bengio, and Amos Storkey. Three factors influencing minima in sgd. arXiv preprint arXiv: 2017.
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 International Conference on Learning Representations, 2017.
Robert Kleinberg, Yuanzhi Li, and Yang Yuan. alternative view: When does sgd escape local minima? In International Conference Machine Learning, pp. 2703-2712, 2018.
Hendrik Anthony Kramers. Brownian motion in field of force and the diffusion model of chemical reactions. Physica, 7(4):284-304 1940.
Alex Krizhevsky, One weird trick for parallelizing convolutional neural networks. arXiv preprint arXiv:1404.5997, 2014.
Alex Krizhevsky, Geoffrey Hinton, al. Learning multiple layers of features from tiny images. 2009.
Yann LeCun. The mnist database of handwritten digits. http://yann. lecun. com/exdb/nmist// 1998.
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. nature, 521((753)):366, 2015.
Hao Li, Zheng Xu, Gavin Taylor, Christoph Studer, and Tom Goldstein. Visualizing the loss landscape of neural nets. In Advances in Neural Information Processing Systems, pp. -399, 2015 8.
Qianxiao Li, Cheng Tai, et al. Stochastic modified equations and adaptive stochastic gradient algorithms. Proceedings of the 34th International Conference on Machine Learning-Von Volume 70, pp. 2101-2110. JMLR. org, 2017.
Seymour Lipschutz, Murray R Spiegel, and Dennis Spellman. Vector analysis and introduction lensor analysis. McGraw-Hill, 2009.
Stephan Mandt, Matthew D Hoffman, and David M Blei. Stochastic gradient descent as approximate bayesian inference. The Journal of Machine Learning Research, 18(1):487344907, 2017.
Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nati Srebro. Exploring general- ization in deep learning. In Advances in Neural Information Processing Systems, pp. 2017.
Thanh Huy Nguyen, Umut Simsekli, Mert Gurbuzbalaban, and Gaël Richard. First exit time analysis of stochastic gradient descent under heavy-tailed gradient noise. In Advances in Neural Information Processing Systems, pp. 273-283, 2019.
Abhishek Panigrahi, Raghav Somani. Navin Goyal, and Pranceth Netrapalli. Non Non-gaussianity of stochastic gradient noise. arXiv preprint arXiv: 19 19.00966, 2019.

---

Published as a conference paper at ICLR 2021
Yudi Pawitan. In all likelihood: statistical modelling and inference using likelihood. Oxford University Press, 2001.
Maxim Raginsky, Alexander Rakhlin, and Matus Telgarsky. Non-convex learning via stochastic gradient langevin dynamies: a nonasymptotic analysis. Conference on Learning Theory, pp- 1674-1703, 2017.
Levent Sagun, Utku Evci, V Ugur Guney, Yann Dauphin, and Leon Bottou. Empirical analysis of the hessian of over- werr-parametrized neural networks. arXiv preprint arXiv: 04454, 2017.
Issei Sato and Hiroshi Nakagawa. Approximation analysis of stochastic gradient langevin dynamics by using fokker-p planckk equation and ito process. International Conference on Machine Learning. pp. 982-990, 2014.
Umut Simsekli,, Levent Sagun, and Mert Gurbuzbalaban. A tail-index analysis stochastic gradient noise in deep neural networks. In International Conference Machine Learning, pp. 5827-5837, 2019.
Samuel L Smith and Quoe Le. A bayesian perspective on generalization and stochastic gradient descent. International Conference on Learning Representations, 2018.
Samuel L Smith, Pieter-Jan Kindermans, and Quoc Le. Don't decay the learning rate, increase the batch size. In International Conference on Learning Representations, 2018
Yusuke Tsuzuku, Issei Sato, and Masashi Sugiyama. Normalized flat minima: Exploring scale invariant definition of flat minima for neural networks using pac-bayesian analysis. arXiv preprint 19X.v:9901.04633 2019.
Nicolaas Godfried Van Kampen. Stochastic processes in physics and chemistry, volume 1, Elsevier, 1992.
Max Welling and Yee W Teh. Bayesian learning via stochastic gradient langevin dynamics. In Proceedings of the 28th international conference on machine learning (ICML-11), pp. 681-688, 2011.
Lei Wu, Zhanxing Zhu, et al. Towards understanding generalization of deep learning: Perspective of loss landscapes. arXiv preprint arXiv://066 10239, 2017.
Lei Wu, Chao Ma, and E Weinan. How sgd selects the global minima in over-parameterized learning: dynamical stability perspective. Advances Neural Information Processing Systems, pp- 2279-8288. 2018
Zeke Xie, Fengxiang He, Shaopeng Fu, Issei Sato, Dacheng Tao, and Masashi Sugiyama. Artificial neural variability for deep learning: On overfitting, noise memorization, and catastrophic forgetting. arXiv preprint arXiv:201 /. /.06220, 2020a.
Zeke Xie, Issei Sato, and Masashi Sugiyama. Stable weight decay regularization. arXiv preprint 1rXiv:2011.11111 2020b.
Zeke Xie, Xinrui Wang, Huishuai Zhang, Issei Sato, and Masashi Sugiyama. Adai: Separating the effects of adaptive learning rate and momentum inertia. arXiv preprint 2.5i::2000.188115 2020c.
Pan Xu. Jinghui Chen, Difan Zou, and Quanquan Gu. Global convergence of langevin dynamics based algorithms for nonconvex optimization. In Advances in Neural Information Processing Systems, pp- 3122-3133, 2018
Zhewei Yao, Amir Gholami, Qi Lei, Kurt Keutzer, and Michael W Mahoney. Hessian-based analysis of large batch training and robustness adversaries. In Advances in Neural Information Processing Systems, pp. 4949-4951 2018.
Chiyuan Zhang, Samy Bengio. Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In International Conference on Machine Learning, 2017a.
12

---

Published as a conference paper at ICLR 2021
Guodong Zhang, Lala Li, Zachary Nado. James Martens, Sushant Sachdeva, George Dahl, Chris Shallue, and Roger B Grosse. Which algorithmic choices matter at which batch sizes? insights from noisy quadratic model. In Advances in Neural Information Processing Systems, pp. 8196-8207, 2019.
Yuchen Zhang, Percy Liang, and Moses Charikar. A hitting time analysis of stochastic gradient langevin dynamics. In Conference on Learning Theory, pp. 1980-2022, 2017b.
Huan Huan-Xiang Xiang Zhou. Rate theories for biologists. Quarterly reviews of biophysics, 43(2):219-293, 2010.
Zhanxing Zhu, Jingfeng Wu, Bing Yu, Lei Wu, and Jinwen Ma. The anisotropic noise in stochastic gradient descent: Its behavior of escaping from sharp minima and regularization effects. In ICMI., pp. 7654-7663, 2019.
A PROOFS
A.1 PROOF OF THEOREM 3.1
This proposition is well known conclusion in statistical physics under Assumption I and We still provide an intuitional proof here, and the following proof of SGD Diffusion will closely relate to this proof. We decompose the proof into two steps: 1) compute the probability of locating in valley a, P(O E Va), and 2) compute the probability flux j = Ss. dSS
Proof.
3
Without losing generality, we first prove the one-dimensional case.
Step 1: Under Assumption [ the stationary distribution around minimum a is P(0)
P(a) expl- _00)((1)), where 7' D. Under Assumption 3 we may only consider the second order Taylor approximation of the density function around critical points. We use the 7 notation as the temperature parameter in the stationary distribution, and use the D notation as the diffusion coefficient in the dynamics, for their different roles.
P(O E Va)
(10)
= P(O)dV
=
(11)
= - P(a) exp
L(0)= - L(a)
d0
(12)
T
10 a) (Ha(0 a) + O(483)
= =P(a) exp
d0
(13)
VEV.
T
=P(a) (2
(14)
H
Step 2:
J -PP(O]V P(O)VD+ + DVP(O)
(15)
VD DVL(O)
D
J - VI(0)
(16)
T
D VD (TT -1 VL
(17)
Apply this result to the Fokker-Planck Equation have
V ((D(O)P(O.t))
(18)
-111 VI((0) P(O,t)
DVP(0,))+
(19)
13

---

Published as a conference paper at ICLR 2021
And thus obtain the Smoluchowski equation and new form of
aP(0,t) 0t
V. D VL(0)+ + P(O,t)
=
(20)
-[(0) V exp [(00)
((0) Dxp
P(O)
(21)
We note that the probability density outside Valley must be zero, P(c) = 0. As we want to compute the probability flux escaping from Valley the proof, the probability flux escaping from other
valleys into Valley a should be ignored. Under Assumption 2 we integrate the equation from Valley a the outside of Valley along the most possible escape path
a
L(0) T
L(0) T
exp
P(O)
dB
exp
d0
(22)
00
Ja
(())
((00)
exp
P(O) -
exp
d0
(23)
T
T
L(a)
P(a) f exp
L(0))
0 exp
d0
(24)
T
T
a
D eex
Lia)
P(a)
T
J
(25)
Sa exp
L(0)
d0
We move J. to the outside of integral based on Gauss's Divergence Theorem, because J is fixed on the escape path from one minimum to another. As there is no field source on the escape path, fy V. J(O)VV = Then VJ(0) = 0. Obviously, only minima are probability sources in deep learning. Under Assumption and the second-order Taylor approximation, we have
L(0) T
exp
d0
(26)
L(b) + (0 T) Ho - b) + O
exp
d0
(27)
T
L(b)
+oo
[0
b) Hs( b)
exp
exp
d0
(28)
T
T
((b)
2TT
cxp
(29)
T
Hyl
Based the results of Step I and Step obtain
Ss. J.dS
J
(30)
P(O V.)
P(0 Va)
DP(a) exp
(((a)
1
(31)
cxp
L(b)
T
2xT [Hbl
P(a)
2xT
H.
D. H.
Hol
ALab
exp
(32)
2TT
T
H..
ALab
exp
(33)
2T
D
We generalize the proof of one-dimensional diffusion high-dimensional diffusion
14

---

Published as a conference paper at ICLR 2021
Step 1:
P(O E Va)
(34)
- P(0)dV JBEV.
(35)
-hev. Joev. exa)exp
L(O) L(a) dV
(36)
T
=P(a) / exp
1 a) Ha10 a) 0(A09)
dV
(37)
JBV.
T
(2xT)
=P(a) det det(H))²
(38)
Step 2: Based the formula of the one-dimensional probability current and flux, obtain
ds
(39)
2 (0 b)
H (0
b)
=J Jn exp
ds
(40)
Sb
T
(2 2
= Jb
(41)
111-11
111 Hni)
So have
I1:=1 Hoi
AL
T 1 V det(Ha) Hbel
exp
T
(42)
del(H)) 1
AL
2m
exp
(43)
(ot(Ha) |Hbel
D
A.2 PROOF OF THEOREM 3.2
Proof. We decompose the proof into two steps and analyze the one-dimensional case like before. The following proof is similar to the proof of SGLD except that make Ta the temperature near the minimum and T3 the temperature near the saddle point b.
One-dimensional SGD Diffusion:
Step 1: Under Assumption 3] we may only consider the second order Taylor approximation of the density function around critical points.
P(0 Va)
(44)
- P(O)dV
(45)
Joev.
-Jev P(a) exp
L(D) - L(a)
dV
(46)
Ta
1(00 a) Ha a) + O(A3))
=P(a) exp
d0
(47)
LEV.
Ta
= =P(a) (2TTT))
(48)
H
Step 2:
+ - DVP((8)
J
(49)
D
DL 1
J -P()) VI(())
VD
VI(0)
(50)
T
T
15

---

Published as a conference paper at ICLR 2021
According to Equation 7 V (+) is ignorable near the minimum and the col b, thus
[ ( VL.
VD
(51)
Apply this result to the Fokker-Plann Equation we have
((D(0) ()
(52)
((- -1) vI11) P(O.t)
=V DVP(0,8) V.
(53)
And thus obtain the Smoluchowski equation and new form of
OP(),t)
D
VL(O)
P(O.0)
= -
(54)
Øt.
T
-L(O) T
L( T
J = D exp
V
exp
P(O)
(55)
We note that the Smoluchowski equation true only near critical points. We assume the point is the midpoint the most possible path between and b, where T(s) = (1 - s) + sT.(b. The temperature Ta dominates the path + 8, while temperature Tμ dominates the path b. So we
have
L(0)
P(0) [[0))L(s)
L(s) T
L(()) L(s)
exp
JD- exp
(56)
Under Assumption 2 we integrate the equation from Valley a to the outside Valley a along the most possible escape path
L(0) ((0)-L(s) L(s)
Left =
exp
P(0))d8
(57)
00
T
0
L(0) L(s)
exp
P(O) do
(58)
00
To
0
[(()) L(s)
+
exp
P(O) d0
(59)
00
Tb
((a) - L(s))
=!P(s) exp
P(a)] + -
(60)
Ta
L(a)) L(s)
exp
P(a)
(61)
Ta
Right = J 1( D- exp
[(() L(s)
db
(62)
T
We move J to the outside of integral based on Gauss's Divergence Theorem, because is fixed on the escape path from one minimum another. As there is field source on the escape path, fy J(OdVV = and V (()) = O. Obviously, only minima are probability sources in deep learning. So we obtain
exp
L(a)-L(s) T.
P(a)
(63)
D exp
((0)
L(s)
d8
16

---

Published as a conference paper at ICLR 2021
Under Assumption
we have
L(0) L(s)
D exp
d0
(64)
T
c
L(b) - L(8)
+ + - b) Hb - b)
D exp
d0
(65)
Tb
1.0
L(b) L(s) + 20 b) T Ho - b)
R D=
exp
d0
(66)
Tb
L(b) L(b)
2nTb
=D exp
(67)
Tb
[Hb
Based on the results of Step I and Step 2, we have
Ss. J JdS
J
7 P(e E V.) P( Vo)
(68)
P(a) exp
L(a)
Ta
1
(69)
D5' exp
l(b) ((b)-((s)
V
2nT [Ho] P(a) /
2n
Th
Hn
TTH Hb
L(8) I(a) I.(b) I(())
exp
(70)
2T 2T
To
To
VTHHa Hb
SAL (1- 8)AL
exp
(71)
2T. 2T
Ta
Tb
So we have
Ta
SAL
(1 - A)
5 = 2n V
exp
(72)
HHH
Ta
To
In the case of pure SGN, Ta = " Ha and
-
Hy gives
2B
2B
1
2BAL
S
(1 (1-s)
2
exp
(73)
7 Hol
"
H.
Ho
We generalize the proof above into the high- ligh-dimensional SGD diffusion.
Step
P(0 E Va)
(74)
=I P(O)dV
=
(75)
JOV.
=P(a) I exp
1 (0 a) TD, H.DD 2 x0- -0) dv
(76)
BEV.
2
(2T) 2
=P(a) det D= Ha)
(77)
Step 2: Based on the formula of the one-dimensional probability current and flux we obtain the high-dimensional flux escaping through Col b:
/
J.
(78)
9b
_ b) TD HHD t1 b) ds
1
=Jid
exp
(79)
Sb
(2TT) m
=Jid
(80)
(Ilige
(Drr Hn:))
17

---

Published as a conference paper at ICLR 2021
where []] indicates the directions perpendicular to the escape direction So we have
1
del(H,DD")
8 SAL
(1 (1-s)AL
7 2x
Heel exp
(81)
Ta
Тb
Ta and To are the eigenvalues H and H corresponding to the escape direction.
We know Da 2 Ha and D3 2n [Hb]+ As D must be positive semidefinite, we place Ho Ug Un Aaag(Hoi, .. Ho(n-1 11, (Hbeeeeeeeee Thus, we have
H1(n-1), Hoe) by its positive semidefinite analog [Ho]*
2BAL
(8
+ (1-8) )
T
2T
exp
(82)
Hbe
7
Hae
|Hbel
A.3 PROOF OF PROPOSITION
Proof. A stationary distribution must have balanced probability flux between valleys. So the probability flux of each valley must be equivalent,
P(0 V1) P(0 E V2)
(83)
As = it leads to P(0 E Vo) x Tu. We normalize the total probability to 1, then we obtain the result.
B ASSUMPTIONS
Assumption indicates that the dynamical system is in equilibrium minima but necessarily near saddle points. means that 2P(0.t)
Øt - J(,, 1) holds near minima 0j and 02, but not necessarily holds near saddle point b. Quasi-Equilibrium Assumption is actually weaker but more useful than the conventional stationary assumption for deep learning (Weliing & Teh, 2011] Mandt al., (017). Under Assumption 2 the probability density P can behave like a stationary distribution only inside valleys, but density transportation through saddle points can busy. more like: stable lakes (loss valleys) is connected by rapid Rivers (escape paths). In contrast, the stationary assumption requires strictly zero flux between lakes (loss valleys). Little knowledge about density motion can be obtained under the stationary assumption.
Low Temperature Assumption is common (Van Kampen 1992. Zhou 2010 Berglund 2013 Jas
trzębski al. 2017), and is always justified when // is small. Under Assumption 3 the probability densities will concentrate around minima and MPPs. Numerically, the 6-sigma rule may often provide good approximation for Gaussian distribution. Assumption 3 will make the second order Taylor approximation, Assumption I even more reasonable in SGD diffusion.
Here, we try provide more intuitive explanation about Low Temperature Assumption in the domain of deep learning. Without loss of generality, we discuss it in one one-dimensional dynamics. The temperature can be interpreted as real number D. In SGD, we have the temperature as = 2/ H. In statistical physics, AL is large, then we call Low Temperature Approximation. Note that AL
D D' appears insides an exponential function in the theoretical analysis. People usually believe that, numerically, AL can make good approximation, for similar reason of the 6-sigma rule in D statistics. In the final training phase of deep networks, a common setting is r7 0.01 and B = 128. Thus, may safely apply Assumption to the loss valleys which satisfy the very mild condition AL > 2.3 x 10-4, Empirically, the condition AL HT
π 2.3 x 10-4 holds well in SGD dynamics. It also suggests that, we can adjust the learning rate let SGD search among loss valleys with certain barrier heights.
C THE STOCHASTIC GRADIENT NOISE ANALYSIS
Figure SouureJeemoon demonstrates that the SGN also approximately Gaussian on a randomly initialized ResNet
with B 50 CIFAR-10. We also note that the SGN on ResNet seems less Gaussian than SGN on
18

---

Published as a conference paper at ICLR 2021
30
304
167
201
307
302
101
(a) Gradient Noise of one minihatch across parameters
(h) Lévy noise
10a
Demai
(c) Gradient Noise of one parameter across minibatches
(d) Gaussian noise
Figure 7: The Gradient Noise Analysis. The histogram of the norm of the gradient noises computed with ResNet18 (He et al.) 2016) on CIFAR-10 (Krizhevsky et al. 2009).
0.92
0.02
0.02
0.01
Car Buti berilitte CH80
Mose
00.02
-0.02
-0.03
-0.01
Figure 8: The plot the SGN covariance and the Hessian by training fully fully-connected network on MNIST. We display all elements H(,,) [-0.03, 0.03] of the Hessian matrix and the corresponding elements in gradient noise covariance matrix in the original coordinates.
19

---

Published as a conference paper at ICLR 2021
Rater Calee bratecte Pertor
0.4
Hake goal
0.3
0.3
0.2
0.2
0.2
0.1
0.0
0.0
0.0
0.1
0.2
0.3
0.4
0.5
0.0
0.1
0.2
0.5
0.4
0.5
Hissoon
Hessson
Figure 9: The plot of the SGN covariance and the Hessian by training fully-connected network on Avila. We display all elements ((,)) E [le 4, 0.5] of the Hessian matrix and the corresponding elements in gradient noise covariance matrix in the space spanned by the eigenvectors of Hessians.
fully-comnected networks with the same batch size. Panigrahi et al. (2019) presented more results the Gaussianity SGN under various conditions.
By Figure 8 we validate C = π in the original coordinates on MNIST. By Figure 9 we also validate C H on another dataset, Avila, in the space spanned by the eigenvectors of Hessian. The relation
π can still observed these two cases.
Data Precessing: We perform the usual per-pixel zero-mean and unit-variance normalization MNIST. We leave the preprocessing of Avila in D Model: Fully-connected networks.
D MAIN EXPERIMENTS
Figure 10 and T2 respectively validate that the exponential relation of the escape rate with the Hessian, the batch size and the learning rate.
D.1 EXPERIMENTAL SETTINGS
Datasets: a) Avila, b) Banknote Authentication, c) Cardiotocography, d) Dataset for Sensorless Drive Diagnosis.
We perform per-pixel zero-mean and unit-variance normalization on input data. For simplicity, also transform multi-class problems into binary-class problems by grouping labels, although this is unnecessary.
Data Precessing:
Model: Two-layer fully-connected networks with one hidden layer and 10 neurons per hidden layer.
Initializations: To ensure the initialized models are near minima, we first pretrain models with 200-1000 epochs fit each data as well as possible. We set the pretrained models' parameters as the initialized 0z=0-
Valleys' Boundary: In principle, any small neighborhood around Oz=o can regarded as the inside of the start valleys. In our experiments, we set each dimension's 's distance from 6:= should be less than 0.05, namely | < 0.05 for each dimension i. If we rescale the landscape by factor k, the neighborhood will also be rescaled by k. Although we don't know which loss valleys exist inside the neighborhood, we know the landscape of the neighborhood invariant in each simulation.
Hyperparameters: In Figure 10
(a) 7 = 0.001, = (b) 0.015, B = 1, (c) 0.005, B
(d) 17 = 0.0005, B 1. In Figure
II (a) 17 = 0.02, (b) In Figure 13 (a) 17 0.0002, B = 100,
0.6, (c) = 0.18, (d) = 0.01. In
Figure 12 (a) B 1, (b) B 1, =
(b) = 0.001, B 100, (c)
100, -
100. Figure 14 (a)
100, 0.0005, 100, 0.000,, (b) 0.00,
7= 0.0002,
0.0001, (c) 17 0.0002, B
100, = We note that the hyperparameters need
be tuned for each initialized pretrained models, due the stochastic property of deep learning.
20

---

Published as a conference paper at ICLR 2021
interol
Confidence interval
(a) Avila
(b) Banknote
Pearson Correlation: 9856 95% Confisence interval
Pearson Correlation 8901
95% Confidence interval
(c) Cardiotncography
(d) Diagnosis
Figure 10: The escape rate exponentially depends on the "path Hessians" in the dynamics of SGD. -log(7) linear with 1. to the escape directions.
z. The "path Hessians" indicates the eigenvalues of Hessians corresponding
21

---

Published as a conference paper at ICLR 2021
interol
interval
(a) Avila
(b) Banknote
Pearson Corre atfon-O 9585 95% Confiderce ce intervl
Pearson Cerre anton 0,9778
95% Confidance intervol
(c) Cardiotocography
(d) Diagnosis
Figure 11: The escape exponentially depends the batch size in the dynamics of SGD. -og(7)) linear with B.
22

---

Published as a conference paper at ICLR 2021
Pcarson Corre atlan 90% Confidance interval
Poarson Cornelatin2.975
95% Contiderce interval
(a) Avila
(b) Banknote
Corniaanan
(c) Cardiotocography
(d) Diagnosis
Figure 12: The escape rate exponentially depends on the learning rate in the dynamics of SGD.
- -log(7) is linear with 1 The estimated escape rate has incorporated as the time unit.
23

---

Published as a conference paper at ICLR 2021
Pearson Corre arlon 9913 95% Confidirce intenvl
Pearson Correlacion 9839
95% Confidince intervol
(a) Avila
(b) Banknote
Confidence interval
Interval
(c) Cardiotocography
(d) Diagnosis
The relation of the escape rate and the isotropic diffusion coefficient D. The escape formula that log(?) is linear with is validated.
Figure 13:
According our experience, can always find the hyperparameters discover the quantitative relations as long as the pretrained model fits the data set well enough. The fined-tuned requirement be avoided in Section B because the models in Section are artificially initialized.
Observation: we observe the number of iterations from the initialized position to the terminated position. We repeat experiments 100 times to estimate the escape rate y and the mean escape time As the escape time is random variable obeying an exponential distribution, t ~ Exponential(?). the estimated escape rate can be written as
100
(84)
100 t
The 95% confidence interval of this estimator is
1.96 V100 < <
1.96
5(1
(1
+
(85)
V100
D.2 EXPERIMENTS ON SGLD
Experimental Results:
Figure 13 shows highly precise exponential relation of the escape rate and the diffusion coefficient in the figure. Figure 14 shows a proportional relation of the escape rate and the Hessian determinant in the figure. Overall, the empirical results support the density diffusion theory in the dynamics of white noise. experiments on SGLD, we carefully adjust the injected gradient noise scale in experiment ensure that D is significantly smaller than the loss barrier' height and large enough to dominate SGN scale. If D is too large, learning dynamics will be reduced to Free Brownian Motion.
24

---

Published as a conference paper at ICLR 2021
Pearson Corre 2,00 Confidence
Pearson O 9588 Confidence
(a) Avila
(b) Banknote
Pearson Corre atlono 5993
Pearson Correiaionne 5993
95% Confidence ce interval
55% Cerfidance interval
38
(c) Cardiotocography
(d) Diagnosis
Figure 14: The relation of the escape rate and the Hessian determinant in the dynamics of white noise. The escape formula that y linear with & is validated.
25

---

Published as a conference paper at ICLR 2021
E EXPERIMENTS ON MORE MODELS
We supply experiments of training three models on artificial Gaussian datasets. In these experiments, can analytically know the locations of the minima, Hessians and loss barriers, as each input feature is Gaussian noise.
E. EXPERIMENTS SETTINGS
Data Set: We generate 50000 Gaussian samples and random two-class labels as the training data set, ((0() (0) )x)) NO, I), ( {0, 1 {1, ,50000}}:
Hyperparameters: In Figure T5
(a) 1 0.0001, B - 100. (b) y 0.001, 100, (c)
0.0003, B 100. In Figure 16
(a) 17 0.0001, B 50. D 0.2, (z 0.001, =0,
0.0005, (c) 1 0.0003, B = 1, = 0.0003. In Figure 17 (a) = 0.006, B = 50, (b)
0.05, B 50, (c) 7
0.005, 0.005, B, In Figure 18 (a) 7j 0.006, (b) g= 0.06, (c) 0.1. In
Figure 19: (a) B 1, (b) B = 1, B = We note that the hyperparameters are recommended
and needn't t be fine tuned again. The artificially initialized parameters avoids the stochastic property of the initial states.
Experiment Setting Styblinski- Tang Function is commonly used function in nonconvex opti- mization, written
((0)
Σ 00 160 50.).
We use high-dimensional Styblinski-Tang Function as the test function, and Gaussian samples as training data.
L(0) f(O z)).
where data samples & ~ WO 1). The one-dimensional Styblinski-Tang Function has one global minimum located at -2.903534, one local minimum located d, and one saddle point b 0.156731 as the boundary separating Valley a₁ and Valley ag. For a n-dimensional Styblinski- Tang Function, we initialize parameters ot=0- vk 1-2.903534, ..... -2.903544, and set the valley's
boundary 0: < vx 0.16631, where is the dimension index. We record the number of iterations required to escape from the valley to the outside of valley. The setting 1 does not need labels.
Experiment Setting 2: We study the learning dynamics of Logistic Regression, Parameters Initial- ization: 0=- (O...., 0). Valley Boundary: -0.1 < 0; < 0.1. Due the randomness of training data and the symmetry of dimension, the origin must be minimum and there are lot unknown valleys neighboring the origin valley. And we can set an arbitrary boundary surrounding the origin valley group, and study the mean escape time from the group of valleys.
Experiment Setting 3: We study the learning dynamics MLP with ReLu activations, cross entropy losses, depth as 3, and hidden layers' width as 10. Parameters Initialization: 0,=0 (0.1, ................. 0.1) with a small Gaussian noise e = (0, 0.01I). Valley Boundary: 0.05 < 0, < 0.15. To prevent the gradient disappearance problem of deep learning, symmetry breaking of deep learning, we add a small Gaussian noise to each parameter's initial value. Due to the complex loss landscape of deep networks, we hardly know the exact information about valleys and cols. However, the escape formula can still approximately hold even if an arbitrary boundary surrounding an arbitrary group of valleys. We set the batch size as I in this setting. When the batch size is small, the gradient noise is more like a heavy-tailed noise. We can validate whether or not the propositions can hold with very-small-baas gradient noise in practice.
move the starting point from the origin. For
E.2 EXPERIMENTS RESULTS
Figure 15 shows the relation of the escape rate and the isotropic diffusion coefficient D. Figure 16 shows the relation of the escape rate and the Hessian determinant in the dynamics of white noise. Figure 17 shows the relation of the escape rate and the second order directional derivative in the dynamics of SGD. Figure [8] shows the relation of the escape rate and the batch size in the dynamics of SGD. Figure 19 shows the relation of the escape rate and the learning rate in the dynamics of SGD.
26

---

Published as a conference paper at ICLR 2021
Custissn strad
(a) Styblinski-Tang Function
(b) Logistic Regression
(c)
Figure 15: The relation of the escape rate and the diffusion coefficient D in the dynamics of SGLD. The escape formula that - log(7) is linear with is validated in the setting of Styblinski-Tang, Function, Logistic Regression and MLP.
Germittion:1 2046 53% Contidence interal
Feunsn 6.0947 55% Conficeroe Ianra
Peaman 5903
95% Castiende rieval
(a) Styblinski-Tang Function
(b) Logistic Regression
(c) MLP
Figure 16: The relation of the escape rate and the Hessian determinants in the dynamics of SGLD. The escape formula that y is linear with & is validated in the setting of Styblinski -ang Function, Logistic Regression and MLP.
Pearics Combitor3.550 3363
Peaser Ca 3975
Porsoon Cww.eateee 5902
(a) Styblinski-Taal Tang Function
(b) Logistic Regression
(c) MLP
Figure 17:
The escape rate exponentially depends on the sharpness in the dynamics of SGD. The escape formula that log(>) is linear with & is validated in the setting of Styblinski-Tan Function, Logistic Regression and MLP.
27

---

Published as a conference paper at ICLR 2021
Pousen Domristoond 99% Cosfiannc vieve
Peaner 21900.397 55% Corter Eitonaa
Porsan Dorre 5ens 99% Carslacee steve
(a) Styblinski-Tang Function
(b) Logistic Regression
(c) MLP
Figure 18: The escape rate exponentially depends the batch size in the dynamics of SGD. The escape formula that log(>) linear with validated in the setting Styblinski-Tang Function, Logistic Regression and MLP.
Praron Carvartrnd
Pesiter stan
Proroon Carre aww.ot
(a) Styblinski-Tann Tang Function
(b) Logistic Regression
(c) MLP
Figure 19: The escape rate exponentially depends on the learning rate in the dynamics of SGD. The escape formula that log(>) is linear with is validated in the setting of Styblinski-Tane Function, Logistic Regression and MLP.
28


Reviews:
[{"review_id": "pQ-FamlsN5", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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": "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. \nIn 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. \n\nThis approach has already been analysed in the literature and the authors give a good introduction to previous works. \n\nThe 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.\n\n**Points that needs to be clarified :**\n\nThe 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. \n\nIt 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. \n\n**Additional comments :**\n\nIn 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.\n\nThe 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.\n\nIn 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.\n\nTypo after : \"The mean escape time analysis of SGLD\"\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "oNKioZnB7NX", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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": "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. \n\nQuestions, comments and ideas:\n- 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). \n- 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. \n- What are the implications of Assumption 1? How does it depend on the network architecture?\n- 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? \n- The numerical results are for a two-layer network? What happens if we were to increase depth or width? \n- 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?\n- 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. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "mpJCvpL2QgG", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "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. \n\n\n1. 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? \n\n\n2. 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.\n\n\n3. 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.\n\nThe 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). \n\nI read the authors' feedback and appreciate the clarifications. I keep my score. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "gD63KPyyEuY", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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 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.\n\nThis 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.\n\nSome shortcomings are listed as follows:\n\nFirst, the concept “valley” is frequently used in this paper, but it seems that no formal definition has been given for “valley”.\n\nSecond, 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. \n\n----------------------\nAfter rebuttal:\nI thank the authors'  clarification. I keep my rating.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

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)