# Overfitting Can Be Harmless for Basis Pursuit, But Only to a Degree

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Feb 2020.

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

- [Uniform Convergence of Interpolators: Gaussian Width, Norm Bounds, and Benign Overfitting](https://mlsanity.com/paper/2106.09276/) (2021)
- [Optimistic Rates: A Unifying Theory for Interpolation Learning and Regularization in Linear Regression](https://mlsanity.com/paper/2112.04470/) (2021)
- [A Non-Asymptotic Moreau Envelope Theory for High-Dimensional Generalized Linear Models](https://mlsanity.com/paper/2210.12082/) (2022)
- [Minimum ℓ1-norm interpolators: Precise asymptotics and multiple descent](https://mlsanity.com/paper/2110.09502/) (2021)
- [Provable Tempered Overfitting of Minimal Nets and Typical Nets](https://mlsanity.com/paper/2410.19092/) (2024)

## Abstract (arXiv)

Recently, there have been significant interests in studying the so-called "double-descent" of the generalization error of linear regression models under the overparameterized and overfitting regime, with the hope that such analysis may provide the first step towards understanding why overparameterized deep neural networks (DNN) still generalize well. However, to date most of these studies focused on the min ℓ2-norm solution that overfits the data. In contrast, in this paper we study the overfitting solution that minimizes the ℓ1-norm, which is known as Basis Pursuit (BP) in the compressed sensing literature. Under a sparse true linear regression model with p i.i.d. Gaussian features, we show that for a large range of p up to a limit that grows exponentially with the number of samples n, with high probability the model error of BP is upper bounded by a value that decreases with p. To the best of our knowledge, this is the first analytical result in the literature establishing the double-descent of overfitting BP for finite n and p. Further, our results reveal significant differences between the double-descent of BP and min ℓ2-norm solutions. Specifically, the double-descent upper-bound of BP is independent of the signal strength, and for high SNR and sparse models the descent-floor of BP can be much lower and wider than that of min ℓ2-norm solutions.