abess: Fast Best Subset Selection

Jin Zhu, Zezhi Wang, Liyuan Hu, Junhao Huang, Kangkang Jiang, Yanhang Zhang, Borui Tang, Shiyun Lin, Junxian Zhu, Canhong Wen, Heping Zhang, Xueqin WangOpenalex Unknown 2021 · DOI · OpenAlex

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:

  1. Sequencing: It generates a sequence of models with increasing support sizes (the number of predictors).
  2. 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.
Overview of core tuning parameters in the abess package, including support size and group index options.

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.

Structure of the abess class object returned after model fitting, detailing the coefficients and tuning values.

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

Abstract

Extremely efficient toolkit for solving the best subset selection problem &lt;<a href="https://www.jmlr.org/papers/v23/21-1060.html" target="_top">https://www.jmlr.org/papers/v23/21-1060.html</a>&gt;. This package is its R interface. The package implements and generalizes algorithms designed in &lt;<a href="https://doi.org/10.1073%2Fpnas.2014241117" target="_top">doi:10.1073/pnas.2014241117</a>&gt; that exploits a novel sequencing-and-splicing technique to guarantee exact support recovery and globally optimal solution in polynomial times for linear model. It also supports best subset selection for logistic regression, Poisson regression, Cox proportional hazard model, Gamma regression, multiple-response regression, multinomial logistic regression, ordinal regression, Ising model reconstruction &lt;<a href="https://doi.org/10.1080%2F01621459.2025.2571245" target="_top">doi:10.1080/01621459.2025.2571245</a>&gt;, (sequential) principal component analysis, and robust principal component analysis. The other valuable features such as the best subset of group selection &lt;<a href="https://doi.org/10.1287%2Fijoc.2022.1241" target="_top">doi:10.1287/ijoc.2022.1241</a>&gt; and sure independence screening &lt;<a href="https://doi.org/10.1111%2Fj.1467-9868.2008.00674.x" target="_top">doi:10.1111/j.1467-9868.2008.00674.x</a>&gt; are also provided.
BibTeX
@inproceedings{zhu2021abess,
  author = {Jin Zhu and Zezhi Wang and Liyuan Hu and Junhao Huang and Kangkang Jiang and Yanhang Zhang and Borui Tang and Shiyun Lin and Junxian Zhu and Canhong Wen and Heping Zhang and Xueqin Wang},
  title = {{abess: Fast Best Subset Selection}},
  booktitle = {Openalex Unknown},
  year = {2021},
  doi = {10.32614/cran.package.abess},
}
Figure