Active top-K ranking from noisy comparisons

Soheil Mohajer, Changho Suh

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Scopus citations

Abstract

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 languageEnglish (US)
Title of host publication54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages875-882
Number of pages8
ISBN (Electronic)9781509045495
DOIs
StatePublished - Feb 10 2017
Event54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016 - Monticello, United States
Duration: Sep 27 2016Sep 30 2016

Publication series

Name54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016

Other

Other54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016
CountryUnited States
CityMonticello
Period9/27/169/30/16

Fingerprint Dive into the research topics of 'Active top-K ranking from noisy comparisons'. Together they form a unique fingerprint.

Cite this