# Entrywise Error Bounds for Spectral Ranking with Semi-Random Adversaries

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 59 references that are in the map.
- First posted on arXiv 22 May 2026.

## Builds on (most cited first, 17 of 17)

- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Deep reinforcement learning from human preferences](https://mlsanity.com/paper/1706.03741/) (2017)
- [Chatbot Arena: An Open Platform for Evaluating LLMs by Human Preference](https://mlsanity.com/paper/2403.04132/) (2024)
- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Estimation from Pairwise Comparisons: Sharp Minimax Bounds with Topology Dependence](https://mlsanity.com/paper/1505.01462/) (2015)
- [Spectral Method and Regularized MLE Are Both Optimal for Top-K Ranking](https://mlsanity.com/paper/1707.09971/) (2017)
- [Spectral MLE: Top-K Rank Aggregation from Pairwise Comparisons](https://mlsanity.com/paper/1504.07218/) (2015)
- [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)
- [Lagrangian Inference for Ranking Problems](https://mlsanity.com/paper/2110.00151/) (2021)
- [Semi-Random Sparse Recovery in Nearly-Linear Time](https://mlsanity.com/paper/2203.04002/) (2022)
- [Non-Convex Matrix Completion Against a Semi-Random Adversary](https://mlsanity.com/paper/1803.10846/) (2018)
- [Fast and Near-Optimal Diagonal Preconditioning](https://mlsanity.com/paper/2008.01722/) (2020)
- [Nonparametric Estimation in the Dynamic Bradley-Terry Model](https://mlsanity.com/paper/2003.00083/) (2020)
- [Ranking from Pairwise Comparisons in General Graphs and Graphs with Locality](https://mlsanity.com/paper/2304.06821/) (2023)
- [Minimax Hypothesis Testing for the Bradley-Terry-Luce Model](https://mlsanity.com/paper/2410.08360/) (2024)
- [Hypothesis Testing for Generalized Thurstone Models](https://mlsanity.com/paper/2512.02912/) (2025)

## Built on by (most cited first, 1 of 1)

- [Bradley-Terry model under general comparison graphs](https://mlsanity.com/paper/2610.06237/) (2026)

## Abstract (arXiv)

Bradley-Terry-Luce (BTL) model estimation is a well-established strategy to rank a collection of items given a dataset of pairwise comparisons. Although the theoretical performance of BTL estimation methods, such as spectral and maximum likelihood estimation, is well studied in the regime of uniformly sampled graphs, generalizing such results to a wider class of random graphs has proved challenging. In this work, we investigate the entry-wise error of spectral algorithms against a semi-random adversary that can arbitrarily boost the sampling probabilities of certain edges. We find that the performance of the unweighted spectral method is heavily dependent on the spectral properties of the generated graph. Furthermore, we show that asymptotic performance approaching that of uniformly sampled graphs can be recovered by appropriately reweighting the observed edges to counteract the adversary and restore the spectral gap. Finally, we provide numerical simulations that support our theoretical findings.