The Randomized Midpoint Method for Log-Concave Sampling

Abstract

Sampling from log-concave distributions is a well researched problem that has many applications in statistics and machine learning. We study the distributions of the form $p^{\ast }\propto \exp (-f(x))$, where $f:{\mathbb{R}}^d\to \mathbb{R}$ has an $L$-Lipschitz gradient and is $m$-strongly convex. In our paper, we propose a Markov chain Monte Carlo (MCMC) algorithm based on the underdamped Langevin diffusion (ULD). It can achieve $\epsilon \cdot D$ error (in 2-Wasserstein distance) in $\tilde{O}\left({\kappa }^{7/6}/{\epsilon }^{1/3}+\kappa /{\epsilon }^{2/3}\right)$ steps, where $D\stackrel{\mathrm{def}}{=}\sqrt{\frac{d}{m}}$ is the effective diameter of the problem and $\kappa \stackrel{\mathrm{def}}{=}\frac{L}{m}$ is the condition number. Our algorithm performs significantly faster than the previously best known algorithm for solving this problem, which requires $\tilde{O}\left({\kappa }^{1.5}/\epsilon \right)$ steps. Moreover, our algorithm can be easily parallelized to require only $O(\kappa \log \frac{1}{\epsilon })$ parallel steps. To solve the sampling problem, we propose a new framework to discretize stochastic differential equations. We apply this framework to discretize and simulate ULD, which converges to the target distribution $p^{\ast }$. The framework can be used to solve not only the log-concave sampling problem, but any problem that involves simulating (stochastic) differential equations.

Cited by in corpus (19)

• High-Order Langevin Diffusion Yields an Accelerated MCMC Algorithm
• Complexity of randomized algorithms for underdamped Langevin dynamics
• On the Convergence of Langevin Monte Carlo: The Interplay between Tail Growth and Smoothness
• An Analysis of Constant Step Size SGD in the Non-convex Regime: Asymptotic Normality and Bias
• On the Ergodicity, Bias and Asymptotic Normality of Randomized Midpoint Sampling Method
• Optimal dimension dependence of the Metropolis-Adjusted Langevin Algorithm
• Sqrt(d) Dimension Dependence of Langevin Monte Carlo
• Composite Logconcave Sampling with a Restricted Gaussian Oracle
• Random Coordinate Langevin Monte Carlo
• Hessian-Free High-Resolution Nesterov Acceleration for Sampling
• Random Coordinate Underdamped Langevin Monte Carlo
• Structured Logconcave Sampling with a Restricted Gaussian Oracle
• Convergence of Langevin Monte Carlo in Chi-Squared and Renyi Divergence
• A Proximal Algorithm for Sampling from Non-smooth Potentials
• The query complexity of sampling from strongly log-concave distributions in one dimension
• Unadjusted Hamiltonian MCMC with Stratified Monte Carlo Time Integration
• Penalized Langevin dynamics with vanishing penalty for smooth and log-concave targets
• When is the Convergence Time of Langevin Algorithms Dimension Independent? A Composite Optimization Viewpoint
• Wasserstein distance estimates for the distributions of numerical approximations to ergodic stochastic differential equations