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

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.

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.

• I couldn't exactly understand what you mean. There is only single model (not different models and their average ) that is learning via mini-batches, and I can see no reason why visiting mini-batches at different orders at each epoch prone to better results. I know they may produces different results but I see no correlation between changing the order and producing better results. I've checked the fifth chapter but didn't understand much thing. Commented Oct 7, 2015 at 13:52
• Updated, I tried to make things clearer Commented Oct 7, 2015 at 14:54
• I'm aware of model averaging that you mention about but still counld't get the relation with mini-batch visiting order of stochastic gradient descent. The quoted part means the same model continues to learn at each epoch with different mini-batch order. So I can see no averaging or averaging effect. So I agree your first claim and what you said in the second paragraph, but see no connection between them. Commented Oct 7, 2015 at 17:03