No Free Lunch for Approximate MCMC
arXiv:2010.12514
Abstract
It is widely known that the performance of Markov chain Monte Carlo (MCMC) can degrade quickly when targeting computationally expensive posterior distributions, such as when the sample size is large. This has motivated the search for MCMC variants that scale well to large datasets. One popular general approach has been to look at only a subsample of the data at every step. In this note, we point out that well-known MCMC convergence results often imply that these ``subsampling'' MCMC algorithms cannot greatly improve performance. We apply these abstract results to realistic statistical problems and proposed algorithms, and also discuss some design principles suggested by the results. Finally, we develop estimates for the singular values of random matrices bounds that may be of independent interest.
References in corpus (12)
- Austerity in MCMC Land: Cutting the Metropolis-Hastings Budget
- On Markov chain Monte Carlo methods for tall data
- Coresets for Scalable Bayesian Logistic Regression
- Firefly Monte Carlo: Exact MCMC with Subsets of Data
- The True Cost of Stochastic Gradient Langevin Dynamics
- Complexity Results for MCMC derived from Quantitative Bounds
- Representation of Markov chains by random maps: existence and regularity conditions
- Metropolis-Hastings reversiblizations of non-reversible Markov chains
- Theoretical properties of quasi-stationary Monte Carlo methods
- PASS-GLM: polynomial approximate sufficient statistics for scalable Bayesian GLM inference
- Spectral Subsampling MCMC for Stationary Time Series
- Some quantitative results on Lipschitz inverse and implicit functions theorems