Fast Computation of Leave-One-Out Cross-Validation for $k$-NN Regression
Authors: Motonobu Kanagawa
Venue: Accepted by TMLR ()

Abstract: We describe a fast computation method for leave-one-out cross-validation (LOOCV) for $k$-nearest neighbours ($k$-NN) regression. We show that, under a tie-breaking condition for nearest neighbours, the LOOCV estimate of the mean square error for $k$-NN regression is identical to the mean square error of $(k+1)$-NN regression evaluated on the training data, multiplied by the scaling factor $(k+1)^2/k^2$. Therefore, to compute the LOOCV score, one only needs to fit $(k+1)$-NN regression only once, and does not need to repeat training-validation of $k$-NN regression for the number of training data. Numerical experiments confirm the validity of the fast computation method.

Published in Transactions on Machine Learning Research (12/2024)
Fast Computation of Leave-One-Out Cross-Validation for K-NN Regression
Motonobu Kanagawa Data Science Department EURECOM
noteoobb.kanngouueeeeeenn
Reviewed on OpenReview: https: openreview. net/ forun? id= quz2
Abstract
We describe a fast computation method for leave-one-out cross-validation (LOOCV) for k-nearest neighbours (k-NN) regression. We show that, under tie-breaking condition for nearest noighbours, the LOOCV estimate of the mean square error for k-NN regression is identical to the mean square error of (k + 1)-NN regression evaluated on the training data, multiplied by the scaling factor (k + 1)2/k² Therefore, to compute the LOOCV score, one only needs to fit (k 1)-NN regression only once, and does not need to repeat training- validation of k-NN regression for the number of training data. Numerical experiments confirm the validily of the fast computation method.
1 Introduction
1977 is classic nonparametric regression method that often performs surprisingly well in practice despite its simplicity (Chen et al. 2018) and thus has been
k-Nearest Neighbours (k-NN) regression (Stone
actively studied both theoretically and methdologically (e.g, Györfi et al. 2002 Kpotufe 2011 Jiang 2019
Azadkia 2019 Madrid Padilla et al. 2020 Kpotufe and Martinet 2021 Lalande and Doya 2023 Ignatiadis
et al.) 2023 Matabuena et al.) 2024). It has a wide range of applications such as missing- -aluu imputation
(Tryaankaaya et al. 2001), conditional independence testing [Runge 2018 outlier detection (Breunig al.
2000), approximate Bayesian computation (Biau et al. 2015). and function-valued regression (Lian 201
to just name few.
For any test input, A-NN regression obtains its k-ncarest training inputs and averages the corrosponding k training outputs to predict the test output. Thus, the number k of nearest neighbours (and the distance function on the input space) a key hyperparameter of k-NN regression and must. be selected carefully. Indeed, theoretically,
is known that k should increase as the training data size increases for k-NN regression to converge to the true function (e.g., Györfi et al. 2002 Theorem 6.2). Hence, one should not use a prespecified value for & (e.g., = 5) and must select A: depending the training data.
A standard way for selecting the hyperparameters of a learning method is cross-validation (e.g., Hastie et al. 2009 Section 7.10). However, cross-validation can be costly when the training data size large. particular, leave-one-out. cross- cross-validene validaaniottoon (LOOOVV (Stone) 1974) can be computationally intensive since, if naively applied, it requires training the lcarning method on a training dataset of size n and repeating it n times. This issue also applies to the use of LOOCV for k-NN regression. On the other hand, theoretically, LOOCV is known to be better than crossvaalidatinn of smaller number of split-folds
estimator of the generalization error (c.g., Arlot and Celisse 2010 Section 6.2). Azadkia (2019) theoretically analyses LOOCV for k-NN regression in selecting & and discusses its optimality.
This paper describes a fast method for computing LOOCV for k-NN regression. Specifically, we show that, under tic-breaking assumption for nearest neighbours, the LOOCV estimate of the mean-squared error is identical to the mean square error of (k 1)-NN regression evaluated on the training data, multiplied by the scaling factor (k + 1)2/k2 (Corollary in Section 31. Therefore, to perform LOOCV, one only needs to fit

---

Published in Transactions on Machine Learning Research (12/2024)
(ke + 1)-NN regression only once and does not need to repeat the k-NN fit times. To our knowledge, this method has not been reported in the literature.
This paper is organised as follows. We describe k-NN regression and LOOCV in Section 2 We present the fast computation method in Section g empirically confirm its validity in Section 4 discuss the tie-breaking condition in Section and conclude Section i
2
h NN Regression and LOOCV
Suppose given input-output pairs training data:
D, = ((11,8)): -.. (#n: vn)) C X 3/
(1)
where X' and y the input. and output spaces. Specifically, X' is a metric space with distance metric || z'|l is the Euclidean
dx X' x X + [0, oo) (e.g,, X' = _2 is D-dimensional space and dx(xxx)) distance). The output space Y' can be discrete (c.g.. y = {0, 1} in the case of binary classification) or continuous (e.g., y = R for the case of real-valued regression, or y = RM for vector-valued regression with M outputs). Below, we use the following notation for the set of training inputs:
X, = (
(2)
Assuming that there is an unknown function f : X + y such that
y: = f(x)) + Eis i= 1...,.,,
where E.,..., V are independent zero-mean noise random variables, the task to estimate the function ʃ based on the training dataset D,. k-NN regression is a simple, nonparametric method for this purpose, which often performs surprisingly well in practice and has solid theoretical foundations (e.g, Györfi et al.
2002
Kpotufe 2011
Chen et al. 2018
2.1 NNN Regression
Let k E N be fixed. For an arbitrary test input x² E X' k-NN regression predicts its output by first searching for the k-nearest neighbours of x" from X, and then computing the average of the corresponding k training outputs. To be more precise, define the set of indices for nearest neighbours as
NN(x", b. Xn) = ii...., in E .I. (x(x".za) S ... S dx(x", (x)) S dx(x", 2z) for all j E n....,,MMMf...... ... }.
(3)
Then, the N-NN prediction for x² is defined as
(x.)
Σ
yh-
(ENN("", X.,)
In the following, we make the following tie-breaking assumption, which makes NN(x8, k, Xa) uniquely specified for = l,...,n (i.e., the inequalities '5" in 3 with x² ze become '<').
Assumption 1 (Tie-breaking). For all i,j 1,...,n with + j, we have I; # xz and dx( # dx(2z, for all L I.
This tie- brebkiek condition is usually satisfied æı. ...,. Fn are multivariate and sampled from a continuous distribution Section provides a further discussion.
2

---

Published in Transactions on Machine Learning Research (12/2024)
2.2 Leave-One Out Validatni (LOOCV)
LOOCV for k-NN regression is defined as follows. Consider the case y = RM with M E N (M = 1 is the case of standard real-valued regression). For each l = n, consider the training dataset ( with the f-th pair (Ie, removod:
Da DaMe(r ve)) = ((21, (....1))........... ..... (IC-1, (ze+1. Be+1). ...., (Zu, kn3}
Then, the K-NN prediction for any x² based Dn ve) is
Pa. (x))))))))) iENN("", No\(ze)
Σ
Then, the LOOCV score for k-NN regression can be defined as
LOOCV D.) = - ni Σ (
- -
(4)
That is, for each 8= 1,..,,,,, the held-out pair (Ize, (e) is used validation data for the k-NN regression fitted the training data Dz (zze, fe)} of size - 1. Calculating the LOOCV score for large is computationally expensive since one needs to fit k-NN regression times if naively implemented. Next, we will show how this computation can be done efficiently by fitting (A + 1)-NN regression only once.
3
Fast Computation of LOOCV for '-NN Regression
To compute the LOOCV score we need to compute, for each l I,...,
(LD.A((rrwO)) iENN(EE R. XxMa()
E
yb.
(5)
To this end, we need to obtain NN(xe, k Xa Xa\a))), the indices for the h nearest neighbours of ae in X, M
The key insight is the following simple fact: The union of {at} and the k nearest neighbours of xe in X \ {art is identical to the + 1 neurest neighbours of me in Xn- That is, under Assumption D we have
NN(0L, X,Max) U [xx] NN(x,, 1 ++1, Xx).
(6)
See Figure I for an illustration of the case ko = 3. The reasoning is as follows. The first nearest neighbour of we in Nn is, of course, de E X,, The second nearest neighbour of me in Xn is the first nearest neighbour of we in X,, {æz). Generally, for 1 S m < k the (m + 1)-th nearest neighbour of xe in X₃ is the meth nearest
neighbour of rę in X, (ze). Therefore, the identity 6 holds.
Using G we can rewrite 5 in terms of (k: + 1)-NN regression, as summarized as follows.
Lemma 1. Under Assumption 1 we have, for all lo E N and L 1,..., n,
+
1
k. SA+LLD, (xz) k V/
Proof. Using 6
we have
(
Σ
Σ
Vi To
3t Vt
iENN(ae b N. Mart)
iENN(me, 1+1, X.)
k+ 1
Σ
1
y/
k y/
k k+
iENN(ae, k+1, X.)
l: + fK41, (xx)
3

---

Published in Transactions on Machine Learning Research (12/2024)
X
Figure 1: Illustration of k = 3 nearest neighbours of zz. The blue point represents 2e, the three red points are the & = 3 nearest neighbours of zz in Xn Mzr), the black points are other points in Xn, \ (æz), and the red circle is the sphere of radius equal to the distance between and its third nearest neighbour in X, Maz) (the red point on the circle).
Lemma shows that the leave-one-out k-NN prediction fK. M(m.) (2t) on the held-out input ay can be written k fet,,, (xx) ve, which does not involve the hold-out operation of removing (æt, 31) from Dn: it just requires fitting the (A + 1)-NN regression fx+1,D, on Dr, evaluate it on It, scale it by (k + 1)/k and subtract it by ye/k.
Thus, to compute the LOOCV score (4, one needs to fit the (k 1)-NN regression only once the dataset Dn. The resulting computationally efficient formula for the LOOCV score is given below.
Corollary 1. Under Assumption 1 for the LOOCV score in 4 we have
fot1.DD (1x) - - v012
(w) =
(7)
n
Proof. Using Lemma I
we have
1
LOOCV(K, Da)
yE
n
1 k
De
1
2
k +
(e.1.D. (xx) 21
T.
y1
k
k
The expression shows that the LOOCV score 44 for k-NN regression is simply the residual sum of squares (or mean-square error) of the (A + 1)-NN regression fitted and evaluated on D., multiplied by the scaling lactor (#)1)² This scaling factor becomes large when & is small, penalising overfitting and preventing too small k from being chosen by LOOCV.
4 Experiments
We empirically check the validity of the formula 7 for efficient LOOCV computation H We consider real-valued regression problem where X' = Rd and ) R, using two real datasets from scikit-learm: "Diabetes" and "Wine". We standardized each input feature to have mean zero and unit variance.
The code for reproducing the experiments is available https://github. http:///ggttaaaccccc//coaa/a//nt
4

---

Published in Transactions on Machine Learning Research (12/2024)
LOOCV Scores
Computation Times
6000
LOOCV-Brute LOOCV-Efficient
0.35
LOOCV-Brute
LOOCV-Efficient
5500
0.30
Time in seconds
0.25
5000
Score
0.20
4500
0.15
4000
0.10
0.05
3500
0.00
15
20
100
200
300
400
Number of Neighbors k
Sample Size
Figure 2: Experimental results on the Diabetes dataset. The left figure shows the LOOCV scores (4) computed in the brute-force manner ("LOOCV-Brute") and by using the derived formula (7) for different values of k. The right figure shows the computation times of either approach for different data sizes for fixed k- = 5.
We compare two approaches: one is the brute-force computation of the LOOCV score 4 ("LOOCV-Brute"). and the other the efficient computation based on the derived formula 7 the implementation of scikit-learr with "xd_tree' for computing nearest neighbours.
We use
Figure 2 (Diabetes) and Figure 3 (Wine) show the respective results. On the left of cach figure, show the LOOCV scores computed by the two methods for different values of k the number of nearest neighbours. They exactly coincide; we also have checked this numerically. This result verifies the correctness of the formula 7 On the right, we show the computation time required for either method for different training data sizes n for fixed k 5. While LOOCV-Brute's computation time increases lincarly with the sample size n, L.OCV-Efffiien'ss computation time remains almost. unchanged and negligible compared with LOOCV-Brute 's computation time. This shows the effectiveness of the formula 7 for the fast computation of the LOOCV score.
5 Discussion on the Tie-breaking Condition
Lastly, as caveat, we consider the case where the bre-break condition in Assumption I is not satisfied, We use the same Diabetes and Wine datasets in Section + but only employ input feature in each datasct: "BMI" for the Diabetes and "malic-acid" for the Wine. Since each feature has many duplicates, there are many # with corresponding to the left figures of Figures 2 and 3 LOOCV-Efftcien is no longer exact and overestimates the LL0CV--Bute when is small.
Ij, thus violating the (ie-breaking condition. Figure 4 shows the results
This phenomenon can be understood by considering the case where such that 24 = x; = æy for some + j * l. In this case, the first nearest neighbour of ze in Xn {21, In is Fe, 24 and Wj, since 2x(x),x2) dx (Ire, .x.) (x),,,)))
Suppose there E (I....,
0. Therefore, depending the tie-breaking rule of the nearest neighbour search algorithm, z; and 2y may be selected the first k + 1 2 nearest neighbours of xz in X,; in this case the identity in (G) does not hold.
Phttps://scikie SCPU: 1.1 GHx Quad-Cor Core Intel Core
neighbours htt.:aaww.....aauueeeeeeeeerrrre Kneeighhbourseegressrr... html
Memory: GR 3733 MHz IPDDR4X.

---

Published in Transactions on Machine Learning Research (12/2024)
Computation Times
LOOCV Scores
0.14
LOOCV-Brute
0.0450
LOOCV-Brute
LOOCV-Efficient
LOOCV-Efficien
0.12
0.0425
Time in seconds
0.10
0.0400
0.08
Score
0.0375
0.06
0.0350
0.0325
0.04
0.0300
0.02
0.0275
0.00
20
40
60
80
100
120
140
Number of Neighbors k
Sample Size
Experimental results the Wine dataset. The left. figure shows the LOOCV scores 4 computed in the brute-force manner ("LOOCV-Brute and by using the derived formula 7 for different values of k. The right figure shows the computation times of either approach for different data sizes for fixed k = 5.
Figure 3:
However, as shown in Figure L.OCVVEfffcient overestimates LOOCV-Brute only for small k where the LOOCV scores are large. Therefore, this issue would not severely affect the best k that minimizes the LOOCV score. Indeed, for the Diabetes data, the best selected by LOOCV-Brute. For the Wine data, the best & of L.00CV-Efficient is k 17, while that of LOOCV-Brute is k = 21, which are similar and would not significantly change the prediction performance.
k and identical
The above example suggests that Assumption I is essential for the formula r to be exact. In practice, one could check whether Assumption [ is satisfied by, e.g., checking whether there are no duplicates in the inputs 21...., beforehand; if they exist, one could resolve the duplicates by, c.g., taking the average of the outputs of duplicated samples. However, as demenstrated in the results in Figures P and 3 for the full Diabetes dataset, Assumption would be satisfied for many practical situations where the input features are multivariate and continuous.
6 Conclusions
We showed that LOOCV for k-NN can be computed quickly by fitting (k + 1)-NN regression only once, evaluating the mean-square error on the training data and multiplying it by the scaling factor (k + /12. By applying this technique, many applications of k-NN regression can be accelerated. It also opens up the possibility using LOOCV for optimising not only & but also the distance function dxi this would one important future direction.
Acknowledgements
The author thanks Takafumi Kajihara for discussion, as well as the Action Editor and the anonymous reviewers for their time and comments.
References
Arlot, S. and Celisse, A. (2010). A survey of cross-validation procedures for model selection. Statistics Surveys, 4:40 79.
Azadkia, M. (2019). Optimal choice of & for k-nearest. neighbor regression. or Xíe preprint arXiv: 190l..9990.00

---

Published in Transactions on Machine Learning Research (12/2024)
LOOCV Scores using BMI feature (Diabetes)
LOOCV Scores using malic_ acid feature (Wine)
LOOCV-Brute
LOOCV-Brute LOOCV-Efficien
LOOCV-Efficient
0.9
12000
10000
Score
Score
0.7
8000
0.6
6000
0.5
0.4
4000
10 Number of Neighbors
20
15 Number of Neighbors k
Figure 4: LOOCV scores for the Diabetes datasct (left) and the Wine dataset (right), each of which only uses one impul feature. The used input feature has many duplicates and thus does not satisfy the lie-breaking condition in Assumption I Left: The best & with the lowest LOOCV score is 17 for both LOOCV- -Buute and L.0CV-Efficient. Right: The best l with the lowest LOOCV score 21 for LOOCV-Brute and 17 for LOOCv-Effiient.
Biau, G., Cérou, F., and Guyader, A. (2015). New insights into approximate Bayesian computation. In Annales de l'IHP Probabilités et Statistiques, volume 51, pages 376-403.
Breunig, M. M., Kriegel, H.-P., Ng, R. T., and Sander, (2000). LOF: identilynng density-based local outliers. In Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data, pages 93 104.
Chen, G. H., Shah, D., et al. (2018). Explaining the success of nearest neighbor methods in prediction. Foundations and TrendsS in Machine Learning, 10(3-6))337-588.
Györfi, L., Kohler, M., Kryzak, A., and Walk, H. (2002). A Distribution-Free Theory of Nonporametric Regression. Springer.
Hastie, T., Tibshirani, R., and Friedman, J. (2009). The Elements of Statistical Learning: Dala Minnng, Inference, and Prediction. Springer Science & Business Media.
Tgnatiadis, N., Saha, S., Sun, D. I.., and Muralidharan, O. (2023). Empirical Bayes mean estimation with nonparametric errors via order statistic regression replicated data. Journal of the American Statistical Association, 118(542):9877999
Jiang, H. (2019). Non-asymplotic uniform rates of consistency for k-NN regression. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages
Kpotufe, S. (2011). k-NN regression adapts to local intrinsic dimension. Advances in Neural Information Processing Systems, 24.
Kpotufe, and Martinet, G. (2021). Marginal singularity and the benefits of labels in covariate-shift. The Annals of Statistics, 39999 3323.
Lalande, F. and Doya, K. (2023). Numerical data imputation for multimodal data scts: A probabilistic nearest-neighhor kernel density approach. Transactions on Machine Learning Research.
Lian, H. (2011). Convergence of functional k-nearest neighbor regression estimate with functional responses. Electronic Journal of Statistics, 5:31-40.

---

Published in Transactions on Machine Learning Research (12/2024)
Madrid Padilla, O. H., Sharpnack, J., Chen, Y., and Witten, D. M. (2020). Adaptive nonparametric regres- sion with the k-nearest neighbour fused Lasso. Biometrika, (07(2):29333))) 310.
Matabuena, M., Vidal, J. C., Padilla, O. H. M., and Onnela, J.-P. (2024). kNN algorithm for conditional mean and variance estimation with automated uncertainty quantification and variable selection. arXiv preprint 0026::2402.01635
Runge, J. (2018). Conditional independence testing based on a nearest-neighbor estimator of conditional mutual information. In International Conference on Artificial Intelligence and Statistics, pages 938- 948-947. PMLR.
Stone; C. J. (1977). Consistent nonparametric regression. The Annals of Slatistics, 5(4):595 620.
Stone, M. (1974). Cross-validatory choice and assessment of statistical predictions. Journal of the Royal Statistical Sociely: Series B (Methodologicul), 36(2):111-133;
Troyanskaya, O., Cantor, M., Sherlock, G., Brown, P., Hastie, T., Tibshirani, R., Botstein, D., and Altman, R. B. (2001). Missing value estimation methods for dna microarrays. Bioinformatics, 17(6):520- 525.


Reviews:
[{"review_id": "kh4Xbxccrc", "reviewer": "Reviewer_TJJm", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\nTo my best understanding, this finding of the relation between LOOCV of a $k$-NN regression and the training error of a $k+1$-NN model is novel.\nThe finding is easy to apply and very useful for practitioners to use $k$-NN by selecting $k$ via LOOCV.\n\n## Weaknesses/Questions\nThe $k+1$-NN computation is essentially computing the $k+1$ nearest neighbors for each data point.\nSo one might argue, instead of the need of this relation, above is the efficient way to perform LOOCV.\nGiven this, can we remove the tie-breaking condition?\n- If we have the $k+1$ nearest neighbors for each data point, we can actually compute (4) exactly, as we can always selectively removing the data with index $l$ from the neighbor set, which could be done in O(1) if the neighbors are sorted and indexed (if $l$ is in the index, remove it, otherwise remove the farthest neighbor).\nWith above being said, such algorithm is still based on the main finding of the paper.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes a computationally efficient way to compute LOOCV for a $k$-NN regression model by establishing the relation between LOOCV of a $k$-NN regression and the training error of a $k+1$-NN model, under a mild tie-breaking condition.\nExperiments are performed to validate the relation and the computational benefit.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "N/A", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "jp1Eb5EKGD", "reviewer": "Reviewer_fQbo", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "+ The paper is clearly presented. \n + The results appear new. \n\n\n- Currently there are only one experiment.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a fast way to compute the LOOCV for k-NN. \nUnder an assumption for tie-breaking, it is shown that there is \nsimple relationship between the LOOCV score for k-NN and (k+1)-NN.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I would suggest that more experiments be performed.\n\nafter more validation is provided, the paper can be published.", "broader_impact_concerns": "n/a", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "E4PSuB81Rw", "reviewer": "Reviewer_2heP", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The paper proposes a rapid computational approach for LOOCV in k-nearest neighbors (k-NN) regression, addressing a practical concern in the field.\n\n2. The incorporation of a tie-breaking condition for nearest neighbors allows for a clear correlation between LOOCV estimate and mean square error in (k + 1)-NN regression, providing a novel insight.\n\nWeaknesses:\n\n1. The paper does not discuss potential limitations or drawbacks of the proposed method.\n\n2. It is unclear whether the tie-breaking condition for nearest neighbors may introduce biases or affect the accuracy of the results.\n\n3. The experimental results, while confirming the efficacy of the method, may not provide a comprehensive evaluation across various datasets or scenarios.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The study presents a quick way to calculate leave-one-out cross-validation (LOOCV) in k-nearest neighbors (k-NN) regression. By adding a tie-breaking rule for nearest neighbors, the LOOCV error estimation in k-NN regression matches that of (k + 1)-NN regression, adjusted by a scaling factor of $(k + 1)^2/k^2$. This method allows for efficient LOOCV score computation by training (k + 1)-NN regression once, eliminating the need for repetitive k-NN training-validation loops. Experimental findings validate the effectiveness of this streamlined approach.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Additional elaboration is needed regarding the tie-breaking condition. It would be beneficial to explore whether this condition can be relaxed without compromising the algorithm's effectiveness. This inquiry could shed light on the robustness and flexibility of the approach.\n\n\n2. The simulation section should explore the implications of not meeting the tie-breaking condition to enhance the versatility of the proposed technique. Furthermore, including additional numerical experiments on real datasets would strengthen the demonstration of the method's efficacy.", "broader_impact_concerns": "No", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: I was skeptical of the novelty when I first saw it, but could not find it in the literature, and this was backed up by the reviewers.  The idea has clear merit, thus I feel it should be accepted.
Decision: Accept (poster)