  Bayesian inference using Markov Chain Monte Carlo (MCMC) on large datasets
has developed rapidly in recent years. However, the underlying methods are
generally limited to relatively simple settings where the data have specific
forms of independence. We propose a novel technique for speeding up MCMC for
time series data by efficient data subsampling in the frequency domain. For
several challenging time series models, we demonstrate a speedup of up to two
orders of magnitude while incurring negligible bias compared to MCMC on the
full dataset. We also propose alternative control variates for variance
reduction based on data grouping and coreset constructions.
