AISTATS 2022poster41 citations
Tight bounds for minimum $\ell_1$-norm interpolation of noisy data
Guillaume Wang, Konstantin Donhauser, Fanny Yang
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.
BibTeX
@InProceedings{pmlr-v151-wang22k,
title = { Tight bounds for minimum $\ell_1$-norm interpolation of noisy data },
author = {Wang, Guillaume and Donhauser, Konstantin and Yang, Fanny},
booktitle = {Proceedings of The 25th International Conference on Artificial Intelligence and Statistics},
pages = {10572--10602},
year = {2022},
editor = {Camps-Valls, Gustau and Ruiz, Francisco J. R. and Valera, Isabel},
volume = {151},
series = {Proceedings of Machine Learning Research},
month = {28--30 Mar},
publisher = {PMLR},
pdf = {https://proceedings.mlr.press/v151/wang22k/wang22k.pdf},
url = {https://proceedings.mlr.press/v151/wang22k.html},
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. }
}