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

Raaz Dwivedi, Yuansi Chen, Martin J Wainwright, Bin Yu
Proceedings of the 31st Conference On Learning Theory, PMLR 75:793-797, 2018.

Abstract

We consider the problem of sampling from a strongly log-concave density in Rd, and prove a non-asymptotic upper bound on the mixing time of the Metropolis-adjusted Langevin algorithm (MALA). The method draws samples by running a Markov chain obtained from the discretization of an appropriate Langevin diffusion, combined with an accept-reject 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 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 δ for a density with condition number κ, we show that MALA requires O(κdlog(1/δ)) steps, as compared to the O(κ2d/δ2) 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 a zeroth-order method Metropolized random walk (MRW) and show that it mixes O(κd) slower than MALA.

Cite this Paper

BibTeX
@InProceedings{pmlr-v75-dwivedi18a, title = {Log-concave sampling: Metropolis-Hastings algorithms are fast!}, author = {Dwivedi, Raaz and Chen, Yuansi and Wainwright, Martin J and Yu, Bin}, booktitle = {Proceedings of the 31st Conference On Learning Theory}, pages = {793--797}, year = {2018}, editor = {Bubeck, Sébastien and Perchet, Vianney and Rigollet, Philippe}, volume = {75}, series = {Proceedings of Machine Learning Research}, month = {06--09 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v75/dwivedi18a/dwivedi18a.pdf}, url = {https://proceedings.mlr.press/v75/dwivedi18a.html}, abstract = {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 running a Markov chain obtained from the discretization of an appropriate Langevin diffusion, combined with an accept-reject 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 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 a zeroth-order method Metropolized random walk (MRW) and show that it mixes $\mathcal{O}(\kappa d)$ slower than MALA.} }
Endnote
%0 Conference Paper %T Log-concave sampling: Metropolis-Hastings algorithms are fast! %A Raaz Dwivedi %A Yuansi Chen %A Martin J Wainwright %A Bin Yu %B Proceedings of the 31st Conference On Learning Theory %C Proceedings of Machine Learning Research %D 2018 %E Sébastien Bubeck %E Vianney Perchet %E Philippe Rigollet %F pmlr-v75-dwivedi18a %I PMLR %P 793--797 %U https://proceedings.mlr.press/v75/dwivedi18a.html %V 75 %X 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 running a Markov chain obtained from the discretization of an appropriate Langevin diffusion, combined with an accept-reject 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 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 a zeroth-order method Metropolized random walk (MRW) and show that it mixes $\mathcal{O}(\kappa d)$ slower than MALA.
APA
Dwivedi, R., Chen, Y., Wainwright, M.J. & Yu, B.. (2018). Log-concave sampling: Metropolis-Hastings algorithms are fast!. Proceedings of the 31st Conference On Learning Theory, in Proceedings of Machine Learning Research 75:793-797 Available from https://proceedings.mlr.press/v75/dwivedi18a.html.

Related Material