Year: 2021

Abstract:
We develop a quantitative theory on an escape problem of a stochastic gradient descent (SGD) algorithm and investigate the effect of sharpness of loss surfaces on 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-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 al., 2020). We also conduct experiments to empirically validate our theory using neural networks trained with real data.

heading: 1 INTRODUCTION
text: In recent years, the successes of deep learning have been a major driving force of machine learning development (LeCun, 2019). Owing to its strong generalization capability, deep learning has diverged into a wide range of domains, such as computer vision (Krizhevsky et al., 2012), speech recognition (Mikolov et al., 2011), and natural language processing (Collobert et al., 2011). 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 al., 2021). However, at the same time, those unprecedented successes raise a 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, 1992), SGD can find nearly optimal solutions empirically, and further, the obtained solutions generalize well (Keskar et al., 2016; Brutzkus et al., 2017). Analyzing SGD’s role on deep learning is an area of research that is currently attracting strong interest (Masters & Luschi, 2018; Jastrzebski et al., 2021).
One of the promising directions for this question is to study the geometric properties of a training loss landscape. Many empirical studies have found that minima obtained by SGD have distinctive geometric properties. Keskar et al. (2016) have shown that the shape of the minima obtained by SGD tends to be flat. He et al. (2019b) have deepened the investigation by picturing that SGD settles on the flatter side of asymmetric loss surface, which they named “asymmetric valley." Draxler et al. (2018) and Garipov et al. (2018) have shown that separate minima obtained by independent training processes are internally connected through pathways. Li et al. (2017) 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.
An escape problem is a scheme to analyze the dynamic of SGD escaping from local minima (Zhu et al., 2019; Jastrzębski et al., 2017; Hu et al., 2019; Nguyen et al., 2019; Xie et al., 2020). This scheme allows us to investigate why SGD avoids (potentially) bad local minima and settles on good minima. Zhu et al. (2019) 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. Hu et al. (2019) rigorously identified the role of learning rate in escaping. Nguyen et al. (2019) used the Levy process to provide the precise description of SGD as well as its escaping phenomena. Jastrzębski et al. (2017) developed a theory of stochastic differential equation and quantified how the anisotropic noise affects its fast escape from sharp minima. Xie et al. (2020) refined the mathematical 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 time, which formally quantifies escaping. The notion of quasi-potential is defined in a fundamental theory of stochastic dynamical systems, named a Large Deviation Theory (Freidlin & Wentzell, 2012; Dembo & Zeitouni, 2010). Quasi-potential can formulate the distribution of trajectories that a stochastic dynamical system takes. To illustrate quasi-potential for SGD’s escaping problem, we introduce an intuitive notion, steepness of a trajectory (Fig. 1 and Definition 3), and show that it 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 a novel quasi-potential theory that rigorously describes the escape of SGD with no auxiliary variables. Our theory can concisely incorporate the effect of essential factors, i.e., a batch size (B), a learning rate (η), and geometric parameters of loss surfaces (r and λ)
• Our theory can be flexibly applied to 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 our result does not contradict the common knowledge but is a generalization of existing results, such as (Jastrzębski et al., 2017) and (Xie et al., 2020).

heading: 1.1 COMPARISON WITH EXISTING STUDIES ON ESCAPE PROBLEM
text: In Table 1, we 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 is the time to escape that we derive. Our theory provides a unified analysis of exit time incorporating all the essential parameters, batch
size, learning rate, a radius of the region around a minimum, and sharpness of a minimum. As a consequence, we 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 (Jastrzębski et al., 2017) and (Xie et al., 2020) because part of the sharpness dependency is hidden in ∆L. Provided that ∆L = r2λ under Assumption 1, one can see that our results are consistent with previous studies.
The second is our theory’s flexibility. Different from Jastrzębski et al. (2017) and Xie et al. (2020), our theory does not require that SGD reaches the stationary distribution before escaping, which is known to take exponentially many iterations (Xu et al., 2017; Raginsky et al., 2017). Additionally, our theory can evaluate the correspondence with the practical SGD, which has a discrete update rule and state-dependent noise.
Notations: For a k × k matrix A, λj(A) is the j-th largest eigenvalue of A, and λmax(A) = λ1(A) and λmin(A) = λk(A) denote the largest and the smallest eigenvalue of a square matrix. O(·) denotes Landau’s Big-O notation. ‖·‖ denotes the Euclidean norm. Given a time-dependent function θt, θ̇t denotes the differentiation of θt with respect to t. N (µ,Σ) denotes the multivariate Gaussian distribution with the mean µ, and the covariance Σ.

heading: 2 SETTING AND PROBLEM

