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 ^d. Ali that is known about the joint distribution of (X, O) 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₍, ₍). The 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₍. If L₍ denotes the probability of error for a k -local rule given the sample, then estimates L₍ of L₍, are determined for which P | L₍ - L₍ (- Bn), where A and B are positive constants depending only on d, M, and.