Adaptive Sampling for Coarse Ranking

Sumeet Katariya, Lalit Jain, Nandana Sengupta, James Evans, Robert Nowak
Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, PMLR 84:1839-1848, 2018.

Abstract

We consider the problem of active coarse ranking, where the goal is to sort items according to their means into clusters of pre-specified sizes, by adaptively sampling from their reward distributions. This setting is useful in many social science applications involving human raters and the approximate rank of every item is desired. Approximate or coarse ranking can significantly reduce the number of ratings required in comparison to the number needed to find an exact ranking. We propose a computationally efficient PAC algorithm LUCBRank for coarse ranking, and derive an upper bound on its sample complexity. We also derive a nearly matching distribution-dependent lower bound. Experiments on synthetic as well as real-world data show that LUCBRank performs better than state-of-the-art baseline methods, even when these methods have the advantage of knowing the underlying parametric model.

Cite this Paper

BibTeX
@InProceedings{pmlr-v84-katariya18a, title = {Adaptive Sampling for Coarse Ranking}, author = {Katariya, Sumeet and Jain, Lalit and Sengupta, Nandana and Evans, James and Nowak, Robert}, booktitle = {Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics}, pages = {1839--1848}, year = {2018}, editor = {Storkey, Amos and Perez-Cruz, Fernando}, volume = {84}, series = {Proceedings of Machine Learning Research}, month = {09--11 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v84/katariya18a/katariya18a.pdf}, url = {https://proceedings.mlr.press/v84/katariya18a.html}, abstract = {We consider the problem of active coarse ranking, where the goal is to sort items according to their means into clusters of pre-specified sizes, by adaptively sampling from their reward distributions. This setting is useful in many social science applications involving human raters and the approximate rank of every item is desired. Approximate or coarse ranking can significantly reduce the number of ratings required in comparison to the number needed to find an exact ranking. We propose a computationally efficient PAC algorithm LUCBRank for coarse ranking, and derive an upper bound on its sample complexity. We also derive a nearly matching distribution-dependent lower bound. Experiments on synthetic as well as real-world data show that LUCBRank performs better than state-of-the-art baseline methods, even when these methods have the advantage of knowing the underlying parametric model.} }
Endnote
%0 Conference Paper %T Adaptive Sampling for Coarse Ranking %A Sumeet Katariya %A Lalit Jain %A Nandana Sengupta %A James Evans %A Robert Nowak %B Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2018 %E Amos Storkey %E Fernando Perez-Cruz %F pmlr-v84-katariya18a %I PMLR %P 1839--1848 %U https://proceedings.mlr.press/v84/katariya18a.html %V 84 %X We consider the problem of active coarse ranking, where the goal is to sort items according to their means into clusters of pre-specified sizes, by adaptively sampling from their reward distributions. This setting is useful in many social science applications involving human raters and the approximate rank of every item is desired. Approximate or coarse ranking can significantly reduce the number of ratings required in comparison to the number needed to find an exact ranking. We propose a computationally efficient PAC algorithm LUCBRank for coarse ranking, and derive an upper bound on its sample complexity. We also derive a nearly matching distribution-dependent lower bound. Experiments on synthetic as well as real-world data show that LUCBRank performs better than state-of-the-art baseline methods, even when these methods have the advantage of knowing the underlying parametric model.
APA
Katariya, S., Jain, L., Sengupta, N., Evans, J. & Nowak, R.. (2018). Adaptive Sampling for Coarse Ranking. Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 84:1839-1848 Available from https://proceedings.mlr.press/v84/katariya18a.html.

Related Material