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.