We explore the active top-K sorting problem, in which the goal is to recover the top-K items in order out of n items, from adaptive pairwise comparisons that are collected possibly in a sequential manner as per our design choice. Under a fairly general model which subsumes as special cases various models (e.g., Strong Stochastic Transitivity model, BTL model and uniform noise model), we characterize an upper bound on the sample size required for reliable top-K sorting. As a consequence, we demonstrate that active ranking can offer significant multiplicative gains in sample complexity over passive ranking. Depending on the underlying stochastic noise model, such gain varies from around log n/log log n to n2 log n/log log n. We also present an algorithm that runs linearly in n and which achieves the sample complexity bound. Our theoretical findings are corroborated via numerical experiments.
|Original language||English (US)|
|Title of host publication||54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016|
|Publisher||Institute of Electrical and Electronics Engineers Inc.|
|Number of pages||8|
|State||Published - Feb 10 2017|
|Event||54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016 - Monticello, United States|
Duration: Sep 27 2016 → Sep 30 2016
|Name||54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016|
|Other||54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016|
|Period||9/27/16 → 9/30/16|
Bibliographical noteFunding Information:
The work of C. Suh was supported by the National Research Foundation of Korea (NRF) Grant funded by the Korean Government (MSIP) [2015R1C1A1A02036561]
© 2016 IEEE.