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

1.1 Popular approaches

• The BTL model assigns each item a latent preference score, with pairwise win probabilities determined by the two items’ relative scores.The task is to identify the K items with the highest preference scores from repeated pairwise comparisons.Source: §1.1 · p. 2
• The spectral method estimates scores using the leading left eigenvector of a sample transition matrix, while MLE maximizes likelihood and can be formulated as a convex program.The spectral procedure is also known as Rank Centrality and resembles PageRank; regularized variants of MLE are also considered.Source: §1.1 · p. 2
• Prior ℓ2 score-estimation accuracy does not determine top-K accuracy, and the standalone spectral method and MLE remained unsettled for exact recovery.Earlier work found a careful combination of the spectral method and coordinate-wise MLE optimal for top-K ranking.Source: §1.1 · p. 2

1.2 Main contributions

• Both the spectral method and regularized MLE achieve exact top-K identification at optimal sample complexity under random comparisons and a fixed dynamic range.The paper emphasizes that both methods succeed even when only an exceedingly small fraction of item pairs have been compared.Source: §1.2 · p. 2
• A leave-one-out argument controls entrywise score errors, and an asymmetric transition-matrix eigenvector bound improves the spectral method’s ℓ2 error to the minimax limit.The perturbation bound parallels Davis-Kahan’s sin Θ theorem for symmetric matrices.Source: §1.2 · p. 3

1.3 Notation

• The paper defines a π-weighted inner product on R^n, with its corresponding vector and induced matrix norms.The inner product is specified for a strictly positive probability vector π.Source: §1.3 · p. 3

2.1 Problem setup

• The BTL setup models pairwise outcomes from latent item scores and targets the K largest scores, with comparisons sampled on an Erdős–Rényi graph.The main results focus on fixed dynamic range.Source: §2.1 · pp. 3–4

2.2.1 The spectral method: Rank Centrality

• Rank Centrality converts comparison data into a transition matrix and ranks items by its leading left eigenvector, which estimates the latent scores up to scaling.The eigenvector is the Markov chain's stationary distribution.Source: §2.2.1 · pp. 4–5

2.2.2 The regularized MLE

• The regularized MLE solves a convex penalized likelihood problem and ranks items by the largest estimated score entries.Source: §2.2.2 · p. 5

2.3 Main results

• 1-O(n^-5): under fixed dynamic range, Rank Centrality and regularized MLE exactly recover top-K at a sample complexity matching the minimax limit.Source: §2.3 · pp. 5–6

2.4 Optimal control of entrywise estimation errors

• Both methods achieve small ℓ∞ score-estimation error when each item's comparison count, concentrated around npL, exceeds order log n.These entrywise bounds yield exact top-K identification.Source: §2.4 · p. 7

2.5 Heuristic arguments

• Both methods' entrywise errors are expected to spread across coordinates: Rank Centrality combines contraction, near-uniform error averaging, and uncertainty, while the MLE has analogous contraction and smoothing.Source: §2.5 · p. 8

2.6 Numerical experiments

• Additional simulations complement prior experiments and the theory, fixing n=200 while varying the number of repeats L and edge probability p.Source: §2.6 · p. 9
• Spectral method and MLE have very similar ℓ∞ score errors; errors shrink as p or L increases, and relative ℓ∞ errors are not much larger than relative ℓ2 errors.At fixed total sample count n^2pL, performance changes little.Source: §2.6 · p. 9
• Top-K accuracy of the spectral method and regularized MLE improves as score separation grows, matching Theorem 1.Figure 3 shows the top-K ranking accuracy of both methods.Source: Figure 3 · p. 10, §2.6 · p. 10

2.7 Other related works

• Prior work studied parametric BTL and nonparametric transitive ranking; Rajkumar and Agarwal (2014) analyzed perfect total-ranking complexity, not top-K accuracy.Shah and Wainwright (2015) proposed a counting-based top-K algorithm, but their sampling paradigm differs in the sparse regime.Source: §2.7 · p. 10
• Related extensions consider heterogeneous user preferences through low-rank preference matrices (Negahban et al. (2017b); Lu and Negahban (2014)) and other settings beyond this paper’s scope.The passage also names Plackett-Luce models, adaptive sampling, crowdsourcing, and adversarial ranking.Source: §2.7 · p. 10
• The paper studies ℓ∞ errors for asymmetric transition-matrix eigenvectors and regularized MLE without assuming expected data matrices are approximately low rank.Source: §2.7 · p. 11
• The paper contributes a sharp eigenvector perturbation framework for asymmetric probability transition matrices, unlike spectral applications based on symmetric matrices or singular vectors.Its leave-one-out auxiliary quantities are similar in spirit to those of Zhong and Boumal (2017) and Abbe et al. (2017).Source: §2.7 · p. 11

3 Extension: general dynamic range

