Fast Laplace Approximation for Sparse Bayesian Spike and Slab Models

Syed Abbas Zilqurnain Naqvi, Shandian Zhe, Yuan Qi, Yifan Yang, Jieping Ye

In high-dimensional data settings where the number of features ($p$) significantly exceeds the number of samples ($n$), effective feature selection is paramount. While frequentist approaches like the Lasso are computationally efficient and possess desirable "oracle" properties, they often fail to provide comprehensive uncertainty quantification. Conversely, Bayesian spike-and-slab models offer a gold standard for feature selection by providing a full posterior distribution, yet they are traditionally plagued by prohibitive computational costs.

Presented at IJCAI-16, the FLAS (Fast Laplace Approximation for Spike-and-slab) algorithm addresses this trade-off. FLAS delivers a scalable inference framework that maintains the statistical rigor of Bayesian methods while achieving the speed of frequentist $L_1$ solvers.

The Computational Bottleneck in Bayesian Inference

The primary challenge in Bayesian feature selection is the complexity of posterior estimation. Standard methods like Markov Chain Monte Carlo (MCMC) do not scale to datasets with tens of thousands of features. Approximations such as Variational Bayes (VB) or Expectation Propagation (EP) often require inverting a massive $p \times p$ Hessian matrix, leading to $O(p^3)$ or $O(np^2)$ complexity. To bypass this, many methods resort to "mean-field" assumptions, treating features as independent and potentially sacrificing accuracy.

The FLAS Algorithm

FLAS overcomes these hurdles through a three-stage process:

  1. Efficient MAP Estimation: The algorithm first identifies the mode of the posterior using high-performance optimization solvers. It employs L-BFGS for marginalized models and the General Iterative Shrinkage-Thresholding (GIST) algorithm for joint models.
  2. Ensemble Nyström Approximation: To approximate the marginal variances without full matrix inversion, FLAS utilizes a low-rank Nyström approximation. By employing an ensemble approach—averaging approximations from multiple disjoint subsets of columns—the algorithm reduces the complexity of estimating the inverse Hessian's diagonal to $O(knp)$, where $k$ is much smaller than $p$.
  3. Quadrature Integration: Finally, Gauss-Hermite quadrature is used to compute selection probabilities and indicator variables for each feature, providing the desired Bayesian uncertainty estimates.

Empirical Evaluation

The authors evaluated FLAS across 14 real-world datasets and various simulated environments. The results indicate that FLAS consistently matches or exceeds the predictive accuracy of Lasso, Elastic Net, and ARD.

Classification F1 scores across varying training sample sizes.

In terms of efficiency, FLAS demonstrated remarkable speed. On the genomics dataset gse5680, FLAS completed its task in just 0.3 seconds, significantly outperforming Capped $L_1$ (15.3 seconds) and linear-time EP methods (6.52 seconds).

Uncertainty Quantification

A key advantage of FLAS is its ability to provide high-quality uncertainty estimates. In simulations, the selection probabilities generated by FLAS were found to be much closer to the ground truth (established via expensive Gibbs sampling) than those produced by VB or EP.

Posterior mean regression selection probabilities {s_j} as a function of training samples.

Conclusion

FLAS represents a significant step forward in high-dimensional Bayesian inference. By combining the "oracle" properties of frequentist methods with the robust uncertainty quantification of spike-and-slab models, it provides a scalable solution for modern data challenges. Future work may focus on automating hyperparameter tuning and extending the theoretical "oracle" proofs more deeply into the classification domain.

Summary updated

Abstract

We consider the application of Bayesian spike-and-slab models in high-dimensional feature selection problems. To do so, we propose a simple yet effective fast approximate Bayesian inference algorithm based on Laplace's method. We exploit two efficient optimization methods, GIST [Gong et al., 2013] and L-BFGS [Nocedal, 1980], to obtain the mode of the posterior distribution. Then we propose an ensemble Nystrom based approach to calculate the diagonal of the inverse Hessian over the mode to obtain the approximate posterior marginals in O(knp) time, k ≪ p. Furthermore, we provide the theoretical analysis about the estimation consistency and approximation error bounds. With the posterior marginals of the model weights, we use quadrature integration to estimate the marginal posteriors of selection probabilities and indicator variables for all features, which quantify the selection uncertainty. Our method not only maintains the benefits of the Bayesian treatment (e.g., uncertainty quantification) but also possesses the computational efficiency, and oracle properties of the frequentist methods. Simulation shows that our method estimates better or comparable selection probabilities and indicator variables than alternative approximate inference methods such as VB and EP, but with less running time. Extensive experiments on large real datasets demonstrate that our method often improves prediction accuracy over Bayesian automatic relevance determination, EP, and frequentist L1 type methods.
BibTeX
@inproceedings{naqvi2016fast,
  author = {Syed Abbas Zilqurnain Naqvi and Shandian Zhe and Yuan Qi and Yifan Yang and Jieping Ye},
  title = {{Fast Laplace Approximation for Sparse Bayesian Spike and Slab Models}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure