Journal of Machine Learning Research 1 (2000) 1-48

Submitted 4/00; Published 10/00

arXiv:1508.04905v2 [] 12 Oct 2017

Theoretical analysis of cross-validation for estimating the
risk of the k-Nearest Neighbor classifier
Alain Celisse
Laboratoire de Mathématiques
Modal Project-Team
UMR 8524 CNRS-Université Lille 1
F-59 655 Villeneuve d’Ascq Cedex, France
celisse@math.univ-lille1.fr
Tristan Mary-Huard
INRA, UMR 0320 / UMR 8120 Génétique Végétale et Évolution
Le Moulon, F-91190 Gif-sur-Yvette, France
UMR AgroParisTech INRA MIA 518, Paris, France
16 rue Claude Bernard
F-75 231 Paris cedex 05, France
maryhuar@agroparistech.fr

Editor: TBW

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

1. Introduction
The k-nearest neighbor (kNN) algorithm (Fix and Hodges, 1951) in binary classification is
a popular prediction algorithm based on the idea that the predicted value at a new point is
based on a majority vote from the k nearest labeled neighbors of this point. Although quite
c 2000 A. Celisse and T. Mary-Huard.

Celisse and Mary-Huard

simple, the kNN classifier has been successfully applied to many difficult classification tasks
(Li et al., 2004; Simard et al., 1998; Scheirer and Slaney, 2003). Efficient implementations
have been also developed to allow dealing with large datasets (Indyk and Motwani, 1998;
Andoni and Indyk, 2006).
The theoretical performances of the kNN classifier have been already extensively investigated. In the context of binary classification preliminary theoretical results date back to
Cover and Hart (1967); Cover (1968); Györfi (1981). More recently, Psaltis et al. (1994);
Kulkarni and Posner (1995) derived an asymptotic equivalent to the performance of the
1NN classification rule, further extended to kNN by Snapp and Venkatesh (1998). Hall
et al. (2008) also derived asymptotic expansions of the risk of the kNN classifier assuming either a Poisson or a binomial model for the training points, which relates this risk to
the parameter k. By contrast to the aforementioned results, the work by Chaudhuri and
Dasgupta (2014) focuses on the finite sample framework. They typically provide upper
bounds with high probability on the risk of the kNN classifier where the bounds are not
distribution-free. Alternatively in the regression setting, Kulkarni and Posner (1995) provide a finite-sample bound on the performance of 1NN that has been further generalized
to the kNN rule (k ≥ 1) by Biau et al. (2010a), where a bagged version of the kNN rule is
also analyzed and then applied to functional data Biau et al. (2010b). We refer interested
readers to Biau and Devroye (2016) for an almost thorough presentation of known results
on the kNN algorithm in various contexts.
In numerous (if not all) practical applications, computing the cross-validation (CV)
estimator (Stone, 1974, 1982) has been among the most popular strategies to evaluate the
performance of the kNN classifier (Devroye et al., 1996, Section 24.3). All CV procedures
share a common principle which consists in splitting a sample of n points into two disjoint
subsets called training and test sets with respective cardinalities n − p and p, for any
1 ≤ p ≤ n−1. The n−p training set data serve to compute a classifier, while its performance
is evaluated from the p left out data of the test set. For a complete and comprehensive review
on cross-validation procedures, we refer the interested reader to Arlot and Celisse (2010).
In the present work, we focus on the leave-p-out (LpO) cross-validation. Among CV
procedures,
it belongs to exhaustive strategies since it considers (and averages over) all the

n
possible
such splittings of {1, . . . , n} into training and test sets. Usually the induced
p
computation time of the LpO is prohibitive, which gives rise to its surrogate called V −fold
cross-validation (V-FCV) with V ≈ n/p (Geisser, 1975). However, Steele (2009); Celisse
and Mary-Huard (2011) recently derived closed-form formulas respectively for the bootstrap
and the LpO procedures applied to the kNN classification rule. Such formulas allow one
to efficiently compute the LpO estimator. Moreover since the V-FCV estimator suffers a
larger variance than the LpO one (Celisse and Robin, 2008; Arlot and Celisse, 2010), LpO
(with p = bn/V c) strictly improves upon V-FCV in the present context.
Although being favored in practice for assessing the risk of the kNN classifier, the use
of CV comes with very few theoretical guarantees regarding its performance. Moreover
probably for technical reasons, most existing results apply to Hold-out and leave-one-out
(L1O), that is LpO with p = 1 (Kearns and Ron, 1999). In this paper we rather consider
the general LpO procedure (for 1 ≤ p ≤ n − 1) used to estimate the risk (alternatively
the classification error rate) of the kNN classifier. Our main purpose is then to provide
2

Performance of CV to estimate the risk of kNN

distribution-free theoretical guarantees on the behavior of LpO with respect to influential
parameters such as p, n, and k. For instance we aim at answering questions such as: “Does
it exist any regime of p = p(n) (with p(n) some function of n) where the LpO estimator is
a consistent estimate of the risk of the kNN classifier?”, or “Is it possible to describe the
convergence rate of the LpO estimator with respect to p/n?”
Contributions. The main contribution of the present work is two-fold: (i) we describe
a new general strategy to derive moment and exponential concentration inequalities for
the LpO estimator applied to the kNN binary classifier, and (ii) these inequalities serve to
derive the convergence rate of the LpO estimator towards the risk of the kNN classifier.
This new strategy relies on several steps. First exploiting the connection between the
LpO estimator and U-statistics (Koroljuk and Borovskich, 1994) and the Rosenthal inequality (Ibragimov and Sharakhmetov, 2002), we prove that upper bounding the polynomial
moments of the centered LpO estimator reduces to deriving such bounds for the simpler
L1O estimator. Second, we derive new upper bounds on the moments of the L1O estimator
using the generalized Efron-Stein inequality (Boucheron et al., 2005, 2013, Theorem 15.5).
Third, combining the two previous steps provides some insight on the interplay between p/n
and k in the concentration rates measured in terms of moments. This finally results in new
exponential concentration inequalities for the LpO estimator applying whatever the value of
the ratio p/n ∈ (0, 1). In particular while the upper bounds increase with 1 ≤ p ≤ n/2 + 1,
it is no longer the case if p > n/2 + 1. We also provide several lower bounds suggesting our
upper bounds cannot be improved in some sense in a distribution-free setting.
The remainder of the paper is organized as follows. The connection between the LpO
estimator and U -statistics is clarified in Section 2, where we also recall the closed-form
formula of the LpO estimator (Celisse and Mary-Huard, 2011) applied to the kNN classifier.
Order-q moments (q ≥ 2) of the LpO estimator are then upper bounded in terms of those
of the L1O estimator. This step can be applied to any classification algorithm. Section 3
then specifies the previous upper bounds in the case of the kNN classifier, which leads to
the main Theorem 3.2 characterizing the concentration behavior of the LpO estimator with
respect to p, n, and k in terms of polynomial moments. Deriving exponential concentration
inequalities for the LpO estimator is the main concern of Section 4 where we highlight the
strength of our strategy by comparing our main inequalities with concentration inequalities
derived with less sophisticated tools. Finally Section 5 exploits the previous results to
bound the gap between the LpO estimator and the classification error of the kNN classifier.
The optimality of these upper bounds is first proved in our distribution-free framework by
establishing several new lower bounds matching the upper ones in some specific settings.
Second, empirical experiments are also reported which support the above conclusions.

2. U -statistics and LpO estimator
2.1 Statistical framework
Classification We tackle the binary classification problem where the goal is to predict
the unknown label Y ∈ {0, 1} of an observation X ∈ X ⊂ Rd . The random variable
(X, Y ) has an unknown joint distribution P(X,Y ) defined by P(X,Y ) (B) = P [ (X, Y ) ∈ B ]
for any Borelian set B ∈ X × {0, 1}, where P denotes a probability distribution. In what
3

Celisse and Mary-Huard

follows no particular distributional assumption is made regarding X. To predict the label,
one aims at building a classifier fˆ : X → {0, 1} on the basis of a set of random variables
Dn = {Z1 , . . . , Zn } called the training sample, where Zi = (Xi , Yi ), 1 ≤ i ≤ n represent
n copies of (X, Y ) drawn independently from P(X,Y ) . In settings where no confusion is
possible, we will replace Dn by D.
Any strategy to build such a classifier is called a classification algorithm or classification
rule, and can be formally defined as a function A : ∪n≥1 {X × {0, 1}}n → F that maps
a training sample Dn onto the corresponding classifier ADn (·) = fˆ ∈ F, where F is the
set of all measurable functions from X to {0, 1}. Numerous classification rules have been
considered in the literature and it is out of the scope of the present paper to review all
of them (see Devroye et al. (1996) for many instances). Here we focus on the k-nearest
neighbor rule (kNN) initially proposed by Fix and Hodges (1951) and further studied for
instance by Devroye and Wagner (1977); Rogers and Wagner (1978).
The kNN algorithm For 1 ≤ k ≤ n, the kNN rule, denoted by Ak , consists in classifying
any new observation x using a majority vote decision rule based on the label of the k points
X(1) (x), . . . , X(k) (x) closest to x among the training sample X1 , . . . , Xn . In what follows
these k nearest neighbors are chosen according to the distance associated with the usual
Euclidean norm in Rd . Note that other adaptive metrics have been also considered in the
literature (see for instance Hastie et al., 2001, Chap. 14 ). But such examples are out of the
scope of the present work that is, our reference distance does not depend on the training
sample at hand. Let us also emphasize that possible ties are broken by using the smallest
index among ties, which is one possible choice for the Stone lemma to hold true (Biau and
Devroye, 2016, Lemma 10.6,p.125).

Formally, given Vk (x) = 1 ≤ i ≤ n, Xi ∈ X(1) (x), . . . , X(k) (x)
the set of indices of
the k nearest neighbors of x among X1 , . . . , Xn , the kNN classification rule is defined by

P
P

1
, if k1 i∈Vk (x) Yi = k1 ki=1 Y(i) (x) > 0.5

P
Ak (Dn ; x) = fbk (Dn ; x) :=
, (2.1)
0
, if k1 ki=1 Y(i) (x) < 0.5

 B(0.5) , otherwise
where Y(i) (x) is the label of the i-th nearest neighbor of x for 1 ≤ i ≤ k, and B(0.5) denotes
a Bernoulli random variable with parameter 1/2.
Leave-p-out cross-validation For a given sample Dn , the performance of any classifier
fˆ = ADn (·) (respectively of any classification algorithm Å) is assessed by the classification
error L(fˆ) (respectively the risk R(fˆ)) defined by


h 
i
L(fˆ) = P fˆ(X) 6= Y | Dn , and
R(fˆ) = E P fˆ(X) 6= Y | Dn .
In this paper we focus on the estimation of L(fˆ) (and its expectation R(fˆ)) by use of the
Leave-p-Out (LpO) cross-validation for 1 ≤ p ≤ n − 1 (Zhang, 1993; Celisse and Robin,
2008). LpO successively considers all possible splits of Dn into a training set of cardinality
n − p and a test set of cardinality p. Denoting by En−p the set of all possible subsets of
{1, . . . , n} with cardinality n − p, any e ∈ En−p defines a split of Dn into a training sample
De = {Zi | i ∈ e} and a test sample Dē , where ē = {1, . . . , n} \ e. For a given classification
4

Performance of CV to estimate the risk of kNN

algorithm A, the final LpO estimator of the performance of ADn (·) = fb is the average (over
all possible splits) of the classification error estimated on each test set, that is
!
 −1 X
X
n
1
bp (A, Dn ) =
R
1{ADe (Xi )6=Yi } ,
(2.2)
p
p
i∈ē

e∈En−p

e

where AD (·) is the classifier built from De . We refer the reader to Arlot and Celisse (2010)
for a detailed description of LpO and other cross-validation procedures. In the sequel, the
bp (A, Dn ) is replaced by R
bp,n in settings where no confusion can arise
lengthy notation R
bp (Dn ) if the training sample
about the algorithm A or the training sample Dn , and by R
has to be kept in mind.
Exact LpO for the kNN classification algorithm Usually due to its seemingly prohibitive computational cost, LpO is not applied except with p = 1 where it reduces to the
well known leave-one-out. However unlike this widespread idea Celisse and Robin (2008);
Celisse (2008, 2014) proved that the LpO estimator can be efficiently computed by deriving closed-form formulas in several statistical frameworks. The kNN classification rule is
another instance for which efficiently computing the LpO estimator is possible with a time
complexity linear in p as previously established by Celisse and Mary-Huard (2011). Let us
briefly recall the main steps leading to the closed-form formula.
1. From Eq. (2.2) the LpO estimator can be expressed as a sum (over the n observations
of the complete sample) of probabilities:


!
 −1 X
 −1 X
n
X
X
n
1
1
 n

=
1{ADe (Xi )6=Yi }
1{ADe (Xi )6=Yi } 1{i∈e}
/
p
p
p
p
e∈En−p

i=1

i∈e
/

=

1
p

n
X

e∈En−p

e

Pe (AD (Xi ) 6= Yi | i ∈
/ e)Pe (i ∈
/ e).

i=1

Here Pe means that the integration is computed with respect to the random variable
e ∈ En−p , which follows the uniform distribution over the np possible subsets with
cardinality n−p in En−p . For instance Pe (i ∈
/ e) = p/n since it is the proportion of subsamples with
cardinality
n
−
p
which
do
not
contain a given prescribed index i, which
 n
n−1
equals n−p
/ p . (See also Lemma D.4 for further examples of such calculations.)
2. For any Xi , let X(1) , ..., X(k+p−1) , X(k+p) , ..., X(n−1) be the ordered sequence of neighbors of Xi . This list depends on Xi , i.e. X(1) should be noted X(i,1) , but this dependency is skipped here for the sake of readability.
The key in the derivation is to condition with respect to the random variable Rki which
denotes the rank (in the whole sample Dn ) of the k−th neighbor of Xi in the De , that
is Rki = j means that X(j) is the k-th neighbor of Xi in De . Then
De

Pe (A

(Xi ) 6= Yi |i ∈
/ e) =

k+p−1
X

e

Pe (AD (Xi ) 6= Yi | Rki = j, i ∈
/ e)Pe (Rki = j | i ∈
/ e),

j=k

5

Celisse and Mary-Huard

where the sum involves p terms since only X(k) , . . . , X(k+p−1) are candidates for being
the k-th neighbor of Xi in at least one training subset e.
3. Observe that the resulting probabilities can be easily computed (see Lemma D.4):
? Pe (i ∈
/ e) = np
? Pe (Rki = j|i ∈
/ e) = kj P (U = j − k)

e
? Pe (AD (Xi ) 6= Yi |Vki = j, i ∈
/ e) = (1 − Yj ) 1 − FH

k+1
2




+ Yj 1 − F H 0

k−1
2



,

with U ∼ H(j, n − j − 1, p − 1), H ∼ H(Nij , j − Nij − 1, k − 1), and H 0 ∼ H(Nij − 1, j −
Nij , k − 1), where H denotes the hypergeometric distribution and Nij is the number
of 1’s among the j nearest neighbors of Xi in Dn .
The computational cost of LpO for the kNN classifier is the same as that of L1O for the
(k + p − 1)NN classifier whatever p, that is O(p n). This contrasts with the usual np
prohibitive computational complexity seemingly suffered by LpO.
2.2 U -statistics: General bounds on LpO moments
The purpose of the present section is to describe a general strategy allowing to derive
new upper bounds on the polynomial moments of the LpO estimator. As a first step of
this strategy, we establish the connection between the LpO risk estimator and U-statistics.
Second, we exploit this connection to derive new upper bounds on the order-q moments of
the LpO estimator for q ≥ 2. Note that these upper bounds, which relate moments of the
LpO estimator to those of the L1O estimator, hold true with any classifier.
Let us start by introducing U -statistics and recalling some of their basic properties that
will serve our purposes. For a thorough presentation, we refer to the books by Serfling
(1980); Koroljuk and Borovskich (1994). The first step is the definition of a U -statistic of
order m ∈ N∗ as an average over all m-tuples of distinct indices in {1, . . . , n}.
Definition 2.1 (Koroljuk and Borovskich (1994)). Let h : X m −→ R (or Rk ) denote
any Borelian function where m ≥ 1 is an integer. Let us further assume h is a symmetric
function of its arguments. Then any function Un : X n −→ R such that
 −1
X
n
Un (x1 , . . . , xn ) = Un (h)(x1 , . . . , xn ) =
h (xi1 , . . . , xim )
m
1≤i1 <...<im ≤n

where m ≤ n, is a U -statistic of order m and kernel h.
Before clarifying the connection between LpO and U -statistics, let us introduce the main
property of U -statistics our strategy relies on. It consists in representing any U-statistic as
an average, over all permutations, of sums of independent variables.
Proposition 2.1 (Eq. (5.5) in Hoeffding (1963)). With the notation of Definition 2.1, let
us define W : X n −→ R by
r

W (x1 , . . . , xn ) =


