The exact step-size threshold on a quadratic

ProofBeginner⏱ 15 minOptimizationstep sizestabilitydivergencequadratic

Theory: Gradient Descent and Its Convergence Rates →

Problem

For $f(x) = \frac12x^\top Ax$ with $A$ symmetric positive definite with eigenvalues in $[\mu, L]$ , show that gradient descent with step $\eta$ gives $x_t = (I-\eta A)^tx_0$ , and determine exactly the set of $\eta$ for which $x_t\to0$ for every $x_0$ . Find the $\eta$ minimising the worst-case contraction factor.

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
Linear convergence under strong convexity	Optimization	Proof	Intermediate	30 min
Logistic regression diverges on separable data	Classical ML	Proof	Intermediate	30 min
Non-convex gradient descent reaches an approximate stationary point	Optimization	Proof	Intermediate	30 min
Reading the Robbins–Monro conditions off the proof	SGD	Proof	Intermediate	30 min
Gradient descent with exact line search on a quadratic	Optimization	Proof	Advanced	1 hour