On the robustness of the minimum $\ell_2$ interpolator
This work addresses the robustness of interpolation in high-dimensional settings, offering theoretical guarantees that are incremental but precise for understanding overfitting risks.
The paper analyzes the minimum ℓ₂-norm interpolator in high-dimensional linear regression, showing that its prediction loss is bounded by (‖β*‖²₂ r_{cn}(Σ) ∨ ‖ξ‖²)/n, with improved rates for high signal-to-noise ratios and matching lower bounds for low signal-to-noise ratios, providing insight into when interpolation can be harmless.
We analyse the interpolator with minimal $\ell_2$-norm $\hatβ$ in a general high dimensional linear regression framework where $\mathbb Y=\mathbb Xβ^*+ξ$ where $\mathbb X$ is a random $n\times p$ matrix with independent $\mathcal N(0,Σ)$ rows and without assumption on the noise vector $ξ\in \mathbb R^n$. We prove that, with high probability, the prediction loss of this estimator is bounded from above by $(\|β^*\|^2_2r_{cn}(Σ)\vee \|ξ\|^2)/n$, where $r_{k}(Σ)=\sum_{i\geq k}λ_i(Σ)$ are the rests of the sum of eigenvalues of $Σ$. These bounds show a transition in the rates. For high signal to noise ratios, the rates $\|β^*\|^2_2r_{cn}(Σ)/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 $Σ$, this lower bound is of order $\| ξ\|_2^2/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.