Best subset selection via a modern optimization lens

DOI10.1214/15-AOS1388zbMath1335.62115arXiv1507.03133OpenAlexW2963351303MaRDI QIDQ282479

Angela King, Rahul Mazumder, Dimitris J. Bertsimas

Publication date: 12 May 2016

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

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

zbMATH Keywords

algorithmsglobal optimizationmixed integer programmingleast absolute deviationdiscrete optimizationlasso\(\ell_{0}\)-constrained minimizationbest subset selectionsparse linear regression

Mathematics Subject Classification ID

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

Related Items (only showing first 100 items - show all)

Learning Optimized Risk Scores ⋮ 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 L₀ Feature Selection for Linear Regression ⋮ Non-marginal feature screening for additive hazard model with ultrahigh-dimensional covariates ⋮ Linear Time Dynamic Programming for Computing Breakpoints in the Regularization Path of Models Selected From a Finite Set ⋮ A First-Order Optimization Algorithm for Statistical Learning with Hierarchical Sparsity Structure ⋮ Subset selection in network-linked data ⋮ General Feasibility Bounds for Sample Average Approximation via Vapnik--Chervonenkis Dimension ⋮ A Scalable Algorithm for Sparse Portfolio Selection ⋮ Improved RIP-based bounds for guaranteed performance of two compressed sensing algorithms ⋮ A reformulation technique to solve polynomial optimization problems with separable objective functions of bounded integer variables ⋮ Grouped variable selection with discrete optimization: computational and statistical perspectives ⋮ Sparse optimization via vector \(k\)-norm and DC programming with an application to feature selection for support vector machines ⋮ A new perspective on low-rank optimization ⋮ Compositional knockoff filter for high‐dimensional regression analysis of microbiome data ⋮ Simultaneous feature selection and outlier detection with optimality guarantees ⋮ Subset Selection for Linear Mixed Models ⋮ The EAS approach for graphical selection consistency in vector autoregression models ⋮ Learning sparse nonlinear dynamics via mixed-integer optimization ⋮ Solution sets of three sparse optimization problems for multivariate regression ⋮ The min-Knapsack problem with compactness constraints and applications in statistics ⋮ L ₀ -regularization for high-dimensional regression with corrupted data ⋮ Sparse convex optimization toolkit: a mixed-integer framework ⋮ Communication-efficient estimation for distributed subset selection ⋮ Deconfounding and Causal Regularisation for Stability and External Validity ⋮ A graph-based decomposition method for convex quadratic optimization with indicators ⋮ A unified framework for bivariate clustering and regression problems via mixed-integer linear programming ⋮ Sparsifying the least-squares approach to PCA: comparison of lasso and cardinality constraint ⋮ Sparse quantile regression ⋮ Time series modeling and forecasting by mathematical programming ⋮ Polyhedral results and stronger Lagrangean bounds for stable spanning trees ⋮ The EAS approach to variable selection for multivariate response data in high-dimensional settings ⋮ Budget constrained model selection for multiple linear regression ⋮ On computing medians of marked point process data under edit distance ⋮ An automated exact solution framework towards solving the logistic regression best subset selection problem ⋮ Nearly Dimension-Independent Sparse Linear Bandit over Small Action Spaces via Best Subset Selection ⋮ Sparse regression for data-driven deterrence functions in gravity models ⋮ Distributed primal outer approximation algorithm for sparse convex programming with separable structures ⋮ Best subset selection with shrinkage: sparse additive hazards regression with the grouping effect ⋮ Scaled proximal gradient methods for sparse optimization problems ⋮ An \(\ell_{2,0}\)-norm constrained matrix optimization via extended discrete first-order algorithms ⋮ Inference in a Class of Optimization Problems: Confidence Regions and Finite Sample Bounds on Errors in Coverage Probabilities ⋮ Supervised homogeneity fusion: a combinatorial approach ⋮ Subset Selection and the Cone of Factor-Width-k Matrices ⋮ Mixed-integer quadratic programming reformulations of multi-task learning models ⋮ Fast and approximate exhaustive variable selection for generalised linear models with APES ⋮ Unnamed Item ⋮ Resolvability of Hamming Graphs ⋮ Convex Optimization for Group Feature Selection in Networked Data ⋮ Scalable Algorithms for the Sparse Ridge Regression ⋮ A Unified Approach to Mixed-Integer Optimization Problems With Logical Constraints ⋮ The Trimmed Lasso: Sparse Recovery Guarantees and Practical Optimization by the Generalized Soft-Min Penalty ⋮ A polynomial algorithm for best-subset selection problem ⋮ Optimal classification trees ⋮ Optimal $k$-Thresholding Algorithms for Sparse Optimization Problems ⋮ A Duality-Based Method for Identifying Elemental Balance Violations in Metabolic Network Models ⋮ Fast Best Subset Selection: Coordinate Descent and Local Combinatorial Optimization Algorithms ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Group Sparse Optimization for Images Recovery Using Capped Folded Concave Functions ⋮ Best-subset model selection based on multitudinal assessments of likelihood improvements ⋮ Factor-driven two-regime regression ⋮ 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 ⋮ Sparse index tracking using sequential Monte Carlo ⋮ Best subset selection via a modern optimization lens ⋮ On the Convexification of Constrained Quadratic Optimization Problems with Indicator Variables ⋮ Integer constraints for enhancing interpretability in linear regression ⋮ Feature subset selection for logistic regression via mixed integer optimization ⋮ A two-stage approach to the UCITS-constrained index-tracking problem ⋮ Mixed integer quadratic optimization formulations for eliminating multicollinearity based on variance inflation factor ⋮ Clustering, multicollinearity, and singular vectors ⋮ L₀-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 ⋮ 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 ⋮ 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 ⋮ Best subset binary prediction ⋮ Graph structured sparse subset selection ⋮ Sparse high-dimensional regression: exact scalable algorithms and phase transitions ⋮ Newton method for \(\ell_0\)-regularized optimization ⋮ Bayesian selection of best subsets via hybrid search ⋮ Subset selection for multiple linear regression via optimization ⋮ A review of the role of heuristics in stochastic optimisation: from metaheuristics to learnheuristics ⋮ Best subset selection via cross-validation criterion ⋮ Smoothed quantile regression with large-scale inference ⋮ Unnamed Item ⋮ Structural properties of affine sparsity constraints ⋮ Blessing of massive scale: spatial graphical model estimation with a total cardinality constraint approach ⋮ Matrix completion with nonconvex regularization: spectral operators and scalable algorithms ⋮ Combinatorial optimization. Abstracts from the workshop held November 7--13, 2021 (hybrid meeting)

Uses Software

• Gurobi
• PDCO
• ElemStatLearn
• sparsenet
• boost

Cites Work

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

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