Breaking Reversibility Accelerates Langevin Dynamics for Global Non-Convex Optimization

Introduction

Consider the stochastic optimization problem:

Such problems with finite-sum structure arise in many applications, e.g. data analysis and machine learning ([GBCB16]). In this work, our primary focus will be non-convex objectives.

First-order methods such as gradient descent and stochastic gradient descent and their variants with momentum have been popular for solving such optimization problems (see e.g. [Ber15, Bub14]). These first-order methods admit some theoretical guarantees to locate a local minimizer, however their convergence depends strongly on the initialization and they do not have guarantees to visit a global minimum. The Langevin Dynamics (LD) is a variant of gradient descent where a properly scaled Gaussian noise is added to the gradients:

where $\eta>0$ is the stepsize, $\xi_{k}$ is a $d$-dimensional isotropic Gaussian noise with distribution $\mathcal{N}(0,I)$ where for every $k$, the noise $\xi_{k}$ is independent of the (filtration) past up to time $k$ and $\beta>0$ is called the inverse temperature parameter. With proper choice of parameters and under mild assumptions, LD algorithm converges to a stationary distribution that concentrates around a global minimum (see e.g. [BM99, GM91]) from an arbitrary initial point. Therefore, LD algorithm has a milder dependency on the initialization, visiting a global minimum eventually. The analysis of the convergence behavior of LD is often based on viewing LD as a discretization of the associated stochastic differential equation (SDE), known as the overdamped Langevin diffusion or the first-order Langevin diffusion,

where $B_{t}$ is a $d$-dimensional standard Brownian motion (see e.g. [GM91]). Under some mild assumptions on $F$, this SDE admits the following unique stationary distribution:

where $\Gamma>0$ is a normalizing constant. Note that overdamped Langevin diffusion is reversible in the sense that if $X(0)$ is distributed according to the stationary measure $\pi$, then $(X_{t})_{0\leq t\leq T}$ and $(X_{T-t})_{0\leq t\leq T}$ have the same law. It is known that the reversible Langevin algorithm converges to a local minimum in time polynomial with respect to parameters $\beta$ and $d$, the intuition being that the expectation of the iterates follows the gradient descent dynamics which converges to a local minimum (see e.g. [ZLC17, FGQ97]). It is also known that once Langevin algorithms arrive to a neighborhood of a local optimum, they can spend exponentially many iterations in dimension to escape from the basin of attraction of this local minimum. This behavior is known as “metastability” and has been studied well (see e.g. [BGK05, BGK04, Ber13]).

Recently, [TLR18] provided a finer characterization of this metastability phenomenon. They showed that for a given local optimum $x_{\ast}$, with high probability and arbitrary initialization, either LD iterates arrive at a point outside an $\varepsilon$-neighborhood of this local minimum within a recurrence time $\mathcal{T}_{\text{rec}}=\mathcal{O}\left(\frac{1}{m}\log(\frac{1}{\varepsilon})\right)$, where $m$ is smallest eigenvalue of the Hessian $\nabla^{2}F(x_{\ast})$ at the local minimum or they enter this $\varepsilon$-neighborhood by the recurrence time and stay there until a potentially exponentially long escape time $\mathcal{T}_{\text{esc}}$. The escape time $\mathcal{T}_{\text{esc}}$ measures how quickly the LD algorithm can get away from a given neighborhood around a local minimum, therefore it can be viewed as a measure of the effectiveness of LD for the search of a global minimizer, whereas the recurrence time $\mathcal{T}_{\text{rec}}$ can be viewed as the order of the time-scale for which search for local minima in the basin of attraction of that minimum happens.

One popular non-reversible variant of overdamped Langevin that can improve its performance in practice for a variety of applications (Section 4 in [LNP13]) is based on the underdamped Langevin diffusion, also known as the second-order Langevin diffusion ([Kra40]),

where $(\xi_{k+1},\xi^{\prime}_{k+1})$ is a $2d$-dimensional centered Gaussian vector so that $(\xi_{j},\xi^{\prime}_{j})$ are i.i.d. and independent of the initial condition, and for any fixed $j$, the random vectors $((\xi_{j})_{1},(\xi^{\prime}_{j})_{1})$, $((\xi_{j})_{2},(\xi^{\prime}_{j})_{2})$, $\ldots$, $((\xi_{j})_{d},(\xi^{\prime}_{j})_{d})$ are i.i.d. with the covariance matrix:

where $\psi_{0}(t)=e^{-\gamma t}$ and $\psi_{k+1}(t)=\int_{0}^{t}\psi_{k}(s)ds$ for every $k\geq 0$. Recent work [GGZ18] showed that ULD admits better non-asymptotic performance guarantees compared to known guarantees for LD in the context of non-convex optimization when the objective satisfies a dissipativity condition. Recent work also showed that ULD or alternative discretizations of the underdamped diffusion can sample from the Gibbs distribution more efficiently than LD when $F$ is globally strongly convex (see e.g. [CCBJ18, DRD20, MS17]) or strongly convex outside a compact set (see e.g. [CCA+18]).

The second non-reversible variant of overdamped Langevin involves adding a drift term:

where $J\neq 0$ is a $d\times d$ anti-symmetric matrix, i.e. $J^{T}=-J$ and $I$ is the $d\times d$ identity matrix, and $B_{t}$ is a standard $d$-dimensional Brownian motion. It can be shown that such a drift preserves the stationary distribution (1.3) (Gibbs distribution) of the overdamped Langevin dynamics, and it can lead to a faster convergence to the stationary distribution than the reversible Langevin diffusion (the case $J=0$), see e.g. [HHMS93, HHMS05, LNP13, Pav14, GM16] for details. Algorithms based on (1.9) have been applied to sampling, see e.g. [FSS20, RBS16, RBS15, DLP16, DPZ17], and non-convex optimization, see e.g. [HWG+20]. The Euler discretization of (1.9) leads to

which we refer to as the non-reversible Langevin dynamics (NLD).

Contributions. In this paper, we investigate the metastability behavior of non-reversible Langevin algorithms for non-convex objectives. We extend the results of [TLR18] to non-reversible Langevin dynamics and show that for a given local minimum that is within an arbitrary distance $r$ from the initialization, with high probability, either ULD trajectory ends up somewhere outside an $\varepsilon$-neighborhood of this local minimum within a recurrence time $\mathcal{T}_{\text{rec}}^{U}=\mathcal{O}\left(\frac{|\log(m)|}{\sqrt{m}}\log(r/\varepsilon)\right)$ or they enter this neighborhood by the recurrence time and stay there for a potentially exponentially long escape time. The analogous result shown in [TLR18] for reversible LD requires a recurrence time of $\mathcal{T}_{\text{rec}}=\mathcal{O}\left(\frac{1}{m}\log(r/\varepsilon)\right)$. This shows that underdamped dynamics requires a smaller recurrence time by a square root factor in $m$ (ignoring a $\log(m)$ factor). The difference is significant as the smallest eigenvalue $m$ of the Hessian matrix at a local optimum can be very small in a number of applications, including deep learning (see e.g. [CCS+17, SBL16]). Since the recurrence time can be viewed as a measure of the efficiency of the search of a local minimum [TLR18], our results suggest that ULD operates on a faster time-scale to locate a local minimum. Similar results are obtained for NLD. In order to obtain the results, we first give a refined characterization of the dynamics around a local minimum by linearizing the gradients. The analysis here is more complicated compared to the LD case in [TLR18] due to non-reversibility, and requires us to develop new estimates, e.g. Lemma 2, where the eigenvalue and the norm estimates require a significant amount of work because the forward iterations correspond to non-symmetric matrices $H_{\gamma}$ (defined in (2.5)) and achieving the acceleration behavior requires careful estimates. The analysis here also requires us to establish novel uniform $L^{2}$ bounds for NLD in both continuous and discrete times.

