$5 \times 2$ Cross-Validation to estimate the error and variance of error? I want to estimate the mean and variance of the error of a model.
This paper: Approximate Statistical Tests for Comparing Supervised Classification Learning Algorithms, suggests doing $5 \times 2$cv, which is to iterate 5 times a 2-fold and then to compute the mean.
Now, if I have a model that is cheap to train (I mean computational cost is not an issue) and want to estimate the error of the model and the variance, I am aware that you should not estimate the error $1000$ times with for example a $10$-Fold, because variance will be underestimated, as the sample is finite.
Now, Isn't $5 \times 2$cv a little exaggerated? I repeat, computational cost is not an issue here. I think the question could be split into two: If I want to estimate the error, I think it is better off to run, say, $1000$ times a $k$-Fold and then compute the mean.
Then, for the variance: What is the optimal number of repetitions and folds?
The paper I cite deals with small samples, but it is unclear to me what could be considered an small sample, even if we know this is a relative term, it is still unclear.
 A: 
I want to estimate the mean and variance of the error of a model.

That is, in the terminology of Dietterich's paper you link, you are looking at question 1 or 2 (see figure 1) instead of question 8 which is the topic of the paper!?

you should not estimate the error 1000 times with for example a 10-Fold, because variance will be underestimated

For questions 1 + 2 you can get the relevant variance estimates from the proposed cross validation. It is crucial, though, to understand the different sources of variance uncertainty here.
Also, for questions 1 - 4, you want to have large overlap between the training sets for the CV surrogate models: your implicit assumption is that the surrogate models are equal (or at least equivalent) to the final model trained on the whole available data set - for which you use the CV approximation of generalization error. 
You can also say that the training sets of the surrogate models are slightly perturbed versions of the training set for the final model.
The important advantage you get from iterated cross validation (or from out-of-bootstrap estimates) is that you have multiple predictions for the same case by differnt surrogate models. These vary by being trained on slightly different training sets. Thus, you can measure the variance due to these slight differences in training data, aka model instability with respect to exchanging a few training cases.
Iterations help estimating this variance (and reducing the corresponding variance uncertainty on the final estimate).
In addition, you have the actual choice of test cases contributing variance: estimates based on a smaller total number of independent cases are less certain. I'll refer to this as variance due to the fininte test sample size.
With this type of variance, more actual cases help, but more iterations do not have any influence on this source of uncertainty.
It is important to note that these variance contributions are independent of each other. Dietterich's questions 5 - 8 extrapolate further from the training data at hand to a training set of given size $m$ of the (application) domain studied. The corresponding variance uncertainty cannot be measured if only $m$ cases are at hand, and this is the reason for underestimating variance with respect to those questions. But questions 1 - 4 are not subject to this additional variance. 

optimal number of repetitions 



*

*you cannot have too many

*but once the variance contribution of model instability to the final point estimate is negligible compared to the random uncertainty due to the finite number of (tested) cases, more iterations don't help any further.

*In other words, for stable models, you basically don't need iterations (other than for proving the models are stable) 



and [optimal number of] folds?

Being concerned with question 2, I typically go for something between 5-fold and 10-fold

what could be considered an small sample.

This depends somewhat on the context (regression vs. classification). For classification figures of merit that measure a proportion/fraction of cases (e.g. fraction of cases correctly classified), the variance uncertainty due to the finite number of actually indepent tested cases allows to calculate variance up to a range (for the true fraction ranging between 0 or 100% to 50 %).
See e.g. our paper Beleites, C. et al.: Sample size planning for classification models. Anal Chim Acta, 2013, 760, 25-33.
DOI: 10.1016/j.aca.2012.11.007
accepted manuscript on arXiv: 1211.1323
Bottomline is that with less than 100 independent cases in the denominator, variance will typically be too large to draw any meaningful conclusions whether the model is fit for purpose. 
For regression, there are no such bounds (but you can measure this variance). For my applications, I'd say the situation is typically better than for classification.
Anyways, the relevant sample size question also needs to consider how representative the test cases are for the application situation - and that may need much larger sample size.
