Best subset selection via a modern optimization lens

DOI10.1214/15-AOS1388zbMATH Open1335.62115arXiv1507.03133OpenAlexW2963351303MaRDI QIDQ282479FDOQ282479

Authors: Angela King, Rahul Mazumder, Dimitris Bertsimas 

Publication date: 12 May 2016

Published in: The Annals of Statistics (Search for Journal in Brave)

Abstract: 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 { exttt {Lasso}} and other popularly used sparse learning procedures, in terms of achieving sparse solutions with good predictive power.

Full work available at URL: https://arxiv.org/abs/1507.03133

Recommendations

• OR forum: An algorithmic approach to linear regression
• An efficient optimization approach for best subset selection in linear regression, with application to model selection and fitting in autoregressive time-series
• Fast best subset selection: coordinate descent and local combinatorial optimization algorithms
• A new approach to select the best subset of predictors in linear regression modelling: bi-objective mixed integer linear programming
• An effective procedure for feature subset selection in logistic regression based on information criteria

zbMATH Keywords

algorithmslassoglobal optimizationleast absolute deviationmixed integer programming\(\ell_{0}\)-constrained minimizationbest subset selectiondiscrete optimizationsparse linear regression

Mathematics Subject Classification ID

Nonparametric robustness (62G35) Linear regression; mixed models (62J05) Ridge regression; shrinkage estimators (Lasso) (62J07) Nonconvex programming, global optimization (90C26) Combinatorial optimization (90C27) Mixed integer programming (90C11)

Cites Work

• Nearly unbiased variable selection under minimax concave penalty
• SparseNet: coordinate descent with nonconvex penalties
• A unified approach to model selection and sparse recovery using regularized least squares
• The Adaptive Lasso and Its Oracle Properties
• Least angle regression. (With discussion)
• Pathwise coordinate optimization
• Ideal spatial adaptation by wavelet shrinkage
• Variable Selection via Nonconcave Penalized Likelihood and its Oracle Properties
• Title not available (Why is that?)
• Statistics for high-dimensional data. Methods, theory and applications.
• One-step sparse estimates in nonconcave penalized likelihood models
• Simultaneous analysis of Lasso and Dantzig selector
• High-dimensional graphs and variable selection with the Lasso
• Best subset selection via a modern optimization lens
• Analysis of multi-stage convex relaxation for sparse regularization
• Title not available (Why is that?)
• Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
• Atomic Decomposition by Basis Pursuit
• Sharp Thresholds for High-Dimensional and Noisy Sparsity Recovery Using $\ell _{1}$-Constrained Quadratic Programming (Lasso)
• Enhancing sparsity by reweighted \(\ell _{1}\) minimization
• Smooth minimization of non-smooth functions
• Introductory lectures on convex optimization. A basic course.
• Persistene in high-dimensional linear predictor-selection and the virtue of overparametrization
• Asymptotics for Lasso-type estimators.
• Gradient methods for minimizing composite functions
• Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ ¹ minimization
• The sparsity and bias of the LASSO selection in high-dimensional linear regression
• Asymptotic Equivalence of Regularization Methods in Thresholded Parameter Space
• Minimax Rates of Estimation for High-Dimensional Linear Regression Over $\ell_q$-Balls
• Just relax: convex programming methods for identifying sparse signals in noise
• A Statistical View of Some Chemometrics Regression Tools
• Title not available (Why is that?)
• The adaptive and the thresholded Lasso for potentially misspecified models (and a lower bound for the Lasso)
• Aggregation for Gaussian regression
• For most large underdetermined systems of linear equations the minimal 𝓁₁‐norm solution is also the sparsest solution
• A general theory of concave regularization for high-dimensional sparse estimation problems
• Iterative hard thresholding for compressed sensing
• Uncertainty principles and ideal atomic decomposition
• Sparse Approximate Solutions to Linear Systems
• Iterative thresholding for sparse approximations
• Best subset selection, persistence in high-dimensional statistical learning and optimization under \(l_1\) constraint
• The restricted isometry property and its implications for compressed sensing
• Computational study of a family of mixed-integer quadratic programming problems
• Graph puzzles, homotopy, and the alternating group
• A brief history of linear and mixed-integer programming computation
• Certifying the Restricted Isometry Property is Hard
• On constrained and regularized high-dimensional regression
• Least quantile regression via modern optimization
• Nonconcave Penalized Likelihood With NP-Dimensionality
• Near-ideal model selection by \(\ell _{1}\) minimization
• Algorithm for cardinality-constrained quadratic optimization

Cited In (only showing first 100 items - show all)

