Stochastic Gradient Descent

Articles›Machine Learning›Optimization algorithms›Stochastic Gradient Descent

Topics {{#arraymap:Optimization, Neural Networks, Gradient Methods|,|@@item@@|@@item@@|}}

Languages

@@item@@

Summary

Stochastic gradient descent (SGD) is the core optimization algorithm behind modern machine learning. Instead of computing gradients over an entire dataset, it estimates them from small random samples, making training feasible on large-scale data. Nearly all deep learning models are trained using SGD or one of its variants (Adam, RMSProp, etc.).

@@item@@

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

Motivation

In classical Script error: No such module "Glossary"., the full gradient of the Script error: No such module "Glossary". 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 Script error: No such module "Glossary".) at each step, trading a noisier estimate for dramatically lower per-iteration cost.

Algorithm

Given a parameterised Script error: No such module "Glossary".

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 Script error: No such module "Glossary". (step size) and $$ i_t $$ is a randomly selected index.

Mini-batch variant

In practice a Script error: No such module "Glossary". 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 Script error: No such module "Glossary". $\eta_t$ strongly influences Script error: No such module "Glossary".. Common strategies include:

Constant — simple but may overshoot or stall.
Step decay — multiply $\eta$ by a factor (e.g. 0.1) every $$ k $$ epochs.
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 Script error: No such module "Glossary". objectives with Lipschitz-continuous gradients, SGD with a decaying Script error: No such module "Glossary". 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 deep learning — 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 step size per parameter:

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

Practical considerations

Data shuffling — Re-shuffle the dataset each epoch to avoid cyclic patterns.
Script error: No such module "Glossary". — Cap the gradient norm to prevent exploding updates, especially in recurrent networks.
Script error: No such module "Glossary". — Normalising layer inputs reduces sensitivity to the Script error: No such module "Glossary"..
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 (logistic regression, SVMs via SGD)
Reinforcement learning policy optimisation
Recommendation systems and collaborative filtering
Online learning settings where data arrives in a stream

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). "Adam: A Method for Stochastic Optimization". ICLR.
Ruder, S. (2016). "An overview of gradient descent optimization algorithms". arXiv:1609.04747.