How does SGD training error decrease in subsequent epochs when statistically, it requires that samples in subsequent epochs be i.i.d and they are not?

Question

I have been reading the Deep Learning book by Ian Goodfellow and on pg. 277, they mention:

It is also crucial that the minibatches be selected randomly. Computing an unbiased estimate of the expected gradient from a set of samples requires that those samples be independent. We also wish for two subsequent gradient estimates to be independent from each other, so two subsequent minibatches of examples should also be independent from each other

I understand that for any unbiased estimation we require the samples to be i.i.d. so that we ideally end up with a true representation of the underlying data and so the above statement makes sense. However in practice, the samples that SGD sees for the subsequent gradient update (the next epoch) are the same, and it still performs well in the sense that the training error decreases. The authors later mention :

...but of course, the additional epochs usually provide enough benefit due to decreased training error to offset the harm they cause by increasing the gap between training error and test error

I know this happens but if someone could explain to me why and how it happens perhaps from a statistical perspective, it would be great! Another way to put it: why does training error in SGD decrease in subsequent epochs even though the samples are not i.i.d anymore?

Answer 1

The samples might be the same in each epoch, but, before starting the new epoch, the training dataset might be randomly shuffled before splitting it into mini-batches (this is the default behaviour in Keras), which helps to de-correlate the samples.

For example, suppose that your training data consists of $D =\{4, 2, 3, 1, 5, 0 \}$. Now, you decide to perform mini-batch GD with batch size $m = 2$. You also shuffle the training data before each epoch, so before splitting the training data into mini-batches. In the first epoch, you could have batches $B_1 = \{3, 0 \}$, $B_2 = \{4, 5 \}$ and $B_3 = \{2, 1 \}$. In the second epoch, we could have $B_1 = \{4, 1 \}$, $B_2 = \{3, 0 \}$ and $B_3 = \{5, 2 \}$, and so on. So, if there was any spurious/noisy information associated with some specific order of the samples, this would unlikely bias the computation of the gradient.

This should give you some intuition about why shuffling might help to avoid the introduction of any bias due to some specific order of the samples.