Top-$K$ ranking with a monotone adversary

Yuepeng Yang, Antares Chen, Lorenzo Orecchia, Cong Ma
Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:5123-5162, 2024.

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 to solve the resulting SDP efficiently in nearly-linear time in the size of the semi-random comparison graph.

Cite this Paper

BibTeX
@InProceedings{pmlr-v247-yang24b, title = {Top-$K$ ranking with a monotone adversary}, author = {Yang, Yuepeng and Chen, Antares and Orecchia, Lorenzo and Ma, Cong}, booktitle = {Proceedings of Thirty Seventh Conference on Learning Theory}, pages = {5123--5162}, year = {2024}, editor = {Agrawal, Shipra and Roth, Aaron}, volume = {247}, series = {Proceedings of Machine Learning Research}, month = {30 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v247/yang24b/yang24b.pdf}, url = {https://proceedings.mlr.press/v247/yang24b.html}, 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 to solve the resulting SDP efficiently in nearly-linear time in the size of the semi-random comparison graph.} }
Endnote
%0 Conference Paper %T Top-$K$ ranking with a monotone adversary %A Yuepeng Yang %A Antares Chen %A Lorenzo Orecchia %A Cong Ma %B Proceedings of Thirty Seventh Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2024 %E Shipra Agrawal %E Aaron Roth %F pmlr-v247-yang24b %I PMLR %P 5123--5162 %U https://proceedings.mlr.press/v247/yang24b.html %V 247 %X 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 to solve the resulting SDP efficiently in nearly-linear time in the size of the semi-random comparison graph.
APA
Yang, Y., Chen, A., Orecchia, L. & Ma, C.. (2024). Top-$K$ ranking with a monotone adversary. Proceedings of Thirty Seventh Conference on Learning Theory, in Proceedings of Machine Learning Research 247:5123-5162 Available from https://proceedings.mlr.press/v247/yang24b.html.

Related Material