On Ranking and Generalization Bounds

Wojciech Rejchel.

Year: 2012, Volume: 13, Issue: 46, Pages: 1373−1392


The problem of ranking is to predict or to guess the ordering between objects on the basis of their observed features. In this paper we consider ranking estimators that minimize the empirical convex risk. We prove generalization bounds for the excess risk of such estimators with rates that are faster than 1/√n. We apply our results to commonly used ranking algorithms, for instance boosting or support vector machines. Moreover, we study the performance of considered estimators on real data sets.