Timezone: »

 
Poster
Top Rank Optimization in Linear Time
Nan Li · Rong Jin · Zhi-Hua Zhou

Mon Dec 08 04:00 PM -- 08:59 PM (PST) @ Level 2, room 210D
in Poster Session and Reception »

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 rank 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.

[ PDF] 

Author Information

Nan Li (Alibaba Group)
Rong Jin (Michigan State University (MSU))
Zhi-Hua Zhou (Nanjing University)

More from the Same Authors