Is Cross-validation the Gold Standard to Estimate Out-of-sample Model Performance?

Authors: garud  iyengar
henry  lam
tianyu  wang
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 04:13:59

Abstract: Cross-Validation (CV) is the default choice for estimate the out-of-sample performance of machine learning models. Despite its wide usage, their statistical benefits have remained half-understood, especially in challenging nonparametric regimes. In this paper we fill in this gap and show that, in terms of estimating the out-of-sample performances, for a wide spectrum of models, CV does not statistically outperform the simple ``plug-in'' approach where one reuses training data for testing evaluation. Specifically, in terms of both the asymptotic bias and coverage accuracy of the associated interval for out-of-sample evaluation, $K$-fold CV provably cannot outperform plug-in regardless of the rate at which the parametric or nonparametric models converge. Leave-one-out CV can have a smaller bias as compared to plug-in; however, this bias improvement is negligible compared to the variability of the evaluation, and in some important cases leave-one-out again does not outperform plug-in once this variability is taken into account. We obtain our theoretical comparisons via a novel higher-order Taylor analysis that dissects the limit theorems of testing evaluations, which applies to model classes that are not amenable to previously known sufficient conditions. Our numerical results demonstrate that plug-in performs indeed no worse than CV in estimating model performance across a wide range of examples.

Main paper: 
 introduction: 
 Cross-validation (CV) is considered the default choice for estimating the out-of-sample performance of machine learning models [54, 31, 4] and more general data-driven optimization models [13] . Its main rationale is to evaluate models using a testing set that is different from training, so as to provide a reliable estimate of the model generalization ability. Leave-one-out CV (LOOCV) [5, 7] , which repeatedly evaluates models trained using all but one observation on the left-out observation, is a prime approach; however, it is computationally demanding as it requires model re-training for the same number of times as the sample size. Because of this, K-fold CV, which reduces the number of model re-training down to K times (where K is typically 5-10), becomes a popular substitute [34, 42] .Despite their wide usage, the statistical benefits of CV have remained understood mostly for parametric models. In nonparametric regimes, especially those involving slow model convergence rates, their general performances as well as comparisons with the naive "plug-in" approach, i.e., simply reuses all the same training data for model evaluation, stay essentially open. Part of the challenge comes from the subtle inter-dependence of model convergence rates and other characteristics with Figure 1 : Evaluation biases and coverage probabilities of interval estimates (with nominal level 90%) for the mean-squared error evaluation of a fitted random forest regressor (default setup in scikit-learn in [49] with n 0.4 subsamples in each tree), across 500 experimental replications. The bar chart shows the evaluation bias, defined as the absolute mean difference between the estimated and true performance (the vertical line at the top of each bar shows the corresponding standard error). The lines show the coverage probabilities.the correlation between training and validation sets across folds. Consequently, existing results are either based on limit theorems designed to "center" at the average-of-folds instead of full-size model [60] , or restricted to specific models (e.g., linear) [7, 9] or specific (fast) rates [57] . Our goal in this paper, on a high level, is to fill in the challenging regimes beyond these established results, and as such answer the question: Are LOOCV and K-fold CV a "must-use" in estimating out-of-sample model performance in general and, if not, then under what situations are they worthwhile?More precisely, in this paper we conduct a systematic analysis to compare the accuracies in estimating model performances using LOOCV, K-fold CV and plug-in. We focus on the asymptotic bias and coverage accuracy of the associated interval estimate for the out-of-sample evaluation. Our main messages are: First, in terms of these asymptotic criteria, K-fold CV never outperforms plug-in, regardless of the rate at which a parametric or nonparametric model converges. Second, while LOOCV can have a smaller bias than plug-in, this bias improvement can be negligible compared to the evaluation variability and therefore, in a range of important cases, LOOCV again does not outperform plug-in. In particular, we show that all parametric models, as well as some nonparametric models including random forests and kNN with sufficient smoothness, fall into this range. Since LOOCV requires significantly more computation resources, this raises the caution that its use is not always necessary, despite its robust performance for model evaluation.As a simple illustration, Figure 1 shows the evaluation quality of the squared error of a random forest regressor using 2-fold CV, 5-fold CV, LOOCV and plug-in. We see that 2-and 5-fold CVs suffer from larger biases than plug-in (shown in the bar chart) especially for large sample sizes, and correspondingly also significantly poorer coverages of the associated interval estimates (shown by the lines). On the other hand, LOOCV exhibits smaller biases than plug-in, but these do not transform into better coverages since the bias improvement is negligible compared to the statistical variability in the evaluation. Both intervals provide valid coverage guarantees for large sample sizes (shown by the lines). We highlight that this example is not a "cherry pick": Section 5 and Appendix F show similar conclusions for a wide array of numerical examples.We close this introduction by briefly discussing our technical novelty. Our analysis framework to conclude all our comparisons is propelled by a novel higher-order Taylor analysis on the out-ofsample evaluation that account for the dependence between the trained model and the testing data. In contrast to merely sufficient conditions in the literature, under which plug-in and CV variants exhibit low biases and valid coverages, 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.Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?Answer: [Yes] Justification: The abstract and introduction in Section 1 clearly state the claims made with important assumptions and limitations. The claims are supported by a matched theoretical result in Section 3 and experimental results in Section 5.Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
problem framework: 
 We consider the supervised learning setting with observations D n := {(X i , Y i )} i∈[n] drawn i.i.d. from the joint distribution P (X,Y ) := P X × P Y |X . We obtain a predictor ẑ(x) = A(D n ; x) as a function of x with the output domain Z, through a training procedure A on D n . We are interested in evaluating the out-of-sample performance E P (X,Y ) [ℓ(ẑ(X); Y )], where ℓ(z; Y ) : Z × Y → R is the cost function. This evaluation can be a point estimate, or more generally an interval estimate I(α) that covers E P (X,Y ) [ℓ(ẑ(X); Y )] with 1-α probability, i.e., we aim to satisfy P Dn (E P (X,Y ) [ℓ(ẑ(X); Y )] ∈ I(α)) ≈ 1 -α, where the outer probability P Dn is with respect to the data D n used to construct ẑ(•). We focus on the low-dimensional asymptotic setting where n → ∞ and X , Y, Z are of fixed dimensions and defer discussions to other regimes in Section 6.Regarding the scope of our setup, ℓ can be the loss function for supervised learning (e.g., squared loss, cross-entropy loss), in which case ẑ naturally denotes the predicted label and (X, Y ) denotes the feature-label pair. More generally, ℓ can denote a downstream optimization objective in a decisionmaking problem, in which case Y denotes a random outcome that affects the objective given the contextual information X. This latter setup, which is called contextual stochastic optimization [13, 51] , can be viewed as a generalization of supervised learning from building prediction models to prescriptive decision policies. For example, in the so-called newsvendor problem in operations management, the cost refers to monetary loss of a retailer determined by the order quantity z, and covariate X refers to the market condition that drives stochastic demand Y [8, 13] . Our framework in this paper applies to both the traditional supervised learning and prescriptive data-driven decisionmaking settings.We consider three main methods: plug-in, LOOCV, and K-fold CV. We denote Âm and I m (α) as the point estimate and (1 -α)-level interval estimate, using method m ∈ M = {p, loocv, kcv} referring to plug-in, LOOCV and K-fold CV respectively. For convenience, we denote P * as the true joint distribution P (X,Y ) and Pn = (1/n) n i=1 δ (Xi,Yi) as the empirical distribution, and we denote c(z) and c n (z) as the out-of-sample performance E P * [ℓ(z(X); Y )] and the plug-in evaluation of the out-of-sample performance E Pn [ℓ(z(X); Y )] for any decision mapping z(x) respectively. We present our considered point and interval estimates, where the latter are all written in the formI m (α) = [ Âm -z 1-α/2 σm / √ n, Âm + z 1-α/2 σm / √ n], ∀m ∈ M with:EQUATIONEQUATIONwhere z 1-α/2 is the (1 -α/2)-quantile of the standard normal distribution, {N k , k ∈ [K]} is the collection of K equal-length partitions of [n] (for simplicity we assume n is divisible by K) and ẑ(-N k ) (•) := A(D (-N k ) ; •), with D (-N k ) denoting the data set that leaves out {(X i , Y i )} i∈N k .For the K-fold CV estimates, Âkcv and I kcv , we always assume K is fixed with respect to n (e.g., K = 2, 5, 10). On the other hand, Âloocv and I loocv (α) are defined by setting K = n in (2) . Note that there are alternative approaches to construct the interval estimates (e.g., nested cross validation in Appendix G.3), but the above are the most natural and have been shown to have statistical consistency properties as well as superior empirical performance over other intervals [10] .We impose the following regularity and optimality conditions on the cost function:Assumption 1 (Smoothness of Expected Cost) For any x ∈ X , v(z; x) := E P Y |x [ℓ(z; Y )] is twice differentiable with respect to z everywhere, where P Y |x is the conditional distribution of Y given x.Assumption 2 (Regularity of Cost Function) For any y ∈ Y, ℓ(z; y) is twice differentiable with respect to z for every y. Moreover, |ℓ(z; y)|, ∥∇ z ℓ(z; y)∥ 2 are uniformly bounded in z ∈ Z and almost surely in y.Assumption 3 (Optimality Conditions) Z is a bounded open set. The best mapping z * o (x) that minimizes v(z; x), ∀x ∈ X satisfies the first and second-order optimality conditions. More precisely, ∀x ∈ X , ∇ z v(z * o (x); x) = 0, and ∇ zz v(z * o (x); x) is positive definite.While Assumption 2 is standard, we can relax it further to some non-smooth objectives including piecewise linear functions (e.g., ℓ(z; Y ) = |z -Y |); see Assumption 5 in Appendix B.2. The other assumptions above are commonly used in stochastic optimization [25, 29, 38] . We further allow constrained problems in Assumption 6 in Appendix B.2. Next, we distinguish between parametric and nonparametric models in Definitions 1 and 2 below, leaving further details on technical regularity conditions in Appendix B. 3 .Definition 1 (Parametric Model) ẑ(x) = G( θ; x), where θ = argmin θ∈Θ n i=1 ℓ(G(θ; X i ); Y i ) + λ n R(θ) for some regularization function R(θ). Regularity conditions of G(θ; X) are provided in Assumption 7 in Appendix B. 3 .1, which are satisfied by linear models (Example 2 of Section 3). Definition 2 (Nonparametric Model) ẑ(•) is obtained through ẑ(x) ∈ argmin z∈Z i∈[n] w n,i (x)ℓ(z; Y i ) with weights {w n,i (x)} i∈[n]∈ (0, 1/2] if E Dn [∥ẑ(x) -z * (x)∥ 2 ] = Θ(n -γ )for almost every x. Furthermore, we say ẑ(•) has a bias and variability convergence rateγ b , γ v respectively if E Dn [∥E Dn [ẑ(x)] -z * (x)∥ 2 ] = Θ(n -γ b ) and E Dn [∥ẑ(x) -E Dn [ẑ(x)]∥ 2 ] = Θ(n -γv ) for almost every x. Consequently, γ = min{γ b , γ v }.The overall convergence order γ of ẑ(•) is determined by both its bias γ b and variability γ v , whichever dominates. For parametric models in Definition 2, we naturally have γ = γ v = 1/2 (see Proposition 1 in Appendix B.EQUATIONEQUATIONwhere the expectation in (3) is with respect to both the data D n , used to construct ẑ and ẑ(-i) , and P * that generates X, while (4) has expectation taken with respect to only D n .Stability notions are first proposed in [15, 28, 45] and commonly used to provide generalization guarantees for CV [37, 39] as well as refined bounds under more relaxed stability in [16, 1, 2] . We assume the following:Assumption 4 (LOO Stability) ẑ(•) satisfies the expected LOO stability with α n = o(n -1/2 ).This condition holds for many models in Definitions 1 and 2 [15, 28, 17] and is often imposed for the validity of plug-in and CV, e.g. in [10, 18] . For illustration, we provide an example of 1-NN in Appendix B.4.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes]Justification: The paper discusses the strength of assumptions when they are imposed in Section 2 and provides concrete examples in Appendix B to elaborate on these assumptions. This paper also discusses the limitations of the general setup from the asymptotic perspective and scope of model evaluation instead of model selection in Section 6.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach. For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
