Foolish Crowds Support Benign Overfitting

Abstract

We prove a lower bound on the excess risk of sparse interpolating procedures for linear regression with Gaussian data in the overparameterized regime. We apply this result to obtain a lower bound for basis pursuit (the minimum ${\ell }_1$-norm interpolant) that implies that its excess risk can converge at an exponentially slower rate than OLS (the minimum ${\ell }_2$-norm interpolant), even when the ground truth is sparse. Our analysis exposes the benefit of an effect analogous to the "wisdom of the crowd", except here the harm arising from fitting the $\text{noise}$ is ameliorated by spreading it among many directions -- the variance reduction arises from a $\text{foolish}$ crowd.

References in corpus (5)

• Reconciling modern machine learning practice and the bias-variance trade-off
• Benign Overfitting in Linear Regression
• Benign overfitting in ridge regression
• Uniform Convergence of Interpolators: Gaussian Width, Norm Bounds, and Benign Overfitting
• The Geometry of Uniqueness, Sparsity and Clustering in Penalized Estimation

Cited by in corpus (1)

• Tight bounds for minimum l1-norm interpolation of noisy data