  The problem of ranking/ordering instances, instead of simply classifying
them, has recently gained much attention in machine learning. In this paper we
formulate the ranking problem in a rigorous statistical framework. The goal is
to learn a ranking rule for deciding, among two instances, which one is
"better," with minimum ranking risk. Since the natural estimates of the risk
are of the form of a U-statistic, results of the theory of U-processes are
required for investigating the consistency of empirical risk minimizers. We
establish in particular a tail inequality for degenerate U-processes, and apply
it for showing that fast rates of convergence may be achieved under specific
noise assumptions, just like in classification. Convex risk minimization
methods are also studied.
