Stochastic gradient descent (SGD)

Level AdvancedDifficulty ★★★★★Application⌖ Open in the map

What is it?

Use the gradient of a small random batch instead of the whole dataset: a noisy but unbiased estimate, thousands of times cheaper. The noise even helps escape saddles and sharp minima.

Formulas

$\theta_{k+1} = \theta_k - \eta_k\,\frac{1}{|B_k|}\sum_{i\in B_k}\nabla\ell_i(\theta_k)$; $\sum_k\eta_k = \infty, \qquad \sum_k\eta_k^2 < \infty$
Robbins–Monro step-size conditions for convergence

The mathematics behind it

Expectation★★★★★fundamental
A mini-batch gradient is an unbiased estimate of the expected gradient.
Variance★★★★★frequent
Gradient noise variance falls as $1/|B|$ ; it sets the useful learning rate and batch size.

Where is it used?

Computing topics reachable from here, through the chain of ideas that leads to them:

ℒ AI and machine learning

Momentum and Adam★★★★★
Momentum and Adam→Deep learning★★★★★
Momentum and Adam→Deep learning→Convolutional networks (CNNs)★★★★★
Momentum and Adam→Deep learning→Generative models★★★★★
Momentum and Adam→Deep learning→Neural ODEs★★★★★

What depends on it

Momentum and Adam

This page has the essentials. A fuller treatment (intuition, formal definition, worked example) is on the way.