Linear convergence under strong convexity

ProofIntermediate⏱ 30 minOptimizationgradient descentstrongly convexlinear ratepl

Theory: Gradient Descent and Its Convergence Rates →

Problem

Prove that for $\mu$ -strongly convex and $L$ -smooth $f$ , gradient descent with $\eta = 1/L$ satisfies $f(x_t)-f^\star \le (1-1/\kappa)^t(f(x_0)-f^\star)$ with $\kappa = L/\mu$ . Deduce the number of iterations needed for accuracy $\eps$ .

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
Gradient descent finds the minimum-norm interpolator	Learning Theory	Proof	Intermediate	30 min
Non-convex gradient descent reaches an approximate stationary point	Optimization	Proof	Intermediate	30 min
Gradient descent with exact line search on a quadratic	Optimization	Proof	Advanced	1 hour
Implement gradient descent and verify all four rates run	Optimization	Coding	Advanced	3 hours