Why do neural network researchers care about epochs?

Question

An epoch in stochastic gradient descent is defined as a single pass through the data. For each SGD minibatch, $k$ samples are drawn, the gradient computed and parameters are updated. In the epoch setting, the samples are drawn without replacement.

But this seems unnecessary. Why not draw each SGD minibatch as $k$ random draws from the whole data set at each iteration? Over a large number of epochs, the small deviations of which samples are seen more or less often would seem to be unimportant.

Answer 1

In addition to Franck's answer about practicalities, and David's answer about looking at small subgroups – both of which are important points – there are in fact some theoretical reasons to prefer sampling without replacement. The reason is perhaps related to David's point (which is essentially the coupon collector's problem).

In 2009, Léon Bottou compared the convergence performance on a particular text classification problem ($n = 781,265$).

Bottou (2009). Curiously Fast Convergence of some Stochastic Gradient Descent Algorithms. Proceedings of the symposium on learning and data science. (author's pdf)

He trained a support vector machine via SGD with three approaches:

• Random: draw random samples from the full dataset at each iteration.
• Cycle: shuffle the dataset before beginning the learning process, then walk over it sequentially, so that in each epoch you see the examples in the same order.
• Shuffle: reshuffle the dataset before each epoch, so that each epoch goes in a different order.

He empirically examined the convergence $\mathbb E[ C(\theta_t) - \min_\theta C(\theta) ]$, where $C$ is the cost function, $\theta_t$ the parameters at step $t$ of optimization, and the expectation is over the shuffling of assigned batches.

• For Random, convergence was approximately on the order of $t^{-1}$ (as expected by existing theory at that point).
• Cycle obtained convergence on the order of $t^{-\alpha}$ (with $\alpha > 1$ but varying depending on the permutation, for example $\alpha \approx 1.8$ for his Figure 1).
• Shuffle was more chaotic, but the best-fit line gave $t^{-2}$, much faster than Random.

This is his Figure 1 illustrating that:

This was later theoretically confirmed by the paper:

Gürbüzbalaban, Ozdaglar, and Parrilo (2015). Why Random Reshuffling Beats Stochastic Gradient Descent. arXiv:1510.08560. (video of invited talk at NIPS 2015)

Their proof only applies to the case where the loss function is strongly convex, i.e. not to neural networks. It's reasonable to expect, though, that similar reasoning might apply to the neural network case (which is much harder to analyze).

Answer 2

It is indeed quite unnecessary from a performance standpoint with a large training set, but using epochs can be convenient, e.g.:

• it gives a pretty good metric: "the neural network was trained for 10 epochs" is a clearer statement than "the neural network was trained for 18942 iterations" or "the neural network was trained over 303072 samples".
• there's enough random things going on during the training phase: random weight initialization, mini-batch shuffling, dropout, etc.
• it is easy to implement
• it avoids wondering whether the training set is large enough not to have epochs

---

[1] gives one more reason, which isn't that much relevant given today's computer configuration:

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.

---

[1] Bengio, Yoshua. "Practical recommendations for gradient-based training of deep architectures." Neural Networks: Tricks of the Trade. Springer Berlin Heidelberg, 2012. 437-478.

Answer 3

I disagree somewhat that it clearly won't matter. Let's say there are a million training examples, and we take ten million samples.

In R, we can quickly see what the distribution looks like with

plot(dbinom(0:40, size = 10 * 1E6, prob = 1E-6), type = "h")

Some examples will be visited 20+ times, while 1% of them will be visited 3 or fewer times. If the training set was chosen carefully to represent the expected distribution of examples in real data, this could have a real impact in some areas of the data set---especially once you start slicing up the data into smaller groups.

Consider the recent case where one Illinois voter effectively got oversampled 30x and dramatically shifted the model's estimates for his demographic group (and to a lesser extent, for the whole US population). If we accidentally oversample "Ruffed Grouse" images taken against green backgrounds on cloudy days with a narrow depth of field and undersample the other kinds of grouse images, the model might associate those irrelevant features with the category label. The more ways there are to slice up the data, the more of these subgroups there will be, and the more opportunities for this kind of mistake there will be.