1X
h x(j−1)m+1 , . . . , xjm ,
r
j=1

6

(2.3)

Performance of CV to estimate the risk of kNN

where r = bn/mc denotes the integer part of n/m. Then
Un (x1 , . . . , xn ) =
where

P

σ


1 X
W xσ(1) , . . . , xσ(n) ,
n! σ

denotes the summation over all permutations σ of {1, . . . , n}.

We are now in position to state the key remark of the paper. All the developments
further exposed in the following result from this connection between the LpO estimator
defined by Eq. (2.2) and U -statistics.
Theorem 2.1. For any classification rule A and any 1 ≤ p ≤ n − 1 such that the following
bp,n is a U-statistic of order m = n − p + 1
quantities are well defined, the LpO estimator R
m
with kernel hm : X −→ R defined by
m

hm (Z1 , . . . , Zm ) =

1 X 
,
1 D(i)
m
A m (Xi )6=Yi
i=1

(i)

where Dm denotes the sample Dm = (Z1 , . . . , Zm ) with Zi withdrawn.
Proof of Theorem 2.1.
From Eq. (2.2), the LpO estimator of the performance of any classification algorithm A
computed from Dn satisfies
X 1X
bp (A, Dn ) = R
bp,n = 1
1{ADe (Xi )6=Yi }
R
n
p
p e∈En−p
i∈ē


X
X
X
1
1

= n
1{v=e∪{i}}  1{ADe (Xi )6=Yi } ,
p
p
e∈En−p

i∈ē

v∈En−p+1

since there is a unique set of indices v with cardinality n − p + 1 such that v = e ∪ {i}. Then


n
X 1X
X
1
bp,n = 

1{v=e∪{i}} 1{i∈ē}  1nADv\{i} (X )6=Y o .
R
n
i
i
p
p
i=1

v∈En−p+1

e∈En−p

P

Furthermore for v and i fixed, e∈En−p 1{v=e∪{i}} 1{i∈ē} = 1{i∈v} since there is a unique set
of indices e such that e = v \ i. One gets
bp,n = 1 1
R
p np
=

by noticing p

n
p



=

pn!
p!n−p!

X

n
X

i

v∈En−p+1 i=1

1

X

n
n−p+1



=

1{i∈v} 1nADv\{i} (X )6=Y o

v∈En−p+1

n!
p−1!n−p!

i

X
1
1nADv\{i} (X )6=Y o ,
i
i
n−p+1
i∈v

= (n − p + 1)

7

n
n−p+1



.

Celisse and Mary-Huard

The kernel hm is a deterministic and symmetric function of its arguments that does only
depend on m. Let us also notice that hm (Z1 , . . . , Zm ) reduces to the L1O estimator of the
risk of the classification rule A computed from Z1 , . . . , Zm , that is
b1 (A, Dm ) = R
b1,n−p+1 .
hm (Z1 , . . . , Zm ) = R
(2.4)
In the context of testing whether two binary classifiers have different error rates, this fact
has already been pointed out by Fuchs et al. (2013).
We now derive a general upper bound on the q-th moment (q ≥ 1) of the LpO estimator that holds true for any classification rule as long as the following quantities remain
meaningful.
Theorem 2.2. For any classification rule A, let ADn (·) and ADm (·) be the corresponding
classifiers built from respectively Dn and Dm , where m = n − p + 1. Then for every 1 ≤ p ≤
n − 1 such that the following quantities are well defined, and any q ≥ 1,
h
h
i qi
h
h
i qi
bp,n − E R
bp,n
b1,m − E R
b1,m
E R
≤E R
.
(2.5)
Furthermore as long as p > n/2 + 1, one also gets
• for q = 2


E

h
bp,n − E R
bp,n
R

i 2

E
≤

h
i 2
b1,m − E R
b1,m
R
n
·

(2.6)

m

• for every q > 2
h
h
i qi
bp,n − E R
bp,n
E R
≤ B(q, γ)×

h
i


b1,m − E R
b1,m

jnk
R
n
E
max 2q γ

m

m

q


 q 
 v
u

b1,m
u 2Var R

t


,
n
 ,


m

(2.7)

where γ > 0 is a numeric constant and B(q, γ) denotes the optimal constant defined
in the Rosenthal inequality (Proposition D.2).
The proof is given in Appendix A.1. Eq. (2.5) and Eq. (2.6) straightforwardly result
from the Jensen inequality applied to the average over all permutations provided in Proposition 2.1. If p > n/2+1, the integer part bn/mc becomes larger than 1 and Eq. (2.6) becomes
better than Eq. (2.5) for q = 2. As a consequence of our strategy of proof, the right-hand
side of Eq. (2.6) is equal to the classical upper bound on the variance of U-statistics which
suggests it cannot be improved without adding further assumptions.
Unlike the above ones, Eq. (2.7)
Pr is derived from the Rosenthal inequality, which enables us to upper bound a sum k i=1 ξi kq of independent and identically centered random
P
P
variables in terms of ri=1 kξi kq and ri=1 Var(ξi ). Let us remark that, for q = 2, both
terms of the right-hand side of Eq. (2.7) are of the same order as Eq. (2.6) up to constants.
Furthermore using the Rosenthal inequality allows us to take advantage of the integer part
bn/mc when p > n/2 + 1, unlike what we get by using Eq.(2.5) for q > 2. In particular
it provides a new understanding of the behavior of the LpO estimator when p/n → 1 as
highlighted later by Proposition 4.2.
8

Performance of CV to estimate the risk of kNN

3. New bounds on LpO moments for the kNN classifier
Our goal is now to specify the general upper bounds provided by Theorem 2.2 in the case
of the kNN classification rule Ak (1 ≤ k ≤ n) introduced by (2.1).
Since Theorem 2.2 expresses the moments of the LpO estimator in terms of those of the
L1O estimator computed from Dm (with m = n − p + 1), the next step consists in focusing
on the L1O moments. Deriving upper bounds on the moments of the L1O is achieved
using a generalization of the well-known Efron-Stein inequality (see Theorem D.1 for EfronStein’s inequality and Theorem 15.5 in Boucheron et al. (2013) for its generalization). For
the sake of completeness, we first recall a corollary of this generalization that is proved in
Section D.1.4 (see Corollary D.1).
Proposition 3.1. Let Z1 , . . . , Zn denote n independent random variables and ζ =
f (Z1 , . . . , Zn ), where f : Rn → R is any Borelian function. With Z10 , . . . , Zn0 independent copies of the Zi s, there exists a universal constant κ ≤ 1.271 such that for any q ≥ 2,
v
u X
p
u n
kζ − Eζkq ≤ 2κq t
(f (Z1 , . . . , Zn ) − f (Z1 , . . . , Zi0 , . . . , Zn ))2
.
i=1

q/2

b1 (Ak , Dm ) = R
b1,m (L1O estimator computed
Then applying Proposition 3.1 with ζ = R
from Dm with m = n − p + 1) leads to the following Theorem 3.1, which finally allows us
to control the order-q moments of the L1O estimator applied to the kNN classifier.
m
(m = n − p + 1) denote the kNN classifier
Theorem 3.1. For every 1 ≤ k ≤ n − 1, let AD
k
b
learnt from Dm and R1,m be the corresponding L1O estimator given by Eq. (2.2). Then

• for q = 2,

E

h
i2 
k 3/2
b1,m − E R
b1,m
R
≤ C1
;
m

(3.1)

• for every q > 2,
h
E

h
i qi
b1,m − E R
b1,m
R
≤ (C2 · k)q

q q/2
,
m

(3.2)

√
with C1 = 2 + 16γd and C2 = 4γd 2κ, where γd is a constant (arising from Stone’s lemma,
see Lemma D.5) that grows exponentially with dimension d, and κ is defined in Proposition 3.1.
Its proof (detailed in Section A.2) involves the use of Stone’s lemma (Lemma D.5),
(i)
which upper bounds, for a given Xi , the number of points in Dn having Xi among their
k nearest neighbors by kγd . The dependence of our upper bounds with respect to γd (see
explicit constants C1 and C2 ) induces their strong deterioration as the dimension d grows
since γd ≈ 4.8d − 1. Therefore the larger the dimension d, the larger the required sample
size n for the upper bound to be small (at least smaller than 1). Note also that the tie
breaking strategy (based on the smallest index) is chosen so that it ensures Stone’s lemma
to hold true.
9

Celisse and Mary-Huard

In Eq. (3.1), the easier case q = 2 enables to exploit exact
h calculations
i
 (rather
 than
Dn−p
b
upper bounds) of the variance of the L1O. Further noticing E R1,m = R Ak
(risk of
the kNN classifier learnt from Dn−p ), the resulting k 3/2 /m rate is a strict improvement upon
the usual upper bound in k 2 /m which is derived from using the sub-Gaussian exponential
concentration inequality provided by Theorem 24.4 in Devroye et al. (1996).
By contrast the larger k q in Eq. (3.2) comes from the difficulty to derive a tight upper
P
(i)
 )q , where Dm
