Lower bounds for the rate of convergence in nonparametric pattern recognition.
We show that there exist individual lower bounds corresponding to the upper bounds for the rate of convergence of nonparametric pattern recognition which are arbitrarily close to Yang's minimax lower bounds, for certain "cubic" classes of regression functions used by Stone and others. The rates are equal to the ones of the corresponding regression function estimation problem. Thus for these classes classification is not easier than regression function estimation.
Introduction
),. be independent identically distributed R d  f0; 1g-valued
random variables. In pattern recognition (or classication) one wishes to decide whether the
value of Y (the label) is 0 or 1 given the (d-dimensional) value of X (the observation), that
is, one wants to nd a decision function g dened on the range of X taking values 0 or 1 so
that g(X) equals to Y with high probability. Assume that the main aim of the analysis is
to minimize the probability of error :
xg be the a posteriori probability (or regression)
function. Introduce the Bayes-decision
and let
be the Bayes-error. Denote the distribution of X by . Introduce kfk q
R
d) 1=q .
It is well-known (see Devroye, Gyor and Lugosi [8]), that for each measurable function
the relation
Z      1    I fg 6=g  g d (2)
holds, where I A denotes the indicator function of the event A. Therefore the function g
achieves the minimum in (1) and the minimum is L  .
In the classication problem we consider here, the distribution of (X; Y ) (and therefore
also  and g  ) is unknown. Given only the independent sample D
of the distribution of (X; Y ), one wants to construct a decision rule
(R d  f0; 1g) n 7! f0; 1g
such that
is close to L  . In this paper we study asymptotic properties of EL n L  .
If we have an estimate  n of the regression function  and we derive a plug-in rule g n
from  n quite naturally by
then from (2) we get easily
(see [8]). This shows that if k in the same sense, and the
latter has at least the same rate, that is, in a sense, classication is not more complex than
regression function estimation.
It is well-known, that there exist regression function estimates, and so classication rules,
which are universally consistent, that is, which satisfy
for all distributions of (X; Y ). This was rst shown in Stone [14] for nearest neighbor
estimates (see also [8] for a list of references).
Classication is actually easier than regression function estimation in the sense that if
then for the plug-in rule
(see [8] Chapter 6), that is, the relative expected error of g n decreases faster than the expected
error of  n . Moreover, if k then for the plug-in rule
(see Antos [1]), that is, the relation also holds for strong consistency. However the value of
the ratio above cannot be universally bounded, the convergence can be arbitrary slow. It
depends on the behavior of  near 1=2 and the rate of convergence of f n g.
Unfortunately, there do not exist rules for which EL n L  tends to zero with a guaranteed
rate of convergence for all distributions of (X; Y ). Theorem 7.2 and Problem 7.2 in Devroye
et al. [8] imply the following slow-rate-of-convergence result: Let fa n g be a positive sequence
converging to zero with 1=16  a 1  a :. For every sequence fg n g of decision rules,
there exists a distribution of (X; Y ), such that X is uniformly distributed on [0; 1],  2 f0; 1g
for all n.
Therefore, in order to obtain nontrivial rate-of-convergence results, one has to restrict
the class of distributions. Then it is natural to ask what the fastest achievable rate is for a
given class of distributions. This is usually done by considering minimax rate-of-convergence
results, where one derives lower bounds according to the following denition.
Denition 1 A positive sequence fa n g is called lower rate of convergence for a class
D of distributions of (X; Y ) if
lim sup
sup
(X;Y )2D
a n
Remark. In many cases the limit superior in this denition could be replaced by limit
inferior or inmum, because the lower bound for the minimax loss holds for all (su-ciently
large) n.
Since  and  determine the distribution of (X; Y ), the class D of distributions is often
given as a product of a class H of allowed distributions of X and a class F of allowed
regression functions. For example, H may consist of all absolute continuous distributions,
or all distributions (distribution-free approach), or one particular distribution (distribution-
sensitive approach).
In this paper we give lower bounds for some classes D  in the last (and strongest) for-
mat, when H contains one (uniform) distribution, and class of
functions (with a parameter ), dened later. For minimax lower-rate results on other types
of distribution classes (e.g., Vapnik-Chervonenkis classes), see Devroye et al. [8] and the
references therein. For related results on the general minimax theory of statistical estimates
see Ibragimov and Khasmiskii [9], [10], [11], Korostelev and Tsybakov [12].
Yang [16] points out that while (3) holds for every xed distribution for which f n g is
consistent, the optimal rate of convergence for many usual classes is the same in classication
and regression function estimation. He shows many examples and some counterexamples to
this phenomenon with rates of convergence in terms of metric entropy. Classication seems
to have the same complexity as regression function estimation for classes which are rich near
1=2. (See also Mammen and Tsybakov [13].)
For example, it was shown in Yang [16] that for the distribution classes D  above, the
optimal rate of convergence is fn
2+d g, the same as for regression function estimation (see
also Stone [15]).
In some sense, such lower bounds are not satisfactory. They do not tell us anything about
the way the probability of error decreases as the sample size is increased for a given classi-
cation problem. These bounds, for each n, give information about the maximal probability
of error within the class, but not about the behavior of the probability of error for a single
xed distribution as the sample size n increases. In other words, the \bad" distribution,
causing the largest probability of error for a decision rule, may be dierent for each n. For
example, the previous lower bounds for the classes D  does not exclude the possibility that
there exists a sequence fg n g such that for every distribution in D  , the expected probability
of error EL n L  decreases at an exponential rate in n.
In this paper, we are interested also in \individual" minimax lower bounds that describe
the behavior of the probability of error for a xed distribution (X; Y ) as the sample size n
grows.
Denition 2 A positive sequence fa n g is called individual lower rate of convergence
for a class D of distributions of (X; Y ) if
fgng
sup
(X;Y )2D
lim sup
a n
where the inmum is taken over all sequences fg n g of decision rules.
The concept of individual lower rate has been introduced in Birge [7] concerning density
estimation. For individual lower-rate results concerning pattern recognition see Antos and
We will show that for every sequence fb n g tending to zero, fb n n
2+d g is an individual
lower rate of convergence for the classes D  . Hence there exist individual lower rates of
these classes, which are arbitrarily close to the optimal lower rates. These rates are the same
as the individual lower rates for the expected L 2 () error of regression function estimation
for these classes (see also Antos, Gyor and Kohler [4] and Antos [3]). Both for regression
function estimation and pattern recognition, the individual lower rates are optimal, hence
we extend Yang's observation for the individual rates for these classes.
Our results also imply that the ratio ELn L
can tend to zero arbitrary slowly (even
for a xed sequence f n g).
Next we give the denitions of the function classes, for which we derive lower rates of
convergence. Let and denote the L q norm regarding to
the Lebesgue-measure  on R d by k  k Lq () .
Denition 3 For given 1  q  1, R 2
be the class of functions f
such that for R
d ) with
kD
moreover, for every such
with
kD
where D
denotes the partial derivative with respect to
For q < 1, we assume R  1. For all the rate-of-convergence results below hold if
some of M 0 ,. ,MR 1 are innite, that is, if we omit some of the conditions of the rst kind.
These classes are generalizations of the Lipschitz classes of Example 2 in Yang [16], Antos,
Gyor and Kohler [4], Birge [7] and Stone [15], and also generalizations of a special case of
Example 4 in Yang [16] for polinomial modulus of continuity.
Denition 4 For given ~
and M > 0, let V
M) be the class of functions f
such that kfk1  M and for - > 0
where
R

R
r
and e i is the i th unit vector in R d .
These classes are just Example 5 in Yang [16]. We assume that M;M 0 > 1=2.
Denition 5 Denote one of the classes Lip ;d and V ;d by F  . Let D  be the class of
distributions of (X; Y ) such that
(i) X is uniformly distributed on [0; 1] d ,
It is well-known, that there exist regression function estimates f n g, which satisfy
lim sup
sup
(X;Y )2D
+d
(see, e.g., [16] and Barron, Birge and Massart [6]). (This remains true replacing condition (i)
in Denition 5, e.g., with the assumption that  is in a class of distributions with uniformly
bounded density funtions. Note that the rate depends only on  and d.) Thus for the plug-in
rules fg n g
lim sup
sup
(X;Y )2D
2+d
that is, sup (X;Y )2D  (EL n L
2+d
. (The rate n
2+d might be formulated as
d=, the exponent of dimension is just the exponent of 1= in the -metric
entropy of the classes, see [7].)
To handle the two types of classes together, let ~ for the
classes Lip ;d . Thus
holds in all cases. (We may call  as the exponent of global smoothness following [7].)
Now we give conditions for a general function class F  , which assure lower rates of
convergence for the corresponding distribution class D  . A subclass of regression functions
will be indexed by the vectors
of +1 or 1 components, where are introduced below. Denote the set of all such
vectors by C. Let  be the uniform distribution on [0; 1] d .
Assumption 1 With some ~
and  satisfying (6), for any probability distribution fp j g
for every j 2 N , there is a function with support on the brick I
, such that
these are disjoint even for dierent j and j 0 , and for every c 2 C,
(c)
(which are independent of fp j g and j).
Note that
by (6).
Theorem 1 If Assumption 1 holds for a function class F  , then the sequence
a
+d
is a lower rate of convergence for the corresponding distribution class D  .
Assumption 1 is similar to A'2(k) in Birge [7]. In this form, it will be required only for
the individual lower rates. It seems from the proof (choice of fp j g) that for the minimax
rates above, we only use the weaker form:
Assumption 2 With some ~
and  satisfying (6), for any  2 (0; 1], there is a function
with support on the brick I = I
in [0; 1] d , such that for every
(c)
r
Also km  k 2
This is almost the same as Assumption 3 in Yang [16] and A2(k) in Birge [7] in case of
polinomial metric entropy, and Theorem 1 is analogous to Yang's Theorem 2. Both Yang's
and our theorems give as a special case:
Corollary 1 If F  is Lip ;d or V ;d , then the sequence
a
2+d
is a lower rate of convergence for the class D  .
Our main result is the following extention of Theorem 1 to individual lower rates (see
Antos [2] for Lip ;d if
Theorem 2 Let fb n g be an arbitrary positive sequence tending to zero. If Assumption 1
holds for a function class F  , then the sequence
b n a
2+d
is an individual lower rate of convergence for the corresponding distribution class D  .
Remark 1. Applying for the sequence f
b n g, Theorem 2 implies that for all fg n g there is
such that
lim sup
b n a n
Remark 2. Certainly Theorems 1 and 2 hold if we increase the class by leaving condition (i)
from Denition 5.
Focusing again on the classes Lip ;d and
Corollary 2 Let fb n g be an arbitrary positive sequence tending to zero. If F  is Lip ;d or
then the sequence
b n a
2+d
is an individual lower rate of convergence for the class D  .
Call a sequence fc n g an upper rate of convergence for a class D, if there exist rules fg n g
which satisfy
lim sup
sup
(X;Y )2D
that is, sup (X;Y )2D (EL n L  it an individual upper rate of convergence
for a class D, if there exist rules fg n g which satisfy
sup
(X;Y )2D
lim sup
This implies only that for every distribution in D, EL n L possibly with dierent
constants. Then (5) implies that n
2+d is an upper rate of convergence, and thus also an
individual upper rate of convergence for D  . While Theorem 1 shows only that there is no
upper rate of convergence for D  better than n
, it follows from Theorem 2 that n
d
is even the optimal individual upper rate for D  in the sense, that there doesn't exist an
individual upper rate c n of convergence for D  , which satises
lim
Moreover (3) and (4) imply
fgng
sup
(X;Y )2D
lim sup
which shows that Theorem 2 cannot be improved by dropping b n . This shows the strange
nature of individual lower bounds, that while every sequence tending to zero faster than
2+d is an individual lower rate for D  , n
2+d itself is not that.
3 Proofs
The proofs of the theorems apply the following lemma:
l-dimensional real vector taking values in [ 1=4; 1=4] l ,
let C be a zero mean random variable taking values in f1;+1g, and let Y l be inde-
pedent binary variables given C with
Then for the error probability of the Bayes decision for C based on ~
Proof. The Bayes decision is 1 if
Y
Y
(see [8]). One can verify that
where
Y
I fY i =1g +2
I fY i =0g
Y
where
For arbitrary 0 < q < 1=2,   q if and only if j log T j  log 1 q
By Markov's inequality
log 1 q
Moreover because of j log T
, we get
log T
Using the inequality for 1=4  x  1=4
on the one hand
and on the other hand
so
Hence
log T jg
Thus
Efg  q@ 1 Efj log T jg
log 1 q
qA  q@ 1q P
log 1 q
By choosing
Proof of Theorem 1. The method of this proof diers from that of Yang, it can be easily
modied to individual lower bound in Theorem 2. Assumption 1 and 0   (c)  1 imply
that each distribution (X; Y ) with X  Unif[0; 1] d , Y 2 f0; 1g and EfY
for all x 2 [0; 1] d for some c 2 C is contained in D  , which implies
lim sup
gn
sup
(X;Y )2D
a n
lim sup
sup
(X;Y ):XUnif[0;1] d ;EfY jX=xg= (c) (x);c2C
a n
Let g n be an arbitrary rule. By denition, fI A j;k =2 : j; kg is an orthogonal system in
for the measure
R
A
therefore the projection ^
of g
is given
by
I A j;k (x)
where
R (g n 1=2)I A j;k =2 d
R
I A j;k =2
d
R
A j;k
R
A j;k
R
A j;k
R
A j;k
R
A j;k
R
A j;k
(Note that ^
arbitrary. Note that g  = 1+
I A j;k. Then
by (2)
Z      (c) 1    I fgn 6=g  g d
Z
d
Z
d

KX
Let ~
c n;j;k be otherwise. Because of j^c n;j;k c j;k j  I f~c n;j;k 6=c j;k g , we get
I f~c n;j;k 6=c j;k g p +d
This proves
where
Equations (8) and imply
lim sup
gn
sup
(X;Y )2D (;M)
a n
K
gn
sup
a n
To bound the last term, we x the rules fg n g and choose c 2 C randomly. Let
be a sequence of independent identically distributed random variables independent of X 1 ,
. , which satisfy PfC 1=2. Next we derive a lower bound
for
The sign ~ c n;j;k can be interpreted as a decision on C j;k using D n . Its error probability is
minimal for the Bayes decision
C n;j;k , which is 1 if PfC
therefore
l be those X i 2 A j;k . Then given
distributed as
in the conditions of Lemma 1 with u
depends only on C n fC j;k g and on X r 's with r 62 fi therefore is independent of
Now conditioning on X the error of the conditional Bayes
decision for C j;k based on (Y depends only on (Y
Pf
By Jensen-inequality
Pf
1e 10E
K1np 2+d
independently of k. Thus if np 2+d
Pf
and
where
2+d for j  n 1
2+d ,
2+d cn +1
so
lim sup
sup
a n
lim sup
a n
This together with (11) implies the assertion. 2
Proof of Theorem 2. We use the notations and results of the proof of Theorem 1. Now
we have by
fgng
sup
(X;Y )2D
lim sup
b n a n
K
fgng
sup
lim sup
b n a n
In this case we have to choose fp j g independently from n. Since b n and a n tend to zero, we
can take a subsequence fn t g t2N of fng n2N with b n t  2 t and a 1=
that
a 1=
and choose fp j g as
where q t is repeated 2 t =q t times. So
t:d2 t a 1=
a 1=
t:an t an
a 1=

a 1=
by a 1=
specially for
ER ns (C)  K 3
ts
b ns a ns : (15)
We nish the proof in the spirit of Lemma 1 in Antos and Lugosi [5]. Using (15) one gets
fgng
sup
lim sup
b n a n
fgng
sup
lim sup
R ns (c)
b ns a ns
K 3
fgng
sup
lim sup
R ns (c)
ER ns (C)
K 3
fgng

lim sup
R ns (C)
ER ns (C)
Because of (12) and the fact that for all c 2 C
the sequence fR ns (C)=ER ns (C)g is uniformly bounded, so we can apply Fatou's lemma to
get
fgng
sup
lim sup
b n a n
K 3
fgng
lim sup

R ns (C)
ER ns (C)
This together with (14) implies the assertion. 2
Proof of Corollary 1 and 2. We must prove that the classes Lip ;d and V ;d satisfy
Assumption 1. The parameters ~  and  are given as in the text satisfying (6). For any fp j g,
we give the required functions m j and sets A j;k .
First we pack the disjoint sets A j;k into [0; 1] d in the following way: Assume for simplicity,
that not, then the index of the minimal  i takes the role of the rst
dimension in the construction below.) For a given fp j g, let fB j g be a partition of [0; 1] such
that B j is an interval of length p j . We pack disjoint translates of I j into the brick
This gives
Y
and since, for x  1, bxc  x=2 and p j
d
Y
d
Y
where
Let  be the uniform distribution on [0; 1] d and Choose a function
1=4] such that
(I) the support of m is a subset of [0; 1] d ,
denotes a diagonal matrix. Thus m j is a contraction of m from [0; 1] d to
I j . Now we have km
2 and
We only have to check that because of (III), for every c 2 C,
(c)
Case F
Note that the functions m j;k have disjoint support, and this holds also for their derivatives.
If q < 1, then for R
q
thus
For
with
kD
(c) k q
c j;k D
kD
Moreover, for every
with
kD
(c)
(c) (x)k Lq
c j;k  - D
c j;k  - D
c j;k  - D
We can choose m such that its support is in [1=3; 2=3] d . Now if k-k < p j =3 then the support
of  - D
m j;k is in A j;k , hence they are disjoint. Thus for the rst term, with M
c j;k  - D
For the second term,
c j;k  - D
c j;k D
c j;k D
c j;k D
c j;k D
c j;k D
kD
This gives
kD
(c)
If . For R
with P d
kD
c j;k D
kD
Moreover, for every - 2 R d , introduce x 0 and x 00 as a function of x the following way: If x
and x+ - fall in the same A j;k , then let x dierent bricks,
then consider the segment x(x + -), and let x 0 and x 00 be the intersections of this segment
and the borders of the bricks x and x vanishing
outside A j;k , any of its partial derivatives (up to order R) is zero on the border of A j;k , thus
in both case D
(c)
(c)
with
kD
(c)
(c) (x)k 1
(c)
(c)
(c)
(c) (x)k 1
kD
(c)
(c) (x 00
(c)
(c)
Using the fact that x and x 0 are in the same brick, and so the support of D
j;k (x) is in A j;k , for the second term
kD
(c)
(c)
c j;k (D
kp  R
(D
sup
We get the same bound similarly for the rst term, which gives
kD
(c)
(See also [15], p. 1045.)
Case F
Now k (c) k1
c j;k  R i
c j;k  R i
c j;k  R i
We can choose m such that its support is in [1=2; 1] d . Now, if R i - <
then the support
of  R i
i;- m j;k is in A j;k , hence they are disjoint. For the rst term, with M
c j;k  R i
For the second term,
c j;k  R i

c j;k

r


r
(R

r
(R

r



(R


This gives



--R


Lower bounds on the rate of convergence of nonparametric pattern recog- nition
Performance limits of nonparametric estimators.

Strong minimax lower bounds for learning.



On nonparametric estimation of regression.
Statistical Estimation: Asymptotic Theory.
On the bounds for quality of nonparametric
Minimax Theory of Image Reconstruction.
Smooth discrimination analysis.
Consistent nonparametric regression.
Optimal global rates of convergence for nonparametric regression.
Minimax nonparametric classi
--TR
Characterizing rational versus exponential learning curves
Strong Minimax Lower Bounds for Learning
MiniMax Methods for Image Reconstruction
Lower Bounds on the Rate of Convergence of Nonparametric Pattern Recognition
nonparametric pattern recognition;individual rates of convergence