Log-concave sampling: Metropolis-Hastings algorithms are fast!

By Raaz Dwivedi, Yuansi Chen, Martin J. Wainwright, Bin Yu. Annual Conference Computational Learning Theory, 2018

294 citations recorded by the source corpus.

We consider the problem of sampling from a strongly log-concave density in $\mathbb{R}^d$, and prove a non-asymptotic upper bound on the mixing time of the Metropolis-adjusted Langevin algorithm (MALA). The method draws samples by simulating a Markov chain obtained from the discretization of an appropriate Langevin diffusion, combined with an accept-reject step. Relative to known guarantees for the unadjusted Langevin algorithm (ULA), our bounds show that the use of an accept-reject step in MALA leads to an exponentially improved dependence on the error-tolerance. 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 log-concave densities. Furthermore, we derive mixing time bounds for the Metropolized random walk (MRW) and obtain $\mathcal{O}(\kappa)$ mixing time slower than MALA. We provide numerical examples that support our theoretical findings, and demonstrate the benefits of Metropolis-Hastings adjustment for Langevin-type sampling algorithms.

Subfields: Radiology, Nuclear Medicine and Imaging, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/faeac34337de9dd1cd554870725dd51630ef218e

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Radiology, Nuclear Medicine and Imaging

In Statistics and Probability

Citations in the corpus

Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Suffices (2019, background): “logconcave, there are many sampling algorithms with provable rapid convergence; these include the ball walk and hit-and-run [37, 43, 44, 42] (which give truly polynomial algorithms), various discretizations of the overdamped or underdamped Langevin dynamics [21, 22, 24, 8, 26] (which have polynomial”
Stacking for Non-mixing Bayesian Computations: The Curse and Blessing of Multimodal Posteriors (2020, methodology): “That ensures rapid mixing for random-walk Metropolis, scaling as O ( d ) (Roberts et al., 1997; Cotter et al., 2013; Dwivedi et al., 2019), and Hamiltonian Monte Carlo, scaling as O ( d 1 / 4 ) (Beskos et al., 2013; Bou-Rabee et al., 2020; Mangoubi and Smith, 2017, 2019).”