SGD on convex Lipschitz objectives

ProofIntermediate⏱ 30 minSGDsgdconvexaveragingrate

Theory: SGD — Convergence Under Every Standard Assumption →

Problem

Prove $\E f(\bar x_T)-f^\star\le GR/\sqrt T$ for SGD with constant step $\eta = R/(G\sqrt T)$ , where $R = \|x_0-x^\star\|_2$ and $\E[\|g_t\|_2^2\mid\mathcal F_t]\le G^2$ . Note where the proof is identical to the deterministic subgradient argument and where it differs.

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
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
Expected error does not give a high-probability guarantee	SGD	Proof	Advanced	30 min