Latest word on cross validation?

It's a standard result leave-one-out cross-validation is an unbiased estimator of the risk (see, e.g., Lemma 4.1 in Mohri, Rostamizadeh, Talwalkar). Are there any "better" results? Such as, say, with high probability rather than just in expectation?

• From my phone at the moment, but is this type of results (see discussion in Section 3) what you are looking for? math.arizona.edu/~hzhang/math574m/Read/LOOtheory.pdf – Clement C. Jan 6 at 0:05
• Yes, very much in this spirit! But is that the last word as of 2020? :) – Aryeh Jan 6 at 5:39

1 Answer

It is not hard to see that without additional stability assumptions one won't be able to get high probability bounds. For example consider predicting unbiased coin using majority label in the sample. With probability $$~1/\sqrt{n}$$ we get that majority of leave-one-out is exactly the opposite of the excluded point so LOO will give error of 1. Note that the true error is always 1/2.

If one assumes stability then the bounds will depend on the notion of stability being used. Uniform stability will give high probability bounds for both empirical mean and LOO estimator (e.g. https://arxiv.org/abs/1902.10710). Weaker notions will give you weaker bounds. I guess the latest on variance of the estimator is this paper http://www.satyenkale.com/papers/crossvalidation.pdf

• Thanks @Vitaly. Would you say that this more recent result has superseded yours? arxiv.org/pdf/1910.07833.pdf – Aryeh Jan 6 at 9:51
• Yes, it gives a much cleaner and slightly sharper way to implement our proof strategy. The strategy itself becomes harder to tease out in their paper so I'd still recommend starting with our result to those looking for intuition. – Vitaly Jan 6 at 10:17