Prove the O(1/t) rate for gradient descent

ProofAdvanced⏱ 1 hourOptimizationgradient descentconvexratepotential functionflagship

Problem

Let $f$ be convex and $L$ -smooth with minimiser $x^\star$ . Prove that gradient descent with step $\eta = 1/L$ satisfies

f(x_t)-f^\star \le \frac{L\|x_0-x^\star\|_2^2}{2t}.

Identify explicitly the potential function used and the point at which convexity (as opposed to smoothness) is required.

Write a complete argument. Every inequality you use should be one you could state precisely.

Hints — 0 of 3 revealed

Opening this before you have a real attempt on paper is the fastest way to feel like you understand something you cannot reproduce.

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
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