In the modern era of massive datasets containing millions of samples, computing the exact full-batch gradient $nabla f(w) = frac{1}{n} sum_{i=1}^n nabla f_i(w)$ at every iteration requires millions of forward-backward passes, becoming computationally intractable. Machine learning overcame this bottleneck by embracing randomness: Stochastic Gradient Descent (SGD) and its accelerated adaptive variants. By treating individual samples as noisy, unbiased gradient estimators, stochastic optimization turns noise from a liability into a computational asset.
1. The Stochastic Gradient Approximation
Consider the empirical risk minimization objective over $n$ training instances:
$$f(w) = frac{1}{n} sum_{i=1}^n f_i(w)$$
Instead of summing over all $n$ samples, SGD uniformly samples an index $i_t sim text{Uniform}({1, dots, n})$ at step $t$ and updates parameters using solely the stochastic gradient $g_t = nabla f_{i_t}(w_t)$:
$$w_{t+1} = w_t – eta_t nabla f_{i_t}(w_t)$$
Critically, the stochastic gradient is an unbiased estimator of the true gradient:
$$mathbb{E}_{i_t}[g_t mid w_t] = frac{1}{n} sum_{i=1}^n nabla f_i(w_t) = nabla f(w_t)$$
However, the stochastic gradient suffers from variance $sigma^2 = mathbb{E}[|g_t – nabla f(w_t)|^2]$. To stabilize gradient variance, modern practice groups samples into mini-batches $mathcal{B}_t$ of size $B$, reducing variance by a factor of $B$:
$$g_t = frac{1}{B} sum_{i in mathcal{B}_t} nabla f_i(w_t), quad text{Var}(g_t) = frac{sigma^2}{B}$$
2. Polyak Momentum and Nesterov Accelerated Gradient
To eliminate high-frequency stochastic oscillations and accelerate progress along flat ravines, Boris Polyak (1964) introduced Heavy-Ball Momentum, simulating a physical particle rolling down an energy surface with mass and friction:
$$v_t = beta v_{t-1} + g_t, quad w_{t+1} = w_t – eta v_t$$
The velocity vector $v_t$ accumulates past gradients exponentially: $v_t = sum_{tau=0}^t beta^{t-tau} g_tau$. Gradients along oscillating orthogonal directions cancel out by destructive interference, whereas persistent gradients along the ravine floor reinforce each other by constructive interference, increasing effective velocity by $frac{1}{1 – beta}$.
Yurii Nesterov (1983) refined this with Nesterov Accelerated Gradient (NAG). Rather than evaluating the gradient at the current position $w_t$, Nesterov evaluates the gradient “looking ahead” along the momentum trajectory:
$$g_t = nabla f(w_t – eta beta v_{t-1}), quad v_t = beta v_{t-1} + g_t, quad w_{t+1} = w_t – eta v_t$$
This lookahead correction acts as an adaptive brake, dampening velocity before ascending opposing valley slopes and improving the theoretical convergence rate on convex functions from $mathcal{O}(1/T)$ to the optimal theoretical lower bound $mathcal{O}(1/T^2)$.
3. Adaptive Moment Estimation: The Adam Algorithm
In high dimensions, different coordinates exhibit vastly different curvatures. Using a single uniform scalar learning rate $eta$ across all dimensions either causes ill-conditioned coordinates to explode or well-conditioned coordinates to stall. Diederik Kingma and Jimmy Ba (2014) introduced Adam (Adaptive Moment Estimation), dynamically tracking running exponential averages of both the first moment (mean) and second raw moment (uncentered variance) of the gradients:
- First Moment (Velocity):
$$m_t = beta_1 m_{t-1} + (1 – beta_1) g_t$$
- Second Raw Moment (Scale/Curvature):
$$v_t = beta_2 v_{t-1} + (1 – beta_2) g_t^2 quad (text{element-wise square})$$
- Bias Correction: Because $m_0 = 0$ and $v_0 = 0$, both running moments are heavily biased toward zero during the initial iterations. Dividing by $1 – beta^t$ yields unbiased estimators:
$$hat{m}_t = frac{m_t}{1 – beta_1^t}, quad hat{v}_t = frac{v_t}{1 – beta_2^t}$$
- Parameter Update:
$$w_{t+1} = w_t – frac{eta}{sqrt{hat{v}_t} + epsilon} odot hat{m}_t$$
Dividing coordinate-wise by $sqrt{hat{v}_t}$ normalizes the step size: coordinates with large, noisy gradients are dampened, while coordinates with sparse, infrequent gradients receive larger relative updates. Adam remains the ubiquitous default optimization engine across modern machine learning.
