Is it possible to have a higher train error than a test error in machine learning? Usually it is called over-fitting when the test error is higher than the training error. Does that imply that it is called under-fitting when the training error is higher than the test error? Also what is the difference between test error and validation error?
 A: These simplified formulae from Stanley Сhan's Introduction to Probability for Data Science provide some good intuition on the train/test error:
MSEtrain = σ2 (1 - d/N)
MSEtest = σ2 (1 + d/N)
where σ2 is noise variance (data measurement errors and such), N is the sample size, d is a measure of model complexity (d<=N).
Overfitting means that a model fits too closely to the training samples so that it fails to generalize (d is comparable to N): train error is low, test error is high.
When the model is too simple and uderfits data (d<<N), train and test error are about equally high.
When your test error is suspiciously low, that likely means you've got some sort a of data leakage from a test set (e.g. when you preprocess a whole dataframe before splitting).
As of validation vs test error, a separate validation split normally serves as an intermediate test for e.g. best model/hyperparameter selection. Since you purposely select what performs best on this set, it can be treated as a sort of leakage as well. Thus the final test data should remain unseen until the very end of the model development process.
