# 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.

Source: https://www.mlfoundry.in/learn/stochastic-gradient-descent-sgd  
Section: Deep Learning › Optimization Algorithms  
Level: core · 11 min read · updated 2026-10-11

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

$$
\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)
$$

- $i_t$: index drawn uniformly at random at step $t$ (in practice: the next example of a shuffled epoch)
- $g_t$: stochastic gradient: the gradient of a single example's loss
- $\eta_t$: step size at step t; constant or decaying
- $\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 $\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 $f$ with Hessian $H$ and gradient-noise covariance $C=\Sigma(\theta^*)$ at the optimum, the stationary spread of the iterates satisfies $H\Sigma_\theta+\Sigma_\theta H\approx\eta\,C$ for small $\eta$, and taking the trace gives the size of the floor:

$$
\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
$$

- $\operatorname{tr}C$: total variance of a one-example gradient at the optimum, where the mean gradient is zero
- $\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

$$
\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}
$$

- $\sum\eta_t=\infty$: the steps must add up to an unbounded distance, so the iterate can reach the optimum from anywhere
- $\sum\eta_t^2<\infty$: the accumulated noise (variance $\propto\sum\eta_t^2$) stays finite, so the wandering dies out
- $\tau$: how many steps before the decay starts to bite

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

**SGD at a glance**

- **Cost per step:** one example: $1/N$ of a full gradient
- **Gradient:** unbiased: $\mathbb E[g_t]=\nabla f(\theta_t)$; variance $\operatorname{tr}\Sigma(\theta)$ does not vanish at $\theta^*$
- **Constant η:** fast linear phase, then a floor $\approx\frac\eta4\operatorname{tr}C$
- **Decaying η:** converges if $\sum\eta_t=\infty$, $\sum\eta_t^2<\infty$; $O(1/t)$ when strongly convex
- **Stability:** set by the curvature of single examples, not just $L$: 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

> Figure: 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 $\ell_i(\theta)=\tfrac12(\theta-y_i)^2$ with $y=(1,2,6)$. The full loss is minimized at the mean, $\theta^*=3$, and the full gradient is $\theta-3$. A single example's gradient is $\theta-y_i$.

SGD with η = 0.5 from θ = 0, for one fixed sequence of sampled examples

| 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 |

1. Step 1 happens to land exactly on $\theta^*=3$. The full gradient there is 0, so gradient descent would stop.
2. Step 2 samples $y=1$, whose gradient at $\theta=3$ is $+2$, and SGD walks away from the optimum to $\theta=2$. This is the noise ball: at $\theta^*$ the per-example gradients $(2,1,-3)$ average to zero but are individually large, with variance $\sigma^2=\tfrac13(4+1+9)=14/3$.
3. For this 1-D problem the stationary spread is exact: $\delta_{t+1}=(1-\eta)\delta_t-\eta\xi_t$ gives $\operatorname{Var}(\delta)=\eta\sigma^2/(2-\eta)$. With $\eta=0.1$ that is $0.246$, so $\mathbb E[f-f^*]=0.123$ (a 20-million-step simulation gives 0.123). The small-$\eta$ formula $\eta\sigma^2/4=0.117$ is close.
4. Halving $\eta$ to $0.05$ roughly halves the floor (to $0.060$); a $1/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+\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/B$, so the extra regularization relative to full-batch GD scales like $\eta/B$. Full-batch GD has a similar but weaker implicit term (Barrett and Dherin, 2021). The noise scale $\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
import torch, torch.nn as nn
from torch.utils.data import DataLoader, TensorDataset

X = torch.randn(1000, 2)
y = X @ torch.tensor([1.5, -1.0]) + 0.5 * torch.randn(1000)
model = nn.Linear(2, 1, bias=False)

