Safe Screening Rules for ${\ell }_0$-Regression

Abstract

We give safe screening rules to eliminate variables from regression with ${\ell }_0$ regularization or cardinality constraint. These rules are based on guarantees that a feature may or may not be selected in an optimal solution. The screening rules can be computed from a convex relaxation solution in linear time, without solving the ${\ell }_0$ optimization problem. Thus, they can be used in a preprocessing step to safely remove variables from consideration apriori. Numerical experiments on real and synthetic data indicate that, on average, 76\% of the variables can be fixed to their optimal values, hence, reducing the computational burden for optimization substantially. Therefore, the proposed fast and effective screening rules extend the scope of algorithms for ${\ell }_0$-regression to larger data sets.

References in corpus (20)

• Discussion of "Least angle regression" by Efron et al
• Rejoinder to "Least angle regression" by Efron et al
• Discussion of "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
• Robustness and Regularization of Support Vector Machines
• Extended Comparisons of Best Subset Selection, Forward Stepwise Selection, and the Lasso
• Lasso Screening Rules via Dual Polytope Projection
• Safe Feature Elimination for the LASSO and Sparse Supervised Learning Problems
• Screening Tests for Lasso Problems
• Sparse Regression: Scalable algorithms and empirical performance
• Mind the duality gap: safer rules for the Lasso
• Subset Selection for Multiple Linear Regression via Optimization
• Regularization vs. Relaxation: A conic optimization perspective of statistical variable selection
• Rank-one Convexification for Sparse Regression