Sampling from logconcave distributions is a well researched problem that has many applications in statistics and machine learning. We study the distributions of the form $p^{*}\propto\exp(f(x))$, where $f:\mathbb{R}^{d}\rightarrow\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 2Wasserstein distance) in $\tilde{O}\left(\kappa^{7/6}/\epsilon^{1/3}+\kappa/\epsilon^{2/3}\right)$ steps, where $D\overset{\mathrm{def}}{=}\sqrt{\frac{d}{m}}$ is the effective diameter of the problem and $\kappa\overset{\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 \cite{chen2019optimal,dalalyan2018sampling}. 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^{*}$. The framework can be used to solve not only the logconcave sampling problem, but any problem that involves simulating (stochastic) differential equations.
Author Information
Ruoqi Shen (University of Washington)
Yin Tat Lee (UW)
Related Events (a corresponding poster, oral, or spotlight)

2019 Poster: The Randomized Midpoint Method for LogConcave Sampling »
Tue Dec 10th 05:30  07:30 PM Room East Exhibition Hall B + C
More from the Same Authors

2018 Poster: Optimal Algorithms for NonSmooth Distributed Optimization in Networks »
Kevin Scaman · Francis Bach · Sebastien Bubeck · Laurent Massoulié · Yin Tat Lee 
2018 Oral: Optimal Algorithms for NonSmooth Distributed Optimization in Networks »
Kevin Scaman · Francis Bach · Sebastien Bubeck · Laurent Massoulié · Yin Tat Lee