Theoretical analysis of cross-validation for estimating the risk of the k-nearest neighbor classifier

The present work aims at deriving theoretical guaranties on the behavior of cross-validation procedures applied to the k-nearest neighbors (kNN) in the context of binary classification. Here we focus on the-p-out cross-validation (LpO) used to assess the performance of thekNN classifier. Remarkably this LpO estimator can be efficiently computed this context using closed-form formulas derived by11. We describe a general strategy to derive moment and concentration inequalities for the LpO estimator applied to thekNN classifier. Such results are obtained first by exploiting the connection the LpO estimator and U-statistics, and second by making an intensive of the generalized Efron-Stein inequality applied to the L1O estimator. other important contribution is made by deriving new quantifications of the between the LpO estimator and the classification error/risk of kNN classifier. The optimality of these bounds is discussed by means of lower bounds as well as simulation experiments.