Timezone: »

Foolish Crowds Support Benign Overfitting
Niladri S. Chatterji · Philip Long

Tue Nov 29 09:00 AM -- 11:00 AM (PST) @ Hall J #1005
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 noise is ameliorated by spreading it among many directions---the variance reduction arises from a foolish crowd.

Author Information

Niladri S. Chatterji (Stanford University)
Philip Long (Google)

More from the Same Authors