Will cross validation performance be an accurate indication for predicting the true performance on an independent data set? I feel that this question is related to the theory behind cross-validation. I present my empirical finding here and wrote a question related to the theory of cross-validation at there.

I have two models M1 and M2, I use the same data set to train them and perform cross validation using that same data set to find the optimal parameters for each model. Say eventually I found that M1 under its optimal parameter, performs better than M2 under its optimal parameter in terms of the 10-fold cross validation score. Now if I have another independent test data set with both predictors and labels and this test data set is generated from the same distribution of my training data set, then before I apply these 2 well-tuned model on that new test data set, can I claim or should I expect to see that M1 will still perform better than M2 over that new test data set?

I was playing Kaggle Titanic example. I have 2 xgboost model, M1 is well-tuned and M2 is less well-tuned in the sense that M1 has a better 10 fold cross validation performs on the training data set. But then when I submit both, I found that the less well-tuned model actually has a better scores on the test data set. How could that be? And if it is true, then what should we looking for when we fit the data to different models and tune the model parameters?

Here are my specific submission results: I did a random grid search

params_fixed = {'silent': 1,'base_score': 0.5,'reg_lambda': 1,
'max_delta_step': 0,'scale_pos_weight':1,'nthread': 4,
'objective': 'binary:logistic'}
params_grid = {'max_depth': list(np.arange(1,10)),
'gamma': [0,0.05,0.1,0.3, 0.5,0.7,0.9],
'n_estimators':[1,2,5,7,10,15,19,25,30,50], 
'learning_rate': [0.01,0.03,0.05,0.1,0.3,0.5,0.7,0.9,1],
'subsample': [0.5,0.7,0.9], 'colsample_bytree': [0.5,0.7,0.9], 
'min_child_weight': [1,2,3,5], 'reg_alpha': [1e-5, 1e-2, 0.1, 0.5,1,10]
}
rs_grid = RandomizedSearchCV(
          estimator=XGBClassifier(**params_fixed, seed=seed),
          param_distributions=params_grid,
          n_iter=5000,   
          cv=10,
          scoring='accuracy',
          random_state=seed
)


Each time I change the variable n_iter. First, I set n_iter=10, it gives me a set of values of those hyper parameters, let's call this vector $\alpha_1$ and the cv score (accuracy rate) is 0.83389, then I use $\alpha_1$ to train my model and generate prediction on the independent test data set, and when I submit to Kaggle it generates true accuracy on the test data set 0.79426

Second, I set n_iter=100, it gives me $\alpha_2$ and the cv score is 0.83614, i.e., higher than the first one, makes sense, but when I submit to Kaggle, 0.78469, lower than the first one.

Third, I set n_iter = 1000, it gives me $\alpha_3$ and the cv score is 0.83951, i.e., higher than the second one, makes sense, but when I submit to Kaggle, 0.77990, lower than the second one.

Fourth, I set n_iter = 5000, it gives me $\alpha_4$ and the cv score is 0.84512, i.e., higher than the third one, makes sense, but when I submit to Kaggle, 0.72249, lower than the third one.

This is really frustrated. The model is getting better and better on the cross-validation score but when performed on an actual independent data set, its performance is getting worse and worse. Did I interpret the CV scores in the exactly opposite way? I see some paper mentioned that the CV score can be too optimistic for inferring the true test score. However, even if that is true, then I think the CV scores for all of my 4 models should be all optimistic about their own true test score, i.e., the order should preserve. But when applying on the real test data set, the order reversed.

The only reason I can imagine would be, that test data set has a different distribution than the training data set. However, if it is indeed the case, then I believe there is no method under then sun that can cure this problem.
First off, a pragmatic answer: don't discount the possibility that the test set comes from a somewhat different distribution than the data set you're using for training and cross-validation.  You might think that shouldn't happen, but in practice it does seem to occur.

That said, let's go with your hypothetical and assume that the test set comes from exactly the same distribution as the rest of your data.  In that case, it is possible for cross-validation to lead you astray about which model is better, if you're using cross-validation to select hyper-parameters.

You can use cross-validation to either (a) select hyper-parameters, or (b) estimate the accuracy of your model -- but not both at the same time.

It appears you're using cross-validation to select the optimal hyper-parameters: you try many different choices for the hyper-parameters, for each choice estimate accuracy of that choice using cross-validation, and select the best choice.  When you do that, there's no guarantee that the resulting accuracy (with the best parameter) will be predictive of performance on the test set -- it might be an overestimate (due to overfitting).  If it's more of an overestimate for M1 than M2, then you might see what you saw.

If you want to both select hyper-parameters and estimate accuracy, I suggest that you have a separate held-out validation set for estimating accuracy, or use nested cross-validation.  See https://stats.stackexchange.com/q/65128/2921 and http://scikit-learn.org/stable/auto_examples/model_selection/plot_nested_cross_validation_iris.html.