On the Computational Complexity of High-Dimensional Bayesian Variable Selection

Yun Yang, Martin J. Wainwright, Michael I. Jordan

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 Ba…