We sincerely thank you for recognizing our contributions both on the theoretical and practical fronts, and also for the detailed and very helpful suggestions. We address your comments point-by-point as follows.

Claimed strength of results: We would follow your suggestion and change that claim in the introduction to "This analysis helps us provide a complete breakdown of how bias and coverage depend on the convergence rate of the model at hand. This in turn fills in the gap in understanding which methods outperform which others, in regimes that have appeared challenging for previous works." We will also make similar changes in the abstract.

Actually, our original thought was similar to your comment in that we regarded the complete breakdown as a provision of both sufficient and necessary conditions, with the list of assumptions being used to prescribe some regularity in the setting. Nonetheless, we see your very valid point that the use of the term ``necessary conditions" would cause confusion, and so we would change that as you suggested.

Utility of CV versus plug-in: We agree with the reviewer on these additional helpful insights, and would add them into our discussion in Section 3. Specifically,

• In the "Comparing plug-in and K-fold CV" part, we would add "In terms of the magnitude of bias and interval coverage, plug-in is always no worse than K-fold CV. However, in terms of the direction of bias, plug-in gives an optimistic evaluation of the true model performance, while K-fold CV gives a pessimistic evaluation. In high-stake scenarios where a conservative evaluation is preferred, e.g., evaluating the treatment effect of a new drug, K-fold CV can be more desirable than plug-in. "
• In the "Comparing plug-in and LOOCV" part, we would add "In these cases where LOOCV and plug-in give similar evaluation intervals statistically, plug-in should be preferred as it is computationally much more efficient."

Small issues in theorems: First, we would incorporate your suggestions in Points 4 (change to lemmas), 6, 7, 8.

• For point 1, indeed K can scale with n in the result of Theorem 4, and we would clarify the dependence of K there.
• For point 2, the coverage of $c(z^*)$ is of interest to some problems in stochastic optimization, namely in estimating the optimality gap to decide whether one should stop an optimization algorithm. We have mentioned some of this literature [10, 42, 45, 53, 54] in Appendix A. We would move this related discussion to the exposition after Theorem 2.
• For point 3, indeed Theorem 4 implies Theorem 1. Nonetheless, our Theorem 1 highlights the difference among the three types of estimators with respect to the sample size $n$ and model convergence rate $\gamma_v, \gamma$, which we think is helpful for the reader. We are happy to change and merge Theorems 1 and 4 if the reviewer thinks this would be better.
• For point 5, the general condition in Line 155 is under $\gamma \leq 1/4$. However, the condition in line 156 - 157 is given by $\gamma_v$. Note that $\gamma = \min(\gamma_b, \gamma_v)$, so that equality (i.e., the valid coverage guarantee of the plug-in estimator) holds when $\gamma \leq 1/4$ and $\gamma_v > 1/4$.
• For point 9, we apologize for the confusion in the proof of Theorem 3. First, in terms of Assumption 8, the models we study in this paper are covered in Definitions 1 and 2, while Assumption 8 governs the regularity of the (nonparametric) models under Definition 2. Next, for parametric models, existing theoretical results ([36, 46]) have shown that the bias is of order $\Theta(1/n)$ (since $\gamma = 1/2$ as we mention in Proposition 1) under our assumptions. We would incorporate the missing discussion on the relation with Assumption 8 and in terms of the parametric model in the proof in our revised version.

High-dimensional Investigation: The reviewer certainly raises a good question about high-dimensional investigation. We provide some discussions in the Global Response. Essentially, both plug-in and $K$-fold CV may not perform well in this setting, and while there are works on addressing very specific problems (e.g., linear regression), to our best knowledge it remains an open problem to understand the comparisons among different evaluation methods for general high-dimensional problems.

