  We propose a very fast approximate Markov Chain Monte Carlo (MCMC) sampling
framework that is applicable to a large class of sparse Bayesian inference
problems, where the computational cost per iteration in several models is of
order $O(ns)$, where $n$ is the sample size, and $s$ the underlying sparsity of
the model. This cost can be further reduced by data sub-sampling when
stochastic gradient Langevin dynamics are employed. The algorithm is an
extension of the asynchronous Gibbs sampler of Johnson et al. (2013), but can
be viewed from a statistical perspective as a form of Bayesian iterated sure
independent screening (Fan et al. (2009)). We show that in high-dimensional
linear regression problems, the Markov chain generated by the proposed
algorithm admits an invariant distribution that recovers correctly the main
signal with high probability under some statistical assumptions. Furthermore we
show that its mixing time is at most linear in the number of regressors. We
illustrate the algorithm with several models.
