# Sparse Regression at Scale: Branch-and-Bound rooted in First-Order Optimization

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

## Key facts

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

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

- [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)
- [OSSCAR: One-Shot Structured Pruning in Vision and Language Models with Combinatorial Optimization](https://mlsanity.com/paper/2403.12983/) (2024)
- [Noise-aware Physics-informed Machine Learning for Robust PDE Discovery](https://mlsanity.com/paper/2206.12901/) (2022)
- [Grouped Variable Selection with Discrete Optimization: Computational and Statistical Perspectives](https://mlsanity.com/paper/2104.07084/) (2021)
- [L0Learn: A Scalable Package for Sparse Learning using L0 Regularization](https://mlsanity.com/paper/2202.04820/) (2022)
- [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)
- [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)
- [Adaptive Uncertainty-Guided Model Selection for Data-Driven PDE Discovery](https://mlsanity.com/paper/2308.10283/) (2023)
- [Sparse Gaussian Graphical Models with Discrete Optimization: Computational and Statistical Perspectives](https://mlsanity.com/paper/2307.09366/) (2023)
- [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)
- [Predicting Census Survey Response Rates With Parsimonious Additive Models and Structured Interactions](https://mlsanity.com/paper/2108.11328/) (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)
- [Interpretable Time Series Autoregression for Periodicity Quantification](https://mlsanity.com/paper/2506.22895/) (2025)
- [Principal Component Hierarchy for Sparse Quadratic Programs](https://mlsanity.com/paper/2105.12022/) (2021)
- [Feature subset selection for kernel SVM classification via mixed-integer optimization](https://mlsanity.com/paper/2205.14325/) (2022)
- [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)
- [Fair and Accurate Regression: Strong Formulations and Algorithms](https://mlsanity.com/paper/2412.17116/) (2024)
- [Scalable First-order Method for Certifying Optimal k-Sparse GLMs](https://mlsanity.com/paper/2502.09502/) (2025)
- [Computation of Least Trimmed Squares: A Branch-and-Bound framework with Hyperplane Arrangement Enhancements](https://mlsanity.com/paper/2604.11584/) (2026)
- [Best Subset Selection with Efficient Primal-Dual Algorithm](https://mlsanity.com/paper/2207.02058/) (2022)
- [Safe Peeling for L0-Regularized Least-Squares with supplementary material](https://mlsanity.com/paper/2302.14471/) (2023)
- [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)

## Abstract (arXiv)

We consider the least squares regression problem, penalized with a combination of the ℓ0 and squared ℓ2 penalty functions (a.k.a. ℓ0 ℓ2 regularization). Recent work shows that the resulting estimators are of key importance in many high-dimensional statistical settings. However, exact computation of these estimators remains a major challenge. Indeed, modern exact methods, based on mixed integer programming (MIP), face difficulties when the number of features p ~ 104. In this work, we present a new exact MIP framework for ℓ0ℓ2-regularized regression that can scale to p ~ 107, achieving speedups of at least 5000x, compared to state-of-the-art exact methods. Unlike recent work, which relies on modern commercial MIP solvers, we design a specialized nonlinear branch-and-bound (BnB) framework, by critically exploiting the problem structure. A key distinguishing component in our framework lies in efficiently solving the node relaxations using a specialized first-order method, based on coordinate descent (CD). Our CD-based method effectively leverages information across the BnB nodes, through using warm starts, active sets, and gradient screening. In addition, we design a novel method for obtaining dual bounds from primal CD solutions, which certifiably works in high dimensions. Experiments on synthetic and real high-dimensional datasets demonstrate that our framework is not only significantly faster than the state of the art, but can also deliver certifiably optimal solutions to statistically challenging instances that cannot be handled with existing methods. We open source the implementation through our toolkit L0BnB.