Tight bounds for minimum l1-norm interpolation of noisy data

Abstract

We provide matching upper and lower bounds of order ${\sigma }^2/\log (d/n)$ for the prediction error of the minimum ${\ell }_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 ${\ell }_2$-norm interpolation, where asymptotic consistency can be achieved only when the features are effectively low-dimensional.

arXiv comment33 pages, 1 figure; accepted to AISTATS 2022

References in corpus (10)

• Reconciling modern machine learning practice and the bias-variance trade-off
• Benign Overfitting in Linear Regression
• The generalization error of random features regression: Precise asymptotics and double descent curve
• Benign overfitting in ridge regression
• Learning without Concentration
• A Quotient Property for Matrices with Heavy-Tailed Entries and its Application to Noise-Blind Compressed Sensing
• Lower Bound for RIP Constants and Concentration of Sum of Top Order Statistics
• Uniform Convergence of Interpolators: Gaussian Width, Norm Bounds, and Benign Overfitting
• Minimum ${\ell }_1$-norm interpolators: Precise asymptotics and multiple descent
• Foolish Crowds Support Benign Overfitting