Tight bounds for minimum l1-norm interpolation of noisy data

Author name not available (Why is that?)

Publication date: 10 November 2021

Abstract: We provide matching upper and lower bounds of order

s i g m a^{2} / l o g (d / n)

for the prediction error of the minimum

e l l_{1}

-norm interpolator, a.k.a. basis pursuit. Our result is tight up to negligible terms when

d g g 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

e l l_{2}

-norm interpolation, where asymptotic consistency can be achieved only when the features are effectively low-dimensional.

Has companion code repository: https://github.com/DonhauserK/DonhauserK.github.io

This page was built for publication: Tight bounds for minimum l1-norm interpolation of noisy data

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6382746)