In addition, we consider the mean exit time from the basin of attraction of a local minimum for non-reversible algorithms. We focus on the double-well example which has been the recent focus of the literature [BR16, LMS19] as it is the simplest non-convex function that gives intuition about the more general case and for which mean exit time has been studied in continuous time. Our analysis shows that non-reversible dynamics can exit the basin of attraction of a local minimum faster under some conditions and characterizes the improvement for both ULD and NLD compared to LD when the parameters of these algorithms are chosen appropriately. These results support the numerical evidence that non-reversible algorithms can explore the state space more efficiently [CDC15, CFG14, GM16] and bridges a gap between the theory and practice of Langevin algorithms.

Other related work. Langevin dynamics has been studied under simulated annealing algorithms in the optimization, physics and statistics literature and its asymptotic convergence guarantees are well known (see e.g. [Gid85, Haj85, GM91, KGV83, BT93, BLNR15, BM99]). However, finite-time performance guarantees for LD have not been studied until more recently (see e.g. [Dal17, DM17]). Non-asymptotic performance guarantees for stochastic gradient versions have also been studied. See also e.g. [RRT17, ZLC17, CDT20] for related results. [XCZG18] shows that it suffices to have $\mathcal{O}(nd/(\lambda\varepsilon))$ gradient evaluations or $\mathcal{O}(d^{7}/(\lambda^{5}\varepsilon^{5}))$ stochastic gradient evaluations to compute an almost minimizer where $\lambda$ is a spectral gap parameter that is exponentially small in the dimension $d$ and $\varepsilon$ is the target accuracy. These results improve upon the existing results from the seminal work of [RRT17]. [EMS18] also considered Euler discretization of general dissipative diffusions in the non-convex setting, proved a $1/\varepsilon^{2}$ convergence rate, showing that different diffusions are suitable for minimizing different convex/non-convex objective functions $f$. Their expected suboptimality bound also generalizes the results in [RRT17]. See also [NŞR19] for non-asymptotic guarantees for non-convex optimization using Lévy-driven Langevin dynamics proposed in [Şim17].

Main results

In this section, we will study the recurrence time $\mathcal{T}_{\text{rec}}^{U}$ of underdamped Langevin dynamics (ULD), and the corresponding time-scale $\mathcal{T}_{\text{rec}}^{J}$ for non-reversible Langevin dynamics (NLD). We will show that recurrence time of underdamped and non-reversible Langevin algorithms will improve upon that of reversible Langevin algorithms in terms of its dependency to the smallest eigenvalue of the Hessian at a local minimum. For non-convex optimizations, our results suggest that for ULD and NLD, searching for a local minimum happens on a faster time scale compared to the reversible LD. For the rest of the paper, we impose the following assumptions.

The functions $f(\cdot,z)$ are twice continuously differentiable, non-negative valued, and $|f(0,z)|\leq A$, $\left\|\nabla f(0,z)\right\|\leq B$, and $\left\|\nabla^{2}f(0,z)\right\|\leq C$, uniformly in $z\in\mathcal{Z}$ for some $A,B,C>0$.

The empirical risk $F(\cdot)$ is $(m,b)$-dissipative: $\langle x,\nabla F(x)\rangle\geq m\|x\|^{2}-b$.

The initialization satisfies $\|X_{0}\|\leq R:=\sqrt{b/m}$.

For the Hessian $H$ at a fixed local minimum of $F$ defined in (1.1), it is a $d\times d$ symmetric positive definite matrix with eigenvalues $\{\lambda_{i}\}_{i=1}^{d}$ in increasing order, i.e.

Recall the underdamped Langevin (1.7)-(1.8). Define

where we recall that $H$ is the Hessian matrix $\nabla^{2}F$ evaluated at the local minimum $x_{\ast}$. In the first lemma, we provide an estimate on $\|e^{-tH_{\gamma}}\|$. This is the key result that allows the underdamped dynamics to achieve faster rate compared with overdamped dynamics.

(i) If $\gamma\in(0,2\sqrt{m}$), then $\left\|e^{-tH_{\gamma}}\right\|\leq C_{\hat{\varepsilon}}e^{-\sqrt{m}(1-\hat{\varepsilon})t}$, where $C_{\hat{\varepsilon}}:=\frac{1+M}{\sqrt{m(1-(1-\hat{\varepsilon})^{2})}}$, and $\hat{\varepsilon}:=1-\frac{\gamma}{2\sqrt{m}}\in(0,1)$, where $m,M$ are defined in (2.2). (ii) If $\gamma=2\sqrt{m}$, then we have $\left\|e^{-tH_{\gamma}}\right\|\leq\sqrt{C_{H}+2+(m+1)^{2}t^{2}}\cdot e^{-\sqrt{m}t}$, where $C_{H}:=\max_{i:\lambda_{i}>m}\frac{(1+\lambda_{i})^{2}}{\lambda_{i}-m}$.

We investigate the behavior around local minima for the underdamped Langevin dynamics (1.7)-(1.8) by studying recurrence and escape times with the choice of the friction coefficient $\gamma=2\sqrt{m}$ which is optimal for $\|e^{-tH_{\gamma}}\|$. We first recall the Lambert W function $W(x)$ which is defined via the solution of the algebraic equation $W(x)e^{W(x)}=x$. When $-e^{-1}\leq x<0$, $W(x)$ has two branches, the upper branch $W_{0}(x)$ and the lower branch $W_{-1}(x)$, see e.g. [CGH+96].

Fix $\gamma=2\sqrt{m}$, $\delta\in(0,1)$ and $r>0$. For a given $\varepsilon$ satisfying $0<\varepsilon<\overline{\varepsilon}^{U}=\min\left\{\mathcal{O}(r),\mathcal{O}(m)\right\},$ we define the recurrence time

and the escape time $\mathcal{T}_{\text{esc}}^{U}:=\mathcal{T}_{\text{rec}}^{U}+\mathcal{T}$, for any arbitrary $\mathcal{T}>0$. Consider an arbitrary initial point $x$ for the underdamped Langevin dynamics and a local minimum $x_{\ast}$ at a distance at most $r$. Assume that the stepsize $\eta$ satisfies

