The non-convex SGD rate

ProofAdvanced⏱ 1 hourSGDsgdnon-convexstationarityrate

Problem

Prove that for $L$ -smooth $f$ bounded below, SGD with constant $\eta\le1/L$ satisfies

\frac1T\sum_{t<T}\E\|\nabla f(x_t)\|_2^2 \le \frac{2(f(x_0)-f^\star)}{\eta T}+\eta L\sigma^2 ,

and determine the $\eta$ and the resulting rate for a budget $T$ . Compare with the deterministic $O(1/T)$ rate.

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
Measure the covariance estimation rate run	High-Dim Statistics	Coding	Intermediate	1 hour
Mini-batching and the compute budget	SGD	Numerical	Intermediate	30 min
Non-convex gradient descent reaches an approximate stationary point	Optimization	Proof	Intermediate	30 min
Reading the Robbins–Monro conditions off the proof	SGD	Proof	Intermediate	30 min
SGD on convex Lipschitz objectives	SGD	Proof	Intermediate	30 min