Distribution-free performance bounds for potential function rules

Publisher Website
Google Scholar
Abstract
In the discrimination problem the random variable\theta, known to take values in{1, \cdots ,M}, is estimated from the random vectorX. All that is known about the joint distribution of(X, \theta)is that which can be inferred from a sample(X_{1}, \theta_{1}), \cdots ,(X_{n}, \theta_{n})of sizendrawn from that distribution. A discrimination nde is any procedure which determines a decision\hat{ \theta}for\thetafromXand(X_{1}, \theta_{1}) , \cdots , (X_{n}, \theta_{n}). For rules which are determined by potential functions it is shown that the mean-square difference between the probability of error for the nde and its deleted estimate is bounded byA/ \sqrt{n}whereAis an explicitly given constant depending only onMand the potential function. TheO(n ^{-1/2})behavior is shown to be the best possible for one of the most commonly encountered rules of this type.