Stochastic Gradient Descent

Article
Topic area	Machine Learning
Difficulty	Intermediate
Prerequisites	Gradient Descent, Linear Regression

Stochastic gradient descent (often abbreviated ) is an iterative optimisation algorithm used to minimise an written as a sum of differentiable sub-functions. It is the workhorse behind modern machine-learning training, powering everything from to deep neural networks.

Motivation

In classical , the full gradient of the is computed over the entire training set before each parameter update. When the dataset is large this becomes prohibitively expensive. SGD addresses the problem by estimating the gradient from a single randomly chosen sample (or a small ) at each step, trading a noisier estimate for dramatically lower per-iteration cost.

Algorithm

Given a parameterised

$ L(\theta) = \frac{1}{N}\sum_{i=1}^{N} \ell(\theta;\, x_i,\, y_i) $

the SGD update rule at step $ t $ is:

$ \theta_{t+1} = \theta_t - \eta_t \,\nabla_\theta \ell(\theta_t;\, x_{i_t},\, y_{i_t}) $

where $ \eta_t $ is the () and $ i_t $ is a randomly selected index.

Mini-batch variant

In practice a of $ B $ samples is used:

$ \theta_{t+1} = \theta_t - \frac{\eta_t}{B}\sum_{j=1}^{B} \nabla_\theta \ell(\theta_t;\, x_{i_j},\, y_{i_j}) $

Common batch sizes range from 32 to 512. Larger batches reduce gradient variance but increase memory usage.

Pseudocode

initialise parameters θ
for epoch = 1, 2, … do
    shuffle training set
    for each mini-batch B ⊂ training set do
        g ← (1/|B|) Σ ∇ℓ(θ; xᵢ, yᵢ)   # estimate gradient
        θ ← θ − η · g                     # update parameters
    end for
end for

Learning rate schedules

The $ \eta_t $ strongly influences . Common strategies include:

• Constant — simple but may overshoot or stall.
• Step decay — multiply $ \eta $ by a factor (e.g. 0.1) every $ k $ .
• Exponential decay — $ \eta_t = \eta_0 \, e^{-\lambda t} $.
• Cosine annealing — smoothly reduces the rate following a cosine curve, often with warm restarts.
• Linear warm-up — ramp up from a small $ \eta $ during the first few iterations to stabilise early training.

Convergence properties

For objectives with Lipschitz-continuous gradients, SGD with a decaying satisfying

$ \sum_{t=1}^{\infty} \eta_t = \infty, \qquad \sum_{t=1}^{\infty} \eta_t^2 < \infty $

converges almost surely to the global minimum (Robbins–Monro conditions). For non-convex problems — the typical regime for — SGD converges to a stationary point, and empirical evidence shows it often finds good local minima.

Popular variants

Several extensions reduce the variance of the gradient estimate or adapt the per parameter:

Method	Key idea	Reference
	Accumulates an exponentially decaying moving average of past gradients	Polyak, 1964
Nesterov accelerated gradient	Evaluates the gradient at a "look-ahead" position	Nesterov, 1983
	Per-parameter rates that shrink for frequently updated features	Duchi et al., 2011
RMSProp	Fixes 's diminishing rates using a moving average of squared gradients	Hinton (lecture notes), 2012
	Combines with RMSProp-style adaptive rates	Kingma & Ba, 2015
AdamW	Decouples from the adaptive gradient step	Loshchilov & Hutter, 2019

Practical considerations

• Data shuffling — Re-shuffle the dataset each to avoid cyclic patterns.
• — Cap the gradient norm to prevent exploding updates, especially in recurrent networks.
• — Normalising layer inputs reduces sensitivity to the .
• Mixed-precision training — Using half-precision floats accelerates SGD on modern GPUs with minimal accuracy loss.

Applications

SGD and its variants are used across virtually all areas of machine learning:

• Training deep neural networks (computer vision, NLP, speech recognition)
• Large-scale linear models (, SVMs via SGD)
• Reinforcement learning policy optimisation
• and collaborative filtering
• Online learning settings where data arrives in a stream

See also

• Gradient descent
• Backpropagation
• Adam (optimiser)
• Learning rate
• Convex optimisation

References

• Robbins, H. and Monro, S. (1951). "A Stochastic Approximation Method". Annals of Mathematical Statistics.
• Bottou, L. (2010). "Large-Scale Machine Learning with Stochastic Gradient Descent". COMPSTAT.
• Kingma, D. P. and Ba, J. (2015). ": A Method for Stochastic Optimization". ICLR.
• Ruder, S. (2016). "An overview of optimization algorithms". arXiv:1609.04747.