• Theorem 5 assumes p > c0 κ^5 log n/n for the spectral guarantee, while Theorem 6 assumes p ≥ c0 κ^4 log n/n for the regularized-MLE guarantee.The theorems state exact top-K recovery under their respective conditions; the supplied passages do not include the full separation conditions.Source: §3 · pp. 11–12
• The general-κ achievability bounds for both methods do not match the lower bound in κ, partly because ∆K misses the information bottleneck in this regime.The paper introduces generalized separation as a more suitable measure of ranking hardness.Source: §3 · p. 12
• The current analyses do not provide a matching upper bound in terms of (∆*_K)^2.The paper says it is not clear whether this measure can remove κ-dependence from the spectral perturbation analysis, leaving tighter bounds for future work.Source: §3 · p. 12
• The lower bound scales inversely with (∆*_K)^2, whose square is described as a reasonably tight upper bound on a normalized KL-divergence metric.The paper calls ∆*_K the generalized separation measure.Source: §3 · p. 12
• For nonconstant κ, spectral perturbation bounds still depend explicitly on κ, and it remains unclear whether either method alone attains minimal sample complexity.The authors leave tight upper bounds in the general-κ regime open and note that screening extreme scores, for example with Borda count, may be needed.Source: §3 · p. 12

4 Discussion

• The theory is optimal for fixed dynamic range, while statistical and computational limits for general κ remain to be characterized.The paper also notes that whether regularization is necessary for the MLE remains open.Source: §4 · p. 13
• The analysis assumes BTL-generated comparison randomness; whether real data fit the BTL model remains an open practical question.Source: §4 · p. 13
• The results focus on Erdős–Rényi comparison graphs, leaving performance under broader graph families and sampling patterns for future study.Source: §4 · p. 13
• The paper’s leave-one-out and iterative-update approach gives an ℓ∞ perturbation analysis for regularized MLE, which the authors expect could extend to other convex optimization problems.Source: §4 · p. 13

5.1 Preliminaries

• The eigenvector perturbation theorem parallels Davis–Kahan, allows three transition matrices, and requires reversibility only of the reference matrix.It also yields an ℓ2 error bound that improves upon Negahban et al. (2017a) by a logarithmic factor.Source: §5.1 · p. 13
• The spectral method’s ℓ2 error matches the minimax lower bound, establishing its orderwise optimality for that loss.The matching lower bound is from (Negahban et al., 2017a, Theorem 3).Source: §5.1 · p. 14

5.2 Proof outline of Theorem 5

• The leave-one-out matrix replaces transitions involving item m with their expected values, producing a stationary distribution that approximates the original and is independent of item m’s comparisons.This construction decouples the statistical dependency that otherwise makes the pointwise error difficult to control.Source: §5.2 · p. 15

6 Analysis for the regularized MLE

• The section establishes an ℓ∞ error bound for the regularized MLE, the score control used in the paper’s ranking analysis.The conclusion of the proof applies when npL is sufficiently small.Source: §6 · p. 17, §6.5 · p. 22

6.1 Preliminaries and notation

• Preliminary lemmas characterize smoothness and strong convexity of the regularized loss using graph-Laplacian quantities.The Laplacian’s smallest eigenvalue on vectors orthogonal to 1 is used in these bounds.Source: §6.1 · pp. 17–18

6.2 Proof outline of Theorem 6

• The proof analyzes gradient descent from the true score vector, an initialization the authors note is not practical, and uses leave-one-out arguments for entrywise control.The algorithmic trajectory is used to analyze the statistical accuracy of the regularized MLE.Source: §6.2 · p. 18

6.5 Step III

• The final proof step translates the perturbation bound on θ into an entrywise bound on exponentiated scores.This completes the proof of Theorem 6 under the stated condition that npL is sufficiently small.Source: §6.2 · p. 19, §6.5 · p. 22

6.3 Step I

• Gradient descent converges geometrically to the regularized MLE, supporting the proof’s first step of showing the iterate is close to the minimizer.The geometric rate is expressed using ρ = 1 − λ/(λ + np).Source: §6.3 · p. 19

6.4 Step II

• For each item, the leave-one-out loss replaces its comparison terms with expected values, creating a proxy sequence independent of that item’s observed comparisons.Inductive bounds are propagated across iterations and combined with Step I’s optimization guarantee.Source: §6.4 · pp. 20–21

A Proof of Theorem 7

• Swapping the Kth and (K + 1)th scores preserves the generalized separation measure but changes the top-K set.The proof reduces exact identification to distinguishing the two resulting score scenarios.Source: A Proof of Theorem 7 · p. 22
• The proof bounds the scenarios’ total variation using KL divergence, the fact that their comparison distributions differ only at pairs involving those items, and Pinsker’s inequality.The KL bound uses the product structure of the comparison samples and the independence assumption.Source: A Proof of Theorem 7 · p. 23
• When the total variation is at most ϵ, the error probability for distinguishing the two scenarios is at least 1 − ϵ.Source: A Proof of Theorem 7 · pp. 22–23

B Examples for the general κ setting

