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?
 A: 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.
