# Failure of k-fold cross validation

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?

• 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. – Omri374 Dec 24 '17 at 13:40
• @Omri374 I think in the example there is no dependency between samples. Samples are i.i.d – SMA.D Dec 24 '17 at 13:46
• The dependency here is not between samples, but between runs of the CV algorithm, if I understand correctly. – Omri374 Dec 24 '17 at 13:50
• @Omri374 there is always dependency in CV, as long as there are overlapping samples between different folds. That is not a problem of CV. – Lii Dec 24 '17 at 15:38
• @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. – Omri374 Dec 25 '17 at 5:49