  We revisit resampling procedures for error estimation in binary
classification in terms of U-statistics. In particular, we exploit the fact
that the error rate estimator involving all learning-testing splits is a
U-statistic. Thus, it has minimal variance among all unbiased estimators and is
asymptotically normally distributed. Moreover, there is an unbiased estimator
for this minimal variance if the total sample size is at least the double
learning set size plus two. In this case, we exhibit such an estimator which is
another U-statistic. It enjoys, again, various optimality properties and yields
an asymptotically exact hypothesis test of the equality of error rates when two
learning algorithms are compared. Our statements apply to any deterministic
learning algorithms under weak non-degeneracy assumptions.