• When κ = O(1), the earlier results hold with ∆K replaced by ∆*K, while the corresponding lower bound is worse by a factor of log n.Source: B Examples for the general κ setting · p. 24
• With 100 items, adding a very low-scoring item changes ∆*K² only slightly: 0.1107 when present versus 0.1118 when absent.Source: B Examples for the general κ setting · p. 24
• For top-5 recovery with two groups of five high-scoring items, adding items 11–100 makes comparisons within the top ten less informative and increases required sample size.∆*K² is approximately 0.0118 with items 11–100 present versus 0.1181 absent.Source: B Examples for the general κ setting · p. 24

C Proofs in Section 5

• Under the degree-concentration event, the maximum graph degree is at most d.The event holds with probability at least 1 − O(n^-10).Source: C Proofs in Section 5 · p. 24

C.1 Proof of Theorem 8

• The proof of Theorem 8 uses stationary-distribution identities, including (π − π̂)^T1π*^T = 0, in its derivation.Source: §C.1 · p. 25

• The proof splits ∆ into lower-triangular, upper-triangular, and two diagonal parts to establish (51).It focuses first on the lower-triangular contribution; the other three are handled with nearly identical arguments.Source: §C.2 · pp. 25–26
• The lower-triangular contribution is treated as a quadratic form of a sub-Gaussian vector, using independence and a concentration bound.For each pair in E, ∆ entries are sums of independent zero-mean random variables.Source: §C.2 · p. 26
• Applying the same upper bounds to the other terms establishes (51) when d ≳ np.Source: §C.2 · p. 26

C.3 Proof of Lemma 2

• The lemma is established by taking union bounds and using the fact that the event dmax ≤ d has probability at least 1 − O(n^-10), as follows from Lemma 1 in the main text and the remarks after that.Source: §C.3 · p. 27

C.4 Proof of Lemma 3

• On event A0, dmin ≥ np/2; combining this condition with the preceding bound completes Lemma 3.Source: §C.4 · p. 27

C.5 Proof of Lemma 4

• For Lemma 4, a leave-one-out transition matrix replaces probabilities involving item m with their conditional expectations, while remaining a valid transition matrix.Source: §C.5 · p. 28

C.6 Proof of Lemma 6

• The Lemma 6 proof splits Im^4 into a conditional expectation given G−m and the outcomes, plus a fluctuation term.It bounds the expectation and fluctuation separately, then combines the bounds to complete the proof.Source: §C.6 · pp. 30–31

D.1 Proof of Lemma 7

• The Lemma 7 proof applies matrix Bernstein concentration and uses the conditional expectation of the regularized gradient at θ* to bound its norm.Source: §D.1 · pp. 31–32

D.2 Proof of Lemma 9

• For Lemma 9, the proof considers θ within an ℓ∞ distance C of θ* and bounds pairwise score differences under that condition.Source: §D.2 · p. 32

D.3 Proof of Fact 1

• Fact 1 follows by induction: the zero-sum condition 1⊤θt = 0 is preserved by the gradient expression.Source: §D.3 · p. 32

D.4 Proof of Lemma 12

• The Lemma 12 proof yields ∥θ − θ*∥2 ≤ c2 log κ√n.The argument uses optimality, the mean value theorem, and Cauchy–Schwarz.Source: §D.4 · pp. 32–33

D.5 Proof of Lemma 13

• For Lemma 13, the two stated consequences follow from triangle inequalities when the corresponding constants meet the specified lower bounds.Source: §D.5 · p. 33

D.6 Proof of Lemma 14

• The Lemma 14 proof uses an interpolating path from θ* to θt and Hessian bounds to control the gradient update.It also uses that θt − θ* has zero sum when bounding a term in the update.Source: §D.6 · p. 34

D.7 Proof of Lemma 15

• For Lemma 15, the proof applies the gradient update rule and combines preceding bounds under a sufficiently small ε and a stated condition on C2.Source: §D.7 · pp. 34, 36

D.8 Proof of Lemma 16

• The first term in (72) is bounded using Hoeffding’s inequality and union bounds over all m, with the number of incident comparisons of order np.The passage states this bound for every 1 ≤ m ≤ n.Source: §D.8 · p. 37
• For the second term in (72), the proof treats v_m as a zero-mean random vector and applies Bernstein’s inequality under the condition np ≫ log n.The coefficient bound uses g(x) = (1 + e^x)^−1 and |g′(x)| ≤ 1.Source: §D.8 · pp. 37–38

D.9 Proof of Lemma 17

• The proof of Lemma 17 uses the triangle inequality, with the stated proviso that C4 ≥ C3 + C2.Source: §D.9 · p. 38

E Hoeffding’s and Bernstein’s inequalities

• The appendix states Hoeffding’s and Bernstein’s concentration inequalities for independent random variables and omits their proofs.These inequalities are identified as standard tools used throughout the paper.Source: E Hoeffding’s and Bernstein’s… · p. 39