if you have few data where n≤p or n is not sufficiently greater than p, evaluating model performance usually suffers from a variance problem (i.e. the performance depends heavily on the way the test set is choosen).
I think there is a misunderstanding here: measuring the performance of a given model depends on the absolute number of test cases (and on how representative the test set is wrt. the application), but not at the model complexity.
Model complexity enters this question only in the way that too complex or not complex enough models have low performance - and that the confidence interval for the performance estimate may depend on both the actual (true) performance
of the model and the number of test cases.
For details on how to use this to calculate necessary test sample sizes for proportion-type figures of merit (e.g. sensitivity, specificity, accuracy) for different application scenarios, please have a look at our paper:
Beleites, C. and Neugebauer, U. and Bocklitz, T. and Krafft, C. and Popp, J.: Sample size planning for classification models. Anal Chim Acta, 2013, 760, 25-33.
accepted manuscript on arXiv: 1211.1323
One interesting point here is that the confidence intervals are widest for p = 50 %, so if you determine your sample size with that, it will be sufficient with whatever model performance you observe when you have your data.
(You could also plug in some estimate of what performance you expect to achieve.)
Is it possible (and how) to determine beforehand whether CV or hold out should be used?
There are a few points that help with the decision:
First of all, if the hold-out set is produced from available data with a random split similar to the splitting for CV, that hold out is almost always worse than some kind of resampling validation: you have all the drawbacks (dependence issues) you have with resampling, plus lower test sample size - and don't use any of the possible advantages of validating with a truly independent test set.
some reasons for going for an independent test set (as opposed to simple splitting for hold-out)
There's IMHO a crucial difference depending on what the purpose of your testing is, i.e. in which way you want to generalize your findings.
- for measuring the predictive abilities of the model produced from this data set, the dependence between the surrogate models in resampling validation is wanted, so go for cross validation.
- if you want to generalize what performance the given algorithm can achieve with similar data sets (but not the one at hand), then the dependence between the surrogate models makes your estimate overoptimistic, and you may be better or with truly independent test data.
If your total available sample size is too small, so the confidence interval for hold-out results are so wide that hold-out results are useless (I have to tell people that if they reserve 3 test patients only, the confidence interval will range all the way from worse-than-guessing to perfect), there's no choice but resampling.
(If the sample size is so small that neither resampling validation results are useful => get more samples)