(Pure) Stochastic Gradient Descent

Full-batch gradient descent updates the parameters only after computing the gradient of the average loss over the entire dataset. When the dataset is large, this makes each update expensive.

The underlying idea of pure stochastic gradient descent is to replace that full gradient by the gradient of a single training example.

Using the notation introduced in Neural Networks vocabulary, let

$$\mathcal{D}={\left\{\left({\mathbf{x}}^{(i)},{\mathbf{y}}^{(i)}\right)\right\}}_{i=1}^N,$$

and suppose that the training objective is

$$\mathcal{L}(\mathbf{\theta })=\frac{1}{N}\sum _{i=1}^N{\mathcal{L}}_{{\mathbf{x}}^{(i)}}(\mathbf{\theta }),$$

where ${\mathcal{L}}_{{\mathbf{x}}^{(i)}}$ denotes the loss contribution of the single example $\left({\mathbf{x}}^{(i)},{\mathbf{y}}^{(i)}\right)$.

Note

For example, if the mean squared error is used, the loss contribution of a single training example can be written as

$${\mathcal{L}}_{{\mathbf{x}}^{(i)}}(\mathbf{\theta })=\frac{1}{2}{\Vert f_{\mathbf{\theta }}\left({\mathbf{x}}^{(i)}\right)-{\mathbf{y}}^{(i)}\Vert }^2,$$

where $f_{\mathbf{\theta }}\left({\mathbf{x}}^{(i)}\right)$ denotes the network output for the input ${\mathbf{x}}^{(i)}$.

At iteration $t$, one index $i_t\in \{1,\dots ,N\}$ is selected. This symbol denotes the index of the single training example used at optimizer step $t$. Therefore, in pure SGD, one iteration, one optimizer step, and one parameter update coincide.

In the common finite-dataset implementation, training is organized into epochs. At the beginning of epoch $e$, a random permutation ${\pi }_e$ of the index set $\{1,\dots ,N\}$ is drawn, and the examples are processed in the order

$${\pi }_e(1),{\pi }_e(2),\dots ,{\pi }_e(N).$$

If $s\in \{1,\dots ,N\}$ denotes the iteration number within epoch $e$, then the index used at the $s$-th iteration of that epoch is

$$i_t={\pi }_e(s).$$

In other words, the shuffle fixes a random order for the entire epoch, and each iteration simply takes the next example in that order. Thus, the shuffle acts before the epoch starts, while each subsequent iteration still performs exactly one SGD update based on exactly one example. After the $N$-th iteration of that epoch, one epoch has been completed.

Once $i_t$ has been determined, stochastic gradient descent feeds the corresponding example ${\mathbf{x}}^{(i_t)}$ through the network and computes the associated per-example gradient

$${\nabla }_{\mathbf{\theta }}{\mathcal{L}}_{{\mathbf{x}}^{(i_t)}}\left({\mathbf{\theta }}^{(t)}\right),$$

typically by means of backpropagation.

Why This Is A Random Vector

Fix a parameter value $\mathbf{\theta }$. The map

$$i\mapsto {\nabla }_{\mathbf{\theta }}{\mathcal{L}}_{{\mathbf{x}}^{(i)}}\left(\mathbf{\theta }\right)$$

assigns to each dataset index $i\in \{1,\dots ,N\}$ the gradient of the corresponding single-example loss. Under random sampling, $i_t$ is a random variable. Therefore

$${\nabla }_{\mathbf{\theta }}{\mathcal{L}}_{{\mathbf{x}}^{(i_t)}}\left(\mathbf{\theta }\right)$$

is random as well, because it is obtained by evaluating the above map at a random index.

It’s a random vector rather than an ordinary random variable because its value is not a single scalar: it has one coordinate for each parameter in $\mathbf{\theta }$. Each coordinate is an ordinary scalar random variable, and together those coordinates form a vector.

The parameter update is then

$${\mathbf{\theta }}^{(t+1)}={\mathbf{\theta }}^{(t)}-\eta {\nabla }_{\mathbf{\theta }}{\mathcal{L}}_{{\mathbf{x}}^{(i_t)}}\left({\mathbf{\theta }}^{(t)}\right).$$

If the compact parameter vector $\mathbf{\theta }$ is unpacked into weights and biases, this becomes

$$w_k^{(t+1)}=w_k^{(t)}-\eta \frac{\partial {\mathcal{L}}_{{\mathbf{x}}^{(i_t)}}}{\partial w_k},$$ $$b_{\ell }^{(t+1)}=b_{\ell }^{(t)}-\eta \frac{\partial {\mathcal{L}}_{{\mathbf{x}}^{(i_t)}}}{\partial b_{\ell }}.$$

These are not different learning rules: they are simply the component wise form of the same SGD update written in terms of $\mathbf{\theta }$.

Why Shuffling Matters

If the dataset is traversed in the same fixed order at every epoch, then the sequence of updates inherits that same deterministic order. When the stored examples are grouped by class, source, difficulty, or time, many consecutive gradients may point in correlated directions. The parameters may then over-adapt to one portion of the dataset and later partially undo that adaptation when a different portion is encountered.

