<p>From the <a href="https://en.wikipedia.org/wiki/Dvoretzky%E2%80%93Kiefer%E2%80%93Wolfowitz_inequality" rel="nofollow noreferrer">DKW inequality</a>, it follows one can learn an arbitrary distribution over <span class="math-container">$\mathbb{R}$</span> (and in particular over <span class="math-container">$\{1,2,\dots,n\}$</span> to Kolmogorov distance* <span class="math-container">$\varepsilon$</span> with probability at least <span class="math-container">$1-\delta$</span> using
<span class="math-container">$$
O\!\left(\frac{1}{\varepsilon^2}\log\frac{1}{\delta}\right)$$</span> samples; which is optimal in view of the complexity of learning even a single Bernoulli (biased coin): embed the biased coin (with bias either <span class="math-container">$1/2+\varepsilon$</span> or <span class="math-container">$1/2-\varepsilon$</span>) 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.</p>
<p>This implies the same upper (and lower) bounds for your question, where <span class="math-container">$\varepsilon$</span> is defined as the gap <em>(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).</em></p>
<p><span class="math-container">$*$</span> Kolmgorov distance is <span class="math-container">$\ell_\infty$</span> distance between CDFs. This guarantee is stronger (and implies) learning the pdf in <span class="math-container">$\ell_\infty$</span>. For more, see. e.g., this <a href="https://arxiv.org/abs/2002.11457" rel="nofollow noreferrer">short note of mine</a>, specifically Section 4 (not new results, just exposition of &quot;folklore&quot; facts)</p>

CC BY-SA 4.0
2022-05-20T05:27:23.183Z
isn't $\Omega\left(\frac{1}{\epsilon^2}\log\frac{1}{\delta}\right)$ a lower bound for any $\mathcal{D}$?
mathworker21
CC BY-SA 4.0
2022-05-20T05:37:27.463Z
@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?
Clement C.
CC BY-SA 4.0
2022-05-20T06:02:56.627Z
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.
mathworker21
CC BY-SA 4.0
2022-05-20T12:47:27.927Z
@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:)
actcon
CC BY-SA 4.0
2022-05-20T13:08:40.157Z
@ClementC. After reading your cool answer, I became more ambitious and came up with a followup question (I updated the post). Are you aware of any nice lower bound on the problem? Any comment on the problem would be very thankful.
actcon
CC BY-SA 4.0
2022-05-21T02:10:34.110Z
@mathworker21 If one starts with a general distribution, the reduction I stated might depend on the relation between $\varepsilon$ (the gap) and $\max_i p_i$: this is because the $\Omega(1/\varepsilon^2)$ lower bound holds for a biased coin $1/2\pm\varepsilon$, but to distinguish, say $\varepsilon$ from $2\varepsilon$ the bound is only $\Theta(1/\varepsilon)$.
Clement C.
CC BY-SA 4.0
2022-05-21T02:11:22.800Z
@actcon I'd have to think about it -- that's a nice question!
Clement C.
CC BY-SA 4.0
2022-05-22T01:11:48.640Z
Erm, why the downvote? Is there something wrong with this answer?
Clement C.
CC BY-SA 4.0
2022-05-20T04:26:44.510Z
2022-05-20T12:26:13.057Z
2022-05-20T12:26:13.057Z
Clement C.
<p>Say we have a black-box access to a distribution <span class="math-container">$\mathcal{D}$</span> with finite support <span class="math-container">$\{1,2,...,n\}$</span> with probability mass function <span class="math-container">$i \mapsto p_i$</span>. <strong>How many samples of <span class="math-container">$\mathcal{D}$</span> are needed to learn the mode of <span class="math-container">$\mathcal{D}$</span>, i.e. the <span class="math-container">$j$</span> such that <span class="math-container">$p_j=\max\{p_i\}$</span>, (with error probability <span class="math-container">$\delta$</span>)?</strong> Is there any known lower bound? Any idea, comment, or reference will be very helpful.</p>
<ul>
<li>I know that <span class="math-container">$\Theta(\frac{1}{d_H^2} \log\frac{1}{\delta})$</span> samples are required regarding Hellinger distance of <span class="math-container">$\mathcal{D}=(p,1-p)$</span> and <span class="math-container">$\mathcal{D}'=(1-p,p)$</span> in the case of <span class="math-container">$n=2$</span>.</li>
<li>I proved an upper bound <span class="math-container">$O(\frac{1}{\varepsilon^2} \log \frac{n}{\delta})$</span> with standard Hoeffding bound, where <span class="math-container">$\varepsilon$</span> is the difference between the largest and the second largest among <span class="math-container">$p_i$</span>'s.</li>
</ul>
<hr />
<p>Update: I proved a lower bound <span class="math-container">$\Omega(\frac{1}{\gamma}\log\frac{1}{\delta})$</span> by reducing the problem to some <span class="math-container">$n=2$</span> case, where <span class="math-container">$\gamma=\min_i\left(1-2\sqrt{\frac{pp_i}{(p+p_i)^2}}\right)$</span> with <span class="math-container">$p$</span> being the mode. But, I still want to reduce the gap between upper and lower bounds.</p>
<hr />
<p>A followup question: Say we have a black-box access to a distribution <span class="math-container">$\mathcal{D}$</span> with finite support <span class="math-container">$A\cup B:=\{a_1,...,a_n\}\cup\{b_1,...,b_m\}$</span> with probability mass function <span class="math-container">$a_i \mapsto p_i$</span> and <span class="math-container">$b_i \mapsto q_i$</span>. <strong>How many samples of <span class="math-container">$\mathcal{D}$</span> are required to make sure the most frequent sample is in <span class="math-container">$A$</span> (with error probability <span class="math-container">$\delta$</span>)?</strong> For sanity, it is guaranteed that <span class="math-container">$A$</span> contains the mode of <span class="math-container">$\mathcal{D}$</span>.</p>
<ul>
<li>Following Clement's answer, I could prove an upper bound of <span class="math-container">$O(\frac{1}{\varepsilon^2}\log\frac{1}{\delta})$</span>, where <span class="math-container">$\varepsilon=\max\{p_i\}-\max\{q_i\}$</span>. However, a nice lower bound eluded me, mainly because reducing to a Bernoulli case does not seem to work in this case.</li>
</ul>

