Markov chain Monte Carlo (MCMC) is a popular generic algorithm for Bayesian inference. It is widely known that the performance of MCMC algorithms can degrade quite quickly when targeting computationally expensive posterior distributions, including the posteriors associated with any large dataset. This has motivated the search for MCMC variants that scale well for large datasets. One general approach, taken by several research groups, has been to look at only a subsample of the data at every step. In this talk, we focus on a simple "no-free-lunch" results which provide some basic limits on the performance of many such algorithms. We apply these generic results to realistic statistical problems and proposed algorithms, and also discuss some special examples where a free lunch seems possible.
This talk is related to previous and ongoing work with Patrick Conrad, Andrew Davis, James Johndrow, Youssef Marzouk, Natesh Pillai, and Pengfei Wang.