PARTIAL RECOVERY FOR TOP-k RANKING: OPTIMALITY OF MLE AND SUBOPTIMALITY OF THE SPECTRAL METHOD

• 成果类型: Article
• 署名作者: Chen, Pinhan; Gao, Chao; Zhang, Anderson Y.
• 署名单位: University of Chicago; University of Pennsylvania
• 刊物名称: ANNALS OF STATISTICS
• ISSN/ISSBN: 0090-5364
• DOI: 10.1214/21-AOS2166
• 发表日期: 2022
• 页码: 1618-1652
• 关键词: VARIABLE SELECTION

摘要

Given partially observed pairwise comparison data generated by the Bradley-Terry-Luce (BTL) model, we study the problem of top-k ranking. That is, to optimally identify the set of top-k players. We derive the minimax rate with respect to a normalized Hamming loss. This provides the first result in the literature that characterizes the partial recovery error in terms of the proportion of mistakes for top-k ranking. We also derive the optimal signal to noise ratio condition for the exact recovery of the top-k set. The maximum likelihood estimator (MLE) is shown to achieve both optimal partial recovery and optimal exact recovery. On the other hand, we show another popular algorithm, the spectral method, is in general suboptimal. Our results complement the recent work (Ann. Statist. 47 (2019) 2204-2235) that shows both the MLE and the spectral method achieve the optimal sample complexity for exact recovery. It turns out the leading constants of the sample complexity are different for the two algorithms. Another contribution that may be of independent interest is the analysis of the MLE without any penalty or regularization for the BTL model. This closes an important gap between theory and practice in the literature of ranking.