Spectral Method and Regularized MLE Are Both Optimal for Top-K Ranking

Yuxin Chen Jianqing Fan Cong Ma Kaizheng Wang

Statistics Theory and Methods mathscidoc:1912.43373

arXiv preprint arXiv:1707.09971
This paper is concerned with the problem of top- K ranking from pairwise comparisons. Given a collection of K items and a few pairwise comparisons across them, one wishes to identify the set of K items that receive the highest ranks. To tackle this problem, we adopt the logistic parametric model---the Bradley-Terry-Luce model, where each item is assigned a latent preference score, and where the outcome of each pairwise comparison depends solely on the relative scores of the two items involved. Recent works have made significant progress towards characterizing the performance (eg the mean square error for estimating the scores) of several classical methods, including the spectral method and the maximum likelihood estimator (MLE). However, where they stand regarding top- K ranking remains unsettled.
No keywords uploaded!
[ Download ] [ 2019-12-21 11:40:21 uploaded by Jianqing_Fan ] [ 595 downloads ] [ 0 comments ]
@inproceedings{yuxinspectral,
  title={Spectral Method and Regularized MLE Are Both Optimal for Top-K Ranking},
  author={Yuxin Chen, Jianqing Fan, Cong Ma, and Kaizheng Wang},
  url={http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20191221114021622714933},
  booktitle={arXiv preprint arXiv:1707.09971},
}
Yuxin Chen, Jianqing Fan, Cong Ma, and Kaizheng Wang. Spectral Method and Regularized MLE Are Both Optimal for Top-K Ranking. In arXiv preprint arXiv:1707.09971. http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20191221114021622714933.
Please log in for comment!
 
 
Contact us: office-iccm@tsinghua.edu.cn | Copyright Reserved