Spotlight
The Randomized Midpoint Method for LogConcave Sampling
Ruoqi Shen · Yin Tat Lee
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