# Sparse High-Dimensional Regression: Exact Scalable Algorithms and Phase Transitions

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

## Key facts

- Cited by 43 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Sep 2017.

## Built on by (most cited first, 30 of 43)

- [Fast as CHITA: Neural Network Pruning with Combinatorial Optimization](https://mlsanity.com/paper/2302.14623/) (2023)
- [Learning Sparse Nonlinear Dynamics via Mixed-Integer Optimization](https://mlsanity.com/paper/2206.00176/) (2022)
- [Strong Optimal Classification Trees](https://mlsanity.com/paper/2103.15965/) (2021)
- [abess: A Fast Best Subset Selection Library in Python and R](https://mlsanity.com/paper/2110.09697/) (2021)
- [Grouped Variable Selection with Discrete Optimization: Computational and Statistical Perspectives](https://mlsanity.com/paper/2104.07084/) (2021)
- [HARFE: Hard-Ridge Random Feature Expansion](https://mlsanity.com/paper/2202.02877/) (2022)
- [L0Learn: A Scalable Package for Sparse Learning using L0 Regularization](https://mlsanity.com/paper/2202.04820/) (2022)
- [Interpretable Clustering via Multi-Polytope Machines](https://mlsanity.com/paper/2112.05653/) (2021)
- [A new perspective on low-rank optimization](https://mlsanity.com/paper/2105.05947/) (2021)
- [Learning Optimal Prescriptive Trees from Observational Data](https://mlsanity.com/paper/2108.13628/) (2021)
- [Support Recovery with Stochastic Gates: Theory and Application for Linear Models](https://mlsanity.com/paper/2110.15960/) (2021)
- [Slowly Varying Regression under Sparsity](https://mlsanity.com/paper/2102.10773/) (2021)
- [ForestPrune: Compact Depth-Controlled Tree Ensembles](https://mlsanity.com/paper/2206.00128/) (2022)
- [Safe Screening for Logistic Regression with ℓ0-ℓ2 Regularization](https://mlsanity.com/paper/2202.00467/) (2022)
- [SRMD: Sparse Random Mode Decomposition](https://mlsanity.com/paper/2204.06108/) (2022)
- [Sparse Gaussian Graphical Models with Discrete Optimization: Computational and Statistical Perspectives](https://mlsanity.com/paper/2307.09366/) (2023)
- [Statistical Mechanics of Dynamical System Identification](https://mlsanity.com/paper/2403.01723/) (2024)
- [A New Branch-and-Bound Pruning Framework for ℓ0-Regularized Problems](https://mlsanity.com/paper/2406.03504/) (2024)
- [A Splicing Approach to Best Subset of Groups Selection](https://mlsanity.com/paper/2104.12576/) (2021)
- [Fast Projection onto the Capped Simplex with Applications to Sparse Regression in Bioinformatics](https://mlsanity.com/paper/2110.08471/) (2021)
- [Outlier detection in regression: conic quadratic formulations](https://mlsanity.com/paper/2307.05975/) (2023)
- [Constrained Optimization of Rank-One Functions with Indicator Variables](https://mlsanity.com/paper/2303.18158/) (2023)
- [LCEN: A Nonlinear, Interpretable Feature Selection and Machine Learning Algorithm](https://mlsanity.com/paper/2402.17120/) (2024)
- [Principal Component Hierarchy for Sparse Quadratic Programs](https://mlsanity.com/paper/2105.12022/) (2021)
- [Drugs Resistance Analysis from Scarce Health Records via Multi-task Graph Representation](https://mlsanity.com/paper/2302.11231/) (2023)
- [On the Computational Complexity of Private High-dimensional Model Selection](https://mlsanity.com/paper/2310.07852/) (2023)
- [On the Efficiency of ERM in Feature Learning](https://mlsanity.com/paper/2411.12029/) (2024)
- [The Nonconvex Geometry of Linear Inverse Problems](https://mlsanity.com/paper/2101.02776/) (2021)
- [Stochastic Cutting Planes for Data-Driven Optimization](https://mlsanity.com/paper/2103.02506/) (2021)
- [Detecting Racial Bias in Jury Selection](https://mlsanity.com/paper/2103.11852/) (2021)

## Abstract (arXiv)

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 n 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.