Generalized rank-breaking: Computational and statistical tradeoffs

Ashish Khetan, Sewoong Oh

Research output: Contribution to journalArticlepeer-review

Abstract

For massive and heterogeneous modern datasets, it is of fundamental interest to provide guarantees on the accuracy of estimation when computational resources are limited. In the application of rank aggregation, for the Plackett-Luce model, we provide a hierarchy of rank-breaking mechanisms ordered by the complexity in thus generated sketch of the data. This allows the number of data points collected to be gracefully traded off against computational resources available, while guaranteeing the desired level of accuracy. Theoretical guarantees on the proposed generalized rank-breaking implicitly provide such trade-offs, which can be explicitly characterized under certain canonical scenarios on the structure of the data. Further, the proposed generalized rank-breaking algorithm involves set-wise comparisons as opposed to traditional pairwise comparisons. The maximum likelihood estimate of pairwise comparisons is computed efficiently using the celebrated minorization maximization algorithm (Hunter, 2004). To compute the pseudo-maximum likelihood estimate of the set-wise comparisons, we provide a generalization of the minorization maximization algorithm and give guarantees on its convergence.

Original languageEnglish (US)
Pages (from-to)1-42
Number of pages42
JournalJournal of Machine Learning Research
Volume19
StatePublished - Sep 1 2018

Keywords

  • Plackett-Luce model
  • Rank aggregation
  • Sample and Computational tradeoff

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Statistics and Probability
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'Generalized rank-breaking: Computational and statistical tradeoffs'. Together they form a unique fingerprint.

Cite this