Tight bounds for minimum l1-norm interpolation of noisy data
This work addresses the problem of noisy interpolation in high-dimensional settings for researchers in statistics and machine learning, offering a foundational result that complements benign overfitting literature.
The paper tackles the prediction error of minimum l1-norm interpolation for noisy data with isotropic features and sparse ground truths, providing matching upper and lower bounds of order σ²/log(d/n) that are tight up to negligible terms when d >> n, and showing asymptotic consistency.
We provide matching upper and lower bounds of order $σ^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.