Learning a discrete distribution in $\ell_r$ norm

Question

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) 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<r<2$?

Answer 1

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