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.

  • $\begingroup$ It depends on the VC dimension of your problem settings. $\endgroup$ – OmG Apr 15 '20 at 13:56
  • $\begingroup$ @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! $\endgroup$ – nbro Apr 15 '20 at 14:04
  • 1
    $\begingroup$ @nbro thank you. sure. I will do that. $\endgroup$ – OmG Apr 15 '20 at 15:49
  • $\begingroup$ @OmG Could you elaborate a bit more? $\endgroup$ – ashenoy Apr 16 '20 at 5:15

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

The answers to the question On the importance of the i.i.d. assumption in statistical learning on CrossValidated provide more information and details, so you may want to have a look at it too. Here's another answer, which is related to shuffling and how it can or not make the independence assumption hold, that I highly recommend that you read.

  • $\begingroup$ 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? $\endgroup$ – ashenoy Apr 16 '20 at 5:18
  • $\begingroup$ @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. $\endgroup$ – nbro Apr 17 '20 at 0:54

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.