# Safe Screening Rules for ℓ0-Regression

arXiv: https://arxiv.org/abs/2004.08773 · HTML: https://mlsanity.com/paper/2004.08773/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Apr 2020.

## Built on by (most cited first, 7 of 7)

- [OKRidge: Scalable Optimal k-Sparse Ridge Regression](https://mlsanity.com/paper/2304.06686/) (2023)
- [Principal Component Hierarchy for Sparse Quadratic Programs](https://mlsanity.com/paper/2105.12022/) (2021)
- [State-driven Implicit Modeling for Sparsity and Robustness in Neural Networks](https://mlsanity.com/paper/2209.09389/) (2022)
- [Is the Rush to Machine Learning Jeopardizing Safety? Results of a Survey](https://mlsanity.com/paper/2111.14324/) (2021)
- [Path Signatures for Seizure Forecasting](https://mlsanity.com/paper/2308.09312/) (2023)
- [BackboneLearn: A Library for Scaling Mixed-Integer Optimization-Based Machine Learning](https://mlsanity.com/paper/2311.13695/) (2023)
- [Robust support vector machines via conic optimization](https://mlsanity.com/paper/2402.01797/) (2024)

## Abstract (arXiv)

We give safe screening rules to eliminate variables from regression with ℓ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 ℓ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 ℓ0-regression to larger data sets.