DISTRIBUTION-FREE INEQUALITIES FOR THE DELETED AND HOLDOUT ERROR ESTIMATES

In the discrimination problem the random variable θ, known to take values in {1,..,M}, is estimated from the random vector X taking values in Rd. All that is known about the joint distribution of (X, θ) is that which can be inferred from a sample (X1, θ 1)…, (Xn, θn) of size n drawn from that distribution. A discrimination rule is any procedure which determines a decision θ for θ from X and (X1, θ 1),…,(Xn, θ n). The rule is called k-local if the decision θ depends only on X and the pairs (Xi, θ i), for which Xi is one of the k closest to X from Xi,…, Xn. If Ln denotes the probability of error for a k-local rule given the sample, then estimates Ln, of Lnare determined for which exp (– Bn), where A and B are positive constants depending only on d, M, and ∊. © 1979 IEEE