Quasi-potential theory for escape problem: Quantitative sharpness effect on SGD's escape from local minima
Authors: Hikaru Ibayashi
Masaaki Imaizumi
Venue: ICLR 2022 Submitted (2022)
Keywords: deep learning
learning dynamics
SGD
flat minima

Abstract: We develop a quantitative theory on the escape problem of stochastic gradient descent (SGD) and investigate the effect of the sharpness of loss surfaces on escape. Deep learning has achieved tremendous success in various domains, however, it has opened up theoretical problems. For instance, it is still an ongoing question as to why an SGD can find solutions that generalize well over non-convex loss surfaces. An approach to explain this phenomenon is the escape problem, which investigates how efficiently the SGD escapes from local minima. In this paper, we develop a novel theoretical framework for the escape problem using ``quasi-potential," the notion defined in a fundamental theory of stochastic dynamical systems. We show that quasi-potential theory can handle the geometric property of loss surfaces and a covariance structure of gradient noise in a unified manner through an eigenvalue argument, while previous research studied them separately. Our theoretical results imply that sharpness contributes to slowing down escape, but the SGD’s noise structure cancels the effect, which ends up exponentially accelerating its escape. We also conduct experiments to empirically validate our theory using neural networks trained with real data.

Under review as a conference paper at ICLR 2022
QUASI-POTENTIAL THEORY FOR ESCAPE PROBLEM: QUANTITATIVE SHARPNESS EFFECT ON SGD's ES- CAPE FROM LOCAL MINIMA
Anonymous authors Paper under double-blind review
ABSTRACT
We develop quantitative theory on escape problem of stochastic gradient descent (SGD) algorithm and investigate the effect of sharpness of loss surfaces the escape. Deep learning has achieved tremendous success in various domains, however, it has opened up various theoretical open questions. One of the typical questions is why an SGD can find parameters that generalize well over non-convex loss surfaces. An escape problem is an approach to answer this question, which investigates how efficiently an SGD escapes from local minima. In this paper, we introduce quasi- muasi-potential from traditional large deviation theory to the escape problem. Our novel formulation can quantify escaping effect without relying on auxiliary variables and is applicable to including discrete setup. Our theory find that (i) sharpness of a minimum exponentially slows down the escaping. (ii) but the SGD's noise cancels the effect, which leads to exponentially fast escape from sharp minima, as suggested by (Xie et all 202().. We also conduct experiments to empirically validate theory using neural networks trained with real data.
INTRODUCTION
In recent years, the successes of deep learning have been major driving force of machine learn- ing development (LeCun, 2019). Owing to its strong generalization capability, deep learning has diverged into a wide range of domains, such as computer vision (KKizhevsky et al,, 2012),, speech recognition (Mikaloy el all 201I), and natural language processing (Collobert et all, (01)), The high performance of deep learning is underpinned by gradient-based learning algorithms, including stochastic gradient descent (SGD) and its variations (Kingma & Ba, 2014; Schmidt et an, 2021).
However, at the same time, those unprecedented successes raise question:
Why does SGD learn parameters of neural networks with high generalization performance?
Although the optimization problems of neural networks were thought to be difficult to solve (Blum & Rivest, 1192), SGD find nearly optimal solutions empirically, and further, the obtained solutions generalize well (Keskar et all 2016, Brutzkus et all, 2017). Analyzing SGD's role on deep learning an area of research that currently attracting strong interest (Masters & Luschi, 20T; lastrzehski
atal ()2T))
One of the promising directions for this question is study the geometric properties of training loss landscape. Many empirical studies have found that minima obtained by SGD have distinctive geometric properties. Keskar all (2016) have shown that the shape of the minima obtained by SGD tends to be flat. He et all (20196) have deepened the investigation by picturing that SGD settles on the flatter side of asymmetric loss surface, which they named "asymmetric valley." Draxler et (201)) and Garipov et al. (201) have shown that separate minima obtained by independent training processes are internally connected through pathways. Li all (201 have proposed a dimension reduction technique to visualize the geometry of loss surfaces, visually confirming flat minima. Most significantly, Jiang et al. (2019) conducted large-scale experiments and verified that minima in flat and wide regions have the strongest correlations with generalization capabilities. To attain a theoretical understanding of SGD, it is key to quantitatively analyze the connection between SGD and the geometric properties of loss surfaces.

---

Under review as a conference paper at ICLR 2022
PT
Loss Surface: L(0)
V
Steep Trajectory 4p
4.0
Less Steep Trajectory
200
Figure 1: Visual illustration of steepness (Definition B) The steepness of Sur(p) is greater than (1b) because yp moves against the vector field of gradient (().
An escape problem is scheme to analyze the dynamic of SGD escaping from local minima (Zi CLall 201%; Jastrzebski et all 2017: Hn all 2012 Nguyen et al, 201% Xie el all 2020) This scheme allows to investigate why SGD avoids (potentially) bad local minima and settles good minima. Zhu et al (2M1) first investigated the SGD's escape phenomenon and showed that SGD's escape is enhanced by its unique noise structure, called the "anisotropic noise structure." Invoked by their analysis, many studies have been attempting to theoretically quantify this phenomenon. Fm et all (2019) rigorously identified the role of learning rate in escaping. Nguyen al] (201%) used the Levy process to provide the precise description of SGD as well as its escaping phenomena. lass trzebski all (20IL) developed theory of stochastic differential equation and quantified how the anisotropic noise affects its fast escape from sharp minima. XXie et all (2022) refined the mathemati- cal aspect and showed that the SGD's noise structure exponentially enhances escaping under a setup of diffusion theory.
In this paper, we introduce a quasi-potential theory to the escape problem, and investigate a mean exit fime, which formally quantifies escaping. The notion of quasi-potential is defined in fundamen- tal theory of stochastic dynamical systems, named Large Deviation Theory (Ereidim Wentzell, 202; Dembo_& Zeitoui, 2010). Quasi-potential can formulate the distribution of trajectories that a stochastic dynamical system takes. To illustrate quasi quasi-potential for SGD's escaping problem, we introduce an intuitive notion, steepness of trajectory (Fig. M and Definition B), and show that is an effective tool to analyze the SGD's escaping. To the best of our knowledge, this is the first work that applies the quasi-potential to formalize the relationship between SGD's escape and sharpness.
Our main findings and contributions are as follows:
We develop novel quasi-potential theory that rigorously describes the escape of SGD with auxiliary variables. Our theory can concisely incorporate the effeet of essential factors, i.e., a batch size (B), a learning rate (7), and geometric parameters of loss surfaces (r and X)
Our theory be flexibly applied several practical setups: SGD with discrete update and state-dependent gradient noise, while those were sometimes omitted in previous works for mathematical convenience.
We find that a loss surface with sharp minima slows down the escape of SGD, which seems to contradict the common knowledge, i.e., SGD escapes efficiently from sharp minima. We show that result does contradict the common knowledge but is generalization of existing results, such as (Jastrzebskı et al], 2017) and ci 2121).
1.1 COMPARISON WITH EXISTING STUDIES ON ESCAPE PROBLEM
In Table II compare the escape time derived with the results of other studies that analyze the escape problem. There are two main points of focus. The first the time to escape that we derive. Our theory provides unified analysis of exit time incorporating all the essential parameters, batch
2

---

