Why error rate converges faster if the visiting order of mini-batches are changed at each epoch?

Question

I'm quoting from the paper:

As for any stochastic gradient descent method (including the mini-batch case), it is important for efficiency of the estimator that each example or minibatch be sampled approximately independently. Because random access to memory (or even worse, to disk) is expensive, a good approximation, called incremental gradient (Bertsekas, 2010), is to visit the examples (or mini-batches) in a fixed order corresponding to their order in memory or disk (repeating the examples in the same order on a second epoch, if we are not in the pure online case where each example is visited only once). In this context, it is safer if the examples or mini-batches are first put in a random order (to make sure this is the case, it could be useful to first shuffle the examples). Faster convergence has been observed if the order in which the mini-batches are visited is changed for each epoch, which can be reasonably efficient if the training set holds in computer memory.

I'm looking for intuition behind the statement (embolden) above.

Answer 1

Claim 1. When dealing with prediction, averaging different models having the same performance (in terms of your error function) improves the performance. This is due to the convexity of your loss function. As an aside, the less correlated your models are, the better is the gain you achieve averaging them.

When you train a batch model, the order of the lines does not matter. In a streaming algorithm, the order of the lines matters. Shuffling the lines and training the model on the different versions of the file will produce different results. As the model have the same parameters, they usually have comparable performance. As they are different (slightly), their average is usually better than every single algorithm.

More details about this fact can be found in the chapter 5 of "Online Learning and Online Convex Optimization", by Shai Shalev-Shwartz.

Visiting the batches in a random order somehow accomplishes the same process: it produces different weights that are averaged on every epoch.

A related question is this one : RANDOM learning rate in gradient descent. Authors claimed that multiple training epochs performed on the same data set with a randomized learning rate achieves better performance than a deterministic learning rate.