Answers.Body: <blockquote>
    <p>If the i.i.d (independent and identically distributed) assumption holds, shouldn't the training and validation trends be exactly the same?</p>
  </blockquote>
  
  <p>No, not necessarily. Let me explain why.</p>
  
  <p>If you assume your samples (aka examples, observations, data points, etc.) are i.i.d., this means</p>
  
  <ol>
  <li><p>that they come from the same distribution, e.g. a Gaussian <span class="math-container">$\mathcal{N}(0, 1)$</span> (the identically distributed part), and </p></li>
  <li><p>that they are independently drawn from it, i.e., intuitively, each sample provides the same kind of information independently of the others</p></li>
  </ol>
  
  <p>However, even if samples are independently drawn from a certain distribution, they can be different. For example, if you draw a sample <span class="math-container">$x$</span> from <span class="math-container">$\mathcal{N}(0, 1)$</span>, an operation often denoted as <span class="math-container">$x \sim \mathcal{N}(0, 1)$</span>, <span class="math-container">$x$</span> could have the value <span class="math-container">$0$</span>, <span class="math-container">$1$</span>, <span class="math-container">$13$</span> or <span class="math-container">$50$</span> (or any other number), so they could be variable, although your samples will tend to be mainly around <span class="math-container">$0$</span>, because that's where your Gaussian puts more density (and your standard deviation is just <span class="math-container">$1$</span>). If your standard deviation was higher, then there would be even more variability in the sampling process. </p>
  
  <p>So, if you assume that your samples are independently drawn from a certain distribution, it doesn't mean that you will always get the same pattern of samples. In other words, you can still have variability in your samples, and this also depends on the distribution you sample from. </p>
  
  <p>To answer your question more directly, there's a chance that your training data and your validation data don't necessarily have the same patterns, even if the independence assumption holds. Therefore, the training and validation trends (and I assume you mean e.g. the performance) are not necessarily the same, but, although this may also depend on the training method, I would say that they shouldn't be very different (if the assumption holds) because, intuitively, each sample should be as informative as any other sample (independence assumption).</p>
  
  <blockquote>
    <p>Do we work with the fact that there is a certain degree of wrongness to the assumption or am I interpreting it wrongly?</p>
  </blockquote>
  
  <p>It is often convenient to make the i.i.d. assumption even, if it doesn't hold, for several reasons: </p>
  
  <ol>
  <li><p>your training procedure may converge faster (because, intuitively, each sample will be as informative as any other sample)</p></li>
  <li><p>your models may be simpler (e.g., in naive Bayes, you make the i.i.d. assumption only to simplify the model and, in general, the mathematical formulations)</p></li>
  </ol>
  
  <p>Sometimes, if it doesn't hold, your training procedure can be highly affected. In those cases, you can find workarounds and try to make it hold. For example, the usage of the <em>experience replay</em> in deep Q-learning is an example of a trick used to overcome the dependence of successive samples, which causes learning to be highly variable. See this question <a href="https://ai.stackexchange.com/q/10839/2444">Why exactly do neural networks require i.i.d. data?</a>.</p>
  
  <p>The answers to the question <a href="https://stats.stackexchange.com/q/213464/821355">On the importance of the i.i.d. assumption in statistical learning</a> on CrossValidated provide more information and details, so you may want to have a look at it too. Here's <a href="https://stats.stackexchange.com/a/445477/82135">another answer</a>, which is related to shuffling and how it can or not make the independence assumption hold, that I highly recommend that you read.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-16T05:18:44.610Z
Answers.Text: Regardless of the loss taking slightly different values, wouldn't the loss trend indicating how loss is decreasing be roughly the same for both curves? They would be different, but is it reasonable to expect them to tend to each other as batch size increases?
Answers.UserDisplayName: ashenoy
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-17T00:54:33.643Z
Answers.Text: @ashenoy I say this in my answer. I think the answer to your question is "yes", although I don't have a formal proof for this.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-15T14:03:51.200Z
Answers.LastActivityDate: 2020-04-16T01:57:54.107Z
Answers.LastEditDate: 2020-04-16T01:57:54.107Z
Answers.UserDisplayName: nbro
Body: <p>If the i.i.d. (independent and identically distributed) assumption holds for a training-validation set pair, shouldn't their loss trends be exactly the same, since every batch from the validation set is equivalent to having a batch from the training set instead? </p>
  
  <p>If the assumption was to be true wouldn't that make any method that was aware of the fact that there were two separate sets (regularization methods such as early stopping) meaningless?</p>
  
  <p>Do we work with the fact that there is a certain degree of wrongness to the assumption or am I interpreting it wrongly?</p>
  
  <p>P.S - The question stems from an observation made on MNIST (where I suppose the i.i.d assumption holds strongly). The training and validation trends (losses and accuracy both) on MNIST were almost exactly identical for any network (convolutional and feedforward) trained using negative log-likelihood, making regularization meaningless. </p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-04-15T13:56:21.093Z
