# Sample complexity lower bound to learn the mode (the value with the highest probability) of a distribution with finite support

Say we have a black-box access to a distribution $$\mathcal{D}$$ with finite support $$\{1,2,...,n\}$$ with probability mass function $$i \mapsto p_i$$. How many samples of $$\mathcal{D}$$ are needed to learn the mode of $$\mathcal{D}$$, i.e. the $$j$$ such that $$p_j=\max\{p_i\}$$, (with error probability $$\delta$$)? Is there any known lower bound? Any idea, comment, or reference will be very helpful.

• I know that $$\Theta(\frac{1}{d_H^2} \log\frac{1}{\delta})$$ samples are required regarding Hellinger distance of $$\mathcal{D}=(p,1-p)$$ and $$\mathcal{D}'=(1-p,p)$$ in the case of $$n=2$$.
• I proved an upper bound $$O(\frac{1}{\varepsilon^2} \log \frac{n}{\delta})$$ with standard Hoeffding bound, where $$\varepsilon$$ is the difference between the largest and the second largest among $$p_i$$'s.

Update: I proved a lower bound $$\Omega(\frac{1}{\gamma}\log\frac{1}{\delta})$$ by reducing the problem to some $$n=2$$ case, where $$\gamma=\min_i\left(1-2\sqrt{\frac{pp_i}{(p+p_i)^2}}\right)$$ with $$p$$ being the mode. But, I still want to reduce the gap between upper and lower bounds.

A followup question: Say we have a black-box access to a distribution $$\mathcal{D}$$ with finite support $$A\cup B:=\{a_1,...,a_n\}\cup\{b_1,...,b_m\}$$ with probability mass function $$a_i \mapsto p_i$$ and $$b_i \mapsto q_i$$. How many samples of $$\mathcal{D}$$ are required to make sure the most frequent sample is in $$A$$ (with error probability $$\delta$$)? For sanity, it is guaranteed that $$A$$ contains the mode of $$\mathcal{D}$$.

• Following Clement's answer, I could prove an upper bound of $$O(\frac{1}{\varepsilon^2}\log\frac{1}{\delta})$$, where $$\varepsilon=\max\{p_i\}-\max\{q_i\}$$. However, a nice lower bound eluded me, mainly because reducing to a Bernoulli case does not seem to work in this case.
• Simultaneously cross-posted at mathoverflow.net/questions/422893/… May 19 at 13:51
• @EmilJeřábek It is no longer available there (deleted). May 22 at 1:12

## 1 Answer

From the DKW inequality, it follows one can learn an arbitrary distribution over $$\mathbb{R}$$ (and in particular over $$\{1,2,\dots,n\}$$ to Kolmogorov distance* $$\varepsilon$$ with probability at least $$1-\delta$$ using $$O\!\left(\frac{1}{\varepsilon^2}\log\frac{1}{\delta}\right)$$ samples; which is optimal in view of the complexity of learning even a single Bernoulli (biased coin): embed the biased coin (with bias either $$1/2+\varepsilon$$ or $$1/2-\varepsilon$$) in the middle of the domain, where all other elements have mass 0: figuring out which element is the mode corresponds to figuring out the bias.

This implies the same upper (and lower) bounds for your question, where $$\varepsilon$$ is defined as the gap (assuming you have a priori knowledge on that gap; this is not quite apparent from your post. If not, doing something adaptive and slightly more involved might be required).

$$*$$ Kolmgorov distance is $$\ell_\infty$$ distance between CDFs. This guarantee is stronger (and implies) learning the pdf in $$\ell_\infty$$. For more, see. e.g., this short note of mine, specifically Section 4 (not new results, just exposition of "folklore" facts)

• isn't $\Omega\left(\frac{1}{\epsilon^2}\log\frac{1}{\delta}\right)$ a lower bound for any $\mathcal{D}$? May 20 at 5:27
• @mathworker21 yes, you can start with any distribution and embed the corresponding biased coin problem (with a suitable $\varepsilon$) in there. Is that what you mean? May 20 at 5:37
• By "what you mean", do you mean "what you had in mind for a proof"? I meant what I asked, namely if $\Omega(\epsilon^{-2}\log\delta^{-1})$ is always a lower bound; it seems you agree that is always a lower bound. May 20 at 6:02
• @ClementC. Wow, thank you for your answer! And also writing up folklores. It really helps non-specialists like me. Actually, this question was already inspired by your note on distinguishing discrete distributions:) May 20 at 12:47
• Erm, why the downvote? Is there something wrong with this answer? May 22 at 1:11