• Factor-driven two-regime regression
• Optimal $k$-Thresholding Algorithms for Sparse Optimization Problems
• An attention algorithm for solving large scale structured \(l_0\)-norm penalty estimation problems
• Fitting sparse linear models under the sufficient and necessary condition for model identification
• Fast best subset selection: coordinate descent and local combinatorial optimization algorithms
• Simplex QP-based methods for minimizing a conic quadratic objective over polyhedra
• Sparse high-dimensional regression: exact scalable algorithms and phase transitions
• Certifiably optimal sparse principal component analysis
• Sparse regression: scalable algorithms and empirical performance
• Cost-sensitive feature selection for support vector machines
• Cost-based feature selection for support vector machines: an application in credit scoring
• A unified approach to mixed-integer optimization problems with logical constraints
• Lagrangian duality and saddle points for sparse linear programming
• Scalable algorithms for the sparse ridge regression
• Combinatorial optimization. Abstracts from the workshop held November 7--13, 2021 (hybrid meeting)
• DC formulations and algorithms for sparse optimization problems
• On the Solution of ℓ₀-Constrained Sparse Inverse Covariance Estimation Problems
• Semi-automated simultaneous predictor selection for regression-SARIMA models
• Sparse classification: a scalable discrete optimization perspective
• Logistic regression: from art to science
• Leveraged least trimmed absolute deviations
• A two-stage approach to the UCITS-constrained index-tracking problem
• Piecewise Linear Function Fitting via Mixed-Integer Linear Programming
• Solving nonnegative sparsity-constrained optimization via DC quadratic-piecewise-linear approximations
• L₀-Regularized Learning for High-Dimensional Additive Hazards Regression
• Best subset binary prediction
• Title not available (Why is that?)
• Feature subset selection for logistic regression via mixed integer optimization
• Extending AIC to best subset regression
• Sparse regression over clusters: SparClur
• An Alternating Method for Cardinality-Constrained Optimization: A Computational Study for the Best Subset Selection and Sparse Portfolio Problems
• Locating hyperplanes to fitting set of points: a general framework
• Tractable ADMM schemes for computing KKT points and local minimizers for \(\ell_0\)-minimization problems
• Convergent inexact penalty decomposition methods for cardinality-constrained problems
• Certifiably optimal sparse inverse covariance estimation
• A discussion on practical considerations with sparse regression methodologies
• Optimization problems for machine learning: a survey
• Smoothed quantile regression with large-scale inference
• An efficient optimization approach for best subset selection in linear regression, with application to model selection and fitting in autoregressive time-series
• A First-Order Optimization Algorithm for Statistical Learning with Hierarchical Sparsity Structure
• Predicting the equity market risk premium: a model selection approach
• Sparse Convex Regression
• Structural properties of affine sparsity constraints
• Blessing of massive scale: spatial graphical model estimation with a total cardinality constraint approach
• Mixed integer quadratic optimization formulations for eliminating multicollinearity based on variance inflation factor
• Efficient subset selection for the expected opportunity cost
• On the sensitivity of the Lasso to the number of predictor variables
• Investigating consumers' store-choice behavior via hierarchical variable selection
• OR forum: An algorithmic approach to linear regression
• Resolvability of Hamming graphs
• Subset selection for multiple linear regression via optimization
• Linear biomarker combination for constrained classification
• Best subset selection via a modern optimization lens
• On the convexification of constrained quadratic optimization problems with indicator variables
• On cutting planes for cardinality-constrained linear programs
• Sparse hierarchical regression with polynomials
• Ideal formulations for constrained convex optimization problems with indicator variables
• Fast and approximate exhaustive variable selection for generalised linear models with APES
• Matrix completion with nonconvex regularization: spectral operators and scalable algorithms
• Strong formulations for quadratic optimization with M-matrices and indicator variables
• Integer constraints for enhancing interpretability in linear regression
• An offline/online procedure for dual norm calculations of parameterized functionals: empirical quadrature and empirical test spaces
• Title not available (Why is that?)
• A Scalable Algorithm for Sparse Portfolio Selection
• A greedy feature selection algorithm for big data of high dimensionality
• Provably optimal sparse solutions to overdetermined linear systems with non-negativity constraints in a least-squares sense by implicit enumeration
• Linear regression with sparsely permuted data
• Sparse regression at scale: branch-and-bound rooted in first-order optimization
• Title not available (Why is that?)
• Title not available (Why is that?)
• Non-marginal feature screening for additive hazard model with ultrahigh-dimensional covariates
• Optimal classification trees
• Sparse optimization via vector \(k\)-norm and DC programming with an application to feature selection for support vector machines
• A Bayesian perspective of statistical machine learning for big data
• Newton method for \(\ell_0\)-regularized optimization
• Estimation of \(l_0\) norm penalized models: a statistical treatment
• Partially egalitarian portfolio selection
• Numerical characterization of support recovery in sparse regression with correlated design
• On the convergence of inexact alternate minimization in problems with \(\ell_0\) penalties
• Subset selection in network-linked data
• A Mixed-Integer Fractional Optimization Approach to Best Subset Selection
• The EAS approach to variable selection for multivariate response data in high-dimensional settings
• Constructing two-level \(Q_B\)-optimal screening designs using mixed-integer programming and heuristic algorithms
• Discussion of ``Best subset, forward stepwise or Lasso? Analysis and recommendations based on extensive comparisons
• Joint outlier detection and variable selection using discrete optimization
• Simultaneous feature selection and outlier detection with optimality guarantees
• Mathematical programming for simultaneous feature selection and outlier detection under l1 norm
• Divide-and-conquer information-based optimal subdata selection algorithm
• On sparse ensemble methods: an application to short-term predictions of the evolution of COVID-19
• Gaussian Process Assisted Active Learning of Physical Laws
• Budget constrained model selection for multiple linear regression
• On computing medians of marked point process data under edit distance
• Adaptive iterative hard thresholding for least absolute deviation problems with sparsity constraints
• A new approach to select the best subset of predictors in linear regression modelling: bi-objective mixed integer linear programming
• Modern variable selection in action: comment on the papers by HTT and BPV
• Sparse HP filter: finding kinks in the COVID-19 contact rate
• Rejoinder: ``Sparse regression: scalable algorithms and empirical performance
• On support vector machines under a multiple-cost scenario
• Bayesian \(l_0\)-regularized least squares
• An automated exact solution framework towards solving the logistic regression best subset selection problem

Uses Software

• Gurobi
• PDCO
• ElemStatLearn
• sparsenet
• boost

This page was built for publication: Best subset selection via a modern optimization lens

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q282479)