A practical test set bound for rank learning

In a world of exponentially growing data and finite computing resources, rank learning methods can play a critical role in data prioritization. While a number of new rank learning algorithms have been developed, there is a relative paucity of work to generate bounds that characterize the performance of these algorithms. When such bounds have been developed, it has often proved difficult to apply them in real-world settings. In this paper, we develop a new performance bound based on a novel application of the test set bound to rank learning. This bound can be applied to any ranking algorithm. We conduct experiments using data from the Web30K set and report results that demonstrate the tightness and validity of the test set bound for this type of application. We provide a discussion of its use for model selection as well as for comparing algorithmic performance.