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.
This paper proposes a novel binary convex reformulation of the sparse regression problem. A new cutting plane method is devised to exactly solve the problem. Evidence is provided that the cutting plane algorithm fast scales to provable optimality for sample sizes \(n\) and number of regressors \(p\) in the 100,000s. A new phase transition is found in the ability to recover the true coefficients of the sparse regression problem and also in the ability to solve it. An extension of the sparse linear regression to the case of nonlinear regression by augmenting the input data \(X\) with auxiliary nonlinear transformations is also discussed.
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
- 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?
- 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?)
- 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
(69)- Optimization problems for machine learning: a survey
- Sparse classification: a scalable discrete optimization perspective
- Robust subset 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
- Convex optimization under combinatorial sparsity constraints
- Sparse regression over clusters: SparClur
- Ideal formulations for constrained convex optimization problems with indicator variables
- Sparse high-dimensional linear regression. Estimating squared error and a phase transition
- The backbone method for ultra-high dimensional sparse machine learning
- 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
- Sparse high-dimensional regression: exact scalable algorithms and phase transitions
- Scalable holistic linear regression
- Certifiably optimal sparse inverse covariance estimation
- Bicriteria algorithms to balance coverage and cost in team formation under online model
- 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
- An efficient optimization approach for best subset selection in linear regression, with application to model selection and fitting in autoregressive time-series
- Weaker regularity conditions and sparse recovery in high-dimensional regression
- Combinatorial optimization. Abstracts from the workshop held November 7--13, 2021 (hybrid meeting)
- Sparse Convex Regression
- A Mixed-Integer Fractional Optimization Approach to Best Subset Selection
- Sparse and smooth signal estimation: convexification of \(\ell_0\)-formulations
- scientific article; zbMATH DE number 7625166 (Why is no real title available?)
- Stochastic Cutting Planes for Data-Driven Optimization
- An Alternating Method for Cardinality-Constrained Optimization: A Computational Study for the Best Subset Selection and Sparse Portfolio Problems
- MIP-BOOST: Efficient and Effective L0 Feature Selection for Linear Regression
- A First-Order Optimization Algorithm for Statistical Learning with Hierarchical Sparsity Structure
- A Scalable Algorithm for Sparse Portfolio Selection
- Scalable algorithms for the sparse ridge regression
- A unified approach to mixed-integer optimization problems with logical constraints
- Learning sparse classifiers: continuous and mixed integer optimization perspectives
- The trimmed Lasso: sparse recovery guarantees and practical optimization by the generalized soft-min penalty
- Grouped variable selection with discrete optimization: computational and statistical perspectives
- HARFE: hard-ridge random feature expansion
- A new perspective on low-rank optimization
- Simultaneous feature selection and outlier detection with optimality guarantees
- Learning sparse nonlinear dynamics via mixed-integer optimization
- Sparsifying the least-squares approach to PCA: comparison of lasso and cardinality constraint
- Sparse quantile regression
- Subset Selection and the Cone of Factor-Width-k Matrices
- SRMD: sparse random mode decomposition
- Cardinality minimization, constraints, and regularization: a survey
- Exterior-point optimization for sparse and low-rank optimization
- Constrained optimization of rank-one functions with indicator variables
- The sparse(st) optimization problem: reformulations, optimality, stationarity, and numerical results
- Supervised learning of outcome-relevant items from a questionnaire via mixed integer optimization
- Sparse vertex discriminant analysis: variable selection for biomedical classification applications
- Multi-model subset selection
- Feature and functional form selection in additive models via mixed-integer optimization
- Understanding best subset selection: a tale of two c(omplex)ities
- Rank-one convexification for sparse regression
- High-dimensional variable selection with heterogeneous signals: a precise asymptotic perspective
- Provably Efficient Posterior Sampling for Sparse Linear Regression via Measure Decomposition
- Sparse PCA: a new scalable estimator based on integer programming
- Multi-task learning for sparsity pattern heterogeneity: statistical and computational perspectives
- Sparse convex quantile regression: a generalized Benders decomposition approach
- A parametric approach for solving convex quadratic optimization with indicators over trees
- Certifiably optimal direction estimation in sparse single-index model
- Adaptive change point detection and sparsity recovery
- Sparse hierarchical regression with polynomials
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)