heading: 2.1 STOCHASTIC GRADIENT DESCENT AND DYNAMICAL SYSTEM
text: Consider a learning model parameterized by θ ∈ Rd. Given training examples {xi}Ni=1 and a loss function ℓ(θ, xi), we consider a training loss L(θ) := 1N ∑N i=1 ℓ(θ, xi) and a mini-batch loss
LB(θ) := 1B ∑
xi∈B ℓ(θ, xi), where B is a randomly sampled subset of the training data such that |B| = B. We assume that L(θ) is differentiable and its derivative ∇L(θ) is Lipschitz continuous. We mainly consider two types of SGD: a discrete SGD and a continuous SGD. Although a discrete SGD is used in practice, we study continuous SGD as a starting point of our analysis because of its mathematical convenience. This is a widely used approach in general SGD analyses (Ali et al., 2019; Advani et al., 2020) as well as in the escaping analyses (Jastrzębski et al., 2017; Xie et al., 2020).
Discrete SGD: First, we give the usual discrete formulation of SGD. Given an initial parameter θ0 ∈ Rd, SGD generates a sequence of parameters {θk}k∈N by the following update rule:
θk+1 = θk − η∇LB(θk), (1) for k ∈ N, where η > 0 is a learning rate. In particular, we focus on SGD whose noise on gradients has a Gaussian distribution. We decompose −∇LB(θk) in (1) into a gradient term −∇L(θk) and a noise term ∇L(θk)−∇LB(θk), and consider a case that the noise is Gaussian. With this setting, the update rule in (1) is rewritten as
θk+1 = θk − η∇L(θk) + √ η
B Wk, (2)
where Wk ∼ N (0, ηC(θk)) is a parameter-dependent Gaussian noise with its covariance C(θ) := Ei∼Uni({1,...,N}) [ (∇L(θ)−∇ℓ (θ, xi))⊤(∇L(θ)−∇ℓ (θ, xi)) ] .We assume that C(θ) is Lipschitz continuous.
The Gaussianity of the noise on gradients is justified by the following reasons: (i) if the batch sizeB 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 et al., 2016; Jastrzębski et al., 2017; He et al., 2019a), although different findings have been obtained in other settings (Simsekli et al., 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 Gobet (2016)). With a time index t ≥ 0 and the given initial parameter θ0 ∈ Rd, the continuous dynamic of SGD is written as follows:
θ̇t = −∇L(θt) + √ η
B C(θt)
1/2 wt (3)
where wt is a d-dimensional Wiener process, i.e. an Rd-valued stochastic process with t such that w0 = 0 and wt+u−wt ∼ N(0, uI) for any t, u > 0. We note this system can be seen as a Gaussian perturbed dynamical system with a noise magnitude √ η B because η and B do not evolve by time.

heading: 2.2 ESCAPE PROBLEM AND MEAN EXIT TIME
text: We consider the problem on how SGD escapes from minima of loss surfaces. In this paper, our target of interest is quantified by a notion of mean exit time for continuous SGD and discrete mean exit time of discrete SGD. Let θ∗ ∈ Rd be a local minimum of loss surfaces, and D ⊂ Rd be a r-neighborhood of θ∗ with r > 0. We define the mean exit time as follows: Definition 1 (Mean exit time from D). Consider a continuous SGD starting from θ0 ∈ D. Then, a mean exit time of the continuous SGD (3) from D is defined as
E[τ ] := E[min {t : θt /∈ D}]. Definition 2 (Discrete mean exit time from D). Consider a discrete SGD starting from θ0 ∈ D. Then, a discrete mean exit time of the discrete SGD (2) from D is defined as
E[ν] := E[min {kη : θk /∈ D}].
These definitions are common in quasi-potential theory (Freidlin & Wentzell, 2012; Gobet, 2016). Intuitively, the smaller E[τ ] or E[ν] becomes, the faster the system escapes from a regionD. In other words, the system has a stronger tendency to escape from θ∗.
We remark that there are other formulations to analyze the escape problem. Zhu et al. (2019) define escaping efficiency as Eθt [L (θt)− L (θ0)]. Jastrzębski et al. (2017) and Xie et al. (2020) study a ratio between the probability of coming out from θ∗’s neighborhood and the probability mass around θ∗.

heading: 2.3 BASIC ASSUMPTIONS FOR THE ESCAPE PROBLEM
text: We provide basic assumptions for the escape problem, commonly used in the literature (Mandt et al., 2016; Zhu et al., 2019; Jastrzębski et al., 2017; Xie et al., 2020). Assumption 1 (L(θ) is locally quadratic). There exists a matrix H∗ ∈ Rd×d such that for any θ ∈ D, the following equality holds:
∀θ ∈ D,L(θ) = L (θ∗) +∇L (θ∗) (θ − θ∗) + 1 2 (θ − θ∗)⊤H∗ (θ − θ∗)
Assumption 2 (Hesse covariance matrix). For any θ ∈ D, C(θ) is approximately equal to H∗.
It is known that Assumption 2 holds around a critical point θ∗ (Zhu et al., 2019; Jastrzębski et al., 2017). It is also empirically shown that Assumption 2 can approximately hold even for randomly chosen θ (see Section 2 of Xie et al. (2020)). We further investigate a variant of Assumption 2 in Section 5.

heading: 3 QUASI-POTENTIAL THEORY
text: We introduce the basic notions of the quasi-potential theory. We start with defining a notion of steepness of a trajectory followed by the systems (3) on a loss surface L(θ). Let φ = {φt}t∈[0,T ] be a trajectory over a finite time interval [0, T ]. Or more formally, φ is a continuous map from [0, T ] to Rd, and is an element of C0T (Rd) which is a support of a dynamical process in [0, T ]. Given a trajectory φ and the system (3), we define the following quantity: Definition 3 (Steepness). Steepness of a trajectory φ followed by (3) is defined as
S0T (φ) := 1
2 ∫ T 0 (φ̇t +∇L (φt))⊤ C (φt)−1/2 (φ̇t +∇L (φt)) dt.
Steepness S0T (φ) can be intuitively interpreted as the hardness of climbing that the system (3) is exposed to while following the trajectory φ on L(θ) (Fig. 1). 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 & Zeitouni (2010).
Steepness is useful to describe a distribution of trajectories generated by dynamical systems. If a trajectory φ has a large steepness S0T (φ), 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 Freidlin & Wentzell (2012)). For any δ, ζ > 0, φ ∈ C0T ( Rd ) , and sufficiently small ε > 0, the following holds:
Pφ′ ( φ′ ∈ C0T (Rd) | ρ (φ′, φ) < δ ) ≥ exp { −ε−2 [S0T (φ) + ζ] } ,
where ρ(φ′, φ) = supt∈[0,T ] ‖φ′t − φt‖. Lemma 2 (Theorem 3.1 in Section 3.3 Freidlin & Wentzell (2012)). Let Φ(s) ={ φ ∈ C0T (Rd) | S0T (φ) ≤ s } . For any δ, ζ, s > 0 and sufficiently small ε > 0, we have:
Pφ′ { φ′ ∈ C0T (Rd) | ρ(φ′,Φ(s)) ≥ δ } ≤ exp{−ε−2(s− ζ)},
where ρ(φ′,Φ(s)) = infφ∈Φ(s) ρ(φ′, φ).
Although we restrict our attention to the system (3), the same discussion is applicable to a general class of diffusion processes and dynamical systems with Markov perturbations (For details, see section 5.7 in Dembo & Zeitouni (2010) or Section 6.5 in Freidlin & Wentzell (2012)).
Although there are several trajectories from θ∗ to θ ∈ D with different steepness, a dominating factor for mean exit time is the smallest steepness among them, which is called quasi-potential: Definition 4 (Quasi-potential). Quasi-potential of θ ∈ D is defined as
V (θ) := inf T>0 inf φ:(φ0,φT )=(θ ∗,θ) S0T (φ).
Similar to steepness, quasi-potential can be seen as the minimum effort the system (3) needs to climb from θ∗ up to θ on L(θ). (For more details, see Section 5.3 of Freidlin & Wentzell (2012)).

