--- abstract: 'We consider in this work small random perturbations (of multiplicative noise type) of the gradient flow. We rigorously prove that under mild conditions, when the potential function is a Morse function with additional strong saddle condition, the perturbed gradient flow converges to the neighborhood of local minimizers in $O(\ln ({\varepsilon}^{-1}))$ time on the average, where ${\varepsilon}$ is the scale of the random perturbation. Under a change of time scale, this indicates that for the diffusion process that approximates the stochastic gradient method, it takes (up to logarithmic factor) only a linear time of inverse stepsize to evade from all saddle points and hence it implies a fast convergence of its discrete–time counterpart.' author: - 'Wenqing Hu [^1] , Chris Junchi Li [^2] .' title: 'On the fast convergence of random perturbations of the gradient flow.' --- *Keywords*: random perturbations of dynamical systems, saddle point, exit problem, stochastic gradient descent, diffusion approximation. *2010 Mathematics Subject Classification Numbers*: 37D05, 60J60, 68Q87, 68W20. Introduction. ============= Setup and the main results. --------------------------- Let $F:{\mathbb R}^n\to {\mathbb R}$ be a function in class ${\mathbf{C}}^{(3)}$ with bounded first and second derivatives and let $\nabla F$ be its gradient vector field on ${\mathbb R}^n$. In this paper we consider small random perturbations (of multiplicative noise type) of the gradient flow associated with the function $F$. Let $Y^{\varepsilon}_t$ be defined as the solution to the stochastic differential equation (SDE) with small parameter ${\varepsilon}>0$: $$\label{Eq:SGDPerturbation} dY^{\varepsilon}_t = - {\nabla}F(Y^{\varepsilon}_t)dt + {\varepsilon}{\sigma}(Y^{\varepsilon}_t)dW_t \ , \ Y_0^{\varepsilon}=x \ .$$ Here ${\sigma}(\bullet)$ is an $n\times n$ matrix–valued function with bounded coefficients in class ${\mathbf{C}}^{(2)}$ and bounded first derivatives of these coefficients, such that the diffusion matrix $a(x)={\sigma}(x){\sigma}^T(x)$ is uniformly positive definite. In the case where $\varepsilon = 0$, the SDE reduces to the gradient flow ODE: $$\label{Eq:GradientFlow} \dfrac{d}{dt}S^t x=-{\nabla}F(S^t x) \ , \ S^0x=x \ .$$ It is well–known, see e.g., Sec. 10.2 of @[BORKAR], that the equilibria of the gradient flow differential equation are the critical points of $F(\bullet)$ (i.e., the gradient vector evaluated at the critical point is 0). Classical results state that under mild regularity conditions for $F(\bullet)$, every solution $S^t x$ of the gradient flow on ${\mathbb R}^n$ exists for all $t \ge 0$, and $S^t x$ converges to a connected component of the set of critical points of $F$ as $t \to \infty$. Additionally, following the trajectories of gradient flow the function value $F$ is nonincreasing, but they may be trapped in the neighborhood of a saddle point for a substantial amount of time. To see the first conclusion, note that for any solution of ODE, $F(\bullet)$ itself serves as a Lyapunov function: $$\frac{d F(S^t x)}{dt} = \nabla F(S^t x)\cdot \frac{d S^t x}{dt} = -| \nabla F(S^t x)|^2 \le 0 \ ,$$ and hence $F (S^t x)$ is a non–increasing function. Our goal in this paper is to use tools from classical stochastic analysis to prove the following result: adding a small amount of random perturbation (multiplicative noise type) enables fast evasion from saddle points and lands the process in a neighborhood of the set of local minimum points. Let $x^*$ be a local minimum point of $F(\bullet)$ in the sense that for some open neighborhood $U(x^*)$ of $x^*$: $$x^* = \arg\min{\limits}_{x\in U(x^*)} F(x) .$$ Then given any positive constant $e>0$, we aim to characterize the distribution of the stopping time $T^{\varepsilon}_x$ defined as $$\label{Eq:HittingTimeSGDPerturbationManySaddle} T^{\varepsilon}_x \equiv \inf\{t\geq 0: Y^{\varepsilon}_0=x \ , \ F(Y^{\varepsilon}_t ) \leq F(x^*) + e\}$$ as ${\varepsilon}\to 0^+$. Equivalently, when starting from $Y^{\varepsilon}_0=x$, $T^{\varepsilon}_x$ is the first time the perturbed gradient flow dynamics $Y^{\varepsilon}_t$ leads to at least the amount of $F(x) - F(x^*) - e$ decay in function value of $F$. In a hand–waiving manner, our main result (Theorem \[Thm:MajorResultSGDPerturbationConvergenceTime\]) can be formulated as follows. #### Main Result. *Let the function $F: {\mathbb R}^n{\rightarrow}{\mathbb R}$ be a Morse function satisfying the "strong saddle condition" that will be specified in Section 1.2. When ${\varepsilon}\to 0^+$, ${\mathbf E}T^{\varepsilon}_x$ is asymptotically bounded by $C \ln ({\varepsilon}^{-1})$, where $C>0$ is some constant that is determined by the landscape of the function $F$.* This result is significant in the sense that, when there exist many saddle points on the landscape of the function $F(\bullet)$ the ODE risks being trapped at around saddle points. Nevertheless as long as the function satisfy some additional landscape property, by adding small random perturbation ${\varepsilon}\sigma(Y^{\varepsilon}_t) dW_t$ the random dynamics pays a merely $\ln({\varepsilon}^{-1})$ factor of time (multiplied by a constant) to enter into a neighborhood of the set of local minimum points. Strong saddle condition. ------------------------ To detail the landscape condition of $F(\bullet)$, we first remind the readers of the definition of Morse function, as follows. \[Def:Morse\] A function $F:{\mathbb R}^n\to {\mathbb R}$ is a <span>*Morse function*</span> if it is smooth and has all its critical points being <span>*non–degenerate*</span>, i.e., for each critical point $x$, all eigenvalues of the Hessian matrix ${\nabla}^2 F(x)$ are nonzero. Morse functions admit a local quadratic re–parametrization at each critical point, which is the content of the so–called <span>*Morse Lemma*</span> @[Milnor1963] [Lemma 2.2]. To ensure that the perturbed gradient flow escapes from saddle points, we introduce the following "strict saddle property" (compare with @[GeEtAl1503], @[sun2015nonconvex]) as follows. \[strict saddle property\]\[Def:StrictSaddleProperty\] Given fixed ${\gamma}_1>0$ and ${\gamma}_2>0$, we say a Morse function $F$ defined on ${\mathbb R}^n$ satisfies the "strict saddle property" if each point $x\in {\mathbb R}^n$ belongs to one of the following: (i) $|{\nabla}F(x)|\geq {\gamma}_2 >0$ ; (ii) $|{\nabla}F(x)|< {\gamma}_2$ and ${\lambda}_{\min}({\nabla}^2 F(x))\leq -{\gamma}_1 <0$ ; (iii) $|{\nabla}F(x)|< {\gamma}_2$ and ${\lambda}_{\min}({\nabla}^2 F(x))\geq {\gamma}_1>0$. We will call a saddle point $x\in {\mathbb R}^n$ of the function $F$ a "strict saddle" if Definition \[Def:StrictSaddleProperty\] (ii) holds at $x$. Thus a Morse function $F$ that satisfies the strict saddle property has all its saddle points being strict saddle points. For the sake of proof, it is natural to assume that all eigenvalues of the Hessian ${\nabla}^2 F$ at critical points are uniformly bounded away from 0. This leads to our new notion of "strong saddle property" as follows. \[strong saddle property\]\[Def:StrongSaddleProperty\] Let the Morse function $F(\bullet)$ satisfy the strict saddle property with parameters ${\gamma}_1>0$ and ${\gamma}_2>0$. We say the Morse function $F(\bullet)$ satisfy the "strong saddle property" if for some ${\gamma}_3 > 0$ and any $x \in {\mathbb R}^n$ such that $\nabla F(x) = 0$, all eigenvalues ${\lambda}_i$, $i=1,2,...,n$ of the Hessian ${\nabla}^2 F(x)$ at $x$ satisfying (ii) in Definition \[Def:StrictSaddleProperty\] are bounded away from zero by some ${\gamma}_3>0$ in absolute value, i.e., $|{\lambda}_i|\geq {\gamma}_3>0$ for any $1\leq i \leq n$. We will call a saddle point $x\in {\mathbb R}^n$ of the function $F$ a "strong saddle" if Definition \[Def:StrongSaddleProperty\] holds at $x$. Thus a Morse function $F$ that satisfies the strong saddle property has all its saddle points that are strong saddle points. Throughout this paper we will work under Definition \[Def:StrongSaddleProperty\] for the function $F$. Linerization of the gradient flow near a strong saddle point. ------------------------------------------------------------- By the classical Hartman–Grobman Theorem (see @[Arnold] [§13]), for any strong saddle point $O$ that we consider, there exists an open neighborhood $U$ of $O$, and a ${\mathbf{C}}^{(0)}$ homeomorphism mapping $f: U{\rightarrow}{\mathbb R}^n$, such that the gradient flow is mapped by $f$ into a linear flow. The homeomorphism $f$ is called a (linear) conjugacy mapping. It turns out, that this mapping can be taken to be $h$–Hölder continuous for some $0<h\leq 1$ that depends only on the Hessian ${\nabla}^2 F(O)$ at $O$ (see @[StrengthenedHartmanGrobman]). To make our argument work, we will have to put an additional **Linerization Assumption.** *The homeomorphism $f$ provided by the Hartman–Grobman Theorem can be taken to be ${\mathbf{C}}^{(2)}$.* This assmption is needed in some technical proof that we provide in the Appendix of this paper. It is known that a sufficient condition for the validity of the ${\mathbf{C}}^{(2)}$ Linerization Assumption is the so called non–resonance condition (see, for example, the Sternberg linerization Theorem @[KatokHasselblatt] [Theorem 6.6.6]). We refer the reader to the Appendix for more discussions about our Linerization Assumption. Application in statistical machine learning. -------------------------------------------- In this subsection we draw a connection between the perturbed gradient flow defined in and the stochastic gradient method in statistical machine learning. Stochastic gradient method (SGM) is a stochastic analogue of the gradient descent algorithm, aiming at finding the local or global minimizers or maximizers of the function expectation parameterized by some random variable. One can schematically formulate the optimization problem as follows: under some initial distribution, we target at finding a local minimum point $x^*$ of the expectation of function $F(x) \equiv {\mathbf E}[ F(x;\zeta) ]$, where the indexed random variable $\zeta$ follows some prescribed distribution. If the regularity conditions on the exchangeability of gradient operator and expectation operator hold, e.g., when $\zeta$ is supported on a finite set, the gradient method updates via the iteration $$x_t = x_{t-1} - \beta {\mathbf E}[ \nabla F(x_{t-1};\zeta) ] .$$ However when the scale of the problem is extremely large, the access of expected gradients ${\mathbf E}[ \nabla F(z_{t-1};\zeta) ]$ are often expensive, and SGM prevails due to its one–query of noisy gradient at each iteration. In particular, SGM iteration often takes the following form $$x_t = x_{t-1} - \beta \nabla F(x_{t-1}; \zeta_t) ,$$ where $\beta$ is the fixed step–size and $\{\zeta_t\}$ are i.i.d. random variables that have the same distribution as $\zeta$. Due to its advantage in scalable data, SGM gains tremendous popularity in solving many large–scale statistical machine learning problems in the age of <span>*Big Data Tsunami*</span>. To analyze them, we associate the SGM with a diffusion process, i.e., the solution to a stochastic differential equation. Conversely, the SGM iteration can be viewed as a discrete–time, numerical scheme of such diffusion process. We follow the setting of the recent work by @[JunchiOptimization] and analyze a constant small step–size, continuous–time analogue of the stochastic gradient method that takes the form $$\label{Eq:SGD} dX_t = -{\beta}{\nabla}F(X_t)dt + {\beta}{\sigma}(X_t)dW_t \ , \ X_0=x \ ,$$ where $\sigma(z) = \left[\text{Var}\left(\nabla F(z;\zeta)\right)\right]^{1/2}$ is a positive semidefinite matrix. Equivalently, one can accelerate a factor of ${\beta}^{-1}$ and obtain for $Y^{\sqrt{{\beta}}}_t \equiv X_{t/{\beta}}$, $$dY^{\sqrt{{\beta}}}_t = - {\nabla}F(Y^{\sqrt{{\beta}}}_t)dt + \sqrt{{\beta}} {\sigma}(Y^{\sqrt{{\beta}}}_t)dW_t \ , \ Y^{\sqrt{{\beta}}}_0=x \ .$$ In other words, holds for ${\varepsilon}=\sqrt{{\beta}}$. Therefore under the small step–size regime ${\beta}{\downarrow}0$, the stochastic process $Y^{\sqrt{{\beta}}}_t$ defined in can be viewed as a continuous–time analogue of the SGM iteration, which addresses the stochasticity emerging from SGM. Thus from statistical machine learning point of view we are interested in the asymptotic as ${\beta}{\downarrow}0$ of the hitting time $$\label{Eq:HittingTimeSGDManySaddle} \tau^{\beta}= \inf\{t: F(X_t) \leq F(x^*) + e\} \ .$$ In plain words, how much time (upper bound) does it require *for the function value to decay* by at least $F(X_0) - F(x^*) + e$ using stochastic gradient descent? By using our main result stated in Section 1.1, we observe the phenomenon that when the the noise term ${\beta}{\sigma}(X_t)dW_t$ in is sufficiently omnidirectional it enables <span>*fast*</span> evasion from saddle points. Our Corollary \[Corollary:MajorResultSGDConvergenceTime\] in this paper suggests a time complexity ${\mathbf E}\tau^{\beta}\lesssim O(\beta^{-1}\ln (\beta^{-1}))$ as ${\beta}{\downarrow}0$ in discrete–time SGM (compare with @[GeEtAl1503], which requires $O(\beta^{-2})$ iteration). In other words, the hitting time to a point, in terms of function value, close to a local minimizer takes time that only introduces an additional factor of $O(\ln (\beta^{-1}))$ (compare with @[GeEtAl1503]). It is worth mentioning that the previous work by Pemantle @pemantle1990nonconvergence proves from a gradient flow viewpoint that SGM can avoid all nondegenerate saddle points, whenever the diffusion matrix $a(x)$ is uniformly positive definite or "omnidirectional" (see also a recent work by @lee2016gradient for the pure gradient descent case). However, neither of these works provides an analysis on the convergence rates. Within the scope of this work, we concentrate on the diffusion process associated with the discrete–time SGM, and we do not aim to quantify the approximation errors when bridging the discrete–time and continuous–time versions. We believe that using tools from numerical stochastic differential equations, such approximation error is small compared to the noise of dynamics and can be estimated rigorously, which potentially inspires another thread of interesting works. The rest of this paper is organized as follows. In Section 2 we quantify the decay of function value as well as the exit time in the neighborhood of one specific strong saddle point. We turn to analyze the general scenario in Section 3 where there are finitely many saddles that the process encounters along its trajectory. We provide the precise statement of theorem in the final part of this paper. Some technical proofs that validate the conclusions of Section 2 are left in the Appendix. Analysis of the function decay and exit time in a neighborhood of one specific "strong saddle". =============================================================================================== In this section we analyze the decay in function value of $F$ and the exit time asymptotic in a neighborhood of one specific "strong saddle" point $x_s\in {\mathbb R}^n$. These problems have been discussed thoroughly in the literature on random perturbations of dynamical systems (see for example @[Kifer1981], @[Bakhtin2008SPA], @[BakhtinHeteroclinic], @[MonterBakhtinNormalForm], among others), yet we will still compensate some additional technical proofs that are left in these literature (the technical part of the proof of Theorem \[Thm:Kifer1981Strengthened\] will be put in the Appendix). In @[Kifer1981], the author discussed the behavior of the trajectory of in a neighborhood of one specific strong saddle point $x_s$. Without loss of generality we can assume that the saddle point $x_s=0$ is the origin inside $U \subset {\mathbb R}^n$: a bounded connected open set with smooth boundary. Let $G\subset U$ be a domain with smooth boundary, so that $0$ is the only isolated saddle inside $G$. The work @[Kifer1981] provides both the "exit time" and the "exit trajectory" analyses. Roughly speaking, for the perturbed system , as ${\varepsilon}$ is small, starting from an initial condition that is being attracted to $0$ by the deterministic flow the first exit trajectory should happen along the unstable direction with most negative eigenvalue of the Hessian ${\nabla}^2 F$, that is the direction pointed by the strict saddle property in Definition \[Def:StrictSaddleProperty\]. Some refinements of @[Kifer1981] can also be found in @[Bakhtin2008SPA], @[BakhtinHeteroclinic], @[MonterBakhtinNormalForm]. Let us work under the set–up of @[Kifer1981]. Let $0$ belong to the interior of $G$ and there are no other equilibriums in $G$. Let $A={\nabla}^2 F(0)$. We assume that $-{\lambda}_1=-{\lambda}_2=...=-{\lambda}_{q}<-{\lambda}_{q+1}\leq...\leq -{\lambda}_{p} <0<{\lambda}_{p+1}\leq ... \leq {\lambda}_n$ are the (real) eigenvalues of $A$, and ${\lambda}_1\geq {\gamma}_1>0$. We shall work with the time–rescaled and perturbed process $Y_t^{\varepsilon}$ as in . Let $$\label{Eq:HittingTimeSGDPerturbation} \tau^{\varepsilon}_x=\inf\{t>0: Y_0=x \ , \ Y^{\varepsilon}_t\in {\partial}G\} \ .$$ Let us also consider the corresponding deterministic gradient flow . The author of @[Kifer1981] introduced a decomposition $$G\cup {\partial}G=0\cup A_1\cup A_2\cup A_3 \ ,$$ where $A_1$ is a set of points $x\in G\cup {\partial}G$ such that if $x\in A_1$ then $S^ux\in G$ for $u>s$ and $S^u x\not \in G\cup {\partial}G$ if $u\leq s$ for some $s=s(x)\leq 0$ and $S^t x{\rightarrow}0$ as $t{\rightarrow}\infty$; $A_2$ is a set of points $x\in G\cup {\partial}G$ such that if $x\in A_2$ then $S^u x\in G$ for $u<s$ and $S^u x\not\in G\cup {\partial}G$ if $u>s$ for some $s=s(x)\geq 0$ and $S^t x{\rightarrow}0$ as $t{\rightarrow}-\infty$; $A_3$ is a set of points $x\in G\cup {\partial}G$ such that if $x\in A_3$ then $S^u x\in G$ provided $s_1<u<s_2$ and $S^u x\not\in G\cup {\partial}G$ if either $u>s_2$ or $u<s_1$ for some $s_1=s_1(x)\leq 0$ and $s_2=s_2(x)\geq 0$. It is noted in @[Kifer1981] that $A_1$ and $A_3$ may be simultaneously empty. If $x\in A_2\cup A_3$, then $S^t x$ leaves $G$ after some time, so that there is a finite $$\label{Eq:DeterministicFiniteExitTime} t(x)=\inf\{t>0 : S^t x\in {\partial}G\} \ .$$ As in @[Kifer1981], let us denote by ${\Gamma}_{\text{max}}$ the eigenspace of $A$ which corresponds to the eigenvalues $-{\lambda}_1,...,-{\lambda}_q$. Then as in @[Kifer1981], there exists a $q$–dimensional sub–manifold $W_{\text{max}}$ tangent to ${\Gamma}_{\text{max}}$ at $0$ and is invariant with respect to $S^t$. We see that $Q_{\text{max}}=W_{\text{max}}\cap {\partial}G$ is not empty. If $q>1$ then $Q_{\text{max}}$ is a sub–manifold of ($q-1$)–dimensions on the boundary ${\partial}G$. If $q=1$ then $Q_{\text{max}}$ consists of two points. The result of @[Kifer1981] can be summarized as follows. \[Thm:Kifer1981\] (a) (Exit time distribution) If $x\in (0\cup A_1)\backslash {\partial}G$ then for any ${\delta}>0$ we have $$\label{Eq:ExitTimeStableManifold} \lim{\limits}_{{\varepsilon}{\downarrow}0}{\mathbf P}_x\left(1-{\delta}<\dfrac{\tau_x^{\varepsilon}{\lambda}_1}{|\ln {\varepsilon}|}<1+{\delta}\right)=1 \ ,$$ i.e., $\dfrac{\tau_x^{\varepsilon}}{|\ln {\varepsilon}|}$ tends in probability to $\dfrac{1}{{\lambda}_1}$ as ${\varepsilon}{\downarrow}0$. If $x\in A_2\cup A_3$ then for any ${\delta}>0$ we have $$\label{Eq:ExitTimeUnStableManifold} \lim{\limits}_{{\varepsilon}{\downarrow}0}{\mathbf P}_x\left(1-{\delta}<\dfrac{\tau_x^{\varepsilon}}{t(x)}<1+{\delta}\right)=1 \ ,$$ i.e., $\tau_x^{\varepsilon}$ tends in probability to $t(x)$ as ${\varepsilon}{\downarrow}0$. \(b) (Expected exit time distribution) If $x\in (0\cup A_1)\backslash {\partial}G$ then $$\label{Eq:ExpectedExitTimeStableManifold} \lim{\limits}_{{\varepsilon}{\downarrow}0}|\ln {\varepsilon}|^{-1}{\mathbf E}_x\tau_x^{\varepsilon}={\lambda}_1^{-1} \ .$$ If $x\in A_2\cup A_3$ then $$\label{Eq:ExpectedExitTimeUnStableManifold} \lim{\limits}_{{\varepsilon}{\downarrow}0}{\mathbf E}_x \tau_x^{\varepsilon}=t(x) \ .$$ \(c) (Exit distribution) If $x\in (0\cup A_1) \backslash {\partial}G$ then for any open set $Q$ of ${\partial}G$ such that $Q \supset Q_{\text{max}}$ we have $$\label{Eq:ExitDistributionStableManifold} \lim{\limits}_{{\varepsilon}{\downarrow}0}{\mathbf P}_x(Y_{\tau_x^{\varepsilon}}^{\varepsilon}\in Q)=1 \ .$$ If $x\in A_2\cup A_3$ then for any Borel measurable set $Q$ in ${\mathbb R}^n$ we have $$\label{Eq:ExitDistributionUnstableManifold} \lim{\limits}_{{\varepsilon}{\downarrow}0}{\mathbf P}_x(Y_{\tau_x^{\varepsilon}}^{\varepsilon}\in Q)={\mathbf 1}(S^{t(x)}x \in Q) \ .$$ Making use of this Theorem, since $t(x)$ is finite for fixed $x$, it is then seen that by and we have, for any $x\in G$, that $$\label{Eq:xExitTimeAsymptoticNonDegenerateSaddleSGDPerturbation} \lim{\limits}_{{\varepsilon}{\downarrow}0}\dfrac{{\mathbf E}_x\tau_x^{\varepsilon}}{\ln \left({\varepsilon}^{-1}\right)}\leq \dfrac{1}{{\lambda}_1}\leq \dfrac{1}{{\gamma}_1} \ .$$ Back to the problem of convergence time of a diffusion approximation of the stochastic gradient method in Section 1.3, in @[JunchiOptimization], based on @[Kifer1981], the authors discuss the behavior of the trajectory of in a neighborhood of one specific strong saddle point $x_s$. Without loss of generality we can assume that the saddle point $x_s=0$ is the origin inside $U \subset {\mathbb R}^n$ a bounded connected open set with smooth boundary. Let $G\subset U$ be a domain with smooth boundary, so that $0$ is the only isolated saddle inside $G$. Let us denote the hitting time $$\label{Eq:HittingTime} \tau^{\beta}({\partial}G)=\inf\{t>0, X_t\in {\partial}G\} \ .$$ Here $X_t$ is as in . Then @[JunchiOptimization] concluded with the result that for any $x\in G$, $$\label{Eq:xExitTimeAsymptoticNonDegenerateSaddle} \lim{\limits}_{{\beta}{\downarrow}0}\dfrac{{\mathbf E}_{x}\tau^{\beta}({\partial}G)}{{\beta}^{-1}\ln ({\beta}^{-1})}\leq \dfrac{1}{2{\gamma}_1} \ .$$ The derivation of is based on Theorem \[Thm:Kifer1981\], working with the perturbed process $Y_t^{\sqrt{{\beta}}}$ in . Recall that in Section 1.3 we have $X_{t/{\beta}}=Y_t^{\sqrt{{\beta}}}$. Therefore $\tau^{\beta}({\partial}G)$ in and $\tau_x^{\sqrt{{\beta}}}$ in (we let ${\varepsilon}=\sqrt{{\beta}}$) relates each other with a scaling factor $\tau^{\beta}({\partial}G)=\tau_x^{\sqrt{{\beta}}}/{\beta}$. This gives us . From here we have recovered the main result of @[JunchiOptimization]. Due to the fact that we have to deal with many saddles instead of one saddle associated with the landscape of $F$, it turns out, that in our subsequent analysis we actually need a uniform (rather than pointwise) version of Theorem \[Thm:Kifer1981\] (this is only technical, see Appendix). The asymptotic limits in parts (b) and (c) of Theorem \[Thm:Kifer1981\], and thus in are for *fixed* $x\in G$, and what we need in our subsequent analysis are the corresponding asymptotic limits *uniformly* for all $x\in U\cup {\partial}U$ where $U$ is an open neighborhood $U\subset G$ of the saddle point $O$. Under our Linerization Assumption, this can be achieved via an adaptation of the arguments in @[BakhtinHeteroclinic]. We provide additional technical proofs in the Appendix. Let us briefly describe the result in what follows. Let $U\subset G$ be an open neighborhood of the saddle point $O$. Let $U$ be chosen so small that $\text{dist}(U\cup {\partial}U, {\partial}G)>0$. Let $t(x)$ be defined as in . Set $${\partial}G_{U\cup {\partial}U {\rightarrow}{\text{out}}}=\{S^{t(x)}x \text{ for some } x\in U \cup {\partial}U \text{ with finite } t(x)\}\cup Q_{\text{max}} \ .$$ For small $\mu>0$ we let $$Q^\mu=\{x\in {\partial}G \ , \ \text{dist}(x, {\partial}G_{U\cup {\partial}U{\rightarrow}\text{out}})<\mu\} \ .$$ Then we have an extension of the previous result. \[Thm:Kifer1981Strengthened\] For any $r>0$, there exist some ${\varepsilon}_0>0$ so that for all $x\in U\cup {\partial}U$ and all $0<{\varepsilon}<{\varepsilon}_0$ we have $$\label{Eq:ExpectedExitTimeStrengthened} \dfrac{{\mathbf E}_x\tau_x^{\varepsilon}}{\ln({\varepsilon}^{-1})}\leq \dfrac{1}{{\lambda}_1}+r \ .$$ For any small $\mu>0$ and any $\rho>0$, there exist some ${\varepsilon}_0>0$ so that for all $x\in U\cup {\partial}U$ and all $0<{\varepsilon}<{\varepsilon}_0$ we have $$\label{Eq:ExitDistributionStrenghtened} {\mathbf P}_x(Y_{\tau_x^{\varepsilon}}^{\varepsilon}\in Q^\mu)\geq 1-\rho \ .$$ *Proof.* We make use of Lemmas \[Appendix:Lm:ExitTimeExitDistributionPart1\], \[Appendix:Lm:ExitTimeExitDistributionPart2\], \[Appendix:Lm:ExitTimeExitDistributionPart3\], and we choose $$0<{\varepsilon}_0<\min({\varepsilon}_0(r), {\varepsilon}_0(\rho, \mu), {\varepsilon}_0(r, 1), {\varepsilon}_0(\rho, \mu, 1), ..., {\varepsilon}_0(r, k_0-1), {\varepsilon}_0(\rho, \mu, k_0-1), {\varepsilon}_0(r, k_0), {\varepsilon}_0(\rho, \mu, k_0)) \ ,$$ where $k_0=k_0(r,\rho,\mu)$, so that we can conclude the result of this Theorem. $\square$ The general case: finitely many saddles. ======================================== Let us consider the case when the Morse function $F$ has finitely many strong saddles $O_1,...,O_k$ (according to Definition \[Def:StrongSaddleProperty\]). Since the problem formulated in Section 1 is only about function value decay so that the process $Y_t^{\varepsilon}$ hits a local minimum point of $F$, we can assume, without loss of generality, that the saddles $O_1,...,O_k$ are ordered in such a way that $F(O_1)>F(O_2)>...>F(O_k)$, and the point $x^*$ is a local minimum point of $F$ with $F(x^*)<F(O_k)$. We will work within the basin $U(x^*)$ of $x^*$, so that $O_1,...,O_k$ are the only critical points besides $x^*$ in $U(x^*)$. Let us work with the perturbed process $Y_t^{\varepsilon}$ in . Let $Y_0^{\varepsilon}=x\in U(x^*)$ and $F(x)>F(O_1)$. Given a fixed small number $e>0$, such that $F(O_k)>F(x^*)+e$, let $$T^{\varepsilon}_x=\inf\{t\geq 0: Y_0^{\varepsilon}=x \ , \ F(Y_t^{\varepsilon})\leq F(x^*)+e\} \ .$$ Our goal is to give an asymptotic estimate of $T^{\varepsilon}_x$. For each saddle point $O_i$, we consider a nested pair of open neighborhoods $U_i\subsetneq V_i$ containing $O_i$. Let us first pick all $V_i$, $i=1,2,...,k$ in such a way that $O_i\in V_i$ is the only stationary point inside $V_i$, and for any $i\neq j$, we have $V_i\cap V_j=\emptyset$. Let us then pick $U_i\subset V_i$ such that $\text{dist}({\partial}U_i, {\partial}V_i)>0$ for all $i=1,2,...,k$. For each saddle point $O_i$, let us denote by ${\Gamma}_{i, \text{max}}$ the eigenspace of ${\nabla}^2 F(O_i)$ which corresponds to the negative eigenvalues of ${\nabla}^2 F(O_i)$ with largest absolute value. For each open neighborhood $V_i$, as in @[Kifer1981], we can construct a submanifold $W_{i, \text{max}}$ that is tangent to ${\Gamma}_{i, \text{max}}$ at $O_i$ and is invariant with respect to $S^t$. Let $Q_{i, \text{max}}=W_{i, \text{max}}\cap {\partial}V_i$. By the classification of points in $V_i\cup {\partial}V_i$ as $O_i$, $A_1$, $A_2$, $A_3$ as in @[Kifer1981] presented in our Section 2, we see that for any point $x\in U_i\cup {\partial}U_i$, either there exist some finite $t(x)$ such that $S^{t(x)}x\in {\partial}V_i$, or $S^t x{\rightarrow}O_i$ as $t{\rightarrow}\infty$. Let $${\partial}V_{i, U_i\cup {\partial}U_i {\rightarrow}{\text{out}}}=\{S^{t(x)}x \text{ for some } x\in U_i \cup {\partial}U_i \text{ with finite } t(x)\}\cup Q_{i, \text{max}} \ .$$ For any fixed positive number $h>0$, we introduce the level curves $$C_i(F(O_i)\pm h)=\{x\in {\mathbb R}^n: F(x)=F(O_i)\pm h\} \ .$$ Given $h>0$ sufficiently small, let us introduce the open domain $$D((F(O_i)+h, F(O_{i-1})-h))=\{x\in {\mathbb R}^n: F(O_i)+h<F(x)<F(O_{i-1})-h\} \ .$$ If $i=1$, we can symbolically let $F(O_0)=\infty$, so that $$D((F(O_1)+h, F(O_0)-h))=D((F(O_1)+h, \infty))=\{x\in {\mathbb R}^n: F(O_1)+h<F(x)\} \ .$$ Note that the curve $C_i(F(O_i)\pm h)$ and the domain $D((F(O_i)+h, F(O_{i-1})-h))$ may have several disconnected components, and only some of these components have points that are close to $O_i$ ($O_{i-1}$). Also note that $C_i(F(O_i)-h)$ ($C_{i-1}(F(O_{i-1})+h)$) are the lower (upper) boundaries of $D((F(O_i)+h, F(O_{i-1})-h))$. We will now present a geometric lemma, that describes the geometry (see Figure 1) of the gradient flow in a neighborhood of a non–degenerate strong saddle. \[Lm:GeometricLemma\] (Geometric lemma) Uniformly for all $i=1,2,...,k$, we have the following. \(i) Besides the basic assumptions of the nested neighborhoods $U_i$, $V_i$ that we imposed before, we can pick $U_i$, $V_i$ in such a way that there exist some constant $\mu>0$ independent of $i$, and some constant $h>0$ that may depend on the choice of $U_i$ and $V_i$, such that for any $x\in {\partial}V_i$ with $\text{dist}(x, {\partial}V_{i, U_i\cup {\partial}U_i{\rightarrow}\text{out}})<\mu$, we have $F(x)<F(O_i)-h$; \(ii) One can pick the constant $h>0$ so small that $C_i(F(O_i)+\frac{h}{2})\cap U_i\neq \emptyset$; \(iii) For fixed $h>0$ as in (ii), there exist some ${\kappa}>0$ such that $|{\nabla}F(x)|\geq {\kappa}$ for any point $x\in D(F(O_i)+\frac{h}{2}, F(O_{i-1})-\frac{h}{2})$; \(iv) One can pick the constant ${\kappa}>0$ so small that for any point $x\in C_i(F(O_i)+\frac{h}{2})$, and $x\not \in U_i$, there exist a tubular neighborhood ${\mathcal T}(x)$, such that ${\partial}{\mathcal T}(x)\cap C_i(F(O_i)-h)\neq \emptyset$, ${\partial}{\mathcal T}(x)\cap C_i(F(O_i)+h)\neq \emptyset$, and all other boundaries of ${\mathcal T}(x)$ are parallel to flow lines of . Moreover, for any $y\in {\mathcal T}(x)$, we have $|{\nabla}F(y)|\geq {\kappa}$. *Proof.* By the classical Hartman–Grobman Theorem (@[Arnold] [§13]), within a sufficiently small neighborhood of the strong saddle point $O_i$, the flow $S^t x$ in is ${\mathbf{C}}^{(0)}$–conjugate to the linear flow with matrix $-{\nabla}^2 F(O_i)$. Since the claims stated in this Lemma are all invariant under ${\mathbf{C}}^{(0)}$ deformation, we just have to prove this lemma under the framework of linear dynamics (see Figure 1). \(i) By the so–called Inclination Lemma @[Brin-Stuck] [Theorem 5.7.2] (also see Lemma 5.7.1 in the same reference), one can pick $U_i$ small enough so that all flows starting from $U_i\cup {\partial}U_i$, if not attracted to $O_i$, will approach the unstable manifold of the saddle point $O_i$, before they hit ${\partial}V_i$. In fact, the Inclination Lemma indicates that the flow $S^t x$ will map any small disk that is intersecting transversally with the stable manifold, with the dimension equal to that of the unstable manifold, to be close to the unstable manifold in ${\mathbf{C}}^{(1)}$–norm. Moreover, this disk is stretched in the unstable directions while it is being attracted to the unstable manifold. Due to non–degeneracy of the saddle point $O_i$, by picking $V_i$ relatively large with respect to $U_i$ we see that the statement follows; \(ii) Note that if $h>0$ satisfy (i), then any $\widetilde{h}>0$ such that $\widetilde{h}<h$ also satisfy (i). Thus by picking $\widetilde{h}$ sufficiently small we have (ii); \(iii) Fix $h>0$ as in (ii), since one can find a neighborhood $N_i$ of $O_i$ inside $U_i$, such that $C_i(F(O_i)+\frac{h}{2})$ does not touch this neighborhood, and $O_i$'s are isolated zeros of $|{\nabla}F(x)|$, we see that we have (iii); \(iv) We can take the neighborhood $N_i$ of $O_i$ inside $U_i$ to be so small that for any point $x\in C_i(F(O_i)+\frac{h}{2})$ and $x\not\in U_i$, the flow line of passing through $x$ and connecting $C_i(F(O_i)+h)$ to $C_i(F(O_i)-h)$, does not touch $N_i$. In fact, since by (ii) we know that $C_i(F(O_i)+\frac{h}{2})\cap U_i\neq \emptyset$, we have, that for any $x\not\in U_i$ and $x\in C_i(F(O_i)+\frac{h}{2})$, the point $x$ lies outside of some invariant stable cone $K_{\delta}^s$ (see Figure 1). The Inclination Lemma again implies that the forward flow $S^t x$ stretches $x$ along the unstable direction, thus keeps the resulting flow away from $N_i$. Thus the flow line of passing through $x$ and connecting $C_i(F(O_i)+h)$ to $C_i(F(O_i)-h)$, does not touch $N_i$. Further, the family of flow lines in a tubular neighborhood ${\mathcal T}(x)$ of this flow line are connecting $C_i(F(O_i)+h)$ to $C_i(F(O_i)-h)$, and they do not touch $N_i$. For any $y$ on this ${\mathcal T}(x)$, we will have $|{\nabla}F(y)|\geq {\kappa}>0$. $\square$ ![Geometry of gradient flow dynamics near a saddle point.](Fig1_formal.jpg){height="10cm" width="13cm"} Note that as $h{\rightarrow}0$, we have ${\kappa}{\rightarrow}0$, and it might happen that $\dfrac{h}{{\kappa}^2}{\rightarrow}\infty$. However, in what follows we will pick some fixed $h>0$ and ${\kappa}>0$ as well as the neighborhoods of the saddle points as in Lemma \[Lm:GeometricLemma\], and we let ${\varepsilon}{\rightarrow}0$. Let us provide now an auxiliary lemma, which is essentially adapted from @[FWbook] [Chapter 2, Lemma 3.1], that will be used frequently in our subsequent arguments. Before we state the lemma, let us first introduce some definition regarding exit behavior of the flow $\{S^t x: t \geq 0\}$ in . Let $D\subset {\mathbb R}^n$ be an open domain in ${\mathbb R}^n$. Let $x\in D$ and we consider the deterministic trajectory $\{S^t x: t\geq 0\}$. \[Def:RegularANDPenetratingExit\] We say that the trajectory $\{S^t x: t\geq 0\}$ starting from initial condition $x\in D$, exits $D$ in a "regular manner" if $$t(x, {\partial}D)=\inf\{t\geq 0: S^t x\not\in D\}<\infty \ ,$$ and for some sufficiently small ${\delta}>0$ we have $$\label{Eq:RegularExit} S^{t(x,{\partial}D)+{\delta}}(x)\not \in D\cup {\partial}D \ .$$ We say that the trajectories $\{S^t x: t\geq 0, x\in D\}$ exit $D$ in a "penetrating manner" if for any $x\in D$, the trajectory $\{S^t x: t\geq 0\}$ exits $D$ in a regular manner, such that there exist some constant $T_0>0$ with $t(x,{\partial}D)\leq T_0$ for all $x\in D$, and there exist some constant $c>0$, such that for some sufficiently small ${\delta}>0$, we have $$\label{Eq:PenetratingEntrance} \max{\limits}_{t(x,{\partial}D)\leq t\leq t(x,{\partial}D)+{\delta}}\text{dist} \ (S^t x, D\cup {\partial}D)\geq c >0 \ ,$$ uniformly for all $x\in D$. We say that the part of the boundary ${\Gamma}\subseteq {\partial}D$ is the "exit piece" of $\{S^t x, x\in D, t\geq 0\}$ if $\{S^t x: x\in D, t\geq 0\}$ exit $D$ in a penetrating manner, and for any point $y\in {\Gamma}$, there exist some $x\in D$ and $t(x,{\partial}D)\leq T_0$ such that $S^{t(x,{\partial}D)} x=y$. \[Lm:FiniteTimeComparisonGradientFlowANDSGDPerturbation\] Let the domain $D\subset {\mathbb R}^n$ and initial point $x\in D$ be stated as in Definition \[Def:RegularANDPenetratingExit\]. Let $$t(x,{\partial}D)=\inf\{t\geq 0: S^t x\not \in D\} \ .$$ Let $$\tau^{\varepsilon}_x({\partial}D)=\inf\{t\geq 0: Y_0=x \ , \ Y_t^{\varepsilon}\in {\partial}D\} \ .$$ If $t(x,{\partial}D)$ is finite for some choice of $x$ and $D$, and $\{S^t x: t\geq 0\}$ exits $D$ in a regular manner, then $\tau_x^{\varepsilon}({\partial}D) {\rightarrow}t(x,{\partial}D)$ in probability as ${\varepsilon}{\downarrow}0$, i.e., for any given ${\delta}>0$, $$\label{Eq:FiniteTimeComparisonGradientFlowANDSGDPerturbationConvergenceInProbability} \lim{\limits}_{{\varepsilon}{\rightarrow}0}{\mathbf P}_x(|\tau^{\varepsilon}_x({\partial}D)-t(x,{\partial}D)|>{\delta})=0 \ .$$ Moreover, if $\{S^t x, t\geq 0, x\in D\}$ exits $D$ in a penetrating manner, then there exist some ${\varepsilon}_0>0$ that may depend on $D$ and $c$, and some constant $C$ that may depend on $T_0$, but is independent of ${\varepsilon}_0$, such that for any $0<{\varepsilon}<{\varepsilon}_0$ we have $$\label{Eq:FiniteTimeComparisonGradientFlowANDSGDPerturbationFiniteExpectedTime} \sup{\limits}_{x\in D}{\mathbf E}_x \tau^{\varepsilon}_x({\partial}D)\leq C \ .$$ Finally, suppose $\{S^t x, t\geq 0, x\in D\}$ exits $D$ in a penetrating manner, and ${\Gamma}\subseteq {\partial}D$ is the exit piece as in Definition \[Def:RegularANDPenetratingExit\]. Then for any open set $Q$ of ${\partial}D$ and $Q\supset{\Gamma}$, for any $\rho>0$ sufficiently small, there exist some ${\varepsilon}_0>0$ such that for any $0<{\varepsilon}<{\varepsilon}_0$, we have $$\label{Eq:FiniteTimeComparisonGradientFlowANDSGDPerturbationExitPosition} {\mathbf P}_x(Y^{\varepsilon}_{\tau_x^{\varepsilon}({\partial}D)}\in Q)\geq 1-\rho \ ,$$ for all $x\in D$. *Proof.* If $\{S^t x, t\geq 0\}$ exits $D$ in a regular manner, then for every sufficiently small ${\delta}>0$ we have $$S^{t(x,{\partial}D)-{\delta}}x\in D \ , \ S^{t(x,{\partial}D)+{\delta}}x\not\in D\cup {\partial}D \ .$$ Let ${\delta}_1>0$ be the distance of the trajectory segment $\{S^s x \ , \ s\in [0, t(x,{\partial}D)-{\delta}]\}$ from ${\partial}D$, and ${\delta}_2>0$ be the distance of $S^{t(x,{\partial}D)+{\delta}}x$ from ${\partial}D$, and let $\bar{{\delta}}=\min({\delta}_1,{\delta}_2)>0$. By @[FWbook] [Chapter 2 , Theorem 1.2] we see that $$\lim{\limits}_{{\varepsilon}{\rightarrow}0}{\mathbf P}_x\left\{\sup{\limits}_{0\leq s \leq t(x,{\partial}D)+{\delta}}|Y^{\varepsilon}_s(x)-S^s x|>\bar{{\delta}}\right\}=0 \ .$$ Here $Y^{\varepsilon}_t(x)$ denotes the process $Y_t^{\varepsilon}$ in with $Y^{\varepsilon}_0=x$. This implies that $$\label{Eq:PointwiseEstimateHittingTime} \lim{\limits}_{{\varepsilon}{\rightarrow}0}{\mathbf P}_x(\tau^{\varepsilon}_x({\partial}D)\in [t(x,{\partial}D)-{\delta}, t(x,{\partial}D)+{\delta}])=1 \ ,$$ which is , and from here we see $\tau^{\varepsilon}_x({\partial}D){\rightarrow}t(x,{\partial}D)$ in probability as ${\varepsilon}{\downarrow}0$. Now let us assume that $\{S^t x \ , \ t\geq 0 \ , \ x\in D\}$ exit $D$ in a penetrating manner. Let $t(x,{\partial}D)\leq T_0$ for all $x\in D$ and $\max{\limits}_{t(x, {\partial}D)\leq t\leq t(x,{\partial}D)+{\delta}}\text{dist} \ (S^t x, D\cup {\partial}D)\geq c >0$ uniformly for all $x\in D$ and some ${\delta}>0$. This implies that for every ${\delta}>0$, there exist some ${\varepsilon}_0>0$ such that for any $0<{\varepsilon}<{\varepsilon}_0$ we have $$\label{Eq:UniformEstimateHittingTime} {\mathbf P}_x(|\tau^{\varepsilon}_x({\partial}D)-t(x,{\partial}D)|>{\delta})\leq {\delta}$$ for all $x\in D$. Therefore $$\sup{\limits}_{x\in D} {\mathbf P}_x(\tau^{\varepsilon}_x({\partial}D)>2T_0)\leq {\delta}\ .$$ By strong Markov property of the process $Y_t^{\varepsilon}$ we see that $$\begin{array}{ll} \sup{\limits}_{x\in D} {\mathbf P}_x(\tau_x^{\varepsilon}({\partial}D)>n\cdot 2 T_0) & = \sup{\limits}_{x\in D} [{\mathbf P}_x(\tau^{\varepsilon}_{Y^{\varepsilon}_{(n-1)2T_0}}({\partial}D)>2T_0|Y^{\varepsilon}_{(n-1)2T_0}\in D){\mathbf P}_x(\tau_x^{\varepsilon}({\partial}D)>(n-1)2T_0)] \\ & \leq {\delta}\cdot \sup{\limits}_{x\in D}{\mathbf P}_x(\tau_x^{\varepsilon}({\partial}D)>(n-1)2T_0) \ . \end{array}$$ Therefore for every integer $n\geq 0$ we have, for every $x\in D$, $${\mathbf P}_x(\tau_x^{\varepsilon}({\partial}D)> n \cdot 2T_0)\leq {\delta}^n \ .$$ Therefore we have $$\begin{array}{ll} {\mathbf E}_x\tau_x^{\varepsilon}({\partial}D) & \leq \sum{\limits}_{n=0}^\infty (n+1)\cdot 2T_0\cdot {\mathbf P}_x(n\cdot 2T_0< \tau_x^{{\varepsilon}}({\partial}D)\leq (n+1)\cdot 2T_0) \\ & \leq \sum{\limits}_{n=0}^\infty (n+1)\cdot 2T_0\cdot {\mathbf P}_x(\tau_x^{{\varepsilon}}({\partial}D)>n\cdot 2T_0) \\ & \leq \sum{\limits}_{n=0}^\infty (n+1)\cdot 2T_0 \cdot {\delta}^n \\ & \leq C \end{array}$$ since we can choose ${\delta}>0$ to be sufficiently small. This implies . Finally, let us prove . For any ${\delta}>0$ and any $\mu>0$, we have $$\begin{array}{ll} &{\mathbf P}_x\left(|Y^{\varepsilon}_{\tau_x^{\varepsilon}({\partial}D)}-S^{t(x,{\partial}D)}x|>{\delta}\right) \\ = & {\mathbf P}_x\left(|Y^{\varepsilon}_{\tau_x^{\varepsilon}({\partial}D)}-S^{t(x,{\partial}D)}x|>{\delta}\ , \ |\tau_x^{\varepsilon}({\partial}D)-t(x,{\partial}D)|>\mu\right) \\ & \ \ \ \ \ +{\mathbf P}_x\left(|Y^{\varepsilon}_{\tau_x^{\varepsilon}({\partial}D)}-S^{t(x,{\partial}D)}x|>{\delta}\ , \ |\tau_x^{\varepsilon}({\partial}D)-t(x,{\partial}D)|\leq \mu\right) \\ \leq & {\mathbf P}_x\left(|\tau_x^{\varepsilon}({\partial}D)-t(x,{\partial}D)|>\mu\right) \\ & \ \ \ \ \ +{\mathbf P}_x\left(|Y^{\varepsilon}_{\tau_x^{\varepsilon}({\partial}D)}-S^{t(x,{\partial}D)}x|>{\delta}\ , \ |\tau_x^{\varepsilon}({\partial}D)-t(x,{\partial}D)|\leq \mu\right) \\ \leq & {\mathbf P}_x\left(|\tau_x^{\varepsilon}({\partial}D)-t(x,{\partial}D)|>\mu\right) \\ & \ \ \ \ \ +{\mathbf P}_x\left(\sup{\limits}_{t(x,{\partial}D)-\mu \leq t\leq t(x,{\partial}D)+\mu}|Y^{\varepsilon}_t-S^{t(x,{\partial}D)}x|>{\delta}\right) \\ \leq & {\mathbf P}_x\left(|\tau_x^{\varepsilon}({\partial}D)-t(x,{\partial}D)|>\mu\right) \\ & \ \ \ \ \ +{\mathbf P}_x\left(\sup{\limits}_{t(x,{\partial}D)-\mu \leq t\leq t(x,{\partial}D)+\mu}(|Y^{\varepsilon}_t-S^t x|+|S^t x-S^{t(x,{\partial}D)}x|)>{\delta}\right) \\ \leq & {\mathbf P}_x\left(|\tau_x^{\varepsilon}({\partial}D)-t(x,{\partial}D)|>\mu\right) \\ & \ \ \ \ \ +{\mathbf P}_x\left(\sup{\limits}_{t(x,{\partial}D)-\mu \leq t\leq t(x,{\partial}D)+\mu}|Y^{\varepsilon}_t-S^t x|+ \sup{\limits}_{t(x,{\partial}D)-\mu \leq t\leq t(x,{\partial}D)+\mu}|S^t x-S^{t(x,{\partial}D)}x|>{\delta}\right) \ . \end{array}$$ Due to the continuity of the flow $S^t x$, one can pick $\mu>0$ small enough such that for all $x\in D$ we have $\sup{\limits}_{t(x,{\partial}D)-\mu \leq t\leq t(x,{\partial}D)+\mu}|S^t x-S^{t(x,{\partial}D)}x|<\dfrac{{\delta}}{2}$. Thus we have $$\begin{array}{ll} &{\mathbf P}_x\left(|Y^{\varepsilon}_{\tau_x^{\varepsilon}({\partial}D)}-S^{t(x,{\partial}D)}x|>{\delta}\right) \\ \leq & {\mathbf P}_x\left(|\tau_x^{\varepsilon}({\partial}D)-t(x,{\partial}D)|>\mu\right) +{\mathbf P}_x\left(\sup{\limits}_{t(x,{\partial}D)-\mu \leq t\leq t(x,{\partial}D)+\mu}|Y^{\varepsilon}_t-S^t x|>\dfrac{{\delta}}{2}\right) \ . \end{array}$$ By as well as the fact that $t(x,{\partial}D)\leq T_0$ for all $x\in D$, we see that the above estimate implies . $\square$ Let us define $$C(\pm h)=\bigcup\limits_{i=1}^k C_i(F(O_i)\pm h) \ .$$ For simplicity of notations let us also define $C_i(\pm h)=C_i(F(O_i)\pm h)$. Let us define a sequence of stopping times (see Figure 2, one can also find similar constructions in @[FWbook] [Chapter 6], also see @[Koralov2004]) $$\label{Eq:SequenceStoppingTime} 0={\sigma}_0\leq \tau_1\leq {\sigma}_1\leq \tau_2\leq {\sigma}_2\leq ...$$ such that $$\label{Eq:SequenceStoppingTimeTau} \tau_j=\inf\{t>{\sigma}_{j-1}: Y_t^{\varepsilon}\in C(h/2)\} \ ,$$ $$\label{Eq:SequenceStoppingTimeSigma} {\sigma}_j=\inf\{t>\tau_j: Y_t^{\varepsilon}\in C(-h)\} \ .$$ ![Sequence of stopping times.](Fig2_formal.jpg){height="10cm" width="10cm"} Let us start the process $Y_t^{\varepsilon}$ from $Y_0^{\varepsilon}=x\in {\mathbb R}^n$, such that $F(x)>F(O_1)$, and at the same time $x\not\in V_1\cup {\partial}V_1$. Let us also assume that we have some $H>0$ such that $H>F(x)$, and for all points $y\in {\partial}V_1$, we have $H>F(y)$. From our geometric lemma Lemma \[Lm:GeometricLemma\], we see that for any $x_1$ such that $F(x_1)\geq F(O_1)+h/2$, we have $|{\nabla}F(x_1)|\geq {\kappa}>0$. By the fact that $\dfrac{d}{dt}F(S^t x)=-|{\nabla}F(S^t x)|^2\leq -{\kappa}^2$, this implies that $$\label{Eq:HittingTimeUniformBoundTowardsBottomGradientFlow} t(x,C_1(h/2))\leq \dfrac{F(x)-F(O_1)-h/2}{{\kappa}^2}<\dfrac{H-F(O_1)-h/2}{{\kappa}^2} \ .$$ Moreover, since $S^t x$ is a gradient flow, the flow lines of $S^t x$ will be perpendicular to $C_1(h/2)$ when $x\in C_1(h/2)$. Due to the fact that $|{\nabla}F(x_1)|\geq {\kappa}>0$ when $x_1\in C_1(h/2)$, we see that the flow $S^t x$ will hit $C_1(h/2)$ in a penetrating manner. Therefore by Lemma \[Lm:FiniteTimeComparisonGradientFlowANDSGDPerturbation\] we see that for such initial point $x$ we have the following. \[Lm:FirstTravelTimeFinite\] There exists some ${\varepsilon}_0>0$ uniformly for all $x$ with $H> F(x)\geq F(O_1)+h/2$, such that for all $0<{\varepsilon}<{\varepsilon}_0$, there exist some finite $C>0$ independent of ${\varepsilon}$ such that $$\label{Eq:TravelTimeFinite} {\mathbf E}_x \tau_1\leq C \ .$$ Now we are ready to state and prove our main Theorem. \[Thm:MajorResultSGDPerturbationConvergenceTime\] Consider the process $Y_t^{\varepsilon}$ defined as in . Suppose the Morse function $F(x)$ have $k$–strong saddle points (according to Definition \[Def:StrongSaddleProperty\]) $O_1$, ..., $O_k$ inside the basin $U(x^*)$, such that $F(O_1)>...>F(O_k)$. Let ${\gamma}_1>0$ be chosen as in Definition \[Def:StrictSaddleProperty\]. Let the initial condition $Y_0=x\in U(x^*)$ be such that $F(x)>F(O_1)$. Let $x^*$ be the unique local minimum of $F$ within $U(x^*)$ such that $F(x^*)<F(O_k)$. Then we have \(i) For any small $\rho>0$, with probability at least $1-\rho$, the process $Y_t^{\varepsilon}$ in converges to the minimizer $x^*$ for sufficiently small ${\varepsilon}$ after passing through all $k$ saddle points $O_1$, ..., $O_k$; \(ii) Consider the stopping time $T_x^{\varepsilon}$ defined in . Then as ${\varepsilon}{\downarrow}0$, conditioned on the above convergence of $Y_t^{\varepsilon}$ to $x^*$, we have $$\label{Eq:TotalExitTimeAsymptoticSGDPerturbationManySaddle} \lim{\limits}_{{\varepsilon}{\rightarrow}0}\dfrac{{\mathbf E}T_x^{\varepsilon}}{\ln ({\varepsilon}^{-1})}\leq \dfrac{k}{{\gamma}_1} \ .$$ *Proof.* By the strong Markov property of the process $Y_t^{\varepsilon}$, we see that the process $\widetilde{Y}^{\varepsilon}_s=Y^{\varepsilon}_{\tau_1+s}$ can be viewed as an independent copy of the process $Y_s^{\varepsilon}$ starting from $Y_0^{\varepsilon}=Y_{\tau_1}^{\varepsilon}$. By part (ii) of our Lemma \[Lm:GeometricLemma\], we can consider two cases, that either $Y^{\varepsilon}_{\tau_1}\in U_1\cup {\partial}U_1$ or $Y^{\varepsilon}_{\tau_1}\not\in U_1\cup {\partial}U_1$ but $Y^{\varepsilon}_{\tau_1}\in C_1(h/2)$. Let us consider first the case when $Y^{\varepsilon}_{\tau_1}\in U_1\cup {\partial}U_1$. Let $\mu>0$ be chosen as in Lemma \[Lm:GeometricLemma\]. Let $$Q_1^\mu=\{x\in {\partial}V_1 \ , \ \text{dist}(x, {\partial}V_{1, U_1\cup {\partial}U_1{\rightarrow}\text{out}})<\mu\} \ .$$ Let $\widetilde{{\sigma}}_1=\inf\{t\geq \tau_1: Y_t^{\varepsilon}\in {\partial}V_1\}$. Then by Theorem \[Thm:Kifer1981Strengthened\] equation we see that $$\lim{\limits}_{{\varepsilon}{\rightarrow}0}{\mathbf P}_x(Y_{\widetilde{{\sigma}}_1}^{\varepsilon}\in Q_1^\mu | Y_{\tau_1}^{\varepsilon}\in U_1\cup {\partial}U_1)=1 \ .$$ From the above we see that for any small $q>0$ there exist some ${\varepsilon}_0>0$ such that for any $0<{\varepsilon}<{\varepsilon}_0$ we have $${\mathbf P}_x(Y_{\widetilde{{\sigma}}_1}^{\varepsilon}\in Q_1^\mu| Y_{\tau_1}^{\varepsilon}\in U_1\cup {\partial}U_1)\geq 1-q \ .$$ By part (c) of our Lemma \[Lm:GeometricLemma\] we know that for all $x\in Q_1^\mu$, we have $F(x)\leq F(O_1)-h$. This implies that $\{Y_{\widetilde{{\sigma}}_1}^{\varepsilon}\in Q_1^\mu\}\subseteq \{\widetilde{{\sigma}}_1\geq {\sigma}_1\}$. Therefore we have $${\mathbf P}_x(\widetilde{{\sigma}}_1\geq {\sigma}_1 | Y_{\tau_1}^{\varepsilon}\in U_1\cup {\partial}U_1)\geq 1-q \ .$$ From Theorem \[Thm:Kifer1981Strengthened\] equation we see that $$\lim{\limits}_{{\varepsilon}{\rightarrow}0} \dfrac{{\mathbf E}_x (\widetilde{{\sigma}}_1-\tau_1| Y_{\tau_1}^{\varepsilon}\in U_1\cup {\partial}U_1)} {\ln({\varepsilon}^{-1})}\leq \dfrac{1}{{\gamma}_1} \ .$$ Since $\lim{\limits}_{{\varepsilon}{\rightarrow}0}{\mathbf P}_x(\widetilde{{\sigma}}_1\geq {\sigma}_1 | Y_{\tau_1}^{\varepsilon}\in U_1\cup {\partial}U_1)=1$, we have $$\lim{\limits}_{{\varepsilon}{\rightarrow}0} \dfrac{{\mathbf E}_x ({\sigma}_1-\tau_1| \widetilde{{\sigma}}_1\geq {\sigma}_1 \ , \ Y_{\tau_1}^{\varepsilon}\in U_1\cup {\partial}U_1)} {\ln({\varepsilon}^{-1})}\leq \dfrac{1}{{\gamma}_1} \ .$$ From here, taking into account that equations and are uniform bounds with respect to all $x$ such that $H>F(x)\geq F(O_1)+h/2$, we have, for any $r>0$, there exist some ${\varepsilon}_0>0$, as $0<{\varepsilon}<{\varepsilon}_0$, we have $$\label{Eq:Sigma2-Tau1ConditionalPart1} \dfrac{\sup{\limits}_{H>F(y)\geq F(O_1)+h/2} {\mathbf E}_y ({\sigma}_1-\tau_1| \widetilde{{\sigma}}_1\geq {\sigma}_1 \ , \ Y_{\tau_1}^{\varepsilon}\in U_1\cup {\partial}U_1)} {\ln({\varepsilon}^{-1})}\leq \dfrac{1}{{\gamma}_1}+r \ .$$ If $\widetilde{{\sigma}}_1 < {\sigma}_1$, then since $Y_{\widetilde{{\sigma}}_1}^{\varepsilon}\in {\partial}V_1$, we can separately consider cases when $Y_{\widetilde{{\sigma}}_1}^{\varepsilon}\in D(F(O_1)+h/2, \infty)\cup C_1(h/2)$ or $Y_{\widetilde{{\sigma}}_1}^{\varepsilon}\not \in D(F(O_1)+h/2, \infty)\cup C_1(h/2)$. If $Y_{\widetilde{{\sigma}}_1}^{\varepsilon}\in D(F(O_1)+h/2, \infty)\cup C_1(h/2)$, then together with the strong Markov property of $Y_t^{\varepsilon}$, we can apply a similar argument as above as we did for $Y_0^{\varepsilon}=x$, so that for some ${\varepsilon}_0>0$ we have $$\begin{array}{ll} & \sup{\limits}_{H>F(y)\geq F(O_1)+h/2} {\mathbf E}_y({\sigma}_1-\widetilde{{\sigma}}_1|Y_{\widetilde{{\sigma}}_1}\in D_1(F(O_1)+h/2, \infty)\cup C_1(h/2), \widetilde{{\sigma}}_1<{\sigma}_1, Y_{\tau_1}^{\varepsilon}\in U_1\cup {\partial}U_1) \\ \leq & \sup{\limits}_{y\in {\partial}V_1, H>F(y)\geq F(O_1)+h/2}{\mathbf E}_y \tau_1+\sup{\limits}_{H>F(y)\geq F(O_1)+h/2}{\mathbf E}_y({\sigma}_1-\tau_1) \\ \leq & C+\sup{\limits}_{H>F(y)\geq F(O_1)+h/2}{\mathbf E}_y({\sigma}_1-\tau_1) \end{array}$$ for all $0<{\varepsilon}<{\varepsilon}_0$. Here we have used Lemma \[Lm:FirstTravelTimeFinite\]. Thus for any $r>0$ there exist some ${\varepsilon}_0>0$ so that for any $0<{\varepsilon}<{\varepsilon}_0$ we have $$\label{Eq:Sigma2-Tau1ConditionalPart2} \begin{array}{ll} &\dfrac{\sup{\limits}_{H>F(y)\geq F(O_1)+h/2}{\mathbf E}_y ({\sigma}_1-\tau_1| Y_{\widetilde{{\sigma}}_1}\in D_1(F(O_1)+h/2, \infty)\cup C_1(h/2) , \widetilde{{\sigma}}_1<{\sigma}_1 , Y_{\tau_1}^{\varepsilon}\in U_1\cup {\partial}U_1)} {\ln({\varepsilon}^{-1})} \\ \leq & \dfrac{\sup{\limits}_{y\in {\partial}V_1, H>F(y)\geq F(O_1)+h/2}{\mathbf E}_y(\widetilde{{\sigma}}_1-\tau_1|Y_{\tau_1}^{\varepsilon}\in U_1\cup {\partial}U_1)}{\ln({\varepsilon}^{-1})} +\dfrac{\sup{\limits}_{y\in {\partial}V_1, F(y)\geq F(O_1)+h/2}{\mathbf E}_y \tau_1}{\ln({\varepsilon}^{-1})} \\ & \ \ \ \ \ +\dfrac{\sup{\limits}_{H>F(y)\geq F(O_1)+h/2}{\mathbf E}_y({\sigma}_1-\tau_1)}{\ln({\varepsilon}^{-1})} \\ \leq & \dfrac{1}{{\gamma}_1}+r+\dfrac{\sup{\limits}_{H>F(y)\geq F(O_1)+h/2}{\mathbf E}_y({\sigma}_1-\tau_1)}{\ln({\varepsilon}^{-1})} \ . \end{array}$$ Here we have used equation of Theorem \[Thm:Kifer1981Strengthened\], Lemma \[Lm:FirstTravelTimeFinite\], as well as strong Markov property of the process $Y_t^{\varepsilon}$. Let us then look at the case when $Y_{\widetilde{{\sigma}}_1}^{\varepsilon}\not\in D(F(O_1)+h/2, \infty)\cup C_1(h/2)$. In this case, we construct a domain $D$ such that $D=\bigcup{\limits}_{x, x\in C_1(F(O_1)+h/2), x\not\in U_1}{\mathcal T}(x)$, where ${\mathcal T}(x)$ is the tubular neighborhood in part (iv) of Lemma \[Lm:GeometricLemma\] (see Figure 1). The domain $D$ consists of flow lines of , and connects $C_1(h)$ with $C_1(-h)$. (It may have several disconnected components, yet we pick only of of these components.) Moreover, along the flow lines in $D$, for any $z\in D$, we have $|{\nabla}F(z)|\geq {\kappa}$. The condition $Y_{\widetilde{{\sigma}}_1}^{\varepsilon}\not\in D(F(O_1)+h/2, \infty)\cup C_1(h/2)$ but $Y_{\widetilde{{\sigma}}_1}^{\varepsilon}\in {\partial}V_1$ implies that $Y_{\widetilde{{\sigma}}_1}^{\varepsilon}\in D$ (see Figure 1). By Lemma \[Lm:FiniteTimeComparisonGradientFlowANDSGDPerturbation\], we have, for any $r>0$, there exist some ${\varepsilon}_0>0$, for any $0<{\varepsilon}<{\varepsilon}_0$ we have $$\label{Eq:Sigma2-Tau1ConditionalPart3} \begin{array}{ll} &\dfrac{\sup{\limits}_{H>F(y)\geq F(O_1)+h/2}{\mathbf E}_y ({\sigma}_1-\tau_1| Y_{\widetilde{{\sigma}}_1}^{\varepsilon}\not \in D_1(F(O_1)+h/2, \infty)\cup C_1(h/2) , \widetilde{{\sigma}}_1<{\sigma}_1 , Y_{\tau_1}^{\varepsilon}\in U_1\cup {\partial}U_1)} {\ln({\varepsilon}^{-1})} \\ \leq & r \ . \end{array}$$ Equations , and settle all possible cases when $Y_{\tau_1}^{\varepsilon}\in U_1\cup {\partial}U_1$. Let us then turn to the case when $Y_{\tau_1}^{\varepsilon}\not\in U_1\cup {\partial}U_1$. Notice that by definition of $\tau_1$, we have $Y_{\tau_1}^{\varepsilon}\in C_1(h/2)$. Hence from the above construction of the domain $D$ we can then apply Lemma \[Lm:FiniteTimeComparisonGradientFlowANDSGDPerturbation\] again so that for any $r>0$, there exist some ${\varepsilon}_0>0$, for any $0<{\varepsilon}<{\varepsilon}_0$ we have $$\label{Eq:Sigma2-Tau1ConditionalPart4} \dfrac{\sup{\limits}_{H>F(y)\geq F(O_1)+h/2}{\mathbf E}_y ({\sigma}_1-\tau_1| Y_{\widetilde{{\sigma}}_1}^{\varepsilon}\not\in U_1\cup {\partial}U_1)} {\ln({\varepsilon}^{-1})} \leq r \ .$$ Combining equations , , , we see that, for any $r>0$, there exist some ${\varepsilon}_0>0$ so that for any $0<{\varepsilon}<{\varepsilon}_0$ we have $$\label{Eq:Sigma2-Tau1ConditionalCombined} \begin{array}{ll} &\dfrac{\sup{\limits}_{H>F(y)\geq F(O_1)+h/2}{\mathbf E}_y({\sigma}_1-\tau_1)}{\ln({\varepsilon}^{-1})} \\ \leq & \dfrac{\sup{\limits}_{H>F(y)\geq F(O_1)+h/2}{\mathbf E}_y ({\sigma}_1-\tau_1| Y_{\tau_1}^{\varepsilon}\not\in U_1\cup {\partial}U_1) \cdot {\mathbf P}_y(Y_{\tau_1}^{\varepsilon}\not\in U_1\cup {\partial}U_1)} {\ln({\varepsilon}^{-1})} \\ & + \dfrac{\sup{\limits}_{H>F(y)\geq F(O_1)+h/2} {\mathbf E}_y ({\sigma}_1-\tau_1| \widetilde{{\sigma}}_1\geq {\sigma}_1 \ , \ Y_{\tau_1}^{\varepsilon}\in U_1\cup {\partial}U_1) \cdot {\mathbf P}_y( \widetilde{{\sigma}}_1\geq {\sigma}_1 \ , \ Y_{\tau_1}^{\varepsilon}\in U_1\cup {\partial}U_1)} {\ln({\varepsilon}^{-1})} \\ & + \dfrac{\sup{\limits}_{H>F(y)\geq F(O_1)+h/2} \begin{array}{c} {\mathbf E}_y ({\sigma}_1-\tau_1| Y_{\widetilde{{\sigma}}_1}\in D_1(F(O_1)+h/2, \infty)\cup C_1(h/2) , \widetilde{{\sigma}}_1< {\sigma}_1 , Y_{\tau_1}^{\varepsilon}\in U_1\cup {\partial}U_1) \\ \cdot {\mathbf P}_y(Y_{\widetilde{{\sigma}}_1}\in D_1(F(O_1)+h/2, \infty)\cup C_1(h/2), \widetilde{{\sigma}}_1< {\sigma}_1, Y_{\tau_1}^{\varepsilon}\in U_1\cup {\partial}U_1) \end{array}} {\ln({\varepsilon}^{-1})} \\ & + \dfrac{\sup{\limits}_{H>F(y)\geq F(O_1)+h/2} \begin{array}{c} {\mathbf E}_y ({\sigma}_1-\tau_1| Y_{\widetilde{{\sigma}}_1}^{\varepsilon}\not \in D_1(F(O_1)+h/2, \infty)\cup C_1(h/2), \widetilde{{\sigma}}_1< {\sigma}_1 , Y_{\tau_1}^{\varepsilon}\in U_1\cup {\partial}U_1) \\ \cdot {\mathbf P}_y(Y_{\widetilde{{\sigma}}_1}^{\varepsilon}\not \in D_1(F(O_1)+h/2, \infty)\cup C_1(h/2), \widetilde{{\sigma}}_1< {\sigma}_1 , Y_{\tau_1}^{\varepsilon}\in U_1\cup {\partial}U_1) \end{array}} {\ln({\varepsilon}^{-1})} \\ \leq & r+\left(r+\dfrac{1}{{\gamma}_1}\right)+\left[ \left(\dfrac{1}{{\gamma}_1}+r+\dfrac{\sup{\limits}_{H>F(y)\geq F(O_1)+h/2}{\mathbf E}_y({\sigma}_1-\tau_1)}{\ln({\varepsilon}^{-1})}\right) +r \right]\cdot q \ . \end{array}$$ Since $q>0$ can be picked arbitrarily small as ${\varepsilon}>0$ is small, we see from that we finally have $$\label{Eq:Sigma2-Tau1FinalEstimate} \lim{\limits}_{{\varepsilon}{\rightarrow}0}\dfrac{\sup{\limits}_{H>F(y)\geq F(O_1)+h/2}{\mathbf E}_y({\sigma}_1-\tau_1)}{\ln({\varepsilon}^{-1})} \leq \dfrac{1}{{\gamma}_1} \ .$$ Notice that we have $F(Y^{\varepsilon}_{{\sigma}_1})\leq F(O_1)-h$. Due to strong Markov property, given $Y_{{\sigma}_1}^{\varepsilon}$, the process $\widetilde{Y}_s^{\varepsilon}=Y_{{\sigma}_1+s}^{\varepsilon}$ is an independent copy of $Y_t^{{\varepsilon}}$. Therefore we can iteratively make use of . From Lemma \[Lm:FiniteTimeComparisonGradientFlowANDSGDPerturbation\] we know that, given any small $\rho>0$, as ${\varepsilon}>0$ is small, with probability greater or equal than $1-\rho$, $Y_{\tau_2}^{\varepsilon}$ lie on $C_2(h/2)$, i.e., $F(Y_{\tau_2}^{\varepsilon})=F(O_2)+h/2$. Similarly, given any small $\rho>0$, as ${\varepsilon}>0$ is small, with probability greater or equal than $1-\rho$, $Y_{{\sigma}_2}^{\varepsilon}$ lie on $C_2(-h)$, i.e., $F(Y_{{\sigma}_2}^{\varepsilon})=F(O_2)-h$. Thus by running the above argument iteratively, we see that for any $\rho>0$ sufficiently small, there exist some ${\varepsilon}_0>0$ such that for any $0<{\varepsilon}<{\varepsilon}_0$, with probability greater or equal than $1-\rho$, the random variable $Y_{{\sigma}_k}^{\varepsilon}$ satisfy $F(Y_{{\sigma}_k}^{\varepsilon})=F(O_k)-h$. Conditioned on this event, we have $$\lim{\limits}_{{\varepsilon}{\rightarrow}0}\dfrac{{\mathbf E}_x T_x^{\varepsilon}}{\ln({\varepsilon}^{-1})} \leq \dfrac{k}{{\gamma}_1} \ .$$ So we arrive at the conclusion of this Theorem. $\square$ Taking into account that $\tau^{\beta}$ in satisfies $\tau^{\beta}=T_x^{\sqrt{{\beta}}}/{\beta}$, we see that we have the following corollary in regards to the diffusion approximation of the stochastic gradient descent (Section 1.3). \[Corollary:MajorResultSGDConvergenceTime\] Consider the process $X_t$ defined as in and let $F(\bullet)$ satisfy the landscape conditions as in Theorem \[Thm:MajorResultSGDPerturbationConvergenceTime\], and also suppose the noise in is sufficiently omnidirectional in the sense that $\sigma(x)\sigma^T(x) $ is uniformly positive definite. Let $x^*$ be the unique local minimum of $F$ as in Theorem \[Thm:MajorResultSGDPerturbationConvergenceTime\], then \(i) For any small $\rho>0$, with probability at least $1-\rho$, SGD diffusion process $X_t$ in converges to the minimizer $x^*$ for sufficiently small ${\beta}$ after passing through all $k$ saddle points $O_1$, ..., $O_k$; \(ii) Consider the stopping time $\tau^{\beta}$ defined in . Then as ${\beta}{\downarrow}0$, conditioned on the above convergence of $SGD$ diffusion process $X_t$, we have $$\label{Eq:TotalExitTimeAsymptoticSGDManySaddle} \lim{\limits}_{{\beta}{\rightarrow}0}\dfrac{{\mathbf E}\tau^{\beta}}{{\beta}^{-1}\ln {\beta}^{-1}}\leq \dfrac{k}{2{\gamma}_1} \ .$$ We thank Professor Mark Freidlin from University of Maryland, College Park for reading the manuscript and for useful suggestions. The first author would like to thank University of Missouri for a startup fund that supports this work. <span>100</span> Arnold, V.I., Geometric Methods in the Theory of Ordinary Differential Equations, *Grundlehren der mathematischen Wissenschaften*, **250**, Springer, 1988. Bakhtin, Y., Exit asymptotics for small diffusion about an unstable equilibrium, *Stochastic Processes and their Applications*, **118** (2008), pp. 839–851. Bakhtin, Y., Noisy heteroclinic networks, *Probability Theory and Related Fields*, **150** (2011), no. 1–2, pp.1–42. Belitskii, G., Rayskin, V., On the Grobmann–Hartman Theorem in $\alpha$–Hölder class for Banach spaces. `https://www.ma.utexas.edu/mp_arc/c/11/11-134.pdf` Borkar, Vivek S., *Stochastic Approximation: A Dynamical Systems Viewpoint*, Cambridge University Press, 2008. Brin, M., Stuck, G.C., *Introduction to dynamical systems*, Cambridge University Press, 2002. Freidlin, M., Wentzell, A., *Random perturbations of dynamical systems*, Second Edition, Springer, 1998. Ge, R., Huang, F., Jin, C., Yuan, Y. Escaping from saddle points–online stochastic gradient descent for tensor decomposition. , (pp. 797–842), 2015. Katok, A., Hasselblatt, B., *Introduction to the modern theory of dynamical systems*, Encyclopaedia of Mathematics and its Applications, Vol 54, Cambridge University Press, Cambridge, 1995. Kifer, Y., The exit problem for small random perturbations of dynamical systems with a hyperbolic fixed point. *Israel Journal of Mathematics*, 40(1), pp. 74–96. Koralov, L., Random Perturbations of 2–Dimensional Hamiltonian Flows, *Probability Theory and Related Fields* **129**, pp 37–62, 2004. Lee, J. D., Simchowitz, M., Jordan, M. I., & Recht, B. Gradient descent only converges to minimizers. , (pp. 1246–1257), 2016. Li, C.J., Li, L., Qian, J., Liu, J.G., Batch Size Matters: A Diffusion Approximation Framework on Nonconvex Stochastic Gradient Descent. Submitted `arXiv:1705.07562[stat.ML]` Milnor, J., *Morse Lemma*, Princeton University Press, 1963. Monter, S.A.A., Bakhtin, Y., Normal forms approach to diffusion near hyperbolic equilibira, *Nonlinearity*, **24** (2011), pp.1883–1907. Pemantle, R. Nonconvergence to unstable points in urn models and stochastic approximations. , (pp. 698–712), 1990. Sun, J., Qu, Q., Wright, J., When are nonconvex problems not scary? Preprint `arXiv:1510.06096[math.OC]` On uniform estimates of mean exit time and exit distribution from a neighborhood of a strong saddle point. ========================================================================================================== In this Appendix we provide technical proof on uniform estimates of mean exit time and exit distribution from a neighborhood of a strong saddle point. These results are needed in Theorem \[Thm:Kifer1981Strengthened\] of Section 2. In this Appendix we adopt all notations and set–up of Section 2. We will let $O$ be the strong saddle point that we consider. First of all, we have (see @[StrengthenedHartmanGrobman]) the fact that the homeomorphism that deforms the dynamics on $U\cup {\partial}U$, where $U$ is an open neighborhood of the strong saddle point $O$, into a linear dynamics in the classical Hartman–Grobman Theorem (see @[Arnold] [§13]) can be taken to be $h$–Hölder continuous for some $0<h\leq 1$ that depends only on the Hessian ${\nabla}^2 F(O)$ at $O$. Let ${\Lambda}=-{\nabla}^2 F(O)$. Recall that ${\Lambda}$ has eigenvalues ${\lambda}_1={\lambda}_2=...={\lambda}_q>{\lambda}_{q+1}\geq ...\geq {\lambda}_p>0>-{\lambda}_{p+1}\geq...\geq -{\lambda}_n$. Our proof is based on the arguments in @[Kifer1981], @[BakhtinHeteroclinic] and @[MonterBakhtinNormalForm], and in fact it is a straightforward adaptation of the proof of Lemma 8.1 in @[BakhtinHeteroclinic]. We will have to put an assumption (see our Linerization Assumption of Section 1.3) that the the homeomorphism provided by the Hartman–Grobman Theorem can be taken to be ${\mathbf{C}}^{(2)}$, as in @[BakhtinHeteroclinic]. However, the homeomorphism provided by the Hartman–Grobman Theorem that maps the dynamics near a strong saddle point to linear dynamics needed in @[BakhtinHeteroclinic] can be weakened to a normal form condition as in @[MonterBakhtinNormalForm] (yet this work is only in dimension $2$). It is known that the validity of the ${\mathbf{C}}^{(2)}$ condition needs the so called non–resonance condition to hold (see, for example, the Sternberg linerization Theorem @[KatokHasselblatt] [Theorem 6.6.6]), which may not be satisfied for some algorithms that arise in statistical machine learning practice. Thus our Theorem \[Thm:Kifer1981Strengthened\] only covers a mildly general case of gradient flows. In the case when algorithms that arise in statistical machine learning practice have a strong saddle that does not admit ${\mathbf{C}}^{(2)}$ conjugacy (resonant case), we can make a similar argument and possibly extend it to higher dimensions as in @[MonterBakhtinNormalForm]. The work @[MonterBakhtinNormalForm] conveys the information that when $-{\nabla}F(x)$ (and in general the drift term in the dynamical system) does not admit a ${\mathbf{C}}^{(2)}$ conjugacy to linear flow near a saddle point, the exit time and exit distribution analysis heavily depends on the analysis of the normal form of the flow near that saddle point. We leave this thread of work to future investigations. Let us denote $$\label{Appendix:Eq:FirstNeighborhoodStableManifold} (A_1\cup O)_{[0,{\varepsilon})}=\{x: \text{dist}(x,A_1\cup O)<{\varepsilon}\} \ ,$$ and for $k=1,2,...$ we denote $$\label{Appendix:Eq:ArbitraryNeighborhoodStableManifold} (A_1\cup O)_{[{\varepsilon}^{1/2^{k-1}}, {\varepsilon}^{1/2^k})}=\{x: {\varepsilon}^{1/2^{k-1}}\leq \text{dist}(x,A_1\cup O)<{\varepsilon}^{1/2^k}\} \ .$$ We provide the following three Lemmas, which settle the proof of Theorem \[Thm:Kifer1981Strengthened\] in Section 2. \[Appendix:Lm:ExitTimeExitDistributionPart1\] (i) For any $r>0$, there exist some ${\varepsilon}_0={\varepsilon}_0(r)$ such that for any $0<{\varepsilon}<{\varepsilon}_0$ and any $x\in U\cup {\partial}U$ with $x\in (A_1\cup O)_{[0, {\varepsilon})}$ we have $${\mathbf E}\tau_x^{\varepsilon}\leq \left(\dfrac{1}{{\lambda}_1}+r\right)\ln({\varepsilon}^{-1}) \ .$$ \(ii) For any $\rho>0$ and $\mu>0$, there exist some ${\varepsilon}_0={\varepsilon}_0(\rho, \mu)$ such that for any $0<{\varepsilon}<{\varepsilon}_0$ and any $x\in U\cup {\partial}U$ with $x\in (A_1\cup O)_{[0, {\varepsilon})}$ we have $${\mathbf P}(Y^{\varepsilon}_{\tau_x^{\varepsilon}}\in Q^\mu)\geq 1-\rho \ .$$ *Proof*. If $x\in A_1\cup O$, then the proof of this lemma is more or less the same as in @[Kifer1981]. If $0<\text{dist}(x, A_1\cup O)<{\varepsilon}$, one can modify the proof in @[BakhtinHeteroclinic], and the argument is more or less the same as in the proof of the next Lemma, so that we refer to the proof of the next Lemma for more details. $\square$ \[Appendix:Lm:ExitTimeExitDistributionPart2\] (i) For any $k\in {\mathbb N}$ and any $r>0$, there exist some ${\varepsilon}_0={\varepsilon}_0(r,k)$ such that for any $0<{\varepsilon}<{\varepsilon}_0$ and any $x\in U\cup {\partial}U$ with $x\in (A_1\cup O)_{[{\varepsilon}^{1/2^{k-1}}, {\varepsilon}^{1/2^k})}$ we have $${\mathbf E}\tau_x^{\varepsilon}\leq \left(\dfrac{1}{2^{k-1}{\lambda}_1}+r\right)\ln({\varepsilon}^{-1}) \ .$$ \(ii) For any $k\in {\mathbb N}$ and any $\rho>0$, any $\mu>0$, there exist some ${\varepsilon}_0={\varepsilon}_0(\rho,\mu,k)$ such that for any $0<{\varepsilon}<{\varepsilon}_0$ and any $x\in U\cup {\partial}U$ with $x\in (A_1\cup O)_{[{\varepsilon}^{1/2^{k-1}}, {\varepsilon}^{1/2^k})}$ we have $${\mathbf P}(Y^{\varepsilon}_{\tau_x^{\varepsilon}}\in Q^\mu)\geq 1-\rho \ .$$ *Proof*. Let $V\supset U$ be an open neighborhood of $O$. Let $f: V{\rightarrow}{\mathbb R}^n$ be the ${\mathbf{C}}^{(2)}$ conjugacy that maps the flow $S^t x$ in within $V$ into linear dynamics $\dot{y}={\Lambda}y$, $f(O)=0\in {\mathbb R}^n$. Explicitly, the solution of the linear flow $\dot{y}={\Lambda}y$, $y(0)=y_0=(y_0^1,...,y_0^n)$ is given by $y(t)=(y^1(t),...,y^n(t))$ such that $y^l(t)=y_0^l e^{{\lambda}_l t}$ for $l=1,2,...,n$ [^3]. We will denote the linear flow corresponding to $S^t$ to be $S^t_{\Lambda}$, so that $f(S^t x)=S^t_{\Lambda}(f(x))$. We set ${\mathcal Y}_{\varepsilon}(t)=f(Y^{\varepsilon}_t)$. According to the argument that leads to (8.1) at the beginning of Section 8 of @[BakhtinHeteroclinic], we have $$\label{Appendix:Eq:BakhtinHeteroclinic8-1} d{\mathcal Y}_{\varepsilon}(t)={\Lambda}{\mathcal Y}_{\varepsilon}(t)+{\varepsilon}B({\mathcal Y}_{\varepsilon}(t))dW(t)+{\varepsilon}^2 C({\mathcal Y}_{\varepsilon}(t))dt \ ,$$ where $B$ and $C$ are continuous and bounded in a neighborhood $f(V)$ of the origin $0$, and $B$ is non–degenerate. From the assumption that $x\in (A_1\cup O)_{[{\varepsilon}^{1/2^{k-1}}, {\varepsilon}^{1/2^k})}$ we know that the initial condition $$\label{Appendix:Eq:BakhtinHeteroclinic8-2} {\mathcal Y}_{\varepsilon}(0)=y_0+{\varepsilon}^{1/2^k}\xi_{\varepsilon}\ ,$$ where $y_0\in f(A_1\cup O)$ and $\xi_{\varepsilon}$ is a point on $f(V)$ such that ${\varepsilon}^{1/2^k}\leq \text{dist}(\xi_{\varepsilon}, f(A_1\cup O))<1$. Let $\widetilde{V}\subset V$ and $W=f(V)$, $\widetilde{W}=f(\widetilde{V})$, so that $$\widetilde{W}=\{y\in {\mathbb R}^n: |y^j|\leq R, j=1,2,...,n\}\subset W$$ for some small $R>0$. Thus $y_0^l=0$ for all $l\leq p$. We would like to study the system with initial data given by . Let us define the stopping times $$t_{W,{\varepsilon}}=\inf\{t\geq 0: {\mathcal Y}_{\varepsilon}(t)\in {\partial}W\} \ ,$$ $$t_{\varepsilon}=\inf\{t\geq 0: \max(|{\mathcal Y}_{{\varepsilon}}^1(t)|,...,|{\mathcal Y}_{{\varepsilon}}^q(t)|)=R\}\wedge t_{W, {\varepsilon}} \ .$$ It turns out, and will be clear from the proof that follows, that ${\mathbf P}(t_{\varepsilon}<t_{W,{\varepsilon}}){\rightarrow}1 \text{ as } {\varepsilon}{\rightarrow}0$. Similarly as in deriving equation (8.6) of @[BakhtinHeteroclinic], we have the solution ${\mathcal Y}_{\varepsilon}(t)$ in mild form $${\mathcal Y}_{\varepsilon}(t)=e^{{\Lambda}t}{\mathcal Y}_{\varepsilon}(0)+{\varepsilon}e^{{\Lambda}t}\int_0^t e^{-{\Lambda}s}B({\mathcal Y}_{\varepsilon}(s))dW_s+{\varepsilon}^2 e^{{\Lambda}t}\int_0^t e^{-{\Lambda}s}C({\mathcal Y}_{\varepsilon}(s))ds \ .$$ Fix some number $a\in \left(0,\dfrac{1}{2^k}\right)$. For every $l=1,2,...,n$ let us define $$\tau_{\varepsilon}^l=\inf\{t: |{\mathcal Y}_{\varepsilon}^l(t)-(S^t_{\Lambda}y_0)^l|={\varepsilon}^{a}\} \ ,$$ and we define $$\tau_{\varepsilon}=\min\{\tau_{\varepsilon}^l: l=1,2,...,n\} \ .$$ In very much the same way as the derivation of Lemmas 8.2–8.4 (see Section 11 of @[BakhtinHeteroclinic]) we see that we have $$\label{Appendix:Eq:BakhtinHeteroclinicLemma8-2} \sup{\limits}_{t\geq 0}|{\mathcal Y}_{\varepsilon}(\tau_{\varepsilon}\wedge t)-S^{t\wedge \tau_{\varepsilon}}_{\Lambda}y_0|\stackrel{{\mathbf P}}{\rightarrow}0 \text{ as } {\varepsilon}{\rightarrow}0 \ ,$$ $$\label{Appendix:Eq:BakhtinHeteroclinicLemma8-3} \tau_{\varepsilon}\stackrel{{\mathbf P}}{\rightarrow}\infty \text{ as } {\varepsilon}{\rightarrow}0 \ ,$$ $$\label{Appendix:Eq:BakhtinHeteroclinicLemma8-4} {\mathbf P}(\tau_{\varepsilon}=\min(\tau_{\varepsilon}^1,...,\tau_{\varepsilon}^q)){\rightarrow}1 \text{ as
{'source': 'arXiv_out/1706'}