Rank-one Convexification for Sparse Regression

Abstract

Sparse regression models are increasingly prevalent due to their ease of interpretability and superior out-of-sample performance. However, the exact model of sparse regression with an ${\ell }_0$ constraint restricting the support of the estimators is a challenging (\NP-hard) non-convex optimization problem. In this paper, we derive new strong convex relaxations for sparse regression. These relaxations are based on the ideal (convex-hull) formulations for rank-one quadratic terms with indicator variables. The new relaxations can be formulated as semidefinite optimization problems in an extended space and are stronger and more general than the state-of-the-art formulations, including the perspective reformulation and formulations with the reverse Huber penalty and the minimax concave penalty functions. Furthermore, the proposed rank-one strengthening can be interpreted as a \textit{non-separable, non-convex, unbiased} sparsity-inducing regularizer, which dynamically adjusts its penalty according to the shape of the error function without inducing bias for the sparse solutions. In our computational experiments with benchmark datasets, the proposed conic formulations are solved within seconds and result in near-optimal solutions (with 0.4\% optimality gap) for non-convex ${\ell }_0$-problems. Moreover, the resulting estimators also outperform alternative convex approaches from a statistical perspective, achieving high prediction accuracy and good interpretability.

References in corpus (19)

• Discussion of "Least angle regression" by Efron et al
• Rejoinder to "Least angle regression" by Efron et al
• Least Angle Regression
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Nearly unbiased variable selection under minimax concave penalty
• The ALAMO approach to machine learning
• Extended Comparisons of Best Subset Selection, Forward Stepwise Selection, and the Lasso
• Lower bounds on the performance of polynomial-time algorithms for sparse linear regression
• A Practical Scheme and Fast Algorithm to Tune the Lasso With Optimality Guarantees
• The DFS Fused Lasso: Linear-Time Denoising over General Graphs
• Regularization vs. Relaxation: A conic optimization perspective of statistical variable selection
• Sparse and Smooth Signal Estimation: Convexification of L0 Formulations
• 2x2 convexifications for convex quadratic optimization with indicator variables

Cited by in corpus (11)

• Optimization Problems for Machine Learning: A Survey
• A Scalable Algorithm For Sparse Portfolio Selection
• Sparse and Smooth Signal Estimation: Convexification of L0 Formulations
• Mixed-Projection Conic Optimization: A New Paradigm for Modeling Rank Constraints
• A unified approach to mixed-integer optimization problems with logical constraints
• A new perspective on low-rank optimization
• Consistent Second-Order Conic Integer Programming for Learning Bayesian Networks
• 2x2 convexifications for convex quadratic optimization with indicator variables
• Scalable Algorithms for the Sparse Ridge Regression
• Compact extended formulations for low-rank functions with indicator variables
• Safe Screening Rules for ${\ell }_0$-Regression