# Can I subsample a large dataset at every MCMC iteration?

Problem: I want to perform a Gibbs sampling to infer some posterior over a large dataset. Unfortunatelly, my model is not very simple and thus sampling is too slow. I would consider variational or parallel approaches, but before going that far...

Question: I would like to know whether I could randomly sample (with replacement) from my dataset at every Gibbs iteration, so that I have less instances to learn from at every step.

My intuition is that even if I change the samples, I would not be changing the probability density and therefore the Gibbs sample should not notice the trick. Am I right? Are there some references of people having done this?

• As an aside: another idea would be to do multiple analyses on random subsamples of the big dataset. That way you can also cross-validate. – conjectures May 30 '14 at 11:04
• I cannot answer your exact question with any authority (although my suspicion is that you would be just increasing the approximation error that comes with Monte Carlo), the sad truth is that this is just an unfortunate aspect of Bayesian MCMC analyses: they're computationally expensive. @conjectures comment is a great idea, but doesn't really get at the heart of the issue: it's too expensive to draw all of those samples for each individual. My recommendation is to write your own C code for the heavy work (Rcpp in R, Cython in Python, etc.) and also parallelize (when no branch dependencies). – user44764 May 30 '14 at 14:18
• @conjectures This sounds like Michael Jordan's bag of little bootstraps. – jaradniemi Jun 2 '14 at 19:40
• I would suggest changing your sampler to avoid the latent variable augmentation altogether. You will no longer have a Gibbs sampler, but a Metropolis-Hastings algorithm with a proposal based on a normal approximation to the likelihood should work just fine. See Section 16.4 of the 2nd edition of Bayesian Data Analysis. – jaradniemi Jun 2 '14 at 19:42
• This is an area of active research that I don't know well enough to accurately summarize for you. See for example jmlr.org/proceedings/papers/v32/bardenet14.pdf and arxiv.org/pdf/1304.5299v4.pdf – Andrew M Sep 22 '14 at 14:37

About the subsampling strategies: just for example consider to have two observations $X_1 \sim N(\mu_1, \sigma_1^2)$ and $X_2 \sim N(\mu_2,\sigma_2^2)$ and consider to put some priors on the mean and variance. Let $\theta = (\mu_1, \mu_2, \sigma_1^2, \sigma_2^2)$, the posterior we want to evaluate is $$f(\theta|X_1, X_2) \propto f(X_1|\theta)f(X_2 | \theta)f(\theta)$$ COnsider now a binomial variable $\delta \sim B(0.5)$. If $\delta=0$ we chose $X_1$, if $\delta =1$ we chose $X_2$, the new posterior is$$f(\theta, \delta|X_1, X_2) \propto f(X_1, X_2|\delta,\theta)f(\theta)f(\delta)$$ where $f(X_1, X_2|\delta,\theta) = f(X_1|\theta)^{\delta} f(X_2|\theta)^{1-\delta}$ and $f(\delta) = 0.5$. Now if you want to sample $\delta$ with a Gibbs step you have to compute $f(X_1|\theta)$ and $f(X_2|\theta)$ because $P(\delta=1)= \frac{f(X_1|\theta) }{f(X_1|\theta) +f(X_2|\theta) }$. If you otherwise use the Metropolis Hastings then you propose a new state $\delta^*$ and you have to compute only one between $f(X_1|\theta)$ and $f(X_2|\theta)$, the one associated with the proposed states but you have to compute one between $f(X_1|\theta)$ and $f(X_2|\theta)$ even for the last accepted state of $\delta$. Then I am not sure that the metropolis will give you some advantage. Moreover here we are considering a bivariate process, but with a multivariate process the sampling of the $\delta$s can be very complicated with the metropolis.