Abstract
The abess package provides an extremely efficient toolkit for solving the best subset selection problem. By implementing a novel sequencing-and-splicing technique, it guarantees exact support recovery and globally optimal solutions in polynomial time for linear models. Beyond standard regression, it supports logistic, Poisson, Cox, and Gamma regressions, as well as Ising model reconstruction, multiple-response regression, and various PCA methods. This package serves as a high-performance R interface to the underlying C++ implementation, bridging the gap between theoretical optimality and practical computational speed.
The Challenge of Best Subset Selection
In statistics and machine learning, the goal of feature selection is to find the simplest model that maintains high predictive accuracy. Best subset selection—identifying the absolute best sparse model for a given data set—is considered the "holy grail" of this field. However, it has historically been a computational nightmare, classified as an NP-hard problem. This has forced researchers to rely on "greedy" approximations like LASSO or stepwise selection, which are fast but often fail to find the true optimal set of predictors, particularly when features are highly correlated.
The Sequencing-and-Splicing Approach
The core innovation of abess (Adaptive Best Subset Selection) is the sequencing-and-splicing technique. The algorithm operates in two main phases:
- Sequencing: It generates a sequence of models with increasing support sizes (the number of predictors).
- Splicing: This phase allows the algorithm to swap sets of variables in and out of the model. Unlike traditional stepwise methods that only add or remove one variable at a time, splicing enables the search to "jump" out of local minima to find the global optimum.
This approach turns a theoretically "impossible" problem into a practical tool, achieving exact support recovery in polynomial time for linear models. The package also includes automated tuning using Information Criteria (such as GIC, AIC, or BIC) or cross-validation to determine the optimal number of predictors for a given dataset.
Broad Model Support and Advanced Features
abess is not limited to simple linear regression. It unifies a wide variety of statistical tasks under a single sparse optimization umbrella:
- Generalized Linear Models (GLMs): Includes Logistic, Poisson, Cox (survival), Gamma, Multinomial, and Ordinal regression.
- Graphical Models: Ising model reconstruction for undirected graphical models.
- Dimensionality Reduction: Sparse PCA and Robust PCA (decomposing a matrix into low-rank and sparse components).
- Advanced Selection: Support for group selection (selecting variables in predefined blocks) and Sure Independence Screening (SIS) for ultra-high dimensional "big data" applications.
Performance and Practical Utility
Implemented with a high-performance C++ backend via Rcpp, abess is designed to handle large-scale datasets efficiently. It is particularly robust in "small $n$, large $p$" scenarios, such as the trim32 mammalian eye tissue dataset, where identifying a small number of relevant genes among hundreds of probes is critical.
The package provides a comprehensive output for users, including a matrix of coefficients for different support sizes, deviance measures, and the final selected "best" model size. While the linear model has the strongest theoretical guarantees, the performance on non-Gaussian models remains highly efficient, relying on optimized Newton-iteration convergence.
Conclusion
abess represents a significant leap forward in sparse modeling. By combining the theoretical rigor of best subset selection with the speed of modern algorithmic techniques, it provides researchers with a versatile and powerful toolkit for high-dimensional data analysis.
Summary updated