No free lunch for stochastic gradient Langevin dynamics

Abstract As sample sizes grow, scalability has become a central concern in the development of Markov chain Monte Carlo (MCMC) methods. One general approach to this problem, exemplified by the popular stochastic gradient Langevin dynamics (SGLD) algorithm, is to use a small random subsample of the data at every time step. This paper shows that this approach often fails: while decreasing the sample size increases the speed of each MCMC step, for typical datasets this is balanced by a matching decrease in accuracy. This result complements recent work on lower bounds for subsampling MCMC by focusing on actual errors for SGLD, including non-reversible algorithms, and by giving assumptions that are comparatively easy to verify.