Shuffling removes this persistent ordering effect. No example is always first, no block of similar examples is always encountered at the same stage of training, and the stochastic updates are less systematically biased by the storage order of the dataset.

If no shuffling and no other random sampling mechanism are used, then the sequence of indices $i_1,i_2,\dots$ is deterministic. In that case, the randomness discussed below is not generated by the data-order process itself.

Expectation And Unbiasedness Under Uniform Sampling

In the idealized case of uniform sampling with replacement,

$$\mathbb{P}(i_t=i)=\frac{1}{N},i=1,\dots ,N.$$

Let

$${\mathbf{G}}_t(\mathbf{\theta })={\nabla }_{\mathbf{\theta }}{\mathcal{L}}_{{\mathbf{x}}^{(i_t)}}\left(\mathbf{\theta }\right).$$

Since ${\mathbf{G}}_t(\mathbf{\theta })$ is a random vector, its expectation is taken componentwise:

$$\mathbb{E}\left[{\mathbf{G}}_t(\mathbf{\theta })\right]=(\mathbb{E}[G_{t,1}],\dots ,\mathbb{E}[G_{t,p}]),$$

where $p$ is the number of coordinates of $\mathbf{\theta }$. The expectation here is taken with respect to the random choice of the index $i_t$; the vector $\mathbf{\theta }$ simply specifies the point in parameter space at which the gradient is being evaluated.

Using the definition of expectation for a discrete random variable,

$$\mathbb{E}\left[{\nabla }_{\mathbf{\theta }}{\mathcal{L}}_{{\mathbf{x}}^{(i_t)}}\left(\mathbf{\theta }\right)\right]=\sum _{i=1}^N\mathbb{P}(i_t=i){\nabla }_{\mathbf{\theta }}{\mathcal{L}}_{{\mathbf{x}}^{(i)}}\left(\mathbf{\theta }\right).$$

Because the sampling is uniform,

$$\mathbb{E}\left[{\nabla }_{\mathbf{\theta }}{\mathcal{L}}_{{\mathbf{x}}^{(i_t)}}\left(\mathbf{\theta }\right)\right]=\frac{1}{N}\sum _{i=1}^N{\nabla }_{\mathbf{\theta }}{\mathcal{L}}_{{\mathbf{x}}^{(i)}}\left(\mathbf{\theta }\right).$$

On the other hand, since

$$\mathcal{L}(\mathbf{\theta })=\frac{1}{N}\sum _{i=1}^N{\mathcal{L}}_{{\mathbf{x}}^{(i)}}(\mathbf{\theta }),$$

linearity of differentiation gives

$${\nabla }_{\mathbf{\theta }}\mathcal{L}(\mathbf{\theta })=\frac{1}{N}\sum _{i=1}^N{\nabla }_{\mathbf{\theta }}{\mathcal{L}}_{{\mathbf{x}}^{(i)}}(\mathbf{\theta }).$$

Therefore

$$\mathbb{E}\left[{\nabla }_{\mathbf{\theta }}{\mathcal{L}}_{{\mathbf{x}}^{(i_t)}}\left(\mathbf{\theta }\right)\right]={\nabla }_{\mathbf{\theta }}\mathcal{L}(\mathbf{\theta }).$$

This is the precise sense in which the single-example gradient is an unbiased estimator of the full gradient. It does not mean that the gradient computed from the particular sampled example is itself equal to the full gradient; the equality holds only at the level of expectation over the sampling randomness.

When training is implemented by shuffling once per epoch and then traversing the permuted dataset without replacement, the same intuition remains valid, but the exact conditional expectation at a given iteration within the epoch is the average over the remaining unused examples of that epoch rather than over the whole dataset.

Because a single training example is not necessarily representative of the entire dataset, the corresponding gradient may vary substantially from one iteration to the next. As a result, the updates of the weights and biases exhibit stochastic fluctuations, and the optimization trajectory is typically less smooth than in full-batch gradient descent. At the same time, this variability can be beneficial: the sampling-induced noise may help the iterates avoid becoming trapped in poor local minima or saddle-type regions, thereby encouraging a broader exploration of the parameter space, or equivalently, of the loss landscape.

Approximate Equality In Practice

For one realized draw of the training example, one may write informally

$${\nabla }_{\mathbf{\theta }}{\mathcal{L}}_{{\mathbf{x}}^{(i_t)}}(\mathbf{\theta })\approx {\nabla }_{\mathbf{\theta }}\mathcal{L}(\mathbf{\theta }),$$

but this is only a heuristic statement. For a single example, the discrepancy may be large, because one sample need not be representative of the whole dataset. The approximation becomes exact only in expectation, or accidentally at parameter values for which the sampled-example gradient happens to coincide with the dataset-average gradient.

Tip

In much of deep-learning practice, the term “SGD” is often used loosely to include mini-batch SGD.
Strictly speaking, however, pure SGD corresponds to the case where exactly one training example is used per update.