# Spike-and-Slab Posterior Sampling in High Dimensions

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Mar 2025.

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

- [Separating Oblivious and Adaptive Models of Variable Selection](https://mlsanity.com/paper/2602.16568/) (2026)
- [Sparse Nonparametric Contextual Bandits](https://mlsanity.com/paper/2503.16382/) (2025)
- [Variational Task Vector Composition](https://mlsanity.com/paper/2509.18208/) (2025)

## Abstract (arXiv)

Posterior sampling with the spike-and-slab prior [MB88], a popular multimodal distribution used to model uncertainty in variable selection, is considered the theoretical gold standard method for Bayesian sparse linear regression [CPS09, Roc18]. 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) [YWJ16], only work when the measurement count grows at least linearly in the dimension [MW24], 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 ∈ ℝn× d and noisy observations y = Xθ^star + xi of a signal θ^star drawn from a spike-and-slab prior π with a Gaussian diffuse density and expected sparsity k, where xi ~ N(mathbb0n, σ2In). We give a polynomial-time high-accuracy sampler for the posterior π(· mid X, y), for any SNR σ-1 > 0, as long as n ≥ k3 · 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 ≈ nd in the same setting, as long as n ≥ k5 · 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 σ = O(frac1k) is bounded.