The interpolation peak is a conditioning phenomenon

ProofAdvanced⏱ 30 minLearning Theorydouble descentconditioningvariancemarchenko-pastur

Theory: Bias–Variance, Interpolation and Double Descent →

Problem

For least squares with $p<n$ and fixed design, show that the variance component of the risk is $\sigma^2\operatorname{tr}\big((X^\top X)^{-1}\Sigma\big)$ and that it diverges as $\lambda_{\min}(X^\top X)\to0$ . Using Marchenko–Pastur, locate the divergence at $p=n$ and explain why the risk falls again for $p>n$ .

Write a complete argument. Every inequality you use should be one you could state precisely.

Solution

Opening this before you have a real attempt on paper is the fastest way to feel like you understand something you cannot reproduce.

Related problems

All problems

Problem	Field	Type	Difficulty	Time
Marchenko–Pastur edges and conditioning	Random Matrices	Numerical	Beginner	15 min
The bias–variance decomposition is an identity	Learning Theory	Proof	Beginner	15 min
The Δ²/12 noise variance	Quantization	Proof	Beginner	15 min
Frobenius versus operator norm for random matrices	Random Matrices	Numerical	Intermediate	30 min
Gradient descent finds the minimum-norm interpolator	Learning Theory	Proof	Intermediate	30 min