A Finite Sample Distribution-Free Performance Bound for Local Discrimination Rules

In the discrimination problem the random variable, known to take values in \1, , M\, is estimated from the random vector X. All that is known about the joint distribution of (X, ) is that which can be inferred from a sample (X₁, ₁), , (Xₙ, ₙ) of size n drawn from that distribution. A discrimination rule is any procedure which determines a decision for from X and (X₁, ₁), , (Xₙ, ₙ). A rule is called k-local if the decision depends only on X and the pairs (Xᵢ, ᵢ) for which Xᵢ is one of the k-closest to X from X₁, , Xₙ. It is shown that for any k-local discrimination rule, the mean-square difference between the probability of error for the rule and its deleted estimate is bounded by A/n where A is an explicitly given small constant which depends only on M and k. Thus distribution-free confidence intervals can be placed about probability of error estimates for k-local discrimination rules.