SGD & Optimization Dynamics
Stochastic approximation, step-size schedules, variance reduction, adaptive methods and their convergence guarantees.
Level 3 — Graduate
- SGD — Convergence Under Every Standard Assumption21 min
Convex, strongly convex and non-convex SGD; constant versus decaying steps; Robbins–Monro; and the difference between expected and high-probability guarantees.
The stochastic gradient oracleSGD on convex Lipschitz functionsSGD on strongly convex smooth functions with constant step - Adaptive Methods and Variance Reduction13 min
AdaGrad, RMSProp, Adam and AdamW derived from their design goals, plus SVRG and SAGA and what each one actually guarantees.
AdaGrad regret boundAdamAdam can fail to converge
Problems (12)
Open in the browser| Solved | Problem | Type | Difficulty | Time |
|---|---|---|---|---|
| Derive Adam's bias correction | Proof | 15 min | ||
| Mini-batching and the compute budget | Numerical | 30 min | ||
| Reading the Robbins–Monro conditions off the proof | Proof | 30 min | ||
| SGD on convex Lipschitz objectives | Proof | 30 min | ||
| Why AdamW differs from Adam with L2 | Proof | 30 min | ||
| Expected error does not give a high-probability guarantee | Proof | 30 min | ||
| Implement SGD and locate the noise floor run | Coding | 3 hours | ||
| The AdaGrad summation inequality | Proof | 30 min | ||
| The non-convex SGD rate | Proof | 1 hour | ||
| The SVRG control variate | Proof | 1 hour | ||
| Derive the constant-step SGD noise floor abyss | Proof | 1 hour | ||
| Open: why does Adam beat SGD on transformers? abyss | Proof | Research |