Optimal Exponential Bounds on the Accuracy of Classification

COUV_CAHIER_EGND_A31by G. Kerkyacharian, A. B. Tsybakov, V. Temlyakov, D. Picard & V. Koltchinskii

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 → {0, 1}, the generalization error of f is defined by R( f ) = P{Y = f (X)}. Its minimum R∗ over all binary classifiers f is called the Bayes risk and is attained at aBayes classifier. The performance of any binary classifier fˆn based on the training data is characterized by the excess risk R(fn) − R*.We study Bahadur’s type exponential bounds on the following minimax accuracy confidence function based on the excess risk: (…)

Download the paper