CC BY-SA 4.0
2022-05-19T13:51:05.370Z
Simultaneously cross-posted at https://mathoverflow.net/questions/422893/sample-complexity-lower-bound-to-learn-the-mode-the-value-with-the-highest-prob
Emil Jeřábek
CC BY-SA 4.0
2022-05-22T01:12:47.423Z
@EmilJeřábek It is no longer available there (deleted).
Clement C.
<lower-bounds><pr.probability><st.statistics><sample-complexity>
Sample complexity lower bound to learn the mode (the value with the highest probability) of a distribution with finite support
actcon
# Sample complexity lower bound to learn the mode (the value with the highest probability) of a distribution with finite support

(Asked by: username_0 on 2022-05-19)

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.

**Tags:** lower-bounds, pr.probability, st.statistics, sample-complexity

> **Comments:**
> **username_1**: Simultaneously cross-posted at https://mathoverflow.net/questions/422893/sample-complexity-lower-bound-to-learn-the-mode-the-value-with-the-highest-prob  
> **username_2**: @EmilJeřábek It is no longer available there (deleted).  

---

## 1 answers

### Answer by username_2 on 2022-05-20. Score: 1 | Accepted answer

From the [DKW inequality](https://en.wikipedia.org/wiki/Dvoretzky%E2%80%93Kiefer%E2%80%93Wolfowitz_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](https://arxiv.org/abs/2002.11457), specifically Section 4 (not new results, just exposition of "folklore" facts)

> **Comments:**
> **username_3**: isn't $\Omega\left(\frac{1}{\epsilon^2}\log\frac{1}{\delta}\right)$ a lower bound for any $\mathcal{D}$?  
> **username_2**: @username_3 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?  
> **username_3**: 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.  
> **username_0**: @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:)  
> **username_0**: @ClementC. After reading your cool answer, I became more ambitious and came up with a followup question (I updated the post). Are you aware of any nice lower bound on the problem? Any comment on the problem would be very thankful.  
> **username_2**: @username_3 If one starts with a general distribution, the reduction I stated might depend on the relation between $\varepsilon$ (the gap) and $\max_i p_i$: this is because the $\Omega(1/\varepsilon^2)$ lower bound holds for a biased coin $1/2\pm\varepsilon$, but to distinguish, say $\varepsilon$ from $2\varepsilon$ the bound is only $\Theta(1/\varepsilon)$.  
> **username_2**: @username_0 I'd have to think about it -- that's a nice question!  
> **username_2**: Erm, why the downvote? Is there something wrong with this answer?  

---

