Adaptive Estimation of Shannon Entropy

I Introduction

is one of the most fundamental quantities of information theory and statistics, which emerged in Shannon’s 1948 masterpiece as the answer to foundational questions of compression and communication.

Consider the problem of estimating Shannon entropy $H(P)$ from $n$ i.i.d. samples. Classical theory is mainly concerned with the case where the number of samples $n\to\infty$, while the support size $S$ is fixed. In that scenario, the maximum likelihood estimator (MLE), $H(P_{n})$, which plugs in the empirical distribution into the definition of entropy, is asymptotically efficient [2, Thm. 8.11, Lemma 8.14] in the sense of the Hájek convolution theorem and the Hájek–Le Cam local asymptotic minimax theorem . It is therefore not surprising to encounter the following quote from the introduction of Wyner and Foster who considered entropy estimation:

“The plug-in estimate is universal and optimal not only for finite alphabet i.i.d. sources but also for finite alphabet, finite memory sources. On the other hand, practically as well as theoretically, these problems are of little interest. ”

In contrast, various modern data-analytic applications deal with datasets which do not fall into the regime of fixed alphabet and $n\to\infty$. In fact, in many applications the support size $S$ is comparable to, or even larger than the number of samples $n$.

Corpus linguistics: about half of the words in the Shakespearean canon appeared only once .

Network traffic analysis: many customers or website users are seen a small number of times .

Analyzing neural spike trains: natural stimuli generate neural responses of high timing precision resulting in a massive space of meaningful responses .

The problem of entropy estimation in the large alphabet regime (or non-asymptotic analysis) has been investigated extensively in various disciplines, which we refer to for a detailed review. One recent breakthrough in this direction came from Valiant and Valiant , who constructed the first explicit entropy estimator whose sample complexity is $n\asymp\frac{S}{\ln S}$ samples, which they also proved to be necessary. It was also shown in that the MLE requires $n\asymp S$ samples, implying that MLE is strictly sub-optimal in terms of sample complexity.

However, the aforementioned estimators have not been shown to achieve the minimax $L_{2}$ rates. In light of this, Wu and Yang and Jiao et al. independently developed schemes based on approximation theory that achieved the minimax $L_{2}$ convergence rates for the entropy. Furthermore, Jiao et al. proposed a general methodology for estimating functionals, and showed that for a wide class of functionals (including entropy, mutual information, and power sum functionals), their methodology leads to minimax rate-optimal estimators whose performance with $n$ samples is essentially that of the MLE with $n\ln n$ samples. The approximation ideas proved to be very fruitful in Acharya et al. , Wu and Yang , Han, Jiao, and Weissman , Jiao, Han, and Weissman , Bu et al. , Orlitsky, Suresh, and Wu , Wu and Yang .

On the practical side, Jiao et al. showed that the minimax rate-optimal estimators introduced in can lead to consistent and substantial performance boosts in various machine learning algorithms.

I-B Refined minimaxity: adaptive estimation

The primary approach to alleviate the pessimism of minimaxity in statistics is the construction of adaptive procedures, which has gained particular prominence in nonparametric statistics . The goal of adaptive inference is to construct a single procedure that achieves optimality simultaneously over a collection of parameter spaces. Informally, an adaptive procedure automatically adjusts to the unknown parameter, and acts as if it knows the parameter lies in a more restricted subset of the whole parameter space. A common way to evaluate such a procedure is to compare its maximum risk over each subset of the parameter space in the collection with the corresponding minimax risk. If they are nearly equal, then we say such a procedure is adaptive with respect to that collection of subsets of the parameter space.

The primary results of this paper are twofold.

First, we show that the minimax rate-optimal entropy estimator in Jiao et al. is adaptive with respect to the collection of parameter space $\mathcal{M}_{S}(H)$, where $\mathcal{M}_{S}(H)\triangleq\{P:H(P)\leq H,P\in\mathcal{M}_{S}\}$. Moreover, the estimator does not need to know $S$ nor $H$, which is an advantage in practice since usually the support size $S$ nor an a priori upper bound on the true entropy $H(P)$ are known.

Second, we show that the sample size enlargement effect still holds in this adaptive estimation scenario. Table I demonstrates that in estimating various functionals, the performance of the minimax rate-optimal estimator with $n$ samples is nearly that of the MLE with $n\ln n$ samples, which the authors termed “effective sample size enlargement” in . We compute the maximum risk of the MLE over each $\mathcal{M}_{S}(H)$, and show that for every $H$, the performance of the estimator in with $n$ samples is still nearly that of the MLE with $n\ln n$ samples.

These facts suggest that the estimator in Jiao et al. is near optimal in a very strong sense, for which we refer the readers to for a detailed discussion on methodology behind their estimator, literature survey, and experimental results.

I-C Mathematical framework and estimator construction

Before we discuss the main results, we would like to recall the construction of the entropy estimator in . The approach is to tackle the estimation problem separately for the cases of “small $p$” and “large $p$” in $H(P)$ estimation, corresponding to treating regions where the functional is “nonsmooth” and “smooth” in different ways. Specifically, after we obtain the empirical distribution $P_{n}$, for each coordinate $P_{n}(i)$, if $P_{n}(i)\ll\ln n/n$, we (i) compute the best polynomial approximation for $-p_{i}\ln p_{i}$ in the regime $0\leq p_{i}\ll\ln n/n$, (ii) use the unbiased estimators for integer powers $p_{i}^{k}$ to estimate the corresponding terms in the polynomial approximation for $-p_{i}\ln p_{i}$ up to order $K_{n}\sim\ln n$, and (iii) use that polynomial as an estimate for $-p_{i}\ln p_{i}$. If $P_{n}(i)\gg\ln n/n$, we use the estimator $-P_{n}(i)\ln P_{n}(i)+\frac{1}{2n}$ to estimate $-p_{i}\ln p_{i}$. Then, we add the estimators corresponding to each coordinate.

We define the minimax risk for Multinomial model with $n$ observations on support size $S$ for estimating $H(P),P\in\mathcal{M}_{S}(H)$ as

which is the quantity we will characterize in this paper. To simplify the analysis, we also utilize the Poisson sampling model, i.e., we first draw a random variable $N\sim\mathsf{Poi}(n)$, and then obtain $N$ samples from the distribution $P$. It is equivalent to having a $S$-dimensional random vector $\mathbf{Z}$ such that each component $Z_{i}$ in $\mathbf{Z}$ has distribution $\mathsf{Poi}(np_{i})$, and all coordinates of $\mathbf{Z}$ are independent.

The counterpart of minimax risk in the Poissonized model is defined as

The following lemma, which follows from , shows that the minimax risks under the Multinomial model and the Poissonized model are essentially equivalent.

The minimax risks under the Poissonized model and the Multinomial model are related via the following inequalities:

For simplicity, we re-define $n/2$ as $n$, and denote

The estimator $\hat{H}$ in Jiao et al. is constructed as follows.

We explain each equation in detail as follows.

Equation (8): Note that $\hat{p}_{i,1}$ and $\hat{p}_{i,2}$ are i.i.d. random variables such that $n\hat{p}_{i,1}\sim\mathsf{Poi}(np_{i})$. We use $\hat{p}_{i,2}$ to determine whether we are operating in the “nonsmooth” regime or not. If $\hat{p}_{i,2}\leq 2\Delta$, we declare we are in the “nonsmooth” regime, and plug in $\hat{p}_{i,1}$ into function $L_{H}(\cdot)$. If $\hat{p}_{i,2}>2\Delta$, we declare we are in the “smooth” regime, and plug in $\hat{p}_{i,1}$ into $U_{H}(\cdot)$.

The coefficients $r_{k,H},0\leq k\leq K$ are coefficients of the best polynomial approximation of $-x\ln x$ over $$up to degree$K$, i.e.,

where $\mathsf{poly}_{K}$ denotes the set of algebraic polynomials up to order $K$. Note that in general $g_{k,\alpha}$ depends on $K$, which we do not make explicit for brevity.

Then we define $\{g_{k,H}\}_{1\leq k\leq K}$

Lemma 9 shows that for $nX\sim\mathsf{Poi}(np)$,

is a near-best polynomial approximation for $-p\ln p$ on $[0,4\Delta]$. Thus, we can understand $S_{K,H}(X),nX\sim\mathsf{Poi}(np)$ as a random variable whose expectation is nearly Note that we have removed the constant term from the best polynomial approximation. It is to ensure that we assign zero to symbols we do not see. the best approximation of function $-x\ln x$ over $[0,4\Delta]$.

Any reasonable estimator for $-p\ln p$ should be upper bounded by the value one. We cutoff $S_{K,H}(x)$ by upper bound $1$, and define the function $L_{H}(x)$, which means “lower part”.

The function $U_{H}(x)$ (means “upper part”) is nothing but a product of an interpolation function $I_{n}(x)$ and the bias-corrected MLE. The interpolation function $I_{n}(x)$ is defined as follows:

The following lemma characterizes the properties of the function $g(x;a)$ appearing in the definition of $I_{n}(x)$. In particular, it shows that $I_{n}(x)\in C^{4}$.

For the function $g(x;a)$ on $[0,a]$ defined as follows,

The function $g(x;1)$ is depicted in Figure 1. As pointed out in , it is not necessary to use the interpolation function to achieve the minimax rates. Here we keep it in order to be consistent with .

II Main Results

Since $\sup_{P\in\mathcal{M}_{S}}H(P)=\ln S$, we assume throughout this paper that $0<H\leq\ln S$. Denote by $\mathcal{M}_{S}(H)$ the set of all discrete probability distributions $P$ with support size $|\mathsf{supp}(P)|=S$ and entropy $H(P)\leq H$. We say an estimator $\hat{H}\equiv\hat{H}(\mathbf{Z})$ is within accuracy $\epsilon>0$, if and only if

For the plug-in estimator $H(P_{n})$, the following theorem presents the non-asymptotic upper and lower bounds for the $L_{2}$ risk.

If $H\geq H_{0}>0$, where $H_{0}$ is a universal positive constant, then for the plug-in estimator $H(P_{n})$, we have

Note that the only assumption in Theorem 1 is that the upper bound $H$ should be no smaller than a constant, which is a reasonable assumption to avoid the subtle case where the naive zero estimator $\hat{H}\equiv 0$ has a satisfactory performance. The minimum sample complexity of the plug-in approach can be immediately obtained from Theorem 1.

If $H\geq H_{0}>0$, where $H_{0}$ is a universal positive constant, the plug-in estimator $H(P_{n})$ is within accuracy $\epsilon$ if and only if

Recall that it requires $n\gtrsim\frac{S}{\epsilon}\vee\frac{\ln^{2}S}{\epsilon^{2}}$ samples for the MLE to achieve accuracy $\epsilon$ when there is no constraint on the entropy . Hence, when the upper bound on the entropy is loose, i.e., $H\asymp\ln S$, the minimum sample complexity in the bounded entropy case is exactly the same, i.e., we cannot essentially improve the estimation performance. On the other hand, when the upper bound is tight, i.e., $H\ll\ln S$, the required sample complexity enjoyed a significant reduction.

When it comes to the maximum $L_{2}$ risk, we conclude from Theorem 1 that the bounded entropy property helps only at the boundary, i.e., when $n$ is close to $S$ and $H$ is small. Moreover, this help vanishes quickly as $S$ increases: when $n=S^{1-\delta}$, the maximum $L_{2}$ risk will be at the order $(\delta H)^{2}$, and the naive zero estimator achieves worst case risk $H^{2}$.

Is the plug-in estimator $H(P_{n})$ optimal in the minimax sense? It has been shown in that when there is no constraint on $H(P)$, i.e., $H=\ln S$, the answer is negative. What about subsets of $\mathcal{M}_{S}$, such as $\mathcal{M}_{S}(H)$? The following theorem characterizes the minimax $L_{2}$ rates over $\mathcal{M}_{S}(H)$.

If $H\geq H_{0}>0$, where $H_{0}$ is a universal positive constant, then

where the infimum is taken over all possible estimators. Moreover, the upper bound is achieved by the estimator $\hat{H}^{*}$ in under the Poissonized model without the knowledge of $H$ nor $S$, and in particular,

An immediate result on the sample complexity is as follows.

If $H\geq H_{0}>0$, where $H_{0}$ is a universal positive constant, the minimax rate-optimal estimator in is within accuracy $\epsilon$ if

For the minimum sample complexity, we still distinguish $H$ into two cases. Firstly, when $H\asymp\ln S$, the required sample complexity is $n\asymp\frac{S}{\epsilon\ln S}$, which recovers the minimax results with no constraint on entropy in . Secondly, when $H\ll\ln S$, there is a significant improvement.

We conjecture that the minimax rates in Theorem 2 can be refined to

In other words, we conjecture that the exact constant in the minimax rates in the regime $S\ln S>e^{2}nH\ln n$ is $\frac{1}{2}$. It is partially justified by the observation that the minimax squared error without any samples is $(H/2)^{2}$.

We also conclude from Theorem 2 that the bounded entropy constraint again helps only at the boundary, and this help vanishes quickly as $S$ increases: when $n=S^{1-\delta}$, we do not have sufficient information to make inference, and the naive zero estimator is near-minimax.

If $H\geq H_{0}>0$, where $H_{0}$ is a universal positive constant, then for the hard-thresholding estimator $P_{s}$ in , the plug-in estimator $H(P_{s})$ satisfies

The proof is completed by the proof of the lower bound in Theorem 1 (cf. Section IV). ∎

To sum up, we have obtained the following conclusions.

The minimax rate-optimal entropy estimator in Jiao et al. is adaptive with respect to the collection of parameter space $\mathcal{M}_{S}(H)$, where $\mathcal{M}_{S}(H)\triangleq\{P:H(P)\leq H,P\in\mathcal{M}_{S}\}$. Moreover, the estimator does not need to know $S$ nor $H$, which is an advantage in practice since usually the support size $S$ nor an a priori upper bound on the true entropy $H(P)$ are known.

Second, the sample size enlargement effect still holds in this adaptive estimation scenario. Table I demonstrates that in estimating various functionals, the performance of the minimax rate-optimal estimator with $n$ samples is essentially that of the MLE with $n\ln n$ samples, which the authors termed “sample size enlargement” in . Theorems 1 and 2 show that over every $\mathcal{M}_{S}(H)$, the performance of the estimator in with $n$ samples is still essentially that of the MLE with $n\ln n$ samples.

III Proof of Upper Bounds in Theorem 1

First we consider the case where $S\ln S\leq e^{2}nH$. For the bias, it has been shown in that

As for the variance, shows that by the Efron-Stein inequality, we have

For any discrete distribution $P=(p_{1},p_{2},\cdots,p_{S})$, we have

where we have used the assumption $H\geq H_{0}>0$ in the last step.

Hence, when $S\ln S\leq e^{2}nH$, we have

which completes the proof for the first part. For the second part, we introduce a lemma first.

Given $n\geq 2$. For $p\leq\frac{1}{n}$ and $n\hat{p}\sim\mathsf{B}(n,p)$, we have

Define $f(x)=-x\ln x$ on $$. We also know that$\left|\mathsf{Bias}\left(f(\hat{p}_{i})\right)\right|\leq\frac{1}{n}$holds for all$i$ . In light of the previous result and Lemma 4, we have

Now we bound $B_{1},B_{2},B_{3}$ separately. By the concavity of $f(\cdot)$ we have

where $f^{-1}(\cdot)$ denotes the inverse of $f(\cdot)$, and we restrict $f^{-1}(\cdot)\in[0,e^{-1}]$ to avoid possible ambiguities. It is straightforward to verify that for any $a>0$ and $0<x_{1}\leq x_{2}<1/(ea)$, we have

We summarize some more properties of $f^{-1}(\cdot)$ in the following lemma.

Combining these properties of $f^{-1}(\cdot)$ yields

where (50) follows from (45), (51) follows from (46), (52) follows from (47) and

by assumption, and the last equality follows from (48).

Now we proceed to bound $B_{2}$, which is given by

As for $B_{3}$, due to the concavity of $f(\cdot)$, the minimum of $\sum_{i:p_{i}>\frac{1}{n}}f(p_{i})$ is attained when all but one $p_{i}$ are at the boundary $p_{i}=\frac{1}{n}$, hence

where the last inequality is obtained by separating two cases $S>n^{\beta}$ and $S\leq n^{\beta}$ for some constant $\beta>1$, say, $\beta=2$. The proof is completed by noticing that :

IV Proof of Lower Bounds in Theorem 1

We first derive a lower bound for the bias term. We recall the following result in .

where we have used the assumption $S\ln S\leq e^{2}nH$ and $H\geq H_{0}>0$ in the last inequality. Hence, we have proved that

For the lower bound in the case where $S\ln S>e^{2}nH$, we consider another distribution

where $A\in(0,1)$ is the solution to the equation

The lower bounds in Theorem 1 for the bias part can thus be established by combining (68) and (74).

We now turn to the lower bound for variance. We will actually prove a stronger result: a minimax lower bound for all estimators for the $L_{2}$ risk, which naturally is also a lower bound for the maximum risk of the MLE. We use Le Cam’s two-point method here. Suppose we observe a random vector ${\bf Z}\in(\mathcal{Z},\mathcal{A})$ which has distribution $P_{\theta}$ where $\theta\in\Theta$. Let $\theta_{0}$ and $\theta_{1}$ be two elements of $\Theta$. Let $\hat{T}=\hat{T}({\bf Z})$ be an arbitrary estimator of a function $T(\theta)$ based on $\bf Z$. We have the following general minimax lower bound.

[28, Sec. 2.4.2] Denoting the Kullback-Leibler divergence between $P$ and $Q$ by

Applying this lemma to the Poissonized model $n\hat{p}_{i}\sim\mathsf{Poi}(np_{i}),1\leq i\leq S$, we know that for $\theta_{1}=(p_{1},p_{2},\cdots,p_{S}),\theta_{0}=(q_{1},q_{2},\cdots,q_{S})$,

then for $\Delta=|H(\theta_{1})-H(\theta_{0})|$, Markov’s inequality yields

Fix $\epsilon\in(0,1)$ to be specified later, and let

where $A$ is the solution to (70). Direct computation yields

and it can be directly verified that $h(0)=h^{\prime}(0)=0$, and $|h^{\prime\prime}(0)|=\frac{1-A}{A}>0$. Hence, for $\epsilon$ small enough we have $D(\theta_{1}\|\theta_{0})\leq\epsilon^{2}/A$. By choosing $\epsilon=(nA)^{-\frac{1}{2}}\lesssim 1$, we have

Hence, by Lemma 7 and $nD(\theta_{1}\|\theta_{0})\leq 1,A\asymp H/\ln S$ we can obtain the following minimax lower bound under the Poissonized model

The corresponding minimax lower bound for the variance in the Multinomial model follows from Lemma 1. The proof of Theorem 1 is complete by combining the lower bounds for the bias and the variance.

V Proof of Upper Bounds in Theorem 2

where $nX\overset{D}{=}nY\sim\mathsf{Poi}(np)$, and $X,Y$ are independent. We first recall the following lemma from .

Suppose $0<c_{1}=16(1+\delta),0<8c_{2}\ln 2=\epsilon<1,\delta>0$. Then the bias and variance of $\xi(X,Y)$ are given as follows:

where we have used Lemma 3 in the last step. Hence,

When $S\ln S\leq enH\ln n$, for $\epsilon$ small enough, say, $\epsilon<\frac{1}{2}$, we have

where we have used the assumption that $H\geq H_{0}>0$. Hence, the term $\frac{S(\ln n)^{4}}{n^{2-\epsilon}}$ is negligible when compared with others, and we have reached the end for the case $S\ln S\leq e^{2}nH\ln n$.

For the case where $S\ln S\geq e^{2}nH\ln n$, we need stronger results for the bias and variance in the regime where $p<\frac{1}{en\ln n}$. The results are summarized in the following lemma.

If $0<c_{2}\leq 1\leq c_{1}$, for $nX\sim\mathsf{Poi}(np),0<p<\frac{1}{en\ln n}$, we have

where the constant $D_{p}$ is given in Lemma 15.

Using the Poisson tail bound (cf. Lemma 17) and similar argument to [11, Lemma 8], we have the following lemma.

Suppose $0<c_{1}=16(1+\delta),0<10c_{2}\ln 2=\epsilon<1,\delta>0$. Then for $0<p<\frac{1}{en\ln n}$, we have

where $c_{3}$ is some universal constant which only depends on $c_{1}$ and $c_{2}$.

Now we proceed to bound the total bias and variance. For the bias, we can write

Using similar arguments in the proof of upper bound in Theorem 1, we can show that

Combining the total bias and variance constitutes a complete proof of the upper bounds in Theorem 2.

VI Proof of Lower Bounds in Theorem 2

When $S\ln S\leq e^{2}nH\ln n$, the lower bound for the squared bias, i.e., the $\frac{S^{2}}{(n\ln n)^{2}}$ term, can be obtained using a similar argument in . Specifically, we can assign two product measures $\mu_{0}^{N}$ and $\mu_{1}^{N}$ to the first $N(\leq S)$ components in the distribution vector $P$, where

In , $N=S$. However, in our case, we have an additional constraint that $H(P)\leq H$. Since

One can show that the measures $\mu_{i}^{N},i=0,1$ are highly concentrated around their expectations . Hence, in order to ensure $H(P)\leq H$ with overwhelming probability, we can set $N\asymp\min\{nH,S\}$, and the condition $S\ln S\leq e^{2}nH\ln n$ and $H\geq H_{0}>0$ yield that $nH\gtrsim S$, and thus $N\gtrsim S$. Hence by (120),

The variance bound $\frac{H\ln S}{n}$ has been given in (89), and so far we have completed the proof of the first part. As for the second part, the key lemma we will employ is the so-called method of two fuzzy hypotheses presented in Tsybakov . Below we briefly review this general minimax lower bound.

where $F_{i},i=0,1$ are the marginal distributions of $\mathbf{Z}$ when the priors are $\sigma_{i},i=0,1$, respectively.

Here $V(P,Q)$ is the total variation distance between two probability measures $P,Q$ on the measurable space $(\mathcal{Z},\mathcal{A})$. Concretely, we have

where $p=\frac{dP}{d\nu},q=\frac{dQ}{d\nu}$, and $\nu$ is a dominating measure so that $P\ll\nu,Q\ll\nu$.

First we assume that $S\lesssim n^{\frac{3}{2}}$. In light of Lemma 11, we construct two measures as follows.

For any $0<\eta<1$ and positive integer $L>0$, there exist two probability measures $\nu_{0}$ and $\nu_{1}$ on $[\eta,1]$ such that

$\int t^{l}\nu_{1}(dt)=\int t^{l}\nu_{0}(dt)$, for all $l=0,1,2,\cdots,L$;

$\int-\ln t\nu_{1}(dt)-\int-\ln t\nu_{0}(dt)=2E_{L}[-\ln x]_{[\eta,1]}$,

where $E_{L}[-\ln x]_{[\eta,1]}$ is the distance in the uniform norm on $[\eta,1]$ from the function $g(x)=-\ln x$ to the space spanned by $\{1,x,\cdots,x^{L}\}$.

The following lemma characterizes the properties of $E_{L}[-\ln x]_{[\eta,1]}$.

If $K\geq eL^{2}$, there exists a universal constant $D_{0}\geq 1$ such that

with universal positive constants $d_{1}\in(0,e^{-1}],d_{2}>2$ to be determined later. Without loss of generality we assume that $d_{2}\ln n$ is always a positive integer. Due to $S\ln S\geq e^{2}nH\ln n$, we have $(D_{0}\eta)^{-1}\geq eL^{2}$, thus Lemma 13 yields

$\int t^{1}\mu_{1}(dt)=\int t^{1}\mu_{0}(dt)=d_{1}H/(S\ln S)$;

$\int t^{l}\mu_{1}(dt)=\int t^{l}\mu_{0}(dt)$, for all $l=2,\cdots,L+1$;

$\int-t\ln t\mu_{1}(dt)-\int-t\ln t\mu_{0}(dt)=2\eta ME_{L}[-\ln x]_{[\eta,1]}$.

Let $\mu_{0}^{S-1}$ and $\mu_{1}^{S-1}$ be product priors which we assign to the length-$(S-1)$ vector $(p_{1},p_{2},\cdots,p_{S-1})$, and we set $p_{S}=d_{1}(1-H/\ln S)$. With a little abuse of notation, we still denote the overall product measure by $\mu_{0}^{S}$ and $\mu_{1}^{S}$. Note that $P$ may not be a probability distribution, we consider the set of approximate probability vectors

with parameter $\epsilon>0$ to be specified later, and further define under the Poissonized model,

In light of Lemma 14, it suffices to consider $R_{P}(S,n,H,\epsilon)$ to give a lower bound of $R(S,n,H)$. Denote

Denote by $\pi_{i}$ the conditional distribution defined as

Now consider $\pi_{0},\pi_{1}$ as two priors. By setting

we have $\beta_{0}=\beta_{1}=0$ in Lemma 11. Applying union bound yields that

and the Chebychev inequality tells us that

where we have used our assumption that $S\lesssim n^{\frac{3}{2}}$. For bounding $\mu_{i}^{S}[H(P)>H]$, we first remark that for $d_{1}\leq e^{-1}$,

hence, for $d_{1}$ sufficiently small, say, $d_{1}\leq\min\{\frac{1}{4},f^{-1}\left(\min\{\frac{H_{0}}{8},\frac{1}{e}\}\right)\}$, where $f(x)=-x\ln x$ is defined in $[0,e^{-1}]$ and $f^{-1}(\cdot)$ denotes the inverse function of $f(\cdot)$, we have

Denote by $F_{i},G_{i}$ the marginal probability under prior $\pi_{i}$ and $\mu_{i}^{S}$, respectively, for all $i=0,1$. In light of (145), (149), (152) and (161), we have

Hence, the total variational distance is then upper bounded by

where we have used the triangle inequality of the total variation distance. The idea of converting approximate priors $\mu_{i}^{S}$ into priors $\pi_{i}$ via conditioning comes from Wu and Yang .

Now it follows from Lemma 11 and Markov’s inequality that

and the desired result follows directly from Lemma 14. Hence we have obtained the desired lower bound in the case $S\lesssim n^{\frac{3}{2}}$.

For $S\gtrsim n^{\frac{3}{2}}$, we can change the parameters in (132) into

for some small $\beta>0$, say, $\beta=1/4$. Applying the similar analysis yields

VII Future work

This paper studies the adaptive estimation framework to strengthen the optimality properties of the approximation theoretic entropy estimator proposed in Jiao et al. . We remark that the techniques in this paper are by no means constrained to entropy, and we believe analogous results are also true for the estimators of $F_{\alpha}(P)=\sum_{i=1}^{S}p_{i}^{\alpha}$ in . Furthermore, we find the fact that the sample size enlargement effect still holds in the adaptive estimation setting very intriguing, and we believe there is a larger picture surrounding this theme to be explored.

VIII Acknowledgments

The authors would like to express their most sincere gratitude to Dany Leviatan for valuable advice on the literature of approximation theory, in particular, for suggesting the result in Lemma 16.

Appendix A Auxiliary Lemmas

The following lemma characterizes the performance of the best uniform approximation polynomial for $-x\ln x,x\in$.

Denote by $\sum_{k=0}^{K}g_{K,k}x^{k}$ the $K$-th order best uniform approximation polynomial for $-x\ln x,x\in$, then for $p_{K}(x)=\sum_{k=1}^{K}g_{K,k}x^{k}$, we have the norm bound

where $D_{n}>0$ is a universal constant for the norm bound. In fact, the following inequality holds:

where the function $\nu_{1}(p)$ is was introduced by Ibragimov as the following limit for $p$ positive even integer and $m$ positive integer

Furthermore, we also have the pointwise bound: there exists a universal constant $D_{p}>0$ such that for any $C\geq 1$,

[30, Thm. 8.4.8] There exists some universal constant $M>0$ such that for any order-$n$ polynomial $p(x)$ in $$, we have

The following lemma gives some tails bounds for Poisson and Binomial random variables.

[31, Exercise 4.7] If $X\sim\mathsf{Poi}(\lambda)$, or $X\sim\mathsf{B}(n,\frac{\lambda}{n})$, then for any $\delta>0$, we have

Appendix B Proof of Lemmas

For $S=1,2$, the result is obvious, and we assume in the sequel that $S\geq 3$. Denote $H(P)=\sum_{i=1}^{S}-p_{i}\ln p_{i}$ by $H$, we construct the Lagrangian:

By taking the derivative with respect to $p_{i}$, we obtain that

is a quadratic form of $\ln p_{i}$, so the equation $\frac{\partial\mathcal{L}}{\partial p_{i}}=0$ has at most two solutions.

Hence, we conclude that components of the maximum achieving distribution can only take two values $p_{i}\in\{q_{1},q_{2}\}$, and suppose $q_{1}$ appears $m$ times. We distinguish the analysis into two cases.

If $\min\{q_{1},q_{2}\}\geq\frac{1}{S^{2}}$, we have $-\ln p_{i}\leq 2\ln S$ for all $i$. Hence,

B-A2 Case II

If $q_{1}$ or $q_{2}$ is smaller than $\frac{1}{S^{2}}$, without loss of generality we can assume that $q_{1}\leq q_{2}$ and $q_{1}<\frac{1}{S^{2}}$. Then

where we have used the inequalities $m\leq S,(S-m)q_{2}\leq 1$ in (186), and the monotonically increasing property of $x(\ln x)^{2}$ for $x\in[0,e^{-2}]$ in (187). The last inequality follows from $H\leq\ln S$ and $(\ln S)^{2}/S\leq 4/e^{2}<3/4$.

B-B Proof of Lemma 4

Define $f(x)=-x\ln x$ on $$, and the order-$n$ Bernstein polynomial

where $\Delta^{k}f(x)$ is the order-$k$ forward difference of $f(\cdot)$ at $x$ with step size $h=1/n$:

Since $f^{(3)}(\cdot)\geq 0$, the mean value theorem for the forward difference shows that $\Delta^{3}f(\cdot)\geq 0$, and $B_{n}^{(3)}(f,x)\geq 0$ by (191). Hence $B_{n}^{(2)}(f,x)$ is monotonically non-decreasing with respect to $x\in$, which yields that for $0\leq x\leq 1/n$,

The proof is completed by applying (193) and the Taylor’s formula

B-C Proof of Lemma 5

For $0<x_{1}\leq x_{2}<1/e$, we write $-y_{1}\ln y_{1}=x_{1},-y_{2}\ln y_{2}=x_{2}$. It follows from $x_{1}\leq x_{2}$ that $y_{1}\leq y_{2}$. By the mean value theorem,

Now we give an upper bound for $y_{2}$ in terms of $x_{2}$. Since $y_{2}<1/e$, we have

Substituting this result in $-y_{2}\ln y_{2}=x_{2}$ once more yields a refined inequality

which completes the proof of the first inequality. For the second equality, we write

B-D Proof of Lemma 9

For the bias, it is straightforward to see that for $nX\sim\mathsf{Poi}(np)$, we have

where $p_{K}(x)\triangleq\sum_{k=1}^{K}g_{K,H}x^{k}$ is the best approximating polynomial appearing in Lemma 15. Since $\frac{p}{4\Delta}\leq\frac{1}{K^{2}}$, Lemma 15 asserts that

The proof for the second part is similar to [11, Lem. 5].

B-E Proof of Lemma 13

we have $E_{L}[f_{N}]_{}=E_{L}[-\ln x]_{[N^{-1},1]}$. Let $\Delta_{L}(x)=\frac{\sqrt{1-x^{2}}}{L}+\frac{1}{L^{2}}$ and define the following modulus of continuity for $f$:

There are an upper bound and a lower bound for $\tau_{1}(f_{N},\Delta_{L})$:

The upper bound is shown in [15, Lem. 4]. For the lower bound, denote by $x_{L}\in$ the solution to the equation $x_{L}-\Delta_{L}(x_{L})=-1$, we have the following closed-form formula:

The relationship between $\tau_{1}(f_{N},\Delta_{L})$ and $E_{L}[f_{N}]_{}$ was shown in [33, Thm. 3.13, Thm. 3.14] that there exist two universal constants $M_{1},M_{2}>0$ such that

Applying (223) and (224) and setting the approximation order to be $DL$ with constant $D>1$ to be specified later, then given $N=(10D)^{2}M\geq(10DL)^{2}$, the non-increasing property of $E_{n}[f_{N}]_{}$ with respect to $n$ yields

Hence, there exists a sufficiently large constant $D>0$ such that

and this lemma is proved by setting $D_{0}=\max\{100D^{2},1\}$.

B-F Proof of Lemma 14

Fix $\delta>0$. Let $\hat{H}({\bf Z})$ be a near-minimax estimator of $H(P)$ under the Multinomial model. The estimator $\hat{H}({\bf Z})$ obtains the number of samples $n$ from observation $\bf Z$. By definition, we have

where $R(S,n,H)$ is the minimax $L_{2}$ risk under the Multinomial model. Note that for any vector $P\in\mathcal{M}_{S}(\epsilon,H)$ ($P$ is not necessarily a probability distribution), we have

where by definition we have $\left|\sum_{i=1}^{S}p_{i}-d_{1}\right|\leq\epsilon$. Hence, given $P\in\mathcal{M}_{S}(\epsilon,H)$, let $\mathbf{Z}=[Z_{1},\cdots,Z_{S}]^{T}$ with $Z_{i}\sim\mathsf{Poi}(np_{i})$ and let $n^{\prime}=\sum_{i=1}^{S}Z_{i}\sim\mathsf{Poi}(n\sum_{i=1}^{S}p_{i})$, (233) suggests to use the estimator $d_{1}\left(\hat{H}(\mathbf{Z})-\ln d_{1}\right)$ to estimate $H(P)$. Note that

the triangle inequality gives (define $A=\sup_{x\in[d_{1}-\epsilon,d_{1}+\epsilon]}\ln^{2}(ex)$)

where we have used the fact that conditioned on $n^{\prime}=m$, $\mathbf{Z}\sim\mathsf{Multinomial}(m,\frac{P}{\sum_{i}p_{i}})$, and $R(S,n,H)\leq\left(\sup_{P\in\mathcal{M}_{S}}H(P)\right)^{2}=(\ln S)^{2}$. Moreover, the last step follows from Lemma 17. The proof is completed by the arbitrariness of $\delta$ and Lemma 1.

B-G Proof of Lemma 15

Hence, it follows from the triangle inequality that

which completes the proof of the norm bound.

For the pointwise bound, [30, Thm. 7.3.1] asserts that there exists a universal positive constant $M_{1}$ such that

where $\varphi(x)=\sqrt{x(1-x)}$, and $\omega_{\varphi}^{2}(f,t)$ is the second-order Ditzian-Totik modulus of smoothness defined by

According to Lemma 16, since $p_{K}^{\prime\prime}(x)$ is a polynomial with order $K-2<2K$, there exists some positive constant $M_{2}$ such that

hence for any $x,y\in[0,C/K^{2}]$, we have

As a result, we know that for any $C\geq 1$, $u=C/K^{2}$ and $x\in[0,u]$,

where $D_{n}$ is the coefficient of the norm bound in (173). Hence, the universal positive constant $D_{p}\triangleq 16M_{1}M_{2}\ln 2+1+D_{n}$ satisfies

References