# On Markov chain Monte Carlo methods for tall data

arXiv: https://arxiv.org/abs/1505.02827 · HTML: https://mlsanity.com/paper/1505.02827/

## Key facts

- Cited by 50 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 May 2015.

## Built on by (most cited first, 30 of 50)

- [Densely connected normalizing flows](https://mlsanity.com/paper/2106.04627/) (2021)
- [A Survey of Monte Carlo Methods for Parameter Estimation](https://mlsanity.com/paper/2107.11820/) (2021)
- [Diffusion posterior sampling for simulation-based inference in tall data settings](https://mlsanity.com/paper/2404.07593/) (2024)
- [Sampling from Bayesian Neural Network Posteriors with Symmetric Minibatch Splitting Langevin Dynamics](https://mlsanity.com/paper/2410.19780/) (2024)
- [Bayesian inference via sparse Hamiltonian flows](https://mlsanity.com/paper/2203.05723/) (2022)
- [A Symmetry-Aware Exploration of Bayesian Neural Network Posteriors](https://mlsanity.com/paper/2310.08287/) (2023)
- [DG-LMC: A Turn-key and Scalable Synchronous Distributed MCMC Algorithm via Langevin Monte Carlo within Gibbs](https://mlsanity.com/paper/2106.06300/) (2021)
- [Revealing the Distributional Vulnerability of Discriminators by Implicit Generators](https://mlsanity.com/paper/2108.09976/) (2021)
- [Fast Bayesian Coresets via Subsampling and Quasi-Newton Refinement](https://mlsanity.com/paper/2203.09675/) (2022)
- [A survey of Monte Carlo methods for noisy and costly densities with application to reinforcement learning and ABC](https://mlsanity.com/paper/2108.00490/) (2021)
- [Deep Variational Free Energy Approach to Dense Hydrogen](https://mlsanity.com/paper/2209.06095/) (2022)
- [Non-reversible Parallel Tempering for Deep Posterior Approximation](https://mlsanity.com/paper/2211.10837/) (2022)
- [PAC-Bayes Bounds for Bandit Problems: A Survey and Experimental Comparison](https://mlsanity.com/paper/2211.16110/) (2022)
- [Bounding Wasserstein distance with couplings](https://mlsanity.com/paper/2112.03152/) (2021)
- [How to Combine Variational Bayesian Networks in Federated Learning](https://mlsanity.com/paper/2206.10897/) (2022)
- [Variational Inference for Bayesian Neural Networks under Model and Parameter Uncertainty](https://mlsanity.com/paper/2305.00934/) (2023)
- [Coreset Markov Chain Monte Carlo](https://mlsanity.com/paper/2310.17063/) (2023)
- [Variational Inference with Locally Enhanced Bounds for Hierarchical Models](https://mlsanity.com/paper/2203.04432/) (2022)
- [An optimal transport approach for selecting a representative subsample with application in efficient kernel density estimation](https://mlsanity.com/paper/2206.01182/) (2022)
- [Bayesian Quantification with Black-Box Estimators](https://mlsanity.com/paper/2302.09159/) (2023)
- [Bayesian Pseudo-Coresets via Contrastive Divergence](https://mlsanity.com/paper/2303.11278/) (2023)
- [Machine Learning and the Future of Bayesian Computation](https://mlsanity.com/paper/2304.11251/) (2023)
- [Parameter estimation from an Ornstein-Uhlenbeck process with measurement noise](https://mlsanity.com/paper/2305.13498/) (2023)
- [Approximate Bayesian inference from noisy likelihoods with Gaussian process emulated MCMC](https://mlsanity.com/paper/2104.03942/) (2021)
- [A fast asynchronous MCMC sampler for sparse Bayesian inference](https://mlsanity.com/paper/2108.06446/) (2021)
- [Asynchronous and Distributed Data Augmentation for Massive Data Settings](https://mlsanity.com/paper/2109.08969/) (2021)
- [Optimality in Noisy Importance Sampling](https://mlsanity.com/paper/2201.02432/) (2022)
- [Discovering Inductive Bias with Gibbs Priors: A Diagnostic Tool for Approximate Bayesian Inference](https://mlsanity.com/paper/2203.03353/) (2022)
- [Centered plug-in estimation of Wasserstein distances](https://mlsanity.com/paper/2203.11627/) (2022)
- [General bounds on the quality of Bayesian coresets](https://mlsanity.com/paper/2405.11780/) (2024)

## Abstract (arXiv)

Markov chain Monte Carlo methods are often deemed too computationally intensive to be of any practical use for big data applications, and in particular for inference on datasets containing a large number n of individual data points, also known as tall datasets. In scenarios where data are assumed independent, various approaches to scale up the Metropolis-Hastings algorithm in a Bayesian inference context have been recently proposed in machine learning and computational statistics. These approaches can be grouped into two categories: divide-and-conquer approaches and, subsampling-based algorithms. The aims of this article are as follows. First, we present a comprehensive review of the existing literature, commenting on the underlying assumptions and theoretical guarantees of each method. Second, by leveraging our understanding of these limitations, we propose an original subsampling-based approach which samples from a distribution provably close to the posterior distribution of interest, yet can require less than O(n) data point likelihood evaluations at each iteration for certain statistical models in favourable scenarios. Finally, we have only been able so far to propose subsampling-based methods which display good performance in scenarios where the Bernstein-von Mises approximation of the target posterior distribution is excellent. It remains an open challenge to develop such methods in scenarios where the Bernstein-von Mises approximation is poor.