An a Priori Exponential Tail Bound for k-Folds Cross-Validation
This work addresses the reliability of cross-validation estimates for practitioners in machine learning, offering a theoretical insight that is incremental but clarifies a known issue.
The paper tackles the problem of understanding the concentration of k-fold cross-validation estimates around true risk by deriving an exponential tail bound that attributes this concentration to the stability of the learning rule and the number of folds, rather than bias and variance.
We consider a priori generalization bounds developed in terms of cross-validation estimates and the stability of learners. In particular, we first derive an exponential Efron-Stein type tail inequality for the concentration of a general function of n independent random variables. Next, under some reasonable notion of stability, we use this exponential tail bound to analyze the concentration of the k-fold cross-validation (KFCV) estimate around the true risk of a hypothesis generated by a general learning rule. While the accumulated literature has often attributed this concentration to the bias and variance of the estimator, our bound attributes this concentration to the stability of the learning rule and the number of folds k. This insight raises valid concerns related to the practical use of KFCV and suggests research directions to obtain reliable empirical estimates of the actual risk.