Best subset selection via a modern optimization lens
From MaRDI portal
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 out of features in linear regression given 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 in the 1000s and in the 100s in minutes to provable optimality, and finds near optimal solutions for in the 100s and 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.
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
Cites work
- A brief history of linear and mixed-integer programming computation
- A general theory of concave regularization for high-dimensional sparse estimation problems
- A Statistical View of Some Chemometrics Regression Tools
- A unified approach to model selection and sparse recovery using regularized least squares
- Aggregation for Gaussian regression
- Algorithm for cardinality-constrained quadratic optimization
- Analysis of multi-stage convex relaxation for sparse regularization
- Asymptotic Equivalence of Regularization Methods in Thresholded Parameter Space
- Asymptotics for Lasso-type estimators.
- Atomic Decomposition by Basis Pursuit
- Best subset selection via a modern optimization lens
- Best subset selection, persistence in high-dimensional statistical learning and optimization under l₁ constraint
- Certifying the Restricted Isometry Property is Hard
- Computational study of a family of mixed-integer quadratic programming problems
- Enhancing sparsity by reweighted \(\ell _{1}\) minimization
- For most large underdetermined systems of linear equations the minimal 𝓁1‐norm solution is also the sparsest solution
- Gradient methods for minimizing composite functions
- Graph puzzles, homotopy, and the alternating group
- High-dimensional graphs and variable selection with the Lasso
- scientific article; zbMATH DE number 5957408 (Why is no real title available?)
- scientific article; zbMATH DE number 1906319 (Why is no real title available?)
- scientific article; zbMATH DE number 845714 (Why is no real title available?)
- Ideal spatial adaptation by wavelet shrinkage
- Introductory lectures on convex optimization. A basic course.
- Iterative hard thresholding for compressed sensing
- Iterative thresholding for sparse approximations
- Just relax: convex programming methods for identifying sparse signals in noise
- Least angle regression. (With discussion)
- Least quantile regression via modern optimization
- Minimax Rates of Estimation for High-Dimensional Linear Regression Over \ell_q-Balls
- Near-ideal model selection by \(\ell _{1}\) minimization
- Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
- Nearly unbiased variable selection under minimax concave penalty
- Nonconcave Penalized Likelihood With NP-Dimensionality
- On constrained and regularized high-dimensional regression
- One-step sparse estimates in nonconcave penalized likelihood models
- Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ 1 minimization
- Pathwise coordinate optimization
- Persistene in high-dimensional linear predictor-selection and the virtue of overparametrization
- Sharp Thresholds for High-Dimensional and Noisy Sparsity Recovery Using $\ell _{1}$-Constrained Quadratic Programming (Lasso)
- Simultaneous analysis of Lasso and Dantzig selector
- Smooth minimization of non-smooth functions
- Sparse Approximate Solutions to Linear Systems
- SparseNet: coordinate descent with nonconvex penalties
- Statistics for high-dimensional data. Methods, theory and applications.
- The adaptive and the thresholded Lasso for potentially misspecified models (and a lower bound for the Lasso)
- The Adaptive Lasso and Its Oracle Properties
- The restricted isometry property and its implications for compressed sensing
- The sparsity and bias of the LASSO selection in high-dimensional linear regression
- Uncertainty principles and ideal atomic decomposition
- Variable Selection via Nonconcave Penalized Likelihood and its Oracle Properties
Cited in
(only showing first 100 items - show all)- A two-stage approach to the UCITS-constrained index-tracking problem
- Extending AIC to best subset regression
- Strong formulations for quadratic optimization with M-matrices and indicator variables
- Locating hyperplanes to fitting set of points: a general framework
- Best subset binary prediction
- Linear regression with sparsely permuted data
- Cost-sensitive feature selection for support vector machines
- DC formulations and algorithms for sparse optimization problems
- Logistic regression: from art to science
- Cost-based feature selection for support vector machines: an application in credit scoring
- On the sensitivity of the Lasso to the number of predictor variables
- Lagrangian duality and saddle points for sparse linear programming
- Tractable ADMM schemes for computing KKT points and local minimizers for \(\ell_0\)-minimization problems
- Optimization problems for machine learning: a survey
- Convergent inexact penalty decomposition methods for cardinality-constrained problems
- A unified primal dual active set algorithm for nonconvex sparse recovery
- High-dimensional variable selection via low-dimensional adaptive learning
- An effective procedure for feature subset selection in logistic regression based on information criteria
- Solving nonnegative sparsity-constrained optimization via DC quadratic-piecewise-linear approximations
- Provably optimal sparse solutions to overdetermined linear systems with non-negativity constraints in a least-squares sense by implicit enumeration
- Sparse classification: a scalable discrete optimization perspective
- Smoothing Newton method for \(\ell^0\)-\(\ell^2\) regularized linear inverse problem
- A guide for sparse PCA: model comparison and applications
- Robust subset selection
- New bounds for subset selection from conic relaxations
- Mining events with declassified diplomatic documents
- Variable selection in convex quantile regression: \(\mathcal{L}_1\)-norm or \(\mathcal{L}_0\)-norm regularization?
- A convex relaxation framework consisting of a primal-dual alternative algorithm for solving \(\ell_0\) sparsity-induced optimization problems with application to signal recovery based image restoration
- Sparse regression at scale: branch-and-bound rooted in first-order optimization
- Constructing two-level \(Q_B\)-optimal screening designs using mixed-integer programming and heuristic algorithms
- Adaptive iterative hard thresholding for least absolute deviation problems with sparsity constraints
- Sparse regression over clusters: SparClur
- Ideal formulations for constrained convex optimization problems with indicator variables
- Clustering, multicollinearity, and singular vectors
- Predicting the equity market risk premium: a model selection approach
- The backbone method for ultra-high dimensional sparse machine learning
- Detecting racial bias in jury selection
- A solution approach for cardinality minimization problem based on fractional programming
- Sparse high-dimensional regression: exact scalable algorithms and phase transitions
- Subset selection for multiple linear regression via optimization
- Best subset selection via cross-validation criterion
- Matrix completion with nonconvex regularization: spectral operators and scalable algorithms
- A Bayesian perspective of statistical machine learning for big data
- Certifiably optimal sparse inverse covariance estimation
- Semi-automated simultaneous predictor selection for regression-SARIMA models
- Sparse HP filter: finding kinks in the COVID-19 contact rate
- Sparse regression: scalable algorithms and empirical performance
- Best subset, forward stepwise or Lasso? Analysis and recommendations based on extensive comparisons
- A discussion on practical considerations with sparse regression methodologies
- Discussion of ``Best subset, forward stepwise or Lasso? Analysis and recommendations based on extensive comparisons
- Modern variable selection in action: comment on the papers by HTT and BPV
- A look at robustness and stability of \(\ell_1\)-versus \(\ell_0\)-regularization: discussion of papers by Bertsimas et al. and Hastie et al.
- Rejoinder: ``Sparse regression: scalable algorithms and empirical performance
- On sparse ensemble methods: an application to short-term predictions of the evolution of COVID-19
- Leveraged least trimmed absolute deviations
- Simplex QP-based methods for minimizing a conic quadratic objective over polyhedra
- An efficient optimization approach for best subset selection in linear regression, with application to model selection and fitting in autoregressive time-series
- Certifiably optimal sparse principal component analysis
- On integer and MPCC representability of affine sparsity
- An offline/online procedure for dual norm calculations of parameterized functionals: empirical quadrature and empirical test spaces
- Divide-and-conquer information-based optimal subdata selection algorithm
- Investigating consumers' store-choice behavior via hierarchical variable selection
- On support vector machines under a multiple-cost scenario
- On cutting planes for cardinality-constrained linear programs
- 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
- Graph structured sparse subset selection
- Newton method for \(\ell_0\)-regularized optimization
- Bayesian selection of best subsets via hybrid search
- A review of the role of heuristics in stochastic optimisation: from metaheuristics to learnheuristics
- Smoothed quantile regression with large-scale inference
- Combinatorial optimization. Abstracts from the workshop held November 7--13, 2021 (hybrid meeting)
- OR forum: An algorithmic approach to linear regression
- Mixed integer nonlinear program for minimization of Akaike's information criterion
- Best subset selection via a modern optimization lens
- Feature subset selection for logistic regression via mixed integer optimization
- A new approach to select the best subset of predictors in linear regression modelling: bi-objective mixed integer linear programming
- Piecewise Linear Function Fitting via Mixed-Integer Linear Programming
- scientific article; zbMATH DE number 3940420 (Why is no real title available?)
- scientific article; zbMATH DE number 6982301 (Why is no real title available?)
- Minimization of Akaike's information criterion in linear regression analysis via mixed integer nonlinear program
- A first derivative Potts model for segmentation and denoising using ILP
- Integer constraints for enhancing interpretability in linear regression
- Optimization for L1-Norm Error Fitting via Data Aggregation
- Sparse Convex Regression
- On the Solution of ℓ0-Constrained Sparse Inverse Covariance Estimation Problems
- A Mixed-Integer Fractional Optimization Approach to Best Subset Selection
- Sparse and smooth signal estimation: convexification of \(\ell_0\)-formulations
- Outlier detection in time series via mixed-integer conic quadratic optimization
- scientific article; zbMATH DE number 7387624 (Why is no real title available?)
- Sparse index tracking using sequential Monte Carlo
- On the convexification of constrained quadratic optimization problems with indicator variables
- L0-Regularized Learning for High-Dimensional Additive Hazards Regression
- Global optimization for sparse solution of least squares problems
- A penalty decomposition approach for multi-objective cardinality-constrained optimization problems
- An Alternating Method for Cardinality-Constrained Optimization: A Computational Study for the Best Subset Selection and Sparse Portfolio Problems
- A Computational Framework for Solving Nonlinear Binary Optimization Problems in Robust Causal Inference
- Stability Representations of Many-to-One Matching Problems: An Integer Optimization Approach
- MIP-BOOST: Efficient and Effective L0 Feature Selection for Linear Regression
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)
