PAC-like upper bounds for the sample complexity of leave-one-out cross-validation
Sean B. Holden · 1996
When designing a pattern classifier it is often the case that we have available a supervised learning technique and a collection of training data, and we would like to gain some idea of what the error probability of our classifier will be after training.A popular way of approaching this problem in practice is to use some form of error estimate, one of the most popular estimates being the cross-validation estimate.In this paper we address the following question: if we have n training examples what is the probability that the leave-one-out cross-validation estimate differs from the actual error probability by more than a constant c?We derive upper bounds on this probability for the closure algorithm and the deterministic l-inclusion graph prediction strategy.1