Provably Efficient Posterior Sampling for Sparse Linear Regression via Measure Decomposition
提出一种将多峰后验分布分解为对数凹混合测度的方法，从而将采样问题转化为可处理的对数凹采样，在样本数超过维度常数倍时给出多项式时间算法，数值实验表明其统计性质优于现有方法。
We consider the problem of sampling from the posterior distribution of a d-dimensional coefficient vector θ, given linear observations y=Xθ+ε. 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 paper, 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.