Adversarial Top-K Ranking

Cited 11 time in webofscience Cited 0 time in scopus
  • Hit : 634
  • Download : 0
DC FieldValueLanguage
dc.contributor.authorSuh, Changhoko
dc.contributor.authorTan, Vincent YFko
dc.contributor.authorZhao, Renboko
dc.date.accessioned2017-05-10T04:15:34Z-
dc.date.available2017-05-10T04:15:34Z-
dc.date.created2016-11-22-
dc.date.created2016-11-22-
dc.date.issued2017-04-
dc.identifier.citationIEEE TRANSACTIONS ON INFORMATION THEORY, v.63, no.4, pp.2201 - 2225-
dc.identifier.issn0018-9448-
dc.identifier.urihttp://hdl.handle.net/10203/223598-
dc.description.abstractWe study the top-K ranking problem where the goal is to recover the set of top-K ranked items out of a large collection of items based on partially revealed preferences. We consider an adversarial crowdsourced setting where there are two population sets, and pairwise comparison samples drawn from one of the populations follow the standard Bradley-Terry-Luce model (i.e., the chance of item i beating item j is proportional to the relative score of item i to item j), while in the other population, the corresponding chance is inversely proportional to the relative score. When the relative size of the two populations is known, we characterize the minimax limit on the sample size required (up to a constant) for reliably identifying the top-K items, and demonstrate how it scales with the relative size. Moreover, by leveraging a tensor decomposition method for disambiguating mixture distributions, we extend our result to the more realistic scenario, in which the relative population size is unknown, thus establishing an upper bound on the fundamental limit of the sample size for recovering the top-K set.-
dc.languageEnglish-
dc.publisherIEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC-
dc.subjectLATENT VARIABLE MODELS-
dc.titleAdversarial Top-K Ranking-
dc.typeArticle-
dc.identifier.wosid000398595500021-
dc.identifier.scopusid2-s2.0-85017626501-
dc.type.rimsART-
dc.citation.volume63-
dc.citation.issue4-
dc.citation.beginningpage2201-
dc.citation.endingpage2225-
dc.citation.publicationnameIEEE TRANSACTIONS ON INFORMATION THEORY-
dc.identifier.doi10.1109/TIT.2017.2659660-
dc.contributor.localauthorSuh, Changho-
dc.contributor.nonIdAuthorTan, Vincent YF-
dc.contributor.nonIdAuthorZhao, Renbo-
dc.description.isOpenAccessN-
dc.type.journalArticleArticle; Proceedings Paper-
dc.subject.keywordAuthorAdversarial population-
dc.subject.keywordAuthorBradley-Terry-Luce model-
dc.subject.keywordAuthorcrowdsourcing-
dc.subject.keywordAuthorminimax optimality-
dc.subject.keywordAuthorsample complexity-
dc.subject.keywordAuthortop-K ranking-
dc.subject.keywordAuthortensor decompositions-
dc.subject.keywordPlusLATENT VARIABLE MODELS-
Appears in Collection
EE-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡ Click to see webofscience_button
⊙ Cited 11 items in WoS Click to see citing articles in records_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0