Sorted Top-k in Rounds
This work addresses round-efficient rank aggregation for applications where multiple interactions are costly, providing theoretical bounds that are incremental but precise.
The paper tackles the sorted top-k problem, aiming to recover the top-k items in correct order using pairwise comparisons with a constant number of rounds, and characterizes optimal sample complexity as Θ(n^2) for r=1, Θ(n√k + n^{4/3}) for r=2, and ~Θ(n^{2/r}k^{(r-1)/r} + n) for r≥3 in the noiseless case, with extensions to noisy comparisons.
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 $Θ(n^2)$ for $r=1$, $Θ(n\sqrt{k} + n^{4/3})$ for $r=2$ and $\tildeΘ\left(n^{2/r} k^{(r-1)/r} + n\right)$ for $r \geq 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.