Title: Free lunches and subsampling MCMC
Authors: Aaron Smith - University of Ottawa (Canada) [presenting]
Natesh Pillai - Harvard University (United States)
James Johndrow - Duke University (United States)
Abstract: 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. 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 that can avoid our generic results and provide a free (or at least cheap) lunch.