Stochastic gradient descent and mini-batches

Estimating the gradient from a few samples

Most fitting problems minimise an average over data, $f(\mathbf w)=\frac1n\sum_{i=1}^{n}\ell_i(\mathbf w)$, for instance squared errors over $n$ observations. The exact gradient needs all $n$ terms at every step, which is too slow when $n$ is millions of ticks. Stochastic gradient descent draws a random mini-batch $B$ of $b$ observations and uses their average gradient $g_B$ instead. This estimate is unbiased, meaning that on average it equals the true gradient.

The price of the shortcut is noise. The variance of the batch gradient falls like $1/b$, so halving its standard deviation needs a four times larger batch, a steeply diminishing return. One epoch is a full pass over the data and holds $n/b$ updates. With a constant step the iterates never settle: they keep jittering in a small ball around the minimum, because even at the minimum the batch gradient is not zero. The fix is a step that shrinks. The classical Robbins-Monro conditions ask that $\sum_t\eta_t=\infty$, so the walk can travel as far as needed, and $\sum_t\eta_t^{2}<\infty$, so the noise dies out. The schedule $\eta_t=\eta_0/t$ satisfies both.

• Unbiased: a random batch gradient equals the full gradient on average.
• Noisy: variance $\sigma^2/b$, so four times the batch halves the standard deviation.
• Shrinking steps: $\sum\eta_t=\infty$ and $\sum\eta_t^2<\infty$, e.g. $\eta_t=\eta_0/t$, give convergence.

Lab · what's graded

• The full gradient15 pts
• The noise of one sample15 pts
• The noise of a batch15 pts
• Updates per epoch15 pts
• A step schedule that converges15 pts
• The mini-batch loop10 pts
• Why a constant step does not settle15 pts