Top-$K$ ranking with a monotone adversary
Yuepeng Yang Antares Chen Lorenzo Orecchia Cong Ma
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.