Gradient descent finds the minimum-norm interpolator

ProofIntermediate⏱ 30 minLearning Theoryimplicit biasminimum normgradient descent

Theory: Bias–Variance, Interpolation and Double Descent →

Problem

Let $X\in\R^{n\times p}$ with $p>n$ and $\operatorname{rank}(X)=n$ . Show that gradient descent on $\tfrac12\|y-X\beta\|_2^2$ from $\beta_0 = 0$ converges to the minimum $\ell^2$ -norm solution of $X\beta=y$ . What happens for $\beta_0\ne0$ ?

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
The bias–variance decomposition is an identity	Learning Theory	Proof	Beginner	15 min
Implicit bias of gradient descent on underdetermined least squares	DL Theory	Proof	Intermediate	30 min
Linear convergence under strong convexity	Optimization	Proof	Intermediate	30 min
Logistic regression diverges on separable data	Classical ML	Proof	Intermediate	30 min
Prove the O(1/t) rate for gradient descent abyss	Optimization	Proof	Advanced	1 hour