Adaptive Sampling for Heterogeneous Rank Aggregation from Noisy Pairwise Comparisons

Yue Wu, Tao Jin, Hao Lou, Pan Xu, Farzad Farnoud, Quanquan Gu
Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, PMLR 151:11014-11036, 2022.

Abstract

In heterogeneous rank aggregation problems, users often exhibit various accuracy levels when comparing pairs of items. Thus, a uniform querying strategy over users may not be optimal. To address this issue, we propose an elimination-based active sampling strategy, which estimates the ranking of items via noisy pairwise comparisons from multiple users and improves the users’ average accuracy by maintaining an active set of users. We prove that our algorithm can return the true ranking of items with high probability. We also provide a sample complexity bound for the proposed algorithm, which outperforms the non-active strategies in the literature and close to oracle under mild conditions. Experiments are provided to show the empirical advantage of the proposed methods over the state-of-the-art baselines.

Cite this Paper

BibTeX
@InProceedings{pmlr-v151-wu22f, title = { Adaptive Sampling for Heterogeneous Rank Aggregation from Noisy Pairwise Comparisons }, author = {Wu, Yue and Jin, Tao and Lou, Hao and Xu, Pan and Farnoud, Farzad and Gu, Quanquan}, booktitle = {Proceedings of The 25th International Conference on Artificial Intelligence and Statistics}, pages = {11014--11036}, year = {2022}, editor = {Camps-Valls, Gustau and Ruiz, Francisco J. R. and Valera, Isabel}, volume = {151}, series = {Proceedings of Machine Learning Research}, month = {28--30 Mar}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v151/wu22f/wu22f.pdf}, url = {https://proceedings.mlr.press/v151/wu22f.html}, abstract = { In heterogeneous rank aggregation problems, users often exhibit various accuracy levels when comparing pairs of items. Thus, a uniform querying strategy over users may not be optimal. To address this issue, we propose an elimination-based active sampling strategy, which estimates the ranking of items via noisy pairwise comparisons from multiple users and improves the users’ average accuracy by maintaining an active set of users. We prove that our algorithm can return the true ranking of items with high probability. We also provide a sample complexity bound for the proposed algorithm, which outperforms the non-active strategies in the literature and close to oracle under mild conditions. Experiments are provided to show the empirical advantage of the proposed methods over the state-of-the-art baselines. } }
Endnote
%0 Conference Paper %T Adaptive Sampling for Heterogeneous Rank Aggregation from Noisy Pairwise Comparisons %A Yue Wu %A Tao Jin %A Hao Lou %A Pan Xu %A Farzad Farnoud %A Quanquan Gu %B Proceedings of The 25th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2022 %E Gustau Camps-Valls %E Francisco J. R. Ruiz %E Isabel Valera %F pmlr-v151-wu22f %I PMLR %P 11014--11036 %U https://proceedings.mlr.press/v151/wu22f.html %V 151 %X In heterogeneous rank aggregation problems, users often exhibit various accuracy levels when comparing pairs of items. Thus, a uniform querying strategy over users may not be optimal. To address this issue, we propose an elimination-based active sampling strategy, which estimates the ranking of items via noisy pairwise comparisons from multiple users and improves the users’ average accuracy by maintaining an active set of users. We prove that our algorithm can return the true ranking of items with high probability. We also provide a sample complexity bound for the proposed algorithm, which outperforms the non-active strategies in the literature and close to oracle under mild conditions. Experiments are provided to show the empirical advantage of the proposed methods over the state-of-the-art baselines.
APA
Wu, Y., Jin, T., Lou, H., Xu, P., Farnoud, F. & Gu, Q.. (2022). Adaptive Sampling for Heterogeneous Rank Aggregation from Noisy Pairwise Comparisons . Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 151:11014-11036 Available from https://proceedings.mlr.press/v151/wu22f.html.

Related Material