cross-validation and over-fitting I am performing model evaluation (via maximum likelihood) on several datasets with a number of different classes of models.
I have reasons to suspect that a specific class of models is (much) more flexible than the others, and therefore measures such as AIC might favour this more flexible class due to the risk of over-fitting. One of the reasons is that, for example, when I switch to BIC results change dramatically (although it is fair to say that BIC might be over-penalizing model complexity).
Therefore, I performed a 10-fold cross validation on stratified data ($9/10$-th training, $1/10$-th test), and evaluated the models using the sum (or average) log likelihood on the hold out test data, as an estimate of model out-of-sample performance.
To my surprise, the model class that I thought was more flexible(*) won the model comparison under 10-fold CV. 


*

*Should I conclude that there is no over-fitting going on, notwithstanding the mixed evidence from other metrics (e.g., BIC) and prior information?

*Are there other tests you would perform to verify that this model class is (not) winning out of additional flexibility?


(*) Edit: not just more flexible, but excessively more flexible.
 A: 
I have reasons to suspect that a specific class of models is more flexible than the others, and therefore measures such as AIC might favour this more flexible class due to over-fitting.

A few points of clarification


*

*The fact that a more flexible model fits better is a very natural thing and by no means indicates overfitting. A model can be either not flexible enough (underfitting), and too flexible (overfitting).

*The most common methods to find the right degree of flexibility include AIC, BIC and CV, where AIC and CV are closely related, see 1). The fact that AIC and BIC differ for large datasets is well-known. 

*Which of them is best has been subject to extended debates, with no clear answer. In any case, both AIC and CV are means to avoid overfitting (with AIC having a bit of reputation for favoring too complex models).


To summarize, I don't see a general problem with choosing the model that is favored by your 10-fold CV.
1) Stone, M. (1977) An Asymptotic Equivalence of Choice of Model by Cross-Validation and Akaike's Criterion. Journal of the Royal Statistical Society. Series B (Methodological), 39, 44-47.
A: There is another simple answer: a bug in the code. Whops.
After a long debugging session, I found a subtle indexing mistake in the script that was reading the results of the 10-fold CV. 
I am writing this as a separate answer because I feel it might be instructive...
What pointed me to the existence of a bug, expectations aside, was that the predictions of the CV on test folds would often beat the predictions based on MLE results obtained by training on the full dataset. This should not happen, or at least be extremely unlikely, and it is a clear signal that there is a mistake somewhere.
Now the results that I get are better aligned with previous information. The model that I believed to be "exceedingly flexible" is not consistently best any more. As expected, the result of the 10-fold CV across models happens to be somewhat in-between what AIC and BIC predict.
