Top Rank Optimization in Linear Time
This work addresses the computational bottleneck in bipartite ranking for applications requiring fast and accurate top-ranked predictions, offering a significant speed improvement.
The paper tackles the problem of bipartite ranking with a focus on top-ranked instances, proposing the TopPush approach that achieves linear-time computational complexity and is 10-100 times faster than state-of-the-art methods while maintaining competitive accuracy.
Bipartite ranking aims to learn a real-valued ranking function that orders positive instances before negative instances. Recent efforts of bipartite ranking are focused on optimizing ranking accuracy at the top of the ranked list. Most existing approaches are either to optimize task specific metrics or to extend the ranking loss by emphasizing more on the error associated with the top ranked instances, leading to a high computational cost that is super-linear in the number of training instances. We propose a highly efficient approach, titled TopPush, for optimizing accuracy at the top that has computational complexity linear in the number of training instances. We present a novel analysis that bounds the generalization error for the top ranked instances for the proposed approach. Empirical study shows that the proposed approach is highly competitive to the state-of-the-art approaches and is 10-100 times faster.