Non-convex gradient descent reaches an approximate stationary point

ProofIntermediate⏱ 30 minOptimizationnon-convexstationary pointrate

Problem

Let $f$ be $L$ -smooth and bounded below by $f^\star$ . Prove that gradient descent with $\eta = 1/L$ satisfies

\min_{0\le s<t}\|\nabla f(x_s)\|_2 \le \sqrt{\frac{2L(f(x_0)-f^\star)}{t}} .

Then state three things this does not establish, with a concrete example for one of them.

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

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
Linear convergence under strong convexity	Optimization	Proof	Intermediate	30 min
Measure the covariance estimation rate run	High-Dim Statistics	Coding	Intermediate	1 hour
SGD on convex Lipschitz objectives	SGD	Proof	Intermediate	30 min
Why exactly one factor starts at zero	Fine-Tuning	Proof	Intermediate	30 min