Sequential Mode Estimation with Oracle Queries

We consider the problem of adaptively PAC-learning a probability distribution P’s mode by querying an oracle for information about a sequence of i. i. d. samples X1, X2, .. . generated from P. 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 con- fidence. We analyze the query complexity of these algorithms for any underlying distribution P, and derive corresponding lower bounds on the optimal query complexity under the two querying models.

Authors

• Dhruti Shah
• Tuhinangshu Choudhury
• Nikhil Karamchandani Indian Institute of Technology Bombay
• Aditya Gopalan

Keywords

No keywords are indexed for this paper.