Provably Efficient Posterior Sampling for Sparse Linear Regression via Measure Decomposition

• 成果类型: Article
• 署名作者: Montanari, Andrea; Wu, Yuchen
• 署名单位: Stanford University; Stanford University; University of Pennsylvania
• 刊物名称: JOURNAL OF THE AMERICAN STATISTICAL ASSOCIATION
• ISSN/ISSBN: 0162-1459; 1537-274X
• DOI: 10.1080/01621459.2025.2537461
• 发表日期: 2026-01-02
• 页码: 636-654
• 关键词: Bayesian linear regression; sampling; Spike-and-slab prior; Uncertainty Quantification; bayesian variable selection; computational-complexity; inference; needles; straw; gibbs; spike; limit

摘要

We consider the problem of sampling from the posterior distribution of a d-dimensional coefficient vector theta, given linear observations y=X theta+epsilon. For sparse Bayesian models, such posteriors are in general multimodal, and therefore challenging to sample from. This observation has prompted the exploration of various heuristics that aim at approximating the posterior distribution. In this article, we study a different approach based on decomposing the posterior distribution into a log-concave mixture of simple product measures. This decomposition allows us to reduce sampling from a multimodal distribution of interest to sampling from a log-concave one, which is tractable and has been investigated in detail. We prove that, under mild conditions on the prior, for random designs, such measure decomposition is generally feasible when the number of samples per parameter n/d exceeds a constant threshold. We thus obtain a provably efficient (polynomial time) sampling algorithm in a regime where this was previously not known. Numerical simulations confirm that the algorithm is practical, and reveal that it has attractive statistical properties compared to state-of-the-art methods. Supplementary materials for this article are available online, including a standardized description of the materials available for reproducing the work.