How to compute confidence intervals for the performance estimate of nested cross validation?

Question

Nested cross validation (NCV) is the standard procedure to estimate the performance of a classifier, after tuning its parameters and hyper-parameters. Despite being a concept quite general and widely known, there seem to me to be no clear receipt on how to compute the error on this performance estimate. Surely, the question has been asked elsewhere on 'Cross Validated', for example here, or here, or here. However none of those answers or questions is highly voted, as I would expect for a question so general and important. Nor can I find an answer to my questions elsewhere on the internet.

In sum, I found the following answers, and I cannot decide myself for one:

1. use wilson score interval, see here. In this case the error band only depends on the performance itself (which sounds strange to me. furthermore it only applies to accuracy, for what I understood, not to other performance measures as AUC for ROC)
2. since the NCV estimate is the mean on the N outer folds, compute the SE of this mean and Wald intervals (this is what I would have done before reading around). If this answer is correct, why would one need bootstrap and/or repeated CV, see below?
3. same as 2. but with repeated cross validation, so one has more measures (which however are correlated then), the issues inherent to this choice are explained here. Nice insightful paper, that offers no solution though.
4. bootstrapping, but computationally veeery expensive as NCV is per se already expensive.
5. permutations (practically too expensive, see above)

Therefore, what would be the recommended procedure, say in a problem with 1000 participants and 100 features and a grid search over say 100 hyperparameters combinations? How would that change for 10k participants and 1k features?

Answer 1

Your question actually motivated me to writeup a recently published Stanford paper - link. Here's the writeup if you're curious. Note that you'll still see the performance hits because it uses NCV, but this method seems statistically robust.

Finally, I think Cross Validated was missing info about computing the SE because the method didn't exist. Dependence between folds has been a long-standing issue with cross validation that, in my experience, is just ignored.

"Roughly speaking, we expect the standard CV intervals to perform better when n/p is larger and when more regularization is used. In our experiments, we saw that even in the mundane linear model with n/p = 10, the miscoverage rate of standard CV was about 50% larger than the nominal rate." - section 7

Paper Info (in case the link dies):

• Name: Cross-validation: what does it estimate and how well does it do it?
• Authors: Stephen Bates, Trevor Hastie, and Robert Tibshirani
• Year: 2021
• Key conclusions: "We have made two main contributions. First, we discussed point estimates of prediction error via subsampling techniques. Our primary result is that common estimates of prediction error—cross-validation, bootstrap, data splitting, and covariance penalties—cannot be viewed as estimates of the prediction error of the final model fit on the whole data. ... Secondly, we discuss inference for cross-validation, deriving an estimator for the MSE of the CV point estimate, nested CV."