2
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – yasin.yazici
    Oct 7, 2015 at 13:52
  • $\begingroup$ Updated, I tried to make things clearer $\endgroup$
    – RUser4512
    Oct 7, 2015 at 14:54
  • $\begingroup$ 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. $\endgroup$
    – yasin.yazici
    Oct 7, 2015 at 17:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.