What is better? x-times repeated n-fold cross validation or repeated (xn)-fold cross validation? x-times repeated n-fold cross validation has a higher bias than basic n-fold cross validation (without repetitions). If I want to reduce variance but maintain a low bias, isn't it probably better to use xn-fold cross validation instead of x-times repeated n-fold cross validation? E.g. is 40-fold cross validation probably better than 4-times repeated 10-fold cross validation? If not, why? Which values for x and n are recommendable?
 A: Consider that there are several sources of variance for validation figures of merit. 


*

*The finite number of cases available leads to variance uncertainty (any kind of performance measurement is affected by this).

*Resampling validation tests surrogate models and then uses their observed performance as approximation to the performance of the model trained on the whole data set. These surrogate models are assumed to be equivalent to the "whole data model", but in practice they may vary. Systematic deviations here mean that resampling validation is biased (e.g. the well-known slight pessimistic bias caused by ascending learning curve). Random deviations (i.e. model instability) cause additional variance on the performance estimate. 


The finite-sample-size variance uncertainty stays the same if you change the number of folds (at the end of the cross validation run, observations of $n$ tested cases enter the calculation of the figure of merit - regardless of $k$). Neither can this change when iterating/repeating the cross validation: you cannot get around the fact that you have only $n$ true cases to test. 
Repeating a $k$-fold cross validation does help with variance caused by model instability: More ($n \cdot k$) models are averaged. But comparing $n \times k$-fold cross validation (i.e. $n$ repetitions) with a single run of $nk$-fold cross validation would compare the same total number of surrogate models, and then any difference would depend on whether the change in splitting proportions would lead to better stability. 
However, one advantage of repeated cross validation is that you can very easily assess the stability: each run predicts each case exactly once. These prediction are done by surrogate models that differ in their training data composition as the case in question was left out together with different other cases. But as the case in question is the same, any variance observed across the runs must be due to model instability. Obviously, this does not work with leave-one-out cross validation where all possible surrogate models ($n$ possible combinations of $n-1$ out of $n$ cases) are evaluated in a single run.
If you'd want to estimate model instability from a single run of cross validation, you'd need to have sufficiently high numbers of cases tested by each surrogate model to detect the instability (i.e. performance variation between surrogate models) among the variance due to the number of tested cases (which are disjunct sets of cases) for each surrogate model. This needs low $k$ and large $n$ (and/or huge instability).

Bottom line recommendation:


*

*go for a sensible choice of $k$: 


*

*$k$ should be < $n$ (no leave one out), so always a few cases are left out together (also allows stratificatoin).

*Between $k$ = 5 to 10, 20 up to, say, $\frac{n}{3}$ or $\frac{n}{2}$ seems to be typically a sensible range.


*do some repetitions (say, 10) to prove that your models are stable. 


*

*If the models are stable, more repetitions would be a waste. 

*If they are slightly unstable, you can always add more repetitions until the variance caused by instability $\ll$ variance due to limited number of cases. Further reduction won't help your total variance uncertainty. 

*If your models are really unstable, you anyways need to step back and rethink your model development. 






*

*If you are not interested in the model trained on the data at hand but in the performance of models generated by the algorithm at hand for the application in general, then there's the additional uncertainty how representative the data set you have at hand is. This bias and variance you cannot assess with resampling validation, but your performance estimate is subject to this additional uncertainty.

