Costs of cross-validation

Topic: Estimating error rates · more questions on this topic
‹ Jackknife of the mean A tempting wrong turn ›

For n=1000, how many times must the classifier be trained for leave-one-out cross-validation, for 10-fold cross-validation, and for nested cross-validation with m=10 outer folds and 9-fold inner cross-validation over K=5 candidate models? Count the final training steps too.

Worked answer (click to show)

Leave-one-out cross-validation trains n=1000 classifiers. Ten-fold cross-validation trains 10. For nested cross-validation with m=10, each outer iteration runs 9\times 5=45 inner fits to compare the candidates and one refit of the chosen model on the training and validation data, 46 in all, so 10\times 46=460. The final classifier needs its own selection, taken here as 10-fold cross-validation over 5 candidates, hence 50 fits, plus one fit on all the data: 51. The total is 460+51=511. The full procedure requires about fifty times as many fits as one ten-fold calculation. That cost is specific to these loop sizes. The assessment benefit comes from keeping selection inside each outer training set.