# Tight bounds for minimum l1-norm interpolation of noisy data

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 36 references that are in the map.
- First posted on arXiv 10 Nov 2021.

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

- [Reconciling modern machine learning practice and the bias-variance trade-off](https://mlsanity.com/paper/1812.11118/) (2018)
- [Benign Overfitting in Linear Regression](https://mlsanity.com/paper/1906.11300/) (2019)
- [The generalization error of random features regression: Precise asymptotics and double descent curve](https://mlsanity.com/paper/1908.05355/) (2019)
- [Linearized two-layers neural networks in high dimension](https://mlsanity.com/paper/1904.12191/) (2019)
- [Benign overfitting in ridge regression](https://mlsanity.com/paper/2009.14286/) (2020)
- [High-Dimensional Asymptotics of Prediction: Ridge Regression and Classification](https://mlsanity.com/paper/1507.03003/) (2015)
- [Harmless interpolation of noisy data in regression](https://mlsanity.com/paper/1903.09139/) (2019)
- [Classification vs regression in overparameterized regimes: Does the loss function matter?](https://mlsanity.com/paper/2005.08054/) (2020)
- [Uniform Convergence of Interpolators: Gaussian Width, Norm Bounds, and Benign Overfitting](https://mlsanity.com/paper/2106.09276/) (2021)
- [Learning without Concentration](https://mlsanity.com/paper/1401.0304/) (2014)
- [On Uniform Convergence and Low-Norm Interpolation Learning](https://mlsanity.com/paper/2006.05942/) (2020)
- [Foolish Crowds Support Benign Overfitting](https://mlsanity.com/paper/2110.02914/) (2021)
- [On the robustness of minimum norm interpolators and regularized empirical risk minimizers](https://mlsanity.com/paper/2012.00807/) (2020)
- [A Quotient Property for Matrices with Heavy-Tailed Entries and its Application to Noise-Blind Compressed Sensing](https://mlsanity.com/paper/1806.04261/) (2018)

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

- [Benign Overfitting without Linearity: Neural Network Classifiers Trained by Gradient Descent for Noisy Linear Data](https://mlsanity.com/paper/2202.05928/) (2022)
- [Benign Overfitting in Linear Classifiers and Leaky ReLU Networks from KKT Conditions for Margin Maximization](https://mlsanity.com/paper/2303.01462/) (2023)
- [Fast Rates for Noisy Interpolation Require Rethinking the Effects of Inductive Bias](https://mlsanity.com/paper/2203.03597/) (2022)
- [A Non-Asymptotic Moreau Envelope Theory for High-Dimensional Generalized Linear Models](https://mlsanity.com/paper/2210.12082/) (2022)
- [Noisy Interpolation Learning with Shallow Univariate ReLU Networks](https://mlsanity.com/paper/2307.15396/) (2023)
- [Strong inductive biases provably prevent harmless interpolation](https://mlsanity.com/paper/2301.07605/) (2023)
- [Benign Overfitting in Deep Neural Networks under Lazy Training](https://mlsanity.com/paper/2305.19377/) (2023)
- [Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks](https://mlsanity.com/paper/2404.18769/) (2024)
- [Training shallow ReLU networks on noisy data using hinge loss: when do we overfit and is it benign?](https://mlsanity.com/paper/2306.09955/) (2023)
- [Overfitting Behaviour of Gaussian Kernel Ridgeless Regression: Varying Bandwidth or Dimensionality](https://mlsanity.com/paper/2409.03891/) (2024)
- [An Agnostic View on the Cost of Overfitting in (Kernel) Ridge Regression](https://mlsanity.com/paper/2306.13185/) (2023)
- [Provable Tempered Overfitting of Minimal Nets and Typical Nets](https://mlsanity.com/paper/2410.19092/) (2024)
- [Implicit Regularization Leads to Benign Overfitting for Sparse Linear Regression](https://mlsanity.com/paper/2302.00257/) (2023)
- [Surprises in adversarially-trained linear regression](https://mlsanity.com/paper/2205.12695/) (2022)
- [Tight bounds for maximum ℓ1-margin classifiers](https://mlsanity.com/paper/2212.03783/) (2022)
- [Bayesian Analysis for Over-parameterized Linear Model via Effective Spectra](https://mlsanity.com/paper/2305.15754/) (2023)

## Abstract (arXiv)

We provide matching upper and lower bounds of order σ2/log(d/n) for the prediction error of the minimum ℓ1-norm interpolator, a.k.a. basis pursuit. Our result is tight up to negligible terms when d gg n, and is the first to imply asymptotic consistency of noisy minimum-norm interpolation for isotropic features and sparse ground truths. Our work complements the literature on "benign overfitting" for minimum ℓ2-norm interpolation, where asymptotic consistency can be achieved only when the features are effectively low-dimensional.