Lastly, regarding whether empirical risk minimization theory can give insights on the performance of plug-in (even in low dimension), our take is that, as this theory is mostly based on non-asymptotic bounds instead of asymptotically exact results (as we mentioned in Section 6), it could be difficult to know whether CV outperforms plug-in or vice versa. Besides, the performance of nonparametric estimators is not directly revealed from the standard empirical risk minimization theory which mostly focuses on parametric models (though with exceptions). Because of these, CV is still more commonly applied than plug-in, even though as our paper suggests plug-in could be superior when taking into account both statistical and computational benefits.

We thank the reviewer for recognizing the significance of our results and the helpful suggestions. We address the reviewers' main concerns as follows.

Our choice of interval estimate, and not use the interval suggested in [8]: The reviewer raises the valid point that our interval is one particular choice and questions why we don't use the interval in [8]. First, we point out that the interval in [8], namely eq. (9) in [8], which uses nested CV (NCV) in both the point and variance estimates in the interval, is designed for (high-dimensional) parametric models. In contrast, our paper focuses on the distinct setting of nonparametric models, especially in the most challenging slow rate regime. That is, NCV is not designed for, and would not be competitive to our setting. In fact, NCV does not help theoretically and empirically:

• NCV does not offer valid coverages for nonparametric models theoretically: The interval length of NCV is controlled by $\sqrt{MSE}$. Due to the restriction $\sqrt{MSE} \in [SE, \sqrt{K} SE]$ in Sec 4.3.2 in [8] (SE = $\Theta(n^{-1/2})$ is the standard error in their eq. (2)), this interval length is $\Theta(1/n^{1/2})$ for a fixed $K$. In nonparametric models with $\gamma < 1/4$, this length is overly small compared with the bias of NCV being $C n^{-2\gamma}$ (for a constant $C > 0$ smaller than that of eq. (2) in our paper). This is despite that the CV point estimator in [8] used bias correction in their eq. (9), that correction is for parametric models but not nonparametric models. Then the bias in [8] dominates the interval length and leads to an invalid coverage asymptotically.
• NCV does not perform well empirically in our setting: This is expected from the above explanation. We implement NCV with 5 and 10 folds for randomforest in the regression problem (same setting as Figure 1 in our paper), shown in Table 2 of the attached pdf. While the bias of NCV is controllable and the interval gives nearly valid coverage when n is small, the larger bias order starts to exert effect when $n$ is large, leading to a significant drop in the coverage of NCV which becomes invalid.
• NCV is computationally very demanding, requiring over 1000 random splits to stabilize the variance estimate (as mentioned in [8]) and needs to refit in total 1000*K times. Note that [8] does not focus on computation expense as we do in our paper in comparing LOOCV with plug-in.
• [8] does not provide rigorous theoretical guarantees on the valid coverage of their interval (9), even in their own setting. They only correct the variance estimate for parametric models.

We will include the above comparison discussion with NCV in [8] in our future work part, and include the additional numerical results in Appendix in our revised version. In our comparison discussion, we would properly indicate that [8] focuses on a different setting and hence is disadvantageous for ours.

Finally, back to our interval estimate (2), we stress that our choice is natural -- It is widely used with valid statistical properties and outperformance over earlier works as shown in [9]. [8] also considers this natural choice and shows that it performs well under large samples in their experiment (n>400 in Figure 10 in [8]). Our paper and [8] essentially point out two different problems by using (2): [8] corrects the variance estimate in high dimension but parametric models while we show that this interval does not yield valid coverage for nonparametric models with slow rates.

Code Reproducibility: We apologize for not documenting the code well previously. We now provide clean documentation on the experimental configuration for reproducibility and also change the default solver to CVXOPT (open source package). Here is the anonymous link to our revised code: Link.

Empirical results using different fold numbers: We have shown 5-CV results for the regression problem in Table 5, and newsvendor problem in Table 7 in the paper. To alleviate further the reviewer's concern, we now also provide additional results of 5, 10, 20-CV for regression and portfolio tasks for more sample sizes in Table 1 of the attached pdf. We will include them in our revised version and use 5-CV throughout the main body. As shown in these results, larger K still suffers from coverage problems when n is large, even though it can help when $n$ is small. These continue to support the validity of our theoretical results.

