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:
- 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.
- 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$.
- 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.
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.
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