Sequential Mode Estimation with Oracle Queries
Abstract
We consider the problem of adaptively PAC-learning a probability distribution 𝒫's mode by querying an oracle for information about a sequence of i.i.d. samples X1, X2, … generated from 𝒫. We consider two different query models: (a) each query is an index i for which the oracle reveals the value of the sample Xi, (b) each query is comprised of two indices i and j for which the oracle reveals if the samples Xi and Xj are the same or not. For these query models, we give sequential mode-estimation algorithms which, at each time t, either make a query to the corresponding oracle based on past observations, or decide to stop and output an estimate for the distribution's mode, required to be correct with a specified confidence. We analyze the query complexity of these algorithms for any underlying distribution 𝒫, and derive corresponding lower bounds on the optimal query complexity under the two querying models.
Cite
Text
Shah et al. "Sequential Mode Estimation with Oracle Queries." AAAI Conference on Artificial Intelligence, 2020. doi:10.1609/AAAI.V34I04.6018Markdown
[Shah et al. "Sequential Mode Estimation with Oracle Queries." AAAI Conference on Artificial Intelligence, 2020.](https://mlanthology.org/aaai/2020/shah2020aaai-sequential/) doi:10.1609/AAAI.V34I04.6018BibTeX
@inproceedings{shah2020aaai-sequential,
title = {{Sequential Mode Estimation with Oracle Queries}},
author = {Shah, Dhruti and Choudhury, Tuhinangshu and Karamchandani, Nikhil and Gopalan, Aditya},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2020},
pages = {5644-5651},
doi = {10.1609/AAAI.V34I04.6018},
url = {https://mlanthology.org/aaai/2020/shah2020aaai-sequential/}
}