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

By Yuxin Chen, Jianqing Fan, Cong Ma, Kaizheng Wang. 2017

130 citations recorded by the source corpus.

This paper is concerned with the problem of top-K ranking from pairwise comparisons. Given a collection of n 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 (e.g. 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. We demonstrate that under a natural random sampling model, the spectral method alone, or the regularized MLE alone, is minimax optimal in terms of the sample complexity — the number of paired comparisons needed to ensure exact top-K identification, for the fixed dynamic range regime. This is accomplished via optimal control of the entrywise error of the score estimates. We complement our theoretical studies by numerical experiments, confirming that both methods yield low entrywise errors for estimating the underlying scores. Our theory is established via a novel leave-one-out trick, which proves effective for analyzing both iterative and non-iterative procedures. Along the way, we derive an elementary eigenvector perturbation bound for probability transition matrices, which parallels the Davis-Kahan Θ theorem for symmetric matrices. This also allows us to close the gap between the l2 error upper bound for the spectral method and the minimax lower limit.

Subfields: Computer Science Applications, Economics and Econometrics, Marketing, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Science Applications

In Economics and Econometrics

In Marketing

In Optimization & Training

Citations in the corpus

Generalized Results for the Existence and Consistency of the MLE in the Bradley-Terry-Luce Model (2021, methodology): “Theorem 3.1 of Chen et al. (2019) requires that p = Ω( log d d ) , to ensure that the comparison graph is connected.”
Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution (2017, methodology): “In particular, this technique results in tight performance guarantees for the generalized power method [133], the spectral method [1,30], and convex programming approaches [30,44,108,133]; however, it has not been applied to analyze nonconvex optimization algorithms.”
PARTIAL RECOVERY FOR TOP-K RANKING: OPTIMALITY OF MLE AND SUB-OPTIMALITY OF SPECTRAL METHOD (2020, methodology): “The results of [7] lead to the following intriguing research questions.”
The Sample Complexity of Best-k Items Selection from Pairwise Comparisons (2020, background): “An early work that has studied the exact k-selection was done by Feige et al. (1994). Feige et al. (1994) have shown that if ∆i,j ≥ ∆ > 0 for all items i and j where ∆ > 0 is a priori known, then to find the best-k items of [n] with probability at least 1 − δ, Θ(∆−2 log(k/δ)) comparisons are suffici”
Optimal full ranking from pairwise comparisons (2021, methodology): “Both the MLE and the spectral method have been studied for parameter estimation [11, 42] and top-k ranking [9, 11] under the BTL model.”
Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview (2018, methodology): “Finally, the spectral method has been applied to many other problems beyond the ones discussed here, including but not limited to community detection [133], [134], phase synchronization [9], joint alignment [11], ranking from pairwise comparisons [72], [135], [136], tensor estimation [137]–[140].”