Distribution-free inequalities for the deleted and holdout error estimates

In the discrimination problem the random variable \theta, known to take values in {1,\ldots,M} , is estimated from the random vector X taking values in {\bfR}^{d} .

Abstract

In the discrimination problem the random variable \theta , known to take values in {1 ,\ldots ,M} , is estimated from the random vector X taking values in {\bfR}^{d} . Ali that is known about the joint distribution of (X,O) is that which can be inferred from a sample (X_{1} , \theta_{1}, \ldots , (X_{n}, \theta_{n}) of size n drawn from that distribution. A discrimination rule is any procedure which determines a decision \hat{\theta} for \theta from X and (X_{1},\theta_{1}) , \ldots , (X_{n}, \theta_{n}) . The rule is called k -local if the decision \hat{\theta} depends only on X and the pairs (X_{i}, \theta_{i}) ,for which X_{i} is one of the k closest to X from X_{1} , \ldots ,X_{n} . If L_{n} denotes the probability of error for a k -local rule given the sample, then estimates \hat{L}_{n} of L_{n} , are determined for which P {| \hat{L}_{n} - L_{n} \geq \epsilon} \exp (- Bn) , where A and B are positive constants depending only on d , M , and \epsilon .