Why SGD converges
What can actually be proved about gradient methods — O(1/k) for smooth convex losses, a linear rate with strong convexity, Nesterov's optimal O(1/k²), SGD's noise floor with a constant step and its O(1/k) and O(1/√k) rates with decaying steps, variance reduction, and what survives without convexity.
45 min
After this lesson you can
- Prove the O(1/k) rate of gradient descent on smooth convex functions and state the linear rate under strong convexity
- State Nesterov's accelerated rate and the matching lower bound, and explain what "optimal" means
- Derive the SGD recursion, the noise floor with a constant step, and why decaying steps (Robbins–Monro) remove it
- Explain how variance reduction (SVRG) recovers a linear rate on finite sums
- Say what gradient methods guarantee on non-convex losses (stationary points) and what is known about saddle points
In this lesson
- The picture first
- Gradient descent on a smooth convex function: O(1/k)
- Acceleration: Nesterov’s O(1/k²), and why nothing beats it
- SGD: the recursion, the floor, and the cure
- Variance reduction: linear rates for finite sums
- Without convexity: stationary points and saddles
This lesson is part of Descent Pro
Descent Pro unlocks every lesson on the route, from base camp to the summit. Every plan starts with a free trial.