Derive the constant-step SGD noise floor

ProofGraduate⏱ 1 hourSGDsgdnoise floorconstant steprecursionflagship

Theory: SGD — Convergence Under Every Standard Assumption →

Problem

Let $f$ be $\mu$ -strongly convex and $L$ -smooth, and let SGD use a constant step $\eta\le1/(2L)$ with an unbiased oracle of variance at most $\sigma^2$ . Prove

\E\|x_T-x^\star\|_2^2 \le (1-\eta\mu)^T\|x_0-x^\star\|_2^2 + \frac{\eta\sigma^2}{\mu},

and interpret each term. Then determine the $\eta$ minimising the bound for a fixed budget $T$ .

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

Hints

Hints — 0 of 3 revealed

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
Mini-batching and the compute budget	SGD	Numerical	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
Expected error does not give a high-probability guarantee	SGD	Proof	Advanced	30 min
Implement SGD and locate the noise floor run	SGD	Coding	Advanced	3 hours