Results on different dimensional problems: As other reviewers mention, our main contribution and novelty are for the asymptotic regime with $n\to\infty$ and fixed $p$. This corresponds to most classical CV papers with statistical guarantees [5,6,9]. The models we choose, i.e., linear models, kNN, randomforest are common under this setup. Correspondingly, our empirical results are used to validate theoretical results in this regime. Nonetheless, we provide discussions on the high-dimensional case (including p > n) in the Global Response, but we politely point out that this is not our main focus and is worth a separate substantial work on its own (as Reviewer tGmJ also hints).

Other suggestions: We use the question form in the title because the answer is not clear-cut - LOOCV is indeed the best statistically but computationally expensive. We will incorporate other great suggestions from the reviewer in our revised paper.

Optimistic versus Pessimistic Bias: Optimistic bias refers to underestimating the expected cost. Plug-in suffers such bias since it is evaluated on the same training data. In contrast, pessimistic bias refers to overestimating the expected cost. CV suffers such bias since CV is unbiased for the evaluation using fewer training samples than the whole dataset, and appears more erroneous than it should be compared to the true evaluation using the whole dataset. We will incorporate this discussion after stating the current Theorems 1 and 2.

We sincerely thank you for your recognition of the importance and clarity of our paper, and also for your very helpful comments. To respond to your main suggestions, we have run additional experiments on model selection and real-world data set. These experimental results will be incorporated into the Appendix. There we will also provide additional discussion on model selection that we leave for future work, which we reveal below as well.

Model Selection

A difference between model selection and the model evaluation task we focus on in this paper is that in the former, we focus on the performance rank between different models instead of the absolute performance value. Intuitively, the accuracy of the performance rank depends on not only the evaluations of the compared models, but also the inter-dependence between these evaluation estimates. This adds complexity to understanding the errors made by each selection approach. There are some discussion for specific problems, such as linear regression, classification and density estimation (see, e.g., Section 6 of our reference [3]). However, the theoretical understanding of model selection remains wide open in general problems.

That being said, there are some model selection problems where plug-in easily leads to a naive selection:

• Selecting hyperparameters: Consider the best regularized parameter $\alpha$ in the ridge regression. Plug-in always chooses $\alpha = 0$ since it has the smallest training loss.
• Selecting the best model class: Consider the regression problem $\hat f \in argmin_{f \in F_i} \sum_i^n (f(X_i) - Y_i)^2$ for the nested classes $F_1 \subset F_2 \subset F_3$, and we want to select the best $F_i$ among the three classes. Plug-in always selects the largest class, $F_3$, since it has the smallest training loss.

In these problems, CV can select the regularization parameter or model class different from the naive choice. It hints that CV could be better than plug-in for such problem, but this is theoretically not well-understood. Per the reviewer's suggestions, we include some simulation experiments on model selection using plug-in versus CV as follows, where in each case we report the result averaged over 100 experimental repetitions:

Case 1: Select the hyperparameter in ridge regression

Suppose we have a "misspecified" linear data generating process: $Y = \sum_i^{50}(X^{(i)} + sin(X^{(i)})) + \epsilon$ with $X^{(i)}$ being the $i$-th component of $X$ and $\epsilon \sim U(0, 1)$. We want to find the best hyperparameter $\alpha$ from the regularized linear models $\beta_{\alpha} \in argmin_{\beta} (Y_i - \beta^{\top}X_i)^2 + \alpha ||\beta ||^2$ that minimizes the expected cost $E[(Y - \beta_{\alpha}^{\top}X)^2]$. We show the model selection results in the following table, where the first column of each procedure represents the best $\alpha$ that the procedure finds and the second column represents the true cost under such $\alpha$:

