Is it normal to get more variance in k folds cross-validation of an algorithm than in k repetitions? Is it normal to get a lot more variance in k folds cross-validation of an algorithm than in k repetitions of the same algorithm (neural network) on the same dataset?
k = k_folds = 10, same random seeds
Cross Validation Accuracy with k folds : 89.78% (+/-13.29%)
Mean Test Accuracy on k independent runs: 84.08% (+/-2.76%)
Thanks in advance
 A: Cross validation error will contain variance due to the randomness within the selection of the k folds as well as any randomness from with the algorithm. Simply running an algorithm multiple times will give an error rate where the only variance comes from the randomness contained in the algorithm. So yes, it makes sense that the cross validation error would have more variance.
A: You have (at least) 3 sources of variance/randomness/random uncertainty here: 


*

*your algorithm being non-deterministic: running repeatedly with the same training data yields different results for the same test data

*model instability: training on slightly different training data yields different results for the same test data

*variance due to the finite test set: predicting different test cases that share the same reference value/label/class yields different results.


Looking at the differences between the folds of $k$-fold cross validation covers (1) - (3), so expect that to be larger than variance (1) alone.
Total variance is best reduced by having more repetitions for the largest of these variance contributions. So,


*

*if the dominating variance is the non-deterministic aspect of the algorithm, train repeatedly on the same training set and do an aggregate prediction for this bunch of models. Or stabilize the training procedure.

*if the dominating variance is model instability wrt. changes in the training set, you can bag (bootstrap aggregate) or regularize your model

*if the dominating variance comes from having too few test cases, nothing but getting more test cases will help.

