Is Cross-validation the Gold Standard to Estimate Out-of-sample Model Performance?
Authors: Garud Iyengar
Henry Lam
Tianyu Wang
Venue: NeurIPS 2024 poster (2024)
Keywords: cross-validation
plug-in
uncertainty quantification
nonparametric models
Primary area: learning_theory
TL;DR: Plug-in approaches perform no worse than cross-validation approaches when estimating out-of-sample model performance.

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.

Is Pross-Validation the Gold Standard to Estimate Out-of-sample Model Performance?
Garud Tyengar, Henry Lam, Tianyu Wang'
Department of Industrial Engineering and Operations Research
Columbia University
New York, NY 10027 {gi00, kh12114, ho2e
Abstract
Cross-Validatio Validation (CV) is the default choice for estimate the out-of-sample per- formance 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 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 paramet- ric nonparametric models converge. Leave-one-out CV can have smaller bias as compared to plug-in; however, this bias improvement negligible compared the variability of the evaluation, and in some important cases leave-one-out again does not outperform plug-in once this variability taken into account. We obtain our theoretical comparisons via 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 wide range of examples.
Introduction
Cross-validatios (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 [33. Its main rationale is evaluate models using testing set that is different from training, a reliable estimate 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 prime approach; however, it is computationally demanding as it requires model re-training for the same number of times the sample size. Because of this, K-fold CV, which reduces the number of model re- re-training down to K times (where K is typically 5-10), becomes a popular substitute
to provide
34
42
Despite their wide usage, the statistical benefits of CV have remained understood mostly para- metric models. In nonparametric regimes, especially those invol slow model convergence rates, their general performances as well as comparisons with the naive "plug-in" approach, i.c., 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
Authors ordered alphabetically. More information the data and code available utlttps://github
com/ htt////aggiaaauo///ooooooooaaaaa
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Evaluation Bias (x103)
2
1.0
Coverage Probability
Plug-in
0.8
2-CV
1.5
5-CV
0.6
LOOCV
1
0.5
1200
2400
4800
9600
Sample Size n
Figure 1: Evaluation biases and coverage probabilities of interval estimates (with nominal level 90%) for the mean-squared error evaluation of fitted random forest regressor (default setup in scikit-learn in [9 with n2 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-fi 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 "must-use" in estimating sample model performance in general and, if not, then under what situations are they worthwhile?
More precisely, in this paper we conduct 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 K-fold CV never outperforms plug-in 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 T 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 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 "cherry pick": " Section 5 and Appendix 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 propelled by a novel higher-order Taylor analysis on the out-of- sample 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 the gap in understanding which methods outperform which others, in regimes that have appeared challenging for previous works.
Problem Framework
We consider the supervised learning setting with observations D,, {(X,, Y.))eee)) drawn i.i.d. from the joint distribution P(x,)) == Px Pylx. We obtain predictor ((x) = A(D,;

---

function of z with the output domain 2, through a training procedure A on Dn. We are interested in evaluating the out-of-sample performance Exx, ((((()); where {(2; ) : Z x y + the cost function, This evaluation can be a point estimate, or more generally an interval estimate I(a) that covers Ep xx.) [(()(();; (((xX)) Y] with 1-a probability, i.e., we aim to satisfy PD, (BEr,x.)) [e(3(X); Y)] e I(a)) R 1 a, where the outer probability PD., is with respect to the data D,, used to construct 2(-). We focus on the now-dimensional asymptotic setting where 12 - so and X, Z are of fixed dimensions and defer discussions to other regimes in Section
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 downstream optimization objective in decision- making 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 operations management, the cost refers monetary loss of retailer determined by the order quantity z, and covariate X refers to the market condition that drives stochastic demand Y [8 [3]. Our framework in this paper applies to both the traditional supervised learning and prescriptive data-driven decision- making settings.
We consider three main methods: plug-in, LOOCV, and K-fold CV. We denote Am, and (m(()) as the point estimate and (1 - -levve interval estimate, using method m E .M- = {p, loocu, kcu) referring to plug-in, LOOCV and K-fold CV respectively. For convenience, we denote P as the true joint distribution PP P(),y) and IP,, = (1/m) Σ o(,,y,) Y.) as the empirical distribution, and we denote c(2) and (2) as the out-of-sample performance Ep- (e(x(X); Y) and the plug-in evaluation of the out-of-sample performance EEg [[(=(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 form (m) = Amm 21 21-0/20m/ ml Vr. Am + 21-0/20m/ Vnl, Vm M with:
Ap cx) ox
Σ (e(3(X)): Ap)?, =E(m)
(1)
Akce 1 Σ Σ e(s(-Na) No) (X:): ōkev / Σ Σ ((EE)-))())): REIK]IEN
A (2)
T1 kE(R]IENE
where 21-a/2 is the (1 a q22)-uuantile of the standard normal distribution, (Ne, E [K]} is the collection of K equal-length partitions of [r]] (for simplicity we assume n is divisible by K) and 2(-N)) = A(D with D(-N.) denoting the data set that leaves out {(X,, YEJNEN For the K-fold CV estimates, ÅRco and IkCU, we always assume K is fixed with respect to n (e.g.. K = 2, 5, 10). On the other hand, Atooev and Liooce (a) are defined by setting K = n in ( 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 [T].
We impose the following regularity and optimality conditions on the cost function:
Assumption (Smoothness of Expected Cost) For any E X, v(2;z) == Eryla Y)) is twice differentiable with respect to z everywhere, where IP Y is the conditional distribution Y Y given x.
Assumption (Regularity of Cost Function) For any y E V, (z;y)) is twice differentiable with respect to for every y. Moreover, (( almost surely in y.
are uniformly bounded in E Z and
Assumption 3 (Optimality Conditions) Z is bounded open set. The best mapping 2x(x) that minimizes v22,2), Vo E X satisfies the first and second-orter optimality conditions. More precisely, Vr E X, (x); 0, and v,,(( (z) is positive definite.
While Assumption 2 is standard, we can relax it further to some non-smooth objectives including piecewise linear functions (e.g., {(2; Y) = Jz Y)); see Assumption in Appendix B.2 The other
assumptions above are commonly used stochastic optimization 25 29
38
We further allow
constrained problems in Assumption X in Appendix B.2
3

---

Example 1 The function {(2; Y) (2-Y), (eg-regressionn, compact ser 3/ and 2g (z)
E
z] with {a |2| < B) for any B maxzex 2 (z) satisfy Assumptions 7 and
Next, we distinguish between parametric and nonparametric models in Definitions and below, leaving further details on technical regularity conditions Appendix B.3
Definition (Parametric Model) a(x) = G(0; x). where 0 = argmingee
(G X.); Y,) -
X₂ R(0) for some regularization function R(0). Regularity conditions of G(O: ; X are provided in
Assumption in Appendix B.3.7 which are satisfied by linear models (Example of Section 3
Definition 2 (Nonparametric Model) 2(-) is
with weights obtained through depending on Dn. and x.
2(x)
argmin Eig(n) W (n,((x)((2;
Regularity conditions of W.na (.) are provided in Assumption 8 in Appendix B.3.2 which are satisfied by the classical k-Nearest Neighbor (kNN) and forest learners (Examples of Section
Define 2" 2²(+) ;= A(Do) as the oracle best model using the training procedure A with infinite data DO We now define the notion convergence rate order for model 8()):
Definition 3 (Convergence Rate) For model 2(-), we say it has convergence rate of order
Y E (0, 1/2] ED, [1]{(x) 2* (=)) [|] = O(n (anaa)) for almost every z. Furthermore, we say { has bias and variability convergence rate "bo respectively if BD, [[, (xx))] = θ (n (=>))
and ED, (1x) (+x))]l]] = (o(n">>)) for almost every v. Consequently, 7 min (7b, 7r).
The overall convergence order 7 of =(-) is determined by both its bias 7h and variability Tv- whichever dominates. For parametric models in Definition 2 we naturally have % = 1/2 (see Proposition I in Appendix B.3.1. However, unless [G(O; x) 0 E }} contains the model (-) that optimizes (2; -), there a discrepancy between x (-) and the limiting model =-)) For nonparametric models in Assumption 2 both 7% and To depend on the hyperparameter configuration and are often smaller
than 1/2. When their hyperparameters are properly chosen (e.g. Theorems 5 in [3] D, we have
2" (-) (-) thanks to the nonparametric power in eliminating model misspecification.
Lastly, introduce the following stability conditions:
Definition (Stability) Denote two leave-one-out (LOO) stability notions Onn, Bn by:
(Expected LOO Stability)
On = max rE
(...,(), -2 -2 (xx (2)
(3)
(Pointwise LOO Stability)
Bn max sE(n]
EED
(x.00
where the expectation in 3 with respect to both the data Dn, used to construct & and 2(-1), and Is that generates X, while has expectation taken with respect to only D,..
Stability notions are first proposed in [5
45 and commonly used provide generalization
guarantees for CV [37 39 well as refined bounds under more relaxed stability in [16] 2 We
assume the following:
Assumption 4 (LOO Stability) 2(-) satisfies the expected LOO stability with a,, o(n 1/2).
This condition holds for many models in Definitions 1 and 2
and is often imposed for the validity of plug-in and CV, e.g. in 10 18] For illustration, we provide an example of I-NN in Appendix B.4
15 28
3 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 IP in the following are taken with respect D,..
Theorem (Bias) Suppose Assumptions 2(-) in Definitions
7 3 and hold. Recall "o in Definition 3 Then, for
and 2
B[c(2) Ap] O(n 2% 0, E[((2) Ascul O(n 2()) < Ele(() -Loveu] = o(n 1)n << 0.

---

Theorem 2 (Coverage Validity) Suppose Assumptions 7 2 3 and hold. Recall M
{p, kcv, loocv}. Then, for 2()) and 2" (-) in Definitions and
+Ify > 1/4, then: lim P(c(()) Im) = lim P(mp=>) E [m] - a, for m E M.
.
If s 1/4, then lim, P(c(2*) E Im) < <1- a for m E M.
- -1o P(((()) E Ip) S - a, where equality holds if and only if Bn = o (1-1/22 (or
Tv > 1/4).
1imm- P((((2) E Tkoo) < a
limp-+00 P(((2) E [looc) = a.
In the following, we use Theorems and 2 to compare plug-in, K-fold CV and LOOCV, and highlight our novelty relative to what is known in the literature. In nutshell, the regime Y S 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 | and 2 together stipulate that plug-in in is always no worse than K- K-fold CV in terms of estimating sample performance. In terms of evaluation bias, plug-in 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 7 = 7h = 1 1/2. their biases in Theorem | are both O(n -)) 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 in is ( 22') which is no bigger than that of K-fold CV since Y S %o. This behavior arises because. even though plug-in incurs an underestimation of O(n 2%) 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 7 1/4), their coverages differ for nonparametric models, with plug-in still always no worse than K-fold CV. Specifically, when 7 S 1/4, K-fold CV incurs invalid coverage, whereas plug-in still yields valid coverage as long as 7o > 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] 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 7 > 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 7 S 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 pes- simistic, bias o ol/nn) However, this bias improvement can be negligible compared to the evaluation variability captured in interval coverage, specifically when 7 > 1/4 (which includes all parametric models) and when y I 1/4.% > 1/4. In the latter case in particular, the bias of plug-in, even though larger than LOOCV, is small enough ensure valid coverage.
We visually summarize our discussions on biases and interval coverages in Figure 2 In particular, Figure (b) display our new contributions on both plug-in and CVs under slow rate y. We also see that plug-in intervals provide valid coverages for (c), while K-fold CV only valid for (c) and LOOCV is valid across (c)..
5

---

-00
80
8
1 4' Yb
1 4
(a) Yv _
(b) Yv
(c) Yv, Yb
Plug-in
K-fold CV
LOOCV
c c(z²
c(2)
Figure 2: Concept plots of interval coverages of c(2), and also c(="), ) for our considered approaches across model rates, where the black line represents the value of the expected cost and point considered covered if it falls within the corresponding interval.
Examples. We exemplify the above insights with several specific models. Denote da dy as the dimensions of X and Y. We consider a regression problem with {(2;Y) = (2 - Y)² and dg = 4, dy L, where 1 E P with:
p= p=x ( Pr| (ff(z), 1). Vo with Lipschitz continuous f(z)). (5)
We consider the worst-case instance of IP* in the sense that N6. Yu take the smallest attainable values in Chapter of 33
Example 2 (Regularized) Linear-ERM (8) G(0;z) ZTx An 1, R(0) 11012 satisfy As- sumption / Specifically, =/v 1/2, and all of plug-in, K K-fold CV and LOOCV provide valid coverages for c(ē).
Example 3 (KNN-Learner) Denote the nearest index set ( {i|X; is kNN of x)) Then (x)( 1 (kk.). satisfies Assumption 2 with hyperparameter kn- Specifically, log n) and no = (og(kz/n), log n.) (from Chapter 6 in (331). If kn = w(Vn) then LOOCV and plug-in provide valid coverages for c(ē); otherwise, only LOOCV provide valid coverages.
log kn. (2 (2g
Example 4 (Forest Learner) Consider forest F = (TI...,,TTh, where each Ti Rd {1....,Li Li} is (tree) partition of Rd into L; regions. Then (n,(x) 1 (x,))) (x)) /T satisfies Assumption 2 where the hyperparameter is the subsampling ratio 3 2/3 in each tree.
Specifically, To = (1 - 3) 2 from (57) and 76 < 1/6 (from Lemma in Appendix B. Then LOOCV and plug-in provide valid coverages for c(2).
We summarize theoretical comparisons in this section in Table I the first half of which shows our general comparisons terms of both evaluation bias and interval coverage, while the second half illustrates our considered examples.
Table 1: Asymptotic bias and coverage for each approach, where and X denote valid and invalid coverages. o(-), 22.)) and w(.) follow the standard big O notation.
Bias
Coverage Validity
Model
Specifications
c(3) Ap
c(3) Åbcr
c(2) Alooen
Ip
Iken
Ioocy
> 1/4
onn 1/2
o(n 172)
/
General
7h < 1/4, To 1/4
o(n onn21/2/ 1/2]
w(n 1122
oln
/
X
Toe 1/4
A(n 1122)
Q(n 0122/
X
X
1
Linear-ERM.
Onn
O(n-1)
V
/
Specific d
kNN with ki 1/4)
((n 1/8)
O(n
o(n-1)
X
X
/
KNN with k., = 2/3 2/3
(n 2/3 2/3
O(n 1/122
X
Forest with 0.4
(n -033
w(n w(n-1/6)
X
/
Finally, we point out that Theorem 2 also shows, in addition to our evaluation target c(é), the coverage on the oracle best performance c(=*). The latter is generally different quantity than c(2), but it plays an important role our analysis. When 7 > 1/4, c(2) and e(=*) are very close and an interval for c(2) &) is also valid to cover c(2") ). On the other hand, when 7 S 1/4, the statistical discrepancy

---

between c(2) and c(2*) is too large for any interval estimates of c(2) to be valid for e(>*), but nonetheless LOOCV and plug-in for %o 1/4 can still validly cover c(2) thanks to their small evaluation biases.
4 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 | which are unknown in the literature, require 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 [8 IO However, [18] only shows that CLTs hold for c(2) when On 8, o and does not show exactly when CLT fails; [00] only gives CLT's for CVs with different center than c(2), c(2*). In this regard, our main technical contribution theoretical gaps and characterize necessary conditions, instead of merely sufficient conditions, to conclude interval (in)validity across the entire spectrum.
fill in these
4.1 Evaluation Bias
One key component of Theorem I hinges on the characterization of optimistic bias for plug-in, namely Ep, [c, (2) c(a)], which captures the underestimation amount of the objective value relative to the truth when using empirical estimator:
Lemma 1 (Plug-in Bias) Suppose Assumptions 7 and hold. For 2(-) in Assumption ED. [c, ED. [c(2)] (n2222n)) O.
The proof of Lemma relies novel second-order Taylor expansion centered at the deterministic decision (z) := [x)] on both the empirical gap e, (2) Cn (2,) and the true gap c(z,)) -c()) in nonparametric models (-). Here,
not center them at the limiting decision +xx) compared with the parametric setup from 4 36 since in nonparametric models, 2(-) 2n (-) 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 [x]] 2, (z)ll²) and [[[] 2n (Xx) [[]] which requires a more involved analysis through comparison on the asy asymptotic expansion terms of 2(-) 2n, (-)- To understand the optimistic bias further, we provide a constructive proof for kNN with an optimistic bias (11/k,) Proposition in Appendix D.I
The results for CVs follow from the observation that K-fold CV (where here K can be any number up n) gives unbiased evaluation for the model trained with n21 1/K) samples:
Lemma 2 (CV Bias) Suppose Assumptions
and 4 hold. For 2(-) in Definitions 7 and 1
Ep, [Acce] Ep, [c(2)] O(K=1n 27) O. E A ED, [c(2)] o(n -1 0.
4.2 Interval Coverage
The proof of Theorem Saaremm@hinge Thinges on the following equivalences of conditions among stability, conver- gence rate, and coverage validity. For plug-in, have:
Theorem (Equivalence among Stability, Convergence Rate and Coverage Validity for Plug-in)
Suppose Assumptions ? Blnd Then the following three conditions are equivalent:
S1 Bn = 1/22 52: lim P(c(2) E Ip) = aa S3
To > 1/4.
Theorem 3 shown through three components of arguments, where the first two are our new technical contributions:
(1) S3 sufficient for S1. Intuitively, a faster rate of 7v means that the effect of one data point is usually small, implying fast pointwise stability. This result follows from refined decomposition of the variability term =(x: ((-0)()) through the influence of each point based on the asymptotic expansions of ε()) Assumption
2 We examine bias and variability respectively, with formal
results provided in Proposition 5 Appendix E.I.]

---

(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 interval invalidity. From Lemmal [
if S3 does
not hold, i.c. To 1/4. 4. then Ep Cr (2) c()) = On 1/2) and this implies that S2 does not hold
from Proposition 2 in Appendix E.1.2
(3) S1 is sufficient for 92. This follows from direct verification of Lemma 2 in 18 ensure asymptotic normality for plug-in in and the small variability of the interval width (Lemma 7 in Ap-
pendix C. Furthermore, due small difference between c(2) and c(2*) (Lemma Appendix the plug-in interval can also cover the quantity ED, [c{2)] and c(=") if > 1/4 (i.e. Corollary Appendix 1.1.4).
In the above, we show that the condition B, = onn or Yo < 1/4 is a necessary and sufficient condition ensure valid plug-in interval if Assumption Assumptionnhoods holld. Note that [88] demonstrate that in specific nonparametric model, Assumption plug-in by providing counterexample (Lemma 3 there). Our results are not directly comparable to theirs. First, we assume Assumption throughout the entire paper and show that plug-in does not provide valid coverage guarantees when another stability notion, Bn, 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 [8].
4 is a necessary condition for the coverage invalidity of
Theorem (Equivalence between Convergence Rate and Coverage Validity for CV) Suppose Assumptions 7 3 and hold. Then for K K-fold CV, the following two conditions are equivalent:
$4:72 1/4,
$5 lim IP(((2) E [Rew) =
For LOOCV, we always have lim,,- P(c(2) E [toocv) 1 a. However, lim P(((z*) Im) < 11 a, Vm E {kcv, looce} i S 1/4.
To understand the necessary condition for K'fold CV, since is small, the difference between the expected performance between the decision a(x) and s(~Ne) is not negligible, leading to a larger overestimate of performance from c(2) compared with the interval width. However, following the stability condition from Assumption LOOCV can still provide a valid coverage guarantee for c(2), since the difference between en ()) and Atooey is always (n-n1/2)) In contrast, the sufficient condition for S5 follows by the asymptotic normality of CV through verifying Theorem I in (10).
Numerical Experiments
Setups. We consider two synthetic experiments validate our theoretical results: (1) Regression
problem: {(2; Y) (2-Y);: (2) Conditional value-at-risk (CVaR) portfolio optimization: E(2; Y) 2. 2 - = with 2 = (= = (zp, 2 1 2p = 1, Zp 2 0} for some r) E (0, 1). In the regression example, we consider ridge regression, kNN with k, = ((n2/a), and Forest with / 0.4 (recall Example 4 In portfolio optimization, we consider sample average approximation (SAA, which belongs to Assumption
I and KNN with ki ((n2/4). We run plug-in, 5-fold CV and LOOCV with nominal level a 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(²*); ); (2) Interval Width (IW); and (3) bias: Difference between c(²) and the midpoint of the interval E[((()] - E[A.].
Full experimental setup details are deferred to Appendices F. and F2 with results of more K-fold CV results with K 2, 10, 20. Moreover, we present a real- cal-world regression dataset in Appendix F3
Table 2 shows that, in terms of coverage, parametric models including ridge regression and SAA cover both c(²) and c(=") when n is large, across all methods. On the other hand, nonparametric models (kNN and Forest) incur invalid coverages, due to their slow rates 7 < 1 1/4. When using kNN with k; = (nz only LOOCV provides valid coverage for c(2) (nearly 90%) while plug-in and 5-CV fail when n becomes larger. When using Forest and kNN with A, = (n2333,, plug-in is valid while 5-CV does not work. This matches the theoretical coverage guarantees in Table
Results.
Table 2 also reports interval widths and biases to understand how some of the intervals fail. Lengths comparable across each method, with plug-in usually shorter than LOOCV and 5-CV, This can be
8

---

attributed to that plug-in in approximates 2()) better while extra variability arises from the data splitting in CVs, an observation in line with those [8] Biases are relatively large for nonparametric models for all methods. However, when n is large, both kNN with Kn (n22/a) 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(2) (i.e., within [0.85, 0.95]) and boldfaced values in parantheses mean valid coverage for c(²").
IW and biases for kNN and Forest in the regression problem are presented in unit x109. Results
on other sample sizes and numerical reports on standard errors can be found in Tables 3 and in
A Appendix F
method
7
Plug-in
5-CV
LOOCV
cov90
IW
bias
cov90
IW
bias
cov90
IW
bias
Regression Problem (d,
10, dg
1)
Ridge
1200
0.77 (0.95)
0.16
0.02
0.55 (0.31)
0.18
-0.08
0.78 (0.90)
0.17
0.00
2400
0.85 (0.97)
0.11
0.01
0.84 (0.92)
0.12
-0.02
0.86 (0.95)
0.12
-0.00
4800
0.88 (0.93)
0.08
0.00
0.89 (0.92)
0.08
-0.01
0.89 (0.92)
0.08
0.00
kNN n 2/3
2400
0.84 (0.00)
1.63
0.08
0.78 (0.00)
1.68
-0.38
0.85 (0.00)
1.64
-0.01
4800
0.87 (0.00)
1.11
0.03
0.66 (0.00)
1.14
-0.37
0.86 (0.00)
1.11
-0.03
9600
0.88 (0.00)
0.75
0.02
0.61 (0.00)
0.77
-0.28
0.88 (0.00)
0.76
-0.01
Forest
2400
0.77 (0.00)
1.77
0.26
0.66 (0.00)
1.83
-0.37
0.72 (0.00)
1.80
0.01
4800
0.86 (0.00)
1.19
0.47
0.47 (0.00)
1.24
-0.32
0.85 (0.00)
1.20
-0.03
9600
0.85 (0.00)
0.73
0.11
0.42 (0.00)
0.76
-0.28
0.90 (0.00)
0.75
-0.02
Optimization (d, = 5, dy = 5)
SAA
1200
0.82 (0.88)
0.04
0.00
0.82 (0.87)
0.04
0.00
0.89 (0.88)
0.04
-0.01
2400
0.90 (0.89)
0.02
-0.00
0.91 (0.89)
0.02
-0.00
0.92 (0.89)
0.02
-0.01
KNN 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
00:000
6 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 method over another should also take into account the variability and computational demand, specifically:
For parametric and nonparametric models with fast rate (y > 1/4, including the so-called sieve estimators in [19] when the true function f(x) is 2dz-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 (r. 1/4, < 1/4), which include KNN with h; = w(v in Example 3 and the forest learner in Example 4 plug-in and LOOCV negligible but K-fold is not. Correspondingly. both plug-in and LOOCV provide valid coverages but K'folld CV does not. Since plug-in is computationally much lighter than LOOCV, it again preferred.
the biases in
For nonparametric models with slow rate (7, S 11/4), which include kNN with k, = ((vn) in Example 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 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 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) I2 32 bias-correcter K-fold CV B0 [] and bias-corrected plug-in [27 351 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-van validation, e.g., fold number increasing with n [S] can potentially help improve the statistical cinisticl--cmpuuatiionaall 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 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 high level, this is because the evaluation bias may be correlated among different hyperparameter values and ultimately lcading 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 in for model selection 43 56 [2]. We provide further discussions on the failure cases of the plug-in in procedure for model selection in Appendix G.T
Asymptotic versus Nonasymptotic Behaviors. Our results asymptotic and there is an obvious open question on extending to finite-sample results. Nonetheless, our results still shed light on the finite-smpll performances of different approaches. For example, our numerical results, which show finite-sample coverage behaviors in Figure and Table conform to our asymptotic theories. Note that there are some non-asymptotic intervals based on concentration inequalities with exact coverage guarantees 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 the asymptotic setting where n - 0o and X'Y, 2 are of fixed dimensions. Future work includes investigating different model evaluation approaches under other regimes, including high nigh-dimensiooal 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 nested cross-var vols--vliiotion procedure to remedy. However, this latter procedure designed for -igh-dimensional parametric models and does not help in the slow rate regimes of nonparametric models in our setting. We provide further comparisons in Appendix
Smoothness and Stability. 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., 77.
10

---

Acknowledgments and Disclosure of Funding
The authors thank the area chair and four anonymous referees for offering many useful comments and valuable feedback. We gratefully acknowledge support from the InnoHK initiative, the Government of the HKSAR, Laboratory for AT-Powered Financial Technologies, and the Columbia Innovation Hub Award.
References
[1] Karim Abou-Moustafa and Csaba Szepesvári. An priori exponential tail bound for k-folds tross-validation arXiv preprint arXiv: /o.. 05801, 2017.
[2] Karim Abou-Moustafa and Csaba Szepesvári. An exponential efron-stein inequality for i_g stable learning rules. In Algorithmic Learning Theary, pages 31-63. PMLR, 2019.
[3] Anass Aghbalou, Anne Sabourin, and François Portier. On the bias of k-fold cross validation with stable learners. In International Conference on Artificial Intelligence and Statistics, pages 3775-3794, PMLR, 2023.
D Anderson and K Burhham Model selection and multi-model inference. Second. NY: Springer-Verlag. Verlag, 63(2020):10, 2004.
Sylvain Arlot and Alain Celisse. survey of cross-validation procedures for model selection. 2010.
[6] Susan Athey, Julie Tibshirani, and Stefan Wager. Generalized random forests. The Annals of Statistics, 47 10:1148-1178, 2019.
[7] Morgane Austern and Wenda Zhou. Asymptotics of cross-validation. arXiv preprint 11X111200.111111 2020.
[8] Gi Ban and Cynthia Rudin. The big data newsvendor: Practical insights from machine learning. Operations Research, 67(1):90-108, 2019.
[9] Stephen Bates, Trevor Hastie, and Robert Tibshirani. Cross-validation: what does it estimate and how well does it do it? Journal of the American Statistical Association, pages 1-12, 2023.
[10] Pierre Bayle, Alexandre Bayle, Lucas Janson, and Lester Mackey. Cross-validation confidence intervals for test error. Advances in Neural Information Processing Systems, 33: 13:16339 16350, 2020.
[11] Güzin Bayraksan and David P Morton. Assessing solution quality in stochastic programs. Mathematical Programming, 108:495-5144 2006.
[12] Ahmad Beirami. Meisam Razaviyayn, Shahin Shahrampour, and Vahid Tarokh. On Optimal Generalizabil- ity in Parametric Learning. In Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
[13] Dimitris Bertsimas and Nathan Kallus. From predictive to preseriptive analytics. Management Science, 66 (3):1025 1044, 2020.
[14] Patrick Billingsley. Probability and measure. John Wiley & Sons, 2017.
[15] Olivier Bousquet and André Elisseeff. Stability and generalization. The Journal of Machine Learning Research,
2002.
[16] Alain Celisse and Benjamin Guedj. Stability revisited: new generalisation bounds for the leave-one-out. arXiv preprint www.i: 1608.06412, 2016.
[17] Zachary Charles and Dimitris Papailiopoulos. Stability and generalization of learning algorithms that converge to global optima. In International conference machine learning, pages 745-754. PMLR, 2018.
[18] Qizhao Chen, Vasilis Syrgkanis, and Morgane Austern. Debiased machine learning without sample-splitting for stable estimators. Advances in Neural Information Processing Systems, 35:3096 3109, 2022.
[19] Xiaohong Chen. Large sample sieve estimation of seni-noopaaameetric models. Handbook of econometrics, 18549-5632.. 2007.
[20] Guang Cheng. Moment consistency of the exchangeably weighted bootstrap for semiparametric m- estimation. Scandinavian Journal of Statistics, 42(3):665 6664446666666666 2015.

---

[21] Vietor Chernozhukov, Whitney Newey, Rahul Singh, and Vasilis Syrgkanis. Adversarial estimation of riesz representers. arXiv preprint arXiv:2101.00000 2020.
[22] Denis Chetverikov, Zhipeng Liao, and Victor Chernozhukov. On cross-validated lasso high dimensions. The Annals of Statistics, 49(3):1300 1317. 2021.
[23] Matthicu Comec. Concentration inequalities of the cross-validation estimate for stable predictors. arXiv preprint 1iv: 1,513,, 2010.
[24] Luc Devroye and Terry Wagner. Distribution free performance bounds for potential function rules. IEEE Transactions on Information Theory, 25(5):601-604, 1979.
[25] John C. Duchi and Feng Ruan. Asymptotic optimality in stochastic optimization. The Annals of Statistics, 49(1). 2021. doi: 10.1214/1-AOSS133
[26] Sandrine Dudoit and Mark J van der Laan. Asymptotics of cross-validated risk estimation in estimator selection and performance assessment. Statistical methodology. 2(2): 154, 2005.
[27] Bradley Efron. The Estimation of Prediction Error. Journal of the American Statistical Association, 99 (467)x119633) 632. 2004. doi: 10.1198/01621
14.11988006244440000000606777 4504000000992.
[28] Andre Elisseeff, Theodoros Evgeniou, Massimiliano Pontil, and Leslie Pack Kaelbing. Stability of randomized learning algorithms. Journal of Machine Learning Research, 6(1), 2005.
[29] Adam N. Elmachtoub, Henry Lam, Haofeng Zhang, and Yunfan Zhao. Estimate- Then-Optimize Versus A Stochastic Dominance Perspective, 2023.
[30] Tadayoshi Fushiki. Estimation of prediction error by using k-fold cross-validation. Statistics and Comput- ing. 21:137-146, 1.
[31] Seymour Geisser. The predictive sample reuse method with applications. Journal of the American statisticul Association, 70(350):3203325 1975.
[32] Ryan Giordano, William Stephenson, Runjing Liu, Michael Jordan, and Tamara Broderick. A swiss army infinitesimal jackknife. In The 22nd International Conference on Artificial Intelligence and Statistics. pages 1119--1444 1147. PMLR, 2019.
[33] László Györfi, Michael Kohler, Adam Krzyzak, and Harro Walk. distribution-ffee theory of nonparamet- ric regression. Springer Science & Business Mcdia, 2006.
[34] Trevor Hastie, Robert Tibshirani, Jerome H Friedman, and Jerome H Friedman. The elements of statistical learning: data mining, inference, and prediction, volume 2. Springer, 2009.
[35] Garud Iyengar, Henry Lam, and Tianyu Wang. Hedging against complexity: Distributionally robust optimization with parametric approximation. In International Conference on Artificial Intelligence and Statisticx, pages 9976-10011. 1. PMLR, 2023.
[36] Garud Iyengar, Henry Lam, and Tianyu Wang. Optimizer's 's information criterion: Dissecting and correcting bias in data-driven optimization. arXiv preprint arXiv:2306. 10081, 2023.
[37] Satyen Kale, Ravi Kumar, and Sergei Vassilvitskii. Cross-validation and mean-square stability. In ICS, pages 487-495, 2011.
[38] Nathan Kallus and Xiaojie Mao. Stochastic optimization forests. Management Science, 69(4):1975-1999 2023.
[39] Ravi Kumar, Daniel Lokshtanov, Sergei Vassilvitskii, and Andrea Vattani. Ncar-optimal bounds for cross-validation via loss stability. In International Conference Machine Learning, pages 27-35. PMLR, 2013.
[40] Henry Lam. On the impossibility statistically improving empirical optimization: A second-order stochastic dominance perspective. arXiv preprint arXiv:2105.1341) 2021.
[41] Henry Lam and Huajie Qian. Bounding optimality gap in stochastic optimization via bagging: Statistical efficiency and stability. arXiv preprint AXXi:1810002944 2018.
[42] Jing Lei. Cross-validation with confidence. Journal of the American Statistical Association, 115(532): 1978 1997,197,222 2020.
12

---

[43] Sifan Liu and Edgar Dobriban. Ridge regression: Structure, cross-validation, and sketching. arXiv preprint urXiv:1910.02333, 2019.
[44] Wai-Kei Mak, David P Morton, and R Kevin Wood. Monte carlo bounding techniques for determining solution quality in stochastic programs. Operations research letters, 24(1-2):47-56 1999.
[45] Sayan Mukherjee, Partha Niyogi, Tomaso Poggio, and Ryan Rifkin. Learning theory: stability is sufficient for generalization and necessary and sufficient for consistency of empirical risk minimization. Advances in Computational Mathematics, 25:161-18 1931, 2006.
[46] N. Murata, S. Yoshizawa, and S. Amari. Network information criterion-determinin the number of hidden units for an artificial neural network model. IEEE Trunsactions on Neural Networks, 5(6):865-872, 1994. doi: 10.1 109772.329688.
[47] Yoichi Nishiyama. Moment convergence m-estimators. Statistica Neerlandica, 64(4):505 507, 2010.
[48] Pratik Patil, Yuting Wei, Alessandro Rinaldo, and Ryan Tibshirani. Uniform consistency of cross-validation estimators high-dimensional ridge regression. In International Conference on Artificial Intelligence and Statistics, pages 3178-3186. PMLR, 2021.
[49] Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al. Scikit-learn: Machine learning in python. the Journal of machine Learning research, 12:2825- 2830, 2011.
[50] Meng Qi, Yuanyuan Shi, Yongzhi Qi, Chenxin Ma, Rong Yuan, Di Wu, and Zuo-Jun Shen. A practical end-to-end inventory management model with deep learning. Management Science, 69(2):59--77 773, 2023,
[51] Utsav Sadana, Abhilash Chenreddy, Erick Delage, Alexandre Forel, Emma Frejinger, and Thibaut Vidal. A survey of contextual optimization methods for decision making under uncertainty. arXiv preprint arXiv:2306. 10374, 2023.
[52] Alexander Shapiro. Monte carlo sampling methods. Handbooks in operations research and management science, 10:353 425,53-425,,0 2003.
[53] Alexander Shapiro, Darinka Dentcheva, and Andrzej Ruszczynski, Lectures stochastic programming: modeling and theory. SIAM, 2021.
[54] Mervyn Stone. Cross-validatory choice and assessment of statistical predictions. Journal of the royal statistical society: Series (Methedological), 36(2):111-133, 1974.
[55] Aad W Van der Vaart. Asymptotic statistics, volume 3. Cambridge university press, 2000.
[56] Stefan Wager. Cross-validation, risk estimation, and model selection: Comment on paper by rosset and übbsirran. Journal of the American Statistical Association, 115(529):157-160, 2020.
[57] Stefan Wager and Susan Athey. Estimation and inference of heterogencous treatment effects using random forests. Journal of the American Statistical A Association, 113(523): 122823):1228-1222 2018
[58] Shuaiwen Wang, Wenda Zhou, Haihao Lu, Arian Malcki, and Vahab Mirrokni. Approximate Leave-One Out for Fast Parameter Tuning in High Dimensions. In Proceedings of the 35th International Conference Machine Learning, pages 5228-5237. PMLR, 2018
[59] Jon Wellner and Aad van der Varrt. Weak convergence and empirical processes: with applications to statistics. Springer Science & Business Media, 2013.
[60] Ping Zhang. Assessing prediction error in non-parametric regression. Scandinavian journal of statistics, pages 83-94, 1995.
13

---

Appendix
A Other Related Work and Discussions
Plug-in Approaches in Standard Stochastic Optimization. In the classical stochastic optimization without covariates, the interval of optimal model performance constructed centered the plug-in approach set as empirical objective solved by sample average approximation [33] Furthermore, to address the low coverage probability of the naive interval 44 52 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 generally easy compared with estimating the currentperfornance of function 2(-) or x () in the contextual stochastic optimization due slow rates and casy violations of the asymptotic normality.
Generability models with y < 1/4. In general, many nonparametric models converge with rale y & 1/4. When E(z;Y) denotes the &g loss, models such as sieve estimators [99 satisfy the fast rate 1/4. However, to the best of our knowledge, these models difficult to implement in the general contextual stochastic optimization problem arising from decision complexity. Standard benchmarks there in Assumption 2 may still suffer from y < 1/4 (also imply from Lemma follows), surging the need for studying the evaluation approaches under these regimes.
B Details in Section 2
B.1 Technical Lemmas
We list the following technical lemmas as well as discussions on their positions in this paper.
Lemma (Standard M-estimator Result, from Theorem 5.21 in (55) For each in an open subset of Fu-
clidean space. Let w - (a) be measurable function such that 0 + (a)) is differentiable 9g for almost
every with derivative V P.mo, (x) and such that for every 01, 02 in neighborhood of Ao and measurable
function K (xx) with RE. [K (x)) < oo:
|mr, (2:) mag (x) S [() - 02l1.
Furthermore, assume that the map Bg- (mo(z)) admits a second-order Taylor expansion point of maximum 0o. f Tn Os, then:
Vnlū - 00) - -V 1 V mms (X:) o1)).
In particular, the sequence vT(0 Ou) is asymptotically normal with zero and covariance matrix
oog Eg- /V (x) Vx) (x) V
We refer readers to Theorem 5.31 in [SS] under constrained cases.
Lemma justifies the convergence rate of standard parametric learners. This result is the convergence in distribution for 0 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 Mcsstmmator ([59 47 (20), we can transform the
convergence in distribution for in Lemma to the moment convergence result by: [D,, [n]]@ 8" [13] < oo
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 distribution.
Lemma (Lyapunov Central Limit Theorem, extracted from Theorem 27.3 (14) Suppose
(Xi...., Xn....) is sequence of independent random variables, each with finite expected variance of. Define s Ei= of If for some Lyapunov condition lim (1/5 2+5) Σ" E|| 1111 (1|2+t1] satisfied, then we have:
Σ
(X:- 1). 111
This Lyapunov CLT gives asymptotic normality guarantees when the variance X; is not bounded, which happens frequently when it comes to the asymptotic expansion in nonparametric models.
Lemma 5 (Minimax Nonparametrie Lower bounds, extracted from Theorem 3.2 in 33 Consider the class of distributions (X, Y) such that:
14

---

1. X is uniformly distributed in [0, 10:
2. Y =f(X) + where e is the standard normal; And X and are independent.
3. f(X) globally Lipschitz continuous such that for all 21, 22 E R we have: 15(z)) f(02)1 1
C|| - x2
We call that class distributions by pC, then we have:
Ep, II -1
lim inf inf n-000 Ta (X.Y)EPO
2 C1 > 0,
2dg
C Czaa Itds
for some constants C1 independent of C.
Consider {(2; Y) = (a - Y)? Then any estimated 2(-) = f.(.) from Dn satisfics such lower bound. Recall
the bias-variance decomposition of (1)x(.)) - fll?, as long as 2(-) converges to (5).), then 7 S 24d," that is,
cither YBB S 24d or < 24d. This justifies the rate of y/ in Example
B.2
Technical Regularity Conditions
We first list extensions of assumptions nonsmooth and constrained problems, which both natural in literature 58 29]:
Assumption 5 (Regularity of Cost Function) For any E V, R(=YY) is differentiable with respect almost everywhere. [8(2; Y) Mo and Y M1 uniformly Furthermore, E(z; Y) can be written as composite function f(h(z; y)), where h(2; y) R x R + R is twice differentiable with respect everywhere in for any E 3: f(() R R has finite non con-differentiable points and twice differentiable almost everywhere.
E Z and almost surely y-
Note that E(2; Y) -1 satisfy such condition.
Assumption 6 (Optimality Conditions with Constraints) The decision space Z and the optimal solution satisfy the following:
1. 2 C Rd= is open in the form {z E 18== : g2(z) S O, E J1; 0. E J2) with J J1 U U and g;(2). Vj E J twice differentiable with respect to z for any 2. For any x, of (x; is twice differentiable with respect to near 27)
2. The KKT condition holds for the oracle problem. That is, for any given the optimal decision 2 (== argmin,gg v(2,x)) exists and is unique for almost every x, with 20(x) and its Lagrange multiplier {ar (z; 2)e satisfying the first-order condition:
V=((=((T):)) Eajla:
JEJ
and the complementary slackness condition
3. For any x E X, V=: = E. definite.
is positive
B.3 Examples and Justifications of Parametric and Nonparametric Models
B.3.1 Parametric Models
We assume G(O; :r) can be any parametrized decision with respect to 0 and x. which includes linear and more complicate models in both supervised learning, and contextual stochastic optimization problems 8 50
Assumption 7 (Additional Conditions Assumption adapted from Assumption 7 in (9) Suppose As-
sumption 6 holds. And for models in Assumption for any E X. G(0;z) is twice differentiable and Lipschirz continuous with respect to 0 in neighborhood 8* argmingge Eg [e(G((; X Y)] (exists and unique). We allow either of the following two scenarios:
1. When Z is unconstrained set (i.e. Assumption VeEsy [u(G((";));)) = 0. And
V x [v(G(O; zz); æ)) is invertible for any 0 O and positive definite 0 = 0";
15

---

2. When 2 is constrained set (i.e., Assumption 6 suppose for any a E X. az (2;00) is twice differen- tiable with respect to 0 near 0"; At the point 0 0º. =x0 and its Lagrange multiplier ai (0"; (x) satisfy the first-order condition:
ValBex v(G (2);))
Bex laj (0 ; (G(O" :x)] (00)00)))))))))))))))))))))));
0:
JEJ
0, Vj E J, 0, X. And Bx [T(G(0;));; (;= Voor(G((: ZJEJ 0j (T) (T) oog; oog (G(O;))))) is invertible for any E @ and positive definite at 0 = 0
and the complementary slackness condition az; ( (G
In Assumption ! the first-order optimality condition holds for the empirical 0; And we assume Aa/n S C for some C as goes to infinity. R(0) is twice continuously differentiable for any 0 e θ and V o0 R(0) is uniformly bounded for any 0 O
These conditions naturally imposed to investigate the constrained stochastic optimization problem in We verify that 7 = 1/2 for parametric models.
25
29
Proposition 1 (Convergence Rate in Parametric Models) For parametric models in Assumption 7 have 7 77=7 7ou 1/2.
Proof of Proposition 7 For simplicity, we only consider the unregularized case. In the setup of Assumption assume the following two minimization problems have unique solutions with:
i
argmin FCB
(()().).):..
argmin Ex (r,,, ((G(((:)))) ( ece
Suppose Assumption 7 holds. Then combining Lemma
3 we have:
If 2 an unconstrained set, we have:
Vū(ō- - 0') = ([
Σ X)) + op))); V
2. If Z is constrained set, following Corollary 1 of 25 we have:
- = Pr [, [[(G((;))):)
Vol(G((' + o1))
where Py = A ) A and A denotes the matrix of with rows Ex VVg, (G(O r.)) J.
Regularization cases can be derived similarly (like Theorem in (40). No matter in each case, following Assumption 1 due the bounded cost, gradient condition in Assumption
2 we have 7 1/2 since [B]]](xx)
2" (x)]lx) = E[] x)
G( 2)1 O(Il
[|2)) O(n -1/2). And since the dominating term just
the variability term
VooEr (G(()
+ E. Vol(G(O"; Yi), have Tv 1/2. D
This G(O; æ) can be any function as long as satisfies Assumption 7 Furthermore, (G0; x), E ) does not necessarily include the underlying best 2 (x). Since the constrained expansion is similar than the unconstrained version and the moment convergence can be implicd from convergence in distribution, in the following, we mainly focus the unconstrained case of models satisfying Definitions [ [nd
B.3.2 Nonparametric Models
We consider the unconstrained optimization problem under Assumption 3 Especially, we denote E(ā(x)] (a function over 2) the root of Ep, (Eig (x) Y.) 0, ve and abbreviate it z,. in the following. Recall from Assumption 2 given Dr., we obtain the solution by:
a(x) E argmin
(n)(())((2; Vi). (E
Σ
(6)
TEN
Assumption (Expansion Conditions) Suppose the following expansion holds for the decision obtained from 6 for the corresponding Wn,ii
H
xxx) 2. (x)
D
W V...c))Vell....)) + 27r),
(7)
sE(n)
16

---

where H V. 20,,D, (x)) (x))) (J} Intuitively. this result is obtained using similar routines as
M-estimator theory from Lemma 3 since 2(x) 2n (x) = (1(1) and conditions for 0 and 6 there holds similarly for 2(x:) 2n (x) here. In the following for each specific learner, we classify it through the following the two classes:
2(x) - 2- (x) Bu,a +
E
(z((X,, (0)))>))
(8)
x))
(EN(D
2(x) (x) Bud
Σ
(m (i), op(n~)))
(9)
where Br. = O(n denotes the deterministic bias termn across these two classes, i.e., En (2) - (x).
For the variability term:
In the first case for almost every I, we have: (1X,((XX)))) = O, ([X, YDJI <
Do, (N(Da, x)
(n) Furthermore, for i E [m], we have: Ex (0x, ((X,, Y.)) = 0 and
Blllox YO
In the second case for almost every x, we have: Be (axr))lnn,((Xx11) = 0(n Va; Furthermore, for [m], we have: Ex,ion ((X;, Y.)) and (Ex, Il,,,, ((G, YO) O(1
O,
Therefore, ( Yi) Hp... u (x) V V. ;);;; Y.), where (x.)(x) depends on X.
following, we verify a number nonparametric models satisfying or (2). Specifically, we show that Examples 3
satisfy these conditions and present their convergence rates Y, Yo T and corresponding o as
follows.
Example 3 Recall a(x) obtained from Example 3 with a hyperparameter k.. then if we choose kn min Min[Cron (Cn" ---] 1) for some C, 8 > 0 from Theorem 5 of [3] a(x) converges to (x).
Proposition 2 (Convergence Rate of KNN Learner) KNN learner, we denote Ba, S CB& (0)
==())l o ). where i is the nearest sample among random points near the covariate and and the order of Br,z can be tight with respect to n from Lemma
variability term can be regarded as the empirical optimization over a problem where the underlying random distribution is mixed distribution over kn conditional distribution with equal weights near the current covariate Furthermore:
H
2(x) - =xn))
Σ V=l(z((z)VV)) + (p Nr.
(10)
kn
(ENDn.a(kn)
where H Vin.ena (1(n Y)i the expectation over all the possible datasets D.. and the kn neighbors around x. Therefore, VD..* = Op ( (v².) following the M-estimator theory of empirical optimization due to kn samples around. There, (1X(, Y.)) = H V v.((z.(0)) Y.) from 8
One can show that ITOp is a special case of 8 In this case, the convergence rate of 2(-) -())))))))
Op (##) 1/de V Vkn with being some parameter. Tuning the best kn ((14))))) yielding the con- vergence rate 7 2.42. This result may attain the lower bound of estimation even in the regression (i.e. Lemma 5 above) such that y 2.43p Therefore, the learner usually belongs to the slow rate regime (7 < 1 when d, is large).
On other hand, for a number of other nonparametric models, we verify the condition that holds and check the corresponding rate "/, 76 with c(2, Y)- = (2 - Y)² to illustrate basic propertics the learner for readers to get familiarity, where (x) becomes E|y [x] there.
Example 4 We recall existing results from 557 6
Example (Convergence Rate Random Forest Regression) When we have no constraints, reduces to similar problems as in the mean estimation z (x) = [[ (7). Then we can represent Ba = 2(x))
78 logit mw) 1ig 10g
E[{(x)) = 0
and &n. ((,,, Y.) (X, Y.)] -E(T) through Hajek projection
17

---

for some bounded random variable T such that ((X,,((X,,X))) = On Here, where 8n. is the subsample size with lim Sn. 00, limm-so log" (n)) by Theorem 8 in 157) and Theorem in (G] for 8n n², where us means training examples are making balanced splits the sense that each split puts at least fraction w of observations in the parent node and x 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 convergence rate : and 5. logl [oo[]-=)) Certainly, this also does not obey the lower bound result around discussion Lemma
2dg log
We demonstrate that some kernel estimators also satisfy our previous conditions:
Example 6 (Kernel Learner) (x)) K((X, /ma) with the hyperparameter hn and the kernel K(-). where K a >> I with | ((x)dr < cc. Standard kernels include the naive kernel K(x)) ||llaas and Gaussian kernel K (z) exp( 11=11 |=]]²).
Specifically, for regression problem, we have:
Example 7 (Nadaraya- Wattar Regression (33) Consider the Nadaraya Watson kernel regression E(x) (x(x-X,) X,) Ej=1 En Ka x,j for some K₁ (x(x) K (x//h)/h This is the solution when E(2; Y) = (z Y)² Then Kg (a-X()
BR. (x) ((((z)) and ((,x((X,, Y.))
[e(Kn,, (Y, (Y,-E[y]X.). If choose h On 2, )
then holds for many classical kernels,
Gaussian kernel K(x) = -exp(-llazt and naive kernel
K(x) [(1 for constant
Proposition 3 (Convergence Rate of Kernel Regression) Suppose X follows uniform distribution 11 and Y f(X) + g(X)e for the normal with some bounded functions f(X), ((X). When we take (x) (1) (See more details in Chapter of (331), then Ba, O(ba) and Vo
(m dz/3) as long as we tune lo such that ho - and nh - 0o as n cc. And
D On, On, ((X., Op(n 11/2 dz/2) with:
Φn.x( vi)) = =(Y; - E[Y (I) t/a = (p de/3)
Φn.x; ((Xi, Yi)) = (Yi E|Y X.I) = Op(1n
In this case, the convergence rate of 2(-) - (-))
h/2 4./2 1/2//1///2 hn) We obtain y d,
when setting
Nn = O(n u. ). This usually belongs to slow rate regime (7 4)-
Remark 1 (Usage of Regularity Condition in Assumption 8 In the following proof. when comes non- parametric models, we split into two conditions that all the nonparametric models satisfy (8. where we replace with 100 if needed since so far we only consider KNN learner in such category, or 99 should work.
B.4 Examples of Stability Conditions
Example (Expected LOO Stability of kNN Model) For Example with kn 1, we can reparametrize the data-driven decision (i.e. å(x)) by
8(x) LLEER argmin ((2; Yj),
2E2
where R, X is the region (neighborhod X,) such that the closest point from {Xi)ceju) is X3. Then since the decision is bounded ||=||] S from Assumption 3 we have:
E[(2(X) 20- (
Thus on the I-NN Model.
More generally, k. o(n), the stability condition there be shown through symmetry technique from 24 to obtain ot,. = O (Vk./
Example 9 (Expected LOO Stability of Parametric Models) Suppose the objective E(2; Y) is strongly con- vex and Assumptions 2 and hoold Then a., = O(1/n) in a standard empirical risk minimization approach from [15. which includes all the parametric models we discuss.
18

---

C Proofs in Section 3
The technical details of Theorem Theorem have been specified in Section
Proofs of Theorem This follows from combination of the results in Lemma and Lemma] 2
Proofs of Theorem This follows from combination of the results in Theorem 3 and Theorem
Before going the detail proofs of evaluation bias and coverage guarantees for both plug-in and CV estimators, we first mention two lemmas that will he used in the following detailed results:
Lemma (Performance Gap) Suppose Assumptions and 3 hold. For 2(-) in Definitions 7 Mand have <( c(=") Op(nn 21). And ED,, [c{=)] - c(=") C/n +o + 21) for some C > O.
To show this result, we take second recond-order Taylor expansion v(2; at 2 (0)x) and notice first-order term can be eliminated through Assumption 3 without or with constraints.
Lemma (Validity Variability Plug-in and Cross- Validation Approaches) Denote
Vare. (X)= Y)]- Suppose Assumptions and hold. Then variance estimators o in satisfy 03 4 o2; And dee in satisfy 0 4 o².
This result shows the width of each interval docs not vary significantly in terms of O -1/2) and demonstrates the need to study the bias for each approach to distinguish between them.
Proof of Lemma First, consider the nonparametric models in Assumption where x (x) 25 (2:).
Case 1: Z is unconstrained set (Assumption 3). We take the second-order Taylor expansion at the center
(2)) for the inner cost objective v(2;z) Bry [((;; Y),, Vz. isat
Ep- (e(((x))):: E.. (X))
1 Exx (((()) - =0())) ( (() -2 =x())
=
-Ex
= (z)) +
(II)
+ [ (z)1
From Assumption 3 the first-order term above becomes zero since (=)(="(x);)" = 0. And for the second-
order above, we have: 0 N Hax I Ay xd, Vr for some de 0 from Assumption g
This implies
that:
- du B2x [| 2x
05 Fex 1(((x) - (X))
=x)))
2
2
Therefore, we have Ep. [e(E(X); Y)] E. (x):) - - =
Case 2: 2 is constrained set (Assumption 6
Recall V (()))))))) = (==u(=((x): +
Similarly, we take the second-order Taylor expansion at the center 2" (x) for the inner cost v() For each E X, we obtain:
Ejer aj
v(((x);)) (2"())))
-=()) Veu(="(r): x²(x)) + (5(0) - V= - =x))) + ([1 - z ="())1?).
Σ a3(()) (8(x) =-)))) +(ll((x)) - (xx))))
YEJ
2 (8(x) - xx)) (V
Eaj(o)V SEJ
(8(x) x² (x)),
(12)
where the second equality follows by the KKT condition from Assumption 6 And if we take the second-order Taylor expansion for (2) the center x (2x for each E J and E X, have:
g. (}())) 9, (z (z)) Vag, (=))) - = (x))
(13)
(8(x) - x" (x)) V..g, (x" (x)) - x (x)) + -[11((x)) - (x)]
The left-hand side above in 13 converges to since g (3(x)) (x 3 Vjj E B from the first-order expansion of g3 (z) and 2(x)
E. x= (xx) in Definition Summing the terms of 13) over j J with each weight
19

---

being (x) (1)
and plugging it back into 12) to cancel {(x) = ==(x) out in the first-order term, we have:
v(5(x):)) - v(=" (x))a) = (ā(z) - x (4)) Vazu(= (c)) (())))
- ==)))
2
Σ (z) (='(())))))))))))))>))))))))(( و (3(+))) ((] (x))l
jed
= 2 ( 2" (x)) V (=)= (z): =²))) d() - (x))1
(14)
where the second equality above holds by underlying measure Fx and obtain:
13
Then we integrate the left-hand side over i E N' with the
d - -c(²)) Be ((((x) 2' (x)) 220 (x) (x): = (x)) + o(I ==11kxxx)
Then we consider parametric models in Assumption Tif we suppose Assumption hoolds. Here, limiting decision 2" (x)) is often not equal to (r). When we do not have constraints We analyze the first-order term ahove and have: Exx (G() 2" (x)) =
0 under Definitions
[
and asp:add-param-desss -ecrssion
When 2 is unconstrained, in Equation 11 the first-order optimality condition in Assumption 7 gives rise to Ep [V [V=v(=" (====(xx); ()(x))
And the analysis under Assumption I follows similarly as the case of Assumption 2 The only difference being that we directly analyze c(²) cT²") over æ E When
(x))]
constrained, the lirst-order optimality condition in: Vzc(z") + Σjer Ex [aj (0";=" V=)x))VV (x)) =
In both cases, we obtain Ez- [(( - Es- [e(2" (X); = e(] - -= =².
Then since Epy ||| ==I,,,_] O(n 2Tw). Then have:
ED. - c(=")))))))))" C/n o(n 2T),
which finishes the proof.
Proof of Lemma We establish the L, convergence empirical variance term ag true variance
Vary. (X); }] Applying the Li-LLN to (X): since the cost function is bounded, we have:
T))
Σ (X):)))))))) -(==))² 4 Varg-
since Dr, is i.idd and =" =XX) is independent with Dn. Therefore, we need to show that the following term converges to 0:
Ep,
- - (x))))))))(((xx
Ep,,
(((E(X.): co()))² (x(= c(>"))²
(15)
((((())): e== (x=) + EDD, ((())) - 2()))
Er.
2Ep,, [l(()(X:); Y.)) f( (Xi): Y=)o(=))]]
For the first term on the right-hand side in 13 we have:
Epn ((((0))))) - ((sx)))))) s 2M..D. -(=))))))((())))))))
$ 2M, ='())]] +
For the second the right-hand side in 15p.
have:
Ed. (G(())+(e
()) (x2)) ||
+ +ED, [<((3') ((()))((x'))
< Ep.
< M,,
=" (Xx))l + 2MM.D, (lc. - -((=")] 0.
For the third term on the right-hand side in 15
we have:
Pp, [I(e(((()) {(=' (X.):
SEp, (3) - ((= Y.) + Eo. (X -((=)(
Eo, (lx(..) =x(X.]] M,D.B, (lc. ca I|] M.E,, (lon(x") c[>")]] + 0.
20

---

Therefore, we show that the variance estimator of the plug-in estimator converges. In terms of the convergence of &kke. following the same routine before, we also only need to show:
Ep.
Σ
(LECEl- NE (X.):..) - (X(="(X));;x) c(> d(>)))²
kE(K] NEN
Σ EDA
[IOEET (X.;;)))
-c (x) (x)) clz -(z)))
KE]K] KEN;
Then the same emror decomposition in 13 and show that L -onssisitn
D Proofs of Evaluation Bias in Section
D.1 Evaluation Bias of the Plug-in Estimator
Proof of Lemmmal 7 We first consider the case where E(2; Y) is twice differentiable with respect to for all Y. And the proof generalizing to the piecewise twice differentiable function satisfying Assumption is the same as the parametric setup following Theorem from [36]
The bias for parametric models is provided in Theorem from (36] where 1/2 and the bias is O(n 1/2)).
For nonparametric models that satisfy Definition recall the definition of en (x), and we define:
Ti ((E(X.): Σ (x.)(X.);
T- (x): ((3(X):
We expand the term inside the expectation as:
((a(x)): E[((=(X);))] - E[Ti] E [Tp] + E
(x.) (X)]]
E[Ti] B[Tb]. Then the second equality follows by 2..()) is deterministic mapping and the observation that {X,,, Hie(n) are i.i.d.
(i) Consider the nonparametric model with respect to the expansion scenario in 9 For P.. we have: ((x)) 2n (x) = Σm= on.a ((X,, Y)) + (n(w). And that higher-order term (n (w) can be ignored since we only focus on the term with the order of o(n -2x).. More detailedly, ignoring the (I):(-) - zn (-) = o(n 27c) term, we take second-order Taylor expansions to both terms Ti and T2.
2*w).
For the term T1, we have:
E = R
(X:) (X.))
(3(X)) (X.)) ViL ()(E(X))) (x31)
2m
E EVV. on.. Ki)) [[(((X)) (x),,))))) =x(X)))
where the second equality above follows by:
E
=.lz (B(X)))) - 2n (x.1))
(8(X))
Vil(z.
Sn.. ((X., ((X,, x.11)
(16)
B CiV_L(=n (mX, Y:)) + n
Σ E ((z= on,x, ((X,, Y3)]
zzj
V
e.l((z T +0=-
EV (X); (x
21

---

where the third equality above in (16) follows by the independence of the model index under and j under the conditional expectation. More specifically, Vi # J. have:
[[V=((=((X):)x)) on ((X,, YJM = E 2xx,
( =xx (V Y:)) E,g,,, ((X3, Yi)II (g) 0.
The equality (a) above follows by the fact that conditioned on any covariate æ, (on, Y)] = 0. This implies the last equality of (16).
For the term T2, we have:
T2 F VV (E. x(X)] - -x( - (Ix)) 22. (X))
((( zn (x,,) (x)):
where the first equality of T2 follows by the chain rule the conditional expectation under stochastic D.::
[[V=((=n(X)::) (#(X) 2. (X))] B [V_((,, Ex(a(X)
(x(ea) 2., (X)]] 0,
On the other hand, show that the second-order term of right-hau hand side of [[] and B[7,] is o(n o(n 27) We only consider the case of 1. This is because generalizing to case of dg only requires to sum over each elementwise component from matrix (2(x) en (z()) - 2, (z))
We first consider bounding the difference as follows:
x2x.4 (llxa))(xx
(X)II Exx (x)) zn (x.)1l
||]
G x, ((X,, x3)) |
Sr x (( X.))
E
+ oonn" 200)
B. x.
Yi))]
Ex,x, ( ((Xg, Ex 10,x (1x, X(iI + oln 21)
n
sE[m]
n2 (Ex, [xx,[02,x, [02.x ((X,, Y.)]] Exx, x. Io ((X,, K.Il o(n -111-210) = o(n 21o),
(17)
where the second equality above follows by expanding ( Ei= on ((X,, Ki)) ( Ei= &, (.)) such that the inner product terms of X; and X, cancels out. Then we apply the result from Assumption 2 obtain the result in (17).
and
Then we consider the noise difference that incorporates the Hessian matrix, that is putting V (x, into 2(X.) - 2n (x.))) and V (X)( Y) into 2(X) z,, (X). Note that if we take Fzzl(2,(X))))
o((X, ()X,((X Y)) T. then we can replace the original influence function Φ (xx, Y)) with 2 ((X, ()x((X))))
which does not affect the order of the influence function with respect to π the term
since 9((X, Y)) is of the constant level. Then it reduces to the similar analysis in Epx. a [xx =n =x)]]= - -ex,,=ll=(() za (X.))
Therefore, based on the results above, the numerator part of the only bias term in 16 becomes:
((xx((X,
|EFEx,r,IV VVl((n (X)
-Exx(Wo,x (X Esy, Tr T
= =EF(x.r) [T| V. (V)
O (x,r) [Wn, (X)]= (m11-200)
where H. = Er. (X) Y)] and the last equation follows from
(ii) Consider the nonparametric model with respect to the expansion scenario 10
Consider the expansion
of [[[i]] and 72. following the similar proof calculations to cancel out the term Ep xll((() - 2n (X)]1]]
Epy . [[x((( (X.) [1'] and plugging in the expansion, we have:
B[T + Tı]
e(n, ()))) k. (
O(n 12200
kn
Ain
[V or ox ((X.) ((XV)) On -270 > 0. which finishes the proof.
Therefore, in both cases,
22

---

Proposition 4 (Optimistic Bias for kNN) Suppose Assumptions 7 and 3 hold. Consider KNN extimators in Example
3 then there exists P PxX.Y) (n) (n) for each such that the bias term ED. (c) c()) (1/k.)
(11 2%0
In the proof of Proposition 4 construct IP, (1)) mixture distribution where the marginal support Fxx of each component separate and the conditional distribution Fyj for within each component is the same. Then to analyze the bias, we need 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/nn) bias with n samples; In our kNN case, we have kn effective samples used to obtain 2 3(X,) for each E [n]] therefore constituting an (1/k.) bias.
We state the following non-contextual bias lemma before diving into Proposition
Lemma 8 (Optimistic Bias in Stochastic Optimization from [46
36 Suppose Assumptions
3 holds.
Consider the sample average approximation (SAA) solution {(x) 2, Vx E X, where:
1 Σ 72
2 argmin 2E2
E(2; Y.),
Then: E EL ET ((2 1B(((2; Y)
+ + for some C < 0.
Proof of Proposition 4 For cach pair choice and k.. construct an example of P(x,)). W.l.ogg, assume kn := 2kd E & and construct the following multi-cluster distribution Px = Eie(kn) R., 1xER, U(R,), where U (H.) denotes the uniform distribution over the region H., the area of each [&s being the same. We can partition the regions {Rl |ee[,,, such that diam( Rt) < d(R,, R2), Vi and j * i. Therefore, E| 1x,eR,1 = 2kn, Vj. And each conditional distribution Y|X Eie(ka.) Pf- XER, for k, distributions {Fy, [A,]].
Under the event (E:= 1X,ER, 2 kin Vj]. each in-sample decision 8(X.) only selects data from same region and incurs the same optimistic bias as the SAA method. Recall 2(X,) from Example 3 is equivalent to the SAA method using that kn samples since it uses the data from the same Y distribution as X, conditioned each X; (i.c. some P.)) That is 8(X;) argmingeN,... indices Ne which includes Y, and other kn points from the same cluster.
f(2; Yj) for the k. nearest covariates X with
Recall the result from the general optimistic bias result in the uncontextual stochastic optimization (Lemma Since (X.) only involves kn samples around X., we immediately have:
1
Ble(a(X:); YJ)EE- B((((((); Y)
Then we show P(E) 1 when is large, which follows from union of kn Chernoff bounds with the multiplicative form applying to n random variables {1x,en, hew Vj E [kr.]. That is:
P(E = P( Σ Lx,ER, < k), &
Σ
Ix,eR, < k..) S kn (kk(-)k.//).
sC(kn]
which converges to 0 exponentially fast with respect to the sample size since we set k. 2((2²) for some 8 > O. Therefore, have:
Σ ((8(X)))3)) = R[((3(X));; Yi)
E((E(()) + P(A) C
TE((E(X)) () +o
ki
kin
[[((a(X): YD)
where the third cquality follows by the fact that: from the comparison between the exponentially tail and k = M(n²).
D.2 Evaluation Bias of Cross- Validation Estimator
Proof of Lemma 2
We first consider the K fold CV for any fixed K. Note that from Lemma Following the performance gap result from Lemma we have:
c(2) c(2 )
C 2
+ o (1-
23

---

Since K-fold CV is an unbiased estimate of model performance trained with ra(1 1/K) samples, then we have:
E E[Akee| = ED,, () =
o(n(1 -
1/K))
Then comparing the two equations above, we ignore the terms of o(n 27) for any fixed K, we have:
C
E[Akcr c(3)
n
1 )
2
x
((1
1/K) 21 1)
2
C
1 -1)
1
n
1
C
2
2
K
2
where the first inequality follows by Bemouli's inequality that (1 + x)) S for [0, and -. the other side, we have:
BI BLA - c(2)]=
n2 10 ((1- 1)
(1 R ) -1 I
4nC
n
Kn
where the first incquality follows from (1- S 1 2x when E (0,
} and the second inequality applies the Bernouli's inequality again. Therefore, the bias of K-fold CV is O 0(K- 2
Then consider LOOCV, which be directly caleulated through the proof of Lemma Suppose in the unconstrained case but take the second-order Taylor expansion with Maclaurin remainder to both c(2(-)) c(=") and c(2) c(="). This obtains:
E)((((-") c(3)] Elc(( " <(="> (F(e(3)] c(=²))
-
- (x) --====(x))) =x(x)) H (E(- (x) ==(() E[(((()) - (x)) Ha(3(x) = (x)))..
B)((((-)))) (z) = (xx)) (Har-0 - (2) -c)-->))))
+ 0(B1I1 (x) - x" (z)) Elll(()) - - =-'(())))) O(n O( 21-1 + o(1/n).
where H. <(())= (1 X(z))=) as the Maclaurin remainder with X(z) 10. 1), Vx. And the
last equality follows by the continuity of H₂ and then recall the stability condition such that RD, FF []]((x) (x)0(()) = On ") and apply both terms.
E Proofs of Variability in Section 4.2
E.1 Variability of the Plug-in Estimator
E.1.1 S3 is sufficient for S1
Proposition 5 (Fast Rate Implies Stability) Suppose Assumptions 2
and Ahold. For 2(-) in Assumption
with 7oo > 1/4, then 8n =o (n (1/2.)).
Proof of Proposition
Note that Vi E [r]]. we have:
Ep, ED,1((X,) - g(-1) (x.) || Ev.
- ED, (x.))
+ (8(X,) E(((X.)) -
- (X.Iil
S (Ex.(5(X.)] - ED, (x.I))
+ ED, (I(((X.) B[((X.))) - (x 9
where the first part denotes the bias difference and the second part denotes the variance difference. Then need to show the two differences term are of order o(n (1/2). We divide them into two lemmas (T.emma and Lemma 1O). Then the result holds.
Lemma 9 (Bias Stability) When a. = o(n-1111 -1/2) and To 1. ED, [8(X.)] Ep, [x(=0 o(n-111 for 2()) in Assumption 2
24

---

Proef of Lemma 9 First. notice that: Ev, (3 = m. (x)] (rx since X, and 5(-0) are independent.
And we have E (() 2( = o(n 1/2 from On = o(n 1/2). Therefore, we only need to show:
B .s (xx)) - 2(xr) = o(n" -/
In the following two cases, we decompose the influence expansion for the two cstimators.
When 2(-) satisfies
(8)
10
specially): Note that ?/v is equivalent saying k. u2( From 10
Vi E [n]. have:
H
[[a(=)] Bpx [zn(x)) EE
Σ
v=llzn(2):133)
+ +o(k,r))
kn
sENDr.e (ki)
-
k..
Bnn
Σ V.l(en(z):Vi))
- o(ko ) =o(kir))
kn
(END..
where the second equality follows by the definition of en (x) such that DD. EiEND (Ka) Val(en(zr; vi]] In contrast, ignoring the term okk; ) in the derivation, we have:
Hrn.x
[X:) - Erx [2n (X:)) = -B
Σ Vellen((3))133)
+ +o(km
kn
jeNDa, X,ikn)
-
H11
Σ
V=l(En(()))X3))
1 kn
E [H Vxl(ea(X))))))
knn
JEND X, (kn)iii
= 0
E [H Vol(zn (X.))())
kn
E [H (X.)
An
where the third equality follows by X. and (Xy) (m) are independent and using the same argument the previous ones ED,, [2 EEIEND (k..) V=l(zn (z); Yi) Therefore, we have:
[(:(X.) [(x)] kn Ep, [H V. (..) Y.] + o(k.) = =(k.) o(n 11/3).
When 2(.) satisfies p following similar results in kNN models, E[š(w)] E[z, o(n 210)
on 1/2). Besides, we have:
E[5(X.)] Epx [zn ElHp!. (ecix,,,..AM.. (.
ElHb!.x, V (X.); Y:)]
o(n 210) o(n 1/23)
Lemma 10 (Variance Stability) When an o/n-1/3) 1/2) and %
> 1. ED, E({(X.)))
(e(-0 (X,) E(a(-(((..))))) (X.))II o(n 1/2) 2(-) in Assumption
2
Proof of Lemma
10
When 2(-) satisfies ( (or (T0) specifically): Ignoring the o(k,²) terms across equalities,
we have:
(E(X,) E(((X.))) (x,) E(
H
H H
Σ
(X)(1)( +
Σ
Kn
An-1
JENDa. X, (km))
JEND 1.X; (bx--1)
H Kn.x V V=I(
H H
H Hoo.:
Σ
-
li-1
kin
JEND (kaditt
We take the expectation to the two terms the right-hand side. For the first term, we have:
H=1 k. X
Ex, [ Val(za (X.): O(R,*)
E
(xl(
hn
An
25

---

For the second term, we have:
H 1.84
B
Σ
(Vel(en(X)):))
kn-1
kn
JENDRiX (An)i
1(
Hy (
H
) Ex XX,
-xx,
Σ
kn-1
knn
JEENDn.X, (kn)azi
where the first equality follows by X, and Disssi are independent. On one hand, we know H 11,x
||
H 1.Kg
H X2
| o(k ". On the other hand:
Han.X, + o1), which implies that: Ex,
km-1
km
EDDAX, |
E (V))()(())):X)) Vel(zn (X,))11(X9);31,))
jEENTA (Kn)iiti
kn LE,, LX, || (X.) 2n xX)] olkin"" 1/2).
Combining these two arguments, we have: Ep,, [(x()) E[)(X.)) (x(-0 -(-) (k,T") + o(n 11/3]- 1/2) for KNN models.
When 2(.) satisfies
we use the notation in Assumption
Then variability difference becomes:
Ep. (=(x.) E(E(X,))) (8 (x.) - B( (X.))I
1 n Dn.x. (X,, + Σ
dn.X;
On-1.X:
((X,, K30,
= B
73
11 ((X,, XIII
(dn, - -n K31)
n
n
1
Ellon, x. [(X,, Y3)J11
1)
O(n 27/) ) O( n 1h) )+ + O(n -1 1, n 1/2- On 270).
where the second equality follows by the fact that Bl ((X, Y)JJ 1 from Assumption the second term [(0n.z 11- ((2, Y,)) beemlsss are 1 i.i.d. random variables with each mean and
variance El[( (n-1.) 1.)) < co. Then the central limit theorem and uniform convergence
imply:
E (ne( 6n M(X9,
= O(n O(n-1/3). This finishes our proof for the variability
stability for nonparametric models.
F.1.2 S3 is necessary for s2
Proposition 6 (Optimistic Bias Implics Coverage Invalidity) Suppose Assumptions and 3 holld When Ep. [B] = Ep,, (2) - c()) = 2(n (1/2),, S2 does not hold.
Proof of Proposition (O,
6 When the evaluation bias E[B.] = -2(n==)) 1), we show that we cannot have: vnB 4
ca verify that Varp, [7: +T2] ofn 25v) through the same analysis as Lemma Therefore, we have: 2T²(T) + Ts) $ (T Tal
Recall from the proof of Lemma I we have: B = T7 +22 (
((1) > by Chebyshev inequality. Denote the right-hand side of the convergence limit as > 0. Besides
Vn(c. - c(zx)) 4 N(0, from CLT and (-) & (-). Therefore, if y 1/4, we have: vnB 4 NCC, if i < 1/4, we have: n 2B 4 C. In both cases, 4y cannot provide valid coverage guarantee for c(2).
E.1.3 S1 is sufficient for $2
Proposition 7 (Stability Implies Coverage) Suppose Assumptions and 4 Aoldd Then $1 implies $2.
26

---

Lemma 11 (CLT for Plug-in Estimator) Suppose Assumptions 1 2 3 and hold. If B.. o(1- then the plug-in estimator Ap in
satisfies vn(A, c(²) 4 (0,
Proof of Proposition
This result directly follows by the combination of I. Lemma 11 and Iemma
The proof Lemma 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 9 E which is finction of that is estimated through (Vi)se(m) and g is estimated through (Vi) MVG and there exists some go such that "3 go, denote A(Vig) = [. g)] and
An (V: = a Ei= a( g). Suppose we have the following condition:
B.g' 0) O = o(n" 1/2), Vi [n]:
Bg D.v [la(V 9) a(V.g (0 o(n (kmn-),,, Vi [n]
and for 91.92 E G. B[(a[V: ((VVg))) v LE. || 92ll2 for some < cc. Then vT((AA@) A(go)) (An (0) Ag( (1).
Proof of Lemma 17
This result follows by considering c(3) and c(>") as empirical and population version
of the objective, terms An (-) and A(-) there in Lemma 12 Compared with our notion, we need to verify the following three conditions:
6(200)0))000000 g Biae)))(((((()))11 (x,) o(n 1/3);
E B - (()
= o(n
For any two measurable function 21 2x we have:
Ep. [(((a (xx( r)) S ((Bex [X]= -22-222222 (x))
for some L > 0 and y cc.
The first two results directly follow by the stability condition that ct,,, Bo = o (n- (1-22) and the conditions in Assumption that V.((2; is bounded. And the third condition is verified through the first-order expansion that:
E xx. bB (((2)](((([[)))))))))))) ((22()))()))))))( Fx ((V) (xx())==xXx)) =x())))
(Eex [ [V<( (Il=I 22002222))) (x))))))
S (B2x ||| 21 (XX 1x
where we take I 2 Epx
(V:((((()) Y)Il [
and q = such that these conditions hold.
E.1.4 Other Details
Corollary 1 (Coverage of Plug-in Estimator's Interval) Suppose Assumptions and F holdd. If 1/4, Ly provides a valid coverage guarantee for c(2). c(==)())))))))) (E.,,,e,,. [e(=)].
For parametric models under Assumption we have 1/2 > 1/4, and the expected LOO stability notion is satisfied. Therefore, Corollary aalways holds for parametric models.
We first state the following result based on the standard Slutsky's theorem:
Lemma 13 (Bias and CLT) For random sequence An satisfying Vo(An. A) S NO(,,0)), if another random
A (m..n//mm/// then vn(A, B) $ N(0,
Proof of Corollary Note that if y > 1/4, we have: (z),((2) c(2)) 4 (0, d²) from Lemma Combining it with Lemma it is easy to see that 4p provides a valid coverage guarantee for c(²).
Furthermore, consider A, = (&) and c(²). And if we set B = Ep. [c{2]] and c(=") respectively, then
we have: B A + (n 1/2) (1122 from Lemma Then applying Lemma 13 we stil have:
Vn(c.(() c(2)) 4 N(0.03)
vñ(c.(2) Ep. (c(2)) 4 N (0, o²). Therefore, provides valid coverage guarantee for c(>") and Lp_,, c(3)).
27

---

E.2
Variability of Cross-Validation Validation Estimator
Before the proofs of the equivalence condition of cross-validation estimator (i.e. Theorem q we list the CLT for cross-validation.
Lemma 14 (CLT of )ooss-Valliatioo) Suppose Assumptions and 4 hold. Then Akce in 2 satisfies:
(X); /)ı. K. Here the same result holds for VT(( (Akcc - A) 4 N(0, o²) with Ā ExejK B2- [0(3(~N))
Atoocy by setting K-
Note that the asymptotic normality of cross-aaliatiion does not depend on 7, However, the center from the CLT in I Lemma 14fis different from c(2) or c(²"), and the convergence rate ry determines whether the difference is small. Therefore, the validity of the interval for K-fold CV to cover c(2) still depends n.
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) 339 by:
Contimuing from the setup in the main body with Da, we call the loss stability
B (x.,) (((((()) (, -()==
On
12
where (()(X); = ((((X): B. [(((()))
We rewrite Theorem
10 and replace the uniformly integrable condition with our assumptions (since directly implies the uniformly integrable condition there):
bounded cost function condition in Assumption 2
Lemma 15 (CV of CLT from Theorem 1 in 10 Suppose Assumptions Then have:
and hold. If af o(1 ((1))).
Vr A) $ N(
Proof of Lemma 14 show this result, we only need verify loss stability is (1/n) above. This follows by:
- [x -
(E(2 (x):) -x [(-)
S 2(((3(X);)) - 0(28-))0000000 8(2 (X): F))) + ((E(((( Eyc-o (x
For the first term of the right-hand side above, due to the bounded gradient of f, following the first-order Taylor expansion inside the square notation, we have:
(((=(X): Y) {(2 - (X); & - -
Then if take expectation over X, the right-hand hand side reduces Miaa o(1/n).
For the second term of the right-hand hand side above, have:
Y)] - (00 -X),=
2 ( - & [(x(X) - =(x))²)
Then if we take expectation over X, the right-hand side reduces to Mf o(1/n). Therefore, we can apply
Lemma 15 that CLT for cross-validation holds.
Proof of Theorem
We first consider the coverage validity of c(²).
(i LOOCV. Since Lemma 14 holds, in this case, we only need show that the term:
Es (E((((()) = (n 4)).
Ee-
(18)
Then combining this with the Lemma the first-order Taylor expansion to Epyl= [(2; Y)), we have:
13
we obtain the valid coverage of LOOCV intervals for the c(2). From
Ep- (12)(11) (X):
Ep. (((3(N):
(19)
B B2 ((2( (X) {(X)] + +o (1a(-8 (1)(0)))))))))0 (1=(-0(x)-(((1)) -(())), Bax V
28

---

Since the gradient of the cost function V) is bounded and following the stability condition:
Bex (1) [XX]]
11/2)
Therefore, plugging it back above into
19
we immediatcly sec that A Ex Be- (X); Y)]
Ep. (((*(X); = Op (1-1/2) there. Then applying Lemma 13 and Lemma would obtain the result of lim P(c(a) [looco)
a.
on (ii) K-fold CV. For the part that $4 implies $5: if > 1/4, then we can show Ā - c(3) = op(n=1/3) 1/2) too by taking the Taylor expansion for each c()(-Ne)) c(="), Vk E [K] and c(E) - c(="). Then both terms are only or(n=1/3), Then using Lemma 13 witt vni(Aevv Á) 4 N(D, we have: vn((Aa c(a)) 4 (0,
Combining this with Lemma obtaiin S5.
For the part that 55 implies $4, prove by contradiction. Note that i S 1/4, we have: n "A c(a)) 2 C' > from the proof 6 Then if = 1/4, we have vn(ARcr - <()) $ N(C, a a²); if < 1/4, we have: n² ( - c(2) 2 C. In both cases, S5 is invalid. Then we finish the proof.
Then consider the coverage invalidity of c(=)) and prove by contradiction. Suppose otherwise // Akev <(>")) 4. o²) (the coverage validity holds). If 7 < 1/4. then ve (Ater <(=")) 4. Therefore. (AAco - -)(²") Sn However, recall Akce is the estimate n(1 1/K) samples from Lemma 6 we know, nARcc -((²)) 2 C/(1 1/K)² and contradict with the coverage validity condition; I 1/4, we still have n 1/2 (Akco ((=")) 2 C/(1-1/K)) which contradicts with v c(=")) 4 (10, o²).
Therefore, as long as S 1/4, we do not have such coverage for c(>") ") in both K-fold and LOOCV approaches. C
Furthermore. we may provide the coverage validity of CV intervals for c(>*) as in the plug-in in approach when 7 > 1/4.
Corollary 2 (Coverage of CV Intervals) Suppose Assumptions 2 3 and hold. When > 1/4, both Tecu and Trooce in 2 provide valid coverage guarantees for c(2), Ele [2] and c(2
Proof of Corollary 2 Since we are in the situation where Lemma
14 holds. Then when 2(-) - 2 21) = (n-nr)))
we only need to show that A Ep.
= (n )) which is given by the result already presented such that Ep- (c(=(-NN)( (X); y) Ep. [x(="(X): Y)] = O (o)
=" (x) = on +) since [NNel (1 - 1/K) = (z).. Then combining this with Lemma 13 that interval produced in Lemma [4
provides valid coverage guarantees for Ep- [f(2" (X); The argument that the interval provides valid
guarantee for Ep- [(()(X); )] holds similarly.
F Detailed Experimental Results in Section 5
The experiments were run on a normal PC laptop with Processor Core(s), Apple MI with 16GB RAM. took around 80 hours to run all the experiments including regression and portfolio study. All the optimization problems, if cannot solved directly using scikit- -eaan,, 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 run = 500 problem instances. For the standard error reported in Figure and the following tables, we calculate
where a is the standard deviation 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 seales are small.
The corresponding table with a full set of sample sizes n is shown as follows in Table
F.1 Regression Study
Setups. construct synthetic dataset through the scikit-lears using make_ regrressiinnn 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(f) through additional 10000 independent and identicailly distributed test samples.
29

---

Table Evaluation performance of different methods, where boldfaced values mean valid coverage for c(2) (i.e., within [0.85, 0.95]) and boldfaced values in parantheses mean valid coverage for c(2"). IW and biases for kNN and Forest in the regression problem are presented in unit x10*
method
n
Plug-in in
2-CV
LOOCV
cov90
IW
bias
cov90
IW
bias
cov90
bias
Regression Problem (d,
10, dy
1)
Ridge
600
0.76 (0.78)
0.24
0.04
0.08 (0.01)
0.33
-0.34
0.82 (0.59)
0.25
0.00
1200
0.77 (0.95)
0.16
0.02
0.55 (0.31)
0.18
-0.08
0.78 (0.90)
0.17
0.00
2400
0.85 (0.97)
0.11
0.01
0.79 (0.79)
0.12
-0.02
0.86 (0.95)
0.12
-0.00
4800
0.88 (0.93)
0.08
0.00
0.89 (0.92)
0.08
-0.01
0.89 (0.92)
0.08
0.00
KNN 2/8
600
0.81 (0.00)
3.78
0.31
0.66 (0.00)
4.19
-1.53
0.82 (0.00)
3.84
0.05
1200
0.80 (0.00)
2.48
0.12
0.43 (0.00)
2.72
-1.43
0.80 (0.00)
2.50
-0.03
2400
0.84 (0.00)
1.63
0.08
0.30 (0.00)
1.77
-1.21
0.85 (0.00)
1.64
-0.01
4800
0.87 (0.00)
1.11
0.02
0.12 (0.00)
1.20
-1.13
0.86 (0.00)
1.11
-0.03
Forest
600
0.74 (0.00)
4.13
0.82
0.57 (0.00)
4.73
-1.92
0.77 (0.00)
4.32
0.04
1200
0.77 (0.00)
2.71
0.40
0.41 (0.00)
3,06
-1.83
0.69 (0.00)
2.78
0.02
2400
0.77 (0.00)
1.77
0.26
0.29 (0.00)
1.97
-1.54
0.72 (0.00)
1.80
0.01
4800
0.86 (0.00)
1.19
0.15
0.10 (0.00)
1.33
-1.29
0.85 (0.00)
1.20
-0.03
- Optimization (d, 5, d,
5)
SAA
600
0.68 (0.62)
0.05
-0.00
0.61 (0.65)
0.05
-0.00
0.71 (0.78)
0.05
0.00
1200
0.82 (0.88)
0.04
0,00
0.82 (0.87)
0.04
0.00
0.89 (0.88)
0.04
-0.01
2400
0.90 (0.89)
0.02
-0.00
0.91 (0.89)
0.02
-0.00
0.92 (0.89)
0.02
-0.01
kNN n 1/4
600
0.00 (0.00)
0.31
2.41
0.83 (0.00)
0,81
-0.22
0.91 (0.00)
0.76
-0.05
1200
0.00 (0.00)
0.23
2.01
0.65 (0.00)
0.53
-0.21
0.92 (0.00)
0.50
-0.03
2400
0.00 (0.00)
0.17
1.72
0.42 (0.00)
0.35
-0.17
0.92 (0.00)
0.33
-0.00
4800
0.00 (0.00)
0.12
1.43
0.15 (0.00)
0.23
-0.17
0.88 (0.00)
0.22
-0.00
Models. We consider the following optimization models by calling the standard scikit-learn package: (1) Ridge Regression Models, implemented through linear saarrr_ooeelie Ridge (alpha = 1); (2) KNN, imple- mented through gherrsseeerrrroor with nearest neighbor number being 2 (3) Random Forest, implemented through RandoonForertRRgressso with 50 subtrees and sample ratio being n 0.6
Additional Results. Table 3 reports all results in regression (and the portfolio optimization) case, which is a superset Table Table 4 we present the standard error of the interval width and bias for each method used in 3 The bias size of plug-in and 2-CV are significant if we take the size of the standard deviation into account. Here, the plug-in approach still has the smallest standard error of the hias and interval width.
Table 4: Interval Widths and Biases for each Evaluation Procedure for the Regression Problem (Mean and Standard Error).
method
a
Plug-in
2-CV
LOOCV
IW
bias
IW
bias
IW
bias
Ridge
600
0.24
0.04++0.00
0.33+00.00
-0.34+0.01
0.25=0.00
0.00=0000
1200
0.16=0.00
0.02+00.00
0.18+
-0.08++0.00
0.17=0.00
0.00=0.00
2400
0.11 00
0.01
0.12:00.00
~0.02220.00
0.12=00.0
-0:00 00
4800
0.08
0.001 00
0.08
-0.01 00
0.08:00.00
0.00 0.00
KNN
600
3778.222447.22
314.75-+63.4
4187.77
-1332.71
1840.78-+448.8 04
-54.78=63446
1200
34777447:30.88
115.55:2:4466
2718883::33..6
-1428. 284
2503.31::311
24.788=4.770
2400
1628.36:+19.4 16
80.66=27.45
1771.38+221.0
-1206. 12.33
1638. (638.95-:100 19.99
-25.37=27.49
4800
1108.7 1334446
23.85=18.05
(199.71=144.0
-1130.71
1113.23++13.60
-27.48=18.99
Forest
600
4132.75
824.40172.64
4733,39.101.40
-1917.23:91.12
4315.90137.17
41.13481.11
1200
2711 233433336661
404.59:4499.4
3062.29-441.00
-1832.96:770997
2782.08-+37.55
24.61+62.26
2400
1 1768.86=22406
259.31+:32.17
1966.98-22i.s
-1543.64456.67
1801.58+24.62
13.72+44.225
4800
1 1185.55:16.51
145.36: 18.48
1328.21
-1287.63+--2222
12011.0+:16.0
-10.49=31.94
We change the fold number to be 5, 10, 20 to allow variabilities in the fold number. We run all procedures again and report results in Table 5 Although K-fold CV with large number of K has better coverage when is small compared with that of 2-CV in Table 3 n becomes larger. the coverage becomes smaller while the bias
30

---

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.
Table 5: Performance Evaluation of 5, 10, 20-CV Intervals compared with plug-in in estimator in the Regression Problem (Mean and Standard Error), where boldfaced values mean valid coverage for c(2) (i.c., within [0.85, 0.95J), IW and bias for each procedure are presented in unit x 10 and each entry is averaged over 200 experiment repetitions.
method
Plug-in
5-CV
10-CV
20-CV
cnv90
IW (hias)
cav90
IW (bins)
cov90
IW (bias)
cnv90
IW (hias)
Regression Problem (da
10, d,
1)
Forest
1200
0.777
2.71 (0.40)
0.62
2.83 (-0.42)
0.65
2.81 (-0.48)
0.69
2.74 (-0.30)
2400
0.77
1.77 (0.26)
0.66
1.83 (-0.37)
0.60
1.76 (-0.29)
0.64
(-0.23)
4800
0.86
1.19 (0.15)
0.47
1.24 (-0.32)
0.56
1.26 (-0.38)
0.63
1.24 (-0.18)
9600
0.85
0.73 (0.11)
0.42
0.76 (-0.28)
0.52
0.73 (-0.22)
0.51
0.74 (-0.17)
19200
0.86
0.47 (0.07)
0.34
0.49 (-0.23)
0.42
0,48 (-0.13)
0.45
0.48 (-0.11)
KNN 2/3
1200
0.81
2.48 (0.12)
0.76
2.57 (-0.46)
0.77
2.51 (-0.46)
0.76
2.48 (-0.21)
2400
0.80
1.63 (0.08)
0.78
1.68 (40.38)
0.72
1.62 (-0.29)
0.74
1,71 (-0.24)
4800
0.84
1.11 (0.03)
0.66
1.14 (-0.37)
0.70
1.15 (-0.21)
0.68
1.14 (-0.18)
9600
0.88
0.75 (0.04)
0.61
0.77 (-0.28)
0.69
0.70 (-0.15)
0.70
0.69 (-0.12)
19200
0.85
(0.04)
0.49
0.47 (-0.23)
0.66
0.46 (-0.09)
0.68
0.46 (-0.04)
CVaR-Portfolic Optimization (d, 5, dy
5)
KNN 12
2400
0.00
0.172 (1.716)
0.76
0.337 (0.079)
0.82
0.328 (0.035)
0.85
0.329 (0.028)
4800
0.00
0.126 (1.423)
0.74
0.221 (0.038)
0.79
0,218 (0.034)
0.80
0,217 (0.025)
9600
0.00
0.094 (1.108)
0.66
0.147 (0.029)
0.72
0.146 (0.028)
0.76
0.144 (0.021)
F22
CVaR-Porffolio Optimization
Setups. We set = 0.2, d2 = dg = d. = 5 and Px = N E) with (E), 0.81-=1, vi,j. And the
conditional distribution (Y)++== 0.3 x (Bz); + sin ||>||||
vi [ds] for each ~ (0,
Models. We consider the following optimization learners for the subsequent performance assessment: (1) Sam- ple Average Approximation (SAA): We ignore features when making decisions but consider the same decision space (= E 2). That is, for any covariate x, we output the same decision; E argmin = 1 -e [((2; Y)]:
And the convergence rate 7 1: (2) KNN: We the model from Example with k, min miim n 1}. In this case, the convergence rate g. which violates the validity condition of both plug-in and K-fold CV intervals.
F.3 Regression Study in the Additional Real- World Dataset
We include one real-world dataset puma32t with 33 features and 1,000,000 samples regression task. We report the coverage probability of plug-in, 2-CV, and 5-CV for kNN model with k;, = 2/3, where each entry denotes the coverage probability estimated over 100 experimental repetitions for that procedure in Table Here each experimental repetition is conducted differently by shuffling the entire dataset. For given sample size the procedure is 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.
Table 6: Coverage Results of the method KNN in the dataset puma32H, where boldfaced values mean valid coverage for c(3) (i.e., within (0.85, 0.95)).
10000
20000
40000
Plug-in
0.94
0.93
0.90
2-CV
0.88
0.81
0.76
5-CV
0.91
0.86
0.81
In Table 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.
The dataset is available htttps://ww..poott http://www..oommooorrr//////////
31

---

G Further Discussion and Comparison
G.1 Additional Discussion in Model Selection
A difference between the model selection and model evaluation task focus in this paper is that in the former, focus the performance rank between different models instead of the ahsolute performance value. Intuitively, the accuracy of the performance rank depends on not only the evaluations the compared models, 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 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 casily leads naive selection.
Selecting hyperparameters: Consider the best regularized parameter in the ridge regression. Plug-in always chooses
since has the smallest training loss;
Selecting the best model class: Consider the regression problem f argmin Ei (f())) for the nested classes F1 C F2 C Fs, and we want select the hest among the three classes. Plug-in always selects the largest class, Fs, since has smallest training loss.
In these problems, CV can select the regularization parameter model class different from the naive choice. hints that CV could better than plug-in for such problem, but theoretically not well- sellrsndddtoodd general cases.
G.2 Additional Discussion in the High- Hiigh-Dimensional Setting
the high-dimensional setting, i.e. feature dimension p and sample size n both go infinity such that p/n converges to a nonzero constant, besides specific problems like (generalized) linear regression, the problem is wide open our best knowledge. For linear models, we have the following result towards the bias of our considered three procodures:
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 E (0, 1), plug-in still suffers a large bias from overfitting and cannot used directly construct the point estimator and confidence interval evaluate model performance. Some bias correction procedures (27] are proposed to construct consistent point estimators in these gegh-dimessionll scenarios.
For K-fold CV, the point estimate also suffers from non-vanishing bias 58 and may not be 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, theoretically valid coverage guarantees exist for high-dimensional linear models the literature, since almost existing literature is based on some stability conditions and only valid under low dimensioonl asymptotic regimes (17 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 = as in regression problems. We show the simulation results in Table 7 where both plug-in and 5-CV suffer from large bias and have coverage. The hias 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 important to devise improved CV or bias correction approaches.
Table 7: Evaluation performance of high-dimensional ridge regression (100 repetitions) in the regression problem
(n. p)
Plug-in
5-CV
LOOCV
cov90
bias
cov90
bias
cov90
bias
(300, 200)
0.00
21.63
0.00
-48.72
0.59
-0.38
(900, 600)
0.00
4.62
0.00
-8.45
0.51
-0.03
(1800, 1200)
0.00
2.81
0.00
-5.75
0.58
-0.01
32

---

G.3 Comparison with Nested Cross Validation
We elaborate on the discussion of the nested valsdaalio and show it is not suitable under our slow rate regime. Recall that the nested cross-validation (NCV) in P is designed for improving the covariance estimate nigh-dimensional regimes. Therefore, NCV not help theoretically and empirically:
Theoretical Invalid Coverages. NCV does offer valid eoverages for nonparametric models theoreti- cally: The interval length of NCV is controlled by VMSE. Duc to the restriction v VMSE [SE, SKSE in Scction 4.3.2 in [ (SE= ((n (1/1/) is the standard error in their eq. (2)), this interval length is ( /n' /2) for fixed K. In nonparametric models with < 1/4, this length is overly small compared with the bias of NCV, which is On. 27 for constant C > smaller than that of (2) in main body. This is despite that the CV point estimator in [9] used bias correction their eq. (9), that correction for parametric models not nonparametric models. Then the bias in [9] dominates the interval length and leads to an invalid coverage asympiotically. Furthermore, [9] does not provide rigorous thcoretical guarantees on the valid coverage of their interval (9), in their setting. They only correct the variance estimate for parametric models.
Empirical Poor Performance. NCV does not perform well empirically in our setting: This is expected from the above explanation. We implement NCV with and 10 folds for randomforest the regression problem with the same setup Appendix [.T and report results Table g Here, plug-in, 5-CV, 10-CV correspond to the intervals ( in our paper. For NCV, we use Algorithm
(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 is small, the larger bias order starts exert effect when is large. leading significant drop in the coverage of NCV which hecomes invalid.
Computational Inefficiency. Note that (9] does focus computation expense do in paper comparing LOOCV with plug-in, As mentioned (2), NCV is computationally very demanding. requiring over 1000 random splits to stabilize the variance estimate and needs to refit in total 1000 times.
Table 8: Evaluation performance of NCV versus CV for the forest learner in the regression problem, where boldfaced values mean valid coverage for c(2) (i.e., within [0.85, 0.95]). IW and bias for each procedure are presented in unit x x102 and each entry is averaged over 200 experiment repetitions.
Plug-in
S-CV
5-NCV
10-CV
10-NCV
cov90
bias
cov90
IW
bias
cov90
IW
bias
cov90
bias
cov90
10000
0.88
0.41
7.53
15.06
0.48
-2.65
0.80
30000
0.86
3.73
0.22
0.38
3,82
-2.88
0.74
7.65
-0.56
0.29
3.80
-2.21
0.65
7.59
-1.15
1.71
0.11
1.75
-2.25
3.51
-0.48
0.27
1.73
-1.26
0.56
-0.61
300000
0.88
0.92
0.08
0.13
0.93
-1.76
0.47
1.87
-0.28
0.26
0.92
-0.56
0.4
1.85
-0.31
33

---

NeurIPS Paper Checklist
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 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 the checklist as of the factors in their evaluation. While "[Yes] is generally preferable "[No] justification is given (e.g., "error hars 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 binary way. we acknowledge that the true answer is often more nuanced, so please just use your best judgment and write a justification elaborate. All supporting evidence can appear either in the main paper the supplemental material, provided appendix. you answer [Yes] to question, in the justification please point to the section(s) where related material for the question can be found.
is perfectly acceptable answer "[No] provided a proper
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.
1. Claims
Question: the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction Section cllcarly state claims made with important assumptions and limitations. The claims are supported by a matched theoretical result in Section 3 and experimental results in Scction 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 results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
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 conerete examples in Appendix to elaborate on these assumptions. This paper also discusses the limitations of the general setup from asymptotic perspective and scope of model evaluation instcad of model selection in Section
Guidelines:
34

---

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 encouraged to create separate "Limiittions" 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 scope of the claims made, e-g., 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, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to- system might not be used reliably to provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
applicable, the authors should discuss possible limitations their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play important role in developing norms that preserve the integrity the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
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 Scction some additional regularity conditions in Appendix [8] 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 D Dand
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 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.
4. Experimental Result Reproducibility
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 [ evaluation approach are stated in the heginning Section
The point estimate and interval for each
Guidelines:
The answer NA means that the paper does not include experiments.
the paper includes experiments, 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 dataset and/or model, the authors should describe the steps taken to make their results reproducible verifiable.
35

---

Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same datasct, 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 hosted model (e.g., in the of large language model), releasing of model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require relcasing code, the conference does require submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g.. large language model), then there should either be a way to access this model for reproducing the results a way to reproduce the model (e.g.. 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 welcome to describe the particular way they provide closed-soure source models, it may be that access to the model is limited some way (e.g., to registered users), but it should be possible for other rescarchers to have some path to reproducing verifying the results.
reproducibility. In the case of
5. Open access to data and code
Question: Does the paper provide open faithfully reproduce the main experimental results, described supplemental material?
the data and code. with sufficient instructions
Answer: [Yes]
Justification: The paper provides sufficient instructions Appendix F to reproduce main ex- perimental 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.
Please see the NeurIPS code and data submission guidelines (https://nips... http://iips.cccppbllpppp cc/buiicc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible,
"No" acceptable answer. Papers cannot be rejected simply for not including code, unless this is central the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed the results. See the NeurlPS code and data submission guidelines (https: pettps:/nnic //niss///ppps... cc/pulicc/ guides/Codeeuueen sondeeuubisssiooPPo
reproduce
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only a subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Dete Details
Question: Does the paper specify the training and test details (c.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
The paper specifics brief summary of the experimental setup along with the results in Figure I and Scction 5 This paper also provides all the training and test details at the beginning of the
Justification:
Appendix F
Guidelines:
The answer NA means that the paper does not include experiments.
36

---

The experimental setting should be presented in the core of the paper to level of detail that is necessary appreciate the results and make of them.
The full details can be provided either with the code, in appendix, supplemental material.
Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate informa-
tion about the statistical significance of the experiments?
Answer: [Yes]
Justification: The paper reports error bars of one case for the interval widths and biascs in Figure [ For the error bars of numerical results in the Section report them in Appendix (e.g. in Table 4
And we mention how the standard errors are calculated and specified in the beginning Appendix
Guidelines:
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, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror 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 caleulating the error bars should be explained (closed form formula, call to library function, bootstrap, etc.)
The assumptions made should given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error than state they have 96% CI, if the hypothesis of Normality of errors not verified.
asymmetric distributions, authors should be careful not show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). error bars are reported tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. 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 mcans 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 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethies
Answer:
[Yes]
Justification:
The research conducted in the paper conforms with the NeurlPS Code of Ethics in every respect.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
37

---

The authors should make sure preserve anonymity (e.g., if there is special consideration due laws regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Although the paper focuses on the foundation research on constructing reliable perfor- mance guarantees for cach evaluation approach, this paper discusses the potential positive socictal impact in some parts of Section and the motivation for investigating these coverage guarantees in Section This helps people understand the utility each evaluation approach and correctly and efficiently select one that suits to their setup best.
Justification:
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 unintended uses (e.g.- disinformation, generating fake profiles, surveillance), fairness considcrations (e.g., deploy- ment 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 generate deepfakes for disinformation. On the other hand, it not needed point out that generic algorithm 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 intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative socictal impacts, the authors could also discuss possible mitigation strategies (c.g., gated relcase models, providing defenses in addition to attacks, mechanisms for monitor- ing misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g.. pretrained language models, image generators, scraped datasets)?
Question:
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 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 restrictions access the model 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 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) properly referred, including the scikit-learn package and codes from other papers. Both are referred when they first mentioned (e.g. Figure and
Guidelines:
38

---

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 URL.
The name of the license (c.g. CC-BY 4.0) should be included for cach asset. For scraped data from particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are relcased, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license a dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it changed) should provided.
this information not available online, the authors are encouraged reach out asset's creators.
13. 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 accompanying files.
Guidelines:
The answer NA means that the paper does not release assets.
Rescarchers should communicate the details of the dataset/code/model as part of their sub- missions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. 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, applicable, as as details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The NA means that the paper does not involve crowdsoureing research with human subjects.
Including this information in supplemental material fine, but main contribution of 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.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Does paper describe potential risks incurred by study participants, whether such risks were disclosed the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/revicw based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: This paper does not involve crowdsourcing research with human subjects.
Guidelines:
The answer means that 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.
39

---

We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applica- ble), such the institution conducting the review.
40


Reviews:
[{"review_id": "tnzc01cxcu", "reviewer": "Reviewer_JBLc", "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.", "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)}$?\n2. While the numerical experiments are well-designed, providing results from experiments on real-world data would be even more convincing.", "limitations": "The authors clearly state the limitations of the framework, leaving me eager to see the follow-up work.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. The paper addresses a well-motivated and significant problem to machine learning community: the statistical benefits of cross-validation in model evaluation.\n2. The paper is well-written and well-structured, offering comprehensive background information and connecting its conclusions to existing analyses while highlighting its novelty. The framework presented is versatile, applicable to both parametric and nonparametric regimes.\n3. The encouraging conclusion that the plug-in method performs no worse than CV is supported by robust theoretical analysis and convincing numerical experiments.", "weaknesses": "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.\n2. Although the theories are validated on several synthetic datasets, it would be beneficial to provide experimental results on real-world datasets as well.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank you for your recognition of the importance and clarity of our paper, and also for your very helpful comments. To respond to your main suggestions, we have run additional experiments on model selection and real-world data set. These experimental results will be incorporated into the Appendix. There we will also provide additional discussion on model selection that we leave for future work, which we reveal below as well.\n\n# Model Selection \n\nA difference between model selection and the model evaluation task we focus on in this paper is that in the former, we focus on the performance rank between different models instead of the absolute performance value. Intuitively, the accuracy of the performance rank depends on not only the evaluations of the compared models, but also the inter-dependence between these evaluation estimates. This adds complexity to understanding the errors made by each selection approach. There are some discussion for specific problems, such as linear regression, classification and density estimation (see, e.g., Section 6 of our reference [3]). However, the theoretical understanding of model selection remains wide open in general problems. \n\nThat being said, there are some model selection problems where plug-in easily leads to a naive selection:\n- Selecting hyperparameters: Consider the best regularized parameter $\\alpha$ in the ridge regression. Plug-in always chooses $\\alpha = 0$ since it has the smallest training loss.\n- Selecting the best model class: Consider the regression problem $\\hat f \\in argmin_{f \\in F_i} \\sum_i^n (f(X_i) - Y_i)^2$ for the nested classes $F_1 \\subset F_2 \\subset F_3$, and we want to select the best $F_i$ among the three classes. Plug-in always selects the largest class, $F_3$, since it has the smallest training loss.\n\nIn these problems, CV can select the regularization parameter or model class different from the naive choice. It hints that CV could be better than plug-in for such problem, but this is theoretically not well-understood. Per the reviewer's suggestions, we include some simulation experiments on model selection using plug-in versus CV as follows, where in each case we report the result averaged over 100 experimental repetitions:\n\n## Case 1: Select the hyperparameter in ridge regression\nSuppose we have a \"misspecified\" linear data generating process: $Y = \\sum_i^{50}(X^{(i)} + sin(X^{(i)})) + \\epsilon$ with $X^{(i)}$ being the $i$-th component of $X$ and $\\epsilon \\sim U(0, 1)$. We want to find the best hyperparameter $\\alpha$ from the regularized linear models $\\beta_{\\alpha} \\in argmin_{\\beta} (Y_i - \\beta^{\\top}X_i)^2 + \\alpha ||\\beta ||^2$ that minimizes the expected cost $E[(Y - \\beta_{\\alpha}^{\\top}X)^2]$. We show the model selection results in the following table, where the first column of each procedure represents the best $\\alpha$ that the procedure finds and the second column represents the true cost under such $\\alpha$:\n\n|n | Plug-in | | 5-CV| | LOOCV | |\n|--|--|--|--|--|--|--|\n|80|0.0|105.4|10.1|74.1|12.1|70.6|\n|100|0.0|57.2|34.3 |49.9|24.2 | 50.8|\n|200|0.0|36.8|44.4|36.9| 18.2 | 36.5|\n\nWhen $n$ is small, both 5-CV and LOOCV find a better decision than the plug-in. but the accurate evaluation of LOOCV does not necessarily yield a better selection than 5-CV (e.g. $n = 100$). Plug-in always chooses $\\alpha = 0$ and its relative performance depends on the power of regularizations, i.e., when $n = 200$, adding $\\alpha$ does not improve much and thus the performance of plug-in to both 5-CV and LOOCV. However, when $n = 80, 100$, plug-in suffers from worse performance than 5-CV and LOOCV.\n\n## Case 2: Select the best model class\nGiven each $D_n$, we want to select the best among ridge, kNN, and random forest models. Continue the same data process as Case 1, but with 10 features. In each experimental repetition, we select $\\lambda \\sim U(0, 5)$ randomly and generate data from $Y|X: \\sum_i^{10} X^{(i)} + \\lambda sin(X^{(i)}) + \\epsilon$. We show the results of model selection procedures, where the first column of each procedure represents the probability of finding the correct best model, and the second column represents the true cost under the model selected by each procedure:\n|n | Plug-in | | 5-CV| | LOOCV | |\n|--|--|--|--|--|--|--|\n|100|0.52|46.93|0.88|42.07|0.90 |41.64|\n|200|0.57|42.74|0.88|38.19|0.89|37.86|\n|400|0.71|39.94|0.96|37.26|0.95|37.26|\nHere, both 5-CV and LOOCV help find a better decision than plug-in and there is not much difference between 5-CV and LOOCV.\n\n# Real-world Experiments\nWe include one real-world dataset [puma32H](https://www.openml.org/d/1210) with 33 features and 1000000 samples as a regression task. The codes and instructions for reproducing are in the updated codebase link in the Global Response. We report the coverage probability of plug-in, 2-CV, and 5-CV for a kNN model with $k_n = n^{2/3}$, where each entry denotes the coverage probability estimated over 100 experimental repetitions for that procedure. Each experimental repetition is conducted differently by shuffling the entire dataset. We then select the first n rows as the training sample for each model and approximate the true model performance by averaging over the remaining samples in the dataset.\n\n|n | 10000| 20000 | 40000|\n|--|--|--|--|\n|Plug-in | **0.94**| **0.93** |**0.90** |\n|2-CV|**0.88**|0.81 |0.76 |\n|5-CV| **0.91**| **0.86**|0.81|\n\nPlug-in provides valid coverages in this case while 2-CV, 5-CV do not, especially when $n$ is larger (20000 and 40000). These continue to validate our asymptotic theory.\n\n**Scaling of the Variance**:\nIn equation (2), each datapoint $(x_i, y_i)$ is only used **once for evaluation** since the index of each datapoint is only counted once in one of $\\{N_k, k \\in [K]\\}$, the collection of $K$ partitions of $[n]$.  Note that this formula is the same as the standard all-pairs variance estimator in Theorem 5 in the reference [9].", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "91HAKaYijc", "reviewer": "Reviewer_PDH8", "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.", "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?\n2.Could the authors give an example where \\alpha_n = o(n^{-1/2}) and \\gamma \\leq 1/4?\n3.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.\n4.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": "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.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is clearly written and the message is clean. This paper provides new insights regarding CV and leave-one-out CV on model evaluation. I think this work contributes to a recent line of work on understanding the role of CV in model evaluation and model selection.", "weaknesses": "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}). \n\nThe 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for recognizing our contributions and clarity, and also for raising the list of very helpful questions.\n\nRegarding \"Weaknesses\":\n\n**Difference with literature investigating roles of CV**: First, the reviewer mentions that [8] says CV estimates the risk of the algorithm which explains the poor performance of CV for estimating $c(\\hat z)$. However, [8] is mostly interested in parametric models, where the difference between $c(\\hat{z})$ and $E[c(\\hat{z})]$ (or $c(z^*)$) is generally of order $O_p(1/n)$ and negligible compared with the variability, as we mentioned in Section 1 and 3. Therefore, CV still yields valid coverage guarantees for these parametric models.  On the other hand, it is unknown when such bias is significant and leads to invalid coverages in *general nonparametric models* which is our main focus and novelty.\n\nThe reviewer also indicates correctly that recent literature [6,9] say that CV accurately estimates the averaged performance and provides valid coverage guarantees for this quantity. However, like above, it is unclear when the difference between such an averaged performance and true model performance affects the coverage guarantee for general nonparametric models. \n\n\n**Notations**: We will change the notation $z$ to $\\tilde z$ when referring to the prediction domain.\n\nRegarding \"Questions\":\n\n**Overparametrized-regime**: We assume the dimension is fixed and the sample size goes to infinity in this paper. We agree with you that the plug-in estimator would be zero under overparametrized-regime. However, whether CV would perform better in that regime is still an open question (e.g., K-fold CV does not perform well in our additional experiments; please refer to more details on the high-dimensional case in our Global Response).\n\n**Examples under given conditions**: $\\alpha_n = o(n^{-1/2})$ is satisfied for general random forest and kNN learners from the algorithmic stability literature [14,15,40] discussed in our paper. Moreover, we provide the exact formula of $\\gamma_v, \\gamma_b$ ($\\gamma = \\min(\\gamma_v, \\gamma_b)$) for each learner in Examples 3 and 4 in Section 3. Specifically, in regression problems, $\\gamma \\leq 1/4$ is satisfied for general nonparametric models (including kNN learners in Example 3, Forest learner in Example 4, kernel estimators in Example 7) as long as $d_x \\geq 2$ from Lemma 3 of Appendix B. \n\n**Algorithmic evaluation task**: We agree that algorithmic evaluation is also an important and related task. Our paper focuses on model evaluation but our analysis can shed light on constructing intervals for algorithmic evaluation, especially when the difference of the two targeted intervals is relatively small. In Corollaries 1 and 2 in Appendices E.1.4 and E.2 of our paper, when $\\gamma > 1/4$, both plug-in and CV intervals (1) and (2) (regardless of $K$-fold or LOOCV) provide valid coverages for $E_{D_n}[c(\\hat z)]$; Otherwise when $\\gamma \\leq 1/4$, for LOOCV, since $\\sqrt{n}(\\hat A_{loocv} - c(\\hat z))\\overset{p}{\\to} N(0, \\sigma^2)$ and $c(\\hat z) = E_{D_n}[c(\\hat z)] + O_p(\\sqrt{Var_{D_n}[c(\\hat z)]})$, the LOOCV interval (2) is valid for covering $E[c(\\hat z)]$ when $Var_{D_n}[c(\\hat z)] = o(1/n)$; For plug-in, the condition for the coverage validity for $E[c(\\hat z)]$ is equivalent to $Var_{D_n}[c(\\hat z)] = o(1/n)$ and $\\gamma_v > 1/4$. However, it appears open whether there is a more explicit model rate representation for $Var_{D_n}[c(\\hat z)] = o(1/n)$.\n\n**Sample Splitting**: We agree with you that such sample splitting gives an accurate evaluation for the model trained with $n/2$ samples. However, we are interested in the model trained with a full set of samples $\\hat z(x) = A(D_n;x)$. The expected costs of these two models differ by $\\Theta(n^{-2\\gamma})$ due to the performance gap when using $n$ versus $n/2$ samples, which is similar to the evaluation bias using 2-fold CV. When $\\gamma < 1/4$, the difference is $\\omega(n^{-1/2})$, which is large and exceeds the interval length (of order $\\Theta(n^{-1/2})$). That is, the interval used to evaluate the model with $n/2$ samples cannot provide valid coverage guarantees for $c(\\hat z)$. \n\n**Guidance to practitioners**: \n\nFirst, 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:\n- For parametric models, and nonparametric models with a fast rate ($\\gamma > 1/4$, which includes sieves estimators in our reference [18] when the true function $f(x)$ is 2$d_x$-th continuously differentiable in our Examples in Line 198-202), biases in all three considered procedures, plug-in, LOOCV and K-fold CV, are negligible compared to the variability captured in interval coverage. Correspondingly, all three intervals provide valid statistical coverages. Among them, plug-in is the most computationally efficient and should be preferred.\n- For nonparametric models with a slow rate but small variability ($\\gamma_v > 1/4, \\gamma \\leq 1/4$), which include kNN with $k_n = \\omega(\\sqrt n)$ in Example 3 and the forest learner in Example 4 in our paper, the biases in plug-in and LOOCV are negligible but K-fold is not. Correspondingly, both plug-in and LOOCV provide valid coverages but $K$-fold CV does not. Since plug-in is computationally much lighter than LOOCV, it is again preferred. \n- For nonparametric models with slow rate ($\\gamma_v \\leq 1/4$), which include kNN with $k_n = \\Theta(\\sqrt n)$ in Example 3, only LOOCV has a negligible bias and provides valid coverages, and hence should be adopted. \n\nThe above being said, we caution that, in terms of the direction of bias, plug-in is optimistic while K-fold CV is pessimistic, and so the latter could be preferred if a conservative evaluation is needed to address high-stake scenarios (as Reviewer tGmJ suggests).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "6NJXW58N59", "reviewer": "Reviewer_8MSs", "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.", "questions": "### Questions\n\n- 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?\n\n### Suggestions\n\n- 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.\n- 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.\n- L29: \"Reuses\" should be \"reuse\".\n- L31: \"Model rates\" could mean several things. Be more descriptive.\n- L33: Left quotation mark around \"center\" is not formatted correctly.\n- L258: Title escapes into margin.\n- L352: \"as\" should be \"as they are\".\n- Figure 1: Double y-axes are generally hard to read. I suggest you just divide the plot into two instead.\n- L953: You already have one example 3. Maybe you forgot to use the example environment here?\n- L973: Same as the previous comment. \n- Appendix: Equations escape into the right margin in several places.", "limitations": "- I am missing a discussion on optimistic vs. pesimistic bias\n- The listed limitations should include the limitation of looking at one specific way of constructing the interval estimates.\n- The results have no societal impacts as far as I can tell.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The research area is important and interesting.\n- The theoretical results are presented clearly and I have not found any errors in the derivations (but have not looked closely at the proofs).\n- The assumptions are clearly stated and not overly restrictive.", "weaknesses": "- 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.\n- 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.\n- 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.\n- 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.\n- 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**.)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for recognizing the significance of our results and the helpful suggestions. We address the reviewers' main concerns as follows.\n\n**Our choice of interval estimate, and not use the interval suggested in [8]**: The reviewer raises the valid point that our interval is one particular choice and questions why we don't use the interval in [8]. First, we point out that the interval in [8], namely eq. (9) in [8], which uses nested CV (NCV) in both the point and variance estimates in the interval, is designed for *(high-dimensional) parametric models*. In contrast, our paper focuses on the distinct setting of *nonparametric models*, especially in the most challenging *slow rate* regime. That is, NCV is not designed for, and would not be competitive to our setting. In fact, NCV does not help theoretically and empirically: \n- NCV does not offer valid coverages for nonparametric models theoretically: The interval length of NCV is controlled by $\\sqrt{MSE}$. Due to the restriction $\\sqrt{MSE} \\in [SE, \\sqrt{K} SE]$ in Sec 4.3.2 in [8] (SE = $\\Theta(n^{-1/2})$ is the standard error in their eq. (2)), this interval length is $\\Theta(1/n^{1/2})$ for a fixed $K$. In nonparametric models with $\\gamma < 1/4$, this length is overly small compared with the bias of NCV being $C n^{-2\\gamma}$ (for a constant $C > 0$ smaller than that of eq. (2) in our paper). This is despite that the CV point estimator in [8] used bias correction in their eq. (9), that correction is for parametric models but not nonparametric models. Then the bias in [8] dominates the interval length and leads to an invalid coverage asymptotically.\n- NCV does not perform well empirically in our setting: This is expected from the above explanation. We implement NCV with 5 and 10 folds for randomforest in the regression problem (same setting as Figure 1 in our paper), shown in Table 2 of the attached pdf. While the bias of NCV is controllable and the interval gives nearly valid coverage when n is small, the larger bias order starts to exert effect when $n$ is large, leading to a significant drop in the coverage of NCV which becomes invalid. \n- NCV is computationally very demanding, requiring over 1000 random splits to stabilize the variance estimate (as mentioned in [8]) and needs to refit in total 1000*K times. Note that [8] does not focus on computation expense as we do in our paper in comparing LOOCV with plug-in. \n- [8] does not provide rigorous theoretical guarantees on the valid coverage of their interval (9), even in their own setting. They only correct the variance estimate for parametric models.\n\nWe will include the above comparison discussion with NCV in [8] in our future work part, and include the additional numerical results in Appendix in our revised version. In our comparison discussion, we would properly indicate that [8] focuses on a different setting and hence is disadvantageous for ours.\n\nFinally, back to our interval estimate (2), we stress that our choice is natural -- It is widely used with valid statistical properties and outperformance over earlier works as shown in [9]. [8] also considers this natural choice and shows that it performs well under large samples in their experiment (n>400 in Figure 10 in [8]). Our paper and [8] essentially point out two different problems by using (2): [8] corrects the variance estimate in high dimension but parametric models while we show that this interval does not yield valid coverage for nonparametric models with slow rates.\n \n**Code Reproducibility**: We apologize for not documenting the code well previously. We now provide clean documentation on the experimental configuration for reproducibility and also change the default solver to CVXOPT (open source package). Here is the anonymous link to our revised code: [Link](https://anonymous.4open.science/r/CV_GoldStandard-8E35).\n\n**Empirical results using different fold numbers**: We have shown 5-CV results for the regression problem in Table 5, and newsvendor problem in Table 7 in the paper. To alleviate further the reviewer's concern, we now also provide additional results of 5, 10, 20-CV for regression and portfolio tasks for more sample sizes in Table 1 of the attached pdf. We will include them in our revised version and use 5-CV throughout the main body. As shown in these results, larger K still suffers from coverage problems when n is large, even though it can help when $n$ is small. These continue to support the validity of our theoretical results.\n\n**Results on different dimensional problems**: As other reviewers mention, our main contribution and novelty are for the asymptotic regime with $n\\to\\infty$ and fixed $p$. This corresponds to most classical CV papers with statistical guarantees [5,6,9]. The models we choose, i.e., linear models, kNN, randomforest are common under this setup. Correspondingly, our empirical results are used to validate theoretical results in this regime. Nonetheless, we provide discussions on the high-dimensional case (including p > n) in the Global Response, but we politely point out that this is not our main focus and is worth a separate substantial work on its own (as Reviewer tGmJ also hints).\n\n**Other suggestions**: We use the question form in the title because the answer is not clear-cut - LOOCV is indeed the best statistically but computationally expensive. We will incorporate other great suggestions from the reviewer in our revised paper.\n\n**Optimistic versus Pessimistic Bias**: Optimistic bias refers to underestimating the expected cost. Plug-in suffers such bias since it is evaluated on the same training data. In contrast, pessimistic bias refers to overestimating the expected cost. CV suffers such bias since CV is unbiased for the evaluation using fewer training samples than the whole dataset, and appears more erroneous than it should be compared to the true evaluation using the whole dataset. We will incorporate this discussion after stating the current Theorems 1 and 2.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Ybt9c1h1U8", "reviewer": "Reviewer_tGmJ", "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$.\n\nThe authors make two main very practical conclusions, regardless of model type (parametric or nonparametric): \n\n1. 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.\n2. 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.", "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": "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.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "*Contribution:* CV is an extremely widely used methodology that had, until somewhat recently, very slim theoretical underpinnings. I think this paper is a great help in ameliorating that problem, and it even makes some surprising and well-backed-up arguments about the use of CV in practice. In particular, I don't think many attendees of NeurIPS would believe the statement \"using the training loss is pretty much just as good as using $K$ fold CV\"! But, with this paper (hopefully) at the conference, people may start to ask themselves interesting questions about the use of $K$ fold.\n\nIn terms of a more specific contribution, the authors note that previous theoretical work has been light in many cases where the convergence rate of the model is asymptotically less than $1/n^{1/4}$, whereas their paper details this case (as well as the $>1/n^{1/4}$ case) clearly. I'm not deeply familiar enough with the theoretical CV literature to validate this claim about previous work, but I think this is an important contribution in and of itself if it's correct.\n\n*Clarity:* In general, the paper is pretty well written. It's a fairly technical paper, but the authors do a good job of making it straightforward to read. I even found the first chunk of the proofs pretty easy to read through (although I got tripped up eventually, see weaknesses). Overall, I found all concepts completely clearly and precisely defined, which I think is not true of many theoretical papers submitted to NeurIPS.", "weaknesses": "I have a few miscellaneous comments. I don't think any of them are particularly important with the exception of the first two.\n\n**Claimed strength of results**\n\nThe 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.\n\n**Utility of CV versus plug-in (i.e., training loss)**\n\nThe 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:\n\n1. $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.\n\n2. 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'\".\n\nI'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?\n\n**Small issues in theorems**\n\n1. 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.\n2. In Theorem 2, why do we care about the coverage of $c(z^*)$? Is this just a fun fact? Some interpretation would be good.\n3. 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?\n4. 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.\n5. 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 $<$.\n6. 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.\n7. 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.\n8. Line 130: I think the upper bound on the Hessian here is from Assumption 2, not Assumption 3.\n9. 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.\n\n**High dimensions**\n\nI 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank you for recognizing our contributions both on the theoretical and practical fronts, and also for the detailed and very helpful suggestions. We address your comments point-by-point as follows.\n\n**Claimed strength of results**: We would follow your suggestion and change that claim in the introduction to \"This analysis helps us provide a complete breakdown of how bias and coverage depend on the convergence rate of the model at hand. This in turn fills in the gap in understanding which methods outperform which others, in regimes that have appeared challenging for previous works.\" We will also make similar changes in the abstract.\n\nActually, our original thought was similar to your comment in that we regarded the complete breakdown as a provision of both sufficient and necessary conditions, with the list of assumptions being used to prescribe some regularity in the setting. Nonetheless, we see your very valid point that the use of the term ``necessary conditions\" would cause confusion, and so we would change that as you suggested.\n\n \n**Utility of CV versus plug-in**: \nWe agree with the reviewer on these additional helpful insights, and would add them into our discussion in Section 3. Specifically, \n- In the \"Comparing plug-in and K-fold CV\" part, we would add \"In terms of the magnitude of bias and interval coverage, plug-in is always no worse than K-fold CV. However, in terms of the direction of bias, plug-in gives an optimistic evaluation of the true model performance, while K-fold CV gives a pessimistic evaluation. In high-stake scenarios where a conservative evaluation is preferred, e.g., evaluating the treatment effect of a new drug, K-fold CV can be more desirable than plug-in. \"\n- In the \"Comparing plug-in and LOOCV\" part, we would add \"In these cases where LOOCV and plug-in give similar evaluation intervals statistically, plug-in should be preferred as it is computationally much more efficient.\"\n\n\n\n**Small issues in theorems**:\nFirst, we would incorporate your suggestions in Points 4 (change to lemmas), 6, 7, 8.\n- For point 1, indeed K can scale with n in the result of Theorem 4, and we would clarify the dependence of K there.\n- For point 2, the coverage of $c(z^*)$ is of interest to some problems in stochastic optimization, namely in estimating the optimality gap to decide whether one should stop an optimization algorithm. We have mentioned some of this literature [10, 42, 45, 53, 54] in Appendix A. We would move this related discussion to the exposition after Theorem 2.\n- For point 3, indeed Theorem 4 implies Theorem 1. Nonetheless, our Theorem 1 highlights the difference among the three types of estimators with respect to the sample size $n$ and model convergence rate $\\gamma_v, \\gamma$, which we think is helpful for the reader. We are happy to change and merge Theorems 1 and 4 if the reviewer thinks this would be better.\n- For point 5, the general condition in Line 155 is under $\\gamma \\leq 1/4$. However, the condition in line 156 - 157 is given by $\\gamma_v$. Note that $\\gamma = \\min(\\gamma_b, \\gamma_v)$, so that equality (i.e., the valid coverage guarantee of the plug-in estimator) holds when $\\gamma \\leq 1/4$ and $\\gamma_v > 1/4$. \n- For point 9, we apologize for the confusion in the proof of Theorem 3. First, in terms of Assumption 8, the models we study in this paper are covered in Definitions 1 and 2, while Assumption 8 governs the regularity of the (nonparametric) models under Definition 2. Next, for parametric models, existing theoretical results ([36, 46]) have shown that the bias is of order $\\Theta(1/n)$ (since $\\gamma = 1/2$ as we mention in Proposition 1) under our assumptions. We would incorporate the missing discussion on the relation with Assumption 8 and in terms of the parametric model in the proof in our revised version. \n\n\n**High-dimensional Investigation**:\nThe reviewer certainly raises a good question about high-dimensional investigation. We provide some discussions in the Global Response. Essentially, both plug-in and $K$-fold CV may not perform well in this setting, and while there are works on addressing very specific problems (e.g., linear regression), to our best knowledge it remains an open problem to understand the comparisons among different evaluation methods for general high-dimensional problems.\n\nLastly, regarding whether empirical risk minimization theory can give insights on the performance of plug-in (even in low dimension), our take is that, as this theory is mostly based on non-asymptotic bounds instead of asymptotically exact results (as we mentioned in Section 6), it could be difficult to know whether CV outperforms plug-in or vice versa. Besides, the performance of nonparametric estimators is not directly revealed from the standard empirical risk minimization theory which mostly focuses on parametric models (though with exceptions). Because of these, CV is still more commonly applied than plug-in, even though as our paper suggests plug-in could be superior when taking into account both statistical and computational benefits.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We sincerely thank all the reviewers for their helpful suggestions. In this Global Response, we provide additional discussion on several aspects that address the reviewers' comments: practical guidance from our results, differences with existing literature regarding roles of CV, high-dimensional problems, and additional experimental results.

# Guidance to Practitioners 
First, in terms of the magnitude of bias, LOOCV is always smaller than plug-in, while plug-in is no larger than K-fold CV. Despite this bias ordering, the adoption of a method over another should also take into account the variability and computational demand, specifically:
- For parametric models, and nonparametric models with a fast rate ($\gamma > 1/4$, including sieves estimators in our reference [18] when the true function $f(x)$ is 2$d_x$-th continuously differentiable in our Examples in Line 198-202), biases in all three considered procedures, plug-in, LOOCV and K-fold CV, are negligible compared to the variability captured in interval coverage. Correspondingly, all three intervals provide valid statistical coverages. Among them, plug-in is the most computationally efficient and should be preferred.
- For nonparametric models with a slow rate but small variability ($\gamma_v > 1/4, \gamma \leq 1/4$), which include kNN with $k_n = \omega(\sqrt n)$ in Example 3 and the forest learner in Example 4 in our paper, the biases in plug-in and LOOCV are negligible but K-fold is not. Correspondingly, both plug-in and LOOCV provide valid coverages but $K$-fold CV does not. Since plug-in is computationally much lighter than LOOCV, it is again preferred. 
- For nonparametric models with slow rate ($\gamma_v \leq 1/4$), which include kNN with $k_n = \Theta(\sqrt n)$ in Example 3, only LOOCV has a negligible bias and provides valid coverages, and hence should be adopted. 

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


# Comparison with Existing Literature Investigating Roles of CV
Our paper considers a distinct setting from [8] in that we consider general nonparametric models instead of (high-dimensional) parametric models, and provide corresponding theoretical guarantees on bias and coverage on competing procedures. To this end, it has been unknown when the biases of these procedures are significant and lead to invalid coverages in *general nonparametric models* which is our main focus and novelty. Additional discussions are provided in response to Reviewer PDH8. 

To address the variance estimate problem for high-dimensional parametric models,  [8] proposes nested CV (NCV) in both the point and variance estimates in their interval. However, their remedy is not designed for, and also is not empirically competitive, on the nonparametric settings that we consider. Additional discussions are provided in response to Reviewer 8MSs.

# Additional Experiments
In our attached pdf, we include additional numerical results using different $K$ in CV in Table 1, which continues to provide the insights that K-fold CV suffers from poor coverage when n is large; We also include numerical comparisons between naive CV (in equation (2) of our paper) and nested CV (in our reference [8]) in Table 2; and some high-dimensional simulations in Table 3.

Here is the anonymous link to our revised code: [Link](https://anonymous.4open.science/r/CV_GoldStandard-8E35) 

# High Dimensional Discussion
For the high-dimensional setup, 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, it is known regarding the bias of our considered three procedures that:
- 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 \to c \in (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 ([26]) 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 [W2018] and may not be a good choice for evaluating model performance. 
- For LOOCV, recent literature [W2018,P2021] 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 ([6,8,37] and ours).  

For our three procedures, we validate claims for the point estimates above and also investigate the coverage performance of interval estimates (open question), using the same simulation data setup for ridge regression with $\alpha = 1$ as in our regression problems. We show the simulation results in Table 3 of the attached pdf, 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.

[W2018] Wang et al. Approximate LOO for fast parameter tuning in high dimensions. ICML 2018.

[P2021] Patil et al. Uniform consistency of cross-validation estimators for high-dimensional ridge regression. AISTATS 2021.

Meta-review: 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.
Decision: Accept (poster)