Abstract
We consider the sorted top-k problem whose goal is to recover the top-k items with the correct order out of n items using pairwise comparisons. In many applications, multiple rounds of interaction can be costly. We restrict our attention to algorithms with a constant number of rounds r and try to minimize the sample complexity, i.e. the number of comparisons. When the comparisons are noiseless, we characterize how the optimal sample complexity depends on the number of rounds (up to a polylogarithmic factor for general r and up to a constant factor for r = 1 or 2). In particular, the sample complexity is Θ(n2) for r = 1, Θ(n√k + n4/3) for r = 2 and Θ̃ (n2/rk(r-1)/r + n) for r ≥ 3. We extend our results of sorted top-k to the noisy case where each comparison is correct with probability 2/3. When r = 1 or 2, we show that the sample complexity gets an extra Θ(log(k)) factor when we transition from the noiseless case to the noisy case. We also prove new results for top-k and sorting in the noisy case. We believe our techniques can be generally useful for understanding the trade-off between round complexities and sample complexities of rank aggregation problems.
Original language | English (US) |
---|---|
Pages (from-to) | 342-382 |
Number of pages | 41 |
Journal | Proceedings of Machine Learning Research |
Volume | 99 |
State | Published - 2019 |
Event | 32nd Conference on Learning Theory, COLT 2019 - Phoenix, United States Duration: Jun 25 2019 → Jun 28 2019 |
All Science Journal Classification (ASJC) codes
- Artificial Intelligence
- Software
- Control and Systems Engineering
- Statistics and Probability
Keywords
- noisy comparisons
- rank aggregation
- round complexity
- sorting
- top-k ranking