Log-concave sampling: Metropolis-Hastings algorithms are fast

Abstract

We consider the problem of sampling from a strongly log-concave density in ${\mathbb{R}}^d$, and prove a non-asymptotic upper bound on the mixing time of the Metropolis-adjusted Langevin algorithm (MALA). The method draws samples by simulating a Markov chain obtained from the discretization of an appropriate Langevin diffusion, combined with an accept-reject step. Relative to known guarantees for the unadjusted Langevin algorithm (ULA), our bounds show that the use of an accept-reject step in MALA leads to an exponentially improved dependence on the error-tolerance. Concretely, in order to obtain samples with TV error at most $\delta$ for a density with condition number $\kappa$, we show that MALA requires $\mathcal{O}(\kappa d\log (1/\delta ))$ steps, as compared to the $\mathcal{O}({\kappa }^{2}d/{\delta }^2)$ steps established in past work on ULA. We also demonstrate the gains of MALA over ULA for weakly log-concave densities. Furthermore, we derive mixing time bounds for the Metropolized random walk (MRW) and obtain $\mathcal{O}(\kappa )$ mixing time slower than MALA. We provide numerical examples that support our theoretical findings, and demonstrate the benefits of Metropolis-Hastings adjustment for Langevin-type sampling algorithms.

42 pages, 11 Figures; The first two authors contributed equally; A subset of results were presented in an extended abstract at COLT 2018

References in corpus (5)

• Underdamped Langevin MCMC: A non-asymptotic analysis
• Rapid Mixing of Hamiltonian Monte Carlo on Strongly Log-Concave Distributions
• Dimensionally Tight Bounds for Second-Order Hamiltonian Monte Carlo
• Fast mixing of Metropolized Hamiltonian Monte Carlo: Benefits of multi-step gradients
• Complexity Bounds for MCMC via Diffusion Limits

Cited by in corpus (41)

• Sampling Can Be Faster Than Optimization
• Is There an Analog of Nesterov Acceleration for MCMC?
• Stacking for Non-mixing Bayesian Computations: The Curse and Blessing of Multimodal Posteriors
• Sampling as optimization in the space of measures: The Langevin dynamics as a composite optimization problem
• Stochastic Runge-Kutta Accelerates Langevin Monte Carlo and Beyond
• Accelerating Langevin Sampling with Birth-death
• Algorithmic Theory of ODEs and Sampling from Well-conditioned Logconcave Densities
• Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave Distributions
• Bounding the error of discretized Langevin algorithms for non-strongly log-concave targets
• Explicit convergence bounds for Metropolis Markov chains: isoperimetry, spectral gaps and profiles
• An Analysis of Constant Step Size SGD in the Non-convex Regime: Asymptotic Normality and Bias
• Wasserstein Control of Mirror Langevin Monte Carlo
• Langevin Monte Carlo without smoothness
• Simulated Tempering Langevin Monte Carlo II: An Improved Proof using Soft Markov Chain Decomposition
• Sampling Algorithms, from Survey Sampling to Monte Carlo Methods: Tutorial and Literature Review
• Estimating Convergence of Markov chains with L-Lag Couplings
• Truncated Log-concave Sampling with Reflective Hamiltonian Monte Carlo
• Global Non-convex Optimization with Discretized Diffusions
• Efficient MCMC Sampling with Dimension-Free Convergence Rate using ADMM-type Splitting
• Faster Convergence of Stochastic Gradient Langevin Dynamics for Non-Log-Concave Sampling
• Scalable Bayesian computation for crossed and nested hierarchical models
• Nonconvex sampling with the Metropolis-adjusted Langevin algorithm
• AMAGOLD: Amortized Metropolis Adjustment for Efficient Stochastic Gradient MCMC
• Complexity of zigzag sampling algorithm for strongly log-concave distributions
• Estimating Normalizing Constants for Log-Concave Distributions: Algorithms and Lower Bounds
• Convergence of Stein Variational Gradient Descent under a Weaker Smoothness Condition
• Online Sampling from Log-Concave Distributions
• Structured Logconcave Sampling with a Restricted Gaussian Oracle
• On the cost of Bayesian posterior mean strategy for log-concave models
• Restricted Boltzmann Machine and Deep Belief Network: Tutorial and Survey
• Sensing Cox Processes via Posterior Sampling and Positive Bases
• On the Error of Random Sampling: Uniformly Distributed Random Points on Parametric Curves
• Convergence Speed and Approximation Accuracy of Numerical MCMC
• When is the Convergence Time of Langevin Algorithms Dimension Independent? A Composite Optimization Viewpoint
• Non-asymptotic error bounds for scaled underdamped Langevin MCMC
• Sampling for Bayesian Mixture Models: MCMC with Polynomial-Time Mixing
• Aggregated Gradient Langevin Dynamics
• Variance reduction for Random Coordinate Descent-Langevin Monte Carlo
• Scalable random number generation for truncated log-concave distributions
• Mirrored Langevin Dynamics
• An entropic approach for Hamiltonian Monte Carlo: the idealized case