heading: 4 MEAN EXIT TIME ANALYSIS FOR SGD

heading: 4.1 ASSUMPTIONS
text: To analyze the mean exit time, the quasi-potential theory requires several assumptions regarding the stability of the system (3) at θ∗. Assumption 3 (θ∗ is asymptotically stable). For any neighborhood U that contains θ∗, there exists a small neighborhood V of θ∗ such that gradient flow with any initial value θ0 ∈ V does not leave U for t ≥ 0 and limt→∞ θt = θ∗. Assumption 4 (D is attracted to θ∗). ∀θ0 ∈ D, gradient flow with initial value θ0 converges to θ∗ without leaving D as t→ ∞.
where “gradient flow" means a continuous gradient descent defined as θ̇t = −∇L(θt). Stability is a commonly used notion in dynamical systems (Hu et al., 2017; Wu et al., 2017), although it does not always appear in SGD’s escaping analysis (Zhu et al., 2019; Jastrzębski et al., 2017; Xie et al., 2020). Assumption 3 is known to be equivalent to the local minimality of θ∗ under the condition that L(θ) is real analytic around θ∗ (Absil & Kurdyka, 2006). Also, by definition of asymptotic stability in Assumption 3, we can always find a region D that satisfies Assumption 4. The more detailed properties of stability can be found, such as in Section 6.5 of Teschl (2000). Assumption 3 and 4 are necessary to obtain the result (5) in the following section.
Also, we require the following assumption as a boundary condition of Theorem 4. Assumption 5. L(θ∗) = 0
Assumption 5 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 (θ) : Rd 7→ R,
1 2 ∇W (θ)⊤C (θ)1/2∇W (θ)−∇L (θ)⊤ ∇W (θ) = 0,W (0) = 0
has a unique solution.

