Top-K Ranking by Spectral Method and Regularized Maximum Likelihood via Leave-One-Out Analysis

A unified pairwise-comparison ranking and entrywise $\ell_\infty$ estimation framework (established by Yuxin Chen, Jianqing Fan, Cong Ma, and Kaizheng Wang in 2019) proving that both the spectral method (Rank Centrality stationary distribution $\boldsymbol{\pi}$ of the empirical comparison transition matrix $\mathbf{P}$) and $\ell_2$-regularized maximum likelihood estimation ($\widehat{\boldsymbol{\theta}} = \arg\min_{\boldsymbol{\theta}} \mathcal{L}_\lambda(\boldsymbol{\theta})$ with $\mathcal{L}_\lambda(\boldsymbol{\theta}) = \sum_{(i,j)\in\mathcal{E}, i>j}[-y_{j,i}(\theta_i - \theta_j) + \log(1 + e^{\theta_i - \theta_j})] + \frac{1}{2}\lambda\|\boldsymbol{\theta}\|_2^2$) achieve minimax-optimal entrywise $\ell_\infty$ relative error and exact top-$K$ item identification under the Bradley–Terry–Luce (BTL) model $y_{i,j}^{(l)} \sim \text{Bernoulli}(w_j^*/(w_i^* + w_j^*))$ on an Erdős–Rényi comparison graph $\mathcal{G}_{n,p}$ with $L$ repeated comparisons per edge. Theorem 8 establishes a sharp stationary-distribution perturbation bound for reversible Markov chains in the $\boldsymbol{\pi}^*$-weighted norm $\|\mathbf{x}\|_{\boldsymbol{\pi}^*} = \sqrt{\sum_i (x_i^2 / \pi_i^*)}$ (for row distributions): $\|\boldsymbol{\pi} - \boldsymbol{\pi}^*\|_{\boldsymbol{\pi}^*} \le \|\boldsymbol{\pi}^*(\mathbf{P} - \mathbf{P}^*)\|_{\boldsymbol{\pi}^*} / (1 - \rho^* - \|\mathbf{P} - \mathbf{P}^*\|_{\boldsymbol{\pi}^*})$. Combining Theorem 8 with a leave-one-out transition matrix $\mathbf{P}^{(m)}$ (replacing item $m$'s random comparisons by their population means, Section 4.2, Theorem 3) and a leave-one-out gradient-descent trajectory $\boldsymbol{\theta}^{t,(m)}$ for the regularized MLE (Section 4.3, Theorem 4) proves $\|\boldsymbol{\pi} - \boldsymbol{\pi}^*\|_\infty / \|\boldsymbol{\pi}^*\|_\infty \lesssim \sqrt{\log n / (npL)}$ and $\|\widehat{\boldsymbol{\theta}} - \boldsymbol{\theta}^*\|_\infty \lesssim \sqrt{\log n / (npL)}$, achieving exact top-$K$ identification whenever the total sample size satisfies $n^2 p L / 2 \gtrsim n\log n / \Delta_K^2$ where $\Delta_K = (w_K^* - w_{K+1}^*) / w_{\max}^*$ (Theorems 1–2).