Statistics Seminar

Abstract: Posterior sampling with the spike-and-slab prior, a popular multimodal distribution used to model uncertainty in variable selection, is considered the theoretical gold standard method for Bayesian sparse linear regression. 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), only work when the measurement count grows at least linearly in the dimension, 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. This is joint work with Syamantak Kumar, Yusong Zhu, and Kevin Tian.