5.3.2. Stochastic Gradient Descent

Stochastic Gradient Descent

Stochastic Gradient Descent (SGD) extends batch gradient descent by approximating the total loss function $E(w)$ with the loss of a single sampled example $L(f_w(x_i),y_i)$. This drastically reduces computational cost while maintaining an unbiased estimate of the true loss gradient. Let $P(x_{\ast },y_{\ast })$ denote the unknown probability distribution over test examples. Assuming that training data comes from the same distribution, then we can express the error function as
$E(w)=\frac{1}{N}{\sum }_{n=1}^{N}L(f_w(x_n),y_n)\to \mathbb{E}[L(f_w(x_{\ast }),y_{\ast })],$
where $L$ is the pointwise loss function, and $f_w$ is a parametric transformation on $x$ defined by parameters $w$.

In batch gradient descent, we compute the gradient over all training examples in each iteration. To decrease runtime, SGD replaces the true gradient with an unbiased estimate based on a single unformly sampled training point:
$w^{(t)}=w^{(t-1)}-\eta \nabla L(f_w^{(t-1)}(x_i),y_i),$
and runs in $O(D)$ time per iteration, since only one example contributes to the gradient. To reduce bias and improve convergence, we can iterate through the entire dataset once per epoch while shuffling the order of samples at the beginning of each epoch. Like batch gradient descent, this still processes all N samples per epoch ($O(ND)$ total), but unlike BGD - which performs a single update per epoch - SGD updates the weights after every sample. These frequent, low-cost updates allow SGD to reach low-loss regions faster in practice, even though the total computational complexity per epoch is similar.

A middle ground between the accuracy of BGD and the speed of SGD is Mini-Batch SGD, which takes a random sample $\mathcal{B}$ of data points and performs the update rule
$w^{(t)}=w^{(t-1)}-\frac{1}{B}\eta {\sum }_{b=1}^B\nabla L(f_{w^{(t-1)}}(x_{{\mathcal{B}}_b}),y_{{\mathcal{B}}_b}),$
which runs in $O(BD)$ per iteration, such that $B\ll N$. In practice, we shuffle the dataset at the beginning of each epoch, divide it into mini-batches, and perform one update per batch. Without shuffling, mini-batches may contain correlated samples, slowing or biasing convergence.