Best Subset Selection via a Modern Optimization Lens

By Dimitris J. Bertsimas, Angela King, Rahul Mazumder. 2015

758 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Mechanics, Statistics and Probability, Statistical Learning Theory, Mathematical Optimization

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Statistics and Probability

In Statistical Learning Theory

In Mathematical Optimization

Citations in the corpus

Machine Learning Methods That Economists Should Know About (2019, methodology): “As q → 0, the solution penalizes the number of non-zero covariates, leading to best subset regression (Miller [2002], Bertsimas et al. [2016]). In addition there are many hybrid methods and modifications, including elastic nets which combines penalty terms from LASSO and ridge (Zou and Hastie [2005]”
Learning Optimal and Fair Decision Trees for Non-Discriminative Decision-Making (2019, background): “…paper also relates to a nascent stream of research that leverages mixed-integer programming (MIP) to address ML tasks for which heuristics were traditionally employed (Bertsimas, King, and Mazumder 2015; Lou et al. 2013b; Mazumder and Radchenko 2015; Bertsimas and Dunn 2017; Verwer and Zhang 2017).”
Learning Optimized Risk Scores (2016, background): “, 2016; Wang and Rudin, 2015) and other `0-regularized models (Sato et al., 2015, 2016; Bertsimas et al., 2016).”
Extended Comparisons of Best Subset Selection, Forward Stepwise Selection, and the Lasso (2017, positive): “2 What is a realistic signal-to-noise ratio? In their simulation studies, Bertsimas et al. (2016) considered SNRs in the range of about 2 to 8 in their low-dimensional cases, and about 3 to 10 in their high-dimensional cases.”
Learning to Branch in Mixed Integer Programming (2016, methodology): “Recently, discrete optimization has been successfully lever-aged to improve machine learning (ML) methodology (Roth and Yih 2005; Bertsimas, King, and Mazumder 2015).”
Optimal trees for prediction and prescription (2018, background): “Coupled with the increase in computer hardware during this same period as shown in Figure 1-7, a factor of approximately 1,560,000 [113], the overall speedup factor is approximately 2 trillion! This astonishing increase in MIO solver performance has enabled many recent successes when applying modern”
Linear regression with sparsely permuted data (2017, background): “Due to recent advances in integer programming that have meanwhile been taken advantage of for a series of other statistical problems [8, 9], it turns out that problem (18) is practically feasible at least for n in the order of a few thousands.”
Designing Fair, Efficient, and Interpretable Policies for Prioritizing Homeless Youth for Housing Resources (2018, methodology): “Our work is also related to recent applications of mixed-integer programming to machine learning [3, 17, 18].”
Optimization of Tree Ensembles (2017, methodology): “Outside of decision tree models, Bertsimas and King (2015) consider an MIO approach to model selection in linear regression; and Bertsimas et al. (2016a) consider an MIO approach to best subset selection in linear regression.”
IPBoost - Non-Convex Boosting via Integer Programming (2020, background): “…to incorporate combinatorial structure in classification, see, e.g., (Bertsimas & Shioda, 2007; Chang et al., 2012; Bertsimas & King, 2015; Bertsimas et al., 2016), as well as, (Günlük et al., 2016; Bertsimas & Dunn, 2017; Dash et al., 2018; Günlük et al., 2018; Verwer & Zhang, 2019);…”
The Discrete Dantzig Selector: Estimating Sparse Linear Models via Mixed Integer Linear Optimization (2015, methodology): “Thus, it is not directly amenable to simple proximal gradient type algorithms [37, 38, 7].”
Robust Classification (2019, methodology): “…optimization (MIO) methods to solve problems in classical statistics, such as the least quantile squares (Bertsimas and Mazumder 2014) and best subset selection problems (Bertsimas et al. 2016), and to create algorithmic approaches for fitting regression models (Bertsimas and King 2015, 2017).”
The Preference Survey Module: A Validated Instrument for Measuring Risk, Time, and Social Preferences (2016, methodology): “We use a model selection approach, in the spirit of best subset selection (see, e.g., Hocking and Leslie 1967, Bertsimas et al. 2016), which consists of testing all possible combinations of our items using information criteria and then selecting the best model in terms of minimizing mean squared…”
Piecewise-Linear Approximation for Feature Subset Selection in a Sequential Logit Model (2015, background): “The mixed integer optimization (MIO) approach to feature subset selection has recently received a lot of attention as a result of algorithmic advances and hardware improvements (see, e.g., [10, 21, 22, 25, 26]).”
Spectral Algorithms for Computing Fair Support Vector Machines (2017, methodology): “ inﬁnite-dimensional since it must hold for all t ∈ R. 4.1.2 Integer Constraints An initial idea to incorporate (6) in the linear SVM is based on recent empirical results [Miyashiro and Takano, 2015, Bertsimas et al., 2016] where mixed integer programming (MIP) was used to exactly solve cardinality ”
Optimization Models for Machine Learning: A Survey (2019, methodology): “As discussed in [33, 31], sparse regression can be formulated as the best subset selection problem [162]”