for any realization of training data $z$, with probability at least $1-\delta$ with respect to the Gaussian noise, at least one of the following events will occur: (1) $\|X_{k}-x_{\ast}\|\geq\frac{1}{2}\left(\varepsilon+re^{-\sqrt{m}k\eta}\right)$ for some $k\leq\eta^{-1}\mathcal{T}_{\text{rec}}^{U}$; (2) $\|X_{k}-x_{\ast}\|\leq\varepsilon+re^{-\sqrt{m}k\eta}$ for every $\eta^{-1}\mathcal{T}_{\text{rec}}^{U}\leq k\leq\eta^{-1}\mathcal{T}_{\text{esc}}^{U}$.

The expressions of technical constants in the statement of Theorem 3, including $\overline{\varepsilon}^{U},\overline{\eta}^{U}$ and $\underline{\beta}^{U}$, can be found in the proof of Theorem 3 in the Supplementary File.

In many applications, the eigenvalues of the Hessian at local extrema often concentrate around zero and the magnitude of the smallest eigenvalue $m$ of the Hessian can be very small (see e.g. [CCS+17, SBL16]). In [TLR18], the overdamped Langevin algorithm is analyzed and the recurrence time $\mathcal{T}_{\text{rec}}=\mathcal{O}\left(\frac{1}{m}\log(\frac{r}{\varepsilon})\right)$, while our recurrence time $\mathcal{T}_{\text{rec}}^{U}=\mathcal{O}\left(\frac{|\log(m)|}{\sqrt{m}}\log(\frac{r}{\varepsilon})\right)$ for the underdamped Langevin algorithm, which has a square root factor improvement. Since the recurrence time can be viewed as a measure of the efficiency of the search of a local minimum, our result suggests that ULD require smaller recurrence time, so they operate on a faster time scale to locate a local minimum.

2 Non-reversible Langevin dynamics

We investigate the behavior around local minima for the non-reversible Langevin dynamics (1.10) by studying recurrence and escape times. One can expect that the convergence behavior of the non-reversible Langevin diffusion is controlled by the decay of $\left\|e^{-tA_{J}H}\right\|$ in time $t$, which is related to the real part of the eigenvalues $\lambda^{J}_{i}:=\text{Re}\left(\lambda_{i}(A_{J}H)\right)$ indexed with increasing order and their multiplicity. It has been shown that for any anti-symmetric matrix $J$, we have $m=\lambda_{1}\leq\lambda_{1}^{J}\leq\lambda_{d}^{J}\leq\lambda_{d}=M,$ and $m=\lambda_{1}=\lambda_{1}^{J}$ if a very special condition holds. See Theorem 3.3. in [HHMS93] for details. This suggests generically non-reversible Langevin leads to a faster exponential decay compared to reversible Langevin, i.e $\lambda_{1}^{J}>\lambda_{1}$. In addition, we have the following estimates: there exists a positive constant $C_{J}$ that depends on $J$ such that

Now we state the main result on the metastability of non-reversible Langevin dynamics (1.10).

and the escape time $\mathcal{T}_{\text{esc}}^{J}:=\mathcal{T}_{\text{rec}}^{J}+\mathcal{T}$ for any arbitrary $\mathcal{T}>0$. For any initial point $x$ and a local minimum $x_{\ast}$ at a distance at most $r$. Assume the stepsize

The expressions of technical constants in the statement of Theorem 4, including $\overline{\varepsilon}^{J},\overline{\eta}^{J}$ and $\underline{\beta}^{J}$, can be found in the proof of Theorem 4 in the Supplementary File.

One could also ask what is the choice of the matrix $J$ in NLD. A natural idea is to maximize the exponent $\lambda_{1}^{J}$ that appears in Equation (2.6), i.e., let $J_{opt}:=\arg\max_{J=-J^{T}}\lambda_{1}^{J}\,.$ A formula for $J_{opt}$ and an algorithm to compute it is known (see Fig. 1 in [LNP13]), however this is not practical to compute for optimization purposes as it requires the knowledge of the eigenvectors and eigenvalues of the matrix $H$ which is generally unknown in practice. Nevertheless, $J_{opt}$ gives information about the extent of acceleration that can be obtained. It is known that $\lambda_{1}^{J_{opt}}=\frac{\text{Tr}(H)}{d}$, as well as a characterization of the constants $C_{J_{opt}}$ and $n_{1}$ arising in Equation (2.6) when $J=J_{opt}$ (see Equation (46) in [LNP13]). We see that $md\leq\text{Tr}(H)\leq M(d-1)+m$ as the smallest and the largest eigenvalue of $H$ is $m$ and $M$. Therefore, we have

The acceleration is not possible (the ratio above is $1$) if and only if all the eigenvalues of $H$ are the same and are equal to $m$; i.e. when $M=m$ and $\text{Tr}(H)=md$. Otherwise, $J_{opt}$ can accelerate by a factor of $\frac{M(d-1)+m}{md}$ which is on the order of the condition number $\kappa:=M/m$ up to a constant $\frac{d-1}{d}$ which is close to one for $d$ large. In practice, one can also use some easily constructed choices of $J$ as suggested in the literature (see e.g. [HHMS93]), and run the NLD algorithm using $\alpha J$ (which is still anti-symmetric), where $\alpha$ is a constant that can be tuned and it represents the magnitude of non-reversible purturbations. For example, one can choose $J$ to be a circulant matrix, e.g.,

and this product is easy to implement by shifting the gradient vector in the memory by one unit to the left and one unit to the right and then taking the difference.

Exit time for non-reversible Langevin dynamics

For convergence to a small neighborhood of the global minimum, Langevin trajectory needs to not only escape from the neighborhood of a local optimum but also exit the basin of attraction of the current minimum and transit to the basin of attraction of other local minima including the global minima. In particular, the convergence rate to a global minimum is controlled by the mean exit time from the basin of attraction of a local minima in a potential landscape $F(\cdot)$ in (1.2). In this section we will show that non-reversible Langevin dynamics can lead to faster (smaller) exit times.

Here, $o_{\beta}(1)\rightarrow 0$ as $\beta\rightarrow\infty,$ $\det\mbox{Hess }F(x)$ stands for the determinant of the Hessian of $F$ at $x$, and $-\mu^{\ast}(\sigma)$ is the unique negative eigenvalue of the Hessian of $F$ at the saddle point $\sigma$. This formula is known as the Eyring-Kramers formula for reversible diffusions. Its rigorous proof was first obtained by [BGK04] by a potential analysis approach, and then by [HKN04] through Witten Laplacian analysis. We refer to [Ber13] for a survey on mathematical approaches to the Eyring-Kramers formula. We note that in many practical applications, for instance in the training of neural networks, the eigenvalues of the Hessian at local extrema concentrate around zero and the magnitude of the eigenvalues $m$ and $\mu^{\ast}(\sigma)$ can often be very small (see e.g. [SBL16, CCS+17]).

Denote $\Theta_{a_{1}\rightarrow a_{2}}^{\beta}$ as the first time of that the underdamped diffusion (1.4)–(1.5) starting from $a_{1}$ and hitting a small neighborhood of $a_{2}$. [BR16] (Remark 5.2) suggests that the expected exit time is:

That is, the mean exit time for the underdamped diffusion is smaller compared with that of the overdamped diffusion. Roughly speaking, the condition $\gamma+\mu^{\ast}(\sigma)<1$ says that if the curvature of the saddle point in the negative descent direction is not too steep (i.e. if $\mu^{\ast}(\sigma)<1$), we can choose $\gamma$ small enough to accelerate the exit time of the reversible Langevin dynamics. Intuitively speaking, it can be argued that the underdamped process can climb hills and explore the state space faster as it is less likely to go back to the recent states visited due to the momentum term (see e.g. [BR16]). For the discrete time dynamics, it is intuitive to expect that the exit time of the underdamped discrete dynamics is close to that of the continuous time diffusion when the step size is small [BGG17], and hence a similar result as (3.2) will hold for the discrete dynamics when $\gamma+\mu^{\ast}(\sigma)<1$.

2 Non-reversible Langevin dynamics

[LMS19] (Theorem 5.2) showed that the expected time of the non-reversible diffusion $X(t)$ in (1.9) starting from $a_{1}$ and hitting a small neighborhood of $a_{2}$ is given by

We have $\mu_{J}^{\ast}\geq\mu^{\ast}(\sigma)$. As a consequence,

The equality is attained if and only if $u$ is a singular vector of $J$ satisfying $Ju=0$.

Proposition 5 shows that if $J$ is not singular, the non-reversible dynamics is generically faster than the reversible dynamics in the sense of smaller mean exit times. This holds for the discrete dynamics as well, since the exit time for the discrete dynamics is close to that of the continuous dynamics for sufficiently small stepsizes, see e.g. [GM05].

Fix the antisymmetric matrix $J$, the temperature parameter $\beta$, and $\epsilon>0$. One can choose a sufficiently large $n$ and a constant $\bar{\eta}(\epsilon,n,\beta)$ so that for stepsize $\eta\leq\bar{\eta}(\epsilon,n,\beta)$, we have

It then follows from Proposition 5 that for large $\beta$ we have

provided that $(Su)_{i}\neq 0$ for some $i\in\{2,\ldots,d\}$ which occurs if and only if $u$ is a singular vector of $J$ satisfying $Ju=0$.

Numerical Illustrations

In practice, for the NLD algorithm, the matrix $J$ can be chosen as a random anti-symmetric matrix. For quadratic objectives, there is a formula for optimal $J$ matrix; see e.g. [LNP13]. For the ULD algorithm, we can take the parameter $\gamma=2\sqrt{m}$ as predicted by our theory (Lemma 2) for quadratics. On the top panel of Figure 1, we compare ULD and NLD to LD for the double well example with random initialization over 100 runs where $J$ is chosen randomly and $\gamma=2\sqrt{m}$. In this simple example, we observe NLD and ULD have smaller mean exit times (from a barrier) compared to LD.

In general, it is not easy to compare the theoretical performance of ULD and NLD algorithms. However, in some regimes, our theory predicts one is better than the other. For example, when the smallest eigenvalue $m$ is close to the largest eigenvalue $M$, NLD will not improve much upon LD, but ULD will improve upon LD if $m$ is small and ULD will be faster than NLD. In this case, ULD has better performance than NLD. On the bottom panel of Figure 1, we provide an example for training fully-connected neural networks on MNIST where ULD was faster when both methods were tuned.

Conclusion

Langevin Monte Carlo are powerful tools for sampling from a target distribution as well as for optimizing a non-convex objective. The classic Langevin dynamics (LD) is based on the first-order Langevin diffusion which is reversible in time. We studied the two variants that are based on non-reversible Langevin diffusions: the underdamped Langevin dynamics (ULD) and the Langevin dynamics with a non-symmetric drift (NLD). We showed that both ULD and NLD can improve upon the recurrence time for LD in [TLR18] and discussed the amount of improvement. We also showed that non-reversible variants can exit the basin of attraction of a local minimimum faster when the objective has two local minima separated by a saddle point and discussed the amount of improvement. By breaking the reversibility in the Langevin dynamics, our results quantify the improvement in performance and fill a gap between the theory and practice of non-reversible Langevin algorithms.

Acknowledgements and Disclosure of Funding

The authors thank four anonymous referees for helpful suggestions. The authors are very grateful to Emmanuel Gobet, Claudio Landim, Insuk Seo and Gabriel Stoltz for helpful comments and discussions. The authors also thank Yuanhan Hu for the help with numerical experiments. Xuefeng Gao acknowledges support from Hong Kong RGC Grants 24207015 and 14201117. Mert Gürbüzbalaban’s research is supported in part by the grants NSF DMS-1723085 and NSF CCF-1814888. Lingjiong Zhu is grateful to the support from the grant NSF DMS-1613164.

References

Appendix A Figures

Appendix B Proof of results in Section 2

Let $H$ be a symmetric positive definite matrix with eigenvalue decomposition $H=QDQ^{T}$, where $D$ is diagonal with eigenvalues in increasing order $m:=\lambda_{1}\leq\lambda_{2}\leq\cdots\leq\lambda_{d}=:M$ of the matrix $H$. Recall $H_{\gamma}$ from (2.5). Note that

Therefore $H_{\gamma}$ and $G_{\gamma}$ have the same eigenvalues. Due to the structure of $G_{\gamma}$, it can be seen that there exists a permutation matrix $P$ such that

with $i=1,2,\ldots,d$, and $T_{i}(\gamma)$ are $2\times 2$ block matrices with the eigenvalues:

We observe that $T_{\gamma}$ and $G_{\gamma}$ (and therefore $H_{\gamma}$) have the same eigenvalues and the eigenvalues of $T_{\gamma}$ are determined by the eigenvalues of the $2\times 2$ block matrices $T_{i}(\gamma)$.

Since $H_{\gamma}$ is unitarily equivalent to the matrix $T_{\gamma}$, i.e. there exists a unitary matrix $U$ such that $H_{\gamma}=UT_{\gamma}U^{*}$, we have $\left\|e^{-tH_{\gamma}}\right\|=\left\|Ue^{-tT_{\gamma}}U^{*}\right\|=\left\|e^{-tT_{\gamma}}\right\|$. Since $T_{\gamma}$ is a block diagonal matrix with $2\times 2$ blocks $T_{i}(\gamma)$ we have $\left\|e^{-tT_{\gamma}}\right\|=\max_{1\leq i\leq d}\left\|e^{-tT_{i}(\gamma)}\right\|$. Assume that $\gamma^{2}-4\lambda_{1}=\gamma^{2}-4m\leq 0$ so that the eigenvalues $\mu_{i,\pm}$ of $T_{i}(\gamma)$ (see Eqn. (B.2)) are real when $\gamma=2\sqrt{m}$ and complex when $\lambda<2\sqrt{m}$. Note that

We consider $\gamma\in(0,2\sqrt{m}]$. Depending on the value of $\lambda_{i}$ and $\gamma$, there are two cases:

and $\det G_{i}=i\sqrt{4\lambda_{i}-\gamma^{2}}$. We can compute that

where $\mbox{Imag}(a+ib):=ib$ denotes the imaginary part of a complex number. As a consequence, by taking componentwise absolute values

To finish the proof of Case 2, let $\gamma=2\sqrt{m}$. We compute

where we used (B.4) and (B.5) in the last inequality. We conclude from (B.3) for Case 2. ∎

B.2 Proof of Theorem 3