Under review as a conference paper at ICLR 2022
Parameter
Non- stationary
Discrete setup
Study
Time to escape
dependent noisc
al (2017)
& exp [n]
Jastrzebski
exp
2q
B AL
det H det
Ztu (2019)
N/A
V
Nguyen et all (2019)
(1+ O (1711))
X1e ct a (2122
2x A
exp
2 ($ + |xm
V
Ours (continuous SGD)
exp _2
V
Ours (discrete SGD)
exp 2 2 + +0 (V
V
Table 1: Comparison of the studies on the escape problem. B is batch size, 1) is a learning rate, is a radius of the region around a minimum,
is a Hesse matrix of loss functions and X = Amin (H). Further, H'' is a Hesse matrix on one of the neighboring points of the mini- mum and X' is one of its eigenvalues of H' AL difference of training loss values within neighborhood of minimum, E (0, 2] is an index of heavy-tailedness of gradient noise in SGD, and E (0, and (0. 1) are values that implicitly include various factors of the escaping problem. "Non-stationary" denotes whether the result holds without assuming that SGD reaches stationary distribution before escaping. "Parameter dependent noise" denotes whether noise in SGD depends on current parameters. "Discrete setup" means whether the analysis is valid with discrete update by SGD. Our theory has two main advantages: (i) it explicitly quantifies essential factors of escape without relying auxiliary variables, such s, 8 and AL, and (ii) it is applicable to wide range of the settings. Finally, we note that although our results's ' dependency on À seems to be opposite to (Jastrzebski all, 201 7) and (Xie eX (02()) those are all consisitent because AL has an implicit dependency on and 2 under Assumption II.
minima,
size, learning rate, a radius the region around a minimum, and sharpness a minimum. As a consequence, show that the eigenvalues of the Hesse matrix increase the time to escape, which has not been found in other studies. Such effect was less apparent in previous studies such as (Jastrzebski al, 2017) and (Xie et all 202() because part of the sharpness dependency is hidden in AL. Provided that AL = 2 under Assumption MI one can see that our results are consistent with previous studies.
The second is our theory's s flexibility, Different from Jastrzębskı et al. (2017) and at (2022))
our theory does not require that SGD reaches the stationary distribution before escaping, which known to take exponentially many iterations (Xu et all 2017: Ragınsky et all, 2017). Additionally,
our theory can evaluate the correspondence with the practical SGD, which has a discrete update rule and state deatedde noise.
Notations: For k x l matrix A, (AA) is the j-th largest eigenvalue of A, and Xmax A1(A) and Amin(4) = Xe (A) denote the largest and the smallest eigenvalue of square matrix. O()) denotes Landau's 's Big-O notation. ||-|| denotes the Fuclidean norm. Given time-dependent function 0,, O denotes the differentiation of 9 with respect to t. N (H, E) denotes the multivariate Gaussian distribution with the mean μa, and the covariance E.
2 SETTING AND PROBLEM
2.1 STOCHASTIC GRADIENT DESCENT AND DYNAMICAL SYSTEM
Consider a learning model parameterized by 0 E Rdd Given training examples {x:NN and loss function r;), consider training loss [(0) = N ΣN ((0,x,) and mini-batch loss
3

---

Under review as a conference paper at ICLR 2022
== ((0, zz). where B is randomly sampled subset of the training data such that B =. We assume that L(0) is differentiable and its derivative (L( is Lipschitz continuous.
We mainly consider two types SGD: discrete SGD and continuous SGD. Although a discrete SGD is used in practice, study continuous SGD starting point of our analysis because of its mathematical convenience. This a widely used approach general SGD analyses (Ali et all
2019 Advani all 2020) well in the escaping analyses (Jastrzebski all 2017: Xie all
2020.
Discrete SGD: First, give the usual discrete formulation of SGD. Given initial parameter 80 E RR, SGD generates a sequence of parameters (0x KEN by the following update rule:
0c+1 02 1/ T. (0c),
for & E N, where 17 > 0 is a learning rate.
In particular, focus on SGD whose noise gradients has Gaussian distribution. We decompose V. (0x) in (I)) into a gradient term - LVL(0z) and a noise term VI.(0x) (0x): and consider that the noise is Gaussian. With this setting, the update rule in (II) is rewritten
B = 02 v)()( + VB Wk.
(2)
where W₂ N (0,,)()))) is parameter-depeeneett Gaussian noise with its covariance C(0) E3-UUi((1......)) [(VI(0)- Ve (e((,=))) (0,x.)) We assume that C(0) is Lipschitz
continuous.
The Gaussianity of the noise gradients is justified by the following reasons: (i) if the batch size B is sufficiently large, the central limit theorem ensures the noise term becomes Gaussian noise, and (ii) several empirical studies show that the noise term becomes Gaussian noise (Mandt 2016 Jastrzebski et al, 2017: He el all 2019a), although different findings have been obtained other
settings (Simsckli
2019)
Continuous SGD: We also give a continuous SGD, which is exactly discretized to (2) by a classic Euler scheme (Definition 5.1.1 of Gobel (2016)). With time index t Z 0 and the given initial parameter Bu E Rd, the continuous dynamic of SGD is written as follows:
0 - ---V((0))) + V V
where w. d-dimensional Wiener process, i.e. an R. stochastic process with / such that we 0 and Wr+u - We N (0, u/) for any 1, u >> 0. We note this system can be seen as a Gaussian perturbed dynamical system with a noise magnitude / because v7 and do not evolve by time.
2.2 ESCAPE PROBLEM AND MEAN EXIT TIME
We consider the problem how SGD escapes from minima of loss surfaces. In this paper, target of interest quantified by a notion of mean exil time for continuous SGD and discrete mean exit time of discrete SGD. Let 0 E Rdd be local minimum of loss surfaces, and D C Rd be r-neighborhood of l with > O. We define the mean exit time as follows:
Definition 1 (Mean exit time from D). Consider continuous SGD starting from Oo E D. Then,
mean exit time of the continuous SGD (G) from D is defined as
B/r] == E[min {t O, & DH}- Definition 2 (Discrete mean exit time from D). Consider discrete SGD starting from Og E D. Then, a discrete mean exit time of the discrete SGD (Z) from D is defined as
Elv] == E E'min {kn 0g $ DW}.
These definitions common in quasi-potential theory (Freddin & Wentzell, 2012: Gobel 2016).
Intuitively, the smaller [E[r] or [[p] becomes, the faster the system escapes from a region D. In other words, the system has stronger tendency escape from d".
We remark that there are other formulations to analyze the escape problem. Zhu (0099 define escaping efficiency Eg, (0,) - L (fu)). Jastrzębskı et all (2017) and Xie et all (2(20) study ratio between the probability of coming out from 8* neighborhood and the probability mass around 0"
4

---

Under review as a conference paper at ICLR 2022
2.3 BASIC ASSUMPTIONS FOR THE ESCAPE PROBLEM
We provide basic assumptions for the escape problem, commonly used in the literature (Mandt el all 2016 Zhu et all 2019; Dastrzebski all 2017, Xie etll, 2020).
Assumption (L(O) is locally quadratic), There exists a matrix H E Rddd such that for any 8 E D, the following equality holds:
AA E
D, L(0) = L (0") + VL (0 8*) (0 8*) H ( (0)
2
Assumption (Hesse covariance matrix), For any 0 E D, C(0) is approximately equal to H
It is known that Assumption 2 holds around critical point 0 (Zuu et al 201: Dastrzebskı et all 2017). is also empirically shown that Assumption 0 can approximately hold even for randomly chosen & (see Section of Xie all (2020). We further investigate variant of Assumption @ in Section [
QUASI-POTENTIAL THEORY
We introduce the basic notions of the quasi-potente theory. We start with defining notion of steepness of trajectory followed by the systems (G)) on a loss surface L(0). Let = {&Pt jejo,r) be a trajectory over finite time interval [o, 77. Or more formally, &p is a continuous map from [0, 7] Rd, and is element of Cor (IR4) which is support of a dynamical process in [0, Tj. Given trajectory and the system (E), we define the following quantity:
Definition (Steepness). Steepness of a trajectory vp followed by (G) is defined
Ser(p) = 21
1 (+: + (L()))) (vp)) V (+t + (L()))) dt.
Steepness (yp( can be intuitively interpreted as the hardness of climbing that the system (C) is exposed to while following the trajectory ip I(()) (Fig. M.. This notion is generally utilized in the field of dynamical systems, for example, and is called "normalized action functional" in Section 3.2
of Freidlin & Wentzell (2012) and "rate function" in Section 1.2 of Dembo & Zeitount (201T)..
Steepness is useful to describe a distribution of trajectories generated by dynamical systems. If tra- jectory to has a large steepness Sor(p), the probability that the dynamic system takes the trajectory decreases exponentially. Formally, the distribution is analyzed as follows.
Lemma 1 (Theorem 3.1 in Section 3.3 Breidlin & Wentzell (2012)). For any 8,5 > 0, Car (Rd), and sufficiently small & > O, the following holds:
Per (1p' (R p ( (v/,)) < 0) 2 exp {- [Sor (v) +1]
where p((p' supte(oorn 11 sell-
Lemma 2 (Theorem 3.1 in Section 3.3
Freidmm & Wentzell ( Let (bs)
{yp E Cor (Rd) Sur s $). For any 5, ç, > 0 and sufficiently small O, we have:
Po P (RT p(l' (s)) 2 o) s expl-e (a(l-=--(s000 {)},
where p(y', (s)) in( (
Although we restrict our attention to the system (G), the same discussion is applicable to a general class of diffusion processes and dynamical systems with Markov perturbations (For details, section 5.7 in Dembo & Zeitouni (2010) or Section 6.5 in Freidlin & Wentzell (2012)).
Although there several trajectories from 0* 0 D with different steepness, dominating factor for mean exit time is the smallest steepness among them, which called quasi-potential:
Definition 4 (Quasi-pone potential. Quasi-potential of 0 D is defined
V(Ø) := inf inf 7>0 (p Sur()).
Similar to steepness, quasi-potential can be seen as the minimum effort the system (L) needs to climb from 0t up on (0). (For more details, see Section 5.3 of [Feidlin & Wentzell (2012).
5

---

Under review as a conference paper at ICLR 2022
4
MEAN EXIT TIME ANALYSIS FOR SGD
4.1 ASSUMPTIONS
To analyze the mean exit time, the quasi-potential theory requires several assumptions regarding the stability of the system (L)) at 0".
Assumption (0" is asymptotically stable). For any neighborhood that contains 9", there exists small neighborhood V of 0 such that gradient flow flow with any initial value 0o V does not leave for t 2 and lim 0g = 0"
Assumption (D is attracted 0*). V0g E D, gradient flow with initial value O, converges to without leaving D as t oC.
where "gradient flow" means continuous gradient descent defined as 02 = VL
Stability is commonly used notion dynamical systems (Huetal 2017: Wi et 2017), although it does not always appear in SGD's 's escaping analysis (Zhu et all 2019: Jastrzebski et all 2017
Xie al. (020)- Assumption
known to be equivalent to the local minimality of 0 under
the condition that I.(0) is real analytic around 0* (Absil & Kurdyka, 2006). Also, by definition of asymptotic stability in Assumption E. we can always find a region that satisfies Assumption g The more detailed properties of stability can be found, such as in Section 6.5 of [eschl (2000). Assumption and are necessary to obtain the result (5)) in the following section.
Also, we require the following assumption boundary condition of Theorem ! Assumption 5. L(0*) = 0
Assumption is only for simplifying our proofs without changing the essence of our problem.
Finally, we assume the following,
Assumption 6. For a potential field W(0): IRd + R,
( - VL VWW ( =
VW(
has unique solution.
4.2 MAIN RESULTS
In preparation, start with traditional theorem in large deviation theory.
We analyze the mean escape time of SGD under the above assumptions. In preparation, we state two facts. First, shown Hu et all (2019) Theorem 3.4, (()) is calculated as solution of the following Hamilton-Jacohi equation,
(V) (L) VV(0) = 0.
(4)
Second, " is sufficiently small, the mean exit time can be expressed using V(0) as B
B Vi
E [r] = exp
(5)
where Vo := min V(O). Although these facts have been investigated in the literature (for example, see Section 4.4 in Freidlin & Wentzell (2012)), we give our own theorems and proofs in Appendix [ and for completeness.
The followings are our main results. We start with the mean exit time of Continuous SGD. Let E[rscD] be the mean exit time the continuous SGD, and let E [ the mean exit time of an isotropic continuous SGD whose C(0) is set to I.
Theorem 1 (Continuous SGD). Suppose that Assumption 7
h and 0 hold. Then, for
sufficiently small Z
exx E[T = exp
B 2 2>
{}
E|Tsop] = exp 12_

---

Under review as a conference paper at ICLR 2022
This result gives exact expression for the expected escape time with the explicit values of SGD. The results also have two implications. First, these result both of those results show that the mean escape time exponentially increases in the smallest eigen value of H", i... A. This implies that sharper minima generally slow down the escaping, which is seemingly opposite to the implication of the existing literature (Jastrzebski a 2017; Xie et all, 2020). But in fact this is consistent with the existing literature because some of the sharpness factor is implicitly included in other variables such as AL. Second, our result endorses the fact that SGD's anisotropic noise exponentially accelerates the escaping (Xie et all, 2020), because the result shows that the mean exit time of SGD is smaller than that of isotropic SGD by exp [A+].
Our theory can be extended to the discrete case. By [[JUSGD], we denote the discrete mean exit time of the discrete SGD, and by B[V we denote the one of an isotropic version of the discrete SGD, i.e. with C(0) being L. The escaping problem of a discrete SGD, the discrete mean exit time, is formulated as special case of Gober & Menozzi (20T0). By substituting g(-) = 0, f() 1, and kc.) = 0 in Theorem 17 Gobet & Menozzi (20T)) we can obtain the following simplified statement.
max MMSSCD) - [ [[[UsD]] - [[[TSDD]] O(vT).
which immediately prove the following theorem:
Theorem (Discrete SGD). Given, Assumption
and E for sufficiently small B.
[2
B r2 + (V(T)) 17
B 22 +0 E psGD] exp [
E| P = exp
This result suggests that the discrete error does not majorly affect the escape. We note this is the first study that confirms the validity of using continuous SGD model (L) for escape analysis.
4.3 PROOF FOR THEOREM
We describe a proof of Theorem B We begin with the isotropic case and then investigate the non- isotropic case.
Isotropic case E[TSoSGD]: We substitute I to C(0). By the Jacobi equation (8) which is formally given by Theorem H in Appendix Al we have the following form for f D:
(V(())VVV - VL (0) (V = 0. 2
(6)
Given V(0') 0 by definition of V(0), V(0)= 20( is the unique solution of (8) by Assumption 5 and A. Therefore, we have
VO min (L( = min 20 H = 2
=EAD
zEaD
The second equality follows Assumption M and 5 Combined with the fact (5), which is formally shown in Theorem B in Appendix H. we obtain the statement of Theorem M in the isotropic case.
Anisotropic case E|TsGD]: Similar to the isotropic case, the equation @+) (or Theorem ! gives
VV(0) ((0)) - (0) VV(0) = 0.
(V = 2C(0)- satisfies (0) and by Assumption II and Ø. written
can simply
2C(0) - H'0) = -22- 4
Given V((*) by definition of V(A),, V(0) = 0 H 2 is the unique solution of ( by Assump- tion E and f Then, we obtain
VU 2r Amin (11*
(8)
Combined with (,) or Theorem in Appendix Bl finish the proof of Theorem ||
n
7

---

Under review as a conference paper at ICLR 2022
5 FURTHER INVESTIGATION ON COVARIANCE MATRIX
We investigate a variation of Assumption on the covariance matrix. Although Assumption is commonly used (Jastrzebski all 2017; Xie atl 2020), relaxing this is important for a flexible modeling of SGD.
Assumption 7 (Variant of Assumption D) H=~1//2 is positive matrix and there exist constants
C1 C2 0o such that for D, C(0) H'G holds with a positive invertible matrix as 0 < (G) S Am) S C2.
Under this different setup, we obtain the following results.
Theorem 3. Suppose that Assumption N
R and / hold. Then, for sufficiently small B
2 2ー
TisoSGD
exp
exp
2
E [SGD]
S exp
2 _
V02
vo1
suggests that replacing Assumption by Assumption / does not affect the isotropic case, but has constant effect in the anisotropic case.
Proof for Theorem & The result of [[[SoSGD] is obtained in the same way as Theorem M For the proof of [TGGD]], the following lemmas are useful, whose proof's are provided in Appendix C
Lemma 3. For positive invertible matrices A and B, the following inequality holds,
( (A' (A''B-)) B-!) S AA ()mii (
Lemma 4, For invertible matrices A and B, the following inequality holds
Amin Amin(A (AB) 2 Amin (Ann(A)mmin) (A))min(1)
Similar to the proof of Theorem we obtain VV(0) = 2C(0) 2C(00 -V)) Then, VV simply written
VV(0) -
-C - -22
-(HH"))
The second equation follows Assumption II and E. and the fourth equation follows Assumption M
Given that V(0*) 0, obtain V(0) G H 3 for 0 E D. Then, rewrite Vo is
Vo 2r Amin (G 11
By Lemma B develop upper bound on Amin AminnG-Bo (G-1/2
(G-12211/2 <
Aunax G 1/2 )min Amin(HH 1/2) I 9 11/221/2 Similarly, Lemma 3 gives us the following lower bound Xuai (G-1/2 H21/2 Amin (G-1/2)A (2=1/2) c2 c-/1/ 11/2, We substitute the two inequalities
into the solution (H), then obtain the following form of Vo:
1
2r
< Vo < 2r
A
Combined with (6), or Theorem N in Appendix B. we finish the proof of Theorem 5
EXPERIMENT
We conduct an experiment to validate our result discrete setup (Theorem 2) using a neural net- work and real-world datasets. We multi-layer perception and the AVILA dataset (De Stefand atl 201I) to observe that the discrete mean exit time of SGD has exponential dependence on eigenvalue X, radius and ratio of the learning rate and the batch size n/B.
In order for our essential assumptions to hold, we use the mean square loss with l regularizer for (.))) (Assumption (I) and train the model with the gradient descent for sufficiently long time
8

---

Under review as a conference paper at ICLR 2022
mcan exit time
mcan exit time
mcan exit
2): sharpness
rudius
V vn/B: noise magnitude
Figure 2: Empirical validation of Theorem where the empirical mean exit time has exponential dependeney on sharpness a (~ A), radius r, and noise magnitude vn/B.
obtain Oo near 0* We set the r-neighborhood of 0g as D (Assumption E and H. To measure the discrete mean exit time, we repeatedly execute a vanilla SGD from Op for 1000 times and take an average number of steps which SGD exit from D (i.e. when the distance from Og becomes farther than r).
To control A, follow the approach of Xic ct 220.. We obtain sharper minima by mapping the loss function L to La such that (0) == L( vad) (a > 0) and setting 8g := fg/a Since this mapping coverts ad with other properties remaining the same,
surrogate of X.
We show the results in Figure E1 As Theorem e suggests, the noise magnitude /n/ B exponentially accelerates the escaping under our experiment setup, and eigen value and radius have the effect of exponentially slowing down the escaping
RELATED WORKS
We summarize relevant studies related to the topics on loss surfaces and the stochastic gradient descent algorithm. We mainly consider the following three factors.
Loss surface shape: Shape of loss surfaces have long been topic of interest. The argument that the flatness of loss surfaces around local minima improves generalization was first studied by Hochreiter [997), and the observation has recently reconfirmed in deep neural networks by Keskar et all (2016). Sagun et al] (2017) empirically examined the flatness of loss surfaces. The
Schmidhuber (1995
theoretical advantage of the flatness was criticized by Dinh al. (2017) in terms of scale-sensitivity of flatness, but [I suzuku et all (2022) and Rangamann et al, (201g) tackled the criticism by developing scale invariant flatness measures. An effect of the shape of loss surfaces on SGD was investigated
in Wu et all (2017); Ge et all (2018), and Chaudhari et all (2019); Forct et all (2020) developed
variant SGD which made use of this fact. In addition to the flatness, He et all (2019h) proposed
notion of asymmetry of loss surfaces, and eta (201)); Ganpov et all (20K) studied
how several local minima in a loss surface are connected. Li all (2018) developed a random dimensional reduction method visualize loss surfaces high dimensional spaces.
Exit/Stability of SGD: How SGD behaves in neighhorhoods of local minima in loss surfaces is investigated from aspects: stability and escape efficiency. For stability, way in which SGD finds local minima and stabilizes was analyzed by Wi et all (2018); Klemberg et al, (2I18); Achild al (2019); Lietal (20 Smith Le (2017) used Bayesian ideas to analyze the stability. For exiting aspects, Jastrzebski et all (2017) investigated an effect of Hesse matrix of local minima on the ease of escaping ineffective local minima, and Xie all (2020) elaborated this effect via quantitative analysis. Zhu all (2019) showed that anisotropic structure of gradient noise by SGD useful in escaping inefficient local minima, and Igguyen et all (2011) studied an effect of non- Gaussianity of the gradient noise.
SGD property: Detailed nature of SGD itself is also an object of interest. The magnitude of the gradient noise by SGD is an important factor, including its relation to a learning rate and batch size. An effect large batch sizes on the reduction of gradient noise is investigated in Hotter el all (2017); Smith at (2018); Masters. & Luschi (2018). Another area of interest shape of gradient noise distribution. Zhu et all (2019; Hu et all (2017;; Daneshmand et all (2018) investigated the anisotropic nature of gradient noise and its advantage. Simsekli all (209 discussed the fact

---

Under review as a conference paper at ICLR 2022
that gradient noise distribution has heavier tail than Gaussian distributions. Nguyen al (20T))
Şimsekli et all (2011) showed benefits of these heavy tails for SGD. PaDigrag et al. (2 rigorously examined gradient noise in deep learning and how close it is to Gaussian. Xie et (2024)) studied
a situation where the distribution is Gaussian, and then analyzes the behavior of SGD a theoretical way.
CONCLUSION
In this paper, we develop novel quasi-potential theory for the escape problem of SGD, Our theory gives an intuitive picture of SGD's escaping dynamic, and also but is an effective tool for formal analysis. our main result, our theory explicitly describes how the escape of SGD is affected by batch-size, learning rate, and radius of regions, and sharpness (Theorem M.). Furthermore, due to its flexibility, our theory allows the extended analyses, such as SGD's escape under even weaker assumption covariance matrix (Theorem E) and the escape problem of a discrete SGD (Theorem 21. We believe our theory provides solid insight for SGD dynamics and also flexible theory for further studies.
REFERENCES
P-A Absil and K Kurdyka. On the stable equilibrium points of gradient systems. Syst. Control Lett., 55(7):573-577, July 2006.
Alessandro Achille, Giovanni Paolini, and Stefano Soatto. Where is the information in a deep neural 2019.
network? arXiv preprint
Madhu S Advani, Andrew M Saxe, and Haim Sompolinsky. High-dimensional dynamics of gener- alization error in neural networks. Neural Nenw, 32::428-446. December 2020.
Alnur Ali, J Zico Kolter, and Ryan Tibshirani. continuous time view of early stopping for least squares regression. In The 22nd International Conference Artificial Intelligence and Statistics, pp. 1370-1378. PMLR, 2019.
Rajendra Bhatia. Matrix Analysis. Springer, New York, NY, 1997.
Avrim L Blum and Ronald L Rivest. Training 3-node neural network is np-complete. Neural Networks, 5(1):117-127, 1992.
Alon Brutzkus, Amir Globerson, Eran Malach, and Shai Shalev-Shwartz. Sgd learns over- parameterized networks that provably generalize on linearly separable data. arXiv preprint 17Xiv:1710. 101744 2017.
P Chaudhari, A Choromanska, S Soatto, and others. Entropy-sgd: Biasing gradient descent into wide valleys. Journal of Statistical Mechanics: Theory and Experiment, 2019.
Ronan Collobert, Jason Weston, Léon Bottou, Michael Karlen, Koray Kavukcuoglu, and Pavel Kuksa. Natural language processing (almost) from scratch. J. Mach. Learn. Res., 12(ARTICLE): 2493-2537, 2011.
Hadi Daneshmand, Jonas Kohler, Aurelien Lucchi, and Thomas Hofmann. Escaping saddles with stochastic gradients. In Proceedings of the 35th International Conference on Machine Learning, volume 80, pp. 1155-1164, PMLR, 2018.
Claudio De Stefano, Francesco Fontanella, Marilena Maniaci, and Alessandra Scotto di Freca. A method for scribe distinction in medieval manuscripts using page layout features. In International Conference on Image Analysis and Processing, pp. 393-402. Springer, 2011.
Amir Dembo and Ofer Zeitouni. Large Deviations Techniques and Applications. Springer Berlin Heidelberg, Berlin, Heidelberg, 2nd edition, 2010.
Laurent Dinh, Razvan Pascanu, Samy Bengio, and Yoshua Bengio. Sharp minima can generalize for deep nets. In International Conference Machine Learning, pp. 1019-1028, 2017.
10

---

Under review as a conference paper at ICLR 2022
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. PMLR. 2018.
Pierre Foret, Ariel Kleiner, Hossein Mobahi, and Behnam Neyshabur. Sharpness-aware minimiza- tion for efficiently improving generalization. In International Conference on Learning Represen- tations, 2020.
Mark I Freidlin and Alexander D Wentzell. Random Perturbations of Dynamical Systems 3rd Ed. Springer Berlin Heidelberg, Berlin, Heidelberg, 2012.
Timur Garipov, Pavel Izmailov, Dmitrii Podoprikhin, Dmitry Vetrov, and Andrew Gordon Wilson.
Loss surfaces, mode connectivity, and fast ensembling of dnns. In Proceedings of the 32nd Inter- national Conference on Neural Information Processing Systems, pp. 8803-8812, 2018.
Rong Ge, Jason Lee, and Tengyu Ma. Learning mee-hidden-laer neural networks with landscape design. In International Conference on Learning Representations, 2018.
Emmanuel Gobet. Monte-Carlo Methods and Stochastic Processes: From Linear to Non-Linear.
CRC Press, September 2016.
Emmanuel Gobet and Stéphane Menozzi. Stopped diffusion processes: Boundary corrections and overshoot. Stochastic Process. Appl., 120(2):130-16)) Februrrr 2010.
Fengxiang He, Tongliang Liu, and Dacheng Tao. Control batch size and learning rate to generalize well: Theoretical and empirical evidence. Advances in Neural Information Processing Systems, 2019a.
Haowei He, Gao Huang, and Yang Yuan. Asymmetric valleys: Beyond sharp and flat local minima. Advances in Neural Information Processing Systems, 32:2553-2564, 2019b.
Sepp Hochreiter and Jürgen Schmidhuber. Simplifying neural nets by discovering flat minima. In Advances in neural information processing systems, pp. 529-536, 1995.
Sepp Hochreiter and Jürgen Schmidhuber. Flat minima. Neural computation, 9():1-42, 1997.
Elad Hoffer, Itay Hubara, and Daniel Soudry. Train longer, generalize better: closing the general- ization gap in large batch training of neural networks. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pp. 1729-1739, 2017.
Wenqing Hu, Chris Junchi Li, Lei Li, and Jian-Guo Liu. On the diffusion approximation of noncon- vex stochastic gradient descent. arXiv preprint arXiv: 07562, 2017.
Wenqing Hu, Zhanxing Zhu, Haoyi Xiong, and Jun Huan. Quasi-potential as implicit regularizer for the loss function in the stochastic gradient descent. arXiv preprint arXiv:/90J.06054 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:1711.044. 2017.
Stanislaw Jastrzehski, Devansh Arpit, Oliver Astrand, Giancarlo B Kerg, Huan Wang, Caiming Xiong, Richard Socher, Kyunghyun Cho, and Krzysztof Geras. Catastrophic fisher explosion: Early phase fisher matrix impacts generalization. In International Conference Machine Learn- ing. pp. 4772-4784. PMLR, 2021.
Yiding Jiang, Behnam Neyshabur, Hossein Mobahi, Dilip Krishnan, and Samy Bengio. Fantastic generalization measures and where to find them. arXiv preprint arXiv:191..02178. 2019.
Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Pe- ter Tang. On batch-batch training for deep learning: Generalization gap and sharp minima. arXiv preprint arXiv: 1X09::600.0445 2016.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv: 44/26698, 2014.
11

---

Under review as a conference paper at ICLR 2022
Bobby Kleinberg, Yuanzhi Li, and Yang Yuan. An alternative view: When does sgd escape local minima? In International Conference on Machine Learning, pp. (698-2707, PMLR. 2018.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convo- lutional neural networks. Adv. Neural Inf. Process. Syst., 25:1097-1105, 2012.
Yann LeCun. 1.1 deep learning hardware: Past, present, and future. 2019 IEEE International Solid- State Circuits Conference (ISSCC), pp. 12- iecexplore.ieee.co February 2019.
Hao Li, Zheng Xu, Gavin Taylor, Christoph Studer, and Tom Goldstein. Visualizing the loss land- scape of neural nets. Advances in Neural Information Processing Systems, 31, 2018.
Qianxiao Li, Cheng Tai, and Weinan E. Stochastic modified equations and adaptive stochastic gradi- ent algorithms. In Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 2101-2110. PMLR, 2017.
Stephan Mandt, Matthew Hoffman, and David Blei. A variational analysis of stochastic gradient algorithms. Maria Florina Balcan and Kilian Q Weinberger (eds.), Proceedings of The 33rd International Conference Machine Learning, volume 48 of Proceedings of Machine Learning Research, pp. 353-363, New York, New York, USA, 2016. PMLR.
Dominic Masters and Carlo Luschi. Revisiting small batch training for deep neural networks. arXiv preprint arXiv: 22..0,06222222 2018.
Tomáš Mikolov, Anoop Deoras, Daniel Povey, Lukáš Burget, and Jan Černocky. Strategies for training large scale neural network language models. In 20/1 IEEE Workshop on Automatic Speech Recognition Understanding, pp. 196-201. ieeexplore.ieee.ogg December 2011.
Thanh Huy Nguyen, Umut Şimşekli, Mert Gürbüzbalaban, and Gaël Richard. First exit time analysis of stochastic gradient descent under heavy-tailed gradient noise. arXiv preprint 1rXiv:1906.09066 2019.
Abhishck Panigrahi, Raghav Somani, Navin Goyal, and Praneeth Netrapalli. Non-gaussianity of 2019.
stochastic gradient noise. arXiv preprint
Maxim Raginsky, Alexander Rakhlin, and Matus Telgarsky. Non-convex learning via stochastic gradient langevin dynamics: nonasymptotic analysis. In Satyen Kale and Ohad Shamir (eds.), Proceedings of the 2017 Conference on Learning Theory, volume 65 of Proceedings of Machine Learning Research, pp. 1674-1703. PMLR, 2017.
Akshay Rangamani, Nam H Nguyen, Abhishek Kumar, Dzung Phan, Sang H Chin, and Trac D Tran. A scale invariant flatness measure for deep network minima. arXiv preprint arXiv: 1902. 02434, 2019.
Levent Sagun, Utku Evei, V Ugur Guney, Yann Dauphin, and Leon Bottou. Empirical analysis of 2017.
the hessian of pee-paaametriized neural networks. arXiv preprint
Robin M Schmidt, Frank Schneider, and Philipp Hennig. Descending through crowded valley- benchmarking deep learning optimizers. In International Conference on Machine Learning, pp.
9367-9376. PMLR, 2021.
Unut Şimşekli, Mert Gürbüzbalaban, Thanh Huy Nguyen, Gaël Richard, and Levent Sagun. On the heavy-tailed theory of stochastic gradient descent for deep neural networks. arXiv preprint 191:00191..00018, 2019.
Umut Simsekli, Levent Sagun, and Mert Gurbuzbalaban. A Tail-Index analysis of stochastic gra- dient noise in deep neural networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceed- ings of Machine Learning Research, pp. 5827-5837. PMLR, 2019.
Samuel L Smith and Quoc V Le. A bayesian perspective on generalization and stochastic gradient descent. arXiv preprint 1rXiv= 2017..
12

---

Under review as a conference paper at ICLR 2022
Samuel L Smith, Pjeter-Jan Kindermans, Chris Ying. and Quoe V Le. Don't decay the learning rate, increase the batch size. In International Conference on Learning Representations, 2018.
Gerald Teschl. Ordinary differential equations and dynamical systems. Grad. Stud. Math., 140: 08854-0885 08019, 2000.
Yusuke Tsuzuku, Issci Sato, and Masashi Sugiyama. Normalized flat minima: Exploring scale in- variant definition flat minima for neural networks using pac- pac-bayesian analysis. In International Conference Machine Learning, pp. 19366696444 PMLR, 2020.
Lei Wu, Zhanxing Zhu, al. Towards understanding generalization of deep learning: Perspective of loss landscapes. arXiv preprint arXiv: 7706. /0239, 2017.
Lei Wu, Chao Ma, et al. How sgd selects the global minima over per-paaameterize learning: A dynamical stability perspective. Advances in Neural Information Processing Systems, 31:8279- 8288, 2018.
Zeke Xie, Issei Sato, and Masashi Sugiyama. A diffusion theory for deep learning dynamics: Stochastic gradient descent exponentially favors flat minima. In International Conference on Learning Representations, 2020.
Pan Xu, Jinghui Chen, Difan Zou, and Quanquan Gu. Global convergence of langevin dynamics based algorithms for nonconvex optimization. arXiv preprint 17X1v:1707.06611 2017.
Zhanxing Zhu, Jingfeng Wu, Bing Yu, Lei Wu, and Jinwen Ma. The anisotropic noise in stochas- tic gradient descent: Its behavior of escaping from sharp minima and regularization effects. In International Conference on Machine Learning, pp. 7654-7663, PMLR, 2019.
A JACOBI EQUATION OF QUASI-POTENTIAL
Theorem 4, For all 9 E D, (0) satisfies the following Jacobi equation,
(10)) VL (0) vV(0) -0
Proof of Theorem M For u, E Rd, we introduce an inner product and norm regarding a point E D as (u, v) == T C (0) v and |ullo == / (u, u)e. With these definitions, the (up( is
written follows:
1 /''' || + VL (P:)) dt. 2
Sor(p) =
(10)
Note that fo D holds for any E [0, [] by the definition of trajectories. We rewrite the integrand of (III) as follows:
ll + VL (pp:)l
l1 + ( + VL (v:))
(Ilsell, - VVL ) +2 1 II [VL
+2 26,, VL (p))
2 2 1211 [[V)) + (1), VL ((:)))
(11)
We develop parameterization for the term in (LI). For a trajectory yo, we select an bijective function
ʃ (0, 1] - [0, 7) as satisfying the follows: for each [0, T] and 1" E [0, as f((",,
parameterized trajectory st. (P(()) satisfies
|1 11:tt-1p;;- I|V Mlp..
(12)
This parameterization reduces the quasi-potential to the minimum of the following quantity:
(Sor(p) 2 (p") =) /
((T)
l1vt. lp: IIV (Vt-)))) (pt.)) (6t. V (pt-)) dt
(13)
13

---

Under review as a conference paper at ICLR 2022
subject the constraint (I22). Since the integrand of (T3) includes the first order derivative regarding tr, (IE)) holds over different parameterizations f. For convenience, we use another bijective parame-
terization function g [0, R] + [0, 1] as t* g(r) with R >> 0 and [0, R) such that Gr := (Pr())
satisfies
11 =.
(14)
Then, the
is reduced the following formula,
v(0)= inf refo, Rl:lll 1l,, -1.-=11. /"" (I15.Ile. VVL VVL (9.) + ( VL (1..)
dr,
(15)
8,
where Pn 0. By the Bellman equation-type optimality, expand the right hand side of (IS) into the following form:
(Irs (Iéb-lle, (VL + ( (L))) ) )dr ((@R-))
V(0)
inf Ill
(16)
with width value 8 O. The Taylor expansion around R gives
J/ R--
n
[1è-lla. IVL (b.)lla + ( VL (
dr v(SR-))
2.
(VI((n)) [VL((N)ll
VVV +V (VRR)+
PR
Taking + and noticing fR = (16)) can simplified to the following equation:
inf
[|VI + (VI(=),, ,bx), - VVVV (0)
(17)
re 10
It remains to select & which solves the minimization problem IM holds,
Since the following equality
(L(O) (R),
(0)= = (v .
(18)
it is easy to see that trajectory & such that
$ VI(x) VV (B)
|V VV VV (0)
minimizes
(8
With this s*. simplifies
|L)())l [[V VV (8) 1lo.
Taking the square of both sides, we get the statement.
B THEOREM ON EXIT TIME
In this section, we develop the following fundamental theorem on the notion of exit time. For simplicity, we use e to denote / nn/ B. Theorem 5. e is sufficiently small,
E E exp E VVl
holds, where Vo == mingrean V(0')
One might think that if parametrize above (E the equality condition for ([ is violated. Indeed
Sor (+) # L''' I| IVV (o)) + (jb.. VL ((+)) dt
for G. However, & is introduced just for the simple calculation of (or()²") Although & frequently appears in the proof, attention is still on yp and Sor (4²). not on Sor (fp)
14

---

Under review as a conference paper at ICLR 2022
To prove this result, provide the proof for upper bound (Lemma ( and lower bound (Lemma M). Throughout the proofs, we use Cur,e, Pe., instead of Cor or P, to elearly indicate which trajectory are referring to.
We introduce several notions. For d > 0 and R let (0) denote an o-neighbourhood of that is, (0) (6' E R ||0' A|| - 6). Further, for set è C TR (e) (o)
The following lemma provides preliminary facts for proofs.
Lemma 5. For any c > 0, there exist μl, p2, Ti, T2 > such that the the followings hold:
1. V0 D. there exists a trajectory spt such that sp - 0. sp /2,/2((0)) T S Ti and Sor (or) ( =0
2. V0 B,,(00),
(0*), there exists a trajectory x²² such that 9/ v E (D), S T2
and Sor( < Vo
aB pz (D)
D
Ba (0r))
By, (8))
Figure Illustration of domains and boundary, D. B (fn) Bu, (8*), and 0B,,, (D)
The illustration can be found in Fig. H
Proof of Lemma & The first statement immediately holds by the fact that D is attracted to a asymp- totically stable equilibrium position 0* (Assumption B and B)
For the second statement, since Vo == mingread V (8'), there exists a trajectory oot such that أf 8", 4pt E OD and Sor. (y²") Vo, where T, is finite by Lemma 2.2 (a) in Freidin & Wentzell (2012. We cut off the first portion of yp up until the first intersecting point with B,,, (8*) and define it th. This means vi E (f*( 177, E aD and Sor, (v²") < V, hold. By Lemma 2.3 in Fraidin Wentzell (2012), there exists a trajectory from ih, to point 0na 0B (D) such that the steepness is less than K|Op,, - -,%%, with a constant > 0. Then, if we take a small enough (42, we can obtain o such sp PT. sf. E (B, and Sor. (xp*) < S. By connecting &p and y obtain appropriate 2²
L
Lemma 6. Iff 0 is sufficiently small,
E [r]]= = exp --2V
holds, where Vo mineeaa V(0').
Proof of Lemma E We show that for any constant c > 0. there exists small such that Ve S Eo such that E [r] S exp [s (V, + e)]. To the aim, we split the dynamical system (L) our interest into the first half and the second half, { and {0 {0) J. starts with 0f 0o D and terminates when it first reaches (8*). We define the terminating time of (0/}, 71 = minft > 0: 0
Baz/2 /2./2/0 (00))(0)) }}- On the other hand, (0] ) starts with og Or B B2,/2(0") and terminates when it first
15

---

Under review as a conference paper at ICLR 2022
reaches 0D. We define the terminating time of {ff) T2 min 0: 0 0D}. Clearly, the exit time = T1 + T2.
Regarding 71 and T2, we show the following two independent facts with sufficiently small 0.
Fact Ti no more than Ti with probability at least 1/2.
Fact 2 is no more than 72 with probability at least exp {-c-² (Vo + tc).
Fact Given the trajectory 9i provided by Lemma Extpl (1 1), the following inequality holds
Lemma gives us that if
Pog Pog { E Coz,, ob
(R") p (V'' m2/22 2 exp {-
Therefore, if we take < mint
21/ 1)}, we have
Pog Pegfos 1p' E Coz, (R²) (10 ,1) < /1/2 2
1
Since the event of (4' Cor, og (R2) no later than T1, obtain the following which provides Fact 1.
p ( (11) /n/2 means that {0)), reaches By, (0*) in
Pog fn < T 2 2
(19)
Fact Given the trajectory j22 provided by Lemma D.
Lemma
tells us that if s
<
Estpi (92, M2, c/2), the following inequality holds
Pog { Cor.. (R*) p (22) [2) 2 exp (- (Suzs (12) }
{sp E Corr, (Rd) p (22 < {22 is the event that {07) goes out of D in no more than the time
T2. Also, we know that Sor, (122 < Vo + & by Lemma B Hence, can conclude the following
for Fact
Pog (r2 < Th 2 exp (Vo cc).
(20)
Combining (19) and (20), we can obtain
1 exp - (Vo + cc]
Pa (T < Ti + T2)
(21)
Since this is simple exponential distribution, can obtain the following expectation:
E | < 2 (Ti + T2) exp
(Vo + c)}
By setting
min { { in 12 Sapp (491, /1/2, 1), Satpi(p2 12, e/2)
8 In 2(T T2)
we can get
E [T] < exp {e (Vo c)}
Then, we obtain the statement.
Next, we develop the lower bound on the exit time.
Lemma 7. If 0 is sufficiently small,
E [ (2 exp [e- vol)
holds, where Vo mingrean V(0').
16

---

Under review as a conference paper at ICLR 2022
Proof of Lemma A We show for any positive constant 0, there exists small such that Ve - Eg. E [r] 2 exp E (Vo - c)] holds.
We consider a specific case where the initial value of (G)) is in aB /2 which can be trivially extended to general cases. Consider Markov chain Zu (k N) discretization of O, TM with k-th time grid Th. It is formally defined as follows:
1. 70 0,
2. 0k -inf (t > Th 0, 0B (8*)),
3. = inf (t > ύk-1 0, E OB, /2 U
4. 2 = 8
0g Z
0 = 0 = Z
O
0, = 0z, = 7m
Figure 4: A continuous trajectory 0, and the Markov chain Z generated from (0c). Colored domains indicate D, (f0)) and B,,, (0") as illustrated in Fig. G
By introducing Za. can reduce the continuous process {0.), )r to discrete Markov chain transiting between 0B ,B,,/ /2 (0*) and 0D. The illustration can be found in Fig. g.
Let K = fh |||
Z E aD} Then, we have T = Ty and
E E Σ
Peo {k> k}
Peo {k k 11 11)+1))
Σ k=
Poo {K 2 nz (Th Tk-1).
k=U
This can be further evaluated as
E
Σ
Po fk 2x 0k-1)
Σ Poo {N 2 n}
inf OnE0B, (0-)
Elml)
which follows Tk-1 0k- Since /2 (0)) is strict subset of B, (0*), and B,,, (0)) is strict subset of D. it takes positive amount of time to transit from OB (f*) ) to either O (0') or OD, and there exists a positive lower bound t for inf (0*) [[T]] that is independent of E. Thus we get
t
Ped {k 2 k}.
k=1
By Lemma & we immediately get Poo {N > h} > [] - expp -Vo c) hence we have
E B Σ [1 exp ( -- 2 (Vo
=t fe -2 (Vo c)}
k=1
This implies E(r] 2 exp(e-211 o)} holds if is small enough.
17

---

Under review as a conference paper at ICLR 2022
Lemma 8. We obtain
P E 0D Zu E Bp1/2(0))) exp 3-8- (V- (c)-
Proof of Lemma 8 First, decompose P(Zk+1 0D Za 0B (l,22((())) into parts in the following way:
Zx E 0B /2(1)((00)) (2x+1 E EDD
max 1 (
Poj { = [
(22)
max 0gE0B
Pog {r
T) + Pog f-= f
This holds for arbitrary T. we pick T = T large enough so that this inequality holds for the first term:
Poù (T = T") S exp { {-e-2 (Vo -c]}
(23)
The existence of such T is guaranteed by the fact that Vo is finite and the following lemma.
Lemma 9 (Lemma 2.2 (b) in Freidlin & Wentzell (2012)). For any a > 0, there exists positive constants and To, such that for all sufficiently small > 0 and any t, (f)) we have the inequality
Poo (Sa T3 exp - - -T
where Ca. inf {t: Og & (0)}}
Given a constant T", we consider bounding Pag =T= Ti < <T). Consider the following set of jectories:
@VV -06)--)2))= = {op 90 0, Sor (pp Vo c/2
Since it takes least Vo reach 0D from 8", the following inequality holds:
Peg {T Ti T'} - Peg (Py <Vo c/2)]
Also, Lemma Q implies, for all S Supp (Vo 0/22))
P Por (
(v E Cur,o (RQ) p((('' VVV c/2)) 2 6) s expf - -2 ?VVo c/2) - c/2))
expl - 2(o - c)}
Since can be arbitrarily small, the event fep & Φ(V. - c/2)} is equal to the event of {sp
Cur.o (R*) p((p' V(V c/2)) 2 8). Hence, we obtain
Pøş {r = Ti T} < exp(-s (Vo c)}.
(24)
we set < Vln Estp2
(Vo Vo c/2, 5, c/2)), we conclude
Po { 7 < 7} expl-s-2 c)}.
(25)
Combining
and
we prove the statement.
C PROOFS FOR LEMMA AND LEMMA E!
Proof of Lemma G We introduce several definitions only for this proof. Supposing that have a vector I = (I), Æn) E R", zt and æ denote vectors whose coordinates are obtained by rearranging the numbers I, in decreasing order and in increasing order respectively, that is, at
(ot. (ot.......) ....))) and x = ..).....)))) where of 2 2 ot and of & ... S xt. Also, given
y,y Rd. we denote x < y, if
b and
Σ 0
x
y for $ 4k nn.
1=
j=1
j=1
==1
18

---

Under review as a conference paper at ICLR 2022
For matrix A, X(A) A2A), (A)). Also, define its elementwise loga- rithm log X(A) = (log A1 (4), log lop (A)).
Corollary 116 in (Bbana 1997) claims that given two positive matrices A and B, we have
log X (A) + log (B) log X(AB) log ( log (B)
Following the definition of x, the left part, log A (A) log x log (AB). can be equivalently restated
Σ
log A + log
(B)) -
(log A(AB)}} for S 4k S
1
j=1
For the case k 1, we have
{log X (A) + log Xog)+ 2 {log X(AB)}
max flog An (1 log (B) I log Amax (AB) 18i5
Since maxicien flog (n- + log (B) 2 log (A) + log (B log Amin (A) log Amax B) holds, have log Amin (A) log Amax (B) log Xmax (AB), equivalently
Amin (A)Amax (B) S Amax (AB).
Since Amax(A) 1/Amiu (A- have
Amax (A-2) Amin (B-1) Amin ((AB)
Amin (ABB)-1) I Amax (A-1 )rrii (B-1).
Since commuted matrices share eigenvalues, Amin ((AB)-1) AB BA- we have
Amin (A-1B-1) S Amax (Amx(n-))mmnn (B-1).
Proof of Lemma A Amax(A) (A) is equal to the spectral norm of A. By the sub-multiplicaiive property of spectral norm, we obtain
Amax (A) (A) (B) Amax (AB),
Therefore, since Amax (A) = 1/> Amin (A (A-1),
Xmaox (A (A-1) ) (B BB-) 1)2 2 Amax (A (A-1
Amax (A
Amma
(B ) 2 Amax Camax((AA)) ((AB)
1
Amiu (A) Amiul B))
Amin (AB)
Amin (AB) 2 Amin ( (A))min B).
Then, obtain the statement.
19


Reviews:
[{"review_id": "Z00UYWVFjat", "reviewer": "Reviewer_NNov", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "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": "There is a deep inconsistency while using the quasi-potential theory to study the escape properties of such dynamical processes as SGD. The point is that quasi-potential, or in general the Freidlin-Wentzell type large deviations theory, handles \"large scale\" or \"global\" deviations from equilibrium positions. However, in the computable cases the authors must make assumptions on the local properties of the loss landscape, such as their Assumption 1, which essentially says that the loss function is quadratic. Such quadratic approximations can only hold near the equilibrium point (by Morse theory). Thus at a large scale, explicit analytical calculations based on quasi-potential for quadratic loss landscape is not applicable to the escape from local minima of SGD, since such escape is about the \"far from equilibrium\" situation. There is also an inadequacy of citing references, since very similar approaches and even the same examples of quadratic loss landscape have already been considered in Hu et al (2019). The major reason why the authors of Hu et al (2019) did not formally publish their work, but remains it as a preprint, is somehow mainly due to the same inconsistency issue pointed out here.", "summary_of_the_paper": "This work proposes to use the notion of quasi-potential to analyze the dynamics and escape properties of SGD from local minima. Authors expect to use the quasi-potential theory to obtain a quantitative criteria for the ability of escape from local minima.", "summary_of_the_review": "There is a deep inconsistency in the theory proposed in this paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "XUISk6CjyL7", "reviewer": "Reviewer_mKRS", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "1- The paper is well written and easy to follow. The experimental results are confirming the theoretical results. \n\n2- The assumptions 2,3 are still strong and unlike the Xi et al 2020 paper, the covariance C(\\theta) depends on the Hess of minimizer and is independent of \\theta.  \n\n3- In Xi et. al 2020 the exit time depends on the inverse of sharpness but in your results, it depends on it directly. How can one explain this discrepancy? \n\n4- The analysis just considers the SGD with fixed step size however in practice we use decreasing step size to train DNNs. What are the challenges of analyzing this scenario? \n\n5- The exit time depends exponentially on the sharpness. Now, if at the minimum \\lamba=0 and we have wide minima then based on your results the trajectory should jump out of that region instantly which contradicts our observation in practice. How can we explain this based on your theoretical results? \n", "summary_of_the_paper": "This paper uses the quasi potential theory to formalize the escape behavior of SGD happening while training a deep neural network. The quasi potential is defined based on the steepness of a trajectory and is the smallest steepness to go from the minimizer to another point. Utilizing this they analyze both continuous and discrete SGD and show that the average exit time for a trajectory of SGD to move out of the neighborhood of minima depends exponentially on the mini-batch size, the sharpness of the minima, the radius of the neighborhood, and the inverse of learning rate. ", "summary_of_the_review": "The analysis just considers the SGD with fixed step size however in practice we use decreasing step size to train DNNs. What are the challenges of analyzing this scenario? ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "3KNfD2CmbfX", "reviewer": "Reviewer_5Jw7", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "I am not absolutely familiar with the literature of escape time theory for SGD. And, first, I would like to state two important points about this approach: \n - it is not clear for me how it really relates to the explainability of good generalization properties of SGD as stated in the introduction on page 1 in italic center-text. I would have liked more motivation on this fact in the main text. Maybe with some concrete examples that such phenomena exist in practice (escaping bad local minima very fast for example).\n- it is also not clear for me how Assumptions 1 and 2 are good models for what happens in practice. Especially for Assumption 2, for which it has been importantly remarked in S.Wojtowytsch [ https://arxiv.org/abs/2106.02588 ] and Pesme et al. [ https://arxiv.org/abs/2106.09524 ] that the covariance is degenerate near optima and hence cannot be equal to $H^*$ (except if one adds some random noise intentionally in the data set or if one considers the infinite data limit -which is not explained in the article). \n\nI truly understand that these are share problems with already published literature, but still, I am not very convince about these results for the reasons above. \n\nLeaving this discussion on the side, let us now comment a bit more the precise results of the paper under review.\n\nFirst, I have to say that the paper is not very clearly written: for exemple important paragraphs such as the end of the abstract or the exposition of the main contributions are \n fuzzy. It makes the reader confused as it is difficult to know *what results* are going to be proven, *what* is the new contribution of the article, and *why* it is interesting. An archetypal example of this fact is that the authors claim to have developed a \"novel quasi-potential theory that rigorously describes the escape of SGD\": in fact, quasi potential theory is a *theoretical methodology* that helps in exhibiting escape rates, whereas it is often presented as a contribution in itself in the article (even if obviously large deviations is an important theory that should help understanding some of the behavior of SGD).\n\nSecond, it is very troubling that Table 1 offers comparison with some similar studies without explaining precisely the difference in the assumption and/or the results. More importantly, as results of the present article go sometimes in opposite directions with the bounds of Table 1, it is very weird to have almost zero comments on it. Is the bound of the present article in contradiction with the other ones ? stated in a much restricted setting ? only valid in some limit ? For this reason, comparison is, under the current form, almost impossible to make.\n\nThirdly, and maybe more importantly, the content appears to be mathematically not very precise if not sometimes incorrect: a mild example of this fact is that theorems are stated as equality whereas is seems obvious that they are in fact asymptotic first order developments with respect to parameter $\\eta/B$ at the exponential scale (as it is always the case in large deviation theory). Another example is that the well known Hamilton-Jacobi equation Eq (4), is not clearly introduced: no name, no references, no mention of the fact that there is under general assumption no unicity...\n\nFinally, the statements of the theorems are not enough put in perspective with practice and precise SGD dynamics behavior. Do we really see this dynamical phenomenon *during the training of SGD* (and not, as the experiments show, if initialized near a minimum) ?\n\n\n\n ", "summary_of_the_paper": "The paper under review gives mean exit time rates in the small step-size limit of SGD under some quadratic approximation of the loss. The analysis rests on standard results of Freindlin -Wentzell large deviation theory.", "summary_of_the_review": "To conclude, the results of the presented paper may be of great interest, but under the current form, without any proper mathematical formulation, more rigorous comparison, or further perspectives with SGD behavior, I consider that this paper should be revised before resubmission.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper uses quasi-potential theory to analyze the escape behavior of SGD. Although this is a topic of interest to the ML community, the reviewers found a critical issue with the paper, which the authors admit can not be fixed during this submission. I, therefore, do not think there is a need for a longer discussion.
Decision: Reject