bound with q > 2 for the expectation of ( ni=1 1 D(i)
(resp.
(i,j)
D
Ak m (Xi )6=Ak m

(i,j)
Dm )

(Xi )

denotes the sample Dm where Zi has been (resp. Zi and Zj have been) removed.

We are now in position to state the main result of this section. It follows from the
combination of Theorem 2.2 (connecting moments of the LpO estimator to those of the
L1O) and Theorem 3.1 (providing an upper bound on the order-q moments of the L1O).
bp,n denote the LpO risk estimator
Theorem 3.2. For every p, k ≥ 1 such that p+k ≤ n, let R
Dn
(see (2.2)) of the kNN classifier Ak (·) defined by (2.1). Then there exist (known) constants
C1 , C2 > 0 such that for every 1 ≤ p ≤ n − k,
• for q = 2,

E

h

bp,n − E R
bp,n
R

i2 

≤ C1

k 3/2
;
(n − p + 1)

(3.3)

• for every q > 2,
h
E

h
i qi

q/2
q
bp,n − E R
bp,n
R
≤ (C2 k)q n−p+1
,

(3.4)

√
√ d and C2 = 4γd 2κ, where γd denotes the constant arising from Stone’s
with C1 = 128κγ
2π
lemma (Lemma D.5). Furthermore in the particular setting where n/2 + 1 < p ≤ n − k,
then
• for q = 2,

E

h
i2 
b
b
Rp,n − E Rp,n
≤ C1

k 3/2
j
k ,
n
(n − p + 1) n−p+1

(3.5)

• for every q > 2,
h
i qi
bp,n − E R
bp,n
R



n
k2
k 3/2

j
k q,
≤
Γq max 
j
n
n−p+1
(n − p + 1) n−p+1
(n − p + 1)
h

E

√

√
where Γ = 2 2e max 2C1 , 2C2 .
10

q/2
n
n−p+1

3
,
k2 q  (3.6)

Performance of CV to estimate the risk of kNN

The straightforward proof is detailed in Section A.3. Let us start by noticing that both
upper bounds in Eq. (3.3) and (3.4) deteriorate as p grows. This is no longer the case for
Eq. (3.5) and (3.6), which are specifically designed to cover the setup where p > n/2 + 1,
that is where bn/mc is no longer equal to 1. Therefore unlike Eq. (3.3) and (3.4), these last
two inequalities are particularly relevant in the setup where p/n → 1, as n → +∞, which
has been investigated in different frameworks by Shao (1993); Yang (2006, 2007); Celisse
(2014). Eq. (3.5) and (3.6) lead to respective convergence rates at worse k 3/2 /n (for q = 2)
and k q /nq−1 (for q > 2). In particular this last rate becomes approximately equal to (k/n)q
as q gets large.
One can also emphasize that, as a U-statistic of fixed order m = n − p + 1, the LpO
estimator has a known Gaussian limiting distribution, that is (see Theorem A, Section 5.5.1
Serfling, 1980)
√ 
h
i

n b
L
bp,n
Rp,n − E R
−−−−−→ N 0, σ12 ,
n→+∞
m
where σ12 = Var [ g(Z1 ) ], with g(z) = E [ hm (z, Z2 , . . . , Zm ) ]. Therefore the upper bound
given by Eq. (3.5) is non-improvable in some sense with respect to the interplay between n
and p since one recovers the right magnitude for the variance term as long as m = n − p + 1
is assumed to be constant.
Finally Eq. (3.6) has been derived using a specific version of the Rosenthal inequality
(Ibragimov and Sharakhmetov, 2002) stated with the optimal constant and involving a
“balancing factor”. In particular this balancing factor has allowed us to optimize the relative
weight of the two terms between brackets in Eq. (3.6). This leads us to claim that the
dependence of the upper bound with respect to q cannot be improved with this line of
proof. However we cannot conclude that the term in q 3 cannot be improved using other
technical arguments.

4. Exponential concentration inequalities
This section provides exponential concentration inequalities for the LpO estimator applied
to the kNN classifier. Our main results heavily rely on the moments inequalities previously
derived in Section 3, that is Theorem 3.2. In order to emphasize the gain allowed by this
strategy of proof, we start this section by successively proving two exponential inequalities
obtained with less sophisticated tools. We then discuss the strength and weakness of each
of them to justify the additional refinements we introduce step by step along the section.
bp (Ak , Dn ) = R
bp,n can be derived by
A first exponential concentration inequality for R
use of the bounded difference inequality following the line of proof of Devroye et al. (1996,
Theorem 24.4) originally developed for the L1O estimator.
bp,n denote the LpO
Proposition 4.1. For any integers p, k ≥ 1 such that p + k ≤ n, let R
Dn
estimator (2.2) of the classification error of the kNN classifier Ak (·) defined by (2.1).
Then for every t > 0,

P

t2



−n
8(k+p−1)2 γ 2
b
b
d .
Rp,n − E Rp,n > t ≤ 2e

where γd denotes the constant introduced in Stone’s lemma (Lemma D.5).
11

(4.1)

Celisse and Mary-Huard

The proof is given in Appendix B.1.
The upper bound of Eq. (4.1) strongly exploits the facts that: (i) for Xj to be one of
the k nearest neighbors of Xi in at least one subsample X e , it requires Xj to be one of the
k + p − 1 nearest neighbors of Xi in the complete sample, and (ii) the number of points for
which Xj may be one of the k + p − 1 nearest neighbors cannot be larger than (k + p − 1)γd
by Stone’s Lemma (see Lemma D.5).
This reasoning results in a rough upper bound since the denominator in the exponent
exhibits a (k + p − 1)2 factor where k and p play the same role. The reason is that we do not
distinguish between points for which Xj is among or above the k nearest neighbors of Xi in
the whole sample, although these two setups lead to strongly different probabilities of being
among the k nearest neighbors in the training resample. Consequently the dependence
of the convergence rate on k and p in Proposition 4.1 can be improved, as confirmed by
forthcoming Theorems 4.1 and 4.2.
Based on the previous comments, a sharper quantification of the influence of each neighbor among the k + p − 1 ones leads to the next result.
bp,n denote the LpO estimator
Theorem 4.1. For every p, k ≥ 1 such that p + k ≤ n, let R
Dn
(2.2) of the classification error of the kNN classifier Ak (·) defined by (2.1). Then there
exists a numeric constant  > 0 such that for every t > 0,



  


 
bp,n > t , P E R
bp,n − R
bp,n − E R
bp,n > t ≤ exp −n
max P R

t2



h
i ,
p−1
k 2 1 + (k + p) n−1

with  = 1024eκ(1+γd ), where γd is introduced in Lemma D.5 and κ ≤ 1.271 is a universal
constant.
The proof is given in Section B.2.
Let us remark that unlike Proposition 4.1, taking into account the rank of each neighbor
in the whole sample enables to considerably reduce the weight of p (compared to that of
k) in the denominator of the exponent. In particular, one observes that letting p/n → 0 as
n → +∞ (with k assumed to be fixed for instance) makes the influence of the k + p factor
asymptotically negligible. This would allow to recover (up to numeric constants) a similar
upper bound to that of Devroye et al. (1996, Theorem 24.4), achieved with p = 1.
However the upper bound of Theorem 4.1 does not reflect the right dependencies with
respect to k and p compared with what has been proved for polynomial moments in Theorem 3.2. The upper bound seems to strictly deteriorate as p increases, which contrasts with
the upper bounds derived for p > n/2 + 1 in Theorem 3.2. This drawback is overcome by
the following result, which is our main contribution in the present section.
bp,n denote the LpO estimator of
Theorem 4.2. For every p, k ≥ 1 such that p + k ≤ n, let R
D
n
the classification error of the kNN classifier fˆk = Ak (·) defined by (2.1). Then for every
t > 0,


 
h
i
  h
i

t2
b
b
b
b
max P Rp,n − E Rp,n > t , P E Rp,n − Rp,n > t ≤ exp −(n − p + 1) 2 2 ,
∆ k
(4.2)
12

Performance of CV to estimate the risk of kNN

√ 
√
where ∆ = 4 e max C2 , C1 with C1 , C2 > 0 defined in Theorem 3.1.
Furthermore in the particular setting where p > n/2 + 1, it comes


i

i
  h
h
 
n
b
b
b
b
max P Rp,n − E Rp,n > t , P E Rp,n − Rp,n > t ≤ e
×
n−p+1


!1/3 


2



2
2
t
n
1
n
t
,
exp − min (n − p + 1)
,
(n
−
p
+
1)


2e
n − p + 1 4Γ2 k 3/2
n − p + 1 4Γ2 k 2
(4.3)
where Γ arises in Eq. (3.6) and γd denotes the constant introduced in Stone’s lemma
(Lemma D.5).
The proof has been postponed to Appendix B.3. It involves different arguments for
the two inequalities (4.2) and (4.3) depending on the range of values of p. Firstly for
p ≤ n/2 + 1, a simple argument is applied to derive Ineq. (4.2) from the two corresponding
moment inequalities of Theorem 3.2 characterizing the sub-Gaussian behavior of the LpO
estimator in terms of its even moments (see Lemma D.2). Secondly for p > n/2 + 1, we
rather exploit: (i) the appropriate upper bounds on the moments of the LpO estimator
given by Theorem 3.2, and (ii) a dedicated Proposition D.1 which provides exponential
concentration inequalities from general moment upper bounds.
In accordance with the conclusions drawn about Theorem 3.2, the upper bound of
Eq. (4.2) increases as p grows, unlike that of Eq. (4.3) which improves as p increases.
In particular the best concentration rate in Eq. (4.3) is achieved as p/n → 1, whereas
Eq. (4.2) turns out to be useless in that setting. Let us also notice that Eq. (4.2) remains
strictly better than Theorem 4.1 as long as p/n → δ ∈ [0, 1[, as n → +∞. Note also that
the constants Γ and γd are the same as in Theorem 3.1. Therefore the same comments
regarding their dependence with respect to the dimension d apply here.
In order to facilitate the interpretation of the last Ineq. (4.3), we also derive the following
proposition (proved in Appendix B.3) which focuses on the description of each deviation
term in the particular case where p > n/2 + 1.
Proposition 4.2. With the same notation as Theorem 4.2, for any p, k ≥ 1 such that
p + k ≤ n, p > n/2 + 1, and for every t > 0



v
√


u
h
i
2eΓ
k
n
 b
u j k 3/2 k


3/2
b
kt   ≤
P  Rp,n − E Rp,n > √
t + 2e j
e · e−t ,
t
n
n
n−p+1
n−p+1
n−p+1

n−p+1

where Γ > 0 is the constant arising from (3.6).
The present inequality is very similar to the well-known Bernstein inequality (Boucheron
et al., 2013, Theorem 2.10) except the second deviation term of order t3/2 instead of t (for
the Bernstein inequality).
√
With respect to n, the first deviation term is of order ≈ k 3/2 / n, which is the same as
with the Bernstein inequality. The second deviation term is of a somewhat different order,
13

Celisse and Mary-Huard

√
that is ≈ k n − p + 1/n, as compared with the usual 1/n in the Bernstein inequality. Note
that we almost
recover this k/n rate by choosing for instance p ≈ n(1 − log n/n), which
√
√
leads to k log n/n. Therefore varying p allows to interpolate between the k/ n and the
k/n rates.
Note also that the dependence of the first (sub-Gaussian) deviation term with respect to
k is only k 3/2 , which improves upon the usual k 2 resulting from Ineq. (4.2) in Theorem 4.2
for instance. However this k 3/2 remains certainly too large for being optimal even if this
question remains widely open at this stage in the literature.
More generally one strength of our approach is its versatility. Indeed the two above
deviation terms directly result from the two upper bounds on the moments of the L1O
stated in Theorem 3.1. Therefore any improvement of the latter upper bounds would
immediately lead to enhance the present concentration inequality (without changing the
proof).

5. Assessing the gap between LpO and classification error
5.1 Upper bounds
b
First, we derive new upper bounds on different measures of the discrepancy
h
ibetween Rp,n =
bp (Ak , Dn ) and the classification error L(fˆk ) or the risk R(fˆk ) = E L(fˆk ) . These bounds
R
on the LpO estimator are completely new for p > 1, some of them being extensions of former
ones specifically derived for the L1O estimator applied to the kNN classifier.
√
√
bp,n denote the
Theorem 5.1. For every p, k ≥ 1 such that p ≤ k and k + k ≤ n, let R
Dn
ˆ
LpO risk estimator (see (2.2)) of the kNN classifier fk = Ak (·) defined by (2.1). Then,
√
i
4 p k
ˆ
b
E Rp,n − R(fk ) ≤ √
,
2π n
h

(5.1)

and

E

2  128κγ
k 3/2
16 p2 k
d
ˆ
b
·
Rp,n − R(fk )
≤ √
+
2π n − p + 1 2π n2

(5.2)

Moreover,

E

bp,n − L(fˆk )
R

2 

√
√
2 2 (2p + 3) k
1
≤ √
+
·
n
n
π

(5.3)

By contrast with the √
results in the previous sections, a new restriction on p arises in
Theorem 5.1, that is p ≤ k. It is the consequence of using Lemma D.6 in the above proof
to quantify how different two classifiers respectively computed from the same n and n − p
points can be. Indeed this lemma, which provides an upper bound on the L1 stability of the
kNN classifier previously
proved by Devroye and Wagner (1979b), only remains meaningful
√
as long as 1 ≤ p ≤ k.
14

Performance of CV to estimate the risk of kNN

Proof of Theorem 5.1.
e
Proof of (5.1): With fˆke = AD
k , Lemma D.6 immediately provides
h
i
h
i
i
h
bp,n − L(fˆk )
= E L(fˆke ) − E L(fˆk )
E R
h
i
≤ E 1{ADe (X)6=Y } − 1{ADn (X)6=Y }
k
k
√

 e
4 p k
Dn
D
= P Ak (X) 6= Ak (X) ≤ √
·
2π n
Proof of (5.2): The proof combines the previous upper bound with the one established for
the variance of the LpO estimator, that is Eq. (3.3).


i
h
i2
h
i2 
h
i2   h
bp,n − E L(fˆk )
bp,n − E L(fˆk )
bp,n − E R
bp,n
E R
=E R
+ E R
128κγd k 3/2
≤ √
+
2π n − p + 1

√ !2
4 p k
√
,
2π n

which concludes the proof.
The proof of Ineq. (5.3) is more intricate and has been postponed to Appendix C.1.
h
i
bp,n = R(ADn−p ), the right-hand side of Ineq. (5.1) is an
Keeping in mind that E R
k
upper bound on the bias of the LpO estimator, that is on the difference between the risks
of the classifiers built from respectively n − p and n points. Therefore, the fact that this
D
n
upper bound increases with p is reliable since the classifiers Ak n−p+1 (·) and AD
k (·) can
become more and more different from one another
as p increases. More precisely, the
√
upper
√ bound in Ineq. (5.1) goes to 0 provided p k/n does. With the additional restriction
p ≤ k, this reduces to the usual condition k/n → 0 as n → +∞ (see Devroye et al., 1996,
Chap. 6.6 for instance). The monotonicity of this upper upper bound with respect to k can
seem somewhat unexpected. One could think that the two classifiers would become more
and more “similar” to each other as k increases. However it can be proved that, in some
sense, this dependence cannot be improved in the present distribution-free framework (see
Proposition 5.1 and Figure 1).
Note that an upper bound similar to that of Ineq. (5.2) can be easily derived for any
order-q moment (q ≥ 2) at the price of increasing the constants by using (a + b)q ≤
2q−1 (aq + bq ), for every a, b ≥ 0. We also emphasize that Ineq. (5.2) allows us to control the discrepancy between the LpO estimator and the risk of the kNN classifier, that is
the expectation of its classification error. Ideally we would have liked to replace the risk
R(fˆk ) by the prediction error L(fˆk ). But with our strategy of proof, this would require
an additional distribution-free concentration inequality on the prediction error of the kNN
classifier. To the best of our knowledge, such a concentration inequality is not available up
to now.
Upper bounding the squared difference between the LpO estimator and the prediction
error is precisely the purpose of Ineq. (5.3). Proving the latter inequality requires a completely different strategy which can be traced back to an earlier proof by Rogers and Wagner
(1978, see the proof of Theorem 2.1) applying to the L1O estimator. Let us mention that
15

Celisse and Mary-Huard

Ineq. (5.3) combined with the Jensen inequality lead to a less accurate upper bound than
Ineq. (5.1).
Finally the apparent difference between the upper bounds in Ineq. (5.2) and (5.3) results
from the completely different schemes of proof. The first one allows us to derive general
upper bounds for all centered moments of the LpO estimator, but exhibits a worse dependence with respect to k. By contrast the second one is exclusively dedicated to upper
bounding the mean squared
difference between the prediction error and the LpO estimator
√
and leads to a smaller k. However (even if probably not optimal), the upper bound used
in Ineq. (5.2) still enables to achieve minimax rates over some Hölder balls as proved by
Proposition 5.3.
5.2 Lower bounds
5.2.1 Bias of the L1O estimator
The purpose of the next result is to provide a counter-example highlighting that the upper
bound of Eq. (5.1) cannot be improved in some sense. We consider the following discrete
setting where X = {0, 1} with π0 = P [ X = 0 ], and we define η0 = P [ Y = 1 | X = 0 ] and
η1 = P [ Y = 1 | X = 1 ]. In what follows this two-class generative model will be referred to
as the discrete setting DS.
Note that (i) the 3 parameters π0 , η0 and η1 fully describe the joint distribution P(X,Y ) ,
and (ii) the distribution of DS satisfies the strong margin assumption of Massart and
Nédélec (2006) if both η0 and η1 are chosen away from 1/2. However this favourable setting
has no particular effect on the forthcoming lower bound except a few simplifications along
the calculations.
Proposition 5.1. Let us consider the DS setting with π0 = 1/2, η0 = 0 and η1 = 1, and
assume that k is odd. Then there exists a numeric constant C > 1 independent of n and k
Dn−1
n
satisfy
such that, for all n/2 ≤ k ≤ n − 1, the kNN classifiers AD
k and Ak
h

E L



AkDn



−L



D
Ak n−1

i

√
k
≥C
·
n

√
The proof of Proposition 5.1 is provided in Appendix C.2. The rate k/n in the righthand side of Eq. (5.1) is then achieved under the generative model DS for any k ≥ n/2. As
a consequence this rate cannot be improved without any additional assumption, for instance
on the distribution of the Xi s. See also Figure 1 below and related comments.
Empirical illustration To further illustrate the result of Proposition 5.1, we simulated
data according to the DS setting, for different values of n ranging from 100 to 500 and
different values of k ranging from 5 to n − 1.
h 


i
D
n
Figure 1 (a) displays the evolution of the absolute bias E L AD
− L Ak n−1
as
k
a function of k, for several values of n (plain curves). The absolute bias is a nondecreasing
function of k, as suggested by the upper bound provided in Eq. (5.1) which is also plotted
(dashed lines) to ease the comparison. Importantly, the non-decreasing behavior of the
absolute bias is not always restricted to high values of k (w.r.t. n), as illustrated in Figure 1
(b) which corresponds to the same DS setting but with parameter values (π0 , η0 , η1 ) =
16

Performance of CV to estimate the risk of kNN

(0.2, 0.2, 0.9). In particular the non-decreasing behavior now appears for a range of values
of k that are lower than n/2.
Note that a rough idea about the location of the peak, denoted by kpeak , can be deduced
as follows in the simple case where η0 = 0 and η1 = 1.
• For the peak to arise, the two classifiers (based on n and respectively n − 1 observations) have to disagree the most strongly.
• This requires one of the two classifiers – say the first one – to have ties among the k
nearest neighbors of each label in at least one of the two cases X = 0 or X = 1.
• With π0 < 0.5, then ties will most likely occur for the case X = 0. Therefore the
discrepancy between the two classifiers will be the highest at any new observation
x0 = 0.
• For the tie situation to arise at x0 , half of its neighbors have to be 1. This only occurs
if (i) k > n0 (with n0 the number of observations such that X = 0 in the training
set), and (ii) k0 η0 + k1 η1 = k/2, where k0 (resp. k1 ) is the number of neighbors of x0
such that X = 0 (resp. X = 1).
• Since k > n0 , one has k0 = n0 and the last expression boils down to k =

n0 (η1 − η0 )
·
η1 − 1/2

• For large values of n, one should have n0 ≈ nπ0 , that is the peak should appear at
nπ0 (η1 − η0 )
kpeak ≈
·
η1 − 1/2
In the setting of Proposition 5.1, this reasoning remarkably yields kpeak ≈ n, while it
leads to kpeak ≈ 0.4n in the setting of Figure 1 (b), which is close to the location of the
observed peaks. This also suggests that even smaller values of kpeak can arise by tuning the
parameter π0 close to 0. Let us mention that very similar curves have been obtained for
a Gaussian mixture model with two √
disjoint classes (not reported here). On the one hand
this empirically illustrates that the k/n rate is not limited to the discrete setting DS.
On the other hand, all of this confirms that this rate cannot be improved in the present
distribution-free framework.
Let us finally consider Figure 1 (c), which displays the absolute bias as a function of n
where k = bCoef × nc for different values of Coef, where b·c denotes the integer part. With
√
this choice of k, Proposition 5.1 implies that the absolute bias should decrease at a 1/ n
rate, which is supported by the plotted curves. By contrast, panel (d) of Figure 1 illustrates
√
that choosing smaller values of k, that is k = bCoef × nc, leads to a faster decreasing rate.
5.2.2 Mean squared error
Following an example described by Devroye and Wagner (1979a), we now provide a lower
bound on the minimal convergence rate of the mean squared error (see also Devroye et al.,
1996, Chap. 24.4, p.415 for a similar argument).

17

Celisse and Mary-Huard

0.15

0.002

Bias

Bias

0.10

0.001
0.05

0.00

0.000
0

100

200

300

400

500

0

100

200

k
n

100

200

300

400

500

n

100

(a)

400

500

200

300

400

500

(b)

0.020

0.020

0.015

0.015

Bias

Bias

300

k

0.010

0.005

0.010

0.005

0.000

0.000
100

200

300

400

500

100

200

300

n
Coef

1

2

400

500

n
3

4

5

Coef

(c)

1

2

3

4

5

(d)

Figure 1: (a) Evolution of the absolute value of the bias as a function of k, for different
values of n (plain lines). The dashed lines correspond to the upper bound obtained
in (5.1). (b) Same as previous, except that data were generated according to
the DS setting with parameters (π0 , η0 , η1 ) = (0.2, 0.2, 0.9). Upper bounds are
not displayed in order to fit the scale of the absolute bias. (c) Evolution of
the absolute value of the bias with respect to n, when k is chosen such that
k = bCoef × nc (b·c denotes the integer part). The different colors correspond to
different values of Coef. (d) Same as previous, except that k is chosen such that
√
k = bCoef × nc.
18

Performance of CV to estimate the risk of kNN

Proposition 5.2. Let us assume n is even, and that P (Y = 1 | X) = P (Y = 1) = 1/2 is
independent of X. Then for k = n − 1 (k odd), it results

h
i
2  Z 1
1
1
ˆ
b1,n − L(fˆk ) > t dt ≥ √
b
2t · P R
E R1,n − L(fk )
=
·√ ·
8 π
n
0
√
From the upper bound of order k/n (with p = 1) provided by Ineq. (5.3), choosing
√
k = n − 1 leads to the same 1/ n √
rate as that of Proposition 5.2. This suggests that, at
least for very large values of k, the k/n rate is of the right order and cannot be improved
in the distribution-free framework.
5.3 Minimax rates
Let us conclude this section withh a corollary,
which provides a finite-sample bound on the
i
ˆ
ˆ
b
gap between Rp,n and R(fk ) = E L(fk ) with high probability. It is stated under the same
√
restriction on p as the previous Theorem 5.1 it is based on, that is for p ≤ k.
Corollary
√ √ 5.1. With the notation of Theorems 4.2 and 5.1, let us assume p, k ≥ 1 with
p ≤ k, k + k ≤ n, and p ≤ n/2 + 1. Then for every x > 0, there exists an event with
probability at least 1 − 2e−x such that
v
√
u
2 k2
∆
4
p
k
u
bp,n ≤ t 
x + √
,
(5.4)
R(fˆk )) − R
p−1
n
2π
n 1− n
n
where fˆk = AD
k (·).

Proof of Corollary 5.1. Ineq. (5.4) results from combining the exponential concentration
bp,n , namely Ineq. (4.2) (from Theorem 4.2) and the upper bound on the
result derived for R
bias, that is Ineq. (5.1).
h
i
h
i
bp,n + E R
bp,n − R
bp,n ≤ R(fˆk )) − E R
bp,n
R(fˆk )) − R
s
√
4 p k
∆2 k 2
≤√
+
x ·
n−p+1
2π n