The main result we use to prove Theorem 3 is the following proposition. The proof of the following result will be presented later in Section B.2.2.

Assume $\gamma=2\sqrt{m}$. Fix any $r>0$ and

For any initial point $X(0)=x$ with $\|x-x_{\ast}\|\leq r$, and

We are now ready to complete the proof of Theorem 3.

Assume that $\gamma=2\sqrt{m}$. Let us compare the discrete dynamics (1.7)-(1.8) and the continuous dynamics (1.4)-(1.5). Define:

Notice that for any $k\eta\leq s<(k+1)\eta$,

provided that $\eta\leq\min\left\{1,\frac{\gamma}{\hat{K}_{2}}(d/\beta+\overline{A}/\beta),\frac{\gamma\lambda}{2\hat{K}_{1}},\frac{2}{\gamma\lambda}\right\}$, with $C_{v}^{d}$ defined in Lemma 10, where we applied Lemma 28. Hence, we have

Using Pinsker’s inequality, we obtain an upper bound on the total variation $\|\cdot\|_{TV}$:

Using a result about an optimal coupling (Theorem 5.2., [Lin92]), that is, given any two random elements $\mathcal{X},\mathcal{Y}$ of a common standard Borel space, there exists a coupling $\mathcal{P}$ of $\mathcal{X}$ and $\mathcal{Y}$ such that

Hence, given any $\beta>0$ and $K\eta\leq\mathcal{T}_{\text{esc}}^{U}$, we can choose

so that there is a coupling of $\left\{(V(k\eta),X(k\eta)):k=1,2,\ldots,K\right\}$ and $\left\{(V_{k},X_{k}):k=1,2,\ldots,K\right\}$ such that

Let us now complete the proof of Theorem 3. We need to show that

where $K=\lfloor\eta^{-1}\mathcal{T}_{\text{esc}}^{U}\rfloor$ and $\mathcal{A}:=\mathcal{A}_{1}\cap\mathcal{A}_{2}$, where

We can choose $\beta$ sufficiently large so that with probability at least $1-\delta/3$, we have either $\|X(t)-x_{\ast}\|\geq\varepsilon+re^{-\sqrt{m}t}$ for some $t\leq\mathcal{T}_{\text{rec}}^{U}$ or $\|X(t)-x_{\ast}\|\leq\varepsilon+re^{-\sqrt{m}t}$ for all $t\leq\mathcal{T}_{\text{esc}}^{U}$. Moreover, for any $K,\eta$ and $\beta$ satisfying the conditions of the theorem, there exists a coupling of $(X(\eta),\ldots,X(K\eta))$ and $(X_{1},\ldots,X_{K})$ so that with probability $1-\delta/3$, $X_{k}=X(k\eta)$ for all $k=1,2,\ldots,K$. Then, by (B.13) and (B.14), we get

On the event $\left\{(X(\eta),\ldots,X(K\eta))\in\mathcal{A}_{1}\right\}\cap\mathcal{B}$,

provided that (by applying Proposition 7 and Lemma 26) (with $\gamma=2\sqrt{m}$):

where the second inequality above used $M$-Lipschitz property of $\nabla F$ and the last inequality above used Lemma 28. By adding the above two inequalities (B.19) and (B.20) together, we get

By applying Gronwall’s inequality, we get

We have from Lemma 10 that for any $u>0$,

where $C_{v}^{c}$, $C_{x}^{c}$ are defined in Lemma 10. By Lemma 27, we have

Therefore, we can infer from (B.21) that with $K_{0}:=\lceil\eta^{-1}\mathcal{T}_{\text{rec}}^{U}\rceil$,

where the last inequality follows from (B.22), (B.23) and Lemma 27. We can choose $\eta\leq 1$ so that

so that the term in (B.24) is less than $\delta/6$, where $C_{v}^{c}$, $C_{x}^{c}$ are defined in Lemma 10, and then we choose $\beta$ so that

so that the term in (B.25) is also less than $\delta/6$, and we can choose $\eta$ so that $\eta\leq 1$ and

To complete the proof, let us work on the leading orders of the constants. For the sake of convenience, we hide the dependence on $M$ and $L$ and assume that $M,L=\mathcal{O}(1)$. We also assume that $C_{H}=\mathcal{O}(1)$. Recall that $0<\varepsilon\leq\min\{\overline{\varepsilon}_{1}^{U},\overline{\varepsilon}_{2}^{U},\overline{\varepsilon}_{3}^{U}\}$, where it is easy to check that It is easy to check that

where we used $m\leq M=\mathcal{O}(1)$ and

where we used the fact that $m+1\geq 2\sqrt{m}$. Hence, we can take

Moreover, $m\leq M=\mathcal{O}(1)$. Hence, we can take

and since $W_{-1}(-x)\sim\log(1/x)$ for $x\rightarrow 0^{+}$, and we assume $C_{H}=\mathcal{O}(1)$, we get

Next, we recall that stepsize $\eta$ satisfies $\eta\leq\min\{1,\overline{\eta}_{1}^{U},\overline{\eta}_{2}^{U},\overline{\eta}_{3}^{U},\overline{\eta}_{4}^{U}\}$ and it is easy to check that

Moreover, we have (note that $R=\sqrt{b/m}$ in the definition of $C_{x}^{c},C_{v}^{c}$)

together with $m\leq M=\mathcal{O}(1)$ implies that

where we used $C_{x}^{d}\leq\mathcal{O}\left(\frac{d+\beta}{\beta m^{2}}\right)$ and $C_{v}^{d}\leq\mathcal{O}\left(\frac{d+\beta}{\beta m}\right)$, and

where we used $\lambda=\Omega(m)$, $\overline{A}=\Omega(\beta)$, $K_{1}=\mathcal{O}(\frac{1}{\beta m})$, $K_{2}=\mathcal{O}(1)$, $\hat{K}_{1}=\mathcal{O}(\frac{1}{m})$, $\hat{K}_{2}=\mathcal{O}(1+\frac{d}{\beta}\sqrt{m})$, and the minimum between $\frac{m^{1/2}(d+\beta)}{dm^{1/2}+\beta}$ and $m^{5/2}$ is $m^{5/2}$. Hence, we can take

Finally, $\beta$ satisfies $\beta\geq\max\{\underline{\beta}_{1}^{U},\underline{\beta}_{2}^{U}\}$, and We have

where we used $e^{2(1+2\sqrt{m}+M)\eta}=e^{\mathcal{O}(\varepsilon)}=\mathcal{O}(1)$.

B.2.2 Proof of Proposition 7

In this section, we focus on the proof of Proposition 7. We adopt some ideas from [BG03, TLR18]. We recall $x_{\ast}$ is a local minimum of $F$ and $H$ is the Hessian matrix: $H=\nabla^{2}F(x_{\ast})$, and we write

where $\|\rho(Y(t))\|\leq\frac{1}{2}L\|Y(t)\|^{2}$ since the Hessian of $F$ is $L$-Lipschitz (Lemma 1.2.4. [Nes13]). Then, we have

We can write it in terms of matrix form as:

where $B_{t}^{(2)}$ is a $2d$-dimensional standard Brownian motion. Therefore, we have

