Beating the Holdout: Bounds for K-Fold and Progressive Cross-Validation - Blum, Avrim; Kalai, Adam Tauman; Langford, John (COLT '99 Proceedings of the twelfth annual conference on Computational learning theory, 1999)
K-Fold cross-validation is a popular technique in machine learning for estimating the performance of a learned hypothesis on a data set. We provide the first theoretical justification for this method that shows that it is, on average, more accurate than a held-out test set of comparable size.