Sorted Top-k in Rounds

Mark Braverman, Jieming Mao, Yuval Peres

Research output: Contribution to journalConference articlepeer-review

7 Scopus citations

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, Θ(nk + 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 languageEnglish (US)
Pages (from-to)342-382
Number of pages41
JournalProceedings of Machine Learning Research
Volume99
StatePublished - 2019
Event32nd Conference on Learning Theory, COLT 2019 - Phoenix, United States
Duration: Jun 25 2019Jun 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

Fingerprint

Dive into the research topics of 'Sorted Top-k in Rounds'. Together they form a unique fingerprint.

Cite this