Note that the right-hand side of Ineq. (5.4) could be used to derive bounds on R(fˆk ) that
seem similar to confidence bounds. However we do not recommend doing this in practice for
several reasons. On the one hand, Ineq. (5.4) results from the repeated use of concentration
inequalities where numeric constants are not optimized at all, which leads to require a large
sample size n for the deviation terms to be small in practice. On the other hand, explicit
numeric constants such as ∆2 in Corollary 5.1 exhibit a dependence on γd ≈ 4.8d − 1, which
becomes exponentially large as d increases. Proving that this dependence can be weakened
or not remains a completely open question at this stage. Nevertheless one can highlight
that, for a given n, increasing d will quickly make the deviation term larger than 1, whereas
bp,n belong to [0, 1].
both R(fˆk ) and R
19

Celisse and Mary-Huard

√
The right-most term of order k/n in Ineq. (5.4) results from the bias. This is a
necessary price to pay which cannot be improved in the present distribution-free
framework
√
according to Proposition 5.1. Besides combining the restriction p ≤ k with the usual
consistency constraint k/n = o(1) leads to the conclusion that small values of p (w.r.t. n)
have almost no√effect on the convergence rate of the LpO estimator. Weakening the key
restriction p ≤ k would be necessary to potentially nuance this conclusion.
In order to highlight the interest of the above deviation inequality, let us deduce an
optimality result in terms of minimax rate. In the following statement, Corollary 5.1 is
bp,n and the risk R(fˆk )
used to prove that, uniformly with respect to k, the LpO estimator R
of the kNN classifier remain close to each other with high probability.
Proposition 5.3. With the same notation as Corollary 5.1, for every C > 1 and θ > 0,
−(C−1) on which, for any p, k ≥ 1 such
there exists
√ an event
√ of probability at least 1 − 2 · n
that p ≤ k, k + k ≤ n, and p ≤ n/2 + 1, the LpO estimator of the kNN classifier satisfies
√
h
i θ−1 ∆2 C
k 2 log(n)
4 p k
?
ˆ
−√

(1 − θ) R(fk ) − L −
4
2π n
n R(fˆk ) − L?
√
i θ−1 ∆2 C
h
k 2 log(n)
4 p k
?
?
ˆ
b
+√

