Python demo — a script that recomputes what this entry states and prints one line per check
Stochastic gradient descent (SGD) is a variant of gradient descent (GD)
in which the gradient of the objective function is replaced by a
computationally cheaper stochastic approximation. Its main
application in machine learning (ML) is empirical risk minimization (ERM) on a training set that is
large or stored in a distributed database: the gradient of
the empirical risk requires an average over the
entire training set. SGD approximates this average by the
average over a randomly drawn batch of data points.
The batch size trades the computational cost of a single
update against the accuracy of the gradient
approximation.
Definition
B-weatherConsider an
artificial intelligence system (AI system) that uses logistic regression to learn an image
classifier. Logistic regression amounts to finding the minimum
of a differentiable convex objective function, the
empirical risk
\[
f(\weights) \defeq \frac{1}{\samplesize}
\sum_{\sampleidx=1}^{\samplesize}
\lossfunc{\datapoint^{(\sampleidx)}}{\weights} \text{.}
\]
Here, $\lossfunc{\datapoint^{(\sampleidx)}}{\weights}$ denotes
the loss incurred on the data point
$\datapoint^{(\sampleidx)}$ of a training set
$\trainset = \big\{ \datapoint^{(1)}, \ldots,
\datapoint^{(\samplesize)} \big\}$ by the hypothesis with
model parameters $\weights$, and $\samplesize$ is the number of
data points in the training set. Gradient descent (GD) minimizes a
differentiable convex function by taking a
sufficient number of gradient steps,
\[
\weights^{(\iteridx+1)} = \weights^{(\iteridx)}
- \lrate^{(\iteridx)} \nabla f(\weights^{(\iteridx)})
\text{,}
\]
with a step size $\lrate^{(\iteridx)} > 0$. The
gradient of the above objective function is
$\nabla f(\weights) = \frac{1}{\samplesize}
\sum_{\sampleidx=1}^{\samplesize} \nabla_{\weights}
\lossfunc{\datapoint^{(\sampleidx)}}{\weights}$, an average
with one term per data point, so its exact evaluation
requires a pass over the entire training set. SGD instead uses
the estimate
\[
g(\weights) \defeq \frac{1}{\batchsize}
\sum_{\sampleidx \in \batch} \nabla_{\weights}
\lossfunc{\datapoint^{(\sampleidx)}}{\weights} \text{,}
\]
the same average over a batch
$\batch \subseteq \{1, \ldots, \samplesize\}$ of
$\batchsize = |\batch|$ indices chosen uniformly at random
(see Fig. 1).
Figure 1: A training set of $\samplesize = 12$
data points: each is the daily minimum temperature
(feature $\feature$) and daily maximum temperature
(label $\truelabel$) observed on 1 July 2026 at a
different weather station, stored on the two servers
Geosphere.at (filled circles) and FMI.fi
(filled squares). The dotted vertical segments are the
prediction errors of a linear hypothesis map
$\hypothesis(\feature)$ (solid line). A GD update of the
model parameters $\weights$ uses the prediction errors of
all $\samplesize$ data points; an SGD update uses only
those of a randomly chosen batch $\batch$ (circled).
Data generated by pythondemos/stochGD.py, which
downloads the observations from the open data services of
GeoSphere Austria and the Finnish Meteorological Institute
Each SGD iteration generates a new batch
$\batch^{(\iteridx)}$ and performs the GD update with the
estimate in place of the gradient,
\[
\weights^{(\iteridx+1)} = \weights^{(\iteridx)}
- \lrate^{(\iteridx)} \frac{1}{\batchsize}
\sum_{\sampleidx \in \batch^{(\iteridx)}} \nabla_{\weights}
\lossfunc{\datapoint^{(\sampleidx)}}{\weights^{(\iteridx)}}
\text{,}
\]
with a step size $\lrate^{(\iteridx)} > 0$; only the
gradient estimate differs from GD
(see Fig. 2). The update is a
random instance of the GD operator: for a uniformly drawn
batch, its expectation is the GD step
$\weights \mapsto \weights - \lrate^{(\iteridx)}
\nabla f(\weights)$, whose fixed points are the points
satisfying the zero-gradient condition
$\nabla f(\weights) = \mathbf{0}$. Conditions under which such
random iterations converge go back to stochastic
approximation (Robbins and Monro, 1951): the step sizes
must diminish such that
$\sum_{\iteridx=1}^{\infty} \lrate^{(\iteridx)} = \infty$ while
$\sum_{\iteridx=1}^{\infty} \big(\lrate^{(\iteridx)}\big)^{2}
< \infty$ (Bertsekas, 2016, Sect. 2.4.1).
B-approxThe batch size $\batchsize$ is an important
parameter of SGD: $\batchsize = \samplesize$ recovers
GD, while $\batchsize = 1$ updates with the gradient
of a single data point and yields the noisiest estimate.
SGD with $1 < \batchsize < \samplesize$ is mini-batch SGD
(Bottou, 1999). Each update costs $\batchsize$ gradient
evaluations instead of $\samplesize$, which is what makes
empirical risk minimization (ERM) on large training sets feasible; the price is noise
in the update, whose variance shrinks as the batch grows
(Bottou, 2010).
Figure 2: SGD as GD on an approximation of the
objective function: the empirical risk,
the average loss over all $\samplesize$ data points
of the training set (solid), and the average over one randomly
drawn batch $\batch$ (dashed). The gradient of the
dashed curve is the stochastic estimate that SGD uses in
place of the gradient of the solid one
See also: GD, gradient-based method, gradient, ERM,
batch, step size, objective function,
zero-gradient condition, online gradient descent (online GD).
References
Robbins and Monro (1951). A Stochastic Approximation Method. The Annals of Mathematical Statistics.
