<p>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 <span class="math-container">$~1/\sqrt{n}$</span> 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.</p>

<p>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. <a href="https://arxiv.org/abs/1902.10710" rel="noreferrer">https://arxiv.org/abs/1902.10710</a>).
Weaker notions will give you weaker bounds. I guess the latest on variance of the estimator is this paper <a href="http://www.satyenkale.com/papers/crossvalidation.pdf" rel="noreferrer">http://www.satyenkale.com/papers/crossvalidation.pdf</a></p>

CC BY-SA 4.0
2020-01-06T09:51:21.440Z
Thanks @Vitaly. Would you say that this more recent result has superseded yours? https://arxiv.org/pdf/1910.07833.pdf
Aryeh
CC BY-SA 4.0
2020-01-06T10:17:33.770Z
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
CC BY-SA 4.0
2020-01-06T08:19:32.563Z
2020-01-06T08:19:32.563Z
Vitaly
<p>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?</p>

CC BY-SA 4.0
2020-01-06T00:05:46.410Z
From my phone at the moment, but is this type of results (see discussion in Section 3) what you are looking for? https://www.math.arizona.edu/~hzhang/math574m/Read/LOOtheory.pdf
Clement C.
CC BY-SA 4.0
2020-01-06T05:39:56.450Z
Yes, very much in this spirit! But is that the last word as of 2020? :)
Aryeh
<machine-learning><lg.learning><pac-learning>
Latest word on cross validation?
Aryeh
# Latest word on cross validation?

(Asked by: username_0 on 2020-01-04)

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?

**Tags:** machine-learning, lg.learning, pac-learning
> **Comments:**
> **username_1**: From my phone at the moment, but is this type of results (see discussion in Section 3) what you are looking for? https://www.math.arizona.edu/~hzhang/math574m/Read/LOOtheory.pdf  
> **username_0**: Yes, very much in this spirit! But is that the last word as of 2020? :)  

---

## 1 answers

### Answer by username_2 on 2020-01-06. Score: 6 | Accepted 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>

> **Comments:**
> **username_0**: Thanks @Vitaly. Would you say that this more recent result has superseded yours? https://arxiv.org/pdf/1910.07833.pdf  
> **username_2**: 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.  

---

