# Fast Best Subset Selection: Coordinate Descent and Local Combinatorial Optimization Algorithms

arXiv: https://arxiv.org/abs/1803.01454 · HTML: https://mlsanity.com/paper/1803.01454/

## Key facts

- Cited by 53 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Mar 2018.

## Built on by (most cited first, 30 of 53)

- [Fast as CHITA: Neural Network Pruning with Combinatorial Optimization](https://mlsanity.com/paper/2302.14623/) (2023)
- [QuantEase: Optimization-based Quantization for Language Models](https://mlsanity.com/paper/2309.01885/) (2023)
- [Fast Sparse Classification for Generalized Linear and Additive Models](https://mlsanity.com/paper/2202.11389/) (2022)
- [OSSCAR: One-Shot Structured Pruning in Vision and Language Models with Combinatorial Optimization](https://mlsanity.com/paper/2403.12983/) (2024)
- [abess: A Fast Best Subset Selection Library in Python and R](https://mlsanity.com/paper/2110.09697/) (2021)
- [Grouped Variable Selection with Discrete Optimization: Computational and Statistical Perspectives](https://mlsanity.com/paper/2104.07084/) (2021)
- [HARFE: Hard-Ridge Random Feature Expansion](https://mlsanity.com/paper/2202.02877/) (2022)
- [L0Learn: A Scalable Package for Sparse Learning using L0 Regularization](https://mlsanity.com/paper/2202.04820/) (2022)
- [FALCON: FLOP-Aware Combinatorial Optimization for Neural Network Pruning](https://mlsanity.com/paper/2403.07094/) (2024)
- [Generating collective counterfactual explanations in score-based classification via mathematical optimization](https://mlsanity.com/paper/2310.12822/) (2023)
- [A flexible empirical Bayes approach to multiple linear regression and connections with penalized regression](https://mlsanity.com/paper/2208.10910/) (2022)
- [Slowly Varying Regression under Sparsity](https://mlsanity.com/paper/2102.10773/) (2021)
- [ForestPrune: Compact Depth-Controlled Tree Ensembles](https://mlsanity.com/paper/2206.00128/) (2022)
- [Interpretable Generalized Additive Models for Datasets with Missing Values](https://mlsanity.com/paper/2412.02646/) (2024)
- [Safe Screening for Logistic Regression with ℓ0-ℓ2 Regularization](https://mlsanity.com/paper/2202.00467/) (2022)
- [SRMD: Sparse Random Mode Decomposition](https://mlsanity.com/paper/2204.06108/) (2022)
- [Sparse Gaussian Graphical Models with Discrete Optimization: Computational and Statistical Perspectives](https://mlsanity.com/paper/2307.09366/) (2023)
- [Linear regression with partially mismatched data: local search with theoretical guarantees](https://mlsanity.com/paper/2106.02175/) (2021)
- [Predicting Census Survey Response Rates With Parsimonious Additive Models and Structured Interactions](https://mlsanity.com/paper/2108.11328/) (2021)
- [Convex mixed-integer optimization with Frank-Wolfe methods](https://mlsanity.com/paper/2208.11010/) (2022)
- [Outlier detection in regression: conic quadratic formulations](https://mlsanity.com/paper/2307.05975/) (2023)
- [Data-driven discovery of governing differential equations across physical systems](https://mlsanity.com/paper/2606.09638/) (2026)
- [Lasry-Lions Envelopes and Nonconvex Optimization: A Homotopy Approach](https://mlsanity.com/paper/2103.08533/) (2021)
- [Holistic Generalized Linear Models](https://mlsanity.com/paper/2205.15447/) (2022)
- [Constrained Optimization of Rank-One Functions with Indicator Variables](https://mlsanity.com/paper/2303.18158/) (2023)
- [COMET: Learning Cardinality Constrained Mixture of Experts with Trees and Local Search](https://mlsanity.com/paper/2306.02824/) (2023)
- [SWAP: Sparse Entropic Wasserstein Regression for Robust Network Pruning](https://mlsanity.com/paper/2310.04918/) (2023)
- [Scalable Subset Selection in Linear Mixed Models](https://mlsanity.com/paper/2506.20425/) (2025)
- [Group selection and shrinkage: Structured sparsity for semiparametric additive models](https://mlsanity.com/paper/2105.12081/) (2021)
- [Feature subset selection for kernel SVM classification via mixed-integer optimization](https://mlsanity.com/paper/2205.14325/) (2022)

## Abstract (arXiv)

The L0-regularized least squares problem (a.k.a. best subsets) is central to sparse statistical learning and has attracted significant attention across the wider statistics, machine learning, and optimization communities. Recent work has shown that modern mixed integer optimization (MIO) solvers can be used to address small to moderate instances of this problem. In spite of the usefulness of L0-based estimators and generic MIO solvers, there is a steep computational price to pay when compared to popular sparse learning algorithms (e.g., based on L1 regularization). In this paper, we aim to push the frontiers of computation for a family of L0-regularized problems with additional convex penalties. We propose a new hierarchy of necessary optimality conditions for these problems. We develop fast algorithms, based on coordinate descent and local combinatorial optimization, that are guaranteed to converge to solutions satisfying these optimality conditions. From a statistical viewpoint, an interesting story emerges. When the signal strength is high, our combinatorial optimization algorithms have an edge in challenging statistical settings. When the signal is lower, pure L0 benefits from additional convex regularization. We empirically demonstrate that our family of L0-based estimators can outperform the state-of-the-art sparse learning algorithms in terms of a combination of prediction, estimation, and variable selection metrics under various regimes (e.g., different signal strengths, feature correlations, number of samples and features). Our new open-source sparse learning toolkit L0Learn (available on CRAN and Github) reaches up to a three-fold speedup (with p up to 106) when compared to competing toolkits such as glmnet and ncvreg.