  In this paper we demonstrate that tempering Markov chain Monte Carlo samplers
for Bayesian models by recursively subsampling observations without replacement
can improve the performance of baseline samplers in terms of effective sample
size per computation. We present two tempering by subsampling algorithms,
subsampled parallel tempering and subsampled tempered transitions. We provide
an asymptotic analysis of the computational cost of tempering by subsampling,
verify that tempering by subsampling costs less than traditional tempering, and
demonstrate both algorithms on Bayesian approaches to learning the mean of a
high dimensional multivariate Normal and estimating Gaussian process
hyperparameters.
