On Sample Complexity Upper and Lower Bounds for Exact Ranking from Noisy Comparisons
This work addresses the challenge of efficiently ranking items from noisy data for applications like recommendation systems, but it is incremental as it builds on prior ranking literature with broader assumptions.
The paper tackles the problem of exact ranking from noisy comparisons with minimal assumptions, deriving lower bounds and proposing nearly optimal algorithms for both pairwise and listwise ranking, showing improvements against state-of-the-art methods in numerical results.
This paper studies the problem of finding the exact ranking from noisy comparisons. A comparison over a set of $m$ items produces a noisy outcome about the most preferred item, and reveals some information about the ranking. By repeatedly and adaptively choosing items to compare, we want to fully rank the items with a certain confidence, and use as few comparisons as possible. Different from most previous works, in this paper, we have three main novelties: (i) compared to prior works, our upper bounds (algorithms) and lower bounds on the sample complexity (aka number of comparisons) require the minimal assumptions on the instances, and are not restricted to specific models; (ii) we give lower bounds and upper bounds on instances with unequal noise levels; and (iii) this paper aims at the exact ranking without knowledge on the instances, while most of the previous works either focus on approximate rankings or study exact ranking but require prior knowledge. We first derive lower bounds for pairwise ranking (i.e., compare two items each time), and then propose (nearly) optimal pairwise ranking algorithms. We further make extensions to listwise ranking (i.e., comparing multiple items each time). Numerical results also show our improvements against the state of the art.