# stochastic gradient descent (SGD)

*Entry of the [Dictionary of Applied Machine Learning](https://dictionaryofml.org) (course edition), by Alexander Jung, Aalto University. CC BY 4.0. Updated 2026-11-03. [HTML](https://dictionaryofml.org/terms/stochGD.html) · [typeset PDF](https://dictionaryofml.org/terms/stochGD.pdf) · [LaTeX](https://dictionaryofml.org/terms/stochGD.tex) · [Python demo](https://dictionaryofml.org/terms/stochGD.py) · [notebook](https://dictionaryofml.org/terms/stochGD.ipynb)*

Math is LaTeX with the book's macros expanded, so no notation package is needed to read it.

## Abstract

Stochastic gradient descent (SGD) is a variant of gradient descent in which the gradient of the objective function is replaced by a computationally cheaper stochastic approximation. Its main application in machine learning is empirical risk minimization 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

Consider the training set of Fig. 1: twelve weather stations, each contributing one data point with the minimum temperature of a day as feature and its maximum temperature as label, stored on two servers, one of GeoSphere Austria and one of the Finnish Meteorological Institute. The training set holds $m$ data points. Linear regression learns a linear hypothesis from it, so that its predictions match the labels. That amounts to finding the minimum of a differentiable convex objective function, the empirical risk

$$
f({\mathbf w}) := \frac{1}{m}
\sum_{r=1}^{m}
L\left({\mathbf z}^{(r)},{\mathbf w} \right) \text{.}
$$

The training set is $\mathcal{D}^{(\rm train)} = \big\{ {\mathbf z}^{(1)}, \ldots,
{\mathbf z}^{(m)} \big\}$, and each data point ${\mathbf z}^{(r)}$ is a feature vector together with its label. Here, $L\left({\mathbf z}^{(r)},{\mathbf w} \right)$ is the loss that the hypothesis with model parameters ${\mathbf w}$ incurs on ${\mathbf z}^{(r)}$.

Gradient descent searches for a minimum of a differentiable convex function by repeating the gradient step

$$
{\mathbf w}^{(t+1)} = {\mathbf w}^{(t)}
- \eta^{(t)} \nabla f({\mathbf w}^{(t)})
\text{,}
$$

with a step size $\eta^{(t)} > 0$ that is small enough for each step to decrease $f$ (see gradient descent). The gradient of the above objective function is $\nabla f({\mathbf w}) = \frac{1}{m}
\sum_{r=1}^{m} \nabla_{{\mathbf w}}
L\left({\mathbf z}^{(r)},{\mathbf w} \right)$, an average with one term per data point. Its exact evaluation therefore requires a pass over the entire training set, which is computationally expensive when $m$ is large. SGD instead uses the cheaper estimate

$$
g({\mathbf w}) := \frac{1}{B}
\sum_{r \in \mathcal{B}} \nabla_{{\mathbf w}}
L\left({\mathbf z}^{(r)},{\mathbf w} \right) \text{,}
$$

the average of the same terms over a batch $\mathcal{B} \subseteq \{1, \ldots, m\}$ of $B = |\mathcal{B}|$ indices chosen uniformly at random (see Fig. 1).

![Figure 1 of the entry stochGD](https://dictionaryofml.org/terms/fig/stochGD-fig1.svg)

*Figure 1: A training set of $m = 12$ data points: each is the daily minimum temperature (feature $x$) and daily maximum temperature (label $y$) observed on 1 July 2026 at a different weather station, stored on two servers, at Geosphere.at (filled circles) and FMI.fi (filled squares). The dotted vertical segments are the prediction errors of a linear hypothesis map $h$ (solid curve). A gradient descent update of the model parameters ${\mathbf w}$ uses the prediction errors of all $m$ data points; an SGD update uses only those of a randomly chosen batch $\mathcal{B}$ (inside red rings). 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 $\mathcal{B}^{(t)}$ and performs the gradient descent update with the stochastic estimate in place of the gradient (see Fig. 2). The update reads

$$
{\mathbf w}^{(t+1)} = {\mathbf w}^{(t)}
- \eta^{(t)} \frac{1}{B}
\sum_{r \in \mathcal{B}^{(t)}} \nabla_{{\mathbf w}}
L\left({\mathbf z}^{(r)},{\mathbf w}^{(t)} \right)
\text{,}
$$

with a step size $\eta^{(t)} > 0$. For a uniformly drawn batch, the expectation of the update is the gradient descent step ${\mathbf w} \mapsto {\mathbf w} - \eta^{(t)}
\nabla f({\mathbf w})$. The fixed points of that step are the points satisfying the zero-gradient condition $\nabla f({\mathbf w}) = \mathbf{0}$. One classical set of sufficient conditions for the convergence of such random iterations to a minimum of $f$ comes from stochastic approximation (Robbins and Monro, 1951). The step sizes must diminish such that $\sum_{t=1}^{\infty} \eta^{(t)} = \infty$ while $\sum_{t=1}^{\infty} \big(\eta^{(t)}\big)^{2}
< \infty$ (Bertsekas, 2016, Sect. 2.4.1).

![Figure 2 of the entry stochGD](https://dictionaryofml.org/terms/fig/stochGD-fig2.svg)

*Figure 2: SGD as gradient descent on an approximation of the objective function: the empirical risk, the average loss over all $m$ data points of the training set (solid curve), and the average over one randomly drawn batch $\mathcal{B}$ (dashed curve). The gradient of the dashed curve is the stochastic estimate that SGD uses in place of the gradient of the solid one*

The batch size $B$ is the parameter of SGD that sets the cost and the noise of one update: $B = m$ recovers gradient descent, while $B = 1$ updates with the gradient of a single data point and yields the noisiest estimate. SGD with $1 < B < m$ is mini-batch SGD (Bottou, 1999). Each update costs $B$ gradient evaluations instead of $m$. That lower cost is what makes empirical risk minimization on a large training set feasible, which is the main application of SGD in machine learning. The update is noisier than a gradient step, and its variance shrinks as the batch grows (Bottou, 2010). A larger batch draws the dashed curve of Fig. 2 closer to the solid one. At $B = m$, the two coincide; at $B = 1$, they lie furthest apart.

When the training set is spread over several servers, as in Fig. 1, a batch can be drawn from one server at a time, so no server needs the whole training set.

**See also:** [gradient descent](https://dictionaryofml.org/terms/gd.html), gradient-based method, [gradient](https://dictionaryofml.org/terms/gradient.html), [empirical risk minimization](https://dictionaryofml.org/terms/erm.html), batch, step size, objective function, zero-gradient condition, online gradient descent.

## References

- Robbins and Monro (1951). A Stochastic Approximation Method. *The Annals of Mathematical Statistics*. <https://doi.org/10.1214/aoms/1177729586>
- Bertsekas (2016). Nonlinear Programming. *Athena Scientific*.
- Bottou (1999). On-line learning and stochastic approximations. *On-Line Learning in Neural Networks*.
- Bottou (2010). Large-scale machine learning with stochastic gradient descent. *Proceedings of COMPSTAT'2010*. <https://doi.org/10.1007/978-3-7908-2604-3_16>

## Cite this entry

```bibtex
@misc{dictml_stochGD,
  author = {Jung, Alexander},
  editor = {Olioumtsevits, Konstantina and Schnoor, Ekkehard},
  title = {stochastic gradient descent (SGD)},
  howpublished = {Dictionary of Applied Machine Learning (course edition)},
  year = {2026},
  doi = {10.5281/zenodo.21569296},
  note = {ISBN 978-952-64-3013-3, CC BY 4.0, retrieved 2026-11-04},
  url = {https://dictionaryofml.org/terms/stochGD.html}
}
```