\(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.