Minimax Optimal Additive Functional Estimation with Discrete Distribution

This paper addresses a problem of estimating an additive functional given $n$ i.i.d. samples drawn from a discrete distribution $P=(p_1,\mathrm{.}\mathrm{.}\mathrm{.},p_k)$ with alphabet size $k$. The additive functional is defined as $\theta (P;\varphi )={\sum }_{i=1}^k\varphi (p_i)$ for a function $\varphi$, which covers the most of the entropy-like criteria. The minimax optimal risk of this problem has been already known for some specific $\varphi$, such as $\varphi (p)=p^{\alpha }$ and $\varphi (p)=-p\ln p$. However, there is no generic methodology to derive the minimax optimal risk for the additive function estimation problem. In this paper, we reveal the property of $\varphi$ that characterizes the minimax optimal risk of the additive functional estimation problem; this analysis is applicable to general $\varphi$. More precisely, we reveal that the minimax optimal risk of this problem is characterized by the divergence speed of the function $\varphi$.