# Subset Selection with Shrinkage: Sparse Linear Modeling when the SNR is low

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Aug 2017.

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

- [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)
- [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)
- [Theoretical Analysis of Leave-one-out Cross Validation for Non-differentiable Penalties under High-dimensional Settings](https://mlsanity.com/paper/2402.08543/) (2024)
- [Predicting Census Survey Response Rates With Parsimonious Additive Models and Structured Interactions](https://mlsanity.com/paper/2108.11328/) (2021)
- [Blessing of Nonconvexity in Deep Linear Models: Depth Flattens the Optimization Landscape Around the True Solution](https://mlsanity.com/paper/2207.07612/) (2022)
- [Outlier detection in regression: conic quadratic formulations](https://mlsanity.com/paper/2307.05975/) (2023)
- [Principal Component Hierarchy for Sparse Quadratic Programs](https://mlsanity.com/paper/2105.12022/) (2021)
- [Group selection and shrinkage: Structured sparsity for semiparametric additive models](https://mlsanity.com/paper/2105.12081/) (2021)
- [Best Subset Selection with Efficient Primal-Dual Algorithm](https://mlsanity.com/paper/2207.02058/) (2022)
- [Efficient Cross-Validation for Sparse Linear Regression](https://mlsanity.com/paper/2306.14851/) (2023)
- [End-to-end Feature Selection Approach for Learning Skinny Trees](https://mlsanity.com/paper/2310.18542/) (2023)
- [Dynamic Incremental Optimization for Best Subset Selection](https://mlsanity.com/paper/2402.02322/) (2024)
- [MOSS: Multi-Objective Optimization for Stable Rule Sets](https://mlsanity.com/paper/2506.08030/) (2025)
- [Coordinate Optimality Reformulation for Mixed-Integer Convex Programs with Indicators](https://mlsanity.com/paper/2608.01385/) (2026)

## Abstract (arXiv)

We study a seemingly unexpected and relatively less understood overfitting aspect of a fundamental tool in sparse linear modeling - best subset selection, which minimizes the residual sum of squares subject to a constraint on the number of nonzero coefficients. While the best subset selection procedure is often perceived as the "gold standard" in sparse learning when the signal to noise ratio (SNR) is high, its predictive performance deteriorates when the SNR is low. In particular, it is outperformed by continuous shrinkage methods, such as ridge regression and the Lasso. We investigate the behavior of best subset selection in the high-noise regimes and propose an alternative approach based on a regularized version of the least-squares criterion. Our proposed estimators (a) mitigate, to a large extent, the poor predictive performance of best subset selection in the high-noise regimes; and (b) perform favorably, while generally delivering substantially sparser models, relative to the best predictive models available via ridge regression and the Lasso. We conduct an extensive theoretical analysis of the predictive properties of the proposed approach and provide justification for its superior predictive performance relative to best subset selection when the noise-level is high. Our estimators can be expressed as solutions to mixed integer second order conic optimization problems and, hence, are amenable to modern computational tools from mathematical optimization.