Spike-and-Slab Posterior Sampling in High Dimensions

Symantak Kumar, Purnamrita Sarkar, Kevin Tian, Yusong Zhu
Proceedings of Thirty Eighth Conference on Learning Theory, PMLR 291:3407-3462, 2025.

Abstract

Posterior sampling with the spike-and-slab prior (Mitchell and Beauchamp, 1988), a popular multi-modal distribution used to model uncertainty in variable selection, is considered the theoretical gold standard method for Bayesian sparse linear regression (Carvalho et al., 2009; Rockova, 2018). However, designing provable algorithms for performing this sampling task is notoriously challenging. Existing posterior samplers for Bayesian sparse variable selection tasks either require strong assumptions about the signal-to-noise ratio (SNR) (Yang et al., 2016), only work when the measurement count grows at least linearly in the dimension (Montanari and Wu, 2024), or rely on heuristic approximations to the posterior. We give the first provable algorithms for spike-and-slab posterior sampling that apply for any SNR, and use a measurement count sublinear in the problem dimension. Concretely, assume we are given a measurement matrix $X \in \R^{n \times d}$ and noisy observations $y = X\theta^\star + \xi$ of a signal $\theta^\star$ drawn from a spike-and-slab prior $\pi$ with a Gaussian diffuse density and expected sparsity $k$, where $\xi \sim \mathcal{N}(0_d, \sigma^2 I_n)$. We give a polynomial-time high-accuracy sampler for the posterior $\pi(\cdot \mid X, y)$, for any SNR $\sigma^{-1} > 0$, as long as $n \geq k^3 \cdot \text{polylog}(d)$ and $X$ is drawn from a matrix ensemble satisfying the restricted isometry property. We further give a sampler that runs in near-linear time $\approx nd$ in the same setting, as long as $n \geq k^5 \cdot \text{polylog}(d)$. To demonstrate the flexibility of our framework, we extend our result to spike-and-slab posterior sampling with Laplace diffuse densities, achieving similar guarantees when $\sigma = O(\frac{1}{k})$ is bounded.

Cite this Paper

BibTeX
@InProceedings{pmlr-v291-kumar25a, title = {Spike-and-Slab Posterior Sampling in High Dimensions}, author = {Kumar, Symantak and Sarkar, Purnamrita and Tian, Kevin and Zhu, Yusong}, booktitle = {Proceedings of Thirty Eighth Conference on Learning Theory}, pages = {3407--3462}, year = {2025}, editor = {Haghtalab, Nika and Moitra, Ankur}, volume = {291}, series = {Proceedings of Machine Learning Research}, month = {30 Jun--04 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v291/main/assets/kumar25a/kumar25a.pdf}, url = {https://proceedings.mlr.press/v291/kumar25a.html}, abstract = {Posterior sampling with the spike-and-slab prior (Mitchell and Beauchamp, 1988), a popular multi-modal distribution used to model uncertainty in variable selection, is considered the theoretical gold standard method for Bayesian sparse linear regression (Carvalho et al., 2009; Rockova, 2018). However, designing provable algorithms for performing this sampling task is notoriously challenging. Existing posterior samplers for Bayesian sparse variable selection tasks either require strong assumptions about the signal-to-noise ratio (SNR) (Yang et al., 2016), only work when the measurement count grows at least linearly in the dimension (Montanari and Wu, 2024), or rely on heuristic approximations to the posterior. We give the first provable algorithms for spike-and-slab posterior sampling that apply for any SNR, and use a measurement count sublinear in the problem dimension. Concretely, assume we are given a measurement matrix $X \in \R^{n \times d}$ and noisy observations $y = X\theta^\star + \xi$ of a signal $\theta^\star$ drawn from a spike-and-slab prior $\pi$ with a Gaussian diffuse density and expected sparsity $k$, where $\xi \sim \mathcal{N}(0_d, \sigma^2 I_n)$. We give a polynomial-time high-accuracy sampler for the posterior $\pi(\cdot \mid X, y)$, for any SNR $\sigma^{-1} > 0$, as long as $n \geq k^3 \cdot \text{polylog}(d)$ and $X$ is drawn from a matrix ensemble satisfying the restricted isometry property. We further give a sampler that runs in near-linear time $\approx nd$ in the same setting, as long as $n \geq k^5 \cdot \text{polylog}(d)$. To demonstrate the flexibility of our framework, we extend our result to spike-and-slab posterior sampling with Laplace diffuse densities, achieving similar guarantees when $\sigma = O(\frac{1}{k})$ is bounded.} }
Endnote
%0 Conference Paper %T Spike-and-Slab Posterior Sampling in High Dimensions %A Symantak Kumar %A Purnamrita Sarkar %A Kevin Tian %A Yusong Zhu %B Proceedings of Thirty Eighth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2025 %E Nika Haghtalab %E Ankur Moitra %F pmlr-v291-kumar25a %I PMLR %P 3407--3462 %U https://proceedings.mlr.press/v291/kumar25a.html %V 291 %X Posterior sampling with the spike-and-slab prior (Mitchell and Beauchamp, 1988), a popular multi-modal distribution used to model uncertainty in variable selection, is considered the theoretical gold standard method for Bayesian sparse linear regression (Carvalho et al., 2009; Rockova, 2018). However, designing provable algorithms for performing this sampling task is notoriously challenging. Existing posterior samplers for Bayesian sparse variable selection tasks either require strong assumptions about the signal-to-noise ratio (SNR) (Yang et al., 2016), only work when the measurement count grows at least linearly in the dimension (Montanari and Wu, 2024), or rely on heuristic approximations to the posterior. We give the first provable algorithms for spike-and-slab posterior sampling that apply for any SNR, and use a measurement count sublinear in the problem dimension. Concretely, assume we are given a measurement matrix $X \in \R^{n \times d}$ and noisy observations $y = X\theta^\star + \xi$ of a signal $\theta^\star$ drawn from a spike-and-slab prior $\pi$ with a Gaussian diffuse density and expected sparsity $k$, where $\xi \sim \mathcal{N}(0_d, \sigma^2 I_n)$. We give a polynomial-time high-accuracy sampler for the posterior $\pi(\cdot \mid X, y)$, for any SNR $\sigma^{-1} > 0$, as long as $n \geq k^3 \cdot \text{polylog}(d)$ and $X$ is drawn from a matrix ensemble satisfying the restricted isometry property. We further give a sampler that runs in near-linear time $\approx nd$ in the same setting, as long as $n \geq k^5 \cdot \text{polylog}(d)$. To demonstrate the flexibility of our framework, we extend our result to spike-and-slab posterior sampling with Laplace diffuse densities, achieving similar guarantees when $\sigma = O(\frac{1}{k})$ is bounded.
APA
Kumar, S., Sarkar, P., Tian, K. & Zhu, Y.. (2025). Spike-and-Slab Posterior Sampling in High Dimensions. Proceedings of Thirty Eighth Conference on Learning Theory, in Proceedings of Machine Learning Research 291:3407-3462 Available from https://proceedings.mlr.press/v291/kumar25a.html.

Related Material