  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.
