Publication Type

Conference Proceeding Article

Version

acceptedVersion

Publication Date

12-2015

Abstract

This paper discusses how to efficiently choose from $n$ unknown distributions the $k$ ones whose means are the greatest by a certain metric, up to a small relative error. We study the topic under two standard settings---multi-armed bandits and hidden bipartite graphs---which differ in the nature of the input distributions. In the former setting, each distribution can be sampled (in the i.i.d. manner) an arbitrary number of times, whereas in the latter, each distribution is defined on a population of a finite size $m$ (and hence, is fully revealed after m samples). For both settings, we prove lower bounds on the total number of samples needed, and propose optimal algorithms whose sample complexities match those lower bounds.

Discipline

Databases and Information Systems

Research Areas

Data Science and Engineering; Intelligent Systems and Optimization

Publication

NIPS'15: Proceedings of the 28th International Conference on Neural Information Processing Systems, Montreal Canada, 2015 December 7-12

Volume

1

First Page

1036

Last Page

1044

ISBN

9781510825024

Identifier

10.5555/2969239.2969355

Publisher

Neural Information Processing Systems Foundation

City or Country

Montreal, Canada

Additional URL

https://doi.org/10.5555/2969239.2969355

Download

Share

COinS