Grouped variable selection with discrete optimization: computational and statistical perspectives
From MaRDI portal
Abstract: We present a new algorithmic framework for grouped variable selection that is based on discrete mathematical optimization. While there exist several appealing approaches based on convex relaxations and nonconvex heuristics, we focus on optimal solutions for the -regularized formulation, a problem that is relatively unexplored due to computational challenges. Our methodology covers both high-dimensional linear regression and nonparametric sparse additive modeling with smooth components. Our algorithmic framework consists of approximate and exact algorithms. The approximate algorithms are based on coordinate descent and local search, with runtimes comparable to popular sparse learning algorithms. Our exact algorithm is based on a standalone branch-and-bound (BnB) framework, which can solve the associated mixed integer programming (MIP) problem to certified optimality. By exploiting the problem structure, our custom BnB algorithm can solve to optimality problem instances with features and observations in minutes to hours -- over times larger than what is currently possible using state-of-the-art commercial MIP solvers. We also explore statistical properties of the -based estimators. We demonstrate, theoretically and empirically, that our proposed estimators have an edge over popular group-sparse estimators in terms of statistical performance in various regimes. We provide an open-source implementation of our proposed framework.
Recommendations
- Learning sparse classifiers: continuous and mixed integer optimization perspectives
- Fast best subset selection: coordinate descent and local combinatorial optimization algorithms
- Group variable selection via \(\ell_{p,0}\) regularization and application to optimal scoring
- Sparse regression at scale: branch-and-bound rooted in first-order optimization
- Sparse optimization for nonconvex group penalized estimation
Cites work
- A brief history of linear and mixed-integer programming computation
- A selective review of group selection in high-dimensional models
- A sparse signal reconstruction perspective for source localization with sensor arrays
- Algorithms for simultaneous sparse approximation. II: Convex relaxation
- Best subset selection via a modern optimization lens
- Branch-and-bound algorithms: a survey of recent advances in searching, branching, and pruning
- Calibrating nonconvex penalized regression in ultra-high dimension
- Component selection and smoothing in multivariate nonparametric regression
- Consistency of the group Lasso and multiple kernel learning
- Consistent group selection in high-dimensional linear regression
- Consistent model selection criteria on high dimensions
- Doubly penalized estimation in additive regression with high-dimensional data
- Factor-driven two-regime regression
- Fast best subset selection: coordinate descent and local combinatorial optimization algorithms
- Fast learning rate of multiple kernel learning: trade-off between sparsity and smoothness
- Group descent algorithms for nonconvex penalized linear and logistic regression models with grouped predictors
- High-dimensional additive modeling
- scientific article; zbMATH DE number 45848 (Why is no real title available?)
- scientific article; zbMATH DE number 1906319 (Why is no real title available?)
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- scientific article; zbMATH DE number 845714 (Why is no real title available?)
- scientific article; zbMATH DE number 5251637 (Why is no real title available?)
- Iterative hard thresholding methods for \(l_0\) regularized convex cone programming
- Iterative thresholding for sparse approximations
- Learning sparse classifiers: continuous and mixed integer optimization perspectives
- Minimax optimal rates of estimation in high dimensional additive models
- Minimax-optimal rates for sparse additive models over kernel classes via convex programming
- Mixed-integer nonlinear optimization
- Model Selection and Estimation in Regression with Grouped Variables
- Nearly unbiased variable selection under minimax concave penalty
- Nonlinear programming
- On the asymptotic properties of the group lasso estimator for linear models
- On the best search strategy in parallel branch-and-bound: Best-first search versus lazy depth-first search
- On the convergence of block coordinate descent type methods
- On the Reconstruction of Block-Sparse Signals With an Optimal Number of Measurements
- Optimal prediction for sparse linear models? Lower bounds for coordinate-separable M-estimators
- Oracle inequalities and optimal inference under group sparsity
- Perspective cuts for a class of convex 0-1 mixed integer programs
- Perspective reformulations of mixed integer nonlinear programs with indicator variables
- Scalable algorithms for the sparse ridge regression
- Some theoretical results on the grouped variables Lasso
- Sparse additive models
- Sparse and smooth signal estimation: convexification of \(\ell_0\)-formulations
- Sparse Approximate Solutions to Linear Systems
- Sparse high-dimensional regression: exact scalable algorithms and phase transitions
- Sparse HP filter: finding kinks in the COVID-19 contact rate
- Sparse regression at scale: branch-and-bound rooted in first-order optimization
- Sparse solutions to linear inverse problems with multiple measurement vectors
- SparseNet: coordinate descent with nonconvex penalties
- Sparsity constrained nonlinear optimization: optimality conditions and algorithms
- Sparsity in multiple kernel learning
- Statistics for high-dimensional data. Methods, theory and applications.
- Structured sparsity through convex optimization
- Support union recovery in high-dimensional multivariate regression
- The benefit of group sparsity
- The composite absolute penalties family for grouped and hierarchical variable selection
- The Discrete Dantzig Selector: Estimating Sparse Linear Models via Mixed Integer Linear Optimization
- The sparsity and bias of the LASSO selection in high-dimensional linear regression
- Theoretical and Empirical Results for Recovery From Multiple Measurements
- Theoretical Results on Sparse Representations of Multiple-Measurement Vectors
- Using \(\ell_1\)-relaxation and integer programming to obtain dual bounds for sparse PCA
- Variable selection in nonparametric additive models
- Variable selection using adaptive nonlinear interaction structures in high dimensions
Cited in
(13)- Learning sparse classifiers: continuous and mixed integer optimization perspectives
- Best subset selection with shrinkage: sparse additive hazards regression with the grouping effect
- Supervised homogeneity fusion: a combinatorial approach
- Cardinality minimization, constraints, and regularization: a survey
- Constrained optimization of rank-one functions with indicator variables
- Sparse quantile regression via _0-penalty
- Predicting census survey response rates with parsimonious additive models and structured interactions
- Group Selection and Shrinkage: Structured Sparsity for Semiparametric Additive Models
- Feature and functional form selection in additive models via mixed-integer optimization
- Optimal forecast reconciliation with time series selection
- Rank-one convexification for sparse regression
- Multi-task learning for sparsity pattern heterogeneity: statistical and computational perspectives
- Loss given default model for online microloans using neural network based quantile model
This page was built for publication: Grouped variable selection with discrete optimization: computational and statistical perspectives
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6046300)
