Partial Recovery for Top-$k$ Ranking: Optimality of MLE and Sub-Optimality of Spectral Method
This addresses ranking accuracy in applications like sports or recommendations, providing theoretical guarantees for optimal algorithms, though it is incremental by refining prior work on exact recovery.
The paper tackles the problem of top-k ranking from partially observed pairwise comparisons under the BTL model, deriving minimax rates for partial recovery and optimal conditions for exact recovery, and shows that the MLE achieves optimality while the spectral method is sub-optimal.
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 sub-optimal. Our results complement the recent work by Chen et al. (2019) 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.