Poster
The Randomized Midpoint Method for Log-Concave Sampling
Ruoqi Shen · Yin Tat Lee
East Exhibition Hall B, C #163
Keywords: [ Optimization ] [ Probabilistic Methods ] [ MCMC ]
[
Abstract
]
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^{*}\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 2-Wasserstein 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 log-concave sampling
problem, but any problem that involves simulating (stochastic) differential
equations.
Live content is unavailable. Log in and register to view live content