A Uniform Convergence Bound for the Area Under the ROC Curve

Shivani Agarwal,
Sariel Har-Peled
and Dan Roth

The area under the ROC curve (AUC) has been advocated as an
evaluation criterion for the bipartite ranking problem. We study
uniform convergence properties of the AUC; in particular, we
derive a distribution-free uniform convergence bound for the AUC
which serves to bound the expected accuracy of a learned ranking
function in terms of its empirical AUC on the training sequence
from which it is learned. Our bound is expressed in terms of a
new set of combinatorial parameters that we term the
\emph{bipartite rank-shatter coefficients}; these play the same
role in our result as do the standard VC-dimension related shatter
coefficients (also known as the growth function) in uniform
convergence results for the classification error rate. A
comparison of our result with a recent uniform convergence result
derived by Freund et al.\ \cite{FreundIyScSi03} for a quantity
closely related to the AUC shows that the bound provided by our
result can be considerably tighter.