We study Hamiltonian Monte Carlo (HMC) for sampling from a strongly logconcave density proportional to @math where @math is @math -strongly convex and @math -smooth (the condition number is @math ). We show that the relaxation time (inverse of the spectral gap) of ideal HMC is @math , improving on the previous best bound of @math ; we complement this with an example where the relaxation time is @math . When implemented using a nearly optimal ODE solver, HMC returns an @math -approximate point in @math -Wasserstein distance using @math gradient evaluations per step and @math total time.
Various versions of Langevin dynamics have been studied in many recent papers, see @cite_15 @cite_14 @cite_10 @cite_20 @cite_19 @cite_6 @cite_3 @cite_7 @cite_13 @cite_17 @cite_9 @cite_8 . The convergence rate of HMC is also studied recently in @cite_18 @cite_1 @cite_2 @cite_0 @cite_12 @cite_11 . The first bound for our setting was obtained by Mangoubi and Smith @cite_2 , who gave an @math bound on the convergence rate of ideal HMC.
@cite_13 @cite_18 @cite_14 @cite_11 @cite_7 @cite_8 @cite_9 @cite_1 @cite_6 @cite_3 @cite_0 @cite_19 @cite_2 @cite_15 @cite_10 @cite_12 @cite_20 @cite_17
2955467429 2736302961 2186210550 2738410460
We introduce a new probabilistic approach to quantify convergence to equilibrium for (kinetic) Langevin processes. In contrast to previous analytic approaches that focus on the associated kinetic Fokker-Planck equation, our approach is based on a specific combination of reflection and synchronous coupling of two solutions of the Langevin equation. It yields contractions in a particular Wasserstein distance, and it provides rather precise bounds for convergence to equilibrium at the borderline between the overdamped and the underdamped regime. In particular, we are able to recover kinetic behavior in terms of explicit lower bounds for the contraction rate. For example, for a rescaled double-well potential with local minima at distance @math , we obtain a lower bound for the contraction rate of order @math provided the friction coefficient is of order @math . We study the underdamped Langevin diffusion when the log of the target distribution is smooth and strongly concave. We present a MCMC algorithm based on its discretization and show that it achieves @math error (in 2-Wasserstein distance) in @math steps. This is a significant improvement over the best known rate for overdamped Langevin MCMC, which is @math steps under the same smoothness concavity assumptions. The underdamped Langevin MCMC scheme can be viewed as a version of Hamiltonian Monte Carlo (HMC) which has been observed to outperform overdamped Langevin MCMC methods in a number of application areas. We provide quantitative rates that support this empirical wisdom. Recent advances in Bayesian learning with large-scale data have witnessed emergence of stochastic gradient MCMC algorithms (SG-MCMC), such as stochastic gradient Langevin dynamics (SGLD), stochastic gradient Hamiltonian MCMC (SGHMC), and the stochastic gradient thermostat. While finite-time convergence properties of the SGLD with a 1st-order Euler integrator have recently been studied, corresponding theory for general SG-MCMCs has not been explored. In this paper we consider general SG-MCMCs with high-order integrators, and develop theory to analyze finite-time convergence properties and their asymptotic invariant measures. Our theoretical results show faster convergence rates and more accurate invariant measures for SG-MCMCs with higher-order integrators. For example, with the proposed efficient 2nd-order symmetric splitting integrator, the mean square error (MSE) of the posterior average for the SGHMC achieves an optimal convergence rate of L-4 5 at L iterations, compared to L-2 3 for the SGHMC and SGLD with 1st-order Euler integrators. Furthermore, convergence results of decreasing-step-size SG-MCMCs are also developed, with the same convergence rates as their fixed-step-size counterparts for a specific decreasing sequence. Experiments on both synthetic and real datasets verify our theory, and show advantages of the proposed method in two large-scale real applications. We present a unified framework to analyze the global convergence of Langevin dynamics based algorithms for nonconvex finite-sum optimization with @math component functions. At the core of our analysis is a direct analysis of the ergodicity of the numerical approximations to Langevin dynamics, which leads to faster convergence rates. Specifically, we show that gradient Langevin dynamics (GLD) and stochastic gradient Langevin dynamics (SGLD) converge to the almost minimizer within @math and @math stochastic gradient evaluations respectively, where @math is the problem dimension, and @math is the spectral gap of the Markov chain generated by GLD. Both of the results improve upon the best known gradient complexity results. Furthermore, for the first time we prove the global convergence guarantee for variance reduced stochastic gradient Langevin dynamics (VR-SGLD) to the almost minimizer after @math stochastic gradient evaluations, which outperforms the gradient complexities of GLD and SGLD in a wide regime. Our theoretical analyses shed some light on using Langevin dynamics based algorithms for nonconvex optimization with provable guarantees.