Logconcave sampling: MetropolisHastings algorithms are fast!
[edit]
Proceedings of the 31st Conference On Learning Theory, PMLR 75:793797, 2018.
Abstract
We consider the problem of sampling from a strongly logconcave density in $\mathbb{R}^d$, and prove a nonasymptotic upper bound on the mixing time of the Metropolisadjusted Langevin algorithm (MALA). The method draws samples by running a Markov chain obtained from the discretization of an appropriate Langevin diffusion, combined with an acceptreject step to ensure the correct stationary distribution. Relative to known guarantees for the unadjusted Langevin algorithm (ULA), our bounds reveal that the use of an acceptreject step in MALA leads to an exponentially improved dependence on the errortolerance. 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} \big(\kappa d \log(1/\delta) \big)$ steps, as compared to the $\mathcal{O} \big(\kappa^2 d/\delta^2 \big)$ steps established in past work on ULA. We also demonstrate the gains of MALA over ULA for weakly logconcave densities. Furthermore, we derive mixing time bounds for a zerothorder method Metropolized random walk (MRW) and show that it mixes $\mathcal{O}(\kappa d)$ slower than MALA.
Related Material


