Gradient descent with exact line search on a quadratic

ProofAdvanced⏱ 1 hourOptimizationline searchkantorovichquadraticrate

Theory: Gradient Descent and Its Convergence Rates →

Problem

For $f(x) = \frac12x^\top Ax$ with $\mu I\preceq A\preceq LI$ , gradient descent with exact line search chooses $\eta_t = \arg\min_\eta f(x_t-\eta\nabla f(x_t))$ .

Derive the closed form for $\eta_t$ .
Show that the rate is $f(x_{t+1}) \le \left(\frac{\kappa-1}{\kappa+1}\right)^2f(x_t)$ (the Kantorovich bound).
Explain why exact line search does not remove the $\kappa$ dependence.

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 exact step-size threshold on a quadratic	Optimization	Proof	Beginner	15 min
Linear convergence under strong convexity	Optimization	Proof	Intermediate	30 min
Measure the covariance estimation rate run	High-Dim Statistics	Coding	Intermediate	1 hour
Non-convex gradient descent reaches an approximate stationary point	Optimization	Proof	Intermediate	30 min
SGD on convex Lipschitz objectives	SGD	Proof	Intermediate	30 min