validation/training accuracy and overfitting

Question

If we randomly split the data into training data and validation data, and assume the training data and validation data have similar "distributions", i.e. they are both good representations of the whole data set.

In this case, should the validation accuracy always be roughly the same as the training accuracy if there is no overfitting? Or is it possible that, for some cases, there could exist an "intrinsic" gap between the training and validation accuracy that is not due to overfitting or bad representation of the validation data?

If such "intrinsic" gap exists, how to tell if the gap between the training and validation accuracy is "intrinsic" or caused by overfitting?

Answer 1

In this case, should the validation accuracy always be roughly the same as the training accuracy if there is no overfitting?

There are a few points here: "accuracy" and "loss/error/cost" are 2 separate concepts. "Accuracy" is often used in classification problems and computed as the percentage of correctly classified inputs. This makes it quite a noisy measure.

The "loss/error/cost" is a better measure of performance, and can be analysed mathematically more easily. If I may, I'll reformulate your question as:

"Is training error always less than validation error, even if there is no overfitting or bad representation of the data?"

Not always, because these are random quantities. So for a particular combination of dataset + training-validation split + model, the validation error might be lower than the training error. But the expectation of the validation error (bold red line) will be higher than the expectation of the training error (bold blue line):

(Image source: ESL Chapter 7).

Even though training and validation data are drawn from the same distribution, we expect the model to perform better when training than when we test it in the validation set.

Ignoring the irreducible error caused by noise in the data, every model will be associated with some bias and variance. There is no perfect model.

And we expect the combination of bias and variance to be higher on the validation set than on the training set. This is because fitting the model minimises the training set error at the expense of validation set error.

Answer 2

Interesting question! The only situation I can think of is when the data come from a very high-dimensional space (e.g. real world images) where, even if your training and validation set roughly represent the real distribution, the distribution will be extremely sparse. Then it can easily happen that the samples from the validation set are unrepresented enough in the training set, even though the model is not overfitted.

Cross validation should be able to reveal this phenomenon (possibly outliers in the distribution of accuracies for each fold).