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 beneﬁt due to decreased training error to oﬀset 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?