Skip to content
Tutorials Center
My learning

Topics

Lesson 30 of 38 · Proximal and Stochastic Methods

Stochastic Gradient Descent

Learn why SGD uses one sample or a mini-batch per step, how batch size and learning rate change its path, and why a decaying step size is needed for exact convergence.

Training objectives in machine learning are usually sums over data:

Text
F(w) = (1/N) Σ_{i=1..N} f_i(w)

where f_i is the loss on sample i. A full gradient needs all N samples: ∇F(w) = (1/N) Σ ∇f_i(w). When N is millions, one step is expensive. Stochastic gradient descent (SGD) replaces the full gradient by the gradient of a few randomly chosen samples:

Text
w ← w − η · ∇f_i(w)        (i chosen at random)

The key fact: the expected value of ∇f_i(w) over a uniformly random i equals ∇F(w). A stochastic gradient is an unbiased estimate of the true gradient, noisy but cheap.

Mini-batches

In practice, you average over a small batch B of samples:

Text
w ← w − η · (1/|B|) Σ_{i ∈ B} ∇f_i(w)
  • Batch size 1 is the classic SGD: cheapest step, noisiest path.
  • Batch size N is full gradient descent: no noise, costliest step.
  • In between (32, 128, 512) is the usual compromise. The noise variance falls like 1/|B|, and vectorized hardware makes a batch nearly as cheap as one sample.

One pass through all the data is called an epoch.

SGD for least squares

Take linear regression with f_i(w) = ½ (x_iᵀw − y_i)². The sample gradient is x_i (x_iᵀw − y_i). In this example, we generate 2,000 samples from a known weight vector plus noise, then run SGD with different batch sizes. We measure the distance to the exact least-squares solution w_ls (from np.linalg.lstsq), not to the generating weights, since noise shifts the true optimum.

Python Mini-batch SGD with different batch sizes

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

All four runs see the same amount of data (5 epochs), but the learning rates differ, so this is a rough picture, not a fair race. Batch 100 ended closest. Batch sizes 1 and 10 make many more updates, but each is noisy, so they hover around the solution. Full-batch descent makes only 5 steps in 5 epochs and has barely started.

The noise floor and decaying step sizes

With a constant step η, SGD does not settle on the exact minimizer. Each step adds noise from the sampled gradient, so the iterates keep jittering in a ball around the optimum. A bigger η means a bigger ball; a smaller η means a smaller ball but slower progress.

The remedy is a decaying step size, such as η_k = η₀ / (1 + k/τ). Early on the step is large and makes quick progress. Later the step shrinks, so the noise fades. For convex problems, the classical conditions are Σ η_k = ∞ and Σ η_k² < ∞ (for example η_k ∝ 1/k), which let the iterates converge to the optimum.

Python Constant versus decaying step size

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The constant-step distance stays at a noisy level (roughly 0.1 to 0.25 in the run above), while the decaying-step distance tends to shrink and ends about ten times smaller. Neither column is perfectly smooth, because every single-sample step is random.

In practice, deep-learning training often uses a schedule that drops the learning rate in stages, or a smooth cosine decay, for the same reason: big steps first, careful steps at the end.

Why SGD is attractive

  • Cost per step is independent of N. Optimizing over a billion samples costs the same per step as over a thousand.
  • Early progress is fast. The gradient of a few samples already points roughly downhill, so most improvement happens in the first epochs.
  • Noise helps in non-convex problems (neural networks): it can help escape shallow traps.

Its weaknesses are the noise floor, the need to tune η, and slow final convergence compared with full-batch second-order methods. Variants such as momentum and Adam, covered next, address some of these.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. Why is the gradient of a randomly sampled f_i a valid replacement for the full gradient?

    Averaging over the random choice of i gives (1/N)Σ∇f_i, exactly ∇F. So on average the step points the right way.
  2. 2. What does increasing the batch size do to the gradient noise?

    Averaging more independent samples shrinks the variance of the estimate.
  3. 3. With a constant learning rate, where do SGD iterates end up on a convex problem with noisy samples?

    Sampling noise never vanishes, so a constant step leaves a residual error that scales with η.
  4. 4. Which step-size rule gives convergence to the exact optimum for convex problems?

    The steps must stay large enough in total to travel anywhere, yet shrink fast enough that the noise averages out.

Summary

  • SGD replaces ∇F by the gradient on a random sample or mini-batch; the estimate is unbiased.
  • Larger batches cut the variance; smaller batches make more updates per epoch.
  • A constant step size leaves a noise floor; a decaying schedule removes it.
  • Cost per step does not depend on dataset size, which is why SGD powers large-scale learning.

Next: Momentum, Nesterov and Adam