Comments.Text: It depends on the VC dimension of your problem settings.
Comments.UserDisplayName: OmG
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-04-15T14:04:28.183Z
Comments.Text: @OmG I think it would be very nice if you provide a formal answer from this perspective of computational/statistical learning theory. If you feel like writing one, I would really like to see it!
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-04-16T05:15:47.157Z
Comments.Text: @OmG Could you elaborate a bit more?
Comments.UserDisplayName: ashenoy
Tags: <machine-learning><deep-learning><training><iid>
Title: If the i.i.d. assumption holds, shouldn't the training and validation trends be exactly the same?
UserDisplayName: ashenoy
ThreadText: # If the i.i.d. assumption holds, shouldn't the training and validation trends be exactly the same?
  
  (Asked by: username_0 on 2020-04-15)
  
  If the i.i.d. (independent and identically distributed) assumption holds for a training-validation set pair, shouldn't their loss trends be exactly the same, since every batch from the validation set is equivalent to having a batch from the training set instead?
  
  If the assumption was to be true wouldn't that make any method that was aware of the fact that there were two separate sets (regularization methods such as early stopping) meaningless?
  
  Do we work with the fact that there is a certain degree of wrongness to the assumption or am I interpreting it wrongly?
  
  P.S - The question stems from an observation made on MNIST (where I suppose the i.i.d assumption holds strongly). The training and validation trends (losses and accuracy both) on MNIST were almost exactly identical for any network (convolutional and feedforward) trained using negative log-likelihood, making regularization meaningless.
  
  **Tags:** machine-learning, deep-learning, training, iid
  
  > **Comments:**
  > **username_1**: It depends on the VC dimension of your problem settings.  
  > **username_2**: @username_1 I think it would be very nice if you provide a formal answer from this perspective of computational/statistical learning theory. If you feel like writing one, I would really like to see it!  
  > **username_0**: @username_1 Could you elaborate a bit more?  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2020-04-15. Score: 5 | Accepted answer
  
  > If the i.i.d (independent and identically distributed) assumption holds, shouldn't the training and validation trends be exactly the same?
  
  No, not necessarily. Let me explain why.
  
  If you assume your samples (aka examples, observations, data points, etc.) are i.i.d., this means
  
  1. that they come from the same distribution, e.g. a Gaussian $\mathcal{N}(0, 1)$ (the identically distributed part), and
  2. that they are independently drawn from it, i.e., intuitively, each sample provides the same kind of information independently of the others
  
  However, even if samples are independently drawn from a certain distribution, they can be different. For example, if you draw a sample $x$ from $\mathcal{N}(0, 1)$, an operation often denoted as $x \sim \mathcal{N}(0, 1)$, $x$ could have the value $0$, $1$, $13$ or $50$ (or any other number), so they could be variable, although your samples will tend to be mainly around $0$, because that's where your Gaussian puts more density (and your standard deviation is just $1$). If your standard deviation was higher, then there would be even more variability in the sampling process.
  
  So, if you assume that your samples are independently drawn from a certain distribution, it doesn't mean that you will always get the same pattern of samples. In other words, you can still have variability in your samples, and this also depends on the distribution you sample from.
  
  To answer your question more directly, there's a chance that your training data and your validation data don't necessarily have the same patterns, even if the independence assumption holds. Therefore, the training and validation trends (and I assume you mean e.g. the performance) are not necessarily the same, but, although this may also depend on the training method, I would say that they shouldn't be very different (if the assumption holds) because, intuitively, each sample should be as informative as any other sample (independence assumption).
  
  > Do we work with the fact that there is a certain degree of wrongness to the assumption or am I interpreting it wrongly?
  
  It is often convenient to make the i.i.d. assumption even, if it doesn't hold, for several reasons:
  
  1. your training procedure may converge faster (because, intuitively, each sample will be as informative as any other sample)
  2. your models may be simpler (e.g., in naive Bayes, you make the i.i.d. assumption only to simplify the model and, in general, the mathematical formulations)
  
  Sometimes, if it doesn't hold, your training procedure can be highly affected. In those cases, you can find workarounds and try to make it hold. For example, the usage of the *experience replay* in deep Q-learning is an example of a trick used to overcome the dependence of successive samples, which causes learning to be highly variable. See this question [Why exactly do neural networks require i.i.d. data?](https://ai.stackexchange.com/q/10839/2444).
  
  The answers to the question [On the importance of the i.i.d. assumption in statistical learning](https://stats.stackexchange.com/q/213464/821355) on CrossValidated provide more information and details, so you may want to have a look at it too. Here's [another answer](https://stats.stackexchange.com/a/445477/82135), which is related to shuffling and how it can or not make the independence assumption hold, that I highly recommend that you read.
  
  > **Comments:**
  > **username_0**: Regardless of the loss taking slightly different values, wouldn't the loss trend indicating how loss is decreasing be roughly the same for both curves? They would be different, but is it reasonable to expect them to tend to each other as batch size increases?  
  > **username_2**: @username_0 I say this in my answer. I think the answer to your question is "yes", although I don't have a formal proof for this.  
  
  ---
  
  