Given $0\leq t_{0}\leq t_{1}$, we define the matrix flow

is a martingale. Before we proceed to the proof of Proposition 7, we state the following lemma, which will be used in the proof of Proposition 7.

For any $\theta\in\left(0,\frac{2m\sqrt{m}}{\gamma(2C_{H}m+4m+(m+1)^{2})}\right)$, and $h>0$ and any $(V(0),Y(0))$,

Finally, let us complete the proof of Proposition 7.

Since $\|Y(0)\|=\|X(0)-x_{\ast}\|\leq r$, we know that $\tau>0$. Fix some $\mathcal{T}_{\text{rec}}^{U}\leq t_{0}\leq t_{1}$, such that $t_{1}-t_{0}\leq\frac{1}{2\|H_{\gamma}\|}$. Then, for every $t\in[t_{0},t_{1}]$,

It follows that (with $e^{-1/2}\geq 1/2$)

where $c_{0}+c_{1}=\frac{1}{2}$ and $c_{0},c_{1}>0$. We will first bound the second term in (B.40) which will turn out to be zero, and then use Lemma 8 to bound the first term in (B.40).

First, notice that $Z_{t}^{1}\equiv 0$ in the quadratic case and the second term in (B.40) is automatically zero. In the more general case, we will show that the second term in (B.40) is also zero. On the event $\tau\in[t_{0},t_{1}]$, for any $0\leq s\leq t_{1}\wedge\tau$, we have

Therefore, for any $t\in[t_{0},t_{1}\wedge\tau]$, by Lemma 2, we get

where we used $t_{1}\geq t\geq t_{0}\geq\mathcal{T}_{\text{rec}}^{U}\geq\frac{1}{\sqrt{m}}$, and $t_{1}e^{-t_{1}\sqrt{m}}\leq\mathcal{T}_{\text{rec}}^{U}e^{-\mathcal{T}_{\text{rec}}^{U}\sqrt{m}}$ and the definition of $\mathcal{T}_{\text{rec}}^{U}$:

Consequently, if we take $c_{1}=\frac{L}{\sqrt{m}}\left(\sqrt{C_{H}+2}+\frac{m+1}{\sqrt{m}}+\frac{\sqrt{(C_{H}+2)m}+(m+1)}{8\sqrt{C_{H}+2+(m+1)^{2}}}\right)\varepsilon$, then,

Moreover, $c_{0}=\frac{1}{2}-c_{1}=\frac{1}{2}-\frac{L}{\sqrt{m}}\left(\sqrt{C_{H}+2}+\frac{m+1}{\sqrt{m}}+\frac{\sqrt{(C_{H}+2)m}+(m+1)}{8\sqrt{C_{H}+2+(m+1)^{2}}}\right)\varepsilon>\frac{1}{4}$ since it is assumed that $\varepsilon<\frac{\sqrt{m}}{4L\left(\sqrt{C_{H}+2}+\frac{m+1}{\sqrt{m}}+\frac{\sqrt{(C_{H}+2)m}+(m+1)}{8\sqrt{C_{H}+2+(m+1)^{2}}}\right)}$.

Second, we will apply Lemma 8 to bound the first term in (B.40). By using $V(0)=0$ and $\|Y(0)\|\leq r$ and the definition of $\mu_{t_{1}}$ and $\Sigma_{t_{1}}$ in (B.38) and (B.39), we get

by choosing $\theta=\frac{m\sqrt{m}}{\gamma(2C_{H}m+4m+(m+1)^{2})}$ and $t_{1}\geq\mathcal{T}_{\text{rec}}^{U}\geq\frac{1}{\sqrt{m}}$, and $t_{1}e^{-t_{1}\sqrt{m}}\leq\mathcal{T}_{\text{rec}}^{U}e^{-\mathcal{T}_{\text{rec}}^{U}}$, and using the definition $\sqrt{C_{H}+2+(m+1)^{2}}\mathcal{T}_{\text{rec}}^{U}e^{-\sqrt{m}\mathcal{T}_{\text{rec}}^{U}}=\frac{\varepsilon^{2}}{8r^{2}}$, and we also used $\varepsilon\leq\sqrt{\frac{C_{H}+2+(m+1)^{2}}{(C_{H}+2)m+(m+1)^{2}}}r$.

Then with the choice of $h=(\varepsilon+re^{-\sqrt{m}t_{1}})c_{0}$ and $\theta=\frac{m\sqrt{m}}{\gamma(2C_{H}m+4m+(m+1)^{2})}$ in Lemma 8, and using the fact that $h=(\varepsilon+re^{-\sqrt{m}t_{1}})c_{0}\geq\varepsilon c_{0}$, we get

Thus for any $t_{0}\geq\mathcal{T}_{\text{rec}}^{U}$ and $t_{0}\leq t_{1}\leq t_{0}+\frac{1}{2\|H_{\gamma}\|}$,

Fix any $\mathcal{T}>0$ and recall the definition of the escape time $\mathcal{T}_{\text{esc}}^{U}=\mathcal{T}+\mathcal{T}_{\text{rec}}^{U}$. Partition the interval $[\mathcal{T}_{\text{rec}}^{U},\mathcal{T}_{\text{esc}}^{U}]$ using the points $\mathcal{T}_{\text{rec}}^{U}=t_{0}<t_{1}<\cdots<t_{\lceil 2\|H_{\gamma}\|\mathcal{T}\rceil}=\mathcal{T}_{\text{esc}}^{U}$ with $t_{j}=j/(2\|H_{\gamma}\|)$, then we have

Finally, plugging $\gamma=2\sqrt{m}$ into the above formulas and applying the bound on $\|H_{\gamma}$ from Lemma 26, the conclusion follows. ∎

In this section, we state the uniform $L^{2}$ bounds for the continuous time underdamped Langevin dynamics ((1.4) and (1.5)) and the discrete time iterates ((1.7) and (1.8)) in Lemma 10, which is a modification of Lemma 8 in [GGZ18]. The uniform $L^{2}$ bound for the discrete dynamics (1.7)-(1.8) is used to derive the relative entropy to compare the laws of the continuous time dynamics and the discrete time dynamics, and the uniform $L^{2}$ bound for the continuous dynamics (1.4)-(1.5) is used to control the tail of the continuous dynamics in Section B.2.1.

Before we proceed, let us first introduce the following Lyapunov function (from the paper [EGZ19]) which will be used in the proof the uniform $L^{2}$ boundedness results for both the continuous and discrete underdamped Langevin dynamics. We define the Lyapunov function $\mathcal{V}$ as:

and $\lambda$ is a positive constant less than $1/4$ according to [EGZ19]. We will first show in the following lemma that we can find explicit constants $\lambda\in(0,\min(1/4,m/(M+\gamma^{2}/2)))$ and $\overline{A}\in(0,\infty)$ so that the drift condition (B.44) is satisfied. The drift condition is needed in [EGZ19], which is applied to obtain the uniform $L^{2}$ bounds in [GGZ18] that implies the uniform $L^{2}$ bounds in our current setting (the following Lemma 10).

then the following drift condition holds:

