Satyen Kale, Ravi Kumar, and Sergei Vassilvitskii
Proceedings of 2nd Symposium on Innovations in Computer Science (ICS), 2011

$$k$$-fold cross validation is a popular practical method to get a good estimate of the error rate of a learning algorithm. Here, the set of examples is first partitioned into $$k$$ equal-sized folds. Each fold acts as a test set for evaluating the hypothesis learned on the other $$k-1$$ folds. The average error across the $$k$$ hypotheses is used as an estimate of the error rate. Although widely used, especially with small values of $$k$$ (such as 10), the technique has heretofore resisted theoretical analysis. With only sanity-check bounds known, there is not a compelling reason to use the $$k$$-fold cross-validation estimate over a simpler holdout estimate. The complications stem from the fact that the $$k$$ distinct estimates have intricate correlations between them.