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

arXiv: https://arxiv.org/abs/1707.09971 · HTML: https://mlsanity.com/paper/1707.09971/

## Key facts

- Cited by 47 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Jul 2017.

## Built on by (most cited first, 30 of 47)

- [Uncertainty quantification in the Bradley-Terry-Luce model](https://mlsanity.com/paper/2110.03874/) (2021)
- [Ranking Inferences Based on the Top Choice of Multiway Comparisons](https://mlsanity.com/paper/2211.11957/) (2022)
- [Inference for Heteroskedastic PCA with Missing Data](https://mlsanity.com/paper/2107.12365/) (2021)
- [Lagrangian Inference for Ranking Problems](https://mlsanity.com/paper/2110.00151/) (2021)
- [Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Model](https://mlsanity.com/paper/2105.14016/) (2021)
- [Optimal Full Ranking from Pairwise Comparisons](https://mlsanity.com/paper/2101.08421/) (2021)
- [Oneshot Differentially Private Top-k Selection](https://mlsanity.com/paper/2105.08233/) (2021)
- [A Tale of HodgeRank and Spectral Method: Target Attack Against Rank Aggregation Is the Fixed Point of Adversarial Game](https://mlsanity.com/paper/2209.05742/) (2022)
- [Uncertainty Quantification of MLE for Entity Ranking with Covariates](https://mlsanity.com/paper/2212.09961/) (2022)
- [Spectral Ranking Inferences based on General Multiway Comparisons](https://mlsanity.com/paper/2308.02918/) (2023)
- [Spectral Entry-wise Matrix Estimation for Low-Rank Reinforcement Learning](https://mlsanity.com/paper/2310.06793/) (2023)
- [ℓ∞-Bounds of the MLE in the BTL Model under General Comparison Graphs](https://mlsanity.com/paper/2110.10825/) (2021)
- [Localization in 1D non-parametric latent space models from pairwise affinities](https://mlsanity.com/paper/2108.03098/) (2021)
- [Deflated HeteroPCA: Overcoming the curse of ill-conditioning in heteroskedastic PCA](https://mlsanity.com/paper/2303.06198/) (2023)
- [Sequential Manipulation Against Rank Aggregation: Theory and Algorithm](https://mlsanity.com/paper/2407.01916/) (2024)
- [Contextual Online Uncertainty-Aware Preference Learning for Human Feedback](https://mlsanity.com/paper/2504.19342/) (2025)
- [Ranking from Pairwise Comparisons in General Graphs and Graphs with Locality](https://mlsanity.com/paper/2304.06821/) (2023)
- [Statistical ranking with dynamic covariates](https://mlsanity.com/paper/2406.16507/) (2024)
- [Dynamic Ranking with the BTL Model: A Nearest Neighbor based Rank Centrality Method](https://mlsanity.com/paper/2109.13743/) (2021)
- [Spectral Estimators for Structured Generalized Linear Models via Approximate Message Passing](https://mlsanity.com/paper/2308.14507/) (2023)
- [Dynamic Ranking and Translation Synchronization](https://mlsanity.com/paper/2207.01455/) (2022)
- [A Spectral Approach to Item Response Theory](https://mlsanity.com/paper/2210.04317/) (2022)
- [Self Improvement via Fast Tree-search](https://mlsanity.com/paper/2609.19526/) (2026)
- [A Spectral Method for Joint Community Detection and Orthogonal Group Synchronization](https://mlsanity.com/paper/2112.13199/) (2021)
- [ReSync: Riemannian Subgradient-based Robust Rotation Synchronization](https://mlsanity.com/paper/2305.15136/) (2023)
- [Statistical inference for pairwise comparison models](https://mlsanity.com/paper/2401.08463/) (2024)
- [Top-K ranking with a monotone adversary](https://mlsanity.com/paper/2402.07445/) (2024)
- [Minimax Hypothesis Testing for the Bradley-Terry-Luce Model](https://mlsanity.com/paper/2410.08360/) (2024)
- [Assumption-free stability for ranking problems](https://mlsanity.com/paper/2506.02257/) (2025)
- [OpinionRank: Extracting Ground Truth Labels from Unreliable Expert Opinions with Graph-Based Spectral Ranking](https://mlsanity.com/paper/2102.05884/) (2021)

## Abstract (arXiv)

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 sinTheta theorem for symmetric matrices. This also allows us to close the gap between the ℓ2 error upper bound for the spectral method and the minimax lower limit.