The following lemma provides uniform $L^{2}$ bounds for the continuous-time underdamped Langevin diffusion process $(X(t),V(t))$ defined in (1.4)-(1.5) and discrete-time underdamped Langevin dynamics $(X_{k},V_{k})$ defined in (1.7)-(1.8).

Suppose parts $(i)$, $(ii)$, $(iii)$, $(iv)$ of Assumption 1 and the drift condition (B.44) hold. $\gamma>0$ is arbitrary and $\lambda$, $\overline{A}$ are defined in (B.42) and (B.43).

B.2.4 Proofs of auxiliary results

Note that $Q_{t_{0}}(t_{1})Z_{t}^{0}$ is a $2d$-dimensional martingale and by Doob’s martingale inequality, for any $h>0$,

where the last line above uses the fact that $Q_{t_{0}}(t_{1})Z_{t_{1}}$ is a Gaussian random vector with mean

We next estimate $\det(I-\beta\theta\Sigma_{t_{1}})$ fron (B.58). Let us recall from Lemma 2 that if $\gamma=2\sqrt{m}$, then we recall from Lemma 2 that,

Therefore we infer that the eigenvalues of $I-\beta\theta\Sigma$ are bounded below by $1-\theta\frac{\gamma(2C_{H}m+4m+(m+1)^{2})}{2m\sqrt{m}}$. The conclusion then follows from (B.58). ∎

By Assumption 1 (iii), $x\cdot\nabla F(x)\geq m\|x\|^{2}-b$. Thus in order to show the drift condition (B.44), it suffices to show that

Given the definition of $\lambda$ in (B.42), by Lemma 28, we get

by the definition of $\overline{A}$ in (B.43). Hence, (B.59) holds and the proof is complete. ∎

B.3 Proof of Theorem 4

The proof of Theorem 4 is similar to the proof of Theorem 3. For brevity, we omit some of the details, and only outline the key steps and the propositions and lemmas used for the proof of Theorem 4.

Fix any $r>0$ and $0<\varepsilon<\min\{\overline{\varepsilon}_{1}^{J},\overline{\varepsilon}_{2}^{J}\}$, where

For any initial point $X(0)=x$ with $\|x-x_{\ast}\|\leq r$, and

We first compare the discrete dynamics (1.10) and the continuous dynamics (1.9). Define:

By following Lemma 7 in [RRT17] and apply the uniform $L^{2}$ bounds for $X_{k}$ in Corollary 17 provided that the stepsize $\eta$ is sufficiently small (we apply the bound $\|A_{J}\|\leq 1+\|J\|$ to Corollary 17)

where (we use the bound $\|A_{J}\|\leq 1+\|J\|$)

Let us now complete the proof of Theorem 4. We need to show that

where $K=\lfloor\eta^{-1}\mathcal{T}_{\text{esc}}^{J}\rfloor$ and $\mathcal{A}:=\mathcal{A}_{1}\cap\mathcal{A}_{2}$:

Similar to the proof in Section B.2.1 and by (B.63), we get

Similar to the proof in Section B.2.1, we get

provided that (by applying Proposition 11):

By Gronwall’s inequality, we get the key estimate:

To complete the proof, we need work on the leading orders of the constants. We treat $\|J\|$, $M$, $L$ as constant. The argument is similar to the argument in the proof of Theorem 3 and is thus omitted here. The proof is now complete.

B.3.2 Proof of Proposition 11

Before we proceed to the proof of Proposition 11, let us first state the following two lemmas that will be used in the proof of Proposition 11.

where $Q_{t_{0}}(t_{1})$ is defined in (B.73), $Z_{t}^{0}$ is defined in (B.74), and

Given $t_{0}\leq t\leq(t_{1}\wedge\tau)$, where $\tau$ is the stopping time defined in Proposition 11, we have

where $Q_{t_{0}}(t_{1})$ is defined in (B.73), and $Z_{t}^{1}$ is defined in (B.75).

We recall $x_{\ast}$ is a local minimum of $F$ and $H$ is the Hessian matrix: $H=\nabla^{2}F(x_{\ast})$, and we write

where $\|\rho(Y(t))\|\leq\frac{1}{2}L\|Y(t)\|^{2}$ since the Hessian of $F$ is $L$-Lipschitz (Lemma 1.2.4. [Nes13]). This implies that

Given $0\leq t_{0}\leq t_{1}$, we define the matrix flow

and $Z_{t}:=e^{(t-t_{0})A_{J}H}Y_{t}$ so that

We define the decomposition $Z_{t}=Z_{t}^{0}+Z_{t}^{1}$, where

It follows that for any $t_{0}\leq t\leq t_{1}$,

The rest of the proof is similar to the proof of Proposition 7. We apply Lemma 13 to bound the term $Q_{t_{0}}(t_{1})Z_{t}^{1}$ and apply Lemma 12 to bound the term $Q_{t_{0}}(t_{1})Z_{t}^{0}$. By letting $\gamma=1$ in Proposition 7 and replacing $d$ by $d/2$ due to Lemma 12, and $\|H_{\gamma}\|$ by $\|A_{J}H\|$ and using the bounds $\|A_{J}\|\leq(1+\|J\|)$ and $\|A_{J}H\|\leq(1+\|J\|)M$, we obtain the desired result in Proposition 11. ∎

In this section we establish uniform $L^{2}$ bounds for both the continuous time dynamics (1.9) and discrete time dynamics (1.10). The main idea of the proof is to use Lyapunov functions. Our local analysis result relies on the approximation of the continuous time dynamics (1.9) by the discrete time dynamics (1.10). The uniform $L^{2}$ bound for the discrete dynamics (1.10) is used to derive the relative entropy to compare the laws of the continuous time dynamics and the discrete time dynamics, and the uniform $L^{2}$ bound for the continuous dynamics (1.9) is used to control the tail of the continuous dynamics in Section B.3.1. We first recall the continuous-time dynamics from (1.9):

where $J$ is a $d\times d$ anti-symmetric matrix, i.e. $J^{T}=-J$. The generator of this continuous time process is given by

Since $F$ has at most the quadratic growth (due to Lemma 28), we immediately have the following corollary.

We next show uniform $L^{2}$ bounds for the discrete iterates $X_{k}$, where we recall from (1.10) that the non-reversible Langevin dynamics is given by:

Given that $\eta\leq\min\left\{\frac{1}{M\|A_{J}\|^{2}},\frac{4(M+B)}{m^{2}}\right\}$, we have

Since $F$ has at most the quadratic growth (due to Lemma 28), we immediately have the following corollary.

Given that $\eta\leq\min\left\{\frac{1}{M\|A_{J}\|^{2}},\frac{4(M+B)}{m^{2}}\right\}$ and $\|X(0)\|\leq R=\sqrt{b/m}$, we have

B.3.4 Proofs of auxiliary results

By following the proof of Lemma 8. We get

Hence, by the definition of $\Sigma_{t}$ from (B.72), we get

The rest of the proof follows similarly as in the proof of Lemma 8. ∎

and by applying $\|\rho(Y(t))\|\leq\frac{1}{2}L\|Y(t)\|^{2}$ and (2.6), and $t_{0}\leq t\leq(t_{1}\wedge\tau)$ and the definition of the stopping time $\tau$ in Proposition 11, we get the desired result. ∎

