# Best Subset Selection via a Modern Optimization Lens

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

## Key facts

- Cited by 100 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Jul 2015.

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

- [Predictive Multiplicity in Probabilistic Classification](https://mlsanity.com/paper/2206.01131/) (2022)
- [Fast as CHITA: Neural Network Pruning with Combinatorial Optimization](https://mlsanity.com/paper/2302.14623/) (2023)
- [Learning Sparse Nonlinear Dynamics via Mixed-Integer Optimization](https://mlsanity.com/paper/2206.00176/) (2022)
- [Scalable Multitask Learning Using Gradient-based Estimation of Task Affinity](https://mlsanity.com/paper/2409.06091/) (2024)
- [Review of automated time series forecasting pipelines](https://mlsanity.com/paper/2202.01712/) (2022)
- [Evolving Scientific Discovery by Unifying Data and Background Knowledge with AI Hilbert](https://mlsanity.com/paper/2308.09474/) (2023)
- [OSSCAR: One-Shot Structured Pruning in Vision and Language Models with Combinatorial Optimization](https://mlsanity.com/paper/2403.12983/) (2024)
- [Optimization-based Causal Estimation from Heterogenous Environments](https://mlsanity.com/paper/2109.11990/) (2021)
- [On the Power of Preconditioning in Sparse Linear Regression](https://mlsanity.com/paper/2106.09207/) (2021)
- [SynerGPT: In-Context Learning for Personalized Drug Synergy Prediction and Drug Design](https://mlsanity.com/paper/2307.11694/) (2023)
- [Grouped Variable Selection with Discrete Optimization: Computational and Statistical Perspectives](https://mlsanity.com/paper/2104.07084/) (2021)
- [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)
- [A new perspective on low-rank optimization](https://mlsanity.com/paper/2105.05947/) (2021)
- [Foundations of Top-k Decoding For Language Models](https://mlsanity.com/paper/2505.19371/) (2025)
- [ControlBurn: Feature Selection by Sparse Forests](https://mlsanity.com/paper/2107.00219/) (2021)
- [Generating collective counterfactual explanations in score-based classification via mathematical optimization](https://mlsanity.com/paper/2310.12822/) (2023)
- [Manifold constrained steepest descent for smooth and closed-set optimization](https://mlsanity.com/paper/2601.21487/) (2026)
- [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)
- [OKRidge: Scalable Optimal k-Sparse Ridge Regression](https://mlsanity.com/paper/2304.06686/) (2023)
- [Bayesian subset selection and variable importance for interpretable prediction and classification](https://mlsanity.com/paper/2104.10150/) (2021)
- [Safe Screening for Logistic Regression with ℓ0-ℓ2 Regularization](https://mlsanity.com/paper/2202.00467/) (2022)
- [Adaptive Uncertainty-Guided Model Selection for Data-Driven PDE Discovery](https://mlsanity.com/paper/2308.10283/) (2023)
- [Conditional Matrix Flows for Gaussian Graphical Models](https://mlsanity.com/paper/2306.07255/) (2023)
- [Sparse Gaussian Graphical Models with Discrete Optimization: Computational and Statistical Perspectives](https://mlsanity.com/paper/2307.09366/) (2023)
- [SoK: A Review of Differentially Private Linear Models For High-Dimensional Data](https://mlsanity.com/paper/2404.01141/) (2024)
- [Learning Cut Generating Functions for Integer Programming](https://mlsanity.com/paper/2405.13992/) (2024)
- [A New Branch-and-Bound Pruning Framework for ℓ0-Regularized Problems](https://mlsanity.com/paper/2406.03504/) (2024)
- [A Splicing Approach to Best Subset of Groups Selection](https://mlsanity.com/paper/2104.12576/) (2021)

## Abstract (arXiv)

In the last twenty-five years (1990-2014), algorithmic advances in integer optimization combined with hardware improvements have resulted in an astonishing 200 billion factor speedup in solving Mixed Integer Optimization (MIO) problems. We present a MIO approach for solving the classical best subset selection problem of choosing k out of p features in linear regression given n observations. We develop a discrete extension of modern first order continuous optimization methods to find high quality feasible solutions that we use as warm starts to a MIO solver that finds provably optimal solutions. The resulting algorithm (a) provides a solution with a guarantee on its suboptimality even if we terminate the algorithm early, (b) can accommodate side constraints on the coefficients of the linear regression and (c) extends to finding best subset solutions for the least absolute deviation loss function. Using a wide variety of synthetic and real datasets, we demonstrate that our approach solves problems with n in the 1000s and p in the 100s in minutes to provable optimality, and finds near optimal solutions for n in the 100s and p in the 1000s in minutes. We also establish via numerical experiments that the MIO approach performs better than texttt Lasso and other popularly used sparse learning procedures, in terms of achieving sparse solutions with good predictive power.