mlsanityData to 7 Oct 2026

Tight bounds for minimum l1-norm interpolation of noisy data

arXiv 2111.05987 ↗First posted 10 Nov 2021math.ST cs.IT cs.LGcited by 16

Not on the map. Why?

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.

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

Builds on

14 of 36 references.

References · 14

  1. 2018Reconciling modern machine learning practice and the bias-variance trade-offcited by 919
  2. 2019Benign Overfitting in Linear Regressioncited by 544
  3. 2019The generalization error of random features regression: Precise asymptotics and double descent curvecited by 410
  4. 2019Linearized two-layers neural networks in high dimensioncited by 155
  5. 2020Benign overfitting in ridge regressioncited by 152
  6. 2015High-Dimensional Asymptotics of Prediction: Ridge Regression and Classificationcited by 146
  7. 2019Harmless interpolation of noisy data in regressioncited by 121
  8. 2020Classification vs regression in overparameterized regimes: Does the loss function matter?cited by 97
  9. 2021Uniform Convergence of Interpolators: Gaussian Width, Norm Bounds, and Benign Overfittingcited by 54
  10. 2014Learning without Concentrationcited by 50
  11. 2020On Uniform Convergence and Low-Norm Interpolation Learningcited by 24
  12. 2021Foolish Crowds Support Benign Overfittingcited by 24
2 more
  1. 2020On the robustness of minimum norm interpolators and regularized empirical risk minimizerscited by 18
  2. 2018A Quotient Property for Matrices with Heavy-Tailed Entries and its Application to Noise-Blind Compressed Sensingcited by 3

Built on by

Cited by year

Citing papers per year: 2022: 5; 2023: 8; 2024: 3.

16 papers.

Sort:

  1. 2022Benign Overfitting without Linearity: Neural Network Classifiers Trained by Gradient Descent for Noisy Linear Datacited by 74
  2. 2023Benign Overfitting in Linear Classifiers and Leaky ReLU Networks from KKT Conditions for Margin Maximizationcited by 29
  3. 2022Fast Rates for Noisy Interpolation Require Rethinking the Effects of Inductive Biascited by 21
  4. 2022A Non-Asymptotic Moreau Envelope Theory for High-Dimensional Generalized Linear Modelscited by 11
  5. 2023Noisy Interpolation Learning with Shallow Univariate ReLU Networkscited by 11
  6. 2023Benign Overfitting in Deep Neural Networks under Lazy Trainingcited by 10
  7. 2023Strong inductive biases provably prevent harmless interpolationcited by 9
  8. 2024Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networkscited by 8
  9. 2023Training shallow ReLU networks on noisy data using hinge loss: when do we overfit and is it benign?cited by 7
  10. 2024Overfitting Behaviour of Gaussian Kernel Ridgeless Regression: Varying Bandwidth or Dimensionalitycited by 7
  11. 2023An Agnostic View on the Cost of Overfitting in (Kernel) Ridge Regressioncited by 5
  12. 2024Provable Tempered Overfitting of Minimal Nets and Typical Netscited by 5
4 more
  1. 2023Implicit Regularization Leads to Benign Overfitting for Sparse Linear Regressioncited by 4
  2. 2022Surprises in adversarially-trained linear regressioncited by 2
  3. 2022Tight bounds for maximum ℓ1-margin classifierscited by 0
  4. 2023Bayesian Analysis for Over-parameterized Linear Model via Effective Spectracited by 0