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

I'm not sure what you mean by 'intrinsic'.

A higher training accuracy means you have found a model of the training data that doesn't describe the validation data equally well. Because of this, any statistically significant difference in training-validation accuracy is due to overfitting. Figuring out what 'statistically significant' means in this context is not totally trivial, unfortunately, but the general point still stands.

Answer 2

It is a good practice to always plot your CV and training costs alongside each other; preferably, in the same plot. If the distributions are similar, your CV cost and training cost should be pretty similar to start off with. If, as your model trains, you find that these two costs diverge radically, it is most likely due to overfitting.

In the attached plot, we have a classic case of overfitting. The two costs start out the same, but CV cost increases as training cost decreases. Since they started out the same, we know the model was equally poor at explaining the two data sets while in its untrained state.

As for whether the cost difference in the trained model is due to an intrinsic difference in the character of the data, or due to overfitting, that is a more difficult question. The best answer I can give is, if the number of training examples is very large, and the process of splitting the data into training and CV subsets is highly random, you can be pretty certain that these two subsets will be very similar in character. The law of large numbers is on your side. Unless the data is very skewed, it is extremely unlikely that one subset would get all the training examples of a certain character. If, in contrast, you are working with a very small data set, or your process of subset assignment is less-than-random, then you may run into situations where the character of the CV subset differs from the training subset in some fundamental way.