PAC Top-$k$ Identification under SST in Limited Rounds

We consider the problem of finding top-$k$ items from a set of $n$ items using actively chosen pairwise comparisons. This problem has been widely studied in machine learning and has widespread applications in recommendation systems, sports, social choice etc. Motivated by applications where there can be a substantial delay between requesting comparisons and receiving feedback, we consider an active/adaptive learning setting where the algorithm uses limited rounds of \emph{parallel} interaction with the feedback generating oracle.We study this problem under the \emph{strong stochastic transitivity} (SST) noise model which is a widely studied ranking model and captures many applications. A special case of this model is the noisy comparison model for which it was recently shown that $O(n \log k)$ comparisons and $\log^* n$ rounds of adaptivity are sufficient to find the set of top-$k$ items (Cohen-Addad et al., 2020; Braverman et al., 2019). Under the more general SST model, it is known that $O(n)$ comparisons and $O(n)$ rounds are sufficient to find a PAC top-1 item (Falahatgar et al., 2017a,b), however, not much seems to be known for general $k$, even given unbounded rounds of adaptivity. We first show that $\Omega (nk)$ comparisons are necessary for PAC top-$k$ identification under SST even with unbounded adaptivity, establishing that this problem is strictly harder under SST than it is for the noisy comparison model. Our main contribution is to show that the 2-round query complexity for this problem is $\widetilde{\Theta} (n^{4/3} + nk)$, and to show that just 3 rounds are sufficient to obtain a nearly optimal query complexity of $\widetilde{\Theta}(nk)$. We further show that our 3-round result can be improved by a $\log (n)$ factor using $2 \log^* n + 4$ rounds.