Implicit bias of gradient descent on underdetermined least squares

ProofIntermediate⏱ 30 minDL Theoryimplicit biasminimum normrow space

Theory: Why Does Deep Learning Optimization Work? →

Problem

Prove that gradient descent from $\beta_0$ on $\tfrac12\|y-X\beta\|_2^2$ converges to the interpolator closest to $\beta_0$ in $\ell^2$ . Explain why this makes initialisation part of the inductive bias, and why the analogous deep-network statement is open.

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
Gradient descent finds the minimum-norm interpolator	Learning Theory	Proof	Intermediate	30 min
Logistic regression diverges on separable data	Classical ML	Proof	Intermediate	30 min
What fitting random labels rules out	DL Theory	Proof	Intermediate	30 min
Fit a scaling law and derive the compute-optimal allocation run	DL Theory	Coding	Advanced	3 hours
Reproduce double descent run	Learning Theory	Coding	Advanced	3 hours