Skip to content
nonconvexcard

Why ordinary least squares degrades as p approaches n

ProofAdvanced⏱ 30 minRandom Matricesleast squaresconditioningvariancemarchenko-pastur

Problem

Let y=Xβ⋆+εy = X\beta^\star+\varepsilon with ε∼N(0,σ2In)\varepsilon\sim\Ncal(0,\sigma^2I_n) and XX having i.i.d. N(0,1)\Ncal(0,1) entries, p<np<n. Show that the expected squared estimation error of ordinary least squares is

E∥β^−β⋆∥22=σ2 E[tr⁡((X⊤X)−1)],\E\|\hat\beta-\beta^\star\|_2^2 = \sigma^2\,\E\big[\operatorname{tr}\big((X^\top X)^{-1}\big)\big],

and use the Marchenko–Pastur law to argue that this behaves like σ2pn−p\frac{\sigma^2 p}{n-p} for large n,pn,p. Evaluate at p/n=0.5p/n = 0.5 and p/n=0.95p/n = 0.95.

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
SolvedProblemFieldTypeDifficultyTime
Least squares as orthogonal projectionClassical MLProofFoundation15 min
Marchenko–Pastur edges and conditioningRandom MatricesNumericalBeginner15 min
The Δ²/12 noise varianceQuantizationProofBeginner15 min
Frobenius versus operator norm for random matricesRandom MatricesNumericalIntermediate30 min
Implement ridge and find the optimal lambda runClassical MLCodingIntermediate1 hour