Tight bounds for minimum l1-norm interpolation of noisy data

2021/11/10 by Guillaume Wang, Konstantin Donhauser, Wang, Guillaume +3
Computer Science · Earth and Planetary Sciences · Engineering · Mathematics · #FOS: Computer and information sciences #FOS: Mathematics #Geophysical Methods and Applications #Information Theory (cs.IT) #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Seismic Imaging and Inversion Techniques #Sparse and Compressive Sensing Techniques #Statistics Theory (math.ST) #cs.IT #cs.LG #math.IT #math.ST #stat.ML #stat.TH

paper · pdf · doi:10.48550/arxiv.2111.05987

33 pages, 1 figure; accepted to AISTATS 2022

openalex publication_date 2021/11/10 · arxiv created 2022/03/07 · arxiv updated 2022/03/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We provide matching upper and lower bounds of order σ²/log(d/n) for the prediction error of the minimum ℓ₁-norm interpolator, a.k.a. basis pursuit. Our result is tight up to negligible terms when d ≫ 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 ℓ₂-norm interpolation, where asymptotic consistency can be achieved only when the features are effectively low-dimensional.

Citations

• Atomic Decomposition by Basis Pursuit
• Understanding deep learning (still) requires rethinking generalization
• A Quotient Property for Matrices with Heavy-Tailed Entries and its Application to Noise-Blind Compressed Sensing
• The generalization error of random features regression: Precise asymptotics and double descent curve
• Benign overfitting in ridge regression
• Uniform Convergence of Interpolators: Gaussian Width, Norm Bounds, and Benign Overfitting
• The Generalization Error of Random Features Regression: Precise Asymptotics and the Double Descent Curve
• Foolish Crowds Support Benign Overfitting

Related

• Minimum ℓ₁-norm interpolators: Precise asymptotics and multiple descent
• Uniform Convergence of Interpolators: Gaussian Width, Norm Bounds, and Benign Overfitting
• On the robustness of the minimum ℓ₂ interpolator
• Near-Interpolators: Rapid Norm Growth and the Trade-Off between Interpolation and Generalization
• On the robustness of minimum norm interpolators and regularized empirical risk minimizers