Top-K ranking with a monotone adversary

Abstract

In this paper, we address the top-๐พ 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-๐พ 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 log2(๐‘›) factor, where ๐‘› 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 โ„“โˆž error analysis of the weighted MLE that is more explicit and tighter than existing analyses. It relates the โ„“โˆž 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 to solve the resulting SDP efficiently in nearly-linear time in the size of the semi-random comparison graph.

Publication
Conference on Learning Theory