# Spectral MLE: Top-K Rank Aggregation from Pairwise Comparisons

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

## Key facts

- Cited by 34 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Apr 2015.

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

- [Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisons](https://mlsanity.com/paper/2301.11270/) (2023)
- [Distributional Preference Learning: Understanding and Accounting for Hidden Context in RLHF](https://mlsanity.com/paper/2312.08358/) (2023)
- [Uncertainty quantification in the Bradley-Terry-Luce model](https://mlsanity.com/paper/2110.03874/) (2021)
- [Lagrangian Inference for Ranking Problems](https://mlsanity.com/paper/2110.00151/) (2021)
- [Optimal Full Ranking from Pairwise Comparisons](https://mlsanity.com/paper/2101.08421/) (2021)
- [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)
- [ℓ∞-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)
- [On the identifiability of mixtures of ranking models](https://mlsanity.com/paper/2201.13132/) (2022)
- [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)
- [Matrix Completion with Hierarchical Graph Side Information](https://mlsanity.com/paper/2201.01728/) (2022)
- [Byzantine Spectral Ranking](https://mlsanity.com/paper/2211.07902/) (2022)
- [Self Improvement via Fast Tree-search](https://mlsanity.com/paper/2609.19526/) (2026)
- [Ranking with Confidence for Large Scale Comparison Data](https://mlsanity.com/paper/2202.01670/) (2022)
- [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)
- [What Does Preference Learning Recover from Pairwise Comparison Data?](https://mlsanity.com/paper/2602.10286/) (2026)
- [On the Optimal Bounds for Noisy Computing](https://mlsanity.com/paper/2306.11951/) (2023)
- [On Top-k Selection from m-wise Partial Rankings via Borda Counting](https://mlsanity.com/paper/2204.05742/) (2022)
- [Inferences on Mixing Probabilities and Ranking in Mixed-Membership Models](https://mlsanity.com/paper/2308.14988/) (2023)
- [Rate-Optimal Rank Aggregation with Private Pairwise Rankings](https://mlsanity.com/paper/2402.16792/) (2024)
- [Optimal Differentially Private Ranking from Pairwise Comparisons](https://mlsanity.com/paper/2507.09388/) (2025)
- [Top-k Feature Importance Ranking](https://mlsanity.com/paper/2509.15420/) (2025)
- [Entrywise Error Bounds for Spectral Ranking with Semi-Random Adversaries](https://mlsanity.com/paper/2605.23854/) (2026)
- [Achievability and Impossibility of Exact Pairwise Ranking](https://mlsanity.com/paper/2111.10021/) (2021)
- [Efficient and Accurate Top-K Recovery from Choice Data](https://mlsanity.com/paper/2206.11995/) (2022)
- [Random pairing MLE for estimation of item parameters in Rasch model](https://mlsanity.com/paper/2406.13989/) (2024)
- [Pairwise Comparisons without Stochastic Transitivity: Model, Theory and Applications](https://mlsanity.com/paper/2501.07437/) (2025)

## Abstract (arXiv)

This paper explores the preference-based top-K rank aggregation problem. Suppose that a collection of items is repeatedly compared in pairs, and one wishes to recover a consistent ordering that emphasizes the top-K ranked items, based on partially revealed preferences. We focus on the Bradley-Terry-Luce (BTL) model that postulates a set of latent preference scores underlying all items, where the odds of paired comparisons depend only on the relative scores of the items involved. We characterize the minimax limits on identifiability of top-K ranked items, in the presence of random and non-adaptive sampling. Our results highlight a separation measure that quantifies the gap of preference scores between the Kth and (K+1)th ranked items. The minimum sample complexity required for reliable top-K ranking scales inversely with the separation measure irrespective of other preference distribution metrics. To approach this minimax limit, we propose a nearly linear-time ranking scheme, called Spectral MLE, that returns the indices of the top-K items in accordance to a careful score estimate. In a nutshell, Spectral MLE starts with an initial score estimate with minimal squared loss (obtained via a spectral method), and then successively refines each component with the assistance of coordinate-wise MLEs. Encouragingly, Spectral MLE allows perfect top-K item identification under minimal sample complexity. The practical applicability of Spectral MLE is further corroborated by numerical experiments.