main results: 
 We present our main results on the evaluation bias and interval coverage for plug-in, K-fold CV and LOOCV. Unless specified otherwise, E and P in the following are taken with respect to D n .Theorem 1 (Bias) Suppose Assumptions 1, 2, 3 and 4 hold. Recall γ, γ v in Definition 3. Then, for ẑ(•) in Definitions 1 and 2:E[c(ẑ) -Âp ] = Θ(n -2γv ) > 0, E[c(ẑ) -Âkcv ] = Θ(n -2γ ) < 0, E[c(ẑ) -Âloocv ] = o(n -1 ) < 0.Theorem 2 (Coverage Validity) Suppose Assumptions 1, 2, 3 and 4 hold. Recall M = {p, kcv, loocv}. Then, for ẑ(•) and z * (•) in Definitions 1 and 2:• If γ > 1/4, then: lim n→∞ P(c(ẑ) ∈ I m ) = lim n→∞ P(c(z * ) ∈ I m ) = 1 -α, for m ∈ M. • If γ ≤ 1/4, then lim n→∞ P(c(z * ) ∈ I m ) < 1 -α for m ∈ M.lim n→∞ P(c(ẑ) ∈ I p ) ≤ 1 -α, where equality holds if and only ifβ n = o n -1/2 (or γ v > 1/4). -lim n→∞ P(c(ẑ) ∈ I kcv ) < 1 -α. -lim n→∞ P(c(ẑ) ∈ I loocv ) = 1 -α.In the following, we use Theorems 1 and 2 to compare plug-in, K-fold CV and LOOCV, and highlight our novelty relative to what is known in the literature. In a nutshell, the regime γ ≤ 1/4 has been wide open and comprises our major contribution and necessitates our new theory described in Section 4.Comparing plug-in and K-fold CV. Theorems 1 and 2 together stipulate that plug-in is always no worse than K-fold CV in terms of estimating out-of-sample performance. In terms of evaluation bias, plug-in is optimistic while K-fold CV is pessimistic. For such a bias direction, optimistic bias refers to underestimating the expected cost. Plug-in suffers such bias since it is estimated 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. For parametric models, since γ = γ v = 1/2, their biases in Theorem 1 are both Θ(n -1 ). This recovers the results in [30, 36] in which case the bias is negligible when constructing intervals. However, this bias size is unknown for general nonparametric models in the literature. For these models, our new results show that the bias of plug-in is Θ(n -2γv ) which is no bigger than that of K-fold CV since γ ≤ γ v . This behavior arises because, even though plug-in incurs an underestimation of Θ(n -2γv ) due to the reuse of training and evaluation set, K-fold CV loses efficiency due to a loss of training sample from the data splitting, thus leading to an even larger bias of Θ(n -2γ ).The above comparisons are inherited to interval coverage. While plug-in and K-fold CV both exhibit asymptotically exact coverage for parametric models (included in the case γ > 1/4), their coverages differ for nonparametric models, with plug-in still always no worse than K-fold CV. Specifically, when γ ≤ 1/4, K-fold CV incurs invalid coverage, whereas plug-in still yields valid coverage as long as γ v > 1/4. This is because, in this regime, the bias of K-fold CV is bigger than its variability to affect coverage significantly while the bias of plug-in remains small enough to retain coverage validity. In the literature, [21, 18] show valid coverage using plug-in under some stability conditions, but it is unclear regarding their applicability to general models. On the other hand, for CVs, central limit theorems and hence coverage guarantees have been derived generally, but they are centered at the average performance of trained models across folds [42, 10, 26] , and thus bear a gap between such an averaged performance and the true model performance. Recently, [56, 7] further show CV intervals can provide coverage guarantees when γ > 1/4, but they do not touch on the case γ ≤ 1/4. Moreover, all the literature above do not demonstrate an explicit difference between K-fold and LOOCV in their results [7, 57, 10] . From these, our results on the regime γ ≤ 1/4 where we characterize and conclude the difference between K-fold and LOOCV appear the first in the literature.Comparing plug-in and LOOCV. When comparing with plug-in, LOOCV has a smaller, and pessimistic, bias o(1/n). However, this bias improvement can be negligible compared to the evaluation variability captured in interval coverage, specifically when γ > 1/4 (which includes all parametric models) and when γ ≤ 1/4, γ v > 1/4. In the latter case in particular, the bias of plug-in, even though larger than LOOCV, is small enough to ensure valid coverage.We visually summarize our discussions on biases and interval coverages in Figure 2 . In particular, Figure 2 (a)(b) display our new contributions on both plug-in and CVs under slow rate γ. We also see that plug-in intervals provide valid coverages for (b)(c), while K-fold CV is only valid for (c) and LOOCV is valid across(a)(b)(c). -∞ ∞ -∞ ∞ Plug-in K-fold CV LOOCV -∞ ∞ (a) 𝜸 𝒗 ≤ 𝟏 𝟒 (b) 𝜸 𝒗 > 𝟏 𝟒 , 𝜸 𝒃 ≤ 𝟏 𝟒 (c) 𝜸 𝒗 , 𝜸 𝒃 > 𝟏 𝟒𝒄(𝒛 * ) 𝒄(% 𝒛) Examples. We exemplify the above insights with several specific models. Denote d x , d y as the dimensions of X and Y . We consider a regression problem with ℓ(z; Y ) = (z -Y ) 2 and d x = 4, d y = 1, where P * ∈ P with:EQUATIONWe consider the worst-case instance of P * , in the sense that γ b , γ v take the smallest attainable values in Chapter 3 of [33] .Example 2 ((Regularized) Linear-ERM [8] )G(θ; x) = θ ⊤ x, λ n = 1, R(θ) = ∥θ∥ 2 2 satisfy As- sumption 1. Specifically, γ = γ v = 1/2,and all of plug-in, K-fold CV and LOOCV provide valid coverages for c(ẑ).Example 3 (kNN-Learner) Denote the nearest index set N Dn,x (k n ) = {i|X i is a kNN of x}. Then w n,i (x) = 1 {i∈N Dn ,x (kn)} satisfies Assumption 2 with hyperparameter k n . Specifically, γ v = -log k n /(2 log n) and γ b = log(k n /n)/(4 log n) (from Chapter 6 in [33]). If k n = ω( √ n), then LOOCV and plug-in provide valid coverages for c(ẑ); otherwise, only LOOCV provide valid coverages.Example 4 (Forest Learner) Consider a forest F = {τ 1 , . . . , τ T }, where each τ i : R dx → {1, . . . , L i } is a (tree) partition of R dx into L i regions. Then w n,i (x) = T j=1 1 {τj (Xi)=τj (x)} /T satisfies Assumption 2, where the hyperparameter is the subsampling ratio β < 2/3 in each tree. Specifically, γ v = (1 -β)/2 from [57] and γ b < 1/6 (from Lemma 5 in Appendix B.1). Then LOOCV and plug-in provide valid coverages for c(ẑ).We summarize our theoretical comparisons in this section in Table 1 , the first half of which shows our general comparisons in terms of both evaluation bias and interval coverage, while the second half illustrates our considered examples. Specifications c(ẑ) -Âp c(ẑ) -Âkcv c(ẑ) -Âloocv Ip I kcv I loocv General γ > 1/4 o(n -1/2 ) o(n -1/2 ) o(n -1 ) ✓ ✓ ✓ γ b ≤ 1/4, γv > 1/4 o(n -1/2 ) ω(n -1/2 ) ✓ ✗ ✓ γv ≤ 1/4 Ω(n -1/2 ) Ω(n -1/2 ) ✗ ✗ ✓ Specific dx = 4 Linear-ERM Θ(n -1 ) Θ(n -1 ) o(n -1 ) ✓ ✓ ✓ kNN with kn = Θ(n 1/4 ) Θ(n -1/8 ) Θ(n -1/8 ) ✗ ✗ ✓ kNN with kn = Θ(n 2/3 ) Θ(n -2/3 ) Θ(n -1/12 ) ✓ ✗ ✓ Forest with β = 0.4 Θ(n -0.3 ) ω(n -1/6 ) ✓ ✗ ✓Finally, we point out that Theorem 2 also shows, in addition to our evaluation target c(ẑ), the coverage on the oracle best performance c(z * ). The latter is generally a different quantity than c(ẑ), but it plays an important role in our analysis. When γ > 1/4, c(ẑ) and c(z * ) are very close and an interval for c(ẑ) is also valid to cover c(z * ). On the other hand, when γ ≤ 1/4, the statistical discrepancy between c(ẑ) and c(z * ) is too large for any interval estimates of c(ẑ) to be valid for c(z * ), but nonetheless LOOCV and plug-in for γ v > 1/4 can still validly cover c(ẑ) thanks to their small evaluation biases.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer: [Yes]Justification: The paper provides the full set of assumptions in Section 3 and some additional regularity conditions in Appendix B with reference in the main body. For every important theoretical result, we provide the proof sketch and intuition when we state each of them. And we leave other theoretical statements and all the complete proofs in Appendix C, D and E.Guidelines:• The answer NA means that the paper does not include theoretical results.• All the theorems, formulas, and proofs in the paper should be numbered and cross-referenced.• All assumptions should be clearly stated or referenced in the statement of any theorems.• The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition. • Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced. 
