# On the Computational Complexity of High-Dimensional Bayesian Variable Selection

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 May 2015.

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

- [Thompson Sampling for High-Dimensional Sparse Linear Contextual Bandits](https://mlsanity.com/paper/2211.05964/) (2022)
- [ZooD: Exploiting Model Zoo for Out-of-Distribution Generalization](https://mlsanity.com/paper/2210.09236/) (2022)
- [Statistical and Computational Trade-offs in Variational Inference: A Case Study in Inferential Model Selection](https://mlsanity.com/paper/2207.11208/) (2022)
- [Scalable Spike-and-Slab](https://mlsanity.com/paper/2204.01668/) (2022)
- [On Mixing Rates for Bayesian CART](https://mlsanity.com/paper/2306.00126/) (2023)
- [Structure Learning with Adaptive Random Neighborhood Informed MCMC](https://mlsanity.com/paper/2311.00599/) (2023)
- [Bayesian Model Selection via Mean-Field Variational Approximation](https://mlsanity.com/paper/2312.10607/) (2023)
- [A fast asynchronous MCMC sampler for sparse Bayesian inference](https://mlsanity.com/paper/2108.06446/) (2021)
- [Dimension-free Relaxation Times of Informed MCMC Samplers on Discrete Spaces](https://mlsanity.com/paper/2404.03867/) (2024)
- [Covariate-Elaborated Robust Partial Information Transfer with Conditional Spike-and-Slab Prior](https://mlsanity.com/paper/2404.03764/) (2024)
- [Importance is Important: Generalized Markov Chain Importance Sampling Methods](https://mlsanity.com/paper/2304.06251/) (2023)
- [Bayesian inference and neural estimation of acoustic wave propagation](https://mlsanity.com/paper/2305.17749/) (2023)
- [On the Computational Complexity of Private High-dimensional Model Selection](https://mlsanity.com/paper/2310.07852/) (2023)
- [Separating Oblivious and Adaptive Models of Variable Selection](https://mlsanity.com/paper/2602.16568/) (2026)
- [From Estimation to Sampling for Bayesian Linear Regression with Spike-and-Slab Prior](https://mlsanity.com/paper/2307.05558/) (2023)
- [From Minimax Optimal Importance Sampling to Uniformly Ergodic Importance-tempered MCMC](https://mlsanity.com/paper/2506.19186/) (2025)
- [A fast non-reversible sampler for Bayesian mixture models](https://mlsanity.com/paper/2510.03226/) (2025)
- [Beyond Expected Information Gain: Stable Bayesian Optimal Experimental Design with Integral Probability Metrics and Plug-and-Play Extensions](https://mlsanity.com/paper/2604.21849/) (2026)

## Abstract (arXiv)

We study the computational complexity of Markov chain Monte Carlo (MCMC) methods for high-dimensional Bayesian linear regression under sparsity constraints. We first show that a Bayesian approach can achieve variable-selection consistency under relatively mild conditions on the design matrix. We then demonstrate that the statistical criterion of posterior concentration need not imply the computational desideratum of rapid mixing of the MCMC algorithm. By introducing a truncated sparsity prior for variable selection, we provide a set of conditions that guarantee both variable-selection consistency and rapid mixing of a particular Metropolis-Hastings algorithm. The mixing time is linear in the number of covariates up to a logarithmic factor. Our proof controls the spectral gap of the Markov chain by constructing a canonical path ensemble that is inspired by the steps taken by greedy algorithms for variable selection.