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

Markov chain Monte Carlo (MCMC) methods are often deemed far too computationally inten-sive to be of any practical use for large datasets. This paper describes a methodology that aims to scale up the Metropolis-Hastings (MH) algo-rithm in this context. We propose an approxi-mate 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 sub-sampling technique is an alternative to the re-cent approach developed in (Korattikara et al., 2014), and it allows us to establish rigorously that the resulting approximate MH algorithm samples from a perturbed version of the target distribu-tion of interest, whose total variation distance to this very target is controlled explicitly. We ex-plore the benefits and limitations of this scheme on several examples. 1