loader = DataLoader(TensorDataset(X, y), batch_size=1, shuffle=True)   # one example per step
opt = torch.optim.SGD(model.parameters(), lr=0.1)                      # plain SGD: no momentum
tau = 200
sched = torch.optim.lr_scheduler.LambdaLR(opt, lambda t: 1 / (1 + t / tau))  # η_t = η0/(1 + t/τ)

for epoch in range(3):
    for xb, yb in loader:
        opt.zero_grad()
        loss = 0.5 * (model(xb).squeeze(-1) - yb).pow(2).mean()
        loss.backward()
        opt.step()
        sched.step()                 # once per update, not once per epoch
    print(epoch, model.weight.data, sched.get_last_lr())

# torch.optim.SGD itself is just θ ← θ − lr·(grad + weight_decay·θ), optionally with momentum.
# The "stochastic" part is entirely in which examples produced the gradient.
```

True one-example SGD in PyTorch, with a Robbins–Monro schedule

> **A noisy loss curve is not a broken one:** Per-step SGD losses jump around by design, and the training loss plateaus at the noise floor with a constant learning rate. Judge progress by a moving average or by the full training/validation loss evaluated every so often. A plateau that ends when you decay the learning rate was the noise ball, not a bad minimum.

> **Single examples have their own curvature:** Stability for SGD is not just $\eta<2/L$. One example with a large input norm has curvature $\lVert x_i\rVert^2$ far above the average, and a step on it overshoots. In the figure full GD is stable up to 1.46, yet SGD paths start to diverge around $\eta=0.7$. Normalized inputs, gradient clipping and mini-batches all reduce this risk.

> **Why cheap and noisy beats exact:** In the figure, 2000 SGD steps (20 epochs of compute) bring the excess loss to about $10^{-2}$; the same compute buys full GD 20 steps and an excess loss of 0.84. Redundant data make the stochastic gradient almost as informative as the full one at $1/N$ of the price. The exact gradient wins only when you need precision below the noise floor.

**Strengths**

- Cost per step independent of $N$; 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

**Limitations**

- 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)$ at best) compared with full GD's linear rate

**Question:** 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?

- A. The floor halves, and reaching it takes about twice as many steps
- B. The floor stays the same, but is reached faster
- C. The floor drops to zero
- D. Nothing changes: the floor is set by the data alone

**Answer:** A. The floor halves, and reaching it takes about twice as many steps — The stationary excess loss is about $\frac\eta4\operatorname{tr}C$, proportional to $\eta$. The contraction toward it happens at rate about $1-\eta\mu$ per step, so a smaller $\eta$ also approaches more slowly. Decaying $\eta$ over time gets the speed of a large step early and the small floor late.

**Question:** Which pair of step-size sequences both satisfy the Robbins–Monro conditions?

- A. ηₜ = 0.1 and ηₜ = 1/t²
- B. ηₜ = 1/t and ηₜ = 1/t^0.75
- C. ηₜ = 1/√t and ηₜ = 1/t
- D. ηₜ = 1/t² and ηₜ = 1/t

**Answer:** B. ηₜ = 1/t and ηₜ = 1/t^0.75 — Need $\sum\eta_t=\infty$ and $\sum\eta_t^2<\infty$. $1/t$: harmonic sum diverges, $\sum1/t^2$ converges. $1/t^{0.75}$: $\sum$ diverges, $\sum1/t^{1.5}$ converges. A constant violates the second condition, $1/t^2$ the first, and $1/\sqrt t$ the second ($\sum1/t$ diverges).

**Key points**

- SGD steps on $\nabla\ell_{i}$ for a random example: unbiased for $\nabla f$, at $1/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 $\approx\frac\eta4\operatorname{tr}C$.
- Robbins–Monro: $\sum\eta_t=\infty$, $\sum\eta_t^2<\infty$ (e.g. $\eta_0/(1+t/\tau)$) gives convergence, $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.

---

From MLFoundry (https://www.mlfoundry.in). The web page adds interactive figures and diagrams.