≤ Rp (Ak , Dn ) − L ≤ (1 + θ) R(fk ) − L +
,
4
2π n
n R(fˆk ) − L?
(5.5)
where L? denotes the classification error of the Bayes classifier.
Furthermore if one assumes the regression function η belongs to a Hölder ball H(τ, α)
2α
for some α ∈]0, d/4[ (recall that Xi ∈ Rd ) and τ > 0, then choosing k = k ? = k0 · n 2α+d
leads to
bp (Ak? , Dn ) − L? ∼n→+∞ R(fˆk? ) − L? .
R

(5.6)

Ineq. (5.5) gives a uniform control (over k) of the gap between the excess risk R(fˆk ) − L?
bp (fˆk ) − L? with high probability. The decreasing
and the corresponding LpO estimator R
rate (in n−(C−1) ) of this probability is directly related to the log(n) factor in the lower
and upper bounds. This decreasing rate could be made faster at the price of increasing
the exponent of the log(n) factor. In a similar way the numeric constant θ has no precise
meaning and can be chosen as close to 0 as we want, leading to increase one of the other
deviation terms by a numeric factor θ−1 . For instance one could choose θ = 1/ log(n), which
would replace the log(n) by a (log n)2 .
The equivalence stated by (5.6) results from knowing that this choice k = k ? makes the
α
kNN classifier achieve the minimax rate n− 2α+d over Hölder balls with smoothness parameter α ∈]0, d/4[ (see Theorems 3.3 and 3.5 in Audibert and Tsybakov, 2007). Therefore it
is not difficult to check that the other deviation terms are negligible with respect to the
excess risk R(fˆk ) − L? for k = k ? .
Proof of Proposition 5.3. Let us define K ≤ n as the maximum value of k and assume
xk = C · log(n) (for some constant C > 1) for any 1 ≤ k ≤ K. Let us also introduce the
20

Performance of CV to estimate the risk of kNN

event
(
bp (Ak , Dn ) ≤
∀1 ≤ k ≤ K, R(fˆk ) − R

Ωn =
Then P [ Ωcn ] ≤

1
nC−1

K
X

−xk

e

k=1

√ )
2
k
4
p
k
.
∆2 xk + √
n
n
2π

r

→ 0, as n → +∞, since a union bound leads to
=

K
X

e−C·log(n) = K · e−C·log(n) ≤ e−(C−1)·log(n) =

k=1

1
·
nC−1

Furthermore
combining
(for a, b > 0) the inequality ab ≤ a2 θ2 + b2 θ−2 /4 for every θ > 0
√
√
√
with a + b ≤ a + b, it results that
r

 θ−1
k2
k2
 xk
∆2 xk ≤ θ R(fˆk ) − L? +
∆2 
n
4
n R(fˆ ) − L?
k





≤ θ R(fˆk ) − L? +

θ−1

k2
 C · log(n),
∆2 
4
n R(fˆk ) − L?

hence Ineq. (5.5).
Let us now choose k = k ? . Then Theorems 3.3 and 3.5 in Audibert and Tsybakov (2007)
combined with Theorem 7 in Chaudhuri and Dasgupta (2014) provide that the minimax
rate of the kNN classifier is


α
R(fˆk? ) − L?  n− 2α+d ,
where a  b means there exist numeric constants l, u > 0 such that l · b ≤ a ≤ u · b.
It is then easy to check that
 d−3α



−1
− 2α+d
Cθ−1 ∆2 k0
k?2
? ,
ˆ
?
• θ 4 ∆2
·
n
log(n)
=
o
R(
f
C
·
log(n)
=
)
−
L
n→=∞
k
4
n(R(fˆk? )−L? )


√
d
?
?
• p nk ≤ kn = k0 · n− 2α+d = on→+∞ R(fˆk? ) − L? .
The desired conclusion (5.6) finally results from choosing θ = 1/(log n).

6. Discussion
The present work provides several new results quantifying the performance of the LpO
estimator applied to the kNN classifier. By exploiting the connexion between LpO and Ustatistics (Section 2), the polynomial and exponential inequalities derived in Sections 3 and 4
give some new insight on the concentration of the LpO estimator around its expectation for
different regimes of p/n. In Section 5, these results serve for instance to conclude to the
consistency of the LpO estimator towards the risk (or the classification error rate) of the
kNN classifier (Theorem 5.1). They also allow us to establish the asymptotic equivalence
between the LpO estimator (shifted by the Bayes risk L? ) and the excess risk over some
Hölder class of regression functions (Proposition 5.3).
21

Celisse and Mary-Huard

It is worth mentioning that the upper-bounds derived in Sections 4 and 5 — see for
instance Theorem 5.1 — can be minimized by choosing p = 1, suggesting that the L1O
estimator is optimal in terms of risk estimation when applied to the kNN classification
algorithm. This observation corroborates the results of the simulation study presented in
Celisse and Mary-Huard (2011), where it is empirically shown that small values of p (and
in particular p = 1) lead to the best estimation of the risk, whatever the value of parameter
k or the level of noise in the data. The suggested optimality of L1O (for risk estimation) is
also consistent with results by Burman (1989) and Celisse (2014), where it is proved that
L1O is asymptotically the best cross-validation procedure to perform risk estimation in the
context of low-dimensional regression and density estimation respectively.
Alternatively, the LpO estimator can also be used as a data-dependent calibration procedure to choose k: the value k̂p leading to the minimum LpO estimate is selected. Although
the focus of the present paper is different, it is worth mentioning that the concentration
results established in Section 4 are a significant early step towards deriving theoretical
guarantees on LpO as a model selection procedure. Indeed, exponential concentration inequalities have been a key ingredient to assess model selection consistency or model selection
efficiency in various contexts (see for instance Celisse (2014) or Arlot and Lerasle (2012)
in the density estimation framework). Still theoretically investigating the behavior of k̂p
requires some further dedicated developments. One first step towards such results is to
derive a tighter upper bound on the bias between the LpO estimator and the risk. The
best known upper bound currently available is derived from Devroye and Wagner (1980,
see Lemma D.6 in the present paper). Unfortunately it does not fully capture the true
behavior of the LpO estimator with
√ respect to p (at least as p becomes large) and could be
improved in particular for p > k as emphasized in the comments following Theorem 5.1.
Another important direction for studying the model selection behavior of the LpO procedure is to prove a concentration inequality for the classification error rate of the kNN
classifier around its expectation. While such concentration results have been established
for the kNN algorithm in the (fixed-design) regression framework (Arlot and Bach, 2009),
deriving similar results in the classification context remains a challenging problem to the
best of our knowledge.

References
A. Andoni and P. Indyk. Near-optimal hashing algorithms for approximate nearest neighbor
in high dimensions. In Foundations of Computer Science, 2006. FOCS’06. 47th Annual
IEEE Symposium on, pages 459–468. IEEE, 2006.
S. Arlot. Resampling and Model Selection. PhD thesis, University Paris-Sud 11, December
2007. URL http://tel.archives-ouvertes.fr/tel-00198803/en/. oai:tel.archivesouvertes.fr:tel-00198803 v1.
S. Arlot and F. Bach. Data-driven calibration of linear estimators with minimal penalties.
Advances in Neural Information Processing Systems (NIPS), 2:46–54, 2009.
S. Arlot and A. Celisse. A survey of cross-validation procedures for model selection. Statistics Surveys, 4:40–79, 2010.
22

Performance of CV to estimate the risk of kNN

S. Arlot and M. Lerasle. Why v= 5 is enough in v-fold cross-validation. arXiv preprint
arXiv:1210.5830, 2012.
J.-Y. Audibert and A. Tsybakov. Fast learning rates for plug-in estimators under the margin
condition. The Annals of Statistics, 35(2), 2007.
G. Biau and L. Devroye. Lectures on the nearest neighbor method. Springer, 2016.
G. Biau, F. Cérou, and A. Guyader. On the rate of convergence of the bagged nearest
neighbor estimate. The Journal of Machine Learning Research, 11:687–712, 2010a.
G. Biau, F. Cérou, and A. Guyader. Rates of convergence of the functional-nearest neighbor
estimate. Information Theory, IEEE Transactions on, 56(4):2034–2040, 2010b.
S. Boucheron, O. Bousquet, G. Lugosi, and P. Massart. Moment inequalities for functions
of independent random variables. Ann. Probab., 33(2):514–560, 2005. ISSN 0091-1798.
S. Boucheron, G. Lugosi, and P. Massart. Concentration Inequalities: A Nonasymptotic
Theory of Independence. Oxford University Press, 2013.
P. Burman. Comparative study of Ordinary Cross-Validation, v-Fold Cross-Validation and
the repeated Learning-Testing Methods. Biometrika, 76(3):503–514, 1989.
A. Celisse.
Model selection via cross-validation in density estimation, regression
and change-points detection. (In English). PhD thesis, University Paris-Sud 11.
http://tel.archives-ouvertes.fr/tel-00346320/en/., December 2008. URL http:
//tel.archives-ouvertes.fr/tel-00346320/en/.
A. Celisse. Optimal cross-validation in density estimation with the l2 -loss. The Annals of
Statistics, 42(5):1879–1910, 2014.
A. Celisse and T. Mary-Huard. Exact cross-validation for knn: applications to passive and
active learning in classification. JSFdS, 152(3), 2011.
A. Celisse and S. Robin. Nonparametric density estimation by exact leave-p-out crossvalidation. Computational Statistics and Data Analysis, 52(5):2350–2368, 2008.
K. Chaudhuri and S. Dasgupta. Rates of convergence for nearest neighbor classification. In
Advances in Neural Information Processing Systems, pages 3437–3445, 2014.
T. M. Cover. Rates of convergence for nearest neighbor procedures. In Proceedings of the
Hawaii International Conference on Systems Sciences, pages 413–415, 1968.
T. M. Cover and P. E. Hart. Nearest neighbor pattern classification. Information Theory,
IEEE Transactions on, 13(1):21–27, 1967.
L. Devroye and T. Wagner. Distribution-free performance bounds for potential function
rules. IEEE Transactions on Information Theory, 25:601–604, 1979a.
L. Devroye, L. Györfi, and G. Lugosi. A Probilistic Theory of Pattern Recognition. Springer
Verlag, 1996.
23

Celisse and Mary-Huard

L. P. Devroye and T. J. Wagner. The strong uniform consistency of nearest neighbor density
estimates. Ann. Statist., 5(3):536–540, 1977. ISSN 0090-5364.
L. P. Devroye and T. J. Wagner. Distribution-free inequalities for the deleted and holdout
error estimates. Information Theory, IEEE Transactions on, 25(2):202–207, 1979b.
L.P. Devroye and T.J. Wagner. Distribution-free consistency results in nonparametric discrimination and regression function estimation. Ann. Statist., 8(2):231–239, 1980.
E. Fix and J. Hodges. Nearest Neighbor (NN) Norms: NN Pattern Classification Techniques,
chapter Discriminatory analysis- nonparametric discrimination: Consistency principles.
IEEE Computer Society Press, Los Alamitos, CA, 1951. Reprint of original work from
1952.
M. Fuchs, R. Hornung, R. De Bin, and A.-L. Boulesteix. A u-statistic estimator for the
variance of resampling-based error estimators. Technical report, arXiv, 2013.
S. Geisser. The predictive sample reuse method with applications. J. Amer. Statist. Assoc.,
70:320–328, 1975.
L. Györfi. The rate of convergence of kn -nn regression estimates and classification rules.
IEEE Trans. Commun, 27(3):362–364, 1981.
P. Hall, B. U. Park, and R. J. Samworth. Choice of neighbor order in nearest-neighbor
classification. The Annals of Statistics, pages 2135–2152, 2008.
T. Hastie, R. Tibshirani, and J. Friedman. The elements of statistical learning. Springer
Series in Statistics. Springer-Verlag, New York, 2001. ISBN 0-387-95284-5. Data mining,
inference, and prediction.
W. Hoeffding. Probability inequalities for sums of bounded random variables. Journ. of the
American Statistical Association, 58(301):13–30, 1963.
R. Ibragimov and S. Sharakhmetov. On extremal problems and best constants in moment
inequalities. Sankhyā: The Indian Journal of Statistics, Series A, pages 42–56, 2002.
P. Indyk and R. Motwani. Approximate nearest neighbors: towards removing the curse
of dimensionality. In Proceedings of the thirtieth annual ACM symposium on Theory of
computing, pages 604–613. ACM, 1998.
M. Kearns and D. Ron. Algorithmic Stability and Sanity-Check Bounds for Leave-One-Out
Cross-Validation. Neural Computation, 11:1427–1453, 1999.
V. S. Koroljuk and Y. V. Borovskich. Theory of U-statistics. Springer, 1994.
S. R. Kulkarni and S. E. Posner. Rates of convergence of nearest neighbor estimation under
arbitrary sampling. Information Theory, IEEE Transactions on, 41(4):1028–1039, 1995.
L. Li, D. M. Umbach, P. Terry, and J. A. Taylor. Application of the ga/knn method to
seldi proteomics data. Bioinformatics, 20(10):1638–1640, 2004.
24

Performance of CV to estimate the risk of kNN

Pascal Massart and Élodie Nédélec. Risk bounds for statistical learning. The Annals of
Statistics, pages 2326–2366, 2006.
D. Psaltis, R. R. Snapp, and S. S. Venkatesh. On the finite sample performance of the
nearest neighbor classifier. Information Theory, IEEE Transactions on, 40(3):820–837,
1994.
W. H. Rogers and T. J. Wagner. A finite sample distribution-free performance bound for
local discrimination rules. Annals of Statistics, 6(3):506–514, 1978.
E. D. Scheirer and M. Slaney. Multi-feature speech/music discrimination system, May 27
2003. US Patent 6,570,991.
R. J. Serfling. Approximation Theorems of Mathematical Statistics. John Wiley & Sons
Inc., 1980.
J. Shao. Linear model selection by cross-validation. J. Amer. Statist. Assoc., 88(422):
486–494, 1993. ISSN 0162-1459.
P. Y. Simard, Y. A. LeCun, J. S. Denker, and B. Victorri. Transformation invariance in
pattern recognition tangent distance and tangent propagation. In Neural networks: tricks
of the trade, pages 239–274. Springer, 1998.
R. R Snapp and S. S. Venkatesh. Asymptotic expansions of the k nearest neighbor risk.
The Annals of Statistics, 26(3):850–878, 1998.
B. M. Steele. Exact bootstrap k-nearest neighbor learners. Machine Learning, 74(3):235–
255, 2009.
C. J. Stone. Optimal global rates of convergence for nonparametric regression. Ann. Statist.,
10(4):1040–1053, 1982. ISSN 0090-5364.
M. Stone. Cross-validatory choice and assessment of statistical predictions. J. Roy. Statist.
Soc. Ser. B, 36:111–147, 1974. ISSN 0035-9246. With discussion by G. A. Barnard, A. C.
Atkinson, L. K. Chan, A. P. Dawid, F. Downton, J. Dickey, A. G. Baker, O. BarndorffNielsen, D. R. Cox, S. Giesser, D. Hinkley, R. R. Hocking, and A. S. Young, and with a
reply by the authors.
Y. Yang. Comparing learning methods for classification. Statist. Sinica, 16(2):635–657,
2006. ISSN 1017-0405.
Y. Yang. Consistency of cross-validation for comparing regression procedures. The Annals
of Statistics, 35(6):2450–2473, 2007.
P. Zhang. Model selection via multifold cross validation. Ann. Statist., 21(1):299–313, 1993.
ISSN 0090-5364.

25

Celisse and Mary-Huard

Appendix A. Proofs of polynomial moment upper bounds
A.1 Proof of Theorem 2.2
The proof relies on Proposition 2.1 that allows to relate the LpO estimator to a sum of
independent random variables. In the following, we distinguish between the two settings
q = 2 (where exact calculations can be carried out), and q > 2 where only upper bounds
can be derived.
When q > 2, our proof deals separately with the cases p ≤ n/2 + 1 and p > n/2 + 1. In
the first one, a straightforward use of Jensen’s inequality leads to the result. In the second
setting, one has to be more cautious when deriving upper bounds. This is done by using
the more sophisticated Rosenthal’s inequality, namely Proposition D.2.
A.1.1 Exploiting Proposition 2.1
According to the proof of Proposition 2.1, it arises that the LpO estimator can be expressed
as a U -statistic since
X

bp,n = 1
R
W Zσ(1) , . . . , Zσ(n) ,
n! σ
with
mc
j n k−1 bX
n

W (Z1 , . . . , Zn ) =

m

hm Z(a−1)m+1 , . . . , Zam



(with m = n − p + 1)

a=1
m

and

hm (Z1 , . . . , Zm ) =

1 X 
 =R
b1,n−p+1 ,
1 D(i)
m
A m (Xi )6=Yi
i=1

(i)

(i)

where ADm (.) denotes the classifier based on sample Dm = (Z1 , . . . , Zi−1 , Zi+1 , . . . , Zm ).
Further centering the LpO estimator, it comes
h
i
X

bp,n − E R
bp,n = 1
R
W̄ Zσ(1) , . . . , Zσ(n) ,
n! σ
where W̄ (Z1 , . . . , Zn ) = W (Z1 , . . . , Zn ) − E [ W (Z1 , . . . , Zn ) ].
Then with h̄m (Z1 , . . . , Zm ) = hm (Z1 , . . . , Zm ) − E [ hm (Z1 , . . . , Zm ) ], one gets
h
h
i qi

q
bp,n − E R
bp,n
E R
≤ E W̄ (Z1 , . . . , Zn )
(Jensen0 s inequality)

q
n
mc
j n k−1 bX
 

h̄m Z(i−1)m+1 , . . . , Zim 
= E
m
i=1

q
n
c
b
m
j n k−q
 
 X
=
E
h̄m Z(i−1)m+1 , . . . , Zim  .
m



i=1

26

(A.1)

Performance of CV to estimate the risk of kNN

A.1.2 The setting q = 2
If q = 2, then by independence it comes


n
bX
mc
i q i j n k−2
h


bp,n
bp,n − E R
≤
Var 
E R
hm Z(i−1)m+1 , . . . , Zim 
m
h

i=1

mc
j n k−2 bX
n

=
=

m

i=1

j n k−1
m



Var hm Z(i−1)m+1 , . . . , Zim



b1 (A, Z1,n−p+1 ) ,
Var R

which leads to the result.
A.1.3 The setting q > 2
If p ≤ n/2 + 1:

A straightforward use of Jensen’s inequality from (A.1) provides

h

h

bp,n
bp,n − E R
E R

i qi

≤

n
mc
j n k−1 bX


 q
E h̄m Z(i−1)m+1 , . . . , Zim

m
i=1
h
h
i qi
b1,n−p+1 − E R
b1,n−p+1
=E R
.

If p > n/2 + 1: Let us now use Rosenthal’s inequality (Proposition D.2) by introducing
symmetric random variables ζ1 , . . . , ζbn/mc such that
∀1 ≤ i ≤ bn/mc ,




0
0
ζi = hm Z(i−1)m+1 , . . . , Zim − hm Z(i−1)m+1
, . . . , Zim
,

where Z10 , . . . , Zn0 are i.i.d. copies of Z1 , . . . , Zn . Then it comes for every γ > 0

q
q
n
n
bX
bX
mc
mc
 



h̄m Z(i−1)m+1 , . . . , Zim  ≤ E 
ζi  ,
E


i=1

i=1

which implies

v
q 
u n
q
n
n


u


bX
b
b
c
c
c
m
m
m
 X
u X
 
 2  

q
t
E
h̄m Z(i−1)m+1 , . . . , Zim  ≤ B(q, γ) max γ
E [ |ζi | ] , 
E ζi 

 .



i=1
i=1
 i=1



Then using for every i that
E [ |ζi |q ] ≤ 2q E



h̄m Z(i−1)m+1 , . . . , Zim
27

 q

,

Celisse and Mary-Huard

it comes


q
n
bX
mc
 

E
h̄m Z(i−1)m+1 , . . . , Zim 
i=1

≤ B(q, γ) max 2q γ

jnk
m

h
E

!
i q i rj n k
q

b1,m
b1,m − E R
b1,m
,
R
.
2Var R
m
h

Hence, it results for every q > 2
h
h
i qi
bp,n − E R
bp,n
E R
q

≤ B(q, γ) max 2 γ

j n k−q+1

h
E

m

h
i q i j n k−q/2
b1,m − E R
b1,m
,
R
m

r



b1,m
2Var R



!q !
,

which concludes the proof.
A.2 Proof of Theorem 3.1
Our strategy of proof follows several ideas. The first one consists in using Proposition 3.1
which says that, for every q ≥ 2,
v
u m
u X
2
p
u
hm (Z1 , . . . , Zm ) − hm (Z1 , . . . , Zj0 , . . . , Zm )
,
h̄m (Z1 , . . . , Zm ) q ≤ 2κq t
j=1

q/2

b1,m by Eq. (2.4), and h̄m (Z1 , . . . , Zm ) = hm (Z1 , . . . , Zm ) −
where hm (Z1 , . . . , Zm ) = R
E [ hm (Z1 , . . . , Zm ) ]. The second idea consists in deriving upper bounds of
∆j hm = hm (Z1 , . . . , Zm ) − hm (Z1 , . . . , Zj0 , . . . , Zm )
by repeated uses of Stone’s lemma, that is Lemma D.5 which upper bounds by kγd the
maximum number of Xi s that can have a given Xj among their k nearest neighbors. Finally,
for technical reasons we have to distinguish the case q = 2 where we get tighter bounds,
and q > 2.
A.2.1 Upper bounding ∆j hm
(i)

For the sake of readability
the notation D(i) = Dm (see Theorem 2.1), and
 let us now use 
(i)
let Dj denote the set Z1 , . . . , Zj0 , . . . , Zn where the i-th coordinate has been removed.
Then, ∆j hm = hm (Z1 , . . . , Zm ) − hm (Z1 , . . . , Zj0 , . . . , Zm ) is now upper bounded by
∆ j hm ≤

1
1 X n
o − 1(
)
1 D(i)
+
(i)
D
Ak (Xi )6=Yi
m m
A j (Xi )6=Yi
i6=j

≤

k

1
1 X (
) .
+
1
(i)
D
(i)
j
m m
D
A
(Xi )6=A
(Xi )
i6=j

k

28

k

(A.2)

Performance of CV to estimate the risk of kNN

Furthermore, let us introduce for every 1 ≤ j ≤ n,

Aj = {1 ≤ i ≤ m, i 6= j, j ∈ Vk (Xi )} and A0j = 1 ≤ i ≤ m, i 6= j, j ∈ Vk0 (Xi )
where Vk (Xi ) and Vk0 (Xi ) denote the indices of the k nearest neighbors of Xi respectively
among X1 , . . . , Xj−1 , Xj , Xj+1 , . . . , Xm and X1 , ..., Xj−1 , Xj0 , Xj+1 , . . . , Xm . Setting Bj =
Aj ∪ A0j , one obtains
∆j hm ≤

1 X (
1
) .
+
1
(i)
D
(i)
m m
AD (Xi )6=A j (Xi )
i∈Bj

k

(A.3)

k

From now on, we distinguish between q = 2 and q > 2 because we will be able to derive
a tighter bound for q = 2 than for q > 2.
A.2.2 Case q > 2
From (A.3), Stone’s lemma (Lemma D.5) provides
1
1 X (
2kγd
1
) ≤
+
1
+
·
∆j hm ≤
(i)
D
(i)
m m
m
m
AD (Xi )6=A j (Xi )
i∈Bj

k

k

Summing over 1 ≤ j ≤ n and applying (a + b)q ≤ 2q−1 (aq + bq ) (a, b ≥ 0 and q ≥ 1), it
comes
X
2
 4
2
∆ j hm ≤
1 + (2kγd )2 ≤ (2kγd )2 ,
m
m
j

hence
m
X

2
hm (Z1 , . . . , Zm ) − hm (Z1 , . . . , Zj0 , . . . , Zm )

j=1

≤

4
(2kγd )2 .
m

q/2

This leads for every q > 2 to
h̄m (Z1 , . . . , Zm )

q

√ 4kγd
,
≤ q 1/2 2κ √
m

which enables to conclude.
A.2.3 Case q = 2
It is possible to obtain a slightly better upper bound in the case q = 2 with the following
reasoning. With the same notation as above and from (A.3), one has

2 
h
i
2
2
2  X (

)
(using 1{·} ≤ 1)
E ∆ j hm
= 2 + 2 E 
1
(i)
 
D
(i)
j
m
m
D
(Xi )6=A
(Xi )
A
i∈Bj

k

k


≤

2
2 
+ 2 E |Bj |
2
m
m


X
i∈Bj

1(
AD
k

29

(i)

D

(Xi )6=Ak

(i)
j

(Xi )

)
.

Celisse and Mary-Huard

Lemma D.5 implies |Bj | ≤ 2kγd , which allows to conclude



h
E

∆j hm

2 i

≤

2
4kγd  X (
)
+
E
1
(i)
.
D
2
(i)
j
m
m2
D
(Xi )6=A
(Xi )
A
i∈Bj

k

k

Summing over j and introducing an independent copy of Z1 denoted by Z0 , one derives
m
h
X
2 i
E hm (Z1 , . . . , Zm ) − hm (Z1 , . . . , Zj0 , . . . , Zm )
j=1

≤

2
4kγd
+
m
m

m
X



E 1

i=1


AkD

(i)

D (i) ∪Z0

(Xi )6=Ak


(Xi )

+ 1(

)


(i)
D
D (i) ∪Z0
Ak
(Xi )6=Ak j (Xi )

√
√
√
2
2
4 k
32γd k k
k k
≤
=
+ 4kγd × 2 √
+√
≤ (2 + 16γd )
,
m
m
m
2πm
2π m

(A.4)

where the last but one inequality results from Lemma D.6.
A.3 Proof of Theorem 3.2
The idea is to plug the upper bounds previously derived for the L1O estimator, namely
Ineq. (2.5) and (2.6) from Theorem 2.2, in the inequalities proved for the moments of the
LpO estimator in Theorem 2.2.
Proof of Ineq. (3.3), (3.4), and (3.5): These inequalities straightforwardly result from
the combination of Theorem 2.2 and Ineq. (2.5) and (2.6) from Theorem 3.1.
Proof of Ineq. (3.6): It results from the upper bounds proved in Theorem 3.1 and plugged
in Ineq. (2.7) (derived from Rosenthal’s inequality with optimized constant γ, namely Proposition D.3).
Then it comes
h
i q i  √ q
bp,n − E R
bp,n
R
≤ 2 2e ×


v

!2 q
u
√







−1
−q+1
q
√

u
√
n
n
k
k
√ q

q
q
√
,
q
max ( q) t
2C1 k √
(2C
q)

2

n−p+1
n−p+1
n−p+1
n−p+1 


 √ q
= 2 2e ×


q

q 
v




q
√

u


q
√
n
k
k
u
q
3/2


j
k
j
k
max ( q)  2C1 k t
,
q
2C

2
√
n
n

n−p+1


(n − p + 1) n−p+1
n−p+1 
n−p+1


n
q 
q o
n
≤
max λ1 q 1/2 , λ2 q 3/2
,
n−p+1
h

E

30

Performance of CV to estimate the risk of kNN

with
v
√ u
√ q
u
λ1 = 2 2e 2C1 k t

k
(n − p + 1)

j

n
n−p+1

k,

√
λ2 = 2 2e2C2 j

n
n−p+1



√
√
Finally introducing Γ = 2 2e max 2C2 , 2C1 provides the result.

31

k
k√

·
n−p+1

Celisse and Mary-Huard

Appendix B. Proofs of exponential concentration inequalities
B.1 Proof of Proposition 4.1
The proof relies on two successive ingredients: McDiarmid’s inequality (Theorem D.3), and
Stone’s lemma (Lemma D.5).
First with Dn = D and Dj = (Z1 , . . . , Zj−1 , Zj0 , Zj+1 , . . . , Zn ), let us start by upper
bp (Dn ) − R
bp (Dj ) for every 1 ≤ j ≤ n.
bounding R
Using Eq. (2.2), one has
bp (D) − R
bp (Dj )
R
n

1X
≤
p


n −1
p

1
p


n −1
p

≤

1
≤
p

i=1
n
X
i=1
n
X

X
e

X

k

1

De

e

j
AD
k (Xi )6=Ak (Xi )

e

1

{i6∈e}

"
 X
n −1
p

i6=j

 1
1{ADe (Xi )6=Yi } − 1 Dje
{i6∈e}
k
A (Xi )6=Yi

#
1{j∈V De (Xi )} + 1

e

De
j∈Vk j (Xi )

k



1{i6∈e} +

1
p


n −1
p

X

1{j6∈e} ,

e
e

where Dje denotes the set of random variables among Dj having indices in e, and VkD (Xi )
Dje

(resp. Vk (Xi )) denotes the set of indices of the k nearest neighbors of Xi among De (resp.
Dje ).
Second, let us now introduce
o
n
De
e
E
Bj n−p = ∪
1 ≤ i ≤ n, i 6∈ e ∪ {j} , Vk j (Xi ) 3 j or VkD (Xi ) 3 j .
e∈En−p

E

Then Lemma D.5 implies Card(Bj n−p ) ≤ 2(k + p − 1)γd , hence
bp (Dn ) − R
bp (Dj ) ≤ 1
R
p

X
E

i∈Bj n−p


n −1
p

X

2 · 1{i6∈e} +

e

4(k + p − 1)γd
1
1
≤
+
·
n
n
n

The conclusion results from McDiarmid’s inequality (Section D.1.5).
B.2 Proof of Theorem 4.1
In this proof, we use the same notation as in that of Proposition 4.1.
The goal of the proof is to provide a refined version of previous Proposition 4.1 by taking
into account the status of each Xj as one of the k nearest neighbors of a given Xi (or not).
To do so, our strategy is to prove a sub-Gaussian concentration inequality by use of
bp .
Lemma D.2, which requires the control of the even moments of the LpO estimator R
Such upper bounds are derived
• First, by using Ineq. (D.4) (generalized Efron-Stein inequality), which amounts to
control the q-th moments of the differences
bp (D) − R
bp (Dj ) .
R
32

Performance of CV to estimate the risk of kNN

• Second, by precisely evaluating the contribution
of each neighbor Xi of a given Xj ,

e
that is by computing quantities such as Pe j ∈ e, i ∈ ē, j ∈ VkD (Xi ) , where Pe [ · ]
denotes the probability measure with respect to the uniform random variable e over
e
En−p , and VkD (Xi ) denotes the indices of the k nearest neighbors of Xi among X e =
{X` , ` ∈ e}.
bp (D) − R
bp (Dj )
B.2.1 Upper bounding R
For every 1 ≤ j ≤ n, one gets
 −1 X 

1
bp (D) − R
bp (Dj ) = n
R
1{j∈ē}
1{ADe (Xj )6=Yj } − 1{ADe (X 0 )6=Y 0 }
j
j
k
k
p
p
e
1X

+ 1{j∈e}
1{ADe (Xi )6=Yi } − 1 Dje
k
p
Ak (Xi )6=Yi

!)
.

i∈ē