roadmap of theoretical developments: 
 We present the main theoretical ideas to show Theorems 1 and 2. Before going into details, we highlight the main novelties of our analyses: First, the biases for general nonparametric models in Theorem 1, which are unknown in the literature, require a different Taylor analysis compared with the parametric case available in [30] . Second, parts of Theorem 2 come from verifying the central limit theorems (CLTs) in [18, 10] . However, [18] only shows that CLTs hold for c(ẑ) when α n , β n = o(n -1/2 ) and does not show exactly when CLT fails; [10] only gives CLTs for CVs with a different center than c(ẑ), c(z * ). In this regard, our main technical contribution is to fill in these theoretical gaps and characterize necessary conditions, instead of merely sufficient conditions, to conclude interval (in)validity across the entire spectrum.One key component of Theorem 1 hinges on the characterization of optimistic bias for plug-in, namely E Dn [c n (ẑ) -c(ẑ)], which captures the underestimation amount of the objective value relative to the truth when using an empirical estimator:Lemma 1 (Plug-in Bias) Suppose Assumptions 1, 2, 3 and 4 hold. Forẑ(•) in Assumption 2, E Dn [c n (ẑ)] -E Dn [c(ẑ)] = Θ(n -2γv ) < 0.The proof of Lemma 1 relies on a novel second-order Taylor expansion centered at the deterministic decision z n (x) := E[ẑ(x)] on both the empirical gap c n (ẑ) -c n (z n ) and the true gap c(z n ) -c(ẑ) in nonparametric models ẑ(•). Here, we do not center them at the limiting decision z * (x) compared with the parametric setup from [4, 36] since in nonparametric models, ẑ(•) -z n (•) already captures the variability term that leads to the plug-in evaluation bias. Besides, in these nonparametric models, we need to further analyze the second-order difference E[∥ẑ(x) -z n (x)∥ 2 2 ] and E[∥ẑ(X i ) -z n (X i )∥ 2 2 ], which requires a more involved analysis through a comparison on the asymptotic expansion terms of ẑ(•) -z n (•). To understand the optimistic bias further, we provide a constructive proof for kNN with an optimistic bias Θ(1/k n ) in Proposition 4 in Appendix D.1.The results for CVs follow from the observation that K-fold CV (where here K can be any number up to n) gives an unbiased evaluation for the model trained with n(1 -1/K) samples: Lemma 2 (CV Bias) Suppose Assumptions 1, 2, 3 and 4 hold. For ẑ(•) in Definitions 1 and 2,E Dn [ Âkcv ] -E Dn [c(ẑ)] = Θ(K -1 n -2γ ) > 0, E Dn [ Âloocv ] -E Dn [c(ẑ)] = o(n -1 ) > 0.The proof of Theorem 2 hinges on the following equivalences of conditions among stability, convergence rate, and coverage validity. For plug-in, we have: Theorem 3 (Equivalence among Stability, Convergence Rate and Coverage Validity for Plug-in) Suppose Assumptions 1, 2, 3 and 4 hold. Then the following three conditions are equivalent:S1 : β n = o(n -1/2 ), S2 : lim n→∞ P(c(ẑ) ∈ I p ) = 1 -α, S3 : γ v > 1/4.Theorem 3 is shown through three components of arguments, where the first two are our new technical contributions:(1) S3 is sufficient for S1. Intuitively, a faster rate of γ v means that the effect of one data point is usually small, implying a fast pointwise stability. This result follows from a refined decomposition of the variability term ẑ(x) -ẑ(-i) (x) through the influence of each point based on the asymptotic expansions of ẑ(•) in Assumption 2. We examine its bias and variability respectively, with formal results provided in Proposition 5 in Appendix E.1.1.(2) S3 is necessary for S2. Since the variability of the interval width does not differ significantly (Lemma 7 in Appendix C), only the bias would lead to interval invalidity. From Lemma 1, if S3 does not hold, i.e., γ v ≤ 1/4, then E Dn [c n (ẑ) -c(ẑ)] = Θ(n -1/2 ) and this implies that S2 does not hold from Proposition 6 in Appendix E.1.2.(3) S1 is sufficient for S2. This follows from a direct verification of Lemma 2 in [18] to ensure asymptotic normality for plug-in and the small variability of the interval width (Lemma 7 in Appendix C). Furthermore, due to a small difference between c(ẑ) and c(z * ) (Lemma 6 in Appendix C), the plug-in interval can also cover the quantity E Dn [c(ẑ)] and c(z * ) if γ > 1/4 (i.e. Corollary 1 in Appendix E.1.4).In the above, we show that the condition β n = o(n -1/2 ) or γ v < 1/4 is a necessary and sufficient condition to ensure a valid plug-in interval if Assumption 4 holds. Note that [18] demonstrate that in a specific nonparametric model, Assumption 4 is a necessary condition for the coverage invalidity of plug-in by providing a counterexample (Lemma 3 there). Our results are not directly comparable to theirs. First, we assume Assumption 4 throughout the entire paper and show that plug-in does not provide valid coverage guarantees when another stability notion, β n , is large. Second, our results apply to a more general class of nonparametric models in Assumption 2 instead of the particular models and cost functions ℓ in [18] .Theorem 4 (Equivalence between Convergence Rate and Coverage Validity for CV) Suppose Assumptions 1, 2, 3 and 4 hold. Then for K-fold CV, the following two conditions are equivalent:S4 : γ > 1/4, S5 : lim n→∞ P(c(ẑ) ∈ I kcv ) = 1 -α.For LOOCV, we always have lim n→∞ P(c(ẑ) ∈ I loocv ) = 1 -α. However,lim n→∞ P(c(z * ) ∈ I m ) < 1 -α, ∀m ∈ {kcv, loocv} if γ ≤ 1/4.To understand the necessary condition for K-fold CV, since γ is small, the difference between the expected performance between the decision ẑ(x) and ẑ(-N k ) (x) is not negligible, leading to a larger overestimate of performance from c(ẑ) compared with the interval width. However, following the stability condition from Assumption 4, LOOCV can still provide a valid coverage guarantee for c(ẑ), since the difference between c n (ẑ) and Âloocv is always o p (n -1/2 ). In contrast, the sufficient condition for S5 follows by the asymptotic normality of CV through verifying Theorem 1 in [10] .Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?Answer: [Yes] Justification: This paper discloses all the information needed to generate the synthetic data and the test models when discussing the experiments in Appendix F. The point estimate and interval for each evaluation approach are stated in the beginning of Section 3.• The answer NA means that the paper does not include experiments.• If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not. • If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.• Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example , with an open-source dataset or instructions for how to construct the dataset). (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 
numerical experiments: 
 Setups. We consider two synthetic experiments to validate our theoretical results: (1) Regression problem: ℓ(z; Y ) = (z -Y ) 2 ; (2) Conditional value-at-risk (CVaR) portfolio optimization:ℓ(z; Y ) = z v + 1 η (-z ⊤ p Y -z v ) + with Z = {z = (z p , z v )|1 ⊤ z p = 1, z p ≥ 0}for some η ∈ (0, 1). In the regression example, we consider ridge regression, kNN with k n = Θ(n 2/3 ), and Forest with β = 0.4 (recall Example 4). In portfolio optimization, we consider sample average approximation (SAA, which belongs to Assumption 1) and kNN with k n = Θ(n 1/4 ). We run plug-in, 5-fold CV and LOOCV with nominal level 1 -α = 0.9. For each setting, we evaluate the following metrics with 500 experimental repetitions: (1) Coverage Probability (cov90): coverage probability of c(ẑ) with parentheses denoting that of c(z * ); (2) Interval Width (IW); and (3) bias: Difference between c(ẑ) and the midpoint of the intervalE[c(ẑ)] -E[ Â• ].Full experimental setup details are deferred to Appendices F.1 and F.2 with results of more K-fold CV results with K = 2, 10, 20. Moreover, we present a real-world regression dataset in Appendix F.3.. Table 2 shows that, in terms of coverage, parametric models including ridge regression and SAA cover both c(ẑ) and c(z * ) when n is large, across all methods. On the other hand, nonparametric models (kNN and Forest) incur invalid coverages, due to their slow rates γ < 1/4. When using kNN with k n = Θ(n 1/4 ), only LOOCV provides valid coverage for c(ẑ) (nearly 90%) while plug-in and 5-CV fail when n becomes larger. When using Forest and kNN with k n = Θ(n 2/3 ), plug-in is valid while 5-CV does not work. This matches the theoretical coverage guarantees in Table 1 .Table 2 also reports interval widths and biases to understand how some of the intervals fail. Lengths are comparable across each method, with plug-in usually shorter than LOOCV and 5-CV. This can be attributed to that plug-in approximates ẑ(•) better while extra variability arises from the data splitting in CVs, an observation in line with those in [18] . Biases are relatively large for nonparametric models for all methods. However, when n is large, both kNN with k n = Θ(n 2/3 ) and the Forest provide valid coverage for plug-in, attributed to the small bias relative to interval width, but not the case for other approaches (e.g., 5-CV for Forest).Table 2 : Evaluation performance of different methods, where boldfaced values mean valid coverage for c(ẑ) (i.e., within [0.85, 0.95]) and boldfaced values in parantheses mean valid coverage for c(z * ). IW and biases for kNN and Forest in the regression problem are presented in unit ×10 3 . Results on other sample sizes and numerical reports on standard errors can be found in Tables 3 and 4 kNN n 1/4 2400 0.00 (0.00) 0.17 1.72 0.76 (0.00) 0.34 -0.08 0.92 (0.00) 0.33 -0.00 4800 0.00 (0.00) 0.12 1.43 0.72 (0.00) 0.23 -0.04 0.88 (0.00) 0.22 -0.00 9600 0.00 (0.00) 0.09 1.11 0.66 (0.00) 0.15 -0.03 0.89 (0.00) 0.14 0.000Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [Yes]Justification: The paper provides sufficient instructions in Appendix F to reproduce the main experimental results and provide codes in the supplementary files in terms of all evaluation methods mentioned in the paper.Guidelines:• The answer NA means that paper does not include experiments requiring code. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
discussions, limitations and future directions: 
 We close this paper with some guidance to practitioners in light of the results we have obtained, as well as cautionary notes on the limitations of our study and future directions.Guidance to Practitioners. In estimating out-of-sample model performances, our results suggest the following practical guidance in choosing different methods. 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 and nonparametric models with a fast rate (γ > 1/4, including the so-called sieve estimators in [19] when the true function f (x) is 2d x -th continuously differentiable under P in ( 5)), the 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 (γ v > 1/4, γ ≤ 1/4), which include kNN with k n = ω( √ n) in Example 3 and the forest learner in Example 4, 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 (γ v ≤ 1/4), which include kNN with k n = Θ( √ n) in Example 3, only LOOCV has a negligible bias and provides valid coverages, and hence should be adopted.Our comparisons in model evaluation show that plug-in is preferable to K-fold CV, both statistically and computationally since plug-in works across a wider range of models and does not require additional model training. The above being said, we caution that, in terms of the direction of the bias, plug-in is optimistic while K-fold CV is pessimistic, and so the latter can be preferred if a conservative evaluation is needed to address high-stake scenarios. On the other hand, LOOCV provides valid coverages for the widest range of models, but it is computationally demanding.Due to such computational complexity, some alternatives, including approximate leave-one-out (ALO) [12, 32] , bias-corrected K-fold CV [30, 3] and bias-corrected plug-in [27, 35] , aim to control computation load while retaining the statistical benefit of LOOCV through analytical model knowledge. For example, ALO approximates each leave-one-out solution using the so-called influence function in parametric models. However, these ALO approaches are difficult to generalize in our problem setup due to difficulties in approximating the analytical form of influence function in nonparametric models (e.g., random forest). Other variants of cross-validation, e.g., fold number increasing with n [5] , can potentially help improve the statistical-computational tradeoff and we leave the investigations of these procedures as future work.Model Evaluation versus Model Selection. We caution the distinction between model evaluation and selection, namely the selection of hyperparameter among a class of models. Depending on what this class is, our model evaluation comparisons may or may not translate into the performances in model selection. On a high level, this is because the evaluation bias may be correlated among different hyperparameter values and ultimately leading to a low error in the selection task. A general investigation of this issue in relation to model rates appears open, even though specific cases have been studied [5] . For example, it has been pointed out that K-Fold CV can perform better for ridge or lasso linear models than plug-in for model selection [43, 56, 22] . We provide further discussions on the failure cases of the plug-in procedure for model selection in Appendix G.1.Asymptotic versus Nonasymptotic Behaviors. Our results are asymptotic and there is an obvious open question on extending to finite-sample results. Nonetheless, our results still shed light on the finite-sample performances of different approaches. For example, our numerical results, which show finite-sample coverage behaviors in Figure 1 and Table 2 , conform to our asymptotic theories. Note that there are some non-asymptotic intervals based on concentration inequalities with exact coverage guarantees [2, 23, 16] . However, they may be too loose as they are derived from a worst-case analysis.High-Dimensional Problems. As we mentioned in Section 2, our paper focuses on the asymptotic setting where n → ∞ and X , Y, Z are of fixed dimensions. Future work includes investigating different model evaluation approaches under other regimes, including high-dimensional settings where both the dimension and sample size go to infinity. We provide some preliminary discussions of our three considered procedures in high-dimensional settings in Appendix G.2. In particular, in these situations, [9] find that standard cross-validation procedures (2) give low coverages and design a nested cross-validation procedure to remedy. However, this latter procedure is designed for high-dimensional parametric models and does not help in the slow rate regimes of nonparametric models in our setting. We provide further comparisons in Appendix G.3.Despite the relative generality of our scope, we have assumed sufficient model smoothness and stability. Future work includes relaxations of these conditions to broader model classes and cost functions. This is also related to the extension of our analyses to ALO approaches, as these approaches require explicit smoothness, namely gradient-type estimates on the models, as well as other advanced CV approaches in, e.g., [7, 9] .Plug-in Approaches in Standard Stochastic Optimization. In the classical stochastic optimization without covariates, the interval of optimal model performance is constructed centered at the plug-in approach set as the empirical objective solved by the sample average approximation [53] . Furthermore, to address the low coverage probability of the naive interval [44, 52, 11, 41] , later literature improves the interval construction when the cost objective is nonsmooth and the variance estimate is unstable. In general, constructing the interval in the non-contextual case is generally easy compared with estimating the currentperformance of a function ẑ(•) or z * (•) in the contextual stochastic optimization due to slow rates and easy violations of the asymptotic normality.Generability of models with γ < 1/4. In general, many nonparametric models converge with a rate of γ ≤ 1/4. When ℓ(z; Y ) denotes the ℓ2 loss, models such as sieve estimators [19] satisfy the fast rate γ > 1/4. However, to the best of our knowledge, these models are difficult to implement in the general contextual stochastic optimization problem arising from decision complexity. Standard benchmarks there in Assumption 2 may still suffer from γ < 1/4 (also imply from Lemma 5 as follows), surging the need for studying the evaluation approaches under these regimes.B Details in Section 2.We list the following technical lemmas as well as discussions on their positions in this paper.Lemma 3 (Standard M-estimator Result, from Theorem 5.21 in [55] ) For each θ in an open subset of Euclidean space. Let x → m θ (x) be a measurable function such that θ → m θ (x) is differentiable at θ0 for almost every x with derivative ∇xm θ 0 (x) and such that for every θ1, θ2 in a neighborhood of θ0 and a measurable functionK(x) with E P * [K 2 (x)] < ∞: |m θ 1 (x) -m θ 2 (x)| ≤ K(x)∥θ1 -θ2∥.Furthermore, assume that the map θ → E P * [m θ (x)] admits a second-order Taylor expansion at a point of maximum θ0. If θ p → θ0, then:√ n( θ -θ0) = -V -1 θ 0 1 √ n n i=1 ∇xm θ 0 (Xi) + op(1).In particular, the sequence √ n( θ -θ0) is asymptotically normal with mean zero and covariance matrixV -1 θ 0 E P * [∇xm θ 0 (x)∇xm θ 0 (x) ⊤ ]V -1 θ 0 .We refer readers to Theorem 5.31 in [55] under constrained cases.Lemma 3 justifies the convergence rate of standard parametric learners. This result is the convergence in distribution for θ in Lemma 3. Compared to the moment convergence condition we use in Definition 3, we apply the standard theory for the moment convergence of M -estimator ( [59, 47, 20] ), we can transform the convergence in distribution for θ in Lemma 3 to the moment convergence result by:ED n [n∥ θ -θ * ∥ 2 2 ]< ∞ since values of the cost function and its gradient are all bounded from Assumption 2. Therefore, in the following, we only list the result of convergence in distribution.Lemma 4 (Lyapunov Central Limit Theorem, extracted from Theorem 27.3 in [14] ) Suppose {X1, . . . , Xn, . . .} is a sequence of independent random variables, each with finite expected varianceσ 2 i . Define s 2 n = n i=1 σ 2 i . If for some δ > 0, Lyapunov condition limn→∞(1/s 2+δ n ) n i=1 E[∥Xi -µi∥ 2+δ 2 ] = 0 is satisfied, then we have: 1 sn n i=1 (Xi -µi) d → N (0, 1).This Lyapunov CLT gives asymptotic normality guarantees when the variance of Xi is not bounded, which happens frequently when it comes to the asymptotic expansion in nonparametric models.Lemma 5 (Minimax Nonparametric Lower bounds, extracted from Theorem 3.2 in [33] ) Consider the class of distributions of (X, Y ) such that:1. X is uniformly distributed in [0, 1] dx ; 2. Y = f (X) + ϵ,where ϵ is the standard normal; And X and ϵ are independent.3. f (X) is globally Lipschitz continuous such that for all x1, x2 ∈ R dx , we have:|f (x1) -f (x2)| ≤ C∥x1 -x2∥.We call that class of distributions by P C , then we have:lim inf n→∞ inf fn sup (X,Y )∈P C ED n [∥fn -f ∥ 2 ] C 2dx 2+dx n -2 2+dx ≥ C1 > 0,for some constants C1 independent of C.Consider ℓ(z; Y ) = (z -Y ) 2 . Then any estimated ẑ(•) = fn(•) from Dn satisfies such lower bound. Recall the bias-variance decomposition of ∥fn(•) -f ∥ 2 , as long as ẑ(•) converges to z * o (•), then γ ≤ 1 2+dx , that is, either γB ≤ 1 2+dx or γV ≤ 1 2+dx. This justifies the rate of γB in Example 4.We first list our extensions of assumptions to nonsmooth and constrained problems, which are both natural in literature [58, 29] : The decision space Z and the optimal solution satisfy the following:Assumption1. Z ⊂ R dz is open in the form {z ∈ R dz : gj(z) ≤ 0, j ∈ J1; gj(z) = 0, j ∈ J2} with J = J1 ∪ J2 and gj(z), ∀j ∈ J twice differentiable with respect to z for any z. For any x, α * j (x; z) is twice differentiable with respect to z near z * o (x).2. The KKT condition holds for the oracle problem. That is, for any given x, the optimal decision z * o (x)(:= argmin z∈Z v(z, x)) exists and is unique for almost every x, with z * o (x) and its Lagrange multiplier {α * j (x; z)}j∈J satisfying the first-order condition:∇zv(z * o (x); x) + j∈J α * j (x; z * o (x))∇zgj(z * o (x)) = 0, ∀x ∈ X ;and the complementary slackness condition α* j (x; z * o (x))gj(z * o (x)) = 0, ∀j ∈ J, x ∈ X . 3. For any x ∈ X , ∇zz v(z * o (x); x) := ∇zzv(z * o (x); x) + j∈J α * j (x; z * o (x))∇zzgj(z * o (x)) is positive definite.We assume G(θ; x) can be any parametrized decision with respect to θ and x, which includes linear and more complicate models in both supervised learning, and contextual stochastic optimization problems [8, 50] : Assumption 7 (Additional Conditions in Assumption 1, adapted from Assumption 7 in [29] ) Suppose Assumption 6 holds. And for models in Assumption 1, for any x ∈ X , G(θ; x) is twice differentiable and Lipschitz continuous with respect to θ in a neighborhood of θ * := argmin θ∈Θ E P * [ℓ(G(θ; X); Y )] (exists and unique). We allow either of the following two scenarios:1. When Z is a unconstrained set (i.e. Assumption 3), ∇ θ E P X [v(G(θ * ; x); x)] = 0. And ∇ θθ E P X [v(G(θ; x); x)] is invertible for any θ ∈ Θ and positive definite at θ = θ * ;2. When Z is a constrained set (i.e., Assumption 6), suppose for any x ∈ X , α * j (θ; x) is twice differentiable with respect to θ near θ * ; At the point θ = θ * , G(θ * ; x) and its Lagrange multiplier α * j (θ * ; x) satisfy the first-order condition:∇ θ E P X v(G(θ * ; x); x) + j∈J E P X [α * j (θ * ; x)gj(G(θ * ; x))] = 0;and the complementary slackness condition α * j (θ; x)gj(G(θ; x)) = 0, ∀j ∈ J, ∀θ ∈ Θ, ∀x ∈ X . And∇ θθ E P X [v(G(θ; x); x)(:= ∇ θθ v(G(θ; x); x) + j∈J α * j (x)∇ θθ gj(G(θ; x)))) is invertible for any θ ∈ Θ and positive definite at θ = θ * ; 3. In Assumption 1, the first-order optimality condition holds for the empirical θ; And we assume λn/n d → C for some C as n goes to infinity. R(θ) is twice continuously differentiable for any θ ∈ Θ and ∇ 2 θθ R(θ) is uniformly bounded for any θ ∈ Θ.These conditions are naturally imposed to investigate the constrained stochastic optimization problem in [25, 29] . We verify that γ = 1/2 for parametric models.Proposition 1 (Convergence Rate in Parametric Models) For parametric models in Assumption 1, we haveγ = γv = 1/2.Proof of Proposition 1. For simplicity, we only consider the unregularized case. In the setup of Assumption 1, assume the following two minimization problems have unique solutions with:θ = argmin θ∈Θ n i=1 c(G(θ; Xi); Yi), θ * = argmin θ∈Θ E P (X,Y ) [c(G(θ; X); Y )].Suppose Assumption 7 holds. Then combining Lemma 3 we have:1. If Z is an unconstrained set, we have:√ n( θ -θ * ) = -∇ θθ E P (X,Y ) [ℓ(G(θ; X); Y ) -1 1 √ n n i=1 ∇ θ ℓ(G(θ * ; Xi), Yi) + op(1);2. If Z is an constrained set, following Corollary 1 of [25] , we have:√ n( θ -θ * ) = -PT ∇ θθ E P (X,Y ) [ℓ(G(θ; X); Y ) -1 PT 1 √ n n i=1 ∇ θ ℓ(G(θ * ; Xi), Yi) + op(1),where PT = I -A ⊤ (AA ⊤ ) † A and A denotes the matrix of with rows E P X [∇gj(G(θ * ; x))], j ∈ J.Regularization cases can be derived similarly (like Theorem 3 in [40] ). No matter in each case, following Assumption 1 due to the bounded cost, gradient condition in Assumption 2, we have γ= 1 2 since E[∥ẑ(x) - z * (x)∥2] = E[∥G( θ; x) -G(θ * ; x)∥2] = Θ(∥ θ -θ * ∥2) = Θ(n -1/2 ). And since the dominating term is just the variability term -∇ θθ E P (X,Y ) [ℓ(G(θ; X); Y ) -1 1 √ n n i=1 ∇ θ ℓ(G(θ * ; Xi), Yi), we have γv = 1/2. □This G(θ; x) can be any function as long as it satisfies Assumption 7. Furthermore, {Gθ; x), θ ∈ Θ} does not necessarily include the underlying best z * o (x). Since the constrained expansion is similar than the unconstrained version and the moment convergence can be implied from convergence in distribution, in the following, we mainly focus on the unconstrained case of models satisfying Definitions 1 and 2.We consider the unconstrained optimization problem under Assumption 3. Especially, we denote E[ẑ(x)] (a function over x) as the root of ED n [ i∈[n] wn,i(x)∇zℓ(z; Yi)] = 0, ∀x and abbreviate it as zn(x) in the following. Recall from Assumption 2, given Dn, we obtain the solution by:EQUATIONAssumption 8 (Expansion Conditions) Suppose the following expansion holds for the decision obtained from (6) for the corresponding wn,i:ẑ(x) -zn(x) = - H -1 Dn,x n i∈[n]wn,i(x)∇zℓ(zn(x); Yi) + op(n -2γv ),whereHD n,x = ∇ 2 zz ED n [wn,i(x)ℓ(zn(x); Y )].Intuitively, this result is obtained using similar routines as M -estimator theory from Lemma 3 since ẑ(x) -zn(x) = op(1) and conditions for θ and θ * there holds similarly for ẑ(x) -zn(x) here. In the following for each specific learner, we classify it through the following one of the two classes:EQUATIONEQUATIONwhere Bn,x = Θ(n -γ b ) denotes the deterministic bias term across these two classes, i.e., zn(x) -z * (x).For the variability term:• In the first case (8), for almost every x, we have:E[ϕx((X, Y ))] = 0, E[∥ϕx((X, Y ))∥ 2 2 ] < ∞, |N (Dn, x)| = Θ(n 2γv ); Furthermore, for i ∈ [n], we have: EX i [ϕX i ((Xi, Yi))] = 0 and E[∥ϕX i ((Xi, Yi))∥ 2 2 ] < ∞.• In the second case (9), for almost every x, we have:E P (X,Y ) [ϕn,x((X, Y ))] = 0, (E P (X,Y ) [∥ϕn,x((X, Y ))∥ 2 2 ])1 2 = Θ(n 1 2 -γv ), ∀x; Furthermore, for i ∈ [n],we have:EX i [ϕn,X i ((Xi, Yi))] = 0 and (EX i [∥ϕn,X i ((Xi, Yi))∥ 2 2 ]) 1 2 = O(n 1-2γv ).Therefore, ϕn,x((Xi, Yi)) = H -1 Dn,x wn,i(x)∇zℓ(zn(x); Yi), where wn,i(x) depends on Xi.In the following, we verify a number of nonparametric models satisfying (8) or (9) . Specifically, we show that Examples 3, 4 satisfy these conditions and present their convergence rates γ, γ b , γv and corresponding ϕ as follows.Example 3. Recall ẑ(x) obtained from Example 3 with a hyperparameter kn, then if we choose kn = min{Cn δ , n -1} for some C, δ > 0 from Theorem 5 of [13] , ẑ(x) converges to z * o (x).Proposition 2 (Convergence Rate of kNN Learner) In kNN learner, we denote Bn,x ≤ CEx[∥z * (x) -z * (x)∥] = O kn n 1 dx, where x is the nearest sample among n kn random points near the covariate x and and the order of Bn,x can be tight with respect to n from Lemma 5.The variability term can be regarded as the empirical optimization over a problem where the underlying random distribution is a mixed distribution over kn conditional distribution with equal weights near the current covariate x. Furthermore:EQUATIONwhere H kn,x = ∇ 2 zz E Dn(kn,x) [ℓ(zn(x); Y )] is the expectation over all the possible datasets Dn and the kn neighbors around x. Therefore, VD n ,x = Op1 √ knfollowing the M -estimator theory of empirical optimization due to kn samples around. There, ϕx((Xi, Yi)) = -H -1 kn,x ∇zℓ(zn(x); Yi) from (8).One can show that ( 10) is a special case of (8) . In this case, the convergence rate of ẑ(•) -z * (•) = Op kn n 1/dx ∨ 1 √ knwith p being some parameter. Tuning the best kn = Θ(n2 dx +2) yielding the convergence rate γ = 1 dx+2 . This result may attain the lower bound of estimation even in the regression (i.e. Lemma 5 above) such that γ = p dx+2p . Therefore, the learner usually belongs to the slow rate regime (γ < 1 4 when dx is large).On the other hand, for a number of other nonparametric models, we verify the condition that ( 9 for some bounded random variable T such that 1 n ϕn,x((Xi, Yi)) = Op(n1-β 2 ).Here, where sn is the subsample size with limn→∞ sn = ∞, limn→∞ sn log d (n)/n = 0 by Theorem 8 in [57] and Theorem 5 in [6] for sn = n β , where ω means the training examples are making balanced splits in the sense that each split puts at least a fraction ω of observations in the parent node and π means that the probability that the tree splits on the j-th feature is bounded from below at every split in the randomization.In this case, this result above gives a convergence rate γv = 1-β 2 and γ b ≥ -πβ log(1-ω) 2dx log ω . Certainly, this also does not obey the lower bound result around the discussion in Lemma 5.We demonstrate that some kernel estimators also satisfy our previous conditions:Example 6 (Kernel Learner) wn,i(x) = K((Xi -x)/hn) with the hyperparameter hn and the kernel K(•), where K : R dx → R with K(x)dx < ∞. Standard kernels include the naive kernel K(x) = 1 ∥x∥ 2 ≤r and Gaussian kernel K(x) = exp(-∥x∥ 2 ).Specifically, for the regression problem, we have:Example 7 (Nadaraya-Watson Regression [13] ) Consider the Nadaraya-Watson kernel regression ẑ(x) =EQUATION) holds for many classical kernels, e.g. Gaussian kernel K(x) = exp(-∥x∥ 2 ) and naive kernel K(x) = 1 {∥x∥ 2 ≤r} for some constant r.Proposition 3 (Convergence Rate of Kernel Regression) Suppose X follows a uniform distribution [-1, 1] dx and Y = f (X) + g(X)ϵ for the normal ϵ with some bounded functions f (X), g(X). When we take K h (x) = 1 {∥x∥ 2 ≤h} (See more details in Chapter 5 of [33] ), then Bn,x = O(hn) andVD n,x = Op(n -1/2 h -dx/2 n) as long as we tune hn such that hn → 0 and nh dx n → ∞ as n → ∞. And1 n n i=1 ϕn,x((Xi, Yi)) = Op(n -1/2 h -dx/2 n ) with: ϕn,x((Xi, Yi)) = (Yi -E[Y |Xi])1 {∥x-X i ∥ 2 ≤hn} h -dx n = Op(h -dx/2 n ) ϕn,X i ((Xi, Yi)) = (Yi -E[Y |Xi])h -dx n = Op(h -dx n ).In this case, the convergence rate of ẑ(•) -z * (•) = n -1/2 h -dx/2 n ∨ hn . We obtain γ ≤ 1 dx+2 when setting hn = Θ(n-1 dx+2). This usually belongs to the slow rate regime (γ < 1 4 ).Remark 1 (Usage of Regularity Condition in Assumption 8) In the following proof, when it comes to nonparametric models, we split it into two conditions that all the nonparametric models that satisfy (8) , where we replace it with (10) if needed since so far we only consider kNN learner in such category, or (9) should work. where Rj ⊆ X is the region (neighborhod of Xj) such that the closest point from {Xi} i∈[n] is Xj. Then since the decision is bounded ∥z∥ ≤ C from Assumption 3, we have:E[(ẑ(X) -ẑ(-i) (X)) 2 ] ≤ C 2 (P(Rj)) 2 = O 1 n 2 .Thus αn = C n in the 1-NN Model. More generally, if kn = o(n), the stability condition there can be shown through a symmetry technique from [24] to obtainαn = O √ kn/n = o(1/ √ n).Example 9 (Expected LOO Stability of Parametric Models) Suppose the objective ℓ(z; Y ) is strongly convex and Assumptions 2 and 3 hold. Then αn = O(1/n) in a standard empirical risk minimization approach from [15] , which includes all the parametric models we discuss.The technical details of Theorem 1 and Theorem 2 have been specified in Section 4:Proofs of Theorem 1. This follows from a combination of the results in Lemma 1 and Lemma 2. □ Proofs of Theorem 2. This follows from a combination of the results in Theorem 3 and Theorem 4. □ Before going to the detail proofs of evaluation bias and coverage guarantees for both plug-in and CV estimators, we first mention two lemmas that will be used in the following detailed results:Lemma 6 (Performance Gap) Suppose Assumptions 1 and 3 hold. For ẑ(•) in Definitions 1 and 2, we havec(ẑ) -c(z * ) = Op(n -2γ ). And ED n [c(ẑ)] -c(z * ) = C/n 2γ + o n -2γfor some C > 0.To show this result, we take a second-order Taylor expansion for v(z; x) at z * o (x) and notice the first-order term can be eliminated through Assumption 3 without or with constraints. This result shows the width of each interval does not vary significantly in terms of Θ(n -1/2 ) and demonstrates the need to study the bias for each approach to distinguish between them.Proof of Lemma 6. First, we consider the nonparametric models in Assumption 2 where z * (x) = z * o (x). Case 1: Z is an unconstrained set (Assumption 3). We take the second-order Taylor expansion at the center z * (x) for the inner cost objective v(z;EQUATIONFrom Assumption 3, the first-order term above becomes zero since ∇zv(z * (x); x) = 0. And for the secondorder term above, we have: 0 ⪯ Hxx ⪯ λU I dx×dx ∀x for some λU > 0 from Assumption 3. This implies that:0 ≤ 1 2 E P X [(ẑ(X) -z * (X)) ⊤ ∇ 2 zz v(z; x)(ẑ(X) -z * (X))] ≤ λU dx 2 E P X [∥ẑ(X) -z * (X)∥ 2 ].Therefore, we haveE P * [ℓ(ẑ(X); Y )] -E P * [ℓ(z * (X); Y )] = Θ(∥ẑ -z * ∥ 2 2,Px ). Case 2: Z is a constrained set (Assumption 6). Recall ∇zz v(z * o (x); x) := ∇zzv(z * o (x); x) + j∈J α * j (x; z * o (x))∇zzgj(z * o (x))Similarly, we take the second-order Taylor expansion at the center z * (x) for the inner cost v(z; x). For each x ∈ X , we obtain:EQUATIONwhere the second equality follows by the KKT condition from Assumption 6. And if we take the second-order Taylor expansion for gj(z) at the center z * (x) for each j ∈ J and x ∈ X , we have:EQUATIONThe left-hand side above in (13) converges to 0 since gj(ẑ(x)) -gj(z * (x)) p → 0, ∀j ∈ B from the first-order expansion of gj(z) and ẑ(x) p → z * (x) in Definition 2. Summing the terms of (13) over j ∈ J with each weight being α * j (x) and plugging it back into (12) to cancel ẑ(x) -z * (x) out in the first-order term, we have:EQUATION)where the second equality above holds by (13) . Then we integrate the left-hand side over x ∈ X with the underlying measure PX and obtain:c(ẑ) -c(z * ) = 1 2 E P X [(ẑ(x) -z * (x)) ⊤ ∇zz v(z * (x); x)(ẑ(x) -z * (x))] + o(∥ẑ -z * ∥ 2 2,P X ).Then we consider parametric models in Assumption 1 if we suppose Assumption 6 holds. Here, the limiting decision z * (x) is often not equal to z * o (x). When we do not have constraints We analyze the first-order term above and have: E P X [Gx(ẑ(x) -z * (x)] = 0 under Definitions 1 and 2. asp:add-param-decision When Z is unconstrained, in Equation ( 11), the first-order optimality condition in Assumption 7 gives rise to E P X [∇zv(z * (x); x)(ẑ(x) -z * (x))] = 0. And the analysis under Assumption 1 follows similarly as the case of Assumption 2. The only difference being that we directly analyze c(ẑ) -c(z * ) over x ∈ X . When Z is constrained, the first-order optimality condition in : ∇zc(z * ) + j∈J E P * [α * j (θ * ; z * (x))∇zgj(z * (x))] = 0 In both cases, we obtainE P * [ℓ(ẑ(X); Y )] -E P * [ℓ(z * (X); Y )] = Θ(∥ẑ -z * ∥ 2 2,Px ).Then sinceE P Y |x [∥ẑ -z * ∥ 2 2,Px ] = Θ(n -2γv). Then we have:ED n [c(ẑ)] -c(z * ) = C/n 2γ + o(n -2γ ),which finishes the proof. □Proof of Lemma 7. We establish the L1 convergence of the empirical variance term σ2 p to the true variance Var P * [ℓ(z * (X); Y )]. Applying the L1-LLN to ℓ(z * (X); y) since the cost function is bounded, we have:1 n n i=1 (ℓ(z * (Xi); Yi) -c(z * )) 2 L 1 → Var P * [ℓ(z * (X); Y )]since Dn is i.i.d. and z * (X) is independent with Dn. Therefore, we need to show that the following term converges to 0:EQUATIONFor the first term on the right-hand side in (15), we have:ED n ℓ 2 (ẑ(Xi); Yi) -ℓ 2 (z * (Xi); Yi) ≤ 2M0ED n ℓ(ẑ(Xi); Yi) -ℓ(z * (Xi); Yi) ≤ 2M0M1ED n [|ẑ(Xi) -z * (Xi)|] → 0.For the second term on the right-hand side in (15), we have:ED n c 2 n (ẑ) -c 2 (z * ) ≤ ED n c 2 n (ẑ) -c 2 n (z * ) + ED n c 2 n (z * ) -c 2 (z * ) ≤ 2M0M1ED n [|ẑ(Xi) -z * (Xi)|] + 2M0ED n [|cn(z * ) -c(z * )|] → 0.For the third term on the right-hand side in (15) , we have:ED n [|ℓ(ẑ(Xi); Yi))cn(ẑ) -ℓ(z * (Xi); Yi)c(z * )|] ≤ ED n [|cn(ẑ)(ℓ(ẑ(Xi); Yi) -ℓ(z * (Xi); Yi))|] + ED n [|ℓ(z * (Xi); Yi)(cn(ẑ) -c(z * ))|] ≤ M0M1ED n [|ẑ(Xi) -z * (Xi)|] + M0ED n [|cn(ẑ) -cn(z * )|] + M0ED n [|cn(z * ) -c(z * )|] → 0.Therefore, we show that the variance estimator of the plug-in estimator converges.In terms of the convergence of σkcv , following the same routine as before, we also only need to show:ED n   1 n k∈[K] i∈N k (ℓ(ẑ (-N k ) (Xi); Yi) -Âkcv ) 2 -(ℓ(z * (Xi); Yi) -c(z * )) 2   ≤ 1 n k∈[K] i∈N k ED n (c(ẑ (-N k ) (Xi); Yi) -Âkcv ) 2 -(c(z * (Xi); Yi) -c(z * )) 2 .Then we can use the same error decomposition as in (15) and show that L1-consistency. □ D Proofs of Evaluation Bias in Section 4.1Proof of Lemma 1. We first consider the case where ℓ(z; Y ) is twice differentiable with respect to z for all Y .And the proof generalizing to the piecewise twice differentiable function satisfying Assumption 2 is the same as in the parametric setup following Theorem 3 from [36] ,The bias for parametric models is provided in Theorem 1 from [36] where γ = 1/2 and the bias is Θ(n -1/2 ).For nonparametric models that satisfy Definition 2, recall the definition of zn(x), and we define:T1 = 1 n n i=1 ℓ(ẑ(Xi); Yi) - 1 n n i=1 ℓ(zn(Xi); Yi) T2 = E[ℓ(zn(X); Y ) -ℓ(ẑ(X); Y )].We expand the term inside the expectation as:E[ 1 n n i=1 ℓ(ẑ(Xi); Yi)] -E[ℓ(ẑ(X); Y )] = E[T1] + E[T2] + E 1 n n i=1 ℓ(zn(Xi); Yi) -E[ℓ(zn(X); Y )] , = E[T1] + E[T2],Then the second equality follows by zn(•) is a deterministic mapping and the observation that {(Xi, Yi)} i∈[n] are i.i.d.(i) Consider the nonparametric model with respect to the expansion scenario in (9) . For (9), we have: ẑ(x)zn(x) = 1 n n i=1 ϕn,x((Xi, Yi)) + op(n -2γv ). And that higher-order term op(n -γv ) can be ignored since we only focus on the term with the order of o(n -2γv ). More detailedly, ignoring the o(∥ẑ(•)-zn(•)∥ 2 2 ) = o(n -2γv ) term, we take second-order Taylor expansions to both terms T1 and T2.For the term T1, we have:E[T1] = E 1 n n i=1∇zℓ(zn(Xi); Yi) ⊤ (ẑ(Xi) -zn(Xi))+ 1 2n n i=1 (ẑ(Xi) -zn(Xi)) ⊤ ∇ 2 zz ℓ(zn(Xi); Yi)(ẑ(Xj) -zn(Xj)) = 1 n E[∇zℓ(zn(Xi); Yi) ⊤ ϕn,x((Xi, Yi))] + 1 2 E[(ẑ(Xi) -zn(Xi)) ⊤ ∇ 2 zz ℓ(zn(Xi); Yi)(ẑ(Xi) -zn(Xi))],where the second equality above follows by:EQUATIONwhere the third equality above in (16) follows by the independence of the model index under i and j under the conditional expectation. More specifically, ∀i ̸ = j, we have:EQUATION= 0.The equality (a) above follows by the fact that conditioned on any covariate x, E (X,Y ) [ϕn,x((X, Y ))] = 0. This implies the last equality of (16) .For the term T2, we have:T2 = E[∇zℓ(zn(X); Y ) ⊤ (ẑn(X) -z(X))] - 1 2 E[(ẑ(X) -zn(X)) ⊤ ∇ 2 zz ℓ(zn(X); Y )(ẑ(X) -zn(X))] = 0 - 1 2 E[(ẑ(X) -zn(X)) ⊤ ∇ 2 zz ℓ(zn(X); Y )(ẑ(X) -zn(X))],where the first equality of T2 follows by the chain rule of the conditional expectation under the stochastic Dn:E[∇zℓ(zn(X); Y ) ⊤ (ẑ(X) -zn(X))] = E P * [∇zℓ(zn(X); Y ) ⊤ E ẑ [ẑ(X) -zn(X)]] = 0,On the other hand, we show that the second-order term of right-hand side of E[T1] and E[T2] is o(n -2γ ). We only consider the case of dz = 1. This is because generalizing to the case of dz > 1 only requires to sum over each elementwise component from the matrix (ẑ(x) -zn(x))(ẑ(x) -zn(x)) ⊤ .We first consider bounding the difference as follows: 2 such that the inner product terms of Xi and Xj cancels out. Then we apply the result from Assumption 2 to obtain the result in (17) .EQUATIONThen we consider the noise difference that incorporates the Hessian matrix, that is putting ∇zzℓ(zn(Xi); Yi) into ẑ(Xi) -zn(Xi) and ∇zz[ℓ(zn(X); Y )] into ẑ(X) -zn(X). Note that if we take ∇zzℓ(zn(X); Y ) = g((X, Y ))g((X, Y )) ⊤ , then we can replace the original influence function ϕn,X ((X, Y )) with ϕn,X ((X, Y ))g((X, Y )), which does not affect the order of the influence function with respect to n since g((X, Y )) is of the constant level. Then it reduces to the similar analysis in (17) as the termE P X ,ẑ [∥ẑ(X) -zn(X)∥ 2 ] -E P X ,ẑ [∥ẑ(Xi) -zn(Xi)∥ 2 ].Therefore, based on the two results above, the numerator part of the only bias term in (16) becomes:-E P (X,Y ) [∇zℓ(zn(X); Y ) ⊤ ϕn,X ((X, Y ))] = E P (X,Y ) [∇zℓ(zn(X); Y ) ⊤ H -1 n,X wn,x(X)∇zℓ(zn(X); Y )] = E P X [wn,X (X)E P Y |x Tr[H -1 n,x • ∇zℓ(zn(X); Y )∇zℓ(zn(X); Y ) ⊤ ]] = E P (X,Y ) [Tr[H -1 n,X • ∇zℓ(zn(X); Y )∇zℓ(zn(X); Y ) ⊤ ]] = Θ(E P (X,Y ) [wn,x(X)] -1 ) = Θ(n 1-2γv ).where Hx = ∇zzE P Y |x [wn,x(X)ℓ(zn(x); Y )] and the last equation follows from (9) .(ii) Consider the nonparametric model with respect to the expansion scenario in (10) . Consider the expansion of E[T1] and T2, following the similar proof calculations to cancel out the term E P X ,ẑ [∥ẑ(X) -zn(X)∥ 2 ] -E P X ,ẑ [∥ẑ(Xi) -zn(Xi)∥ 2 ] and plugging in the expansion, we have:E[T1 + T2] = n kn Tr[E[H -1 kn,X i ℓ(zn(Xi); Yi)ℓ(zn(Xi); Yi) ⊤ ]] = Θ n kn = Θ(n 1-2γv ).Therefore, in both cases, -E[∇z ℓ(zn(X);Y ) ⊤ ϕ n,X ((X,Y ))] n = Θ(n -2γv) > 0, which finishes the proof.Proposition 4 (Optimistic Bias for kNN) Suppose Assumptions 1, 2 and 3 hold. Consider kNN estimators in Example 3, then there exists one P (X,Y ) (n) for each n such that the bias term ED n [cn(ẑ)-c(ẑ)] = Θ (1/kn) = Θ(n -2γv ).In the proof of Proposition 4, we construct P (X,Y ) (n) as a mixture distribution where the marginal support PX of each component is separate and the conditional distribution P Y |x for x within each component is the same.Then to analyze the bias, we need to focus on the bias within each component, which reduces a well-known problem to the plug-in bias for the standard stochastic optimization (e.g., [46, 36] ) with a Θ(1/n) bias with n samples; In our kNN case, we have kn effective samples used to obtain ẑ(Xi) for each i ∈ [n], therefore constituting an Θ(1/kn) bias.We state the following non-contextual bias lemma before diving into Proposition 4:Lemma 8 (Optimistic Bias in Stochastic Optimization from [46, 36] ) Suppose Assumptions 1, 2, 3 holds. Consider the sample average approximation (SAA) solution ẑ(x) = ẑ, ∀x ∈ X , where:ẑ ∈ argmin z∈Z 1 n n i=1ℓ(z; Yi),Then: E[ 1 n n i=1 c(ẑ; Yi)] = E[c(ẑ; Y )] + C n + o 1n for some C < 0. Proof of Proposition 4. For each pair choice n and kn, we construct an example of P (X,Y ) . W.l.o.g., we assume kn := n 2kn ∈ Z and construct the following multi-cluster distribution PX = i∈[kn]1 kn 1X∈R i U (Ri), where U (Ri) denotes the uniform distribution over the region Ri, the area of each |Ri| being the same. We can partition the regions {Ri} i∈[kn] such that diam(Ri) < d(Ri, Rj), ∀i and j̸ = i. Therefore, E[ n i=1 1X i ∈R j ] = 2kn, ∀j. And each conditional distribution Y |X ∼ i∈[kn] P i Y 1X∈R i for kn distributions {P i Y , i ∈ [kn]}.Under the event E = { n i=1 1X i ∈R j ≥ kn, ∀j}, each in-sample decision ẑ(Xi) only selects the data from the same region and incurs the same optimistic bias as the SAA method. Recall ẑ(Xi) from Example 3 is equivalent to the SAA method using that kn samples since it uses the data from the same Y distribution as Xi conditioned on each Xi (i.e. some P i Y ). That is ẑ(Xi) ∈ argmin j∈N i,kn ℓ(z; Yj) for the kn nearest covariates X with indices N i,kn , which includes Yi and other kn -1 points from the same cluster.Recall the result from the general optimistic bias result in the uncontextual stochastic optimization (Lemma 8). Since ẑ(Xi) only involves kn samples around Xi, we immediately have:E[ℓ(ẑ(Xi); Yi)|E] = E[ℓ(ẑ(X); Y )|E] + Θ 1 kn ,Then we show P(E) ≈ 1 when n is large, which follows from a union of kn Chernoff bounds with the multiplicative form applying to n random variables{1X i ∈R j } i∈[n] ∀j ∈ [kn].That is:P(E c ) = P( n i=1 1X i ∈R j < kn, ∃j) ≤ j∈[kn] P( n i=1 1X i ∈R j < kn) ≤ kn exp(-2kn/8),which converges to 0 exponentially fast with respect to the sample size n since we set kn = Ω(n δ ) for some δ > 0. Therefore, we have:E[ 1 n n i=1 ℓ(ẑ(Xi); Yi)] = E[ℓ(ẑ(Xi); Yi)] = E[ℓ(ẑ(Xi); Yi)|A]P(A) + E[ℓ(ẑ(Xi); Yi)|A c ]P(A c ) = E[ℓ(ẑ(X); Y )|A]P(A) + o C kn + E[ℓ(ẑ(X); Y )|A c ]P(A c ) + P(A) C kn = E[ℓ(ẑ(X); Y )] + Θ 1 kn ,where the third equality follows by the fact that:|E[ℓ(ẑ(Xi); Yi)|A c ] -E[ℓ(ẑ(X); Y )|A c ]|P(A c ) = o 1kn from the comparison between the exponentially tail and kn = Ω(n δ ). □Proof of Lemma 2. We first consider the K-fold CV for any fixed K. Note that from Lemma 6, Following the performance gap result from Lemma 6, we have:c(ẑ) -c(z * ) = C n 2γ + o n -2γ , γ < 1 4 .Since K-fold CV is an unbiased estimate of model performance trained with n(1 -1/K) samples, then we have:E[ Âkcv ] = ED n [c(ẑ (-N k ) )] = c(z * ) + C/(n(1 -1/K) 2γ ) + o(n(1 -1/K)) -2γ) Then comparing the two equations above, if we ignore the terms of o(n -2γ ) for any fixed K, we have:E[ Âkcv -c(ẑ)] = C n 2γ (1 -1 K ) 2γ - C n 2γ = C n 2γ ((1 -1/K) -2γ -1) ≥ C n 2γ 1 1 -2γ/K -1 = C n 2γ • 2γ K -2γ.where the first inequality follows by Bernouli's inequality that (1 + x) r ≤ 1 + rx for r ∈ [0, 1] and x ≥ -1.For the other side, we have:E[ Âkcv -c(ẑ)] = C n 2γ ((1 -1/K) -2γ -1) ≤ C n 2γ (1 + 2 K ) 2γ -1 ≤ 4γC Kn 2γ ,where the first inequality follows from (1 -x) -1 ≤ 1 + 2x when x ∈ (0, 1 2 ] and the second inequality applies the Bernouli's inequality again. Therefore, the bias of K-fold CV is Θ(K -1 n -2γ ).Then we consider LOOCV, which can be directly calculated through the proof of Lemma 6. Suppose we are in the unconstrained case but we take the second-order Taylor expansion with Maclaurin remainder to both c(ẑ (-i) ) -c(z * ) and c(ẑ) -c(z * ). This obtains:E[c(ẑ (-i) ) -c(ẑ)] = E[c(ẑ (-i) )] -c(z * ) -(E[c(ẑ)] -c(z * )) = 1 2 E[(ẑ (-i) (x) -z * (x)) ⊤ H ẑ(-i) (ẑ (-i) (x) -z * (x))] - 1 2 E[(ẑ(x) -z * (x)) ⊤ H ẑ (ẑ(x) -z * (x))], = 1 2 E[(ẑ (-i) (x) -z * (x)) ⊤ (H ẑ(-i) -H ẑ )(ẑ (-i) (x) -z * (x))] + Θ(E[∥ẑ (-i) (x) -z * (x)∥ 2 ] -E[∥ẑ(x) -z * (x)∥ 2 ]) = Θ(n -1-2γ ) + o(1/n).where Hz = ∇ 2 zz c(λ(x)z * + (1 -λ(x))z) as the Maclaurin remainder with λ(x) ∈ [0, 1], ∀x. And the last equality follows by the continuity of Hz and then recall the stability condition such that E Dn,P * [∥ẑ(x)ẑ(-i) (x)∥] = Θ(n -1 ) and apply to both terms.□. ED n [|ẑ(Xi) -ẑ(-i) (Xi)|] = ED n [|(ED n [ẑ(Xi)] -ED n [ẑ (-i) (Xi)]) + (ẑ(Xi) -E[ẑ(Xi)]) -(ẑ (-i) (Xi) -E[ẑ (-i) (Xi)])|] ≤ (ED n [ẑ(Xi)] -ED n [ẑ (-i) (Xi)]) + ED n [|(ẑ(Xi) -E[ẑ(Xi)]) -(ẑ (-i) (Xi) -E[ẑ (-i) (Xi)])|],where the first part denotes the bias difference and the second part denotes the variance difference. Then we need to show the two differences term are of order o(n -1/2 ). We divide them into two lemmas (Lemma 9 and Lemma 10). Then the result holds.□ Lemma 9 (Bias Stability) When αn = o(n -1/2 ) and γv > 1 4 , ED n [ẑ(Xi)] -ED n [ẑ (-i) (Xi)] = o(n -1/2 ) for ẑ(•) in Assumption 2.Proof of Lemma 9. First, notice that: ED n [ẑ (-i) (Xi)] = E P X ,Dn [ẑ (-i) (x)] since Xi and ẑ(-i) are independent. And we have E[ẑ(x) -ẑ(-i) (x)] = o(n -1/2 ) from αn = o(n -1/2 ). Therefore, we only need to show:E P X ,ẑ [ẑ(Xi) -ẑ(x)] = o(n -1/2 ).In the following two cases, we decompose the influence expansion for the two estimators.When ẑ(•) satisfies (8) (or (10) specially): Note that γv > 1 4 is equivalent to saying kn = w(n 1/2 ). From ( 10), ∀i ∈ [n], we have:E[ẑ(x)] -EP X [zn(x)] = -E   H -1 kn,x kn i∈N Dn,x (kn) ∇zℓ(zn(x); Yi)   + o(k -1 n ) = -E P X   H -1 kn,x kn ED n   i∈N Dn ,x (kn)∇zℓ(zn(x); Yi)    + o(k -1 n ) = o(k -1 n ),where the second equality follows by the definition of zn(x) such that ED n [ i∈N Dn,x (kn) ∇zℓ(zn(x); Yi)] = 0. In contrast, ignoring the term o(k -1 n ) in the derivation, we have:E[ẑ(Xi)] -EP X [zn(Xi)] = -E   H -1 kn,X i kn j∈N Dn,X i (kn)∇zℓ(zn(Xj); Yj)  + o(k -1 n ) = -E   H -1 kn,X i kn j∈N Dn,X i (kn),j̸ =i ∇zℓ(zn(Xj); Yj)   - 1 kn E H -1 kn,X i ∇zℓ(zn(Xi); Yi) = 0 - 1 kn E H -1 kn,X i ∇zℓ(zn(Xi); Yi) = - 1 kn E H -1 kn,X i ∇zℓ(zn(Xi); Yi)where the third equality follows by Xi and {Xj} j∈[n],j̸ =i are independent and using the same argument as the previous ones ED n [ i∈N Dn ,x (kn) ∇zℓ(zn(x); Yi)] = 0. Therefore, we have:E[ẑ(Xi) -ẑ(x)] = - 1 kn ED n H -1 kn,X i ∇zℓ(zn(Xi); Yi) + o(kn) = Θ(kn) = o(n -1/2 ).When ẑ(•) satisfies ( 9) or ( 7), following similar results as in kNN models,E[ẑ(x)] -E[zn(x)] = o(n -2γv ) = o(n -1/2). Besides, we have:E[ẑ(Xi)] -EP X [zn(Xi)] = - 1 n E[H -1 Dn,X i wn(Xi, Xi)∇zℓ(zn(Xi); Yi)] = - 1 n E[H -1 Dn,X i ∇zℓ(zn(Xi); Yi)] = o(n -2γv ) = o(n -1/2 ). Lemma 10 (Variance Stability) When αn = o(n -1/2 ) and γv > 1 4 , ED n [|(ẑ(Xi) -E[ẑ(Xi)]) - (ẑ (-i) (Xi) -E[ẑ (-i) (Xi)])|] = o(n -1/2 ) for ẑ(•) in Assumption 2.Proof of Lemma 10. When ẑ(•) satisfies (8) (or (10) specifically): Ignoring the o(k -1 n ) terms across equalities, we have:(ẑ(Xi) -E[ẑ(Xi)]) -(ẑ (-i) (Xi) -E[ẑ (-i) (Xi)]) = - H -1 kn,X i kn j∈N Dn ,X i (kn)∇zℓ(zn(Xj); Yj) +H -1 k n-1 ,X i kn-1 j∈N D n-1 ,X i (k n-1 )∇zℓ(zn-1(Xj); Yj)= - H -1 kn,X i kn ∇zℓ(zn(Xi); Yi) + H -1 k n-1 ,X i kn-1 - H -1kn,X i kn j∈N Dn,X i (kn),j̸ =i (∇zℓ(zn(Xj); Yj) -∇zℓ(zn-1(Xj); Yj)) .We take the expectation to the two terms on the right-hand side. For the first term, we have:E | H -1 kn,X i kn ∇zℓ(zn(Xi); Yi)| ≤ EX i [H -1 kn,X i ∇zℓ(zn(Xi); Yi)] kn = Θ(k -1 n ).For the second term, we have:E   H -1 k n-1 ,X i kn-1 - H -1kn,X i kn j∈N Dn ,X i (kn),j̸ =i (∇zℓ(zn(Xj); Yj) -∇zℓ(zn-1(Xj); Yj))  = EX i H -1 k n-1 ,X i kn-1 - H -1 kn,X i kn E Dn\X i   j∈∈N Dn ,X i (kn),j̸ =i (∇zℓ(zn(Xj); Yj) -∇zℓ(zn-1(Xj); Yj))  where the first equality follows by Xi and {Xj} j̸ =i are independent. On one hand, we know H -1 kn-1,X i = H kn,X i + o(1), which implies that:EX i H -1 k n-1 ,X i k n-1 - H -1 kn ,X i kn = o(k -1 n ).On the other hand:E Dn\X i   j∈∈N Dn ,X i (kn),j̸ =i (∇zℓ(zn(Xj); Yj) -∇zℓ(zn-1(Xj); Yj))   ≤ knLE Dn\X i [|zn(Xi) -zn-1(X)|] = o(knn -1/2 ).Combining these two arguments, we have:ED n [|(ẑ(Xi) -E[ẑ(Xi)]) -(ẑ (-i) (Xi) -E[ẑ (-i) (Xi)])|] = Θ(k -1 n ) + o(n -1/2 ) = o(n -1/2) for kNN models. When ẑ(•) satisfies ( 9) or ( 7), we use the notation in Assumption 2. Then variability difference becomes:ED n [|(ẑ(Xi) -E[ẑ(Xi)]) -(ẑ (-i) (Xi) -E[ẑ (-i) (Xi)])|] = E   1 n ϕn,X i ((Xi, Yi)) + j̸ =i ϕn,X i n - ϕn-1,X i n -1 ((Xj, Yj))   ≤ E [|ϕn,X i ((Xi, Yi))|] n + 1 n -1 E   j̸ =i (ϕn,X i -ϕn-1,X i )((Xj, Yj))   + 1 n(n -1) j̸ =i E[|ϕn,X i ((Xj, Yj))|] = O(n -2γv ) + O(n -1 2 • n -γv ) + O(n -1 • n 1/2-γv ) = O(n -2γv ).where the second equality follows by the fact that E[|ϕn,x((X, Y ))|] = O(n 1-2γv ) from Assumption 8; the second term {(ϕn,x -ϕn-1,x((Xj, Yj))|} j∈[n],j̸ =i are n -1 i.i.d. random variables with each mean 0 and variance E[|(ϕn,x -ϕn-1,x)((Xj, Yj))| 2 ] < ∞. Then the central limit theorem and uniform convergence imply:1 n-1 E j̸ =i (ϕn,X i -ϕn-1,X i )((Xj, Yj)) = O(n -1/2). This finishes our proof for the variability stability for nonparametric models. □Proposition 6 (Optimistic Bias Implies Coverage Invalidity) Suppose Assumptions 1, 2 and 3 hold. WhenED n [B] = ED n [cn(ẑ) -c(ẑ)] = Ω(n -1/2 ), S2 does not hold.Proof of Proposition 6. When the evaluation bias E[Bn] = Ω(n -1 2 ), we show that we cannot have:√ nB d → N (0, σ 2 ).Recall from the proof of Lemma 1, we have: B = T1+T2+cn(zn)-c(zn). We can verify that VarD n [T1+T2] = o(n -2γv ) through the same analysis as in Lemma 1. Therefore, we have: n 2γ (T1 + T2) Proof of Proposition 7. This result directly follows by the combination of Lemma 11 and Lemma 7.The proof of Lemma 11 follows from verifying the stochastic equincontinuity condition of the plug-in estimator as follows:Lemma 12 (General Result for Stochastic Equicontinuity of Plug-in Estimator, Lemma 2 of [18] ) For the estimator ĝ ∈ G which is function of v that is estimated through {Vi} i∈[n] and ĝ(-i) is estimated through {Vj} j∈[n] \{Vi} and there exists some g0 such that ĝ L 2 → g0, denote A(V ; g) = Ev[a(v; g)] and An(V ; g) = 1 n n i=1 a(Vi; g). Suppose we have the following condition:E ĝ,ĝ (-i) [|a(Vi, ĝ) -a(Vi, ĝ(-i) )|] = o(n -1/2 ), ∀i ∈ [n]; E ĝ,ĝ (-i) ,V [|a(V, ĝ) -a(V, ĝ(-i) )| 2 ] = o(n -1 ), ∀i ∈ [n] and for g1, g2 ∈ G, E[(a(V ; g1) -a(V ; g2)) 2 ] ≤ LEv[∥g1 -g2∥ q 2 ] for some q < ∞. Then √ n((A(ĝ) - A(g0)) -( Ân(ĝ) -Ân(g0))) = op(1).Proof of Lemma 11. This result follows by considering c(ẑ) and c(z * ) as the empirical and population version of the objective, i.e.,terms An(•) and A(•) there in Lemma 12. Compared with our notion, we need to verify the following three conditions:• E ẑ,ẑ (-i) E[|ℓ(ẑ(Xi); Yi) -ℓ(ẑ (-i) (Xi); Yi)|] = o(n -1/2 ); • E ẑ,ẑ (-i) E[|ℓ(ẑ(X); Y ) -ℓ(ẑ (-i) (X); Y )| 2 ] = o(n -1 );• For any two measurable function z1(X), z2(X), we have:E P * [(ℓ(z1(X); Y ) -ℓ(z2(X); Y )) 2 ] ≤ L(E P X [∥z1(X) -z2(X)∥]) q ,for some L > 0 and q < ∞.The first two results directly follow by the stability condition that αn, βn = o n -1/2 and the conditions in Assumption 2 that ∇zℓ(z; Y ) is bounded. And the third condition is verified through the first-order expansion that:E P (X,Y ) [(ℓ(z1(X); Y ) -ℓ(z2(X); Y )) 2 ] = E P X,Y [((∇zℓ(z(X); Y )) ⊤ (z1(X) -z2(X))) 2 ] ≤ (E P X [E P Y |X ∥∇zℓ(z(X); Y )∥ 2 ])(E P X [∥z1(X) -z2(X)∥ 2 ]) ≤ M 2 1 (E P X [∥z1(X) -z2(X)∥ 2 ]), where we take L ≥ E P X [E P Y |x ∥∇zℓ(z(X); Y )∥ 2 ] and q = 2 such that these conditions hold. □ For parametric models under Assumption 1, we have γ = 1/2 > 1/4, and the expected LOO stability notion is satisfied. Therefore, Corollary 1 always holds for parametric models.We first state the following result based on the standard Slutsky's theorem:Lemma 13 (Bias and CLT) For a random sequence An satisfying√ n(An -A) d → N (0, σ 2 ), if another random term B = A + op(n -1/2 ), then √ n(An -B) d → N (0, σ 2 ).Proof of Corollary 1. Note that if γ > 1/4, we have:√ n(cn(ẑ) -c(ẑ)) d → N (0, σ2 ) from Lemma 11.Combining it with Lemma 7, it is easy to see that Ip provides a valid coverage guarantee for c(ẑ).Furthermore, consider An = cn(ẑ) and A = c(ẑ). And if we set B = ED n [c(ẑ)] and c(z * ) respectively, then we have: B = A + op(n -1/2 ) from Lemma 6. Then applying Lemma 13, we stil have:√ n(cn(ẑ) -c(ẑ)) d → N (0, σ 2 ) √ n(cn(ẑ) -ED n [c(ẑ)]) d → N (0, σ 2 ).Therefore, Ip provides a valid coverage guarantee for c(z * ) and ED n [c(ẑ)]. □Before the proofs of the equivalence condition of cross-validation estimator (i.e. Theorem 4), we list the CLT for cross-validation.Lemma 14 (CLT of Cross-Validation) Suppose Assumptions 1, 2, 3 and 4 hold. Then Âkcv in (2) satisfies:√ n( Âkcv -Ã) d → N (0, σ 2 ) with Ã = k∈[K] E P * [ℓ(ẑ (-N k ) (X); Y )]/K.Here the same result holds for Âloocv by setting K = n.Note that the asymptotic normality of cross-validation does not depend on γ. However, the center from the CLT in Lemma 14 is different from c(ẑ) or c(z * ), and the convergence rate γ determines whether the difference is small. Therefore, the validity of the interval for K-fold CV to cover c(ẑ) still depends on γ.Before moving to prove Lemma 14, we introduce the following stability from the conditions in [10] . We will show that this can be directly implied from our assumptions of the cost function and the expected LOO stability: Definition 5 (Loss Stability) Continuing from the setup in the main body with Dn, we call the loss stability [39] by:α ls n := 1 n n i=1 E P (X,Y ) ,Dn [( l(ẑ(X); Y ) -l(ẑ (-i) (X); Y )) 2 ],where l(ẑ(X);Y ) = ℓ(ẑ(X); Y ) -E ẑ [ℓ(ẑ(X); Y )].We rewrite Theorem 1 in [10] and replace the uniformly integrable condition with our assumptions (since the bounded cost function condition in Assumption 2 directly implies the uniformly integrable condition there):Lemma 15 (CV of CLT from Theorem 1 in [10] ) Suppose Assumptions 1, 2, 3 and 4 hold. Ifα ls n = o(1/n). Then we have: √ n( Âkcv -Ã) d → N (0, σ 2 ).Proof of Lemma 14. To show this result, we only need to verify the loss stability is o (1/n) above. This follows by:(ℓ(ẑ(X); Y ) -E ẑ [ℓ(ẑ(X); Y )]) 2 -(ℓ(ẑ (-i) (X); Y ) -E ẑ(-i) [ℓ(ẑ (-i) (X); Y )]) 2 ≤ 2(ℓ(ẑ(X); Y ) -ℓ(ẑ (-i) (X); Y ))) 2 + 2(E ẑ [ℓ(ẑ(X); Y )] -E ẑ(-i) [ℓ(ẑ (-i) (X); Y )]) 2 .For the first term of the right-hand side above, due to the bounded gradient of ℓ, following the first-order Taylor expansion inside the square notation, we have:(ℓ(ẑ(X); Y ) -ℓ(ẑ (-i) (X); Y ))) 2 ≤ M 2 1 (ẑ(X) -ẑ(-i) (X)) 2 .Then if we take expectation over X, the right-hand side reduces to M 2 1 α 2 n = o(1/n). For the second term of the right-hand side above, we have:(E ẑ [ℓ(ẑ(X); Y )] -E ẑ(-i) [ℓ(ẑ (-i) (X); Y )]) 2 ≤ E ẑ,ẑ (-i) [(ℓ(ẑ(X); Y ) -ℓ(ẑ (-i) (X); Y )) 2 ] ≤ M 2 1 E ẑ,ẑ (-i) [(ẑ(X) -ẑ(X)) 2 ].Then if we take expectation over X, the right-hand side reduces to M 2 1 α 2 n = o(1/n). Therefore, we can apply Lemma 15 to see that CLT for cross-validation holds. □Proof of Theorem 4. We first consider the coverage validity of c(ẑ).(i) LOOCV. Since Lemma 14 holds, in this case, we only need to show that the term:EQUATIONThen combining this with the Lemma 13, we obtain the valid coverage of LOOCV intervals for the c(ẑ). From the first-order Taylor expansion to E P Y |x [ℓ(z; Y )], we have:EQUATIONSince the gradient of the cost function ∇zℓ(z; Y ) is bounded and following the stability condition:E P X [|ẑ (-i) (X) -ẑ(X)|] = o n -1/2 .Therefore, plugging it back above into (19) , we immediately see that1 n n i=1 E P * [c(ẑ (-i) (X); Y )] - E P * [ℓ(ẑ(X); Y )] = op n -1/2there. Then applying Lemma 13 and Lemma 7 would obtain the result of limn→∞ P(c(ẑ) ∈ I loocv ) = 1 -α.(ii) K-fold CV. For the part that S4 implies S5: if γ > 1/4, then we can show Ã -c(ẑ) = op(n -1/2 ) too by taking the Taylor expansion for each c(ẑ (-N k ) ) -c(z * ), ∀k ∈ [K] and c(ẑ) -c(z * ). Then both terms are only op(n -1/2 ). Then using Lemma 13 with√ n( Âkcv -Ã) d → N (0, σ 2 ), we have: √ n( Âkcv -c(ẑ)) d → N (0, σ 2 ).Combining this with Lemma 7 obtains S5.For the part that S5 implies S4, we prove by contradiction. Note that if γ ≤ 1/4, we have:n 2γ ( Ã -c(ẑ)) p → C > 0 from the proof of Lemma 6. Then if γ = 1/4, we have √ n( Âkcv -c(ẑ)) d → N (C, σ 2 ); if γ < 1/4, we have: n 2γ ( Âkcv -c(ẑ)) p → C.In both cases, S5 is invalid. Then we finish the proof.Then we consider the coverage invalidity of c(z * ) and prove it by contradiction. Suppose otherwise 2γ and contradict with the coverage validity condition; If γ = 1/4,√ n( Âkcv - c(z * )) d → N (0, σ 2 ) (the coverage validity holds). If γ < 1/4, then n 2γ ( Âkcv -c(z * )) d → 0. Therefore, n 2γ ( Âkcv -c(z * )) p → 0. However, recall Âkcv is the estimate of n(1 -1/K) samples from Lemma 6, we know, n 2γ ( Âkcv -c(z * )) p → C/(1 -1/K)we still have n 1/2 ( Âkcv -c(z * )) p → C/(1 -1/K) 2γ , which contradicts with √ n( Âkcv -c(z * )) d → N (0, σ 2 ).Therefore, as long as γ ≤ 1/4, we do not have such coverage for c(z * ) in both K-fold and LOOCV approaches. □ Furthermore, we may provide the coverage validity of CV intervals for c(z * ) as in the plug-in approach when γ > 1/4. Proof of Corollary 2. Since we are in the situation where Lemma 14 holds. Then when ẑ(•) -z * (•) = op(n -1 4 ), we only need to show that Ã -E P * [ℓ(z * (X); Y )] = op(n -12 ), which is given by the result already presented such thatE P * [c(ẑ (-N k ) (X); Y ) -E P * [ℓ(z * (X); Y )] = O(∥ẑ (-N k ) (X) -z * (X)∥ 2 ) = op(n -1 2 ) since n -|N k | = n (1 -1/K) = Θ(n).Then combining this with Lemma 13, that interval produced in Lemma 14 provides valid coverage guarantees for E P * [ℓ(z * (X); Y )]. The argument that the interval provides valid guarantee for E P * [ℓ(ẑ(X); Y )] holds similarly. □The experiments were run on a normal PC laptop with Processor 8 Core(s), Apple M1 with 16GB RAM. It took around 80 hours to run all the experiments including regression and portfolio study. All the optimization problems, if cannot solved directly using scikit-learn, are implemented through the standard solver cvxopt.We consider the regression and CVaR portfolio optimization problem. The latter two objectives are two classical constrained contextual piecewise linear optimization problems. Each case we run m = 500 problem instances.For the standard error reported in Figure 1 and the following tables, we calculate it as:σx = σ √ m ,where σ is the standard deviation of each reported result (i.e. interval width, bias size). We report 1-sigma standard error since the standard error of both interval width and bias scales are small.The corresponding table with a full set of sample sizes n is shown as follows in Table 3 .Setups. We construct the synthetic dataset through the scikit-learn using make_regression function.More specifically, we set 10 features and standard deviation being 1, and others being the default setup. We set random seed from 0 -500 to generate 500 independent instances. And we approximate c(ẑ) through additional 10000 independent and identicailly distributed test samples.becomes more significant compared with the interval length. This indicates the bias decrease order is slower than that of the interval and validates our theoretical results. Setups. We set η = 0.2, dx = dy = dz = 5 and PX = N (0, Σ) with (Σ)ij = 0.8 |i-j| , ∀i, j. And theconditional distribution (Y )i|x = 0.3 × (Bx)i + 2| sin ∥x∥2| + ϵ, ∀i ∈ [dz] for each ϵ ∼ N (0, 4).Models. We consider the following optimization learners for the subsequent performance assessment: (1) Sample Average Approximation (SAA): We ignore features when making decisions but consider the same decision space {z ∈ Z}. That is, for any covariate x, we output the same decision: ẑ ∈ argmin z∈Z , n -1}. In this case, the convergence rate γv = 1 8 , which violates the validity condition of both plug-in and K-fold CV intervals.We include one real-world dataset puma32H2 with 33 features and 1,000,000 samples as a regression task. We report the coverage probability of plug-in, 2-CV, and 5-CV for a kNN model with kn = n 2/3 , where each entry denotes the coverage probability estimated over 100 experimental repetitions for that procedure in Table 6 . Here each experimental repetition is conducted differently by shuffling the entire dataset. For a given sample size n, the procedure is to select the first n rows as the training sample for each model and approximate the true model performance c(ẑ) by averaging over the remaining samples in that dataset. In Table 6 , the plug-in approach provides valid coverages in this case while 2-CV and 5-CV do not, especially when n is larger (20000 and 40000). These results continue to validate our asymptotic theory.A difference between the model selection and 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 discussions for specific problems, such as linear regression, classification, and density estimation (see, e.g., Section 6 in [5] ). 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 α in the ridge regression. Plug-in always chooses α = 0 since it has the smallest training loss;• Selecting the best model class: Consider the regression problem f ∈ argmin f ∈F i n i=1 (f (Xi)-Yi) 2 for the nested classes F1 ⊂ F2 ⊂ F3, and we want to select the best Fi among the three classes. Plug-in always selects the largest class, F3, 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 a problem, but this is theoretically not well-understood in general cases.For the high-dimensional setting, i.e., feature dimension p and sample size n both go to infinity such that p/n converges to a nonzero constant, besides specific problems like (generalized) linear regression, the problem is wide open to our best knowledge. For linear models, we have the following result towards the bias of our considered three procedures:• For plug-in, when p > n, the predictor interpolates the training data so that the training loss becomes zero (unless we add regularization); when p/n → c ∈ (0, 1), plug-in still suffers a large bias from overfitting and cannot be used directly to construct the point estimator and confidence interval to evaluate model performance. Some bias correction procedures ( [27] ) are proposed to construct consistent point estimators in these high-dimensional scenarios.• For K-fold CV, the point estimate also suffers from a non-vanishing bias [58] and may not be a good choice for evaluating model performance.• For LOOCV, recent literature [58, 48] shows that its bias goes to zero.Despite the known results above for the bias, no theoretically valid coverage guarantees exist for high-dimensional linear models in the literature, since almost all existing CV literature is based on some stability conditions and is only valid under low-dimensional asymptotic regimes ( [7, 9, 37] and ours).For our three procedures, we validate claims for the point estimates above and also investigate the coverage performance of interval estimates, using the same simulation data setup for ridge regression with α = 1 as in our regression problems. We show the simulation results in Table 7 , where both plug-in and 5-CV suffer from large bias and have zero coverage. The bias of LOOCV is small but the LOOCV interval suffers from poor coverage. These results indicate that constructing theoretically valid intervals remains open and challenging for high-dimensional problems, and is important to devise improved CV or bias correction approaches. We elaborate on the discussion of the nested cross-validation and show it is not suitable under our slow rate regime. Recall that the nested cross-validation (NCV) in [9] is designed for improving the covariance estimate in high-dimensional regimes. Therefore, NCV does not help theoretically and empirically:Theoretical Invalid Coverages. NCV does not offer valid coverages for nonparametric models theoretically: The interval length of NCV is controlled by [9] (SE = Θ(n -1/2 ) is the standard error in their eq. ( 2)), this interval length is Θ(1/n 1/2 ) for a fixed K. In nonparametric models with γ < 1/4, this length is overly small compared with the bias of NCV, which is Cn -2γ for a constant C > 0 smaller than that of (2) in our main body. This is despite that the CV point estimator in [9] used bias correction in their eq. ( 9), that correction is for parametric models but not nonparametric models. Then the bias in [9] dominates the interval length and leads to an invalid coverage asymptotically. Furthermore, [9] 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.√ M SE. Due to the restriction √ M SE ∈ [SE, √ KSE] in Section 4.3.2 inEmpirical Poor Performance. 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 with the same setup in Appendix F.1 and report results in Table 8 . Here, plug-in, 5-CV, 10-CV correspond to the intervals (2) in our paper. For NCV, we use Algorithm 1 in [9] (following their practical MSE restriction in Section 4.3.2) and bias estimation in Appendix C of [9] to construct the interval for NCV (5-NCV and 10-NCV).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.Computational Inefficiency. Note that [9] does not focus on computation expense as we do in our paper in comparing LOOCV with plug-in. As mentioned in [9] , NCV is computationally very demanding, requiring over 1000 random splits to stabilize the variance estimate and needs to refit in total 1000K times. The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and precede the (optional) supplemental material. The checklist does NOT count towards the page limit.Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:• You should answer [Yes] , [No] , or [NA] .• [NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.• Please provide a short (1-2 sentence) justification right after your answer (even for NA).The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include it (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.The reviewers of your paper will be asked to use the checklist as one of the factors in their evaluation. While "[Yes] " is generally preferable to "[No] ", it is perfectly acceptable to answer "[No] " provided a proper justification is given (e.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering "[No] " or "[NA] " is not grounds for rejection. While the questions are phrased in a binary way, we acknowledge that the true answer is often more nuanced, so please just use your best judgment and write a justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.IMPORTANT, please:• Delete this instruction block, but keep the section heading "NeurIPS paper checklist",• Keep the checklist subsection headings, questions/answers and guidelines below.• Do not modify the questions and only use the provided macros for your answers.Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes]Justification: The paper specifies a brief summary of the experimental setup along with the results in Figure 1 and Section 5. This paper also provides all the training and test details at the beginning of the Appendix F.Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [Yes] Justification: The paper reports error bars of one case for the interval widths and biases in Figure 1 . For the error bars of numerical results in the Section 3, we report them in Appendix F (e.g. in Table 4 ). And we mention how the standard errors are calculated and specified in the beginning of Appendix F.• The answer NA means that the paper does not include experiments. • The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes]Justification: The paper provides the details of the computational resources in the beginning of Appendix F. Since it does not take too much time for all the whole setups of numerical experiments, we only report the rough overall computational time to obtain all the numerical results.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Justification: The research conducted in the paper conforms with the NeurIPS Code of Ethics in every respect.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.• The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [Yes] Justification: Although the paper focuses on the foundation research on constructing reliable performance guarantees for each evaluation approach, this paper discusses the potential positive societal impact in some parts of Section 6 and the motivation for investigating these coverage guarantees in Section 1. This helps people understand the utility of each evaluation approach and correctly and efficiently select one that suits to their setup best.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: The paper poses no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes] Justification: The original owners of assets including code and models (packages) are properly referred, including the scikit-learn package and codes from other papers. Both are referred when they are first mentioned (e.g. in Figure 1 and F ).Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL.• The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?Answer: [Yes]Justification: The proper guidance of replicating the numerical experiment results are provide in the accompanying files.Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
crowdsourcing and research with human subjects: 
 Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?Answer: [NA] Justification: This paper does not involve crowdsourcing nor research with human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector. 
institutional review board (irb) approvals or equivalent for research with human subjects: 
 Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?Answer: [NA] Justification: This paper does not involve crowdsourcing nor research with human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.• We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.The dataset is available at https://www.openml.org/d/1210. 
 
 Appendix:  


Decision: The reviews are very strong and agreement is high. That said, there are some
fairly significant points of context, some of which are highlighted by the
reviewers that are necessary for the authors to describe carefully in their
revision.

1. By K-fold, the authors mean K is O(1) or even "fixed K". Fixed K is the common
   use case in ML, but not generally the case for theoretical results. For
   example, [3] discusses specifically that K should grow with n for reasonable
   risk estimation performance. (See also the Weaknesses highlighted by tGmj).
2. The authors emphasis is on "estimation" not on "model selection". This is
   important. And the distinction is made clear in the experiments used in the
   Author Rebuttal to JBLc: using plug-in for model selection can be
   catastrophically poor. Additionally, the knn example here is obvious: plug-in
   will always select 1 nearest neighbor with 0 plug-in error. The authors draw out this
   distinction slightly in the Discussion, but it deserves more prominent emphasis.
   And the discussion of "interval" vs. "point estimation" for the prediction risk
   is key to Example 3 (see also, e.g. Table 2 Portfolio Optimization, where plug-in
   in this context has 0 coverage and massive bias).
3. The typical ML use-cases for K-fold CV are (1) tuning models and (2)
   comparing different models (usually to demonstrate that "my novel model in
   this NeurIPS paper is better than all the competitors"), not so much "risk estimation". 
   The introduction and
   title seems to suggest that we can just use the plug-in! This is wrong, and
   not what the paper's theory says (nor, what the authors really claim). 
   But this distinction is not made clear by the title or the introduction.
4. The necessary conditions (lines 61--62: "allows us to identify necessary
   conditions, in contrast to merely sufficient conditions in the literature,
   under which plug-in and CV variants exhibit low biases and valid coverages")
   are not weak and the range of problems covered is specific (low dimensions,
   bounded predictions or cost, LOO stability, specific range of gamma). This is
   also not described in the introduction.

The message of this paper needs to be carefully calibrated.
As the reviewers suggest, this paper may well question long-held beliefs of the ML
community in a provocative way. But it is written to be
provocative, possibly claiming more than it delivers in a way that could
result in some danger. Without more nuanced discussion of its deliverables, and
additional context, casual readers may use this paper as license
to use the plug-in estimator to compare models, keying on the statement (line
164 "plug-in is always no worse than K-fold CV"). I would urge the authors to
replace the statements of "evaluate model performance" with "estimate
out-of-sample prediction risk". This is more precise and precludes some of the
potential misunderstandings that could arise.

Reviews: review: paper_summary: paper_summary: The paper argues that Cross-Validation (CV), commonly used to evaluate machine learning models, may not be as statistically beneficial, especially in challenging nonparametric regimes. The paper shows that plug-in is always no worse than K-fold CV for models with any convergence rate. While leave-one-out CV can have a smaller bias than plug-in, this benefit is minimal compared to the variability of the evaluation. The theories are validated by numerical experiments.
strength_weakness: strength_weakness: 1. While the paper acknowledges that it is unclear whether the analysis and conclusions can be extended to model selection, I am eager to see more discussion on this topic, possibly including some simple simulation explorations.
2. Although the theories are validated on several synthetic datasets, it would be beneficial to provide experimental results on real-world datasets as well.
questions: questions: 1. In eq (2), every datapoint $(x_{i}, y_{i})$ is used more than once ($k-1$ times) in k-fold CV, the empirical variance should be scaled of $\frac{1}{n(k-1)}$?
2. While the numerical experiments are well-designed, providing results from experiments on real-world data would be even more convincing.
limitations: limitations: The authors clearly state the limitations of the framework, leaving me eager to see the follow-up work.
paper_summary: paper_summary: This paper considers model evaluation using plug-in method, CV and leave-one-out CV. The main contribution of this paper lies in the asymptotic bias and coverage performance analysis of these methods. The result is that in most cases, it turns out that the plug-in method is no worse than CV or leave-one-out CV.
strength_weakness: strength_weakness: It has been recently revealed in [8] that the CV might be estimating the risk of the algorithm, i.e., E(c(\hat{z})), which probably explains why the performance of CV for estimating c(\hat{z}) is not so good. Even in terms of model evaluation, the recent results in [6,9] show that it might be better to treat CV as estimating the averaged performance of a couple of models, so CV might have a large bias for estimating c(\hat{z}). 

The same notation of z in l88  and l101 refers to the prediction function and values in the prediction domain, respectively, which is a little bit confusing.
questions: questions: 1.In the overparameterized-regime, we would expect the predictor to interpolate, and the plug-in estimator would be zero, would we expect CV to perform better? In another way of speaking, does the result in this paper assume the dimension is fixed and the sample size goes to infinity?
2.Could the authors give an example where \alpha_n = o(n^{-1/2}) and \gamma \leq 1/4?
3.What happens for algorithm evaluation, i.e., estimating E(c(\hat{z})) and constructing a confidence interval for that? The algorithm evaluation task is an equally important problem.
4.Could we simply use sample splitting to perform model evaluation? For example, if n is large, then we can use half data for training and half data for evaluation, and I think it would give a pretty accurate evaluation for the model trained with n/2 samples.
limitations: limitations: This paper reveals that CV may not be a good choice for model evaluation. So a natural question is to ask is the plug-in method the most reasonable one we can use? Maybe the authors could provide some guidance for practitioners.
paper_summary: paper_summary: The paper establishes asymptotic results for bias and coverage of three different kinds of validation schemes, namely k-fold cross-validation, plug-in validation, and leave-one-out cross-validation. The setup is general and includes both parametric and non-parametric models. There are experimental results that cover parts of the finite sample context.
strength_weakness: strength_weakness: - The paper is very technical in nature and contains an appendix of 20 pages, most of which are also technical. (I count to seven theorems, 14 lemmas, and seven propositions.) It is not reasonable to expect reviewers to be able to cover this much material in the limited time frame of the review process in NeurIPS. I think the paper would be more appropriate for a journal submission.
- The code in the supplement is not documented at all and does not contain any configuration or setup for reproducing the results. The project should come with a `pyproject.toml` file, `requirements.txt`, or similar configuration. The zip file also contains numerous files that shouldn't be there, such as cache files. As a result, it is hard to check the validity of the numerical experiments. The experiments also seem to depend on commercial software (MOSEK), which is not ideal.
- The empirical results are questionable to me. You say that the typical number of folds in cross-validation is 5, yet the majority of your experiments use 2 folds, which I have never seen used in practice. I agree that the most common values are 5 and 10, and your experiments should reflect this, plus values above and below to show how the effect of $K$. Perhaps 5, 10, and 20. You even say you haven't "cherry-picked" your results, but this is exactly what this looks like to me, especially when you only show 5 fold results in a few of the cases.
- The empirical results all rely on data with 10 features, making $n/p \geq 60$ everywhere. This is not really representative of the contexts in which these models are used. You should consider $p > n$ or at least lower ratios than this. [8] show that the coverage of the intervals depend on this ratio.
- The results are based on one particular type of interval estimate for $k$-fold cross validation, but it is not clear that this is a good choice. (See **Questions**.)
questions: questions: ### Questions

- It seems to me that your results hinges on the interval estimates defined via (1) and (2) but, as you yourself say, these are not the only possible estimates. And in fact in [8] it is shown that these estimates in fact have as poor coverage as the naive estimates, which I suspect must influence your results as well. Why did you not use the more accurate estimates presented in [8] and why is there not more discussion of the results in that paper in general?

### Suggestions

- Perhaps the title could be more informative. If I understand the paper correctly, you are stating that it is indeed _not_ the gold standard to evaluate model performance. So just say that in the title instead.
- L29: It would help to be more descriptive about what the "plug-in" approach is. Many techniques "re-use training data for model evaluation". Cross-validation also fits this description, for instance.
- L29: "Reuses" should be "reuse".
- L31: "Model rates" could mean several things. Be more descriptive.
- L33: Left quotation mark around "center" is not formatted correctly.
- L258: Title escapes into margin.
- L352: "as" should be "as they are".
- Figure 1: Double y-axes are generally hard to read. I suggest you just divide the plot into two instead.
- L953: You already have one example 3. Maybe you forgot to use the example environment here?
- L973: Same as the previous comment. 
- Appendix: Equations escape into the right margin in several places.
limitations: limitations: - I am missing a discussion on optimistic vs. pesimistic bias
- The listed limitations should include the limitation of looking at one specific way of constructing the interval estimates.
- The results have no societal impacts as far as I can tell.
paper_summary: paper_summary: This is a primarily theoretical paper describing the bias and confidence intervals formed from different methods of assessing the true out-of-sample error of various models. In particular, this paper compares cross-validation (CV) to the "plug-in" estimator (i.e., the training loss). The authors assess the methods based on two criteria: how quickly the converge towards the true out-of-sample error as one gathers more data $n$, and whether or not the confidence intervals (formed as the usual $1-\alpha$ intervals of a CLT approximation to the folds of cross-validation / loss on each training point) achieve the proper coverage of $1-\alpha$.

The authors make two main very practical conclusions, regardless of model type (parametric or nonparametric): 

1. That there is essentially no point to using $K$-fold CV for some fixed $K$, as it has equal bias to the plug-in estimate and achieves coverage for strictly fewer models than does the plug-in.
2. The utility of leave-one-out CV (LOOCV) is questionable, since although it has somewhat better astymptotic performance than plug-in, the gains may not justify its usually enormous computational cost.
strength_weakness: strength_weakness: I have a few miscellaneous comments. I don't think any of them are particularly important with the exception of the first two.

**Claimed strength of results**

The introduction says "[we] identify *necessary* conditions, in contrast to merely *sufficient* conditions in the literature, under which the plug-in and CV variants exhibit low biases and valid coverage." I think a paper truly doing this would be incredibly exciting. However, I do not think this paper does this. In particular, there are eight enumerated assumptions that are used throughout the paper (Assumptions 1-4 in particular), and I did not see any analysis that these assumptions are necessary. The paper *does* completely break down how the bias and coverage depend on the convergence rate of the model at hand. And I think that's great. But I think it means these statements in the introduction and abstract aren't quite correct and should be clarified.

**Utility of CV versus plug-in (i.e., training loss)**

The paper kind of implies in its intro / abstract that it is going to show $K$-fold and LOOCV are actually not as good as the plug in estimator. I think Theorems 1 and 2 (the main theoretical results of the paper) show a more nuanced picture than this, though:

1. $K$-fold.  Theorem 1 shows that $K$-fold (for $K = O(1)$)  has bias that is equal in magnitude to plug-in, and Theorem 2 shows it has equivalent asymptotic coverage. The conclusion from this is very clearly spelled out: "plug-in is always no worse than $K$-fold CV." This might make it *sound* like $K$-fold is a waste of time to a practitioner, but I would argue it's. In particular, plug-in is biased to be *below* the true out-of-sample error, whereas $K$-fold is biased to be *above* the true error. Think of the perspective of a risk-adverse user or a regulator deciding whether to allow a model in a high-stakes situation (self-driving cars, medical procedures, etc.). I really can't see such users ever seeing plug-in as equivalent to $K$-fold; in fact, I would argue that they would hugely prefer to use $K$-fold precisely because its evaluation of the model will be conservative.

2. I thought some of the discussion in the paper was critical of LOOCV's statistical performance, however, LOOCV seems to outperform plug-in in both Theorem 1 and 2. I appreciated the point that one might see the statistical gains as minor in exchange for the computational expense. But I think it could be clearer that the takeaway is "maybe don't bother with LOOCV, especially if you have a parametric model that's nearing it's 'asymptotic regime'".

I'm calling this out here because I think this is a really interesting paper that might get highlighted at the conference. Many non-theoretically oriented people attend NeurIPS, and I really wouldn't want them to get the wrong idea based on reading the introduction / abstract. A doctor making the medical device that will diagnose any of our future tumors might be in attendance -- do you *really* want them to use plug-in over $K$-fold to assess the quality of their algorithms?

**Small issues in theorems**

1. I think it should be made clear when $K$ is a constant, and when it can vary with $n$. I *think* Theorem2 wants it to be a constant whereas Theorem 4 allows it to scale with $n$. But this should be clear.
2. In Theorem 2, why do we care about the coverage of $c(z^*)$? Is this just a fun fact? Some interpretation would be good.
3. Theorem 4 seems to give a much more specific description of LOOCV's bias than does Theorem 1 -- why not state Theorem 4's result in Theorem 1?
4. I was a little confused by Theorem 3/4 being labeled as "Theorems"; they seem like Lemmas to me given that they are building blocks used for Theorems 1/2.
5. In Theorem 2, when $\gamma_v \leq 1/4$, the asymptotic coverage of plug-in is given as $\leq 1-\alpha$. The text then states that equality holds (i.e. coverage is $= 1-\alpha$) when $\gamma_v > 1/4$. But the point is that we're covering $\gamma_v \leq 1/4$, so I think the $\leq$ should be a $<$.
6. I often thought that restating the theorem would be helpful before the proofs in the Appendices; I had to open the paper in multiple windows to flip through everything.
7. There are a lot of random quantities floating around the paper, and it wasn't always clear what expectations were being taken over. It would be good to subscript expectations with what they're with respect to wherever possible.
8. Line 130: I think the upper bound on the Hessian here is from Assumption 2, not Assumption 3.
9. I got a little lost in the proof of Theorem 3 when it suddenly jumped into discussing Assumption 8. First, Assumption 8 isn't an assumption of the Theorem, and Assumption 8 seems to be about nonparametric models, whereas Theorem 3 is generic. I think it could be more clear what's going on here.

**High dimensions**

I think a comparison in high dimensions is a major missing piece to the story here -- at least for parametric models. In particular, the use of cross-validation in the fixed dimension $n \to \infty$ case is a lot less relevant, as in this case it's well known (e.g. from empirical risk minimization theory) that the plug-in estimate will perform well. In high dimensions, say where $n/d \to$ some constant, the plug-in often does not perform well, whereas cross-validation can. I don't think this is a significant direction for change in the paper, but I do think a little discussion (maybe in the future work section) would be good.
questions: questions: I'm curious how the results hold up in high dimensions, but I don't think this is a critical direction for the paper.
limitations: limitations: I think the authors could use a little more discussion of the limitations of their results (see the first section under "Weaknesses"). I don't think there are any societal impacts of this paper.

Comments: title: Rebuttal
comment: We greatly thank the reviewer again for your constructive feedback and thoughtful reading for reviews. We also sincerely thank you for giving us a high evaluation! Specifically, we would emphasize the model selection and high-dimensional issues as our future work in our revised version.
Summary: after reading the reviews and other responses, I think the paper will be even stronger. I would vote for it being highlighted at the conference (e.g. an oral presentation); I think it has a lot of thought-provoking theoretical **and** empirical implications.

I think there was a lot of interesting discussion in the above reviews and responses! I especially thought JBLc’s comments on model selection —and the authors’ responses — were interesting, as this is a really straightforward failure case of plug-in that I hadn’t thought of while reading the paper. I think calling this out in the paper adds to the mystery a bit: plug-in is just as biased as K-fold for any *fixed* model, and yet, somehow, is horrible for model selection. This seems like an interesting direction for future work. I also appreciated the discussion of the high-dimensional work as an interesting direction for more future work.

On merging Theorem 1&4 vs keeping them separate: I would just take the above comment as an $n=1$ sized observation that I found it confusing when reading the paper. I don't think it's a huge deal.
We greatly thank the reviewer for your constructive feedback earlier, and for reading our reply closely and increasing your score!
We greatly thank the reviewer again for your constructive feedback and for giving us a high score.
We greatly thank you for your constructive feedback and thoughtful reply to our response. We also sincerely thank you for increasing the score for our paper! We understand your consideration of the amount and technical nature of the materials, and we are doing our best to make our comprehensive results digestible and the key messages clear in the main body. Most importantly, we believe our results and messages would gain interests and be very useful to the general ML community -- and we are glad to see that you and other reviewers recognize this as well. Lastly, we also politely note that, compared to other published NeurIPS papers on related subjects in the learning theory field, our 20-page appendix perhaps is not that long according to our best understanding.
Thanks! The additional experiments and comments regarding the choice of interval estimate definitely alleviate many of my concerns, and I will raise my score as a result. Apologies for my ignorance regarding your choice of regime. I still, however, contend that the paper is not a good fit for this format and would fit better for a journal submission.
Thank you for the detailed response and I will keep my positive score.
Thank you for the detailed discussions and all the experiments. The experiment results look good to me, so I have raised the score.