When $n$ is small, both 5-CV and LOOCV find a better decision than the plug-in. but the accurate evaluation of LOOCV does not necessarily yield a better selection than 5-CV (e.g. $n = 100$). Plug-in always chooses $\alpha = 0$ and its relative performance depends on the power of regularizations, i.e., when $n = 200$, adding $\alpha$ does not improve much and thus the performance of plug-in to both 5-CV and LOOCV. However, when $n = 80, 100$, plug-in suffers from worse performance than 5-CV and LOOCV.

Case 2: Select the best model class

Given each $D_n$, we want to select the best among ridge, kNN, and random forest models. Continue the same data process as Case 1, but with 10 features. In each experimental repetition, we select $\lambda \sim U(0, 5)$ randomly and generate data from $Y|X: \sum_i^{10} X^{(i)} + \lambda sin(X^{(i)}) + \epsilon$. We show the results of model selection procedures, where the first column of each procedure represents the probability of finding the correct best model, and the second column represents the true cost under the model selected by each procedure:

Real-world Experiments

We include one real-world dataset puma32H with 33 features and 1000000 samples as a regression task. The codes and instructions for reproducing are in the updated codebase link in the Global Response. We report the coverage probability of plug-in, 2-CV, and 5-CV for a kNN model with $k_n = n^{2/3}$, where each entry denotes the coverage probability estimated over 100 experimental repetitions for that procedure. Each experimental repetition is conducted differently by shuffling the entire dataset. We then select the first n rows as the training sample for each model and approximate the true model performance by averaging over the remaining samples in the dataset.

Plug-in provides valid coverages in this case while 2-CV, 5-CV do not, especially when $n$ is larger (20000 and 40000). These continue to validate our asymptotic theory.

Scaling of the Variance: In equation (2), each datapoint $(x_i, y_i)$ is only used once for evaluation since the index of each datapoint is only counted once in one of $\{N_k, k \in [K]\}$, the collection of $K$ partitions of $[n]$. Note that this formula is the same as the standard all-pairs variance estimator in Theorem 5 in the reference [9].

We sincerely thank the reviewer for recognizing our contributions and clarity, and also for raising the list of very helpful questions.

Regarding "Weaknesses":

Difference with literature investigating roles of CV: First, the reviewer mentions that [8] says CV estimates the risk of the algorithm which explains the poor performance of CV for estimating $c(\hat z)$. However, [8] is mostly interested in parametric models, where the difference between $c(\hat{z})$ and $E[c(\hat{z})]$ (or $c(z^*)$) is generally of order $O_p(1/n)$ and negligible compared with the variability, as we mentioned in Section 1 and 3. Therefore, CV still yields valid coverage guarantees for these parametric models. On the other hand, it is unknown when such bias is significant and leads to invalid coverages in general nonparametric models which is our main focus and novelty.

The reviewer also indicates correctly that recent literature [6,9] say that CV accurately estimates the averaged performance and provides valid coverage guarantees for this quantity. However, like above, it is unclear when the difference between such an averaged performance and true model performance affects the coverage guarantee for general nonparametric models.

Notations: We will change the notation $z$ to $\tilde z$ when referring to the prediction domain.

Regarding "Questions":

Overparametrized-regime: We assume the dimension is fixed and the sample size goes to infinity in this paper. We agree with you that the plug-in estimator would be zero under overparametrized-regime. However, whether CV would perform better in that regime is still an open question (e.g., K-fold CV does not perform well in our additional experiments; please refer to more details on the high-dimensional case in our Global Response).

Examples under given conditions: $\alpha_n = o(n^{-1/2})$ is satisfied for general random forest and kNN learners from the algorithmic stability literature [14,15,40] discussed in our paper. Moreover, we provide the exact formula of $\gamma_v, \gamma_b$ ($\gamma = \min(\gamma_v, \gamma_b)$) for each learner in Examples 3 and 4 in Section 3. Specifically, in regression problems, $\gamma \leq 1/4$ is satisfied for general nonparametric models (including kNN learners in Example 3, Forest learner in Example 4, kernel estimators in Example 7) as long as $d_x \geq 2$ from Lemma 3 of Appendix B.

