Timezone: »

 
Poster
Active Ranking without Strong Stochastic Transitivity
Hao Lou · Tao Jin · Yue Wu · Pan Xu · Quanquan Gu · Farzad Farnoud

Tue Nov 29 09:00 AM -- 11:00 AM (PST) @ Hall J #326
in Poster Session 1 »
Ranking from noisy comparisons is of great practical interest in machine learning. In this paper, we consider the problem of recovering the exact full ranking for a list of items under ranking models that do *not* assume the Strong Stochastic Transitivity property. We propose a $$\delta$$-correct algorithm, Probe-Rank, that actively learns the ranking of the items from noisy pairwise comparisons. We prove a sample complexity upper bound for Probe-Rank, which only depends on the preference probabilities between items that are adjacent in the true ranking. This improves upon existing sample complexity results that depend on the preference probabilities for all pairs of items. Probe-Rank thus outperforms existing methods over a large collection of instances that do not satisfy Strong Stochastic Transitivity. Thorough numerical experiments in various settings are conducted, demonstrating that Probe-Rank is significantly more sample-efficient than the state-of-the-art active ranking method.
Keywords: Sample Complexity · ranking · noisy comparison · SST · WST
[ Paper]  [ Poster]  [ OpenReview] 

Author Information

Hao Lou (University of Virginia)
Tao Jin (University of Virginia)
Yue Wu (University of California, Los Angeles)
Pan Xu (Duke University)
Quanquan Gu (UCLA)
Farzad Farnoud (University of Virginia)

More from the Same Authors