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$?

  • $\begingroup$ Out of curiosity: in what context does this question arise? $\endgroup$
    – Clement C.
    Commented Nov 30, 2017 at 19:32
  • $\begingroup$ A natural interpolation between known results. $\endgroup$
    – Aryeh
    Commented Nov 30, 2017 at 20:15

1 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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.