  Cross-validation is widely used for selecting among a family of learning
rules. This paper studies a related method, called aggregated hold-out
(Agghoo), which mixes cross-validation with aggregation; Agghoo can also be
related to bagging. According to numerical experiments, Agghoo can improve
significantly cross-validation's prediction error, at the same computational
cost; this makes it very promising as a general-purpose tool for prediction. We
provide the first theoretical guarantees on Agghoo, in the supervised
classification setting, ensuring that one can use it safely: at worse, Agghoo
performs like the hold-out, up to a constant factor. We also prove a
non-asymptotic oracle inequality, in binary classification under the margin
condition, which is sharp enough to get (fast) minimax rates.
