We study the problem of sampling from a distribution where the negative logarithm of the target density is L-smooth everywhere and m-strongly convex outside a ball of radius R, but potentially non-convex inside this ball. We study both overdamped and underdamped Langevin MCMC and prove upper bounds on the time required to obtain a sample from a distribution that is within ε of the target distribution in 1-Wasserstein distance. For the first-order method (overdamped Langevin MCMC), the time complexity isÕ e cLR 2 d ε 2 , where d is the dimension of the underlying space. For the second-order method (underdamped Langevin MCMC), the time complexity isÕ e cLR 2 √ d ε for some explicit positive constant c. Surprisingly, the convergence rate is only polynomial in the dimension d and the target accuracy ε. It is however exponential in the problem parameter LR 2 , which is a measure of non-logconcavity of the target distribution. In a more algorithmic line of work, Dalalyan (2017) bounded the discretization error of overdamped Langevin MCMC, and provided the first non-asymptotic convergence rate of overdamped Langevin MCMC under log-concavity assumptions. This was followed by a sequence of papers in the strongly log-concave setting (see, e.g., Durmus and Moulines, 2016 , Dalalyan and Karagulyan, 2017 , Dwivedi et al., 2018. Most relevant to our work is the paper by Eberle (2016), which established the convergence rate of overdamped Langevin diffusion under assumptions (A1) -(A3). The continuous-time diffusion studied in that paper is not implementable algorithmically. We note that our proofs in this paper rely heavily on the reflection coupling arguments by Eberle (2016). Two results are particularly relevant to this paper. Under the strong log-concavity assumption, Durmus and Moulines (2016) established aÕ d/ε 2 iteration complexity for overdamped Langevin MCMC, and Cheng et al. (2017) established an iteration complexity ofÕ( √ d/ε) for underdamped Langevin MCMC. This quadratic speedup in d and ε also appears in our results as summarized in Theorem 1.1. Also very relevant to this work is the paper by Eberle et al. (2017) that demonstrated a contraction property of the continuous-time process (2). That result deals, however, with a much larger class of potential functions, and because of this the distance to the invariant distribution scales exponentially with dimension d. At a high level, our analysis in Section 3 yields a more favorable result by combining ideas from both Eberle et al. (2017) and Cheng et al. (2017), under new assumptions. Also noteworthy is that the problem of sampling from non-logconcave distributions has been studied by Raginsky et al. (2017) , but under weaker assumptions, with a worst-case convergence rate that is exponential in d. On the other hand, Ge et al. (2017) established a poly(d, 1/ε) convergence rate for sampling from a distribution close to a mixture of Gaussians, where the mixture components have the same variance (which is subsumed by our assumptions). Finally, there is a large class of sampling algorithms known as Hamiltonian Monte Carlo (HMC), which involve Hamiltonian dynamics in some form. We refer to Ma et al. (2015) for a survey of the results in this area. Among these, the variant studied in this paper (Algorithm 2), based on the discretization of (2), has a natural physical interpretation as the evolution of a particle's dynamics under a viscous force field. This model was first studied by (Kramers, 1940) in the context of chemical reactions. The continuous-time process has been studied extensively (Hérau, ) study the convergence rate of HMC under log-concavity assumptions. After the independent completion of this paper, Bou-Rabee et al. (2018) published a pre-print on arXiv analyzing Hamiltonian Monte Carlo under similar assumptions as ours. In this section we present basic definitions, notational conventions and assumptions used throughout the paper. For q ∈ N we let v q denote the q-norm of a vector v ∈ R d . Throughout the paper we use Bt to denote standard Brownian motion (Mörters and Peres, 2010).
The convergence rates of these two algorithms have been further established for sampling from non-log-concave densities REF .
Sharp Convergence Rates for Langevin Dynamics in the Nonconvex Setting
ArXiv
ArXiv
Computer Science Mathematics