Why k-fold cross validation (CV) overfits? Or why discrepancy occurs between CV and test set? Recently, I was working on a project and found my cross-validation error rate very low, but the testing set error rate very high. This might indicate that my model is overfitting. Why does my cross-validation not overfit while my test set overfits?

More specifically, I have about 2 million observations with 100 variables (n>>p). I randomly split the data set into 80/20 train and test. Then, I fit a model (i.e. XGboost) using a 5-fold cross validation on the training set and the estimated error rate is pretty low. Then, I used the same parameter setting and used the entire training set to fit the model. Surprisingly, when I used the test set to evaluate the performance of the model, the error rate is significantly higher than the CV error rate. Why?

Edit:

(About the error rate)

The error rate is actually multinomial logloss. I achieved a CV error rate of 1.320044 (+/- 0.002126) and a testing error rate of 1.437881. They might seem close by staring at these two numbers, but actually, they are not. I don't know how to justify this, but I am sure that they are different within the scale of performance of this project, which is from ~1.55 to ~1.30.

The way of 5-fold cross validation is like following,


divide the train set into 5 sets.
iteratively fit a model on 4 sets and test the performance on the rest set.
average the performance of all the five iterations.


I mean, if my parameter settings make model overfit, then I should see it at this cross-validation procedure, right? But I don't see it until I use the test set. Under what circumstances on the earth this could happen?

Thanks!

Added:

The only reason I could think of that why CV error rate diffs from test set error rate is 

Cross-Validation will not perform well to outside data if the data you do have is not representative of the data you'll be trying to predict! -- here

But I randomly 8/2 split the 2-million-sample data set and I believe that the train set and test set should have a same distribution of variables.

(Pardon me that I post the same question here also.)

Edit:

(About the data leakage)

I got one interesting commend from @darXider in cross validated. He says,


  Sometimes when feature engineering, you have to be careful to avoid any data leak between training and test sets. For example, if you do a
  PCA on your original, untouched data, use PC1 and PC2 as "new"
  features, and then split your dataset into train and test, you are
  leaking information from training set into test set. That will boost
  your score up. You mentioned that after some feature engineering, your
  CV score and test score started to disagree. That could suggest some
  sort of information leak between training set and test set.


I wonder what is exactly the "data leakage" and why feature engineering BEFORE splitting can still cause "data leakage"??
I agree with the comment you received from Cross Validated – data leakage is something that fits this problem setting as it's known to cause too optimistic CV score when compared to test score. We could confirm that it's actually a data leakage problem if you provided information about the data pre-processing steps that you've taken.

Data leakage means that information is leaking from the test data to the training data, causing the trained model to over-estimate expected performance and to generalize poorly to unseen data, because the leaked information allows the model to learn something that it otherwise wouldn't learn.

As an example, let's say that you had only a small amount of training examples and you end up synthesizing more training examples that are somehow similar to the other training examples. If you implement the synthesis before CV loop and not inside it (within each fold), your CV accuracy will skyrocket but test accuracy will be low. In addition to data synthesis, data leakage can also happen with other pre-processing steps, such as scaling the data, inputting missing values or performing feature selection.