  Cross validation is a central tool in evaluating the performance of machine
learning and statistical models. However, despite its ubiquitous role, its
theoretical properties are still not well understood. We study the asymptotic
properties of the cross validated-risk for a large class of models. Under
stability conditions, we establish a central limit theorem and Berry-Esseen
bounds, which enable us to compute asymptotically accurate confidence
intervals. Using our results, we paint a big picture for the statistical
speed-up of cross validation compared to a train-test split procedure. A
corollary of our results is that parametric M-estimators (or empirical risk
minimizers) benefit from the "full" speed-up when performing cross-validation
under the training loss. In other common cases, such as when the training is
done using a surrogate loss or a regularizer, we show that the behavior of the
cross-validated risk is complex with a variance reduction which may be smaller
or larger than the "full" speed-up, depending on the model and the underlying
distribution. We allow the number of folds to grow with the number of
observations at any rate.
