Timezone: »
Poster
On Sample Complexity Upper and Lower Bounds for Exact Ranking from Noisy Comparisons
Wenbo Ren · Jia (Kevin) Liu · Ness Shroff
Wed Dec 11 05:00 PM -- 07:00 PM (PST) @ East Exhibition Hall B + C #58
This paper studies the problem of finding the exact ranking from noisy comparisons. A noisy 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 \textit{unequal} noise levels; and (iii) this paper aims at the \textit{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) \textit{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.
Author Information
Wenbo Ren (The Ohio State University)
Jia (Kevin) Liu (Iowa State University)
Ness Shroff (The Ohio State University)
More from the Same Authors
-
2022 : Conditional Moment Alignment for Improved Generalization in Federated Learning »
Jayanth Reddy Regatti · Songtao Lu · Abhishek Gupta · Ness Shroff -
2022 Poster: Provably Efficient Model-Free Constrained RL with Linear Function Approximation »
Arnob Ghosh · Xingyu Zhou · Ness Shroff -
2022 Poster: On the Generalization Power of the Overfitted Three-Layer Neural Tangent Kernel Model »
Peizhong Ju · Xiaojun Lin · Ness Shroff -
2021 Poster: Sample Complexity Bounds for Active Ranking from Multi-wise Comparisons »
Wenbo Ren · Jia Liu · Ness Shroff -
2017 Poster: A New Alternating Direction Method for Linear Programming »
Sinong Wang · Ness Shroff