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

Arpit Agarwal, Sanjeev Khanna, Prathamesh Patil
Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, PMLR 151:6814-6839, 2022.

Abstract

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 parallel interaction with the feedback generating oracle. We study this problem under the 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v151-agarwal22a, title = { PAC Top-$k$ Identification under SST in Limited Rounds }, author = {Agarwal, Arpit and Khanna, Sanjeev and Patil, Prathamesh}, booktitle = {Proceedings of The 25th International Conference on Artificial Intelligence and Statistics}, pages = {6814--6839}, year = {2022}, editor = {Camps-Valls, Gustau and Ruiz, Francisco J. R. and Valera, Isabel}, volume = {151}, series = {Proceedings of Machine Learning Research}, month = {28--30 Mar}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v151/agarwal22a/agarwal22a.pdf}, url = {https://proceedings.mlr.press/v151/agarwal22a.html}, abstract = { 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 parallel interaction with the feedback generating oracle. We study this problem under the 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. } }
Endnote
%0 Conference Paper %T PAC Top-$k$ Identification under SST in Limited Rounds %A Arpit Agarwal %A Sanjeev Khanna %A Prathamesh Patil %B Proceedings of The 25th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2022 %E Gustau Camps-Valls %E Francisco J. R. Ruiz %E Isabel Valera %F pmlr-v151-agarwal22a %I PMLR %P 6814--6839 %U https://proceedings.mlr.press/v151/agarwal22a.html %V 151 %X 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 parallel interaction with the feedback generating oracle. We study this problem under the 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.
APA
Agarwal, A., Khanna, S. & Patil, P.. (2022). PAC Top-$k$ Identification under SST in Limited Rounds . Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 151:6814-6839 Available from https://proceedings.mlr.press/v151/agarwal22a.html.

Related Material