# A fast asynchronous MCMC sampler for sparse Bayesian inference

arXiv: https://arxiv.org/abs/2108.06446 · HTML: https://mlsanity.com/paper/2108.06446/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 81 references that are in the map.
- First posted on arXiv 14 Aug 2021.

## Builds on (most cited first, 28 of 28)

- [Dropout as a Bayesian Approximation: Representing Model Uncertainty in Deep Learning](https://mlsanity.com/paper/1506.02142/) (2015)
- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Auto-Encoding Variational Bayes](https://mlsanity.com/paper/1312.6114/) (2013)
- [The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks](https://mlsanity.com/paper/1803.03635/) (2018)
- [Variational Inference: A Review for Statisticians](https://mlsanity.com/paper/1601.00670/) (2016)
- [SNIP: Single-shot Network Pruning based on Connection Sensitivity](https://mlsanity.com/paper/1810.02340/) (2018)
- [Learning Sparse Neural Networks through L0 Regularization](https://mlsanity.com/paper/1712.01312/) (2017)
- [Learning Structured Sparsity in Deep Neural Networks](https://mlsanity.com/paper/1608.03665/) (2016)
- [The State of Sparsity in Deep Neural Networks](https://mlsanity.com/paper/1902.09574/) (2019)
- [Sparse Networks from Scratch: Faster Training without Losing Performance](https://mlsanity.com/paper/1907.04840/) (2019)
- [A Complete Recipe for Stochastic Gradient MCMC](https://mlsanity.com/paper/1506.04696/) (2015)
- [Deep Rewiring: Training very sparse deep networks](https://mlsanity.com/paper/1711.05136/) (2017)
- [Preconditioned Stochastic Gradient Langevin Dynamics for Deep Neural Networks](https://mlsanity.com/paper/1512.07666/) (2015)
- [Bayesian Compression for Deep Learning](https://mlsanity.com/paper/1705.08665/) (2017)
- [Dive into Deep Learning](https://mlsanity.com/paper/2106.11342/) (2021)
- [Frequentist Consistency of Variational Bayes](https://mlsanity.com/paper/1705.03439/) (2017)
- [Model Selection in Bayesian Neural Networks via Horseshoe Priors](https://mlsanity.com/paper/1705.10388/) (2017)
- [On Markov chain Monte Carlo methods for tall data](https://mlsanity.com/paper/1505.02827/) (2015)
- [Convergence Rates of Variational Posterior Distributions](https://mlsanity.com/paper/1712.02519/) (2017)
- [Variational Bayes for high-dimensional linear regression with sparse priors](https://mlsanity.com/paper/1904.07150/) (2019)
- [Sparsity information and regularization in the horseshoe and other shrinkage priors](https://mlsanity.com/paper/1707.01694/) (2017)
- [Bayesian linear regression with sparse priors](https://mlsanity.com/paper/1403.0735/) (2014)
- [Convergence Rates of Variational Inference in Sparse Deep Learning](https://mlsanity.com/paper/1908.04847/) (2019)
- [Perturbation theory for Markov chains via Wasserstein distance](https://mlsanity.com/paper/1503.04123/) (2015)
- [On the Computational Complexity of High-Dimensional Bayesian Variable Selection](https://mlsanity.com/paper/1505.07925/) (2015)
- [Estimating Convergence of Markov chains with L-Lag Couplings](https://mlsanity.com/paper/1905.09971/) (2019)
- [Ensuring Rapid Mixing and Low Bias for Asynchronous Gibbs Sampling](https://mlsanity.com/paper/1602.07415/) (2016)
- [HOGWILD!-Gibbs can be PanAccurate](https://mlsanity.com/paper/1811.10581/) (2018)

## Built on by (most cited first, 3 of 3)

- [Bounding Wasserstein distance with couplings](https://mlsanity.com/paper/2112.03152/) (2021)
- [Asynchronous and Distributed Data Augmentation for Massive Data Settings](https://mlsanity.com/paper/2109.08969/) (2021)
- [A statistical perspective on algorithm unrolling models for inverse problems](https://mlsanity.com/paper/2311.06395/) (2023)

## Abstract (arXiv)

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.