Note that if we can show that $F(x)$ is a Lyapunov function for $X(t)$:

Let us first prove this. Applying Ito formula to $e^{\epsilon_{1}t}F(X(t))$, we obtain from Dynkin formula and the drift condition (B.79) that for $t_{K}:=\min\{t,\tau_{K}\}$ with $\tau_{K}$ be the exit time of $X(t)$ from a ball centered at with radius $K$ with $X(0)=x$,

Let $K\rightarrow\infty$, then we can infer from Fatou’s lemma that for any $t$:

Next, let us prove (B.79). By the definition of $\mathcal{L}$ in (B.76), we can compute that

since $J$ is anti-symmetric so that $\langle\nabla F(x),J\nabla F(x)\rangle=0$. Moreover,

provided that $\|x\|\geq\sqrt{2b/m}$, and thus

for any $\|x\|\geq\sqrt{2b/m}$. On the other hand, for any $\|x\|\leq\sqrt{2b/m}$, we have

Next, recall that $F$ is $M$-smooth, and thus

Recall that $\|X(0)\|=\|x\|\leq R$ and by Lemma 28 we get $F(x)\leq\frac{M}{2}\|x\|^{2}+B\|x\|+A$, and thus

uniformly for small $\eta$, where $\epsilon_{2},b_{2}$ are positive constants that are independent of $\eta$, then we will first show below that

Then by letting $r=1/(1-\eta\epsilon_{2})\geq 1$, which requires $\eta\leq\frac{1}{\varepsilon_{2}}$, we obtain

Define the stopping time $\tau_{k,K}=\min\{k,\inf\{i:|X_{i}|\geq K\}\}$, where $K$ is a positive integer, so that $X_{i}$ is essentially bounded for $i\leq\tau_{k,K}$. Applying the discrete Dynkin’s formula (see, e.g. Section 4.2 in [MT92]), we have

As $\tau_{k,K}\rightarrow k$ almost surely as $K\rightarrow\infty$, we infer from Fatou’s Lemma that

as $r=1/(1-\eta_{2}\epsilon_{2})$. Hence we have

It remains to prove (B.85). Note that as $\nabla F$ is Lipschitz continuous with constant $M$ so that:

provided that $\frac{M}{2}\|A_{J}\|^{2}\eta\leq\frac{1}{2}$. Similar to the arguments in (B.80)-(B.84), we get

where we assumed that $1-\eta\frac{m^{2}}{4(M+B)}\in[0,1)$. Hence, the proof is complete. ∎

The proof is similar to the proof of Corollary 15 and is thus omitted. ∎

Appendix C Proof of Proposition 5 and Proposition 6

We note finally that Equation (3.5) then readily follows from (3.4) and (C.5). ∎

Write $\tau_{a_{1}\rightarrow a_{2}}^{\beta,n}$ for the first time that the continuous-time dynamics $\{X(t)\}$ starting from $a_{1}$ to exit the region $D_{n}$. Then by monotone convergence theorem, we have

Hence, for fixed $\epsilon>0$, one can choose a sufficiently large $n$ such that

We next control the expected difference between the exit times $\hat{\tau}_{a_{1}\rightarrow a_{2}}^{\beta,n}$ of the discrete dynamics, and $\tau_{a_{1}\rightarrow a_{2}}^{\beta,n}$ of the continuous dynamics, from the bounded domain $D_{n}$. For fixed $\epsilon$ and large $n$, we can infer from Theorem 4.2 in [GM05] thatThe Assumption (H2’) in Theorem 4.2 of [GM05] can be readily verified in our setting: for both reversible and non-reversible SDE, the drift and diffusion coefficients are clearly Lipschitz; the diffusion matrix is uniformly elliptic; and the domain $D_{n}$ is bounded and it satisfies the exterior cone condition., for sufficiently small stepsize $\eta\leq\bar{\eta}(\epsilon,n,\beta)$,

Together with (C.6), we obtain for $\eta$ sufficiently small,

Appendix D Recurrence and escape times for underdamped Langevin dynamics with small friction

In this section, we investigate the local analysis results for the underdamped Langevin dynamics (1.7)-(1.8) when the friction coefficient $\gamma$ is small, and in particular, we assume that $0<\gamma<2\sqrt{m}$.

Fix $\gamma<2\sqrt{m}$, $\delta\in(0,1)$ and $r>0$. Assume

where $\hat{\varepsilon}$ and $C_{\hat{\varepsilon}}$ are defined in Lemma 2, and we assumed that $\hat{\varepsilon}=\Omega(1)$ and thus $C_{\hat{\varepsilon}}$ is of order $m^{-1/2}$. Define the recurrence time

Consider an arbitrary initial point $x$ for the underdamped Langevin dynamics and a local minimum $x_{\ast}$ at a distance at most $r$. Assume that the stepsize $\eta$ satisfies

for any realization of $Z$, with probability at least $1-\delta$ w.r.t. the Gaussian noise, at least one of the following events will occur: (1) $\|X_{k}-x_{\ast}\|\geq\frac{1}{2}\left(\varepsilon+re^{-\sqrt{m}(1-\hat{\varepsilon})k\eta}\right)$ for some $k\leq\eta^{-1}\mathcal{T}_{\text{rec}}^{U}$; (2) $\|X_{k}-x_{\ast}\|\leq\varepsilon+re^{-\sqrt{m}(1-\hat{\varepsilon})k\eta}$ for every $\eta^{-1}\mathcal{T}_{\text{rec}}^{U}\leq k\leq\eta^{-1}\mathcal{T}_{\text{esc}}^{U}$.

Notice that in Theorem 18, the definition of $\eta$ and $\beta$ are coupled since $\overline{\eta}^{U}$ depends on $\beta$ and $\underline{\beta}^{U}$ depends on $\eta$. A closer look reveals that when $\eta$ is sufficiently small, the first term in the definition of $\underline{\beta}^{U}$ dominates the second term and $\underline{\beta}^{U}$ is independent of $\eta$. So to satisfy the constraints in Theorem 18, it suffices to first choose $\beta$ to be larger than the first term in $\underline{\beta}^{U}$ and then choose $\eta$ to be sufficiently small.

In [TLR18], the overdamped Langevin algorithm is used and the recurrence time $\mathcal{T}_{\text{rec}}=\mathcal{O}\left(\frac{1}{m}\log(\frac{r}{\varepsilon})\right)$, and thus our recurrence time $\mathcal{T}_{\text{rec}}^{U}=\mathcal{O}\left(\frac{1}{\sqrt{m}}\log\left(\frac{r}{\varepsilon m}\right)\right)$ for the underdamped Langevin algorithm with the choice of $\gamma<2\sqrt{m}$, which has a square root factor improvement ignoring the logarithmic factor. This recurrence time is worse than $\mathcal{T}_{\text{rec}}^{U}=\mathcal{O}\left(\frac{1}{\sqrt{m}}\log\left(\frac{r}{\varepsilon}\right)\right)$ for the underdamped Langevin algorithm with the choice of $\gamma=2\sqrt{m}$ by a logarithmic factor assuming $C_{H}=\mathcal{O}(1)$.