<p>Clément Canonne and I worked this out at some point.</p>

<p>Let $X_j$ be the number of realizations of $j \in [d]$. So $\mathbb{E} X_j = np_j$.
\begin{align*}
  \mathbb{E} J_n^r &amp;= \mathbb{E} \|\hat{P}_n - P \|_r^r \\
    &amp;= \frac{1}{n^r} \sum_{j=1}^d \mathbb{E} |X_j - \mathbb{E}X_j|^r  \\
    &amp;\leq \frac{1}{n^r} \sum_{j=1}^d 3\mathbb{E} X_j  &amp; (*)  \\
    &amp;= \frac{3}{n^{r-1}} .
\end{align*}
We get $(*)$ by a slightly tedious argument you can find in Theorem 5.1 of [1] or I can add here later. It just uses the extreme cases of $r=1$ or $r=2$.</p>

<p>In particular this gives a dimension-free bound. However, one can get a dimension-dependent upper bound simply by using the standard $p$-norm inequalities and the upper bound on the $2$-norm that you state. The dimension-dependent bounds will be better when the dimension is small relative to the number of observations, I believe when $d \leq O(n^{1/q})$ but will have to double-check (where $q = 1 - 1/r$).</p>

<p>[1]:  "$\ell_p$ Testing and Learning of Discrete Distributions" (Bo Waggoner, ITCS 2015), <a href="https://arxiv.org/abs/1412.2314" rel="nofollow noreferrer">https://arxiv.org/abs/1412.2314</a></p>

CC BY-SA 3.0
2017-11-30T18:15:43.530Z
2017-11-30T18:15:43.530Z
usul
<p>Let $P=(p_1,\ldots,p_d)$ be a distribution on $[d]$. Given $n$ iid draws from $P$, we construct some empirical estimate 
$\hat P_n=(\hat p_{n,1},\ldots,\hat p_{n,d})$. Let us define the $r$-risk
by
$$ J_n^r = \sum_{i=1}^d |p_i-\hat p_{n,i}|^r.
$$</p>

<p>It is known (see, e.g., Lemma 2.4 <a href="https://projecteuclid.org/euclid.jap/1421763330" rel="nofollow noreferrer">here</a>) 
that when $\hat P_n$ is the maximum likelihood (i.e., empirical frequency) estimator
and $r\ge2$,
we have
$\mathbb{E}[J_n^r]\le1/n$. In particular, the expected $r$-risk decays at a dimension-free rate.</p>

<p>It is also known that for $r=1$, the risk decays at a minimax rate of $\Theta(\sqrt{d/n})$.</p>

<p>Question: what is known for $1&lt;r&lt;2$?</p>

CC BY-SA 3.0
2017-11-30T19:32:52.287Z
Out of curiosity: in what context does this question arise?
Clement C.
CC BY-SA 3.0
2017-11-30T20:15:56.657Z
A natural interpolation between known results.
Aryeh
<machine-learning><lg.learning><st.statistics>
Learning a discrete distribution in $\ell_r$ norm
Aryeh
# Learning a discrete distribution in $\ell_r$ norm

(Asked by: username_0 on 2017-11-30)

Let $P=(p\_1,\ldots,p\_d)$ be a distribution on $[d]$. Given $n$ iid draws from $P$, we construct some empirical estimate
$\hat P\_n=(\hat p\_{n,1},\ldots,\hat p\_{n,d})$. Let us define the $r$-risk
by
$$ J\_n^r = \sum\_{i=1}^d |p\_i-\hat p\_{n,i}|^r.
$$

It is known (see, e.g., Lemma 2.4 [here](https://projecteuclid.org/euclid.jap/1421763330))
that when $\hat P\_n$ is the maximum likelihood (i.e., empirical frequency) estimator
and $r\ge2$,
we have
$\mathbb{E}[J\_n^r]\le1/n$. In particular, the expected $r$-risk decays at a dimension-free rate.

It is also known that for $r=1$, the risk decays at a minimax rate of $\Theta(\sqrt{d/n})$.

Question: what is known for $1

**Tags:** machine-learning, lg.learning, st.statistics

> **Comments:**
> **username_1**: Out of curiosity: in what context does this question arise?  
> **username_0**: A natural interpolation between known results.  

---

## 1 answers

### Answer by username_2 on 2017-11-30. Score: 2 | Accepted answer

Clément Canonne and I worked this out at some point.

Let $X\_j$ be the number of realizations of $j \in [d]$. So $\mathbb{E} X\_j = np\_j$.
\begin{align\*}
\mathbb{E} J\_n^r &= \mathbb{E} \|\hat{P}\_n - P \|\_r^r \\
&= \frac{1}{n^r} \sum\_{j=1}^d \mathbb{E} |X\_j - \mathbb{E}X\_j|^r \\
&\leq \frac{1}{n^r} \sum\_{j=1}^d 3\mathbb{E} X\_j & (\*) \\
&= \frac{3}{n^{r-1}} .
\end{align\*}
We get $(\*)$ by a slightly tedious argument you can find in Theorem 5.1 of [1] or I can add here later. It just uses the extreme cases of $r=1$ or $r=2$.

In particular this gives a dimension-free bound. However, one can get a dimension-dependent upper bound simply by using the standard $p$-norm inequalities and the upper bound on the $2$-norm that you state. The dimension-dependent bounds will be better when the dimension is small relative to the number of observations, I believe when $d \leq O(n^{1/q})$ but will have to double-check (where $q = 1 - 1/r$).

[1]: "$\ell\_p$ Testing and Learning of Discrete Distributions" (Bo Waggoner, ITCS 2015), <https://arxiv.org/abs/1412.2314>


---

