# Best Subset Selection with Efficient Primal-Dual Algorithm

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 20 of its 42 references that are in the map.
- First posted on arXiv 5 Jul 2022.

## Builds on (most cited first, 20 of 20)

- [Best Subset Selection via a Modern Optimization Lens](https://mlsanity.com/paper/1507.03133/) (2015)
- [On Iterative Hard Thresholding Methods for High-dimensional M-Estimation](https://mlsanity.com/paper/1410.5137/) (2014)
- [Fast Best Subset Selection: Coordinate Descent and Local Combinatorial Optimization Algorithms](https://mlsanity.com/paper/1803.01454/) (2018)
- [Sparse Regression at Scale: Branch-and-Bound rooted in First-Order Optimization](https://mlsanity.com/paper/2004.06152/) (2020)
- [Sparse High-Dimensional Regression: Exact Scalable Algorithms and Phase Transitions](https://mlsanity.com/paper/1709.10029/) (2017)
- [Gap Safe screening rules for sparsity enforcing penalties](https://mlsanity.com/paper/1611.05780/) (2016)
- [Mind the duality gap: safer rules for the Lasso](https://mlsanity.com/paper/1505.03410/) (2015)
- [Celer: a Fast Solver for the Lasso with Dual Extrapolation](https://mlsanity.com/paper/1802.07481/) (2018)
- [Learning Sparse Classifiers: Continuous and Mixed Integer Optimization Perspectives](https://mlsanity.com/paper/2001.06471/) (2020)
- [Support recovery without incoherence: A case for nonconvex regularization](https://mlsanity.com/paper/1412.5632/) (2014)
- [Subset Selection with Shrinkage: Sparse Linear Modeling when the SNR is low](https://mlsanity.com/paper/1708.03288/) (2017)
- [GAP Safe screening rules for sparse multi-task and multi-class models](https://mlsanity.com/paper/1506.03736/) (2015)
- [A Tight Bound of Hard Thresholding](https://mlsanity.com/paper/1605.01656/) (2016)
- [Extended Comparisons of Best Subset Selection, Forward Stepwise Selection, and the Lasso](https://mlsanity.com/paper/1707.08692/) (2017)
- [Gradient Hard Thresholding Pursuit for Sparsity-Constrained Optimization](https://mlsanity.com/paper/1311.5750/) (2013)
- [Regularization vs. Relaxation: A conic optimization perspective of statistical variable selection](https://mlsanity.com/paper/1510.06083/) (2015)
- [High-Dimensional Regression with Binary Coefficients. Estimating Squared Error and a Phase Transition](https://mlsanity.com/paper/1701.04455/) (2017)
- [Structured Sparse Regression via Greedy Hard-Thresholding](https://mlsanity.com/paper/1602.06042/) (2016)
- [The Discrete Dantzig Selector: Estimating Sparse Linear Models via Mixed Integer Linear Optimization](https://mlsanity.com/paper/1508.01922/) (2015)
- [Dual Iterative Hard Thresholding: From Non-convex Sparse Minimization to Non-smooth Concave Maximization](https://mlsanity.com/paper/1703.00119/) (2017)

## Abstract (arXiv)

Best subset selection is considered the `gold standard' for many sparse learning problems. A variety of optimization techniques have been proposed to attack this non-convex and NP-hard problem. In this paper, we investigate the dual forms of a family of ℓ0-regularized problems. An efficient primal-dual method has been developed based on the primal and dual problem structures. By leveraging the dual range estimation along with the incremental strategy, our algorithm potentially reduces redundant computation and improves the solutions of best subset selection. Theoretical analysis and experiments on synthetic and real-world datasets validate the efficiency and statistical properties of the proposed solutions.