Ranking and Empirical Minimization of U-statistics

Stéphan Clémençon, Gábor Lugosi, Nicolas Vayatis

The Annals of Statistics · 2008 · Volume 36 · Issue 2

Abstract

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.

Keywords

60C05, 60E15, 60G25, 68Q32, convex risk minimization, fast rates, Moment inequalities, Statistical learning, theory of classification, U-processes, VC classes

Enable JavaScript for citation tools and additional paper interactions.