The Nesterov potential function

ProofGraduate⏱ 3 hoursAdvanced Optimizationnesterovlyapunovpotential functiono(1/t^2)

Problem

Verify that for Nesterov's method on a convex $L$ -smooth $f$ , the quantity

\mathcal E_t = \frac{t(t+1)}{4L}\big(f(x_t)-f^\star\big) + \frac12\|z_t-x^\star\|_2^2, \qquad z_t = x_t + \frac t2(x_t-x_{t-1}),

is non-increasing, and deduce the $O(1/t^2)$ rate. Identify the exact place where the specific momentum coefficient is needed.

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
Simulate and compare convergence rates run	Advanced Optimization	Coding	Intermediate	1 hour
Prove the O(1/t) rate for gradient descent abyss	Optimization	Proof	Advanced	1 hour
Acceleration as an optimal polynomial	Advanced Optimization	Proof	Graduate	1 hour
Heavy ball on a quadratic — the spectral analysis abyss	Advanced Optimization	Proof	Graduate	3 hours
The Ω(1/t²) lower bound for first-order methods abyss	Advanced Optimization	Proof	Olympiad / Extreme	1 day