Absolute values and Jensen’s inequality then provide
)
 −1 X (
X
1
n
1

bp (D) − R
bp (Dj ) ≤
1 De
R
1{j∈ē} + 1{j∈e}
De
p
p
p
Ak (Xi )6=Ak j (Xi )
e
i∈ē
 −1 X
X
1
n
1

≤ +
1{j∈e}
1 D e
De
n
p
p
Ak (Xi )6=Ak j (Xi )
e
i∈ē

=

1 1
+
n p

n
X

i
Dje
e
Pe j ∈ e, i ∈ ē, AD
(X
)
=
6
A
(X
)
.
i
i
k
k
h

i=1

where the notation Pe means the integration is carried out with respect to the random
variable e ∈ En−p , which follows a discrete uniform distribution over the set En−p of all
n − p distinct indices among {1,
o
o n
n . . .e, n}.
e
Dje
De (X ) ∪ V Dj (X ) , where
(X
)
⊂
j
∈
V
Let us further notice that AD
(X
)
=
6
A
i
i
i
i
k
k
k
k
De

Vk j (Xi ) denotes the set of indices of the k nearest neighbors of Xi among Dje with the
notation of the proof of Proposition 4.1. Then it results
n
i
h
X
Dje
e
(X
)
Pe j ∈ e, i ∈ ē, AD
(X
)
=
6
A
i
i
k
k
i=1

≤

n
X

h
i
De
e
Pe j ∈ e, i ∈ ē, j ∈ VkD (Xi ) ∪ Vk j (Xi )

i=1

≤

n 
X
i=1
n
X

≤2

h
i


De
e
e
Pe j ∈ e, i ∈ ē, j ∈ VkD (Xi ) + Pe j ∈ e, i ∈ ē, j ∈ VkD (Xi ) ∪ Vk j (Xi )


e
Pe j ∈ e, i ∈ ē, j ∈ VkD (Xi ) ,

i=1

which leads to
n

X 

e
bp (D) − R
bp (Dj ) ≤ 1 + 2
R
Pe j ∈ e, i ∈ ē, j ∈ VkD (Xi ) .
n p
i=1

33

Celisse and Mary-Huard

Summing over 1 ≤ j ≤ n the square of the above quantity, it results
n 
X

)2
n

1 2X 
De
+
Pe j ∈ e, i ∈ ē, j ∈ Vk (Xi )
n p
i=1
j=1
( n
)2
n
X 1

