# On the robustness of the minimum ℓ2 interpolator

arXiv: https://arxiv.org/abs/2003.05838 · HTML: https://mlsanity.com/paper/2003.05838/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Mar 2020.

## Built on by (most cited first, 4 of 4)

- [Towards an Understanding of Benign Overfitting in Neural Networks](https://mlsanity.com/paper/2106.03212/) (2021)
- [Data splitting improves statistical performance in overparametrized regimes](https://mlsanity.com/paper/2110.10956/) (2021)
- [Provable Tempered Overfitting of Minimal Nets and Typical Nets](https://mlsanity.com/paper/2410.19092/) (2024)
- [AdaBoost and robust one-bit compressed sensing](https://mlsanity.com/paper/2105.02083/) (2021)

## Abstract (arXiv)

We analyse the interpolator with minimal ℓ2-norm hatβ in a general high dimensional linear regression framework where mathbb Y=mathbb Xβ^*+xi where mathbb X is a random n× p matrix with independent mathcal N(0,Sigma) rows and without assumption on the noise vector xi∈ mathbb Rn. We prove that, with high probability, the prediction loss of this estimator is bounded from above by (|β^*|22rcn(Sigma)vee |xi|2)/n, where rk(Sigma)=sumi≥ kλi(Sigma) are the rests of the sum of eigenvalues of Sigma. These bounds show a transition in the rates. For high signal to noise ratios, the rates |β^*|22rcn(Sigma)/n broadly improve the existing ones. For low signal to noise ratio, we also provide lower bound holding with large probability. Under assumptions on the sprectrum of Sigma, this lower bound is of order | xi|22/n, matching the upper bound. Consequently, in the large noise regime, we are able to precisely track the prediction error with large probability. This results give new insight when the interpolation can be harmless in high dimensions.