Top-$K$ ranking with a monotone adversary

Yuepeng Yang, Antares Chen, Lorenzo Orecchia, Cong Ma

TL;DR

This paper presents a robust approach to the top-$K$ ranking problem under a "monotone adversary"—a scenario where an adversary can add arbitrary pairwise comparisons to a random sample. By combining a novel $\ell_\infty$ error analysis with a fast, SDP-based graph reweighting algorithm, the authors develop a weighted Maximum Likelihood Estimator (MLE) that achieves near-optimal sample complexity in nearly-linear time.

What Problem Does This Paper Address?

Ranking items based on pairwise comparisons is a fundamental task in recommendation systems, sports analytics (like the Elo rating), and web search. A standard framework for this is the Bradley-Terry-Luce (BTL) model, which assumes each item has a latent score, and the probability of one item beating another depends on the difference between their scores.

Most theoretical guarantees for ranking assume uniform sampling, where every pair of items is compared with equal probability. However, real-world data is rarely so clean. The authors tackle the semi-random model, where a base of uniform comparisons is "corrupted" by a monotone adversary who can add any number of additional comparisons.

Intuitively, more data should be better. However, in the world of high-dimensional statistics, these extra comparisons can destroy the "homogeneity" (like uniform vertex degrees) that standard algorithms rely on. As shown in Figure 1, an adversary can create dense clusters of comparisons that bias traditional estimators.

Figure 1: Adjacency matrix of a semi-random comparison graph. Each non-white square cor- responds to a non-zero entry in the adjacency matrix.

Methods

The authors propose a Weighted Maximum Likelihood Estimator (MLE). Instead of treating every comparison equally, they assign a weight $w_{ij}$ to each pair $(i, j)$. The core challenge is finding weights that "neutralize" the adversary's influence.

Their approach involves three main components:

  1. Refined $\ell_\infty$ Analysis: They provide a new theoretical bound relating the ranking error to the spectral properties of the weighted comparison graph—specifically the spectral gap of its Laplacian. Unlike previous work, this analysis doesn't rely on the "leave-one-out" argument, which fails when edges are not independent.
  2. SDP-based Reweighting: To find the best weights, they formulate a Semi-Definite Program (SDP). The goal is to maximize the graph's spectral gap while keeping the maximum weighted degree and individual weights within specific bounds. This effectively "smooths out" the graph to mimic a uniform one.
  3. Fast Solver (MMWU): Solving large-scale SDPs is usually slow. The authors adapt the Matrix Multiplicative Weight Update (MMWU) framework to solve their specific SDP in nearly-linear time relative to the number of comparisons, making it practical for large datasets.

Datasets

The paper primarily uses simulated datasets to rigorously test the theoretical bounds.

  • Setup: They generate an Erdős-Rényi random graph ($n=200$ items) and then simulate a monotone adversary by adding all possible edges between specific subsets of items.
  • Evaluation: They compare their weighted MLE against a "vanilla" MLE (which treats all comparisons equally) to measure the accuracy of recovering the true top-$K$ items across varying score gaps ($\Delta_K$).

Key Insights and Ideas

  • Spectral Properties are the Key: The success of top-$K$ ranking is deeply tied to the connectivity and "expansion" properties of the comparison graph. If the graph has a large spectral gap, the MLE is much more stable.
  • Reweighting as a Defense: You can't stop an adversary from adding biased data, but you can use optimization to down-weight the "noisy" or overly dense parts of the graph, restoring the spectral properties needed for accurate estimation.
  • Bypassing Independence: By using a preconditioned gradient descent analysis for the MLE, the authors avoid the need for edge independence, which is a major hurdle in analyzing non-uniform or adversarial sampling.

Key Results

  • Near-Optimal Complexity: The weighted MLE identifies the top-$K$ items with a sample complexity that is optimal up to a $\log^2(n)$ factor. As shown in Figure 3, their method closely tracks the theoretical minimax limit when the score gap is small.
  • Empirical Superiority: In simulations (Figure 2), the weighted MLE significantly outperforms the vanilla MLE under semi-random sampling, achieving 100% recovery accuracy at much smaller score gaps.
  • Efficiency: The algorithm is computationally efficient, running in $\tilde{O}(|E|)$ time, where $|E|$ is the number of comparisons.
Figure 2: Accuracy of top-K recovery for MLE under uniform sampling and weighted MLE un- der semi-random sampling. See Section F for the experiment setup.
Figure 3: Sample complexity required to exactly recover top-K items v.s. score gap ∆K. The solid line represents the required sample complexity of the weighted MLE as given in Theorem 1. The dashed line represents the minimax lower bound given in Theorem 2.

Limitations and Future Work

  • The Log Factor: There remains a $\log^2(n)$ gap between the proposed method's complexity and the absolute minimax lower bound for certain ranges of the score gap. The authors suggest "shaving" this factor as a direction for future work.
  • Necessity of Weights: While the weighted MLE is proven to work, the authors note that in some specific clustered sampling cases (Appendix E), the vanilla MLE might still succeed. Determining exactly when reweighting is strictly necessary remains an open question.
  • Model Extensions: The current work focuses on the BTL model. Extending these adversarial guarantees to other ranking models, like the Plackett-Luce model for multi-way comparisons, is a promising next step.

Summary updated

Abstract

In this paper, we address the top-$K$ ranking problem with a monotone adversary. We consider the scenario where a comparison graph is randomly generated and the adversary is allowed to add arbitrary edges. The statistician's goal is then to accurately identify the top-$K$ preferred items based on pairwise comparisons derived from this semi-random comparison graph. The main contribution of this paper is to develop a weighted maximum likelihood estimator (MLE) that achieves near-optimal sample complexity, up to a $\log^2(n)$ factor, where $n$ denotes the number of items under comparison. This is made possible through a combination of analytical and algorithmic innovations. On the analytical front, we provide a refined~$\ell_\infty$ error analysis of the weighted MLE that is more explicit and tighter than existing analyses. It relates the~$\ell_\infty$ error with the spectral properties of the weighted comparison graph. Motivated by this, our algorithmic innovation involves the development of an SDP-based approach to reweight the semi-random graph and meet specified spectral properties. Additionally, we propose a first-order method based on the Matrix Multiplicative Weight Update (MMWU) framework. This method efficiently solves the resulting SDP in nearly-linear time relative to the size of the semi-random comparison graph.
BibTeX
@inproceedings{yang2024top,
  author = {Yuepeng Yang and Antares Chen and Lorenzo Orecchia and Cong Ma},
  title = {{Top-$K$ ranking with a monotone adversary}},
  booktitle = {Conference on Learning Theory},
  year = {2024},
}
Figure