# Sparse Regression: Scalable algorithms and empirical performance

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

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Feb 2019.

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

- [Finding Neurons in a Haystack: Case Studies with Sparse Probing](https://mlsanity.com/paper/2305.01610/) (2023)
- [Learning Sparse Nonlinear Dynamics via Mixed-Integer Optimization](https://mlsanity.com/paper/2206.00176/) (2022)
- [Benchmarking sparse system identification with low-dimensional chaos](https://mlsanity.com/paper/2302.10787/) (2023)
- [Sparse Plus Low Rank Matrix Decomposition: A Discrete Optimization Approach](https://mlsanity.com/paper/2109.12701/) (2021)
- [A new perspective on low-rank optimization](https://mlsanity.com/paper/2105.05947/) (2021)
- [Slowly Varying Regression under Sparsity](https://mlsanity.com/paper/2102.10773/) (2021)
- [OKRidge: Scalable Optimal k-Sparse Ridge Regression](https://mlsanity.com/paper/2304.06686/) (2023)
- [A Priori Denoising Strategies for Sparse Identification of Nonlinear Dynamical Systems: A Comparative Study](https://mlsanity.com/paper/2201.12683/) (2022)
- [Sparse PCA With Multiple Components](https://mlsanity.com/paper/2209.14790/) (2022)
- [Fast Projection onto the Capped Simplex with Applications to Sparse Regression in Bioinformatics](https://mlsanity.com/paper/2110.08471/) (2021)
- [Conditional Mean and Variance Estimation via textitk-NN Algorithm with Automated Variance Selection](https://mlsanity.com/paper/2402.01635/) (2024)
- [Feature subset selection for kernel SVM classification via mixed-integer optimization](https://mlsanity.com/paper/2205.14325/) (2022)
- [On the Efficiency of ERM in Feature Learning](https://mlsanity.com/paper/2411.12029/) (2024)
- [Federated Learning With L0 Constraint Via Probabilistic Gates For Sparsity](https://mlsanity.com/paper/2512.23071/) (2025)
- [Detecting Racial Bias in Jury Selection](https://mlsanity.com/paper/2103.11852/) (2021)
- [Holistic Deep Learning](https://mlsanity.com/paper/2110.15829/) (2021)
- [Efficient and robust high-dimensional sparse logistic regression via nonlinear primal-dual hybrid gradient algorithms](https://mlsanity.com/paper/2111.15426/) (2021)
- [Efficient Cross-Validation for Sparse Linear Regression](https://mlsanity.com/paper/2306.14851/) (2023)
- [Path Signatures for Seizure Forecasting](https://mlsanity.com/paper/2308.09312/) (2023)
- [A Consistent and Scalable Algorithm for Best Subset Selection in Single Index Models](https://mlsanity.com/paper/2309.06230/) (2023)
- [Variable Selection Methods for Multivariate, Functional, and Complex Biomedical Data in the AI Age](https://mlsanity.com/paper/2501.06868/) (2025)
- [Stability Regularized Cross-Validation](https://mlsanity.com/paper/2505.06927/) (2025)
- [Enhancing generalizability of model discovery across parameter space with multi-experiment equation learning (ME-EQL)](https://mlsanity.com/paper/2506.08916/) (2025)
- [A fast algorithm for solving the lasso problem exactly without homotopy using differential inclusions](https://mlsanity.com/paper/2507.05562/) (2025)
- [Choosing the Right Regularizer for Applied ML: Simulation Benchmarks of Popular Scikit-learn Regularization Frameworks](https://mlsanity.com/paper/2604.03541/) (2026)
- [From Sequential Nodes to GPU Batches: Parallel Branch and Bound for Optimal k-Sparse GLMs](https://mlsanity.com/paper/2605.22188/) (2026)
- [Entropy-Regularized Probabilistic Gates for Sparse Model Discovery in Scarce-Data Federated Learning](https://mlsanity.com/paper/2607.00275/) (2026)

## Abstract (arXiv)

In this paper, we review state-of-the-art methods for feature selection in statistics with an application-oriented eye. Indeed, sparsity is a valuable property and the profusion of research on the topic might have provided little guidance to practitioners. We demonstrate empirically how noise and correlation impact both the accuracy - the number of correct features selected - and the false detection - the number of incorrect features selected - for five methods: the cardinality-constrained formulation, its Boolean relaxation, ℓ1 regularization and two methods with non-convex penalties. A cogent feature selection method is expected to exhibit a two-fold convergence, namely the accuracy and false detection rate should converge to 1 and 0 respectively, as the sample size increases. As a result, proper method should recover all and nothing but true features. Empirically, the integer optimization formulation and its Boolean relaxation are the closest to exhibit this two properties consistently in various regimes of noise and correlation. In addition, apart from the discrete optimization approach which requires a substantial, yet often affordable, computational time, all methods terminate in times comparable with the verb|glmnet| package for Lasso. We released code for methods that were not publicly implemented. Jointly considered, accuracy, false detection and computational time provide a comprehensive assessment of each feature selection method and shed light on alternatives to the Lasso-regularization which are not as popular in practice yet.