Risk Bounds for Low Cost Bipartite Ranking
This addresses efficiency issues for practitioners in machine learning dealing with large-scale bipartite ranking tasks, though it is incremental as it builds on existing loss structures.
The paper tackles the high computational cost of bipartite ranking by proposing a stochastic algorithm that avoids quadratic sample dependence, achieving competitive performance with significant speed gains compared to batch methods.
Bipartite ranking is an important supervised learning problem; however, unlike regression or classification, it has a quadratic dependence on the number of samples. To circumvent the prohibitive sample cost, many recent work focus on stochastic gradient-based methods. In this paper we consider an alternative approach, which leverages the structure of the widely-adopted pairwise squared loss, to obtain a stochastic and low cost algorithm that does not require stochastic gradients or learning rates. Using a novel uniform risk bound---based on matrix and vector concentration inequalities---we show that the sample size required for competitive performance against the all-pairs batch algorithm does not have a quadratic dependence. Generalization bounds for both the batch and low cost stochastic algorithms are presented. Experimental results show significant speed gain against the batch algorithm, as well as competitive performance against state-of-the-art bipartite ranking algorithms on real datasets.