Asymptotically Efficient Solutions to the Classification Problem

Abstract

We study a class of decision rules based on an adaptive partitioning of an Euclidean observation space. The class of partitions has a computationally attractive form, and the related decision rule is invariant under strictly monotone transformations of coordinate axes. We provide sufficient conditions that a sequence of decision rules be asymptotically Bayes risk efficient as sample size increases. The sufficient conditions involve no regularity assumptions on the underlying parent distributions.