69
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ +1 for question, interestingly I had almost exact same question that about to ask ! $\endgroup$ – hxd1011 Oct 24 '16 at 14:11
  • $\begingroup$ Anecdotal evidence, but I recently fitted a one layer neural network using SGD on the MNIST data, which are 50000 in training size. After one random run-through the classification accuracy was not much higher than 30-40%, and the log-likelihood clearly had not converged. So I repeated the procedure for 30 more epochs leading to over 90% accuracy. At least by counterexample this showed to me they can be necessary. $\endgroup$ – tomka Oct 24 '16 at 14:30
  • 6
    $\begingroup$ @tomka That seems to provide evidence that multiple passes over the data are necessary, which is consistent with the method proposed here: keep drawing $k$ samples per training iteration ad nauseam. $\endgroup$ – Sycorax Oct 24 '16 at 14:36
  • 1
    $\begingroup$ Another interesting question would be: will mini batch order also has an impact on overfitting? $\endgroup$ – Kh40tiK Oct 25 '16 at 8:58
  • 3
    $\begingroup$ @Pinocchio The standard SGD practice is sampling without replacement (until the pool of samples is depleted, at which point a new epoch starts again with all the data). My question is why it does not use sampling with replacement. It turns out that one answer is that sampling without replacement improves the rate of convergence for the model. $\endgroup$ – Sycorax Jan 20 '17 at 4:34
59
$\begingroup$

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: illustration of convergence at given rates

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).

$\endgroup$
  • 3
    $\begingroup$ This is a very insightful answer. Thank you very much for your contribution. $\endgroup$ – Sycorax Oct 24 '16 at 20:19
  • 1
    $\begingroup$ sorry for the ignorance, but do you mind explaining a bit more what the difference between the three is? In particular I am confused about Random, when you say "sample", what do you mean? I know this is not what you are referencing but the standard Neural Net mini batch SGD usually samples batches without replacement at each iteration. Is that what Random does? If it is, how is that different from Shuffle? $\endgroup$ – Pinocchio Jan 20 '17 at 4:32
  • 1
    $\begingroup$ Now that I re-read it all three seem the same algorithm, whats the difference if the data set is shuffled or not and how often if the batches for SGD are always random anyway? $\endgroup$ – Pinocchio Jan 20 '17 at 4:33
  • 3
    $\begingroup$ @Pinocchio Imagine a four-lament dataset. Random might go ACADBBCA; each entry is completely random. Cycle might go BDAC BDAC BDAC; it chooses one order for each epoch and then repeats. Shuffle could be BDAC ADCB CBAD; it goes in epochs, but each one is random. This analysis doesn't use minibatches, just one-element-at-a-time SGD. $\endgroup$ – Dougal Jan 20 '17 at 11:07
  • $\begingroup$ This is a great answer. Thnx you! $\endgroup$ – DankMasterDan Jan 26 '18 at 17:22
23
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ These seem like good points, but regarding your update, it seems that sampling $k$ per epoch is dependent sampling (because the probability of a sample being seen twice in an epoch is 0). So I'm not sure how the authors can claim that the epoch construction is independent, unless their meaning of "approximately independently" is "not at all independently." $\endgroup$ – Sycorax Oct 24 '16 at 14:19
  • 1
    $\begingroup$ @Sycorax Sampling without replacement, despite of course being not independent, is "approximately independent" in the sense that it is exchangeable. From the point of view of training a classifier which doesn't care too much about any one data point, this exchangeability is definitely fairly close to "approximately independent." $\endgroup$ – Dougal Oct 24 '16 at 17:58
17
$\begingroup$

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")

binomial PMF

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.

$\endgroup$
  • 1
    $\begingroup$ I don't think it would make a large difference in practice for a large training set, but definitely I expect it would with a smaller training set. $\endgroup$ – Franck Dernoncourt Oct 24 '16 at 14:19
  • 5
    $\begingroup$ @FranckDernoncourt well, the whole point was that it can matter for large datasets if you start looking at small sub-groups. Which is not an uncommon procedure in large datasets, $\endgroup$ – dimpol Oct 24 '16 at 14:38
  • $\begingroup$ pretty sure you should have used a uniform distribution, not a binomial $\endgroup$ – lahwran Aug 23 '17 at 18:00
  • 2
    $\begingroup$ @lahwran We're sampling $10^7$ times from $10^6$ elements with replacement. In R, this would be samples = sample(1:1E6, size = 1E7, replace = TRUE). From there, you can plot the frequency distribution with plot(table(table(samples)) / 1E7). It looks just like the binomial distribution I plotted above. $\endgroup$ – David J. Harris Aug 23 '17 at 18:35
  • 2
    $\begingroup$ aha! I was wrong, then. $\endgroup$ – lahwran Aug 23 '17 at 20:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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