A fast asynchronous MCMC sampler for sparse Bayesian inference

Abstract

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.

arXiv commentSparse Bayesian inference, Asynchronous MCMC sampling, MCMC mixing, Bayesian deep learning

References in corpus (17)

• Auto-Encoding Variational Bayes
• Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms
• MCMC using Hamiltonian dynamics
• Sparsity information and regularization in the horseshoe and other shrinkage priors
• The State of Sparsity in Deep Neural Networks
• Bayesian Compression for Deep Learning
• Needles and Straw in a Haystack: Posterior concentration for possibly sparse sequences
• Sparse Networks from Scratch: Faster Training without Losing Performance
• Frequentist Consistency of Variational Bayes
• Preconditioned Stochastic Gradient Langevin Dynamics for Deep Neural Networks
• Bayesian Posterior Sampling via Stochastic Gradient Fisher Scoring
• Dive into Deep Learning
• Ergodicity of Approximate MCMC Chains with Applications to Large Data Sets
• Ensuring Rapid Mixing and Low Bias for Asynchronous Gibbs Sampling
• Error bounds for Approximations of Markov chains used in Bayesian Sampling
• Estimating Convergence of Markov chains with L-Lag Couplings
• An approach to large-scale Quasi-Bayesian inference with spike-and-slab priors