Algorithmic evaluation task: We agree that algorithmic evaluation is also an important and related task. Our paper focuses on model evaluation but our analysis can shed light on constructing intervals for algorithmic evaluation, especially when the difference of the two targeted intervals is relatively small. In Corollaries 1 and 2 in Appendices E.1.4 and E.2 of our paper, when $\gamma > 1/4$, both plug-in and CV intervals (1) and (2) (regardless of $K$-fold or LOOCV) provide valid coverages for $E_{D_n}[c(\hat z)]$; Otherwise when $\gamma \leq 1/4$, for LOOCV, since $\sqrt{n}(\hat A_{loocv} - c(\hat z))\overset{p}{\to} N(0, \sigma^2)$ and $c(\hat z) = E_{D_n}[c(\hat z)] + O_p(\sqrt{Var_{D_n}[c(\hat z)]})$, the LOOCV interval (2) is valid for covering $E[c(\hat z)]$ when $Var_{D_n}[c(\hat z)] = o(1/n)$; For plug-in, the condition for the coverage validity for $E[c(\hat z)]$ is equivalent to $Var_{D_n}[c(\hat z)] = o(1/n)$ and $\gamma_v > 1/4$. However, it appears open whether there is a more explicit model rate representation for $Var_{D_n}[c(\hat z)] = o(1/n)$.

Sample Splitting: We agree with you that such sample splitting gives an accurate evaluation for the model trained with $n/2$ samples. However, we are interested in the model trained with a full set of samples $\hat z(x) = A(D_n;x)$. The expected costs of these two models differ by $\Theta(n^{-2\gamma})$ due to the performance gap when using $n$ versus $n/2$ samples, which is similar to the evaluation bias using 2-fold CV. When $\gamma < 1/4$, the difference is $\omega(n^{-1/2})$, which is large and exceeds the interval length (of order $\Theta(n^{-1/2})$). That is, the interval used to evaluate the model with $n/2$ samples cannot provide valid coverage guarantees for $c(\hat z)$.

Guidance to practitioners:

First, in terms of the magnitude of bias, LOOCV is always smaller than plug-in, while plug-in is no larger than K-fold CV. Despite this bias ordering, the adoption of a method over another should also take into account the variability and computational demand, specifically:

• For parametric models, and nonparametric models with a fast rate ($\gamma > 1/4$, which includes sieves estimators in our reference [18] when the true function $f(x)$ is 2$d_x$-th continuously differentiable in our Examples in Line 198-202), biases in all three considered procedures, plug-in, LOOCV and K-fold CV, are negligible compared to the variability captured in interval coverage. Correspondingly, all three intervals provide valid statistical coverages. Among them, plug-in is the most computationally efficient and should be preferred.
• For nonparametric models with a slow rate but small variability ($\gamma_v > 1/4, \gamma \leq 1/4$), which include kNN with $k_n = \omega(\sqrt n)$ in Example 3 and the forest learner in Example 4 in our paper, the biases in plug-in and LOOCV are negligible but K-fold is not. Correspondingly, both plug-in and LOOCV provide valid coverages but $K$-fold CV does not. Since plug-in is computationally much lighter than LOOCV, it is again preferred.
• For nonparametric models with slow rate ($\gamma_v \leq 1/4$), which include kNN with $k_n = \Theta(\sqrt n)$ in Example 3, only LOOCV has a negligible bias and provides valid coverages, and hence should be adopted.

The above being said, we caution that, in terms of the direction of bias, plug-in is optimistic while K-fold CV is pessimistic, and so the latter could be preferred if a conservative evaluation is needed to address high-stake scenarios (as Reviewer tGmJ suggests).