2X 
e
≤2
+2
Pe j ∈ e, i ∈ ē, j ∈ VkD (Xi )
n2
p
i=1
j=1
)2
( n
n
X 1X 

2
e
≤ +8
Pe j ∈ e, i ∈ ē, j ∈ VkD (Xi )
.
n
p

n
2 X
bp (D) − R
bp (Dj ) ≤
R

j=1

(

i=1

j=1

B.2.2 Evaluating the influence of each neighbor
Further using that
!2
n

1X 
e
Pe j ∈ e, i ∈ ē, j ∈ VkD (Xi )
p

n
X
j=1

=

n
X

i=1
n
X

1
p2

j=1
n
X
j=1

=


2
e
Pe j ∈ e, i ∈ ē, j ∈ VkD (Xi )
+

i=1

1
p2


 

e
e
Pe j ∈ e, i ∈ ē, j ∈ VkD (Xi ) Pe j ∈ e, i ∈ ē, j ∈ VkD (X` )

X
1≤i6=`≤n

T1

+

T2 ,

let us now successively deal with each of these two terms.
Upper bound on T 1 First, we start by partitioning the sum over j depending on the
rank of Xj as a neighbor of Xi in the whole sample (X1 , . . . , Xn ). It comes
=

n X
n n
h
io2
X
e
Pe j ∈ e, i ∈ ē, j ∈ VkD (Xi )
j=1 i=1

=

n
X


n h
io2
e
Pe j ∈ e, i ∈ ē, j ∈ VkD (Xi )
+

X


i=1

j∈Vk (Xi )


n h
io2
e
.
Pe j ∈ e, i ∈ ē, j ∈ VkD (Xi )

X
j∈Vk+p (Xi )\Vk (Xi )

Then Lemma D.4 leads to
X





e
Pe j ∈ e, i ∈ ē, j ∈ VkD (Xi )

2

X
j∈Vk (Xi )


=k





e
Pe j ∈ e, i ∈ ē, j ∈ VkD (Xi )

j∈Vk+p (Xi )\Vk (Xi )

j∈Vk (Xi )

≤

X

+



pn−p
nn−1

pn−p
nn−1

2
+

2
+

X
j∈Vk+p (Xi )\Vk (Xi )


 pn−p
e
Pe j ∈ e, i ∈ ē, j ∈ VkD (Xi )
nn−1

 p 2 n − p
kp p − 1 p n − p
=k
,
n n−1nn−1
n n−1
34

2

Performance of CV to estimate the risk of kNN

where the upper bound results from

P

j

a2j ≤ (maxj aj )

n
n

1 XX 
e
T1 = 2
Pe j ∈ e, i ∈ ē, j ∈ VkD (Xi )
p
j=1 i=1

2

P

j

aj , for aj ≥ 0. It results


  
kn−p
p 2 n−p
1
=
·
≤ 2n k
p
n n−1
nn−1

Upper bound on T 2 Let us now apply the same idea to the second sum, partitioning
the sum over j depending on the rank of j as a neighbor of ` in the whole sample. Then,
T2 =

≤

n
1 X
p2

1
p2

X


 

e
e
Pe j ∈ e, i ∈ ē, j ∈ VkD (Xi ) Pe j ∈ e, ` ∈ ē, j ∈ VkD (X` )

j=1 1≤i6=`≤n
n X
X
X
i=1 `6=i j∈Vk (X` )
n X
X

+

1
p2


 pn−p
e
Pe j ∈ e, i ∈ ē, j ∈ VkD (Xi )
nn−1
X

i=1 `6=i j∈Vk+p (X` )\Vk (X`


 kp p − 1
e
Pe j ∈ e, i ∈ ē, j ∈ VkD (Xi )
·
n n−1

We then apply Stone’s lemma (Lemma D.5) to get
T2


n
n
i X
X
e
1 XX h
p
n
−
p
kp
p
−
1

Pe j ∈ e, i ∈ ē, j ∈ VkD (Xi ) 
= 2
1j∈Vk (X` )
+
1j∈Vk+p (X` )\Vk (X`
p i=1 j=1
nn−1
n n−1
`6=i

`6=i





n
pn−p
kp p − 1
k2 n − p
p−1
1 X kp
kγd
+ (k + p)γd
= γd
+ (k + p)
≤ 2
p i=1 n
nn−1
n n−1
n n−1
n−1


k2
p−1
= γd
1 + (k + p − 1)
.
n
n−1

Gathering the upper bounds The two previous bounds provide
n
X
j=1

(

)2
n

1X 
e
= T1 + T2
Pe j ∈ e, i ∈ ē, j ∈ VkD (Xi )
p
i=1

kn−p
k2
≤
+ γd
nn−1
n



p−1
1 + (k + p − 1)
,
n−1

which enables to conclude
n 
X

2
bp (D) − R
bp (Dj )
R

j=1

2
≤
n






p−1
8k 2 (1 + γd )
p−1
2
1 + 4k + 4k γd 1 + (k + p)
≤
1 + (k + p)
.
n−1
n
n−1
35

Celisse and Mary-Huard

B.2.3 Generalized Efron-Stein inequality
Then (D.4) provides for every q ≥ 1
h

bp,n
bp,n − E R
R

√

i
2q

≤ 4 κq

s

8(1 + γd )k 2
n




p−1
1 + (k + p)
.
n−1

√
Hence combined with q! ≥ q q e−q 2πq, it comes


q

h
i2q 
2
p−1
q 8(1 + γd )k
b
b
1 + (k + p)
E Rp,n − E Rp,n
≤ (16κq)
n
n−1

q

2
p−1
8(1 + γd )k
1 + (k + p)
≤ q! 16eκ
.
n
n−1
h
i
2
p−1
d )k
The conclusion follows from Lemma D.2 with C = 16eκ 8(1+γ
1
+
(k
+
p)
n
n−1 . Then
for every t > 0,






 


2
nt
bp,n − E R
bp,n > t ∨ P E R
bp,n − R
bp,n > t ≤ exp −
h
i ·
P R
p−1
2
1024eκk (1 + γd ) 1 + (k + p) n−1
B.3 Proof of Theorem 4.2 and Proposition 4.2
B.3.1 Proof of Theorem 4.2
If p < n/2 + 1:
In what follows, we exploit a characterization of sub-Gaussian random variables by their
2q-th moments (Lemma D.2).
From (3.3) and 
(3.4) applied with 2q, and further introducing a constant ∆ =
p
√
C1 /2, C2 > 0, it comes for every q ≥ 1
4 e max

q
 2
q
h
i 2q   ∆2
∆
k2
k2
q
b
b
E Rp,n − E Rp,n
(2q) ≤
q! ,
(B.1)
≤
16e n − p + 1
8 n−p+1
√
with q q ≤ q!eq / 2πq. Then Lemma D.2 provides for every t > 0



h
i

 h
i

t2
b
b
b
b
P Rp,n − E Rp,n > t ∨ P E Rp,n − Rp,n > t ≤ exp −(n − p + 1) 2 2 .
∆ k
If p ≥ n/2 + 1:
This part of the proof relies on Proposition D.1 which provides an exponential concentration
inequality from upper bounds on the moments of a random variable.
j
k
n
Let us now use (3.3) and (3.6) combined with (D.1), where C = n−p+1
, q0 = 2, and
minj αj = 1/2. This provides for every t > 0

h
h
i
i 
n
b
b
P Rp,n − E Rp,n > t ≤
e×
n−p+1


!1/3 



2


2
2
1
n
t
n
t
,
√ , (n − p + 1)
exp − min (n − p + 1)


2e
n − p + 1 4Γ2 k k
n − p + 1 4Γ2 k 2
36

Performance of CV to estimate the risk of kNN

where Γ arises from Eq. (3.6).
B.3.2 Proof of Proposition 4.2
As in the previous proof, the derivation of the deviation terms results from Proposition D.1.
With the same notation and reasoning as in the jprevious
k proof, let us combine (3.3)
n
and (3.6). From (D.2) of Proposition D.1 where C = n−p+1 , q0 = 2, and minj αj = 1/2,
it results for every t > 0



v
s


u
i
h
3/2
2e
k
k
n
u
 b



3/2
bp,n > Γ
k t + 2e j
kt   ≤
e · e−t ,
P  Rp,n − E R
t j
n
n
(n − p + 1)
n−p+1
n−p+1

where Γ > 0 is given by Eq. (3.6).

37

n−p+1

Celisse and Mary-Huard

Appendix C. Proofs of deviation upper bounds
C.1 Proof of Ineq. (5.3) in Theorem 5.1
The proof follows the same strategy as that of Theorem 2.1 in Rogers and Wagner (1978).
Along the proof, we will repeatedly use some notation that we briefly introduce here.
First, let us define Z0 = (X0 , Y0 ) and Zn+1 = (Xn+1 , Yn+1 ) that are independent copies
of Z1 . Second to ease the reading of the proof, we also use several shortcuts: fbk (X0 ) =
De
n
be
AD
k (X0 ), and fk (X0 ) = Ak (X0 ) for every set of indices e ∈ En−p (with cardinality n − p).
Finally along the proof, e, e0 ∈ En−p denote two random variables which are sets of
distinct indices with discrete uniform distribution over En−p . The notation Pe (resp. Pe,e0 )
means the integration is made with respect to the sample D and also the random variable
e (resp. D and also the random variables e, e0 ). Ee [ · ] and Ee,e0 [ · ] are teh corresponding
expectations. Note that the sample D and the random variables e, e0 are independent from
each other, so that computing for instance Pe (i 6∈ e) amounts to integrating with respect
to the random variable e only.
C.1.1 Main part of the proof
n
With the notation Ln = L(AD
k ), let us start from
i
h
i
i
h
h
 
bp,n Ln ,
bp2 (ADn ) + E L2n − 2E R
bp,n − Ln )2 = E R
E (R
k

let us notice that


 
E L2n = P fbk (X0 ) 6= Y0 , fbk (Xn+1 ) 6= Yn+1 ,
and
h
i


bp,n Ln = Pe fbk (X0 ) 6= Y0 , fbe (Xi ) 6= Yi | i ∈
E R
/
e
Pe (i 6∈ e) .
k
It immediately comes
i
h
bp,n − Ln )2
E (R
i


h
b2 (ADn ) − Pe fbk (X0 ) 6= Y0 , fbe (Xi ) 6= Yi | i ∈
/
e
Pe (i 6∈ e)
(C.1)
=E R
p
k
k

i
h 


/ e Pe (i ∈
/ e) .
+ P fbk (X0 ) 6= Y0 , fbk (Xn+1 ) 6= Yn+1 − Pe fbk (X0 ) 6= Y0 , fbke (Xi ) 6= Yi | i ∈
(C.2)
The proof then consists in successively upper bounding the two terms (C.1) and (C.2) of
the last equality.
Upper bound of (C.1) First, we have
h
i
h
i
X
bp2 (ADn ) =
0
0
0}
p2 E R
E
1
1
1
1
e
e
e,e
b
b
{i
∈e}
/
{j
∈e
/
k
{f (Xi )6=Yi }
{f (Xj )6=Yj }
k

i,j

=

k

i
Ee,e0 1{fbe (Xi )6=Yi } 1{i∈e}
/ 1{fbe0 (Xi )6=Yi } 1{i∈e
/ 0}
k
k
i
h
i
X
+
Ee,e0 1{fbe (Xi )6=Yi } 1{i∈e}
/ 1{fbe0 (Xj )6=Yj } 1{j ∈e
/ 0} .
X

i6=j

h

k

38

k

Performance of CV to estimate the risk of kNN

Let us now introduce the five following events where we emphasize e and e0 are random
variables with the discrete uniform distribution over En−p :
Si0 = {i ∈
/ e, i ∈
/ e0 },
1
Si,j

= {i ∈
/ e, j ∈
/ e0 , i ∈
/ e0 , j ∈
/ e},

2
Si,j
= {i ∈
/ e, j ∈
/ e0 , i ∈
/ e0 , j ∈ e},

3
Si,j

= {i ∈
/ e, j ∈
/ e0 , i ∈ e0 , j ∈
/ e},

4
Si,j
= {i ∈
/ e, j ∈
/ e0 , i ∈ e0 , j ∈ e}.

Then,
i X


h

e
e0
0
0
b
b
b2 (ADn ) =
0
P
f
(X
)
=
6
Y
,
f
(X
)
=
6
Y
|S
p2 E R
i
i
i
i i Pe,e0 Si
e,e
p
k
k
k
i

+

4
XX



 
0
`
`
Pe,e0 fbke (Xi ) 6= Yi , fbke (Xi ) 6= Yi |Si,j
Pe,e0 Si,j

i6=j `=1




0
= nPe,e0 fbke (X1 ) 6= Y1 , fbke (X1 ) 6= Y1 |S10 Pe,e0 S10
+ n(n − 1)

4
X





0
`
`
Pe,e0 fbke (X1 ) 6= Y1 , fbke (X2 ) 6= Y2 | S1,2
Pe,e0 S1,2
.

`=1

Furthermore since
"
#
4


X


1
1 X
`
0
nPe,e0 S1 + n(n − 1)
Pe,e0 S1,2
= 2
Pe,e0 i ∈
/ e, j ∈
/ e0 = 1,
2
p
p
i,j

`=1

it comes

i

h
bp2 (ADn ) − Pe,e0 fbk (X0 ) 6= Y0 , fbe (X1 ) 6= Y1
=
E R
k
k

n
n(n − 1)
A+
B,
2
p
p2

(C.3)

where
h



i
0
A = Pe,e0 fbke (X1 ) 6= Y1 , fbke (X1 ) 6= Y1 | S10 − Pe,e0 fbk (X0 ) 6= Y0 , fbke (X1 ) 6= Y1 | S10

× Pe,e0 S10 ,
4 h



i
X
0
`
`
Pe,e0 fbke (X1 ) 6= Y1 , fbke (X2 ) 6= Y2 | S1,2
− Pe,e0 fbk (X0 ) 6= Y0 , fbke (X1 ) 6= Y1 | S1,2
and B =
`=1



`
× Pe,e0 S1,2
.
• Upper bound for A:
To upper bound A, simply notice that:

  p 2
A ≤ Pe,e0 Si0 ≤ Pe,e0 i ∈
/ e, i ∈
/ e0 ≤
.
n
• Upper bound for B:
To obtain an upper bound for B, one needs to upper bound




0
`
`
Pe,e0 fbke (X1 ) 6= Y1 , fbke (X2 ) 6= Y2 | S1,2
− Pe,e0 fbk (X0 ) 6= Y0 , fbke (X1 ) 6= Y1 | S1,2
, (C.4)
which depends on `, i.e. on the fact that index 2 belongs or not to the training set e.
39

Celisse and Mary-Huard

• If 2 6∈ e (i.e. ` = 1 or 3): Then, Lemma C.2 proves
√
4p k
(C.4) ≤ √
·
2πn
• If 2 ∈ e (i.e. ` = 2 or 4): Then, Lemma C.3 settles
√
√
8 k
4p k
(C.4) ≤ √
+√
·
2π(n − p)
2πn
Combining the previous bounds and Lemma C.1 leads to
√
√ !
√ !




8 k
4p k 
4p k 
1
3
2
4
Pe,e0 S1,2 + Pe,e0 S1,2 + √
+√
Pe,e0 S1,2
+ Pe,e0 S1,2
B≤ √
2πn
2π(n − p)
2πn
√








2 2√ p 
2
p 
1
3
2
4
≤ √
k
Pe,e0 S1,2 + Pe,e0 S1,2 +
+
Pe,e0 S1,2 + Pe,e0 S1,2
n
n−p n
π
√





2 2√ p
2
0
2
4
≤ √
Pe,e0 i ∈
/ e, j ∈
/e +
Pe,e0 S1,2 + Pe,e0 S1,2
k
n
n−p
π
√



2 2 √ p  p 2
2
(n − p)p2 (p − 1) (n − p)2 p2
≤ √
+
k
+ 2
n n
n−p
n2 (n − 1)2
n (n − 1)2
π
√


2 2 √  p 2 p
2
≤ √
k
+
.
n
n n−1
π
Back to Eq. (C.3), one deduces
i


h
bp2 (ADn ) − Pe,e0 fbk (X0 ) 6= Y0 , fbe (X1 ) 6= Y1 = n A + n(n − 1) B
E R
k
k
p2
p2
√
√
1 2 2 (p + 2) k
≤ + √
·
n
n
π
Upper bound of (C.2) First observe that




(−1)
/ e = Pe,e0 fbk (X0 ) 6= Y0 , fbke (Xn+1 ) 6= Yn+1
Pe,e0 fbk (X0 ) 6= Y0 , fbke (Xi ) 6= Yi | i ∈
(−1)
where fbk
is built on sample (X2 , Y2 ), ..., (Xn+1 , Yn+1 ). One has




/e
P fbk (X0 ) 6= Y0 , fbk (Xn+1 ) 6= Yn+1 − Pe,e0 fbk (X0 ) 6= Y0 , fbke (Xi ) 6= Yi | i ∈


 (−1)

(X0 ) 6= Y0 , fbke (Xn+1 ) 6= Yn+1
= P fbk (X0 ) 6= Y0 , fbk (Xn+1 ) 6= Yn+1 − Pe,e0 fbk




(−1)
≤ P fbk (X0 ) 6= fbk
(X0 ) + Pe,e0 fbke (Xn+1 ) 6= fbk (Xn+1 )
√
√
4 k
4p k
≤ √
+√
,
2πn
2πn

40

Performance of CV to estimate the risk of kNN

where we used Lemma D.6 again to obtain the last inequality.
Conclusion:
The conclusion simply results from combining bonds (C.1) and (C.2), which leads to

E

bp,n − Ln
R

2 

√
√
2 2 (2p + 3) k
1
≤ √
+
·
n
n
π

C.1.2 Combinatorial lemmas
All the lemmas of the present section are proved with the notation introduced at the beginning of Section C.1.
Lemma C.1. For any 1 ≤ i 6= j ≤ n,
n−2
 (n−2
(n−p
)
n−p )
1
× n
,
Pe,e0 Si,j
= n
(n−p ) (n−p )

Pe,e0

3
Si,j



n−p−1
(n−p
n−2 ) (n−2 )
,
= n
(n−p ) (nn−p )

n−p
 (n−p−1
)
) (n−2
2
Pe,e0 Si,j
= n−2
×
,
n
n
(n−p )
(n−p )

Pe,e0

4
Si,j



n−p−1
)
(n−2
) (n−p−1
× n−2
·
= n
n
(n−p )
(n−p )

Proof of Lemma C.1. Along the proof, we repeatedly exploit the independence of the random variables e and e0 , which are set of n − p distinct indices with the discrete uniform
distribution over En−p .
Note also that an important ingredient is that the probability of each one of the following
events does not depend on the particular choice of the indices (i, j), but only on the fact
that i 6= j.
1
Pe,e0 Si,j



= Pe,e0 i ∈
/ e, j ∈
/ e0 , i ∈
/ e0 , j ∈
/e



Pe,e0

n−2
 (n−p
) (n−2
n−p )
= Pe (i ∈
/ e, j ∈
/ e) Pe0 j ∈
× n
·
/ e0 , i ∈
/ e0 = n
(n−p ) (n−p )


2
Si,j
= Pe,e0 i ∈
/ e, j ∈
/ e0 , i ∈
/ e0 , j ∈ e

Pe,e0

 (n−p−1 ) (n−p
)
× n−2
·
= Pe (i ∈
/ e, j ∈ e) Pe0 j ∈
/ e0 , i ∈
/ e0 = n−2
n
n
(n−p )
(n−p )


3
Si,j
= Pe,e0 i ∈
/ e, j ∈
/ e0 , i ∈ e0 , j ∈
/e

Pe,e0

 (n−p ) (n−p−1
n−2 )
= Pe (i ∈
/ e, j ∈
/ e) Pe0 j ∈
/ e0 , i ∈ e0 = n−2
·
n
(n−p ) (nn−p )


4
Si,j
= Pe,e0 i ∈
/ e, j ∈
/ e0 , i ∈ e0 , j ∈ e
 (n−p−1 ) (n−p−1
)
= Pe (i ∈
/ e, j ∈ e) Pe0 j ∈
/ e0 , i ∈ e0 = n−2
× n−2
·
n
n
(n−p )
(n−p )

41

Celisse and Mary-Huard

Lemma C.2. With the above notation, for ` ∈ {1, 3}, it comes
√




0
4p k
`
`
≤√
− Pe fbk (X0 ) 6= Y0 , fbke (X1 ) 6= Y1 | S1,2
Pe fbke (X1 ) 6= Y1 , fbke (X2 ) 6= Y2 | S1,2
·
2πn

Proof of Lemma C.2. First remind that as a test sample element Z0 cannot belong to either
e or e0 . Consequently, an exhaustive formulation of




`
`
Pe fbk (X0 ) 6= Y0 , fbke (X1 ) 6= Y1 | S1,2
= Pe fbk (X0 ) 6= Y0 , fbke (X1 ) 6= Y1 | S1,2
.
Then it results


 (2)

`
`
Pe fbk (X0 ) 6= Y0 , fbke (X1 ) 6= Y1 | S1,2
= Pe fbk (X2 ) 6= Y2 , fbke (X1 ) 6= Y1 | S1,2
,
(2)

where fbk is built on sample (X0 , Y0 ), (X1 , Y1 ), (X3 , Y3 ), ..., (Xn , Yn ).
Hence Lemma D.6 implies




0
`
`
− Pe,e0 fbk (X0 ) 6= Y0 , fbke (X1 ) 6= Y1 | S1,2
Pe,e0 fbke (X1 ) 6= Y1 , fbke (X2 ) 6= Y2 | S1,2


 (2)

0
`
`
− Pe,e0 fbk (X2 ) 6= Y2 , fbke (X1 ) 6= Y1 | S1,2
= Pe,e0 fbke (X1 ) 6= Y1 , fbke (X2 ) 6= Y2 | S1,2
n
o n
n (2)
o

o n 0
o

`
`
≤ Pe,e0
fbke (X1 ) 6= Y1 4 fbke (X1 ) 6= Y1 | S1,2
+ Pe,e0
fbk (X2 ) 6= Y2 4 fbke (X2 ) 6= Y2 | S1,2
√
 (2)

4p k
e0
`
b
b
·
= Pe,e0 fk (X2 ) 6= fk (X2 ) | S1,2 ≤ √
2πn

Lemma C.3. With the above notation, for ` ∈ {2, 4}, it comes




0
`
`
Pe,e0 fbke (X1 ) 6= Y1 , fbke (X2 ) 6= Y2 | S1,2
− Pe,e0 fbk (X0 ) 6= Y0 , fbke (X1 ) 6= Y1 | S1,2
√
√
4p k
8 k
≤√
+√
·
2π(n − p)
2πn
Proof of Lemma C.3. As for the previous lemma, first notice that


 (2)

e0
`
`
Pe,e0 fbk (X0 ) 6= Y0 , fbke (X1 ) 6= Y1 | S1,2
= Pe,e0 fbk (X2 ) 6= Y2 , fbk (X1 ) 6= Y1 | S1,2
,
e0
where fbk is built on sample e with observation (X2 , Y2 ) replaced with (X0 , Y0 ). Then





0
`
`
Pe,e0 fbke (X1 ) 6= Y1 , fbke (X2 ) 6= Y2 | S1,2
− Pe,e0 fbk (X0 ) 6= Y0 , fbke (X1 ) 6= Y1 | S1,2




(2)
e0
e
e0
`
`
b
b
b
b
0
0
= Pe,e fk (X1 ) 6= Y1 , fk (X2 ) 6= Y2 | S1,2 − Pe,e fk (X2 ) 6= Y2 , fk (X1 ) 6= Y1 | S1,2

 n

n
o n e0
o

o
(2)
e
`
e0
`
b
b
b
b
0
0
≤ Pe,e
fk (X1 ) 6= Y1 4 fk (X1 ) 6= Y1 | S1,2 + Pe,e
fk (X2 ) 6= Y2 4 fk (X2 ) 6= Y2 | S1,2
√
√




e0
(2)
4p k
8 k
e
`
e0
`
b
b
b
b
+√
·
= Pe,e0 fk (X1 ) 6= fk (X1 ) | S1,2 + Pe,e0 fk (X2 ) 6= fk (X2 ) | S1,2 ≤ √
2π(n − p)
2πn

42

Performance of CV to estimate the risk of kNN

C.2 Proof of Proposition 5.1
The bias of the L1O estimator is equal to
h 


i
Dn−1
n
E L AD
−
L
A
k
k
i
i i
h
 h h
Dn−1
n
(X)
−
A
(X)
|
X
(X),
X
|
X
= −2E (η(X) − 1/2) E E AD
(k+1)
k
k
i
i i
h
 h h
Dn−1
n
(X)
|
X
(X),
X
|
X
(X)
−
A
= −2E (η(X) − 1/2) E E AD
(k+1)
k
k
i 
n h

Dn−1
n
(0) | X(k+1) (0) = 0, X = 0 P X(k+1) (0) = 0 | X = 0
= 1/2 E AD
k (0) − Ak
i 
h
o
Dn−1
n
(0)
−
A
(0)
|
X
(0)
=
1,
X
=
0
P
X
(0)
=
1
|
X
=
0
+E AD
(k+1)
(k+1)
k
k
i 
n h

D
n−1
n
(1)
|
X
(1)
=
0,
X
=
1
P X(k+1) (1) = 0 | X = 1
(1)
−
A
− 1/2 E AD
(k+1)
k
k
i 
h
o
Dn−1
n
,
(1)
−
A
(1)
|
X
(1)
=
1,
X
=
1
P
X
(1)
=
1
|
X
=
1
+E AD
(k+1)
(k+1)
k
k
where X(k+1) (x) denotes the k + 1-th neighbor of x.
Then, a few remarks lead to simplify the above expression.
• On the one hand it is easy to check that
i
h
Dn−1
n
(0)
−
A
(0)
|
X
(0)
=
0,
X
=
0
E AD
(k+1)
k
k
i
h
Dn−1
n
(1)
−
A
(1)
|
X
(1)
=
1,
X
=
1
= 0,
= E AD
(k+1)
k
k
since all of the k + 1 nearest neighbors share the same label.
• On the other hand, let us notice
h
i
Dn−1
n
E AD
(0)
−
A
(0)
|
X
(0)
=
1,
X
=
0
(k+1)
k
k
h
i
Dn−1
n
= P AD
(0)
=
1,
A
(0)
=
0
|
X
(0)
=
1,
X
=
0
(k+1)
k
k
h
i
Dn−1
n
− P AD
(0)
=
0,
A
(0)
=
1
|
X
(0)
=
1,
X
=
0
.
(k+1)
k
k
n
Then knowing X(k+1) (X) and X are not equal implies the only way for AD
and
k
Dn−1
Ak
to differ is that the numbers of k nearest neighbors of each label are almost
equal, that is either equal to (k − 1)/2 or to (k + 1)/2 (k is odd by assumption).

With N01 (respectively Ñ01 ) denoting the number of 1s among th k nearest neighbors of
X = 0 among X1 , . . . , Xn (resp. X1 , . . . , Xn−1 ), the proof of Theorem 3 in Chaudhuri
43

Celisse and Mary-Huard

and Dasgupta (2014) leads to
i
h
Dn−1
n
(0)
=
0
|
X
(0)
=
1,
X
=
0
(0)
=
1,
A
P AD
(k+1)
k
k
h
i
= P n ∈ Vk (0), N01 = (k + 1)/2, Ñ01 = (k − 1)/2 | X(k+1) (0) = 1, X = 0
i
h
k
= × P Ñ01 = (k − 1)/2 | N01 = (k + 1)/2, X(k+1) (0) = 1, X = 0
n

× P N01 = (k + 1)/2 | X(k+1) (0) = 1, X = 0
 




k
k+1 k−1
k
= ×P H
,
; 1 = 1 · η1 ×
η̄ (k+1)/2 (1 − η̄)(k−1)/2
n
2
2
(k + 1)/2


k+1
k
=
× η1 ×
η̄ (k+1)/2 (1 − η̄)(k−1)/2 ,
2n
(k + 1)/2
where H(a, b; c) denotes a hypergeometric random variable with a successes in a population of cardinality a + b, and c draws, and η̄ = π0 η0 + (1 − π0 )η1 = 1/2.
i
h
Dn−1
n
(0)
=
0,
A
(0)
=
1
|
X
(0)
=
1,
X
=
0
Following the same reasoning for P AD
(k+1)
k
k
and recalling that η0 = 0 and η1 = 1 by assumption, it results


h
i
k+1
k
Dn−1
Dn
E Ak (0) − Ak
(0) | X(k+1) (0) = 1, X = 0 = −
×
(1/2)k .
2n
(k + 1)/2
• Similar calculations applied to X = 1 finally lead to



i k + 1 
h 


k
Dn−1
Dn
− L Ak
=
E L Ak
×
(1/2)k × P X(k+1) (0) = 1 | X = 0
2n
(k + 1)/2


k+1
k
=
×
(1/2)k × P [ B(n, 1/2) ≤ k ] .
(k + 1)/2
2n
• The conclusion then follows from considering k
P [ B(n, 1/2) ≤ k ] ≥ 1/2, and also by noticing that

≥

n/2 which entails that

√


k+1
k
k
k
×
(1/2) ≥ C
,
2n
(k + 1)/2
n
where denotes a numeric constant independent of n and k.

44

Performance of CV to estimate the risk of kNN

Appendix D. Technical results
D.1 Main inequalities
D.1.1 From moment to exponential inequalities
Proposition D.1 (see also Arlot (2007), Lemma 8.10). Let X denote a real valued random
variable, and assume there exist C ≥ 1, λ1 , . . . , λN > 0, and α1 , . . . , αN > 0 (N ∈ N∗ ) such
that for every q ≥ q0 ,
!q
N
X
q
αi
E [ |X| ] ≤ C
λi q
.
i=1

Then for every t > 0,
−(mini αi )e−1 minj

P [ |X| > t ] ≤

Ceq0 minj αj e





t
N λj



1
αj





,

Furthermore for every x > 0, it results
"
αi #

N
X
ex
≤ Ceq0 minj αj · e−x .
P |X| >
λi
minj αj

(D.1)

(D.2)

i=1

Proof of Proposition D.1. By use of Markov’s inequality applied to |X|q (q > 0), it comes
for every t > 0
!q
PN
αi
λ
q
E [ |X|q ]
i
i=1
P [ |X| > t ] ≤ 1q≥q0
+ 1q<q0 ≤ 1q≥q0 C
+ 1q<q0 .
tq
t
P
αi
αi
Now using the upperbound N
 λi q ≤ N maxi {λi q } and choosing the particular value
 1 i=1

αj
t
q̃ = q̃(t) = e−1 minj
, one gets
N λj



 1 αi  q̃
αj
t
−α
i
minj
N λj

 maxi N λi e
 + 1q̃<q
P [ |X| > t ] ≤ 1q̃≥q0 C 
0


t



−(mini αi

) e−1

minj





≤ 1q̃≥q0 Ce

t
N λj



1
αj






+ 1q̃<q0 ,

which provides (D.1).


α i
P
ex
Let us now turn to the proof of (D.2). From t∗ = N
λ
combined with
i
i=1
minj αj
x
∗
q = minj αj , it arises for every x > 0

α i

α i
PN
PN
ex

 PN λ
−1 ex
∗
α
λ
e
i
i
i
i=1
i=1
minj αj
minj αj
i=1 λi (q )

αi ≤ max e−αk P

αi = e− mink αk .
= P
N
N
ex
ex
k
t∗
λ
λ
i=1

i

i=1

minj αj

45

i

minj αj

Celisse and Mary-Huard

Then,
PN

∗ αi
i=1 λi (q )
t∗

C

!q ∗

−(mink αk ) minx α

≤ Ce

j

j

= Ce−x .

Hence,
"
P |X| >

N
X
i=1


λi

ex
minj αj

αi #

≤ Ce−x 1q∗ ≥q0 + 1q∗ <q0 ≤ Ceq0 minj αj · e−x ,

since eq0 minj αj ≥ 1 and −x + q0 minj αj ≥ 0 if q < q0 .

D.1.2 Sub-Gaussian random variables
Lemma D.1 (Theorem 2.1 in Boucheron et al. (2013) first part). Any centered random
2
variable X such that P (X > t) ∨ P (−X > t) ≤ e−t /(2ν) satisfies


E X 2q ≤ q! (4ν)q .
for all q in N+ .
Lemma D.2 (Theorem 2.1 in Boucheron et al. (2013) second part). Any centered random
variable X such that


E X 2q ≤ q!C q .
2 /(2ν)

for some C > 0 and q in N+ satisfies P (X > t) ∨ P (−X > t) ≤ e−t

with ν = 4C.

D.1.3 The Efron-Stein inequality
Theorem D.1 (Efron-Stein’s inequality Boucheron et al. (2013), Theorem 3.1). Let
X1 , . . . , Xn be independent random variables and let Z = f (X1 , . . . , Xn ) be a squareintegrable function. Then
Var(Z) ≤

n
X

h
i
E (Z − E [Z | (Xj )j6=i ])2 = ν.

i=1

Moreover if X10 , . . . , Xn0 denote independent copies of X1 , . . . , Xn and if we define for every
1≤i≤n

Zi0 = f X1 , . . . , Xi0 , . . . , Xn ,
then
n

ν=

2 i
1X h
E Z − Zi0
.
2
i=1

46

Performance of CV to estimate the risk of kNN

D.1.4 Generalized Efron-Stein’s inequality
Theorem D.2 (Theorem 15.5 in Boucheron et al. (2013)). Let X1 , . . . , Xn n independent
random variables, f : Rn → R a measurable function, and define ζ = f (X1 , . . . , Xn ) and
0
0
ζi0 = f (Xh1 , . . . , Xi0 , . . . , Xn ), with
copies of Xii . Furthermore let
i X1 , . . . , Xn independent
hP 


Pn 
2
n
0
0 ) 2 | X n . Then there exists
n
(ζ
−
ζ
V+ = E
)
(Z
−
Z
|
X
and
ζ
=
E
−
1
1
i
i
i
i
+
−
a constant κ ≤ 1, 271 such that for all q in [2, +∞[,
q
q
(ζ − Eζ)− q ≤ 2κq kV− kq/2 .
(ζ − Eζ)+ q ≤ 2κq kV+ kq/2 ,
and
Corollary D.1. With the same notation, it comes
v
v
u X
u X
p
p
u n
u n
2
0
t
kζ − Eζkq ≤ 2κq
(ζ − ζi )
(ζ − E [ζ | (Xj )j6=i ])2
≤ 4κq t
i=1

i=1

q/2

. (D.3)
q/2

Moreover considering ζ (j) = f (X1 , . . . , Xj−1 , Xj+1 , . . . , Xn ) for every 1 ≤ j ≤ n, it results
r

Pn
√
(j) 2
.
(D.4)
kζ − Eζkq ≤ 2 2κq
i=1 ζ − ζ
q/2

D.1.5 McDiarmid’s inequality
Theorem D.3. Let X1 , ..., Xn be independent random variables taking values in a set A,
and assume that f : An → R satisfies
sup
x1 ,...,xn ,x0i

f (x1 , ..., xi , ..., xn ) − f (x1 , ..., x0i , ..., xn ) ≤ ci , 1 ≤ i ≤ n .

Then for all ε > 0, one has
2/

Pn

2/

Pn

P (f (X1 , ..., Xn ) − E [f (X1 , ..., Xn )] ≥ ε) ≤ e−2ε

P (E [f (X1 , ..., Xn )] − f (X1 , ..., Xn ) ≥ ε) ≤ e−2ε

2
i=1 ci
2
i=1 ci

A proof can be found in Devroye et al. (1996) (see Theorem 9.2).
D.1.6 Rosenthal’s inequality
Proposition D.2 (Eq. (20) in Ibragimov and Sharakhmetov (2002)). Let X1 , . . . , Xn denote independent real random variables with symmetric distributions. Then for every q > 2
and γ > 0,

v
q 
" n
u n
q#
n
 X
X
X
u

 
≤ B(q, γ) γ
E [ |Xi |q ] ∨ t
E
Xi
E Xi2  ,


i=1

i=1

i=1

where a ∨ b = max(a, b) (a, b ∈ R), and B(q, γ) denotes a positive constant only depending
on q and γ. Furthermore, the optimal value of B(q, γ) is given by
B ∗ (q, γ) =
=

q

| ]
1 + E[ |N
, if
γ
q
−q/(q−1)
0
γ
E [ |Z − Z | ] , if

47

2 < q ≤ 4,
4 < q,

Celisse and Mary-Huard

where N denotes a standard
Gaussian
variable, and Z, Z 0 are i.i.d. random variables with
 1/(q−1)

Poisson distribution P γ 2
.
Proposition D.3. Let X1 , . . . , Xn denote independent real random variables with symmetric distributions. Then for every q > 2,

v
q 
" n
u n
q#
n
 X
 √ q
X
X
u

 
√
E [ |Xi |q ] , ( q)q t
E
≤ 2 2e max q q
Xi
E Xi2  .


i=1

i=1

i=1

Proof of Proposition D.3. From Lemma D.3, let us observe
• if 2 < q ≤ 4, choosing γ = 1 provides
 √ √ q
B ∗ (q, γ) ≤ 2 2e q .
• if 4 < q, γ = q (q−1)/2 leads to
q

√ q  √ √ q
 q
∗
−q/2
1/2
B (q, γ) ≤ q
4eq q + q
≤ q −q/2
8eq = 2 2e q .
Plugging the previous upper bounds in Rosenthal’s inequality (Proposition D.2), it results
for every q > 2

v
q 
" n
u n
q#
n
√ X
 √ √ q
X
X
u

 
E
E [ |Xi |q ] , t
Xi
E Xi2  .
≤ 2 2e q max ( q)q


i=1

i=1

i=1

Lemma D.3. With the same notation as Proposition D.2 and for every γ > 0, it comes
• for every 2 < q ≤ 4,
√ √ q
2e q
B (q, γ) ≤ 1 +
,
γ
∗

• for every 4 < q,
∗

B (q, γ) ≤ γ

−q/(q−1)

q

 q
1/(q−1)
4eq γ
+q
.

Proof of Lemma D.3. If 2 < q ≤ 4,
E [ |N |q ]
B ∗ (q, γ) = 1 +
≤1+
γ

√ √
2e q
γ

√

q

q2
e

48

≤1+

q√ q

2e

e
γ

q

q2
e

√ √ q
2e q
=1+
,
γ

Performance of CV to estimate the risk of kNN

by use of Lemma D.9 and
If q > 4,

√

q 1/q ≤

√

e for every q > 2.

q
Z − Z0
 iq/2
√ h q  1/(q−1)
≤ γ −q/(q−1) 2q/2+1 e q
γ
+q
e
 iq/2
h 
√
√
q
q q
≤ γ −q/(q−1) 2q/2 2e e
γ 1/(q−1) + q
e
q

h

 iq/2
 q
−q/(q−1)
1/(q−1)
−q/(q−1)
1/(q−1)
≤γ
4eq γ
+q
=γ
4eq γ
+q
,

B ∗ (q, γ) = γ −q/(q−1) E



applying Lemma D.11 with λ = 1/2γ 1/(q−1) .

D.2 Technical lemmas
D.2.1 Basic computations for resampling applied to the kNN algorithm
Lemma D.4. For every 1 ≤ i ≤ n and 1 ≤ p ≤ n, one has
p
Pe (i ∈ ē) = ,
n
n
X
kp
,
Pe [ i ∈ ē, j ∈ Vke (Xi ) ] =
n

(D.5)
(D.6)

j=1

X

Pe [ i ∈ ē, j ∈ Vke (Xi ) ] =

k<σi (j)≤k+p

kp p − 1
·
n n−1

(D.7)

Proof of Lemma D.4. The first equality is straightforward. The second one results from
simple calculations as follows.


 −1 X
n
n  −1 X
n
X
X
X
n
n
Pe [ i ∈ ē, j ∈ Vke (Xi ) ] =
1i∈ē 1j∈Vke (Xi ) =
1i∈ē 
1j∈Vke (Xi ) 
p
p
e
e
j=1
j=1
j=1
!
 −1 X
n
p
=
1i∈ē k = k .
n
p
e
For the last equality, let us notice every j ∈ Vi satisfies
Pe [ i ∈ ē, j ∈ Vke (Xi ) ] = Pe [ j ∈ Vke (Xi ) | i ∈ ē ] Pe [ i ∈ ē ] =

n−1p
,
n−pn

hence
X
k<σi (j)≤k+p

Pe [ i ∈ ē, j ∈

Vke (Xi ) ]

=

n
X

Pe [ i ∈ ē, j ∈ Vke (Xi ) ] −

j=1

=k

X
σi (j)≤k

p
n−1p
p p−1
−k
=k
·
n
n−pn
nn−1

49

Pe [ i ∈ ē, j ∈ Vke (Xi ) ]

Celisse and Mary-Huard

D.2.2 Stone’s lemma
Lemma D.5 (Devroye et al. (1996), Corollary 11.1, p. 171). Given n points (x1 , ..., xn ) in
Rd , any of these points belongs to the k nearest neighbors of at most kγd of the other points,
where γd increases on d.
D.2.3 Stability of the kNN classifier when removing p observations
Lemma D.6 (Devroye and Wagner (1979b), Eq. (14)). For every 1 ≤ k ≤ n, let Ak denote
k-NN classification algorithm defined by Eq. (2.1), and let Z1 , . . . , Zn denote n i.i.d. random
variables such that for every 1 ≤ i ≤ n, Zi = (Xi , Yi ) ∼ P . Then for every 1 ≤ p ≤ n − k,
√
4 p k
P [ Ak (Z1,n ; X) 6= Ak (Z1,n−p ; X) ] ≤ √
,
2π n
where Z1,i = (Z1 , . . . , Zi ) for every 1 ≤ i ≤ n, and (X, Y ) ∼ P is independent of Z1,n .
D.2.4 Exponential concentration inequality for the L1O estimator
Lemma D.7 (Devroye et al. (1996), Theorem 24.4). For every 1 ≤ k ≤ n, let Ak denote
b1 (·) denote the L1O estimator
k-NN classification algorithm defined by Eq. (2.1). Let also R
defined by Eq. (2.2) with p = 1. Then for every ε > 0,



h
i

2
ε
b1 (Ak , Z1,n ) − E R
b1 (Ak , Z1,n ) > ε ≤ 2 exp −n
.
P R
γd2 k 2
D.2.5 Moment upper bounds for the L1O estimator
Lemma D.8. For every 1 ≤ k ≤ n, let Ak denote k-NN classification algorithm defined by
b1 (·) denote the L1O estimator defined by Eq. (2.2) with p = 1. Then
Eq. (2.1). Let also R
for every q ≥ 1,
!

2 q
h
i 2q 
(kγ
)
d
b1 (Ak , Z1,n ) − E R
b1 (Ak , Z1,n )
E R
≤ q! 2
.
(D.8)
n
The proof is straightforward from the combination of Lemmas D.1 and D.7.
D.2.6 Upper bound on the optimal constant in the Rosenthal’s inequality
Lemma D.9. Let N denote a real-valued standard Gaussian random variable. Then for
every q > 2, one has
√ √  q  2q
.
E [ |N |q ] ≤ 2e q
e
Proof of Lemma D.9. If q is even (q = 2k > 2), then
r
Z +∞
Z +∞
2
x2
2
q
q 1
− x2
√
x
xq−2 e− 2 dx
E [ |N | ] = 2
e
dx =
(q − 1)
π
2π
0
r0
r
2 (q − 1)!
2
q!
=
=
·
π 2k−1 (k − 1)!
π 2q/2 (q/2)!
50

Performance of CV to estimate the risk of kNN

Then using for any positive integer a
 a a
 a a
√
√
2πa
< a! < 2eπa
,
e
e
it results
√
q!
<
2e e−q/2 q q/2 ,
q/2
2 (q/2)!
which implies
r  
q
e q q/2 √ √  q  2
E [ |N | ] ≤ 2
< 2e q
·
π e
e
q

If q is odd (q = 2k + 1 > 2), then
r Z +∞
r Z +∞
2
√ q −t dt
2
2
q
q − x2
dx =
2t e √ ,
E [ |N | ] =
x e
π 0
π 0
2t
√
by setting x = 2t. In particular, this implies
r Z +∞
r
r


√ √  q  2q
2
2 k
2 q−1 q − 1
q
k −t
2
E [ |N | ] ≤
.
(2t) e dt =
2 k! =
2
! < 2e q
π 0
π
π
2
e

Lemma D.10. Let S denote a binomial random variable such that S ∼ B(k, 1/2) (k ∈ N∗ ).
Then for every q > 3, it comes
r q
√ √
qk
q
E [ |S − E [ S ]| ] ≤ 4 e q
·
2e
Proof of Lemma D.10. Since S − E(S) is symmetric, it comes
q

Z

+∞

E [ |S − E [ S ]| ] = 2

h

P S < E[S ] − t

1/q

i

+∞

Z

P [ S < E [ S ] − u ] uq−1 du.

dt = 2q

0

0

p
Using Chernoff’s inequality and setting u = k/2v, it results
q

Z

E [ |S − E [ S ]| ] ≤ 2q

+∞

r

2

q−1 − uk

u

e

0

du = 2q

k
2

q

Z

+∞

v q−1 e−

v2
2

dv.

0

If q is even, then q −1 > 2 is odd and the same calculations as in the proof of Lemma D.9
apply, which leads to
r q
r q
r q
r q
 q q/2
√ √
√ √
k q/2  q 
k q/2 √
qk
qk
q
E [ |S − E [ S ]| ] ≤ 2
2
!≤2
2
πeq
= 2 πe q
<4 e q
·
2
2
2
2e
2e
2e
51

Celisse and Mary-Huard

If q is odd, then q − 1 > 2 is even and another use of the calculations in the proof of
Lemma D.9 provides
r q
r q
(q − 1)!
q!
k
k
q
E [ |S − E [ S ]| ] ≤ 2q
=2
q−1
q−1 .
(q−1)/2
(q−1)/2
2 2
2 2
2 !
2 !
Let us notice
q!
2(q−1)/2 q−1
2 !

√
2πeq

≤

q q
e

q q
√ r q
e
= 2e
q − 1  q−1 (q−1)/2

(q−1)/2

p
2(q−1)/2 π(q − 1) q−1
2e
(q−1)/2

r


√
q
q (q+1)/2
q
= 2e
q−1 e
q−1

e

and also that
r

q
q−1



q
q−1

(q−1)/2
≤

√

2e.

This implies
q!
2(q−1)/2 q−1
2 !

≤ 2e

 q (q+1)/2
e

√ √  q q/2
=2 e q
,
e

hence
r
q

E [ |S − E [ S ]| ] ≤ 2

q

√ √
k √ √  q q/2
=4 e q
2 e q
2
e

r

qk
2e

q

·

Lemma D.11. Let X, Y be two i.i.d. random variables with Poisson distribution P(λ)
(λ > 0). Then for every q > 3, it comes
iq/2
√ hq
(2λ + q)
E [ |X − Y |q ] ≤ 2q/2+1 e q
.
e
Proof of Lemma D.11. Let us first remark that
E [ |X − Y |q ] = EN [ E [ |X − Y |q | N ] ] = 2q EN [ E [ |X − N/2|q | N ] ] ,
where N = X + Y . Furthermore, the conditional distribution of X given N = X + Y is a
binomial distribution B(N, 1/2). Then Lemma D.10 provides that
r
q
√ √
qN
q
E [ |X − N/2| | N ] ≤ 4 e q
a.s. ,
2e
which entails that
"
q

q

E [ |X − Y | ] ≤ 2 EN

√ √
4 e q

r

qN
2e

q

52

#

q/2+2 √

=2

√
e q

r

q

h
i
q
EN N q/2 .
e

Performance of CV to estimate the risk of kNN

It only remains to upper bound the last expectation where N is a Poisson random variable
P(2λ) (since X, Y are i.i.d. ):
h
i p
EN N q/2 ≤ EN [ N q ]
by Jensen’s inequality. Further introducing Touchard polynomials and using a classical
upper bound, it comes
v
v
u q
 
 
q
h
i u
X
uX
u
q
1
1 q q−i
q/2
t
t
q−i
i
i
i
≤
q
EN N
≤
(2λ)
(2λ)
2 i
2 i
i=1
i=0
v
r
u q  
u1 X q
−1
1
(2λ)i q q−i =
=t
(2λ + q)q = 2 2 (2λ + q)q/2 .
i
2
2
i=0

Finally, one concludes
q

E [ |X − Y | ] ≤ 2

q/2+2 √

√
e q

r

q

iq/2
q −1
√ hq
2 2 (2λ + q)q/2 < 2q/2+1 e q
(2λ + q)
.
e
e

53

