Stochastic Gradient Descent

Training a model means walking downhill on a loss surface. The rule is simple enough: work out which direction reduces the error and step that way. The problem is the cost of working it out. The true downhill direction depends on every training example, so a single honest step over ten million rows means ten million gradient evaluations — and you need thousands of steps. Nobody has that budget.

But look at what those ten million evaluations buy you. The examples are enormously redundant: the first ten thousand rows already point in essentially the same direction as the full set. You spent the other 99.9% of your compute refining a number you were going to round off anyway.

The analogy: fog on a hillside

You are somewhere on a hillside in thick fog and want to reach the bottom of the valley. You cannot see it. All you can do is feel the ground and step downhill.

Full-batch gradient descent is hiring a survey team to map the entire hillside before committing to a single footstep. The direction is exactly right, and you take one step per week.

Stochastic gradient descent is feeling the slope under your own boots and stepping straight away. Sometimes you are standing on a rock and the slope you feel points slightly wrong. But you take a thousand steps in the time the survey team takes one, and the wrong readings largely cancel out because they are wrong in random directions. You arrive first, by a long way, even though no individual step was correct.

The maths

The loss you actually care about is the average over all $N$ training examples,

$$L(\theta) = \frac{1}{N} \sum_{i=1}^{N} \ell_i(\theta)$$

where $\theta$ is the whole collection of parameters and $\ell_i$ is the error on example $i$. In words: the total loss is the average of the individual losses.

Gradient descent updates the parameters by stepping against the gradient:

$$\theta \leftarrow \theta - \eta \, \nabla L(\theta)$$

In words: move each parameter in the direction that reduces the loss, by an amount proportional to how steeply that parameter affects it. The learning rate $\eta$ is the size of the step. The gradient $\nabla L$ comes from Backpropagation.

SGD replaces $\nabla L$ with the gradient of a small random minibatch $B$:

$$\theta \leftarrow \theta - \eta \cdot \frac{1}{|B|} \sum_{i \in B} \nabla \ell_i(\theta)$$

In words: compute the downhill direction from a random handful of examples and step now. The justification is one line: because the minibatch is drawn at random, the average of its gradient over all possible draws is exactly the full gradient. The estimate is noisy but unbiased — it is right on average, and the noise shrinks like $1/\sqrt{|B|}$ as the batch grows.

The explorer below is the fog analogy made literal. Push the learning rate down and watch the walker crawl; push it up and watch it converge in a few strides; push it further and watch it fly past the bottom and climb the far wall. There is a band of good values, and it is narrower than you would like.

Worked example 1: three steps, and the divergence threshold

Take the simplest possible loss, $L(w) = (w - 3)^2$, whose minimum is obviously at $w = 3$. The gradient is $2(w-3)$. Start at $w = 0$ with $\eta = 0.1$.

• Step 1. Gradient $= 2(0 - 3) = -6$. Update: $w = 0 - 0.1(-6) = 0.6$.
• Step 2. Gradient $= 2(0.6 - 3) = -4.8$. Update: $w = 0.6 + 0.48 = 1.08$.
• Step 3. Gradient $= 2(1.08 - 3) = -3.84$. Update: $w = 1.08 + 0.384 = 1.464$.

Look at the distance remaining: $3.0,\ 2.4,\ 1.92,\ 1.536$. Each is exactly $0.8$ times the last. Substituting the update into the distance gives the reason:

$$w_{k+1} - 3 = (1 - 2\eta)(w_k - 3)$$

In words: every step multiplies your remaining distance by the fixed factor $1 - 2\eta$. That single expression tells you everything about the learning rate here. At $\eta = 0.1$ the factor is $0.8$, so you close 20% of the gap per step. At $\eta = 0.5$ the factor is $0$ and you land on the answer in one step. At $\eta = 0.6$ the factor is $-0.2$: you overshoot but land closer, oscillating in. At $\eta = 1.1$ the factor is $-1.2$, so the distance grows 20% per step and you diverge — not slowly, but explosively. Anything above $\eta = 1$ blows up on this problem.

Worked example 2: same compute, four times the progress

Fit a slope with no intercept, $\hat{y} = wx$, to four points: $(1, 2),\ (2, 3.8),\ (3, 6.3),\ (4, 7.9)$. The true slope is about $2$. Per-example gradient is $(w x_i - y_i)\, x_i$. Start at $w = 0.5$ with $\eta = 0.02$.

Full batch. Evaluate all four gradients: $-1.5,\ -5.6,\ -14.4,\ -23.6$. Their average is $-11.275$, so one step gives $w = 0.5 + 0.02(11.275) = 0.726$. That cost four gradient evaluations.

SGD, one example at a time. Spend the same four evaluations, but update after each.

1. Point 1: gradient $-1.5$, so $w = 0.5 + 0.030 = 0.530$.
2. Point 2: gradient $(0.53 \times 2 - 3.8) \times 2 = -5.48$, so $w = 0.530 + 0.110 = 0.640$.
3. Point 3: gradient $(0.640 \times 3 - 6.3) \times 3 = -13.14$, so $w = 0.640 + 0.263 = 0.902$.
4. Point 4: gradient $(0.902 \times 4 - 7.9) \times 4 = -17.16$, so $w = 0.902 + 0.343 = 1.246$.

The average loss started at $8.49$. Full batch brought it to $6.14$; the SGD pass brought it to $2.17$, for identical compute. The reason is visible in the arithmetic: each SGD gradient was computed at an already improved parameter value, while all four full-batch gradients were stale, computed at the same starting point.

What this means in practice

The learning rate is the hyperparameter that matters. Too small and training crawls; too large and it diverges, often after appearing fine for a while. Tune it first, before architecture, before anything else.

A constant rate does not converge. Because each gradient carries noise, SGD eventually stops making progress and rattles around inside a ball near the minimum whose size is set by $\eta$ and the batch size. To settle you must shrink the step — see Learning Rate Schedules.

Batch size is a noise dial, not just a speed dial. Bigger batches give cleaner gradients and better hardware utilisation, but the noise itself does useful work: it discourages the model from settling into narrow, brittle minima. This is the trade-off behind Batch Size and Generalization.

Know the vocabulary. One step (or iteration) is one minibatch update. One epoch is one full pass over the data, which is $N / |B|$ steps. Shuffle between epochs, or the model learns the ordering.

Plain SGD is rarely used bare. Momentum smooths the noisy directions by averaging recent gradients, and Adam additionally gives every parameter its own step size. Both are still SGD underneath.