heading: 4.2 MAIN RESULTS
text: In preparation, we start with a 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, as shown in Hu et al. (2019) Theorem 3.4, V (θ) is calculated as a solution of the following Hamilton-Jacobi equation,
1 2 ∇V (θ)⊤C (θ)1/2∇V (θ)−∇L (θ)⊤ ∇V (θ) = 0. (4)
Second, if ηB is sufficiently small, the mean exit time can be expressed using V (θ) as E [τ ] = exp [ B
η V0
] , (5)
where V0 := minθ′∈∂D V (θ′). 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 A and B for completeness.
The followings are our main results. We start with the mean exit time of Continuous SGD. Let E[τSGD] be the mean exit time of the continuous SGD, and let E[τisoSGD] be the mean exit time of an isotropic continuous SGD whose C(θ) is set to I . Theorem 1 (Continuous SGD). Suppose that Assumption 1, 2, 3, 4, 5, and 6 hold. Then, for sufficiently small ηB ,
E[τisoSGD] = exp [ 2 B η r2λ ] , E[τSGD] = exp [ 2 B η r2λ 1 2 ] .
This result gives an 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.e. λ. This implies that sharper minima generally slow down the escaping, which is seemingly opposite to the implication of the existing literature (Jastrzębski et al., 2017; Xie et al., 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 ∆L. Second, our result endorses the fact that SGD’s anisotropic noise exponentially accelerates the escaping (Xie et al., 2020), because the result shows that the mean exit time of SGD is smaller than that of isotropic SGD by exp [λ 1 2 ].
Our theory can be extended to the discrete case. By E[νSGD], we denote the discrete mean exit time of the discrete SGD, and by E[νisoSGD] we denote the one of an isotropic version of the discrete SGD, i.e. with C(θ) being I . The escaping problem of a discrete SGD, the discrete mean exit time, is formulated as a special case of Gobet & Menozzi (2010). By substituting g(·) = 0, f(·) = 1, and k(·) = 0 in Theorem 17 in Gobet & Menozzi (2010), we can obtain the following simplified statement.
max {E[νisoSGD]− E[τisoSGD],E[νSGD]− E[τSGD]} = O( √ η).
which immediately prove the following theorem:
Theorem 2 (Discrete SGD). Given, Assumption 1, 2, 3, 4, 5, and 6, for sufficiently small ηB ,
E[νisoSGD] = exp [ 2 B η r2λ ] +O (√η) , E[νSGD] = exp [ 2 B η r2λ 1 2 ] +O (√η)
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 a continuous SGD model (3) for escape analysis.

heading: 4.3 PROOF FOR THEOREM 1
text: We describe a proof of Theorem 3. We begin with the isotropic case and then investigate the nonisotropic case.
Isotropic case E[τisoSGD]: We substitute I to C(θ). By the Jacobi equation (4) which is formally given by Theorem 4 in Appendix A, we have the following form for θ ∈ D:
1 2 ∇V (θ)⊤∇V (θ)−∇L (θ)⊤ ∇V (θ) = 0. (6)
Given V (θ∗) = 0 by definition of V (θ), V (θ) = 2L(θ) is the unique solution of (6) by Assumption 5 and 6. Therefore, we have
V0 = min x∈∂D 2L(θ) = min x∈∂D
2θ⊤H∗θ = 2r2λ.
The second equality follows Assumption 1 and 5. Combined with the fact (5), which is formally shown in Theorem 5 in Appendix B, we obtain the statement of Theorem 1 in the isotropic case.
Anisotropic case E[τSGD]: Similar to the isotropic case, the equation (4) (or Theorem 4) gives
1 2 ∇V (θ)⊤C(θ) 1 2∇V (θ)−∇L (θ)⊤ ∇V (θ) = 0. (7)
∇V (θ) = 2C(θ)− 12∇L(θ) satisfies (7) and by Assumption 1 and 2 , 2C(θ)− 12∇L(θ) can simply written as
2C(θ)− 1 2∇L(θ) = 2H∗− 12∇ ( θ⊤H∗θ ) = 2H∗− 1 2 2H∗θ = 4H∗ 1 2 θ.
Given V (θ∗) = 0 by definition of V (θ), V (θ) = θ⊤H∗ 1 2 θ is the unique solution of (7) by Assumption 5 and 6. Then, we obtain
V0 = 2r 2λmin(H ∗ 12 ), (8)
Combined with (5), or Theorem 5 in Appendix B, we finish the proof of Theorem 1.

heading: 5 FURTHER INVESTIGATION ON COVARIANCE MATRIX
text: We investigate a variation of Assumption 2 on the covariance matrix. Although Assumption 2 is commonly used (Jastrzębski et al., 2017; Xie et al., 2020), relaxing this is important for a flexible modeling of SGD.
Assumption 7 (Variant of Assumption 2). H∗−1/2 is a positive matrix and there exist constants 0 < c1 ≤ c2 < ∞ such that for θ ∈ D, C(θ) = H∗G holds with a positive invertible matrix G as 0 < c1 ≤ λmin(G) ≤ λmax(G) ≤ c2.
Under this different setup, we obtain the following results. Theorem 3. Suppose that Assumption 1, 3, 4, 5, 6, and 7 hold. Then, for sufficiently small ηB ,
E[τisoSGD] = exp [ 2Bη r 2λ ]
exp [ 2Bη r 2 1√ c2 λ 1 2 ] ≤ E[τSGD] ≤ exp [ 2Bη r 2 1√ c1 λ 1 2 ] It suggests that replacing Assumption 2 by Assumption 7 does not affect the isotropic case, but has a constant effect in the anisotropic case.
Proof for Theorem 3. The result of E[τisoSGD] is obtained in the same way as Theorem 1. For the proof of E[τSGD], the following lemmas are useful, whose proofs are provided in Appendix C.
Lemma 3. For positive invertible matrices A and B, the following inequality holds,
λmin(A −1B−1) ≤ λmax(A−1)λmin(B−1)
Lemma 4. For invertible matrices A and B, the following inequality holds
λmin(AB) ≥ λmin(A)λmin(B)
Similar to the proof of Theorem 1, we obtain ∇V (θ) = 2C(θ)− 12∇L(θ). Then, ∇V (θ) is simply written as
∇V (θ) = 2C(θ)− 12∇L(θ) = 2C(θ)− 12∇ ( θ⊤H∗θ ) = 2C(θ)− 1 2 2H∗θ
= 2(H∗G)− 1 2 2H∗ = 4G− 1 2H∗− 1 2H∗θ = 4G− 1 2H∗ 1 2 θ.
The second equation follows Assumption 1 and 5, and the fourth equation follows Assumption 7. Given that V (θ∗) = 0, we obtain V (θ) = θ⊤G− 1 2H∗ 1 2 θ for θ ∈ D. Then, we rewrite V0 is as
V0 = 2r 2λmin(G − 12H∗ 1 2 ), (9)
By Lemma 3, we develop an upper bound on λmin(G−1/2H∗1/2) as λmin(G−1/2H∗1/2) ≤ λmax(G −1/2)λmin(H ∗1/2) ≤ c−1/21 λ1/2. Similarly, Lemma 4 gives us the following lower bound λmin(G −1/2H∗1/2) ≥ λmin(G−1/2)λmin(H∗1/2) ≥ c−1/22 λ1/2. We substitute the two inequalities into the solution (9), then obtain the following form of V0:
2r2 1
√ c2 λ
1 2 ≤ V0 ≤ 2r2 1 √ c1 λ 1 2
Combined with (5), or Theorem 5 in Appendix B, we finish the proof of Theorem 3.

heading: 6 EXPERIMENT
text: We conduct an experiment to validate our result of discrete setup (Theorem 2), using a neural network and real-world datasets. We use a multi-layer perception and the AVILA dataset (De Stefano et al., 2011) to observe that the discrete mean exit time of SGD has exponential dependence on eigenvalue λ, radius r and a ratio of the learning rate and the batch size η/B.
In order for our essential assumptions to hold, we use the mean square loss with ℓ2 regularizer for L(θ) (Assumption 1) and train the model with the gradient descent for a sufficiently long time to
obtain θ0 near θ∗. We set the r-neighborhood of θ0 as D (Assumption 3 and 4). To measure the discrete mean exit time, we repeatedly execute a vanilla SGD from θ0 for 1000 times and take an average number of steps at which SGD exit from D (i.e. when the distance from θ0 becomes farther than r).
To control λ, we follow the approach of Xie et al. (2020). We obtain sharper minima by mapping the loss function L to Lα such that Lα(θ) := L( √ αθ) (α > 0) and setting θ0 := θ0/α. Since this mapping coverts λ to αλ with other properties remaining the same, we use α as a surrogate of λ.
We show the results in Figure 2. As Theorem 2 suggests, the noise magnitude √ η/B exponentially accelerates the escaping under our experiment setup, and eigen value and radius have the effect of exponentially slowing down the escaping

heading: 7 RELATED WORKS
text: 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 a topic of interest. The argument that the flatness of loss surfaces around local minima improves generalization was first studied by Hochreiter & Schmidhuber (1995; 1997), and the observation has recently reconfirmed in deep neural networks by Keskar et al. (2016). Sagun et al. (2017) empirically examined the flatness of loss surfaces. The theoretical advantage of the flatness was criticized by Dinh et al. (2017) in terms of scale-sensitivity of flatness, but Tsuzuku et al. (2020) and Rangamani et al. (2019) tackled the criticism by developing scale invariant flatness measures. An effect of the shape of loss surfaces on SGD was investigated in Wu et al. (2017); Ge et al. (2018), and Chaudhari et al. (2019); Foret et al. (2020) developed a variant of SGD which made use of this fact. In addition to the flatness, He et al. (2019b) proposed a new notion of asymmetry of loss surfaces, and Draxler et al. (2018); Garipov et al. (2018) studied how several local minima in a loss surface are connected. Li et al. (2018) developed a random dimensional reduction method to visualize loss surfaces on high dimensional spaces.
Exit/Stability of SGD: How SGD behaves in neighborhoods of local minima in loss surfaces is investigated from two aspects: stability and escape efficiency. For stability, a way in which SGD finds local minima and stabilizes was analyzed by Wu et al. (2018); Kleinberg et al. (2018); Achille et al. (2019); Li et al. (2017). Smith & Le (2017) used Bayesian ideas to analyze the stability. For exiting aspects, Jastrzębski et al. (2017) investigated an effect of a Hesse matrix of local minima on the ease of escaping ineffective local minima, and Xie et al. (2020) elaborated this effect via quantitative analysis. Zhu et al. (2019) showed that anisotropic structure of gradient noise by SGD is useful in escaping inefficient local minima, and Nguyen et al. (2019) studied an effect of nonGaussianity 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 a batch size. An effect of large batch sizes on the reduction of gradient noise is investigated in Hoffer et al. (2017); Smith et al. (2018); Masters & Luschi (2018). Another area of interest is shape of a gradient noise distribution. Zhu et al. (2019); Hu et al. (2017); Daneshmand et al. (2018) investigated the anisotropic nature of gradient noise and its advantage. Simsekli et al. (2019) discussed the fact
that a gradient noise distribution has a heavier tail than Gaussian distributions. Nguyen et al. (2019); Şimşekli et al. (2019) showed benefits of these heavy tails for SGD. Panigrahi et al. (2019) rigorously examined gradient noise in deep learning and how close it is to a Gaussian. Xie et al. (2020) studied a situation where the distribution is Gaussian, and then analyzes the behavior of SGD in a theoretical way.

heading: 8 CONCLUSION
text: In this paper, we develop a 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. In our main result, our theory explicitly describes how the escape of SGD is affected by a batch-size, a learning rate, and radius of regions, and sharpness (Theorem 1). Furthermore, due to its flexibility, our theory allows the extended analyses, such as SGD’s escape under even weaker assumption on covariance matrix (Theorem 3) and the escape problem of a discrete SGD (Theorem 2). We believe our theory provides a solid insight for SGD dynamics and also flexible theory for further studies.

heading: A JACOBI EQUATION OF QUASI-POTENTIAL
text: Theorem 4. For all θ ∈ D, V (θ) satisfies the following Jacobi equation, 1
2 ∇V (θ)⊤C (θ)1/2∇V (θ)−∇L (θ)⊤ ∇V (θ) = 0
Proof of Theorem 4. For u, v ∈ Rd, we introduce an inner product and a norm regarding a point θ ∈ D as 〈u, v〉θ := u⊤C (θ)−1/2 v and ‖u‖θ := √ 〈u, u〉θ. With these definitions, the S0T (φ) is written as follows:
S0T (φ) = 1
2 ∫ T 0 ‖φ̇t +∇L (φt)‖2φt dt. (10)
Note that φt ∈ D holds for any t ∈ [0, T ] by the definition of trajectories. We rewrite the integrand of (10) as follows:
‖φ̇t +∇L (φt)‖2φt = ‖φ̇t‖2φt + ‖∇L (φt)‖ 2 φt + 2 〈φ̇t,∇L (φt)〉φt
= ( ‖φ̇t‖φt − ‖∇L (φt)‖φt )2 + 2 ‖φ̇t‖φt ‖∇L (φt)‖φt + 2 〈φ̇t,∇L (φt)〉φt
≥ 2 ‖φ̇t‖φt ‖∇L (φt)‖φt + 2 〈φ̇t,∇L (φt)〉φt . (11)
We develop a parameterization for the term in (11). For a trajectory φ, we select an bijective function f : [0, 1] → [0, T ] as satisfying the follows: for each t ∈ [0, T ] and t∗ ∈ [0, 1] as t = f(t∗), a parameterized trajectory φ∗t∗ := φf(t∗) satisfies
‖φ̇∗t∗‖φ∗ t∗ = ‖∇L(φ̇∗t∗)‖φ∗t∗ . (12)
This parameterization reduces the quasi-potential to the minimum of the following quantity: (S0T (φ) ≥ S0f(T )(φ∗) =) ∫ f(T ) 0 ‖φ̇∗t∗‖φ∗ t∗ ‖∇L (φ∗t∗)‖φ∗ t∗ + 〈φ̇∗t∗ ,∇L (φ∗t∗)〉φ∗ t∗ dt∗ (13)
subject to the constraint (12). Since the integrand of (13) includes the first order derivative regarding t∗, (13) holds over different parameterizations f . For convenience, we use another bijective parameterization function g : [0, R] → [0, 1] as t∗ = g(r) with R > 0 and r ∈ [0, R] such that φ̂r := φ∗g(r) satisfies
‖ ˙̂φr‖φ̂r = 1. (14)
Then, the quasi-potential is reduced to the following formula, 1
V (θ) = inf r∈[0,R]:∥ ˙̂φr∥φ̂r=1 ∫ R 0 ( ‖ ˙̂φr‖φ̂r ‖∇L (φ̂r)‖φ̂r + ⟨ ˙̂φr,∇L (φ̂r) ⟩ φ̂r ) dr, (15)
where φ̂R = θ. By the Bellman equation-type optimality, we expand the right hand side of (15) into the following form:
V (θ) = inf r∈[0,R]:∥ ˙̂φr∥φ̂r=1 (∫ R R−δ ( ‖ ˙̂φr‖φ̂r ‖∇L (φ̂r)‖φ̂r + ⟨ ˙̂φr,∇L (φ̂r) ⟩ φ̂r ) dr + V (φ̂R−δ) ) ,
(16)
with a width value δ > 0. The Taylor expansion around r = R gives∫ R R−δ ( ‖ ˙̂φr‖φ̂r ‖∇L (φ̂r)‖φ̂r + ⟨ ˙̂φr,∇L (φ̂r) ⟩ φ̂r ) dr + V (φ̂R−δ)
= δ ( ‖∇L(φ̂R)‖φ̂R + ⟨ ∇L(φ̂R), ˙̂φR ⟩ φ̂R − ˙̂φ⊤R∇V (φ̂R) ) + V (φ̂R) +O ( δ2 )
Taking δ → 0 and noticing φ̂R = θ, (16) can be simplified to the following equation:
0 = inf r∈[0,R]:∥ ˙̂φr∥φ̂r=1
( ‖∇L(θ)‖θ + ⟨ ∇L(x)⊤, ˙̂φR ⟩ θ − ˙̂φR∇V (θ) ) (17)
It remains to select φ̂ which solves the minimization problem (17). Since the following equality holds, ⟨
∇L(θ)⊤, ˙̂φR ⟩ θ − ˙̂φR∇V (θ) = ⟨ ∇L(θ)⊤ −∇V (θ)⊤ C (θ)−1/2 , ˙̂φR ⟩ θ , (18)
it is easy to see that a trajectory φ̂∗ such that
˙̂φ∗R = − ∇L(x)⊤ −∇V (θ)C (θ)1/2
‖∇L(θ)⊤ −∇V (θ)C (θ)1/2 ‖θ minimizes (18). With this φ̂∗, (17) simplifies to
‖∇L(θ)‖θ = ‖∇L(θ)⊤ −∇V (θ)C (θ)1/2 ‖θ. Taking the square of both sides, we get the statement.

heading: B THEOREM ON EXIT TIME
text: In this section, we develop the following fundamental theorem on the notion of exit time. For simplicity, we use ε to denote √ η/B.
Theorem 5. If ε is sufficiently small, E [τ ] = exp [ ε−2V0 ] holds, where V0 := minθ′∈∂D V (θ′)
1One might think that if we parametrize as above (14), the equality condition for (11) is violated. Indeed S0T (φ̂) ̸= ∫ T 0 ∥φ̇t∥φ̂t ∥∇L (φ̂t)∥φ̂t + ⟨φ̇t,∇L (φ̂t)⟩φ̂t dt
for φ̂. However, φ̂ is introduced just for the simple calculation of S0T (φ∗). Although φ̂ frequently appears in the proof, our attention is still on φ∗ and S0T (φ∗), not on S0T (φ̂).
To prove this result, we provide the proof for an upper bound (Lemma 6) and a lower bound (Lemma 7). Throughout the proofs, we use C0T,θ0 , Pθ0 , instead of C0T or P, to clearly indicate which trajectory we are referring to.
We introduce several notions. For δ > 0 and θ ∈ Rd, let Bδ(θ) denote an δ-neighbourhood of θ, that is, Bδ(θ) := {θ′ ∈ Rd | ‖θ′ − θ‖ ≤ δ}. Further, for a set Θ ⊂ Rd, Bδ(Θ) := ∪θ∈ΘBδ(θ). The following lemma provides preliminary facts for proofs. Lemma 5. For any c > 0, there exist µ1, µ2, T1, T2 > 0 such that the followings hold:
1. ∀θ ∈ D, there exists a trajectory φ1 such that φ10 = θ, φ1T ∈ Bµ1/2(θ∗), 0 < T ≤ T1 and S0T (φ 1) = 0.
2. ∀θ ∈ Bµ1(θ∗), there exists a trajectory φ2 such that φ20 = θ, φ2T ∈ ∂Bµ2(D), 0 < T ≤ T2 and S0T (φ2) < V0 + c2 .
The illustration can be found in Fig. 3.
Proof of Lemma 5. The first statement immediately holds by the fact that D is attracted to a asymptotically stable equilibrium position θ∗ (Assumption 3 and 4).
For the second statement, since V0 := minθ′∈∂D V (θ′), there exists a trajectory φa such that φa0 = θ∗, φaTa ∈ ∂D and S0Ta (φ
a) = V0, where Ta is finite by Lemma 2.2 (a) in Freidlin & Wentzell (2012). We cut off the first portion of φa up until the first intersecting point with Bµ1(θ∗) and define it as φb. This means φb0 ∈ Bµ1(θ∗), φbTb ∈ ∂D and S0Tb ( φb ) < V0 hold. By Lemma 2.3 in Freidlin & Wentzell (2012), there exists a trajectory from φbTb to a point θµ2 in ∂Bµ2(D) such that the steepness is less than K|θµ2 − φbTb | with a constant K > 0. Then, if we take a small enough µ2, we can obtain φc such φc0 = φ b Tb , φcTc ∈ ∂Bµ2(D) and S0Tc (φ c) < c2 . By connecting φ
b and φc, we obtain an appropriate φ2.
Lemma 6. If ε > 0 is sufficiently small, E [τ ] = O ( exp [ ε−2V0 ] ) holds, where V0 := minθ′∈∂D V (θ′).
Proof of Lemma 6. We show that for any constant c > 0, there exists a small ε0 such that ∀ε ≤ ε0 such that E [τ ] ≤ exp [ ε−2(V0 + c) ] . To the aim, we split the dynamical system (3) of our interest into the first half and the second half, {θ1t }t and {θ2t }t. {θ1t }t starts with θ10 = θ0 ∈ D and terminates when it first reaches Bµ1/2(θ∗). We define the terminating time of {θ1t }t as τ1 := min{t > 0 : θ1t ∈ Bµ1/2(θ∗)}. On the other hand, {θ2t }t starts with θ20 = θτ1 ∈ Bµ1/2(θ∗) and terminates when it first
reaches ∂D. We define the terminating time of {θ2t }t as τ2 := min{t > 0 : θ1t ∈ ∂D}. Clearly, the exit time τ = τ1 + τ2.
Regarding τ1 and τ2, we show the following two independent facts with sufficiently small ε > 0.
Fact 1 : τ1 is no more than T1 with probability at least 1/2. Fact 2 : τ2 is no more than T2 with probability at least exp { −ε−2 (V0 + c) } .
Fact 1: Given the trajectory φ1 provided by Lemma 5, Lemma 1 gives us that if ε < εstp1(φ1, µ1/2, 1), the following inequality holds
Pθ10 { φ′ ∈ C0T1,θ10 (R d) | ρ (φ′, φ1) < µ1/2 } ≥ exp { −ε−2 } .
Therefore, if we take ε < min{ √ 1/ln 2, εstp1(φ1, µ1/2, 1)}, we have
Pθ10 { φ′ ∈ C0T1,θ10 (R d) | ρ (φ′, φ1) < µ1/2 } ≥ 1
2
Since the event of {φ′ ∈ C0T1,θ10 (R d) | ρ (φ′, φ1) < µ1/2} means that {θ1t }t reaches Bµ1(θ∗) in no later than T1, we obtain the following which provides Fact 1.
Pθ10 {τ1 < T1} ≥ 1 2 . (19)
Fact 2: Given the trajectory φ2 provided by Lemma 5, Lemma 1 tells us that if ε < εstp1(φ2, µ2, c/2), the following inequality holds
Pθ20 { φ′ ∈ C0T2,θ20 (R d) | ρ (φ′, φ2) < µ2 } ≥ exp { −ε−2 ( S0T2 (φ2) + c
2
)} .
{φ′ ∈ C0T2,θ20 (R d) | ρ (φ′, φ2) < µ2} is the event that {θ2t }t goes out ofD in no more than the time T2. Also, we know that S0T2 (φ2) < V0 + c 2 by Lemma 5. Hence, we can conclude the following for Fact 2:
Pθ20 {τ2 < T2} ≥ exp { −ε−2 (V0 + c) } . (20)
Combining (19) and (20), we can obtain
Pθ0 {τ < T1 + T2} ≥ 1
2 exp
{ −ε−2 (V0 + c) } . (21)
Since this is a simple exponential distribution, we can obtain the following expectation: E [τ ] ≤ 2 (T1 + T2) exp { ε−2 (V0 + c) } By setting
ε < 1√
ln 2(T1 + T2) min
{√ 1
ln 2 , εstp1(φ1, µ1/2, 1), εstp1(φ2, µ2, c/2)
} ,
we can get
E [τ ] ≤ exp { ε−2 (V0 + c) } .
Then, we obtain the statement.
Next, we develop the lower bound on the exit time. Lemma 7. If ε > 0 is sufficiently small,
E [τ ] = Ω ( exp [ ε−2V0 ] ) holds, where V0 := minθ′∈∂D V (θ′).
Proof of Lemma 7. We show for any positive constant c > 0, there exists a small ε0 such that ∀ε ≤ ε0, E [τ ] ≥ exp [ ε−2(V0 − c) ] holds.
We consider a specific case where the initial value of (3) is in ∂Bµ1/2(θ∗), which can be trivially extended to general cases. Consider a Markov chain Zk (k ∈ N) as a discretization of θt as t = τk with a k-th time grid τk. It is formally defined as follows:
1. τ0 = 0,
2. σk = inf {t > τk : θt ∈ ∂Bµ1(θ∗)}, 3. τk = inf { t > σk−1 : θt ∈ ∂Bµ1/2(θ∗) ∪ ∂D } ,
4. Zk = θτk .
By introducing Zk, we can reduce the continuous process {θt}t to a discrete Markov chain transiting between ∂Bµ1/2 (θ∗) and ∂D. The illustration can be found in Fig. 4.
Let κ := inf{k | Zk ∈ ∂D}. Then, we have τ = τn and
E [τ ] = ∞∑ k=0 ( Pθ0 {κ ≥ k} − Pθ0 {κ ≥ k + 1} ) τk = ∞∑ k=1 Pθ0 {κ ≥ n} (τk − τk−1) .
This can be further evaluated as
E [τ ] > ∞∑ k=1 Pθ0 {κ ≥ k} (τk − σk−1) > ∞∑ k=1 Pθ0 {κ ≥ n} ( inf θ0∈∂Bµ1 (θ∗) E[τ1] ) ,
which follows τk−1 < σk−1. Since Bµ1/2(θ∗) is a strict subset of Bµ1(θ∗), and Bµ1(θ∗) is a strict subset of D, it takes a positive amount of time to transit from ∂Bµ1(θ∗) to either ∂Bµ1/2(θ∗) or ∂D, and there exists a positive lower bound t1 for infθ0∈Bµ1 (θ∗) E[τ1] that is independent of ε. Thus we get
E [τ ] > t1 ∞∑ k=1 Pθ0 {κ ≥ k} .
By Lemma 8, we immediately get Pθ0{κ > k} ≥ [1− exp{−ε−2(V0 − c)}]k−1, hence we have
E [τ ] > t1 ∞∑ k=1 [ 1− exp { −ε−2 (V0 − c) }]k−1 = t1 exp { ε−2 (V0 − c) } .
This implies E[τ ] ≥ exp{ε−2(V0 − c)} holds if ε is small enough.
Lemma 8. We obtain P(Zk+1 ∈ ∂D | Zk ∈ Bµ1/2(θ ∗)) ≤ exp { −ε−2 (V0 − c) } .
Proof of Lemma 8. First, we decompose P(Zk+1 ∈ ∂D | Zk ∈ ∂Bµ1/2(θ∗)) into two parts in the following way:
Pθ0(Zk+1 ∈ ∂D | Zk ∈ ∂Bµ1/2(θ ∗))
≤ max θ′0∈∂Bµ1/2(θ ∗) Pθ′0 {τ1 = τ}
= max θ′0∈∂Bµ1/2(θ ∗)
[ Pθ′0 {τ = τ1 < T}+ Pθ′0 {τ = τ1 ≥ T} ] (22) This holds for arbitrary T , so we pick T = T ′ large enough so that this inequality holds for the first term:
Pθ′0 {τ = τ1 ≥ T ′} ≤ 1
2 exp
{ −ε−2 (V0 − c) } (23)
The existence of such T ′ is guaranteed by the fact that V0 is finite and the following lemma.
Lemma 9 (Lemma 2.2 (b) in Freidlin & Wentzell (2012)). For any α > 0, there exists positive constants c and T0, such that for all sufficiently small ε > 0 and any θ0 ∈ D∪ ∂D\Bα(θ∗) we have the inequality
Pθ0 {ζα > T} ≤ exp { −ε−2c (T − T0) } ,
where ζα = inf {t : θt /∈ D\Bα(θ∗)}.
Given a constant T ′, we consider bounding Pθ′0 {τ = τ1 < T ′}. Consider the following set of trajectories:
Φ(V0 − c/2) := {φ : φ0 = θ′0, S0T (φ) ≤ V0 − c/2}. Since it takes at least V0 to reach ∂D from θ∗, the following inequality holds:
Pθ′0 {τ = τ1 < T ′} ≤ Pθ′0 {φy /∈ Φ(V0 − c/2)} .
Also, Lemma 2 implies, for all ε ≤ εstp2(V0 − c/2, δ, c/2) Pφ′ { φ′ ∈ C0T,θ′0(R d) | ρ ( (φ′ − Φ(V0 − c/2) ) ≥ δ } ≤ exp{−ε−2((V0 − c/2)− c/2)}
= exp{−ε−2(V0 − c)} Since δ can be arbitrarily small, the event of {φy /∈ Φ(V0 − c/2)} is equal to the event of {φ′ ∈ C0T,θ′0(R d) | ρ((φ′ − Φ(V0 − c/2)) ≥ δ}. Hence, we obtain
Pθ′0 {τ = τ1 < T} < exp{−ε −2(V0 − c)}. (24)
If we set ε ≤ 1√ ln 2 εstp2(V0 − c/2, δ, c/2), we conclude
Pθ′0 {τ = τ1 < T} < 1 2 exp{−ε−2(V0 − c)}. (25)
Combining (22), (23), and (25), we prove the statement.

heading: C PROOFS FOR LEMMA 3 AND LEMMA 4
text: Proof of Lemma 3. We introduce several definitions only for this proof. Supposing that we have a vector x = (x1, . . . , xn) ∈ Rn, x↓ and x↑ denote vectors whose coordinates are obtained by rearranging the numbers xj in decreasing order and in increasing order respectively, that is, x↓ = (x↓1, . . . , x ↓ n) and x ↑ = (x↑1, . . . , x ↑ n), where x ↓ 1 ≥ · · · ≥ x↓n and x ↑ 1 ≤ · · · ≤ x↑n. Also, given x, y ∈ Rn, we denote x ≺ y, if n∑
j=1
x↓j = n∑ j=1 y↓j , and k∑ j=1 x↓j ≤ k∑ j=1 y↓j for 1 ≤ ∀k ≤ n.
For an n × n matrix A, λ(A) = (λ1(A), λ2(A), ..., λn(A)). Also, we define its elementwise logarithm log λ(A) = (log λ1(A), log λ2(A), ..., log λn(A)).
Corollary III.4.6 in (Bhatia, 1997) claims that given two positive matrices A and B, we have
log λ↑(A) + log λ↓(B) ≺ log λ(AB) ≺ log λ↓(A) + log λ↓(B)
Following the definition of ≺, the left part, log λ↑(A)+log λ↓(B) ≺ log λ(AB), can be equivalently restated as
k∑ j=1 { log λ↑(A) + log λ↓(B) }↓ j ≤ k∑ j=1 {log λ(AB)}↓j for 1 ≤ ∀k ≤ n
For the case k = 1, we have{ log λ↑(A) + log λ↓(B) }↓ 1 ≤ {log λ(AB)}↓1
⇐⇒ max 1≤i≤n {log λn−i+1(A) + log λi(B)} ≤ log λmax(AB)
Since max1≤i≤n {log λn−i+1(A) + log λi(B)} ≥ log λn(A) + log λ1(B) = log λmin(A) + log λmax(B) holds, we have log λmin(A) + log λmax(B) ≤ log λmax(AB), or equivalently
λmin(A)λmax(B) ≤ λmax(AB).
Since λmax(A) = 1/λmin(A−1) , we have
1
λmax(A−1)
1 λmin(B−1) ≤ 1 λmin((AB)−1)
⇐⇒ λmin((AB)−1) ≤ λmax(A−1)λmin(B−1).
Since commuted matrices share eigenvalues, λmin((AB)−1) = λmin(B−1A−1) = λmin(A−1B−1), we have
λmin(A −1B−1) ≤ λmax(A−1)λmin(B−1).
Proof of Lemma 4. λmax(A) is equal to the spectral norm of A. By the sub-multiplicative property of spectral norm, we obtain
λmax(A)λmax(B) ≥ λmax(AB),
Therefore, since λmax(A) = 1/λmin(A−1),
λmax(A −1)λmax(B −1) ≥ λmax(A−1B−1) ⇐⇒ λmax(A−1)λmax(B−1) ≥ λmax((AB)−1)
⇐⇒ 1 λmin(A)
1 λmin(B) ≥ 1 λmin(AB)
⇐⇒ λmin(AB) ≥ λmin(A)λmin(B).
Then, we obtain the statement.

Review summaries:
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.