Definition
Stochastic gradient descent replaces the full gradient by the gradient of one randomly chosen example: pick uniformly from and update . Each step costs one example instead of , and on average it points the right way.
SGD is the reason deep learning scales. A full gradient over millions of examples is a full pass over the data; a stochastic gradient is one forward and backward pass. If the examples are redundant, as real datasets are, the first thousand stochastic steps make far more progress than one exact step that costs the same.
The idea comes from statistics. Robbins and Monro (1951), "A stochastic approximation method", showed how to find the root of a function you can only observe with noise, using a step size that decreases at the right rate. Kiefer and Wolfowitz (1952) extended it to minimization using finite differences. Rosenblatt's perceptron rule (1958) and Widrow and Hoff's LMS rule (1960) are SGD on particular losses, and backpropagation networks were trained by per-example "online" updates from the start. Bottou's work in the 1990s and 2000s, and the review by Bottou, Curtis and Nocedal (2018), made the large-scale case: SGD reaches a given test error with far less computation than batch methods.
An unbiased, noisy gradient
- index drawn uniformly at random at step (in practice: the next example of a shuffled epoch)
- stochastic gradient: the gradient of a single example's loss
- step size at step t; constant or decaying
- average over the random choice of example, with θ held fixed
Unbiasedness means the noise averages out over many steps, so SGD follows the full gradient in expectation. The noise has covariance . Far from the optimum the full gradient dominates and SGD behaves like gradient descent. Near the optimum the full gradient goes to zero but the per-example gradients do not: each example still wants its own fit. That is the defining difficulty of SGD.
Constant step size: the noise ball
With a constant , SGD converges quickly (at gradient descent's linear rate) to a neighbourhood of the minimum and then wanders inside it forever. For a quadratic with Hessian and gradient-noise covariance at the optimum, the stationary spread of the iterates satisfies for small , and taking the trace gives the size of the floor:
- total variance of a one-example gradient at the optimum, where the mean gradient is zero
- the floor is proportional to the step: halve η, halve the floor, but approach it half as fast
This is the speed–accuracy trade-off of constant-step SGD: a large gets to the ball quickly but the ball is big; a small has a small ball that takes long to reach. Learning-rate decay schedules exist to get both, by starting large and shrinking the ball later.
Robbins–Monro step sizes
- the steps must add up to an unbounded distance, so the iterate can reach the optimum from anywhere
- the accumulated noise (variance ) stays finite, so the wandering dies out
- how many steps before the decay starts to bite
With on a -strongly convex problem, SGD reaches , provided the step does not start too small (roughly for this schedule; otherwise the decay outruns the progress). For general convex problems a step gives . These rates are much slower than gradient descent's per step, but each step is times cheaper, and they do not depend on at all.
SGD at a glance
- Cost per step
- one example: of a full gradient
- Gradient
- unbiased: ; variance does not vanish at
- Constant η
- fast linear phase, then a floor
- Decaying η
- converges if , ; when strongly convex
- Stability
- set by the curvature of single examples, not just : SGD can diverge at an where full GD is stable
- Sampling
- theory: with replacement; practice: random reshuffling each epoch, usually slightly faster
- PyTorch
torch.optim.SGD(params, lr=..., momentum=0, weight_decay=0, nesterov=False)applies whatever gradient you computed: single example, mini-batch or full batch
Worked example: three numbers
Let with . The full loss is minimized at the mean, , and the full gradient is . A single example's gradient is .
| step | θ before | sampled yᵢ | gᵢ = θ − yᵢ | full ∇f = θ − 3 | θ after |
|---|---|---|---|---|---|
| 1 | 0 | 6 | −6 | −3 | 3 |
| 2 | 3 | 1 | 2 | 0 | 2 |
| 3 | 2 | 2 | 0 | −1 | 2 |
| 4 | 2 | 6 | −4 | −1 | 4 |
- 1Step 1 happens to land exactly on . The full gradient there is 0, so gradient descent would stop.
- 2Step 2 samples , whose gradient at is , and SGD walks away from the optimum to . This is the noise ball: at the per-example gradients average to zero but are individually large, with variance .
- 3For this 1-D problem the stationary spread is exact: gives . With that is , so (a 20-million-step simulation gives 0.123). The small- formula is close.
- 4Halving to roughly halves the floor (to ); a schedule sends it to zero.
Noise that helps: implicit regularization
SGD's noise is not only a cost. In non-convex problems it lets the iterate escape saddle points and narrow basins that full-batch GD would settle into. Keskar et al. (2017) observed that small-batch training tends to end in flatter minima than large-batch training, and that the large-batch solutions generalize worse; the link between flatness and generalization is debated, but the effect on which minimum is found is real.
A more precise statement: Smith, Dherin, Barrett and De (2021) showed that, for small learning rates, SGD with random shuffling follows the gradient flow of a modified loss , where the bar averages the squared norm of the mini-batch gradients over an epoch. Part of that penalty is the full gradient's norm; the rest is the gradient variance, which grows like , so the extra regularization relative to full-batch GD scales like . Full-batch GD has a similar but weaker implicit term (Barrett and Dherin, 2021). The noise scale is the quantity that matters, which is why learning rate and batch size have to be tuned together (see Mini-batch gradient descent).
1import torch, torch.nn as nn2from torch.utils.data import DataLoader, TensorDataset34X = torch.randn(1000, 2)5y = X @ torch.tensor([1.5, -1.0]) + 0.5 * torch.randn(1000)6model = nn.Linear(2, 1, bias=False)78loader = DataLoader(TensorDataset(X, y), batch_size=1, shuffle=True) # one example per step9opt = torch.optim.SGD(model.parameters(), lr=0.1) # plain SGD: no momentum10tau = 20011sched = torch.optim.lr_scheduler.LambdaLR(opt, lambda t: 1 / (1 + t / tau)) # η_t = η0/(1 + t/τ)1213for epoch in range(3):14 for xb, yb in loader:15 opt.zero_grad()16 loss = 0.5 * (model(xb).squeeze(-1) - yb).pow(2).mean()17 loss.backward()18 opt.step()19 sched.step() # once per update, not once per epoch20 print(epoch, model.weight.data, sched.get_last_lr())2122# torch.optim.SGD itself is just θ ← θ − lr·(grad + weight_decay·θ), optionally with momentum.23# The "stochastic" part is entirely in which examples produced the gradient.Use when
- +Cost per step independent of ; progress starts after one example
- +Unbiased gradient: follows full GD on average, converges with a Robbins–Monro schedule
- +Noise helps escape saddles and sharp basins; acts as implicit regularization
- +Natural for streaming data and online learning
Avoid when
- −Constant step stalls at a floor ; reaching high precision needs a decaying schedule
- −Very noisy updates; one example per step wastes the parallelism of GPUs
- −Sensitive to outlier examples with large gradients or curvature
- −Slow asymptotic rate ( at best) compared with full GD's linear rate
Check yourself
With a constant learning rate, SGD on a strongly convex problem has stopped improving. You halve the learning rate. What happens to the final excess loss and to the time needed to reach it?
Check yourself
Which pair of step-size sequences both satisfy the Robbins–Monro conditions?
Remember
- ✓SGD steps on for a random example: unbiased for , at of the cost.
- ✓At the optimum the mean gradient is zero but per-example gradients are not, so constant-step SGD stalls in a noise ball .
- ✓Robbins–Monro: , (e.g. ) gives convergence, when strongly convex.
- ✓Its noise acts as an implicit regularizer whose strength scales with η / batch size.
- ✓
torch.optim.SGDis the update rule; batch size 1 in the DataLoader is what makes it one-example SGD.