A necessary and sufficient condition for convergence of error probability estimates in k-nn discrimination (Q1082016)

Let \((X,\theta)\) be an \(R^ d\times \{1,...,s\}\) valued random vector, \((X_ j,\theta_ j)\), \(j=1,...,n\), be its observed values, \(\theta_{nj}^{(k)}\) be the k-nearest neighbor estimate of \(\theta_ j\), \(R^{(k)}\) be the limit of error probability and \(\hat R_{nk}\triangleq (1/n)\sum^{n}_{j=1}I_{(\theta_ j\neq \theta_{nj}^{(k)})}\) be the error probability estimate. It is shown that for every \(\epsilon >0\), there are constants \(a>0\), \(c<\infty\) such that \[ P(| \hat R_{nk}-R^{(k)}| >\epsilon)<ce^{-an} \] if and only if there is no unregular atom of (X,\(\theta)\) and the various concepts of convergence of \(\hat R{}_{nk}\) to \(R^{(k)}\) are equivalent.