Preprint #98-8
MINIMAX NONPARAMETRIC CLASSIFICATION -
PART I: RATES OF CONVERGENCE
by
Yuhong Yang
Iowa State University
ABSTRACT
This paper studies nonparametric classification under minimax considerations.
We first study the problem of minimax estimation of the conditional probability
of class label taking a value, say 1 in the label set {0,1} given the feature
variable. This function, say f , is assumed to be in a general nonparametric
class. We show the minimax rate of convergence under square L sub 2 loss
is determined by the massiveness of the class as measured by metric entropy.
The second part of the paper studies minimax capability of classification.
The loss of interest is the difference between the probability of misclassification
of a classifier and that of the Bayes decision. As well-known, an upper
bound on risk for estimating f gives an upper bound on the risk
for classification, but the rate is known to be suboptimal for the class
of monotone functions. This suggests that one does not have to estimate
f well in order to classify well. However, we show that the two
problems are in fact of the same difficulty in terms of rates of convergence
under a sufficient condition, which is satisfied by many function classes
including Besov (Sobolev), Lipschitz, bounded variation. This is somewhat
surprising compared with a result of Devroye, Gyorfi, and Lugosi (1996).
Index Terms-Conditional probability estimation, mean error probability
regret, metric entropy, minimax rates of convergence, nonparametric classification,
neural network classes, sparse approximation.
Copies of preprints are available from the author upon request.
Use the preprint number (located at the top of the page) and make
the request directly to the author, Iowa State University, Department
of Statistics, Snedecor Hall, Ames, IA 50011-1210.