There is an interesting exercise which shows k-fold cross validation fails in some cases. The exercise is as follows:

Consider a case in that the label is chosen at random according to $P[y =1]= P[y =0]=1/2$. Consider a learning algorithm that outputs the constant predictor $h(x)=1$ if the parity of the labels on the training set is 1 and otherwise the algorithm outputs the constant predictor $h(x)=0$. Prove that the difference between the leave-one-out estimate and the true error in such a case is always 1/2.

My question is in what cases (or under what conditions) k-fold cross validation fails? Is it only k-fold validation that fails or other types of cross validation may fail too?

  • $\begingroup$ Cross validation fails whenever there's a dependency between samples. This kind of dependency exists in the scenario you provided as well as other scenarios, such as time dependent samples (time series), samples that originally belong to a group out of a set and more. $\endgroup$
    – Omri374
    Dec 24, 2017 at 13:40
  • $\begingroup$ @Omri374 I think in the example there is no dependency between samples. Samples are i.i.d $\endgroup$
    – SMA.D
    Dec 24, 2017 at 13:46
  • $\begingroup$ The dependency here is not between samples, but between runs of the CV algorithm, if I understand correctly. $\endgroup$
    – Omri374
    Dec 24, 2017 at 13:50
  • 1
    $\begingroup$ @Omri374 there is always dependency in CV, as long as there are overlapping samples between different folds. That is not a problem of CV. $\endgroup$
    – Lii
    Dec 24, 2017 at 15:38
  • $\begingroup$ @Lii I agree. I was referring to the example provided in the question, in which the model is heavily dependent on the subset of training samples. A change in one sample would change the output of the model even if the number of samples is high. $\endgroup$
    – Omri374
    Dec 25, 2017 at 5:49

1 Answer 1


I found this answer in the same book:

The cross validation method often works very well in practice. However,it might sometime fail, as the artificial example shows. Rigorously understanding the exact behavior of cross validation is still an open problem. Rogers and Wagner (Rogers & Wagner 1978) have shown that for k local rules (e.g., k Nearest Neighbor) the cross validation procedure gives a very good estimate of the true error. Other papers show that cross validation works for stable algorithms.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.