Sparse high-dimensional regression: exact scalable algorithms and phase transitions
From MaRDI portal
Abstract: We present a novel binary convex reformulation of the sparse regression problem that constitutes a new duality perspective. We devise a new cutting plane method and provide evidence that it can solve to provable optimality the sparse regression problem for sample sizes n and number of regressors p in the 100,000s, that is two orders of magnitude better than the current state of the art, in seconds. The ability to solve the problem for very high dimensions allows us to observe new phase transition phenomena. Contrary to traditional complexity theory which suggests that the difficulty of a problem increases with problem size, the sparse regression problem has the property that as the number of samples increases the problem becomes easier in that the solution recovers 100% of the true signal, and our approach solves the problem extremely fast (in fact faster than Lasso), while for small number of samples n, our approach takes a larger amount of time to solve the problem, but importantly the optimal solution provides a statistically more relevant regressor. We argue that our exact sparse regression approach presents a superior alternative over heuristic methods available at present.
Recommendations
- Sparse high-dimensional linear regression. Estimating squared error and a phase transition
- Sparse hierarchical regression with polynomials
- A sparsity preserving stochastic gradient methods for sparse regression
- A comparison of the Lasso and marginal regression
- Square-root lasso: pivotal recovery of sparse signals via conic programming
Cites work
- scientific article; zbMATH DE number 1304261 (Why is no real title available?)
- scientific article; zbMATH DE number 845714 (Why is no real title available?)
- scientific article; zbMATH DE number 6438182 (Why is no real title available?)
- A brief history of linear and mixed-integer programming computation
- An outer-approximation algorithm for a class of mixed-integer nonlinear programs
- Best subset selection via a modern optimization lens
- Branch-and-Bound Methods: A Survey
- Branch-and-price: Column generation for solving huge integer programs
- Does $\ell _{p}$ -Minimization Outperform $\ell _{1}$ -Minimization?
- Matching pursuits with time-frequency dictionaries
- Nearly unbiased variable selection under minimax concave penalty
- Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing
- On general minimax theorems
- On the Performance of Sparse Recovery Via $\ell_p$-Minimization $(0 \leq p \leq 1)$
- Regressions by Leaps and Bounds
- Regularization and Variable Selection Via the Elastic Net
- Robustness and regularization of support vector machines
- Sharp Thresholds for High-Dimensional and Noisy Sparsity Recovery Using $\ell _{1}$-Constrained Quadratic Programming (Lasso)
- Solving mixed integer nonlinear programs by outer approximation
- Sparse high-dimensional linear regression. Estimating squared error and a phase transition
- Sparse high-dimensional regression: exact scalable algorithms and phase transitions
- Sparse regression: scalable algorithms and empirical performance
- Statistics for high-dimensional data. Methods, theory and applications.
- Updating the Inverse of a Matrix
- Variable Selection via Nonconcave Penalized Likelihood and its Oracle Properties
Cited in
(54)- A Mixed-Integer Fractional Optimization Approach to Best Subset Selection
- Sparse high-dimensional regression: exact scalable algorithms and phase transitions
- Discussion of ``Best subset, forward stepwise or Lasso? Analysis and recommendations based on extensive comparisons
- Sparse regression: scalable algorithms and empirical performance
- Simultaneous feature selection and outlier detection with optimality guarantees
- 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
- SRMD: sparse random mode decomposition
- The trimmed Lasso: sparse recovery guarantees and practical optimization by the generalized soft-min penalty
- A unified approach to mixed-integer optimization problems with logical constraints
- Cardinality minimization, constraints, and regularization: a survey
- Combinatorial optimization. Abstracts from the workshop held November 7--13, 2021 (hybrid meeting)
- Scalable algorithms for the sparse ridge regression
- Sparse classification: a scalable discrete optimization perspective
- scientific article; zbMATH DE number 7625166 (Why is no real title available?)
- Grouped variable selection with discrete optimization: computational and statistical perspectives
- HARFE: hard-ridge random feature expansion
- A look at robustness and stability of \(\ell_1\)-versus \(\ell_0\)-regularization: discussion of papers by Bertsimas et al. and Hastie et al.
- MIP-BOOST: Efficient and Effective L0 Feature Selection for Linear Regression
- Sparse regression over clusters: SparClur
- scientific article; zbMATH DE number 7370569 (Why is no real title available?)
- Exterior-point optimization for sparse and low-rank optimization
- scientific article; zbMATH DE number 7415078 (Why is no real title available?)
- An Alternating Method for Cardinality-Constrained Optimization: A Computational Study for the Best Subset Selection and Sparse Portfolio Problems
- Certifiably optimal sparse inverse covariance estimation
- Stochastic Cutting Planes for Data-Driven Optimization
- A discussion on practical considerations with sparse regression methodologies
- Convex optimization under combinatorial sparsity constraints
- Optimization problems for machine learning: a survey
- An efficient optimization approach for best subset selection in linear regression, with application to model selection and fitting in autoregressive time-series
- Sparse high-dimensional linear regression. Estimating squared error and a phase transition
- A First-Order Optimization Algorithm for Statistical Learning with Hierarchical Sparsity Structure
- Bicriteria algorithms to balance coverage and cost in team formation under online model
- Sparse Convex Regression
- Sparse quantile regression
- The backbone method for ultra-high dimensional sparse machine learning
- Best subset, forward stepwise or Lasso? Analysis and recommendations based on extensive comparisons
- Sparsifying the least-squares approach to PCA: comparison of lasso and cardinality constraint
- Subset Selection and the Cone of Factor-Width-k Matrices
- Constrained optimization of rank-one functions with indicator variables
- Detecting racial bias in jury selection
- How can we identify the sparsity structure pattern of high-dimensional data: an elementary statistical analysis to interpretable machine learning
- Weaker regularity conditions and sparse recovery in high-dimensional regression
- A new perspective on low-rank optimization
- Sparse hierarchical regression with polynomials
- Ideal formulations for constrained convex optimization problems with indicator variables
- Robust subset selection
- Learning sparse nonlinear dynamics via mixed-integer optimization
- The sparse(st) optimization problem: reformulations, optimality, stationarity, and numerical results
- A Scalable Algorithm for Sparse Portfolio Selection
- Variable selection in convex quantile regression: \(\mathcal{L}_1\)-norm or \(\mathcal{L}_0\)-norm regularization?
- Bicriteria streaming algorithms to balance gain and cost with cardinality constraint
- Sparse regression at scale: branch-and-bound rooted in first-order optimization
This page was built for publication: Sparse high-dimensional regression: exact scalable algorithms and phase transitions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2176621)
