Stochastic gradient descent (SGD)

Step on the gradient of one random example: an unbiased but noisy estimate of the full gradient that costs 1/N as much. With a constant step it stalls in a noise ball of size ∝ η; Robbins–Monro step sizes (Σηₜ = ∞, Σηₜ² < ∞) make it converge.

11 min read1013 wordscore0 viewsupdated 2026-10-11

Definition

Stochastic gradient descent replaces the full gradient by the gradient of one randomly chosen example: pick iti_t uniformly from {1,…,N}\{1,\dots,N\} and update θt+1=θt−ηt∇ℓit(θt)\theta_{t+1}=\theta_t-\eta_t\nabla\ell_{i_t}(\theta_t). Each step costs one example instead of NN, 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

θt+1=θt−ηt gt,gt=∇ℓit(θt),Eit[gt]=1N∑i=1N∇ℓi(θt)=∇f(θt)\theta_{t+1}=\theta_t-\eta_t\,g_t,\qquad g_t=\nabla\ell_{i_t}(\theta_t),\qquad \mathbb E_{i_t}[g_t]=\frac1N\sum_{i=1}^N\nabla\ell_i(\theta_t)=\nabla f(\theta_t)
iti_t
index drawn uniformly at random at step tt (in practice: the next example of a shuffled epoch)
gtg_t
stochastic gradient: the gradient of a single example's loss
ηt\eta_t
step size at step t; constant or decaying
Eit\mathbb E_{i_t}
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 Σ(θ)=1N∑i(∇ℓi−∇f)(∇ℓi−∇f)⊤\Sigma(\theta)=\frac1N\sum_i(\nabla\ell_i-\nabla f)(\nabla\ell_i-\nabla f)^\top. 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 η\eta, SGD converges quickly (at gradient descent's linear rate) to a neighbourhood of the minimum and then wanders inside it forever. For a quadratic ff with Hessian HH and gradient-noise covariance C=Σ(θ∗)C=\Sigma(\theta^*) at the optimum, the stationary spread of the iterates satisfies HΣθ+ΣθH≈η CH\Sigma_\theta+\Sigma_\theta H\approx\eta\,C for small η\eta, and taking the trace gives the size of the floor:

lim⁡t→∞E[f(θt)−f∗]  ≈  η4tr⁡C,C=1N∑i∇ℓi(θ∗)∇ℓi(θ∗)⊤\lim_{t\to\infty}\mathbb E\big[f(\theta_t)-f^*\big]\;\approx\;\frac{\eta}{4}\operatorname{tr}C,\qquad C=\frac1N\sum_{i}\nabla\ell_i(\theta^*)\nabla\ell_i(\theta^*)^\top
tr⁡C\operatorname{tr}C
total variance of a one-example gradient at the optimum, where the mean gradient is zero
η/4\eta/4
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 η\eta gets to the ball quickly but the ball is big; a small η\eta 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

∑t=0∞ηt=∞,∑t=0∞ηt2<∞,e.g.  ηt=η01+t/τ\sum_{t=0}^{\infty}\eta_t=\infty,\qquad \sum_{t=0}^{\infty}\eta_t^2<\infty,\qquad\text{e.g. }\ \eta_t=\frac{\eta_0}{1+t/\tau}
∑ηt=∞\sum\eta_t=\infty
the steps must add up to an unbounded distance, so the iterate can reach the optimum from anywhere
∑ηt2<∞\sum\eta_t^2<\infty
the accumulated noise (variance ∝∑ηt2\propto\sum\eta_t^2) stays finite, so the wandering dies out
τ\tau
how many steps before the decay starts to bite

With ηt∝1/t\eta_t\propto1/t on a μ\mu-strongly convex problem, SGD reaches E[f−f∗]=O(1/t)\mathbb E[f-f^*]=O(1/t), provided the step does not start too small (roughly η0τμ>1/2\eta_0\tau\mu>1/2 for this schedule; otherwise the decay outruns the progress). For general convex problems a 1/t1/\sqrt t step gives O(1/t)O(1/\sqrt t). These rates are much slower than gradient descent's per step, but each step is NN times cheaper, and they do not depend on NN at all.

SGD at a glance

Cost per step
one example: 1/N1/N of a full gradient
Gradient
unbiased: E[gt]=∇f(θt)\mathbb E[g_t]=\nabla f(\theta_t); variance tr⁡Σ(θ)\operatorname{tr}\Sigma(\theta) does not vanish at θ∗\theta^*
Constant η
fast linear phase, then a floor ≈η4tr⁡C\approx\frac\eta4\operatorname{tr}C
Decaying η
converges if ∑ηt=∞\sum\eta_t=\infty, ∑ηt2<∞\sum\eta_t^2<\infty; O(1/t)O(1/t) when strongly convex
Stability
set by the curvature of single examples, not just LL: SGD can diverge at an η\eta 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
f(θ) = mean ½(xᵢ·θ − yᵢ)², N = 100, κ = 9.8— SGD — full GD, same η → −gᵢ → −∇f ◆ θ*f − f* (log) vs step1e-41e-21η₀·tr C/4step 0 … 2000all 100 gᵢ(θₜ); their mean is ∇fmax ‖gᵢ‖ = 2.433
|
t = 2000 · ηₜ = 0.1000 · f − f* = 0.003 · full GD: 5.6e-17 · path 1
example #59: gᵢ = (0.02, 0.01) vs ∇f = (-0.08, -0.04) · mean f − f* over steps 1000–2000: 0.011 (constant-η floor ≈ 0.009)
fig.SGD on a 100-example least-squares problem in two weights (κ = 9.8), 2000 steps from the open circle. Blue: SGD, one random example per step; green: full gradient descent with the same η. The lower-right panel shows all 100 per-example gradients at the current point: their mean is the full gradient (green diamond) and the orange dot is the one SGD used. Near θ* the mean is zero but the cloud is not, so SGD keeps moving. At the default η₀ = 0.1 the loss stalls around the predicted floor η·tr C/4 = 9.4·10⁻³ (dashed red; over 40 sample paths the measured mean is 1.2·10⁻²). Switch to ηₜ = η₀/(1 + t/200): the noise ball shrinks and the median excess loss at step 2000 falls to 6.6·10⁻⁴, ten times below constant η. Note that 2000 SGD steps cost the same as 20 full-GD steps, where GD is still at 0.84. Push η₀ to 0.7 and some paths diverge (9 of 40); at 1.0 all do, although full GD is stable up to 2/L = 1.46.

Worked example: three numbers

Let ℓi(θ)=12(θ−yi)2\ell_i(\theta)=\tfrac12(\theta-y_i)^2 with y=(1,2,6)y=(1,2,6). The full loss is minimized at the mean, θ∗=3\theta^*=3, and the full gradient is θ−3\theta-3. A single example's gradient is θ−yi\theta-y_i.

stepθ beforesampled yᵢgᵢ = θ − yᵢfull ∇f = θ − 3θ after
106−6−33
231202
3220−12
426−4−14
SGD with η = 0.5 from θ = 0, for one fixed sequence of sampled examples
  1. 1Step 1 happens to land exactly on θ∗=3\theta^*=3. The full gradient there is 0, so gradient descent would stop.
  2. 2Step 2 samples y=1y=1, whose gradient at θ=3\theta=3 is +2+2, and SGD walks away from the optimum to θ=2\theta=2. This is the noise ball: at θ∗\theta^* the per-example gradients (2,1,−3)(2,1,-3) average to zero but are individually large, with variance σ2=13(4+1+9)=14/3\sigma^2=\tfrac13(4+1+9)=14/3.
  3. 3For this 1-D problem the stationary spread is exact: δt+1=(1−η)δt−ηξt\delta_{t+1}=(1-\eta)\delta_t-\eta\xi_t gives Var⁡(δ)=ησ2/(2−η)\operatorname{Var}(\delta)=\eta\sigma^2/(2-\eta). With η=0.1\eta=0.1 that is 0.2460.246, so E[f−f∗]=0.123\mathbb E[f-f^*]=0.123 (a 20-million-step simulation gives 0.123). The small-η\eta formula ησ2/4=0.117\eta\sigma^2/4=0.117 is close.
  4. 4Halving η\eta to 0.050.05 roughly halves the floor (to 0.0600.060); a 1/t1/t 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 f+η4 ∥∇fB∥2‾f+\frac\eta4\,\overline{\lVert\nabla f_{\mathcal B}\rVert^2}, 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 1/B1/B, so the extra regularization relative to full-batch GD scales like η/B\eta/B. Full-batch GD has a similar but weaker implicit term (Barrett and Dherin, 2021). The noise scale η/B\eta/B is the quantity that matters, which is why learning rate and batch size have to be tuned together (see Mini-batch gradient descent).

python
1import torch, torch.nn as nn
2from torch.utils.data import DataLoader, TensorDataset
3
4X = torch.randn(1000, 2)
5y = X @ torch.tensor([1.5, -1.0]) + 0.5 * torch.randn(1000)
6model = nn.Linear(2, 1, bias=False)
7
8loader = DataLoader(TensorDataset(X, y), batch_size=1, shuffle=True) # one example per step
9opt = torch.optim.SGD(model.parameters(), lr=0.1) # plain SGD: no momentum
10tau = 200
11sched = torch.optim.lr_scheduler.LambdaLR(opt, lambda t: 1 / (1 + t / tau)) # η_t = η0/(1 + t/τ)
12
13for 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 epoch
20 print(epoch, model.weight.data, sched.get_last_lr())
21
22# 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.
True one-example SGD in PyTorch, with a Robbins–Monro schedule

Use when

  • +Cost per step independent of NN; 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 ∝η\propto\eta; 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 (O(1/t)O(1/t) 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 ∇ℓi\nabla\ell_{i} for a random example: unbiased for ∇f\nabla f, at 1/N1/N 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 ≈η4tr⁡C\approx\frac\eta4\operatorname{tr}C.
  • ✓Robbins–Monro: ∑ηt=∞\sum\eta_t=\infty, ∑ηt2<∞\sum\eta_t^2<\infty (e.g. η0/(1+t/τ)\eta_0/(1+t/\tau)) gives convergence, O(1/t)O(1/t) when strongly convex.
  • ✓Its noise acts as an implicit regularizer whose strength scales with η / batch size.
  • ✓torch.optim.SGD is the update rule; batch size 1 in the DataLoader is what makes it one-example SGD.
← back to Deep Learning roadmap