Towards scaling up Markov chain Monte Carlo: an adaptive subsampling approach

Rémi Bardenet, Arnaud Doucet, Chris Holmes
Proceedings of the 31st International Conference on Machine Learning, PMLR 32(1):405-413, 2014.

Abstract

Markov chain Monte Carlo (MCMC) methods are often deemed far too computationally intensive to be of any practical use for large datasets. This paper describes a methodology that aims to scale up the Metropolis-Hastings (MH) algorithm in this context. We propose an approximate implementation of the accept/reject step of MH that only requires evaluating the likelihood of a random subset of the data, yet is guaranteed to coincide with the accept/reject step based on the full dataset with a probability superior to a user-specified tolerance level. This adaptive subsampling technique is an alternative to the recent approach developed in (Korattikara et al, ICML’14), and it allows us to establish rigorously that the resulting approximate MH algorithm samples from a perturbed version of the target distribution of interest, whose total variation distance to this very target is controlled explicitly. We explore the benefits and limitations of this scheme on several examples.

Cite this Paper

BibTeX
@InProceedings{pmlr-v32-bardenet14, title = {Towards scaling up Markov chain Monte Carlo: an adaptive subsampling approach }, author = {Bardenet, Rémi and Doucet, Arnaud and Holmes, Chris}, booktitle = {Proceedings of the 31st International Conference on Machine Learning}, pages = {405--413}, year = {2014}, editor = {Xing, Eric P. and Jebara, Tony}, volume = {32}, number = {1}, series = {Proceedings of Machine Learning Research}, address = {Bejing, China}, month = {22--24 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v32/bardenet14.pdf}, url = {https://proceedings.mlr.press/v32/bardenet14.html}, abstract = {Markov chain Monte Carlo (MCMC) methods are often deemed far too computationally intensive to be of any practical use for large datasets. This paper describes a methodology that aims to scale up the Metropolis-Hastings (MH) algorithm in this context. We propose an approximate implementation of the accept/reject step of MH that only requires evaluating the likelihood of a random subset of the data, yet is guaranteed to coincide with the accept/reject step based on the full dataset with a probability superior to a user-specified tolerance level. This adaptive subsampling technique is an alternative to the recent approach developed in (Korattikara et al, ICML’14), and it allows us to establish rigorously that the resulting approximate MH algorithm samples from a perturbed version of the target distribution of interest, whose total variation distance to this very target is controlled explicitly. We explore the benefits and limitations of this scheme on several examples.} }
Endnote
%0 Conference Paper %T Towards scaling up Markov chain Monte Carlo: an adaptive subsampling approach %A Rémi Bardenet %A Arnaud Doucet %A Chris Holmes %B Proceedings of the 31st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2014 %E Eric P. Xing %E Tony Jebara %F pmlr-v32-bardenet14 %I PMLR %P 405--413 %U https://proceedings.mlr.press/v32/bardenet14.html %V 32 %N 1 %X Markov chain Monte Carlo (MCMC) methods are often deemed far too computationally intensive to be of any practical use for large datasets. This paper describes a methodology that aims to scale up the Metropolis-Hastings (MH) algorithm in this context. We propose an approximate implementation of the accept/reject step of MH that only requires evaluating the likelihood of a random subset of the data, yet is guaranteed to coincide with the accept/reject step based on the full dataset with a probability superior to a user-specified tolerance level. This adaptive subsampling technique is an alternative to the recent approach developed in (Korattikara et al, ICML’14), and it allows us to establish rigorously that the resulting approximate MH algorithm samples from a perturbed version of the target distribution of interest, whose total variation distance to this very target is controlled explicitly. We explore the benefits and limitations of this scheme on several examples.
RIS
TY - CPAPER TI - Towards scaling up Markov chain Monte Carlo: an adaptive subsampling approach AU - Rémi Bardenet AU - Arnaud Doucet AU - Chris Holmes BT - Proceedings of the 31st International Conference on Machine Learning DA - 2014/01/27 ED - Eric P. Xing ED - Tony Jebara ID - pmlr-v32-bardenet14 PB - PMLR DP - Proceedings of Machine Learning Research VL - 32 IS - 1 SP - 405 EP - 413 L1 - http://proceedings.mlr.press/v32/bardenet14.pdf UR - https://proceedings.mlr.press/v32/bardenet14.html AB - Markov chain Monte Carlo (MCMC) methods are often deemed far too computationally intensive to be of any practical use for large datasets. This paper describes a methodology that aims to scale up the Metropolis-Hastings (MH) algorithm in this context. We propose an approximate implementation of the accept/reject step of MH that only requires evaluating the likelihood of a random subset of the data, yet is guaranteed to coincide with the accept/reject step based on the full dataset with a probability superior to a user-specified tolerance level. This adaptive subsampling technique is an alternative to the recent approach developed in (Korattikara et al, ICML’14), and it allows us to establish rigorously that the resulting approximate MH algorithm samples from a perturbed version of the target distribution of interest, whose total variation distance to this very target is controlled explicitly. We explore the benefits and limitations of this scheme on several examples. ER -
APA
Bardenet, R., Doucet, A. & Holmes, C.. (2014). Towards scaling up Markov chain Monte Carlo: an adaptive subsampling approach . Proceedings of the 31st International Conference on Machine Learning, in Proceedings of Machine Learning Research 32(1):405-413 Available from https://proceedings.mlr.press/v32/bardenet14.html.

Related Material