Answers.Body: <p>The samples might be the same in each epoch, but, before starting the new epoch, the training dataset might be <strong>randomly shuffled</strong> before splitting it into mini-batches (this is the <a href="https://www.tensorflow.org/api_docs/python/tf/keras/Model#fit" rel="nofollow noreferrer">default behaviour in Keras</a>), which helps to de-correlate the samples.</p>
  <p>For example, suppose that your training data consists of <span class="math-container">$D =\{4, 2, 3, 1, 5, 0 \}$</span>. Now, you decide to perform mini-batch GD with batch size <span class="math-container">$m = 2$</span>. You also shuffle the training data before each epoch, so before splitting the training data into mini-batches. In the first epoch, you could have batches <span class="math-container">$B_1 = \{3, 0 \}$</span>, <span class="math-container">$B_2 = \{4, 5 \}$</span> and <span class="math-container">$B_3 = \{2, 1 \}$</span>. In the second epoch, we could have <span class="math-container">$B_1 = \{4, 1 \}$</span>, <span class="math-container">$B_2 = \{3, 0 \}$</span> and <span class="math-container">$B_3 = \{5, 2 \}$</span>, and so on. So, if there was any spurious/noisy information associated with some specific order of the samples, this would unlikely bias the computation of the gradient.</p>
  <p>This should give you some intuition about why shuffling might help to avoid the introduction of any bias due to some specific order of the samples.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-04-12T21:57:29.750Z
Answers.Text: Got it. I did not know that Keras randomly shuffles after each epoch. As far as I know in Pytorch, the shuffling only takes place once at the start of the training, which is why I assumed that the samples for subsequent epochs are not iid
Answers.UserDisplayName: Kunj Mehta
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-04-12T22:02:18.490Z
Answers.Text: Hm, it's strange that this is the default behaviour in PyTorch. I would like to know why.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-04-12T22:11:49.507Z
Answers.Text: my bad, Pytorch also shuffles every epoch.
Answers.UserDisplayName: Kunj Mehta
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-04-12T22:16:31.077Z
Answers.Text: Are you sure? The [PyTorch documentation](https://pytorch.org/docs/stable/data.html) says that the `DataLoader` has a default parameter `shuffle=False`. It's been a long time since I used PyTorch.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-04-12T22:20:27.633Z
Answers.Text: Yes, by default it is false. But when set to true, it shuffles data at every epoch
Answers.UserDisplayName: Kunj Mehta
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-04-12T21:34:13.153Z
Answers.LastActivityDate: 2022-04-12T22:00:19.903Z
Answers.LastEditDate: 2022-04-12T22:00:19.903Z
Answers.UserDisplayName: nbro
Body: <p>I have been reading the Deep Learning book by Ian Goodfellow and on pg. 277, they mention:</p>
  <blockquote>
  <p>It is also crucial that the minibatches be selected randomly.
  Computing an unbiased estimate of the expected gradient from a set of
  samples requires that those samples be independent. We also wish for
  two subsequent gradient estimates to be independent from each other,
  so two subsequent minibatches of examples should also be independent
  from each other</p>
  </blockquote>
  <p>I understand that for any unbiased estimation we require the samples to be i.i.d. so that we ideally end up with a true representation of the underlying data and so the above statement makes sense. However in practice, the samples that SGD sees for the subsequent gradient update (the next epoch) are the same, and it still performs well in the sense that the training error decreases. The authors later mention :</p>
  <blockquote>
  <p>...but of course, the additional epochs usually provide enough beneﬁt
  due to decreased training error to oﬀset the harm they cause by
  increasing the gap between training error and test error</p>
  </blockquote>
  <p>I know this happens but if someone could explain to me why and how it happens perhaps from a statistical perspective, it would be great! Another way to put it: why does training error in SGD decrease in subsequent epochs even though the samples are not i.i.d anymore?</p>
  
Tags: <machine-learning><deep-learning><stochastic-gradient-descent>
Title: How does SGD training error decrease in subsequent epochs when statistically, it requires that samples in subsequent epochs be i.i.d and they are not?
UserDisplayName: Kunj Mehta
ThreadText: # How does SGD training error decrease in subsequent epochs when statistically, it requires that samples in subsequent epochs be i.i.d and they are not?
  
  (Asked by: username_0 on 2022-04-12)
  
  I have been reading the Deep Learning book by Ian Goodfellow and on pg. 277, they mention:
  
  > It is also crucial that the minibatches be selected randomly.
  > Computing an unbiased estimate of the expected gradient from a set of
  > samples requires that those samples be independent. We also wish for
  > two subsequent gradient estimates to be independent from each other,
  > so two subsequent minibatches of examples should also be independent
  > from each other
  
  I understand that for any unbiased estimation we require the samples to be i.i.d. so that we ideally end up with a true representation of the underlying data and so the above statement makes sense. However in practice, the samples that SGD sees for the subsequent gradient update (the next epoch) are the same, and it still performs well in the sense that the training error decreases. The authors later mention :
  
  > ...but of course, the additional epochs usually provide enough beneﬁt
  > due to decreased training error to oﬀset the harm they cause by
  > increasing the gap between training error and test error
  
  I know this happens but if someone could explain to me why and how it happens perhaps from a statistical perspective, it would be great! Another way to put it: why does training error in SGD decrease in subsequent epochs even though the samples are not i.i.d anymore?
  
  **Tags:** machine-learning, deep-learning, stochastic-gradient-descent
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2022-04-12. Score: 1
  
  The samples might be the same in each epoch, but, before starting the new epoch, the training dataset might be **randomly shuffled** before splitting it into mini-batches (this is the [default behaviour in Keras](https://www.tensorflow.org/api_docs/python/tf/keras/Model#fit)), which helps to de-correlate the samples.
  
  For example, suppose that your training data consists of $D =\{4, 2, 3, 1, 5, 0 \}$. Now, you decide to perform mini-batch GD with batch size $m = 2$. You also shuffle the training data before each epoch, so before splitting the training data into mini-batches. In the first epoch, you could have batches $B\_1 = \{3, 0 \}$, $B\_2 = \{4, 5 \}$ and $B\_3 = \{2, 1 \}$. In the second epoch, we could have $B\_1 = \{4, 1 \}$, $B\_2 = \{3, 0 \}$ and $B\_3 = \{5, 2 \}$, and so on. So, if there was any spurious/noisy information associated with some specific order of the samples, this would unlikely bias the computation of the gradient.
  
  This should give you some intuition about why shuffling might help to avoid the introduction of any bias due to some specific order of the samples.
  
  > **Comments:**
  > **username_0**: Got it. I did not know that Keras randomly shuffles after each epoch. As far as I know in Pytorch, the shuffling only takes place once at the start of the training, which is why I assumed that the samples for subsequent epochs are not iid  
  > **username_1**: Hm, it's strange that this is the default behaviour in PyTorch. I would like to know why.  
  > **username_0**: my bad, Pytorch also shuffles every epoch.  
  > **username_1**: Are you sure? The [PyTorch documentation](https://pytorch.org/docs/stable/data.html) says that the `DataLoader` has a default parameter `shuffle=False`. It's been a long time since I used PyTorch.  
  > **username_0**: Yes, by default it is false. But when set to true, it shuffles data at every epoch  
  
  ---
  
  