Optimal Exponential Bounds on the Accuracy of Classification

Consider a standard binary classification problem, in which (X,Y) is a random couple in X × {0,1}, and the training data consist of n i.i.d. copies of (X,Y). Given a binary classifier f:X {mapping} {0,1}, the generalization error of f is defined by R(f) = ℙ{Y ≠ f(X)}. Its minimum R^* over all binary classifiers f is called the Bayes risk and is attained at a Bayes classifier. The performance of any binary classifier f̂_n based on the training data is characterized by the excess risk R(f̂_n)-R^*. We study Bahadur's type exponential bounds on the following minimax accuracy confidence function based on the excess risk: (Formula presented.) where the supremum is taken over all distributions P of (X,Y) from a given class of distributions M and the infimum is over all binary classifiers f̂_n based on the training data. We study how this quantity depends on the complexity of the class of distributions M characterized by exponents of entropies of the class of regression functions or of the class of Bayes classifiers corresponding to the distributions from M. We also study its dependence on margin parameters of the classification problem. In particular, we show that, in the case when X = [0,1]^d and M is the class of all distributions satisfying the margin condition with exponent α > 0 and such that the regression function η belongs to a given Hölder class of smoothness β > 0, (Formula presented.) for some constants D, λ₀ > 0.