Skip to main content

Adaptive Sampling for Heterogeneous Rank Aggregation from Noisy Pairwise Comparisons

Publication ,  Conference
Wu, Y; Jin, T; Lou, H; Xu, P; Farnoud, F; Gu, Q
Published in: Proceedings of Machine Learning Research
January 1, 2022

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.

Duke Scholars

Published In

Proceedings of Machine Learning Research

EISSN

2640-3498

Publication Date

January 1, 2022

Volume

151

Start / End Page

11014 / 11036
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Wu, Y., Jin, T., Lou, H., Xu, P., Farnoud, F., & Gu, Q. (2022). Adaptive Sampling for Heterogeneous Rank Aggregation from Noisy Pairwise Comparisons. In Proceedings of Machine Learning Research (Vol. 151, pp. 11014–11036).
Wu, Y., T. Jin, H. Lou, P. Xu, F. Farnoud, and Q. Gu. “Adaptive Sampling for Heterogeneous Rank Aggregation from Noisy Pairwise Comparisons.” In Proceedings of Machine Learning Research, 151:11014–36, 2022.
Wu Y, Jin T, Lou H, Xu P, Farnoud F, Gu Q. Adaptive Sampling for Heterogeneous Rank Aggregation from Noisy Pairwise Comparisons. In: Proceedings of Machine Learning Research. 2022. p. 11014–36.
Wu, Y., et al. “Adaptive Sampling for Heterogeneous Rank Aggregation from Noisy Pairwise Comparisons.” Proceedings of Machine Learning Research, vol. 151, 2022, pp. 11014–36.
Wu Y, Jin T, Lou H, Xu P, Farnoud F, Gu Q. Adaptive Sampling for Heterogeneous Rank Aggregation from Noisy Pairwise Comparisons. Proceedings of Machine Learning Research. 2022. p. 11014–11036.

Published In

Proceedings of Machine Learning Research

EISSN

2640-3498

Publication Date

January 1, 2022

Volume

151

Start / End Page

11014 / 11036