text:
\begin{document}

\title{Maximum Likelihood Estimation of Functionals of
Discrete Distributions}

\author{Jiantao~Jiao,~\IEEEmembership{Student Member,~IEEE},~Kartik~Venkat,~\IEEEmembership{Student Member,~IEEE},~Yanjun~Han,~\IEEEmembership{Student Member,~IEEE}, and Tsachy~Weissman,~\IEEEmembership{Fellow,~IEEE}
\thanks{Jiantao Jiao, Kartik Venkat, and Tsachy Weissman are with the Department of Electrical Engineering, Stanford University, CA, USA. Email: \{jiantao,kvenkat,tsachy\}@stanford.edu}.
\thanks{Yanjun Han is with the Department of Electronic Engineering, Tsinghua University, Beijing, China. Email: hanyj11@mails.tsinghua.edu.cn}
}

\date{\today}

\vspace{-10pt}

\maketitle

\begin{abstract}
The Maximum Likelihood Estimator (MLE) is widely used in estimating information measures, and involves ``plugging-in'' the empirical distribution of the data to estimate a given functional of the unknown distribution. In this work we propose a general framework for analyzing the performance of the MLE in estimating functionals of discrete distributions, under the worst-case mean squared error criterion. We show that existing theory, which was developed to accommodate a fixed alphabet and a growing number of observations, is insufficient for analyzing the bias of the MLE, and apply the theory of approximation using positive linear operators to study this bias. The variance is controlled using the well-known tools from the literature on concentration inequalities.

Our techniques yield a characterization of the worst-case $L_2$ risk incurred by the MLE in estimating the Shannon entropy $H(P) = \sum_{i = 1}^S -p_i \ln p_i$, and $F_\alpha(P) = \sum_{i = 1}^S p_i^\alpha,\alpha>0$ up to a multiplicative constant, for any alphabet size $S\leq \infty$ and sample size $n$. As a corollary, for Shannon entropy estimation, we show that it is necessary and sufficient to have $n  \gg S$ observations for the MLE to be consistent. In addition, we establish that it is necessary and sufficient to consider $n \gg S^{1/\alpha}$ samples for the MLE to consistently estimate $F_\alpha(P), 0<\alpha<1$. The minimax rate-optimal estimators for both problems require $S/\ln S$ and $S^{1/\alpha}/\ln S$ samples, which implies that the MLE has a strictly sub-optimal sample complexity. When $1<\alpha<3/2$, we show that the worst-case $L_2$ rate of convergence for the MLE is $n^{-2(\alpha-1)}$ for infinite alphabet size, while the minimax $L_2$ rate is $(n\ln n)^{-2(\alpha-1)}$. When $\alpha\geq 3/2$, the MLE achieves the minimax optimal $L_2$ convergence rate $n^{-1}$ regardless of the alphabet size.

We explicitly establish an equivalence between bias analysis of plug-in estimators for general functionals under arbitrary statistical models, and the theory of approximation using positive linear operators, a subarea of approximation theory with more than a century's history. This equivalence between bias analysis and approximation theory is of relevance and consequence far beyond the specific problem setting in this paper.
\end{abstract}

\begin{IEEEkeywords}
entropy estimation, maximum likelihood estimator, approximation theory, high dimensional statistics, R\'enyi entropy
\end{IEEEkeywords}

\section{Introduction}

Entropy and related information measures arise in information theory, statistics, machine learning, biology, neuroscience, image processing, linguistics, secrecy, ecology, physics, and finance, among other fields. Numerous inferential tasks rely on data driven procedures to estimate these quantities~(see, e.g. \cite{Olsen--Meyer--Bontempi2009impact,Pluim--Maintz--Viergever2003mutual,Viola--Wells1997alignment,Batina--Gierlichs--Prouff--Rivain--Standaert--Veyrat2011mutual,Hill1973diversity,Franchini--Its--Korepin2008Renyi}). Consider the problem of estimating the Shannon entropy of an unknown discrete distribution $P$ based on $n$ i.i.d. samples. This problem has a rich history, of which we refer the reader to~\cite{Jiao--Venkat--Han--Weissman2014minimax} for a review. One of the most widely used estimators for this purpose is the Maximum Likelihood Estimator (MLE), which is simply the empirical entropy. The empirical entropy is an instantiation of the plug-in principle in functional estimation, where a point estimate of the parameter (distribution $P$ in this case) is used to construct an estimator for a {\em functional} of the parameter. The idea of using the MLE for estimating information measures of interest (in this case entropy), is not only intuitive, but has sound justification: {\em asymptotic efficiency}.

The beautiful theory of H\'ajek and Le Cam \cite{Hajek1970characterization,Hajek1972local,LeCam1986asymptotic} shows that, as the number of observed samples grows without bound while the parameter dimension (e.g., alphabet size) remains fixed, the MLE performs optimally in estimating any differentiable functional complying with the benign LAN (Local Asymptotic Normality) condition~\cite{LeCam1986asymptotic}. Thus, for finite dimensional problems, the problems of parameter and functional estimation are well understood in an asymptotic sense, and the MLE appears to be not only natural but also theoretically justified. But does it make sense to employ the MLE to estimate the entropy in most practical applications?

As it turns out, while asymptotically optimal in entropy estimation, the MLE is by no means sacrosanct in many real applications, especially in regimes where the alphabet size is comparable to, or even larger than the number of observations. It was shown that the MLE for entropy is strictly sub-optimal in the large alphabet regime~\cite{Paninski2003,Paninski2004}. Therefore, classical asymptotic theory does not satisfactorily address high dimensional settings, which are becoming increasingly important in the modern era of high dimensional statistics.

The main contribution of this paper is to provide novel tools for analysis of plug-in estimators such as the MLE, complementing the companion paper~\cite{Jiao--Venkat--Han--Weissman2014minimax} which presents new estimators shown to be {\em minimax rate-optimal}. The papers~\cite{Jiao--Venkat--Han--Weissman2014minimax, Jiao--Venkat--Han--Weissman2014beyond} also demonstrate that employing the MLE in functional estimation can result in highly sub-optimal estimators in practical inferential applications.
\subsection{Problem formulation}
To illustrate our methodology, we shall focus on the following problem. Suppose we observe $n$ independent samples from an unknown discrete probability distribution $P = (p_1, p_2, \ldots, p_S)$, with \emph{unknown} support size $S$, and would like to estimate a functional of the distribution of the form:
\begin{equation}\label{eqn.generalf}
F(P) = \sum_{i=1}^{S} f(p_i),
\end{equation}
where $f: [0,1] \to \mathbb{R}$ is a continuous function, and $f(0) = 0$. We shall focus on two concrete and well-motivated examples of functionals of this form. In particular, the Shannon entropy,
\begin{equation}\label{eqn.entropy}
H(P) \triangleq \sum_{i = 1}^S - p_i \ln p_i,
\end{equation}
plays significant roles in information theory and serves as fundamental limits to various operational problems \cite{Shannon1948}. Another interesting class of functionals is $F_\alpha(P), \alpha > 0$:
\begin{equation}
F_\alpha (P) \triangleq \sum_{i = 1}^S p_i^\alpha, \alpha>0.
\end{equation}
The $\alpha$-moments of a distribution often emerge in various operational problems. In particular, the significance of $F_\alpha(P)$ can also be seen via the connection $H_\alpha(P) = \frac{\ln F_\alpha(P)}{1-\alpha}$, where $H_\alpha(P)$ is the R\'enyi entropy \cite{Renyi1961measures}. Like Shannon entropy, R\'enyi entropy is an important information measure emerging in an increasing variety of disciplines such as ecology, quantum information, information theory, and statistics, to name a few. Recently~\cite{Acharya--Orlitsky--Suresh--Tyagi2014complexity} has studied the complexity of estimating the R\'enyi entropy.

In this work, we analyze, for the above two classes of functionals, the performance of MLE, widely considered the most natural plug-in rule.
\begin{definition}
The Maximum Likelihood Estimator (MLE) for the functional $F(P)$ in (\ref{eqn.generalf}) is defined as:
\begin{equation}
F(P_n) \triangleq \sum_{i = 1}^S f(P_n(i)),
\end{equation}
where $P_n$ denotes the empirical distribution induced by $n$ observations.
\end{definition}

We use the conventional decision theoretic framework, and present matching upper and lower bounds (up to multiplicative constants depending neither on $n$ nor $S$) on the maximum $L_2$ risk of the MLE, i.e.
\begin{equation}
\sup_{P \in \mathcal{M}_S} \mathbb{E}_{P} (F(P) - F(P_n))^2,
\end{equation}
where $\mathcal{M}_S$ denotes the set of discrete distributions of support size $S$. The subscript $P$ means that the expectation is taken with respect to the distribution $P$ that generates the i.i.d.\ observations. We omit the subscript for the expectation operator $\mathbb{E}$ if the meaning of the expectation is clear from the context. Understanding the benefits and limitations of the MLE serves two key purposes. First, the approach is a natural benchmark for comparing other more nuanced procedures for estimation of functionals. Second, performance analysis for the MLE reveals regimes where the problem is difficult, and motivates the development of improvements, such as those recently derived in~\cite{Jiao--Venkat--Han--Weissman2014minimax, Wu--Yang2014minimax, Jiao--Venkat--Han--Weissman2014beyond}.
\subsection{Bias of the MLE: an approximation theoretic perspective}
In the entropy estimation literature, considerable effort has been devoted to understanding the non-asymptotic performance of the MLE $H(P_n)$ in estimating $H(P)$. One of the earliest investigations in this direction is due to Miller~\cite{Miller1955} in 1955, who showed that, for any fixed distribution $P$,
\begin{equation}\label{eqn.miller}
\bE H(P_n) = H(P) - \frac{S-1}{2n} + O\left(\frac{1}{n^2}\right).
\end{equation}
Equation~(\ref{eqn.miller}) was later refined by Harris~\cite{Harris1975} using higher order Taylor series expansions to yield
\begin{equation}\label{eqn.harris}
\bE H(P_n) = H(P) - \frac{S-1}{2n} + \frac{1}{12 n^2} \left( 1- \sum_{i = 1}^S \frac{1}{p_i} \right) + O\left( \frac{1}{n^3} \right).
\end{equation}

Harris's result reveals an undesirable consequence of the Taylor expansion method: one cannot obtain uniform bounds on the bias of the MLE. Indeed, the term $\sum_{i = 1}^S \frac{1}{p_i}$ can be arbitrarily large for some distribution $P$. However, it is evident that both $H(P_n)$ and $H(P)$ are bounded above by $\ln S$, since the maximum entropy of any distribution supported on $S$ elements is $\ln S$. Conceivably, for such a distribution $P$ that would make $\sum_{i = 1}^S \frac{1}{p_i}$ very large, we need to compute even higher order Taylor expansions to obtain more accuracy, but even with such efforts we can never obtain a uniform bias bound for all $P$.

We gain one of our key insights into the bias of the MLE by relating it to the approximation error induced by the {\em Bernstein polynomial approximation} of the function $f$. To see this, we first compute the bias of $F(P_n)$.

\begin{lemma}\label{lemma.biasgeneralf}
The bias of the estimator $F(P_n)$ is given by
\begin{align}\label{eqn.biasgeneralfequation}
\mathsf{Bias}(F(P_n)) &\triangleq \bE F(P_n) - F(P) \nonumber \\
&= \sum_{i = 1}^S \left( \sum_{j = 0}^n f \left( \frac{j}{n} \right) \binom{n}{j} p_i^j(1-p_i)^{n-j} - f(p_i) \right).
\end{align}
\end{lemma}

The bias term in (\ref{eqn.biasgeneralfequation}) can be equivalently expressed as\footnote{In the literature of combinatorics, the sum $\sum_{j = 0}^n a_{j,n}B_{j,n}(x)$ is called the Bernoulli sum, and various approaches have been proposed to evaluate its asymptotics \cite{Jacquet--Szpankowski1999entropy}, \cite{Flajolet1999singularity}, \cite{Cichon--Golkbiewski--Kardas--Klonowski}}.
\begin{equation}
\mathsf{Bias}(F(P_n)) = \sum_{i = 1}^S  \left( \sum_{j = 0}^n f\left( \frac{j}{n} \right) B_{j,n}(p_i) - f(p_i) \right) = \sum_{i = 1}^S \left( B_n[f](p_i) - f(p_i)\right),
\end{equation}
where $B_{j,n}(x) \triangleq \binom{n}{j} x^j(1-x)^{n-j}$ is the well-known Bernstein polynomial basis, and $B_n[f](x)$ is the so-called Bernstein polynomial for function $f(x)$.  Bernstein in 1912~\cite{Bernstein1958collected} provided an insightful constructive proof of the Weierstrass theorem on approximation of continuous functions using polynomials, by showing that the Bernstein polynomial of any continuous function converges uniformly to that function.

From a functional analysis viewpoint, the Bernstein polynomial is an operator that maps a continuous function $f\in C[0,1]$ to another continuous function $B_n[f] \in C[0,1]$. This operator is linear in $f$, and is \emph{positive} because $B_n[f]$ is also pointwise non-negative if $f$ is pointwise non-negative. Evidently, bounding the approximation error incurred by the Bernstein polynomial is equivalent to bounding the bias of the MLE $f(X/n)$, where $X \sim \mathsf{Binomial}(n,x)$. As mentioned above, Taylor series expansions are not sufficient to satisfactorily analyze this bias. Fortunately, the theory of \emph{approximation using positive linear operators}~\cite{Paltanea2004} provides us with advanced tools that are very effective for the bias analysis our problem calls for. A century ago, probability theory served Bernstein in breaking new ground in function approximation. It is therefore very satisfying that advancements in the latter have come full circle to help us better understand probability theory and statistics. We briefly review the general theory of approximation using positive linear operators below.

\subsection{Approximation theory using positive linear operators}

Generally speaking, for any estimator $\hat{\theta}$ of a parametric model indexed by $\theta$, the expectation $f \mapsto \bE_\theta f(\hat{\theta})$ is a positive linear operator for $f$, and analyzing the bias $\bE_\theta f(\hat{\theta}) -f(\theta)$ is equivalent to analyzing the approximation properties of the positive linear operator $\bE_\theta f(\hat{\theta})$ in approximating $f(\theta)$. Hence, analyzing the bias of \emph{any} plug-in estimator for functionals of parameters from \emph{any} parametric families can be recast as a problem of approximation theory using positive linear operators~\cite{Paltanea2004}.

Why are approximation theorists interested in this theory? It turns out the most constructive proofs of the Weierstrass theorem concerning the approximation of continuous functions on a compact interval by polynomials use some sequences of positive linear operators. So do the classical operators of Gauss--Weierstrass, Landau, Vall\'ee-Poissin, Jackson, and Bernstein. Concretely, an operator $L$ defined on a linear space of functions, $V$, is called \emph{linear} if
\begin{equation}
L(\alpha f + \beta g) = \alpha L(f) + \beta L(g), \quad \text{for all }f,g\in V, \alpha,\beta \in \mathbb{R},
\end{equation}
and is called \emph{positive}, if
\begin{equation}
L(f)\geq 0\quad \text{for all }f\in V, f\geq 0.
\end{equation}

Given that the most general problems of bias analysis about plug-in methods in functional estimation are a subset of the general theory of approximation using positive linear operators, can we show that for a natural large class of positive linear operators, there exist corresponding probabilistic models such that the bias analysis is exactly the same as approximation properties for the positive linear operator?

Surprising as it may sound, the answer is \emph{yes}. Denote by $\mathcal{F}(I)$ the set of all functions with domain $I$, where $I\subset \mathbb{R}$ is an interval. We note that any positive linear operator $L: V \mapsto \mathcal{F}(I)$ can be expressed as a collection of linear positive functionals $(F_x)_{x\in I}$. Indeed, for any fixed point $x\in I$ we obtain a positive linear functional $F_x: V \mapsto \mathbb{R}$, defined by $F_x(f) \triangleq L(f)(x), f\in V$. Conversely, if we have a collection of positive linear functionals $(F_x)_{x\in I}, F_x: V\mapsto \mathbb{R}$, then we can construct a positive linear operator $L: V\mapsto \mathcal{F}(I)$, where $L(f)(x) \triangleq F_x(f), f\in V$.

Hence, the study of positive linear operators in this context can be reduced to that of positive linear functionals. It was shown in Paltanea~\cite[Remark 1.1.2.]{Paltanea2004} that if $I$ is an interval of $\mathbb{R}$, then for any positive linear functional $F: C(I)\to \mathbb{R}$, there exists a positive regular Borel measure $\mu$, such that we have the integral representation\footnote{We remark that not every positive linear functional can be formulated in the form~(\ref{eqn.generalfriesz}). See~\cite[Remark 1.1.3.]{Paltanea2004}.}:
\begin{equation}\label{eqn.generalfriesz}
F(f) = \int_I f d\mu, \quad f\in C(I),
\end{equation}
where $C(I)$ denotes the space of continuous functions on $I$. The key ingredient of this proof is the Riesz--Markov--Kakutani theorem, which can be invoked in more general settings in which $I$ is not a subset of $\mathbb{R}$.

Denote by $e_j,j\in \mathbb{N}_+ \cup \{0\}$, the monomial functions $e_j(y) = y^j,y\in I$. If we naturally require $F(e_0) = 1$, which means that the functional maps constant valued functions to the same constant, then the measure $\mu$ in (\ref{eqn.generalfriesz}) is a probability measure, implying that $F(f)$ can be written as an expectation
\begin{equation}
F(f) = \bE_\mu f(Z),\quad Z \sim \mu, \mathsf{supp}(\mu)\subset I.
\end{equation}

If we go back to the positive linear operator setting, and with a slight abuse of notation still denote the operator by $F(f)$, then we can parametrize the measure $\mu$ to be $\mu_x, x\in I$, and represent any positive linear operator operating on $C(I)$ as
\begin{equation}
F(f)(x) = \int_I f d\mu_x = \bE_{\mu_x} f(Z),\quad Z\sim \mu_x, x\in I, \mathsf{supp}(\mu_x)\subset I.
\end{equation}

Thus, there is an equivalence between bias analysis of continuous plug-in estimators and approximation theory using positive linear operators. After more than a century's active research on approximation using positive linear operators, where do we stand? Probably a proper description of the current theory is ``highly developed for certain problems, but far from complete''. Indeed, we now have highly non-trivial tools for positive linear operators of functions on one dimensional compact sets, but the general theory for vector valued multivariate functions on non-compact sets is still far from complete~\cite{Paltanea2004}. In the next subsection, we present a sample of existing results in approximation using positive linear operators, corollaries of which will be used to analyze the bias of the MLE for two examples: $F_\alpha(P)$ and $H(P)$. We note, however, that the problem we investigate is somewhat different from the approximation problem, since the parameter $P$ lies in a simplex, which is a strict subset of $\mathbb{R}^S$. Before embarking on discussing the main results of this paper in Section~\ref{sec.mainresults}, we present a short introduction to bias bounding techniques via approximation theory.

\subsection{Some general results in bias analysis}\label{sec.generalbiasanalysis}

First, some elementary approximation theoretic concepts need to be introduced in order to characterize the degree of \emph{smoothness} of functions. For $I\subset \mathbb{R}$ an interval, the first-order modulus of smoothness $\omega^1(f,t),t\geq 0$ is defined as~\cite{Paltanea2004}
\begin{equation}
\omega^1(f,t) \triangleq \sup \{ |f(u) - f(v)|: u,v \in I, |u-v|\leq t \}.
\end{equation}

The second-order modulus of smoothness $\omega^2(f,t),t\geq 0$ \cite{Paltanea2004} is defined as
\begin{equation}
\omega^2(f,t) \triangleq \sup \left \{ \left| f(u) - 2f\left(\frac{u+v}{2}\right) + f(v) \right|: u, v\in I, |u-v|\leq 2t \right\}.
\end{equation}

Ditzian and Totik~\cite{Ditzian--Totik1987} introduced a class of modulus of smoothness, which proves to be extremely useful in characterizing the incurred approximation errors. For simplicity, for functions defined on $[0,1]$, $\varphi(x) = \sqrt{x(1-x)}$, the first-order Ditzian--Totik modulus of smoothness is defined as
\begin{equation}
\omega^1_\varphi(f,t) \triangleq \sup \left \{ |f(u) - f(v)|: u,v\in [0,1], |u-v| \leq t \varphi\left( \frac{u+v}{2}\right) \right \},
\end{equation}
and the second-order Ditzian--Totik modulus of smoothness is defined as

\begin{align}
\omega_\varphi^2(f,t) &  \triangleq \sup \left\{ \left | f(u) - 2f \left( \frac{u+v}{2}\right) +f(v) \right|: u, v\in [0,1], |u-v| \leq 2t \varphi\left( \frac{u+v}{2} \right) \right\}  .
\end{align}

Recall that we denote by $e_j,j\in \mathbb{N}_+ \cup \{0\}$, the monomial functions $e_j(y) = y^j,y\in I$. The first estimate for general positive linear operators, using modulus $\omega^2$ and with precise constants, was given by Gonska~\cite{Gonska1979quantitative}. We rephrase Paltanea~\cite[Cor. 2.2.1.]{Paltanea2004} as follows. Note that notation $e_1 - x e_0$ denotes a continuous function on $I$ which is the difference of a linear function $y$ and a constant function with constant value $x$ over $I$. In other words, it is an abbreviation of $e_1(y) - x e_0(y),y\in I$, which is a function of $y$ rather than $x$.

\begin{lemma}\cite[Cor. 2.2.1.]{Paltanea2004}\label{lemma.paltaneacor221}
Let $F: C(I) \to \mathbb{R}$ be a positive linear functional, where $I \subset \mathbb{R}$ is an interval. Suppose that $F(e_0) = 1, t>0$. Then,
\begin{enumerate}
\item If $\mathrm{length}(I)\geq 2t, s\geq 2$, then
\begin{equation}
|F(f) - f(x)| \leq |F(e_1 - xe_0)|\frac{\omega^1(f,t)}{t} + \left( 1 + \frac{F(|e_1 - xe_0|^s)}{2t^s} \right)\omega^2(f,t).
\end{equation}
\item If we also have $F(e_1) = x$, $x$ is an interior point of $I$ and $\mathrm{length}(I)\leq 2t$, then
\begin{equation}
|F(f) - f(x)| \leq \omega^2(f,t).
\end{equation}
\end{enumerate}
\end{lemma}

We remark that Lemma~\ref{lemma.paltaneacor221} can be applied to bound the bias of plug-in estimators in very general models. For example, consider an arbitrary statistical experiment $\{P_\theta, \theta \in I\}$, and we obtain $n$ i.i.d. samples $X_1,X_2,\ldots,X_n \sim P_\theta$. For any estimator $\hat{\theta}_n$, we would like to analyze the bias of the plug-in estimator $f(\hat{\theta}_n)$ for functional $f(\theta)$.

Suppose $\mathrm{length}(I)\geq 2t, s\geq 2$, then Lemma~\ref{lemma.paltaneacor221} implies that
\begin{equation}
|\bE_\theta f(\hat{\theta}_n) - f(\theta)| \leq |\bE_\theta \hat{\theta}_n - \theta| \frac{\omega^1(f,t)}{t} + \left( 1+ \frac{\bE |\hat{\theta}_n - \theta|^s}{2t^s} \right)\omega^2(f,t).
\end{equation}

If we further assume that $\hat{\theta}_n$ is an unbiased estimator for $\theta$, i.e., $\bE_\theta \hat{\theta}_n = \theta$ holds for all $\theta \in I$, then we have
\begin{equation}
|\bE_\theta f(\hat{\theta}_n) -f(\theta)| \leq \left( 1+ \frac{\bE |\hat{\theta}_n - \theta|^s}{2t^s} \right)\omega^2(f,t).
\end{equation}

Taking $s = 2$ and assuming $\mathsf{Var}(\hat{\theta}_n) \leq \mathrm{length}(I)/2$, we have
\begin{equation}
|\bE_\theta f(\hat{\theta}_n) - f(\theta)| \leq \frac{3}{2} \omega^2(f, \sqrt{\mathsf{Var}(\hat{\theta}_n)}),
\end{equation}
after we take $t = \sqrt{\bE |\hat{\theta}_n - \theta|^2}$.

We remark that Lemma~\ref{lemma.paltaneacor221} is only one way to analyze the bias, which is by no means always tight. For example, the following estimate using Ditzian--Totik modulus is significantly better than Lemma~\ref{lemma.paltaneacor221} for certain functionals such as the entropy.

\begin{lemma}\cite[Thm. 2.5.1.]{Paltanea2004}\label{lemma.paltaneathm251}
If $F: C[0,1] \to \mathbb{R}$ is a positive linear functional such that $F(e_0) = 1$, then
\begin{equation}
|F(f) - f(x)| \leq \frac{|F(e_1 - xe_0)|}{2t\varphi(x)} \omega_\varphi^1(f,2t) + \left( 1 + \frac{3 F((e_1 - x e_0)^2)}{2 (t\varphi(x))^2} \right) \omega_\varphi^2(f,t),
\end{equation}
for all $t\in (0,1/2]$.
\end{lemma}

Considering the same statistical experiment $\{P_\theta, \theta \in I\}$, and the plug-in estimator $f(\hat{\theta}_n)$ for $f(\theta)$, if $\hat{\theta}_n$ is unbiased for $\theta$ and $\mathsf{Var}(\hat{\theta}_n) \leq \frac{\varphi(\theta)^2}{4}$, then it follows from Lemma~\ref{lemma.paltaneathm251} that
\begin{equation}
|\bE_\theta f(\hat{\theta}_n) - f(\theta)| \leq \frac{5}{2} \omega_\varphi^2 \left( f, \frac{\sqrt{\mathsf{Var}(\hat{\theta}_n)}}{\varphi(\theta)} \right),
\end{equation}
after we take $t = \frac{\sqrt{\mathsf{Var}(\hat{\theta}_n)}}{\varphi(\theta)}$.

For certain functions $f(\theta)$ and statistical models Lemma~\ref{lemma.paltaneathm251} is stronger than Lemma~\ref{lemma.paltaneacor221}. For example, if $f(\theta) = -\theta \ln \theta, \theta \in [0,1]$, and we have $n\cdot\hat{\theta}_n \sim \mathsf{B}(n,\theta)$. We will show in Lemma~\ref{lemma.dtmoduluscomputation} that $\omega_\varphi^2(f,t) = \frac{t^2\ln 4}{1+t^2}$, and $\omega^2(f,t) = t\ln 4$. We also have $\mathsf{Var}(\hat{\theta}_n) = \frac{\theta(1-\theta)}{n}$. Hence, Lemma~\ref{lemma.paltaneacor221} gives the upper bound
\begin{equation}\label{eqn.pointwiseboundforentropyf}
|\bE_\theta f(\hat{\theta}_n) - f(\theta)| \leq \frac{3\ln 4}{2} \sqrt{\frac{\theta(1-\theta)}{n}},
\end{equation}
whereas Lemma~\ref{lemma.paltaneathm251} gives
\begin{equation}\label{eqn.normboundentropyf}
|\bE_\theta f(\hat{\theta}_n) - f(\theta)| \leq \frac{5\ln 4}{2n} \cdot \frac{1}{1+1/n},
\end{equation}
which is much stronger when $n$ is large and $\theta$ not too close to the endpoints of $[0,1]$.

There also exist various estimates for the bias when the parameter lies in sets other than an interval in $\mathbb{R}$. However, the bounds we presented are in general \emph{not} optimal for specific functionals, thereby leaving ample room for future development. For example, the recent work~\cite{Han--Jiao--Weissman2015Bayes} showed an improved result that gives strictly better estimates than Lemma~\ref{lemma.paltaneathm251} for all functionals satisfying the conditions. Note that (\ref{eqn.pointwiseboundforentropyf}) is stronger than (\ref{eqn.normboundentropyf}) when $\theta \leq 1/n$, but Han, Jiao, and Weissman~\cite{Han--Jiao--Weissman2015adaptive} showed that even the pointwise bound in~(\ref{eqn.pointwiseboundforentropyf}) is strictly sub-optimal for certain functionals. Han, Jiao, and Weissman~\cite{Han--Jiao--Weissman2015jensen} summarize existing techniques in bias analysis of plug-in estimators, with a general methodology for obtaining tight bounds.

Despite the extensive literature, obtaining the tightest bounds for specific functionals of interest remains a challenge. In the present paper we focus on the functionals $F_\alpha(P)$ and $H(P)$.

\section{Main results}
\label{sec.mainresults}

{\em Notation:} $a \wedge b$ denotes $\min\{a,b\}$, and $\mathcal{M}_S$ denotes the collection of discrete distributions with support size $S, S\leq \infty$. For two non-negative series $\{a_n\},\{b_n\}$, notation $a_n \lesssim b_n$ means that there exists a positive universal constant $C<\infty$ such that $\frac{a_n}{b_n}\leq C$, for all $n$. Notation $a_n \asymp b_n$ is equivalent to $a_n \lesssim b_n$ and $b_n \lesssim a_n$. Notation $a_n \gg b_n$ means that $\liminf_{n\to \infty} \frac{a_n}{b_n} =\infty$.

Below, we present non-asymptotic bounds on the maximum $L_2$ risk incurred by the MLE for estimating $H(P)$ and $F_\alpha(P)$.

\begin{theorem}[Upper bounds on the risk of the MLE]\label{thm.main}
For the functional $F_\alpha(P)$,
\begin{enumerate}
\item $\alpha\geq 2$:
\begin{align}
\sup_{P \in \cM_S} \bE_P \left( F_\alpha(P_n) - F_\alpha(P) \right)^2  \leq \left( \frac{\alpha(\alpha-1)}{2n}\right)^2 + \frac{\alpha^2}{4n}.
\end{align}
\item $1<\alpha<2$:
\begin{align}
\sup_{P \in \cM_S} \bE_P \left( F_\alpha(P_n) - F_\alpha(P) \right)^2 \leq \left ( \frac{4}{n^{\alpha-1}} \wedge  \frac{3S^{1-\alpha/2}}{n^{\alpha/2}} \wedge C_{\alpha,n} \frac{5S}{2n} \right)^2  + \frac{\alpha^2}{4n},
\end{align}
where $C_{\alpha,n} \triangleq n \omega_\varphi^2(x^\alpha,n^{-1/2})>0$ satisfies $\limsup_{n\to \infty}C_{\alpha,n}<\infty$ for $1<\alpha<2$, and $\omega_\varphi^2$ is the second-order Ditzian--Totik modulus of smoothness.
\item $1/2 \leq \alpha<1$:
\begin{align}
\sup_{P \in \cM_S} \bE_P \left( F_\alpha(P_n) - F_\alpha(P) \right)^2 \leq \left(\frac{3S^{1-\alpha/2}}{2n^{\alpha/2}} \wedge  \frac{5S}{2n^{\alpha}} \right)^2  + \left( \frac{10S^{2-2\alpha}}{n}+ \frac{120}{\alpha^2}\left(\frac{S}{n^{2\alpha}}\wedge \frac{1}{n^{2\alpha-1}}\right) \right).
\end{align}
\item $0<\alpha<1/2$:
\begin{align}
\sup_{P \in \cM_S} \bE_P \left( F_\alpha(P_n) - F_\alpha(P) \right)^2 \leq \left(\frac{3S^{1-\alpha/2}}{2n^{\alpha/2}} \wedge  \frac{5S}{2n^{\alpha}} \right)^2 + \left( \frac{10S}{n^{2\alpha}}+ \frac{120}{\alpha^2}\left(\frac{S}{n^{2\alpha}}\wedge \frac{1}{n^{2\alpha-1}}\right) \right).
\end{align}
\item For the entropy $H(P)$,
\begin{equation}
\sup_{P \in \cM_S} \bE_P \left( H(P_n) - H(P) \right)^2 \leq  \left( \ln \left( 1+ \frac{S-1}{n} \right) \right)^2 + \left(\frac{(\ln n)^2}{n}\wedge \frac{2(\ln S + 2)^2}{n}\right).
\end{equation}
\end{enumerate}
Moreover, in all the bounds presented above, the first term bounds the square of the bias, and the second term bounds the variance.
\end{theorem}

There are several interesting implications of this result, highlighted in the following corollaries.

\begin{corollary}\label{cor.remark.thmmain}
For the functional $F_\alpha(P), \alpha > 1$, if $n \gg 1$, MLE is consistent regardless of the alphabet size, i.e., $\sup_{P \in \mathcal{M}_\infty} E_P (F_\alpha(P_n) - F_\alpha(P))^2 \longrightarrow 0$ as $n \rightarrow \infty$, where $\mathcal{M}_\infty$ denotes the set of all discrete distributions.
\end{corollary}
Evidently, when the functional $F_\alpha(P)$ is differentiable everywhere, the number of samples required to make the maximum $L_2$ risk vanish has no dependence on the alphabet size $S$. Results of this form have appeared in the literature, for example, Antos and Kontoyiannis \cite{Antos--Kontoyiannis2001convergence} showed that it suffices to take $n \gg 1$ samples to consistently estimate $F_\alpha(P), \alpha\geq 2, \alpha \in \mathbb{Z}$. To our knowledge, Theorem~\ref{thm.main} gives the first non-asymptotic result for estimation of $F_\alpha(P)$, $\alpha$ non-integer. More refined than Corollary~\ref{cor.remark.thmmain} is the following:

\begin{corollary}\label{cor.largerthanone}
There exist universal convergence rates for $F_\alpha(P), \alpha> 1$, any alphabet size $S$ (possibly infinite):
\begin{equation}
\sup_S \sup_{P \in \cM_S} \bE_P \left( F_\alpha(P_n) - F_\alpha(P) \right)^2 \lesssim \begin{cases} n^{-2(\alpha-1)} & 1< \alpha<3/2 \\ n^{-1} & \alpha\geq 3/2 \end{cases}
\end{equation}
\end{corollary}

Corollary~\ref{cor.largerthanone} implies that, when $\alpha\geq 3/2$, estimation of $F_\alpha(P)$ is extremely simple in terms of convergence rate: plug-in estimation achieves the best possible rate $n^{-1}$ (as shown in the theory of regular statistical experiments of classical asymptotic theory, see~\cite[Chap. 1.7.]{Ibragimov--Hasminskii1981}). However, when $1<\alpha<3/2$, the rate $n^{-2(\alpha-1)}$ is considerably slower. Are the bounds obtained in this regime loose? It turns out that the convergence rate $n^{-2(\alpha-1)}$ is in fact tight for the MLE when $1<\alpha<3/2$. Precisely, we have the following lower bound.

\begin{theorem}\label{thm.loweralphalargerthanone}
If $S = cn, 1<\alpha<3/2$, $c>0$, then
\begin{equation}
\liminf_{n\to \infty} n^{2(\alpha-1)} \cdot \sup_{P \in \mathcal{M}_S} \bE_P(F_\alpha(P_n) - F_\alpha(P))^2>0.
\end{equation}
\end{theorem}

Interestingly, there exist estimators that demonstrate better convergence rates for estimating $F_\alpha(P), 1<\alpha<3/2$. The companion paper~\cite{Jiao--Venkat--Han--Weissman2014minimax} shows that the minimax $L_2$ rate in estimating $F_\alpha(P), 1<\alpha<3/2$, is $(n\ln n)^{-2(\alpha-1)}$ as long as $S\gtrsim n\ln n$, which is achieved using the general methodology developed therein for constructing minimax rate-optimal estimators for nonsmooth functionals.

Let us now examine the case $0 < \alpha <  1$, another interesting regime that has not been characterized before. In this regime, we observe significant increase in the difficulty of the estimation problem. In particular, the relative scaling between the number of observations $n$ and the alphabet size $S$ for consistent estimation of $F_\alpha(P)$ exhibits a phase transition, encapsulated in the following.
\begin{corollary} \label{cor.mlealphaless1}
For the functional $F_\alpha(P), 0<\alpha<1$, if $n \gg S^{\frac{1}{\alpha}}$, MLE is consistent.
\end{corollary}

In words, in the region $0 < \alpha < 1$, $S^{\frac{1}{\alpha}}$ samples are sufficient for estimating $F_\alpha(P)$. It turns out that this characterization of the performance of the MLE is in fact tight. Precisely, we have the following lower bound for the performance of the MLE in this region.
\begin{theorem}\label{thm.lowerfalpha}
If $n \geq S$, then
\begin{enumerate}
\item $1/2\leq \alpha<1$:
\begin{align}
& \sup_{P \in \mathcal{M}_S} \bE_P \left( F_\alpha(P_n) - F_\alpha(P) \right)^2  \nonumber \\
& \quad \geq \frac{\alpha^2(1-\alpha)^2}{72 n^{2\alpha}} (S-1)^2 \left(1-\frac{1}{n}\right)^2 \nonumber \\
& \quad \quad + \left(\frac{\alpha^2}{64en}\left[(2(S-1))^{1-\alpha}-2^{-\alpha} -\frac{1-\alpha}{4n}\left((2(S-1))^{1-\alpha}+2^{-\alpha}\right)\right]^2 - \frac{1}{2} e^{-n/4}S^{2(1-\alpha)} \right),
\end{align}
\item $0<\alpha<1/2$:
\begin{align}
\sup_{P \in \mathcal{M}_S} \bE_P \left( F_\alpha(P_n) - F_\alpha(P) \right)^2  \geq \frac{\alpha^2(1-\alpha)^2}{36 n^{2\alpha}} (S-1)^2 \left(1-\frac{1}{n}\right)^2.
\end{align}
\end{enumerate}
\end{theorem}

\begin{corollary}\label{cor.l2ratesfalphalessone}
The maximum $L_2$ risk of the MLE $F_\alpha(P_n)$ in estimating $F_\alpha(P)$ is characterized as follows when $n\geq S$:
\begin{equation}
\sup_{P \in \mathcal{M}_S} \bE_P \left( F_\alpha(P_n) - F_\alpha(P) \right)^2 \asymp \begin{cases} \frac{S^2}{n^{2\alpha}} + \frac{S^{2-2\alpha}}{n} & 1/2< \alpha<1 \\ \frac{S^2}{n^{2\alpha}} & 0<\alpha \leq 1/2 \end{cases}
\end{equation}
\end{corollary}

Corollary~\ref{cor.l2ratesfalphalessone} follows directly from Theorem~\ref{thm.main} and Theorem~\ref{thm.lowerfalpha}. In particular, it implies that it is necessary and sufficient to take $n \gg S^{1/\alpha}$ samples to consistently estimate $F_\alpha(P), 0<\alpha<1$ using MLE. Thus, as one might expect, the scale of the number of measurements required for consistent estimation increases as $\alpha$ decreases. When $\alpha \to 0$, the number of samples required for the MLE grows super-polynomially in $S$. On the other hand, for $\alpha > 1$, it suffices to take $n \gg 1$ samples for the MLE to be consistent. We exhibit some of our findings by plotting the value required of $\ln n/\ln S$ for consistent estimation of $F_\alpha(P)$ using the MLE $F_\alpha(P_n)$, as a function of $\alpha$,  in Figure~\ref{fig.falphaphase}.

\begin{center}
  \centering
\begin{tikzpicture}[xscale=4.2,yscale=4.2]
\draw [<->, help lines] (0.6,2.8) -- (0.6,0.6) -- (2.8,0.6);
\draw [ultra thick] (1.0316, 2.9171) -- (1.0789, 2.6879) -- (1.1263, 2.5000 ) -- (1.1737, 2.3431 )-- (1.2211, 2.2102) -- (1.2684,2.0961 ) -- (1.3158,1.9971 ) -- (1.3632,1.9103 ) -- (1.4105,1.8338 ) -- (1.4579,1.7656 ) -- (1.5053, 1.7047) -- (1.5526,1.6497 ) -- (1.6000, 1.6);

\draw [ultra thick](1.6, 0.6) -- (2.8, 0.6);
\draw [dashed] (1.6, 0.6) -- (1.6,1.6);
\node [above] at (1.1,1) {not achievable via MLE};
\node [below] at (1.1,1) {(Theorem~\ref{thm.lowerfalpha})};

\node [left] at (0.6, 1.6) {1};
\node [left] at (0.6,0.6) {0};
\node [below] at (1.6, 0.6) {1};
\node [below] at (2.6,0.6) {2};
\node [right] at (2.8,0.6) {$\alpha$};
\node [above] at (0.6,2.8) {$\frac{\ln n}{\ln S}$};
\draw [->] (1.1,1.6) -- (1.4579,1.7656 );
\node [left] at (1.1, 1.6) {$1/\alpha$};

\node [above] at (2.4, 1.8) {achievable via MLE};
\node [below] at (2.4, 1.8) {(Theorem~\ref{thm.main})};
\end{tikzpicture}
\captionof{figure}{For any fixed point above the thick curve, consistent estimation of $F_\alpha(P)$ is achieved using MLE $F_\alpha(P_n)$ as shown in Theorem~\ref{thm.main}. For the regime $0<\alpha<1$, below the thick curve, Theorem~\ref{thm.lowerfalpha} shows that the MLE does not have vanishing maximum $L_2$ risk. }
\label{fig.falphaphase}
\end{center}

A natural question arising in light of Corollary~\ref{cor.mlealphaless1} and Theorem~\ref{thm.lowerfalpha} is whether one can construct estimators that are better than the MLE in terms of required sample complexity for consistent estimation. The answer turns out to be affirmative, as we show in the companion paper~\cite{Jiao--Venkat--Han--Weissman2014minimax}. In particular, the scheme we introduce therein is a consistent estimator of $F_\alpha(P)$ in the regime $0 < \alpha < 1$ when $n\gg \frac{S^{\frac{1}{\alpha}}}{\ln S}$, which is a logarithmic improvement in the sample complexity over the MLE. It is also shown that the scheme of~\cite{Jiao--Venkat--Han--Weissman2014minimax} is minimax rate-optimal.

Let us now shift our focus to the case of entropy $H(P)$, which may be roughly intuitively viewed as the functional $F_\alpha(P)$ when $\alpha \to 1^{-}$. The following corollary demonstrates that such intuition is indeed approximately correct as $H(P)$ coincides with $\alpha \to 1^{-}$ on the phase transition curve shown in Figure \ref{fig.falphaphase}. Theorem~\ref{thm.main} implies the following corollary.
\begin{corollary}
Case $H(P)$: The maximum $L_2$ risk of the MLE vanishes provided $n \gg S$.
\end{corollary}

As it turns out, $n \asymp S$ is the optimal scaling for consistency of $H(P_n)$ in estimating $H(P)$. Further, we show that the same is true of the Miller--Madow bias-corrected estimator \cite{Miller1955} defined as
\begin{equation}
H^{\text{MM}}(P_n) = H(P_n) + \frac{S-1}{2n}.
\end{equation}

\begin{theorem}\label{thm.lowerentropy}
For the entropy $H(P)$, if $n \geq 15S$, then
\begin{equation}
\sup_{P \in \mathcal{M}_S} \bE_P \left( H(P_n) - H(P) \right)^2 \geq \frac{1}{2}\left(\frac{S-1}{2n} + \frac{S^2}{20n^2} - \frac{1}{12n^2}\right)^2 + c \frac{\ln^2 S}{n}.
\end{equation}
Moreover, if $n \geq 15S$, the Miller--Madow bias-corrected estimator satisfies
\begin{equation}
\sup_{P \in \mathcal{M}_S} \bE_P \left( H^{\mathrm{MM}}(P_n) - H(P) \right)^2 \geq \frac{1}{2}\left(\frac{S^2}{20n^2} - \frac{1}{12n^2}\right)^2 + c \frac{\ln^2 S}{n},
\end{equation}
where the positive constant $c>0$ in both expressions does not depend on $S$ or $n$.
\end{theorem}

Theorem~\ref{thm.main} and Theorem~\ref{thm.lowerentropy} imply the following corollary.
\begin{corollary}\label{cor.entropyl2rate}
The maximum $L_2$ risk of the MLE $H(P_n)$ in estimating $H(P)$ is characterized as follows when $n\geq 15S$:
\begin{equation}
\sup_{P \in \mathcal{M}_S} \bE_P \left( H(P_n) - H(P) \right)^2 \asymp \frac{S^2}{n^2} + \frac{\ln^2 S}{n}.
\end{equation}
\end{corollary}

We can raise an analogous question for the estimation of $H(P)$ as we did for $F_\alpha(P), 0<\alpha<1$: does there exist an entropy estimator with vanishing maximum $L_2$ risk with sublinear $n\ll S$ number of samples? The answer is affirmative, as was shown in \cite{Valiant--Valiant2011}, and more recently via a different scheme by the present authors in~\cite{Jiao--Venkat--Han--Weissman2014minimax}, that one can construct estimators for which $n = \omega\left( S/\ln S \right)$ samples suffice for consistent estimation. It was further shown in \cite{Valiant--Valiant2011,Wu--Yang2014minimax} that this is the optimal order as the number of samples needed for any estimator to achieve vanishing maximum $L_2$ risk is at least of order $\omega(S/\ln S)$. As in the case of $F_\alpha(P),0<\alpha<1$, the MLE serves as a very good benchmark when we compare it with the minimax rate-optimal estimator.

To sum up our results regarding achievability and lower bounds on estimation of $F_\alpha(P)$ and $H(P)$, we have Table~\ref{table.summary}, in which JVHW denotes \cite{Jiao--Venkat--Han--Weissman2014minimax}, VV denotes~\cite{Valiant--Valiant2011power,Valiant--Valiant2011}, and WY denotes \cite{Wu--Yang2014minimax}.

The following table summarizes the minimax $L_2$ rates and the $L_2$ convergence rates of the MLE for estimating $F_\alpha(P),\alpha>0$ and $H(P)$.

\begin{table}[h]
\begin{center}

    \begin{tabular}{| l | l | l |}
    \hline
    & Minimax $L_2$ rates & $L_2$ rates of MLE\\ \hline
$H(P)$    & $\frac{S^2}{(n \ln n)^2} + \frac{\ln^2 S}{n} \quad \left( n \gtrsim S/\ln S \right)$ (JVHW,WY,VV) & $\frac{S^2}{n^2} + \frac{\ln^2 S}{n}\quad \left( n \gtrsim S \right)$ (Corollary~\ref{cor.entropyl2rate})  \\ \hline

$F_\alpha(P), 0<\alpha \leq \frac{1}{2}$ &  $\frac{S^2}{(n \ln n)^{2\alpha}} \quad \left( n \gtrsim S^{1/\alpha}/\ln S, \ln n \lesssim \ln S \right)$ (JVHW)  & $\frac{S^2}{n^{2\alpha}}\quad \left( n \gtrsim S^{1/\alpha} \right)$ (Corollary~\ref{cor.l2ratesfalphalessone})     \\
    \hline

$F_\alpha(P), \frac{1}{2}< \alpha<1$ &    $\frac{S^2}{(n \ln n)^{2\alpha}} + \frac{S^{2-2\alpha}}{n}\quad \left( n \gtrsim S^{1/\alpha}/\ln S \right)$ (JVHW) & $\frac{S^2}{n^{2\alpha}} + \frac{S^{2-2\alpha}}{n}\quad \left( n \gtrsim S^{1/\alpha} \right)$ (Corollary~\ref{cor.l2ratesfalphalessone})  \\ \hline

$F_\alpha(P), 1< \alpha<\frac{3}{2}$ & $(n \ln n)^{-2(\alpha-1)}\quad \left(S \gtrsim n\ln n \right)$ (JVHW)  & $n^{-2(\alpha-1)}\quad \left(S \gtrsim n \right)$ (Thm.~\ref{thm.main},\ref{thm.loweralphalargerthanone})  \\ \hline

$F_\alpha(P), \alpha\geq \frac{3}{2}$ & $n^{-1}$ (Thm.~\ref{thm.main})  & $n^{-1}$  \\ \hline
    \end{tabular}

    \caption{Summary of results in this paper and the companion~\cite{Jiao--Venkat--Han--Weissman2014minimax}}
     \label{table.summary}
\end{center}
\end{table}

Table~\ref{table.summary} demonstrates that the MLE cannot achieve the minimax risk for estimation of $H(P)$, and $F_\alpha(P)$ when $0 < \alpha < 3/2$. In these cases, there exist strictly better estimators whose performance with $n$ samples is roughly the same as that of the MLE with $n \ln n$ samples. In other words, the optimal estimators \emph{enlarge} the effective sample size by a logarithmic factor.

To our knowledge, Paninski \cite{Paninski2003} was the first to have realized the connection between Bernstein polynomials and bias of MLE. In the same paper \cite{Paninski2003}, Paninski demonstrated that if $n = cS$, where $c>0$ is a constant, the maximum squared bias of $H(P_n)$, and the Miller--Madow bias-corrected estimator $H^{\mathrm{MM}}(P_n)$, would be bounded from zero. Theorem~\ref{thm.lowerentropy} is the first to provide precise non-asymptotic constants in lower bounding the maximum $L_2$ risk of $H(P_n)$ and $H^{\mathrm{MM}}(P_n)$.

We now present the proofs of Theorem~\ref{thm.main},~\ref{thm.loweralphalargerthanone},~\ref{thm.lowerfalpha}, and~\ref{thm.lowerentropy} in Section~\ref{sec.outline}. Proofs of lemmas are provided in the appendices.

\section{Proofs of main results}\label{sec.outline}

In the sequel, we denote the $n$ samples as $n$ i.i.d. random variables $\{Z_i\}_{1\leq i\leq n}$ taking values in $\mathcal{Z} = \{1,2,\ldots,S\}$ with probability $(p_1,p_2,\ldots,p_S)$. Defining
\begin{equation}
X_i \triangleq \sum_{j = 1}^n \mathbbm{1}(Z_j = i),\quad 1\leq i \leq S,
\end{equation}
we know that $(X_1,X_2,\ldots,X_S)$ follows a multinomial distribution with parameter $(n;p_1,p_2,\ldots,p_S)$. Denote $h_j \triangleq \sum_{i = 1}^S \mathbbm{1}(X_i = j),\quad 0\leq j \leq n$. Then it is evident that the MLE $F(P_n)$ can be alternatively represented as the following linear function of $(h_0,h_1,\ldots,h_n)$:
\begin{equation}
F(P_n) = \sum_{j = 0}^n f\left( \frac{j}{n} \right) h_j.
\end{equation}

\subsection{Proof of Theorem~\ref{thm.main}}

\subsubsection{Bounding the bias}
We first work to bound the bias. Lemma~\ref{lemma.biasgeneralf} shows that the bias of $F(P_n)$ could be represented as
\begin{equation}
\mathsf{Bias}(F(P_n)) = \sum_{i = 1}^S \left( B_n[f](p_i) - f(p_i) \right),
\end{equation}
where $B_n[f](x)$ is the Bernstein polynomial corresponding to $f(x)$. The following lemma summarizes some state-of-the-art bounds for approximation error of Bernstein polynomials. We remark that Lemma~\ref{lemma.bernsteinerror} can be derived easily from the general theory we presented in Section~\ref{sec.generalbiasanalysis}.

\begin{lemma}\label{lemma.bernsteinerror}
The following bounds are valid for function approximation error incurred by Bernstein polynomials:
\begin{enumerate}
\item \cite[Cor. 2.2.1]{Paltanea2004}\cite{Paltanea2008some} for all continuous functions $f$ on $[0,1]$,
\begin{equation}\label{eqn.bern1}
|f(x)-B_n[f](x)| \leq \frac{3}{2} \omega^2\Bigg(f, \sqrt{\frac{x(1-x)}{n}}\Bigg),
\end{equation}
and the constant $3/2$ is shown by \cite{Paltanea2008some} to be the best constant;
\item \cite[Eqn. 10.3.4]{Devore--Lorentz1993} for $f\in C^2[0,1]$, i.e., twice continuously differentiable,
\begin{equation}\label{eqn.bern2}
 | f(x) - B_n[f](x) | \leq \| f'' \|_\infty \frac{x(1-x)}{2n};
\end{equation}
\item \cite[Cor. 4.1.10]{Paltanea2004} for $\varphi(x) = \sqrt{x(1-x)}$ and all continuous functions $f$ on $[0,1]$, we have
\begin{equation}\label{eqn.bern3}
\| B_n[f](x) - f(x) \|_\infty \leq \frac{5}{2}\omega_\varphi^2(f,n^{-1/2});
\end{equation}
\end{enumerate}
\end{lemma}

\begin{proof}
The first part of Lemma~\ref{lemma.bernsteinerror} follows from Lemma~\ref{lemma.paltaneacor221}. The third part of Lemma~\ref{lemma.bernsteinerror} follows from Lemma~\ref{lemma.paltaneathm251}. Regarding the second part, suppose random variable $X \sim \mathsf{B}(n,x)$. We have
\begin{align}
|f(x) - B_n[f](x)|  & = |\bE_x f(X/n) - f(x)| \\
& = |\bE_x (f(x) + f'(x)(X/n-x) + \frac{1}{2} f''(\xi_X) (X/n-x)^2) ) - f(x)| \\
&  = \frac{1}{2} |\bE_x f''(\xi_X) (X/n-x)^2| \\
& \leq \frac{\| f''\|_\infty}{2} |\bE_x (X/n-x)^2| \\
& = \frac{\| f''\|_\infty}{2} \frac{x(1-x)}{n},
\end{align}
where we used Taylor expansion for $f(X/n)$ at point $x$ with the Lagrange remainder. The proof is complete.
\end{proof}

\begin{remark}
Note that although (\ref{eqn.bern3}) is in the form of an upper bound, it has been shown to be a lower bound as well. Totik~\cite{Totik1994approximation} showed the following equivalence property on the norm estimate of Bernstein approximation errors
\begin{equation}
\| B_n[f](x) - f(x) \|_\infty \asymp \omega_\varphi^2(f,n^{-1/2}).
\end{equation}
\end{remark}

It is easy to calculate the second-order modulus of smoothness and the Ditzian--Totik second-order modulus of smoothness for functions $x^\alpha$ and $-x \ln x$. The results are presented in the following lemma.

\begin{lemma}\label{lemma.dtmoduluscomputation}
We have
\begin{center}
    \begin{tabular}{| l | l | l | l |}
    \hline
    & $x^\alpha, 0<\alpha<1$ & $x^\alpha, 1<\alpha< 2$ & $-x \ln x $ \\ \hline
    $\omega^2(f,t)$ & $|2-2^\alpha|t^\alpha$ &  $|2-2^\alpha|t^\alpha$ & $t \ln 4$  \\ \hline
    $\omega^2_\varphi(f,t)$ &  $|2-2^\alpha| \frac{t^{2\alpha}}{(1+t^2)^{\alpha}}$ & $ \asymp t^2$ & $\frac{t^2 \ln 4}{1+t^2}$ \\
    \hline
    \end{tabular}
\end{center}
where the second-order modulus results hold for $0<t\leq 1/2$, and the Ditizan--Totik second-order modulus results hold for $0<t\leq 1$.
\end{lemma}

We first bound the bias incurred by $F_{\alpha}(P_n)$.
\begin{enumerate}
\item $\alpha \geq 2$:

In this case, $f \in C^2[0,1]$, hence
\begin{equation}
|f(x) - B_n[f](x)| \leq \frac{\alpha (\alpha-1) x(1-x)}{2n}.
\end{equation}
Thus, we have
\begin{equation}
|\mathsf{Bias}(F_{\alpha}(P_n))| \leq \sum_{i =1}^S \alpha (\alpha-1) \frac{p_i(1-p_i)}{2n} \leq \frac{\alpha (\alpha-1)}{2n}.
\end{equation}

\item $1<\alpha<2$

The following lemma presents a bound on the bias of $F_\alpha(P_n)$, which does not depend on the alphabet size $S$.

\begin{lemma}\label{lemma.biasalphaonetwo}
The bias of $F_\alpha(P_n)$ for estimating $F_\alpha(P), 1<\alpha<2$, is upper bounded by the following:
\begin{equation}
|\mathsf{Bias}(F_{\alpha}(P_n))| \leq \frac{4}{n^{\alpha-1}}.
\end{equation}
\end{lemma}

We also present two additional bounds involving the alphabet size $S$. Using the pointwise estimate, the bias term of the MLE is upper bounded as follows for all $0<\alpha<2, \alpha \neq 1$:

\begin{align}
\sum_{i = 1}^S \frac{3}{2}|2-2^\alpha| \left( \frac{p_i(1-p_i)}{n} \right)^{\alpha/2} & \leq  \frac{3}{2}|2-2^\alpha|\frac{1}{n^{\alpha/2}} \sum_{i =1}^S p_i^{\alpha/2} \\
& \leq \frac{3}{2}|2-2^\alpha|\frac{1}{n^{\alpha/2}} S \frac{1}{S^{\alpha/2}}  \\
&  = \frac{3}{2}|2-2^\alpha|\frac{S^{1-\alpha/2}}{n^{\alpha/2}}. \label{eqn.biasoneandtwopoint}
\end{align}

Using the norm estimate, when $1<\alpha<2$, the bias would be upper bounded by $C_{\alpha,n} \frac{5S}{2n}$, where $C_{\alpha,n} = n \omega_\varphi^2(x^\alpha,n^{-1/2})$ is a finite positive constant such that $\limsup_{n\to \infty} C_{\alpha,n}<\infty$ for $1<\alpha<2$. Combining Lemma~\ref{lemma.biasalphaonetwo}, the pointwise estimate, and the norm estimate, we know that the bias of $F_\alpha(P_n)$ for $1<\alpha<2$ is upper bounded as
\begin{equation}
|\mathsf{Bias}(F_\alpha(P_n))| \leq  \frac{4}{n^{\alpha-1}} \wedge  \frac{3}{2}|2-2^\alpha|\frac{S^{1-\alpha/2}}{n^{\alpha/2}} \wedge C_{\alpha,n}\frac{5S}{2n}.
\end{equation}

\item $0<\alpha<1$:

The pointwise estimate is given by (\ref{eqn.biasoneandtwopoint}). Using the norm estimate, the bias would be upper bounded by $|2-2^\alpha| \frac{5S}{2n^\alpha}$. Combining the pointwise estimate and the norm estimate, we know that the bias of $F_\alpha(P_n)$ for $0<\alpha<1$ is upper bounded as
\begin{equation}
|\mathsf{Bias}(F_\alpha(P_n))| \leq   \frac{3}{2}|2-2^\alpha|\frac{S^{1-\alpha/2}}{n^{\alpha/2}} \wedge |2-2^\alpha|\frac{5S}{2n^\alpha}.
\end{equation}

\item Upper bound on $|\mathsf{Bias}(H(P_n))|$:

Using the norm estimate, we know
\begin{equation}
|\mathsf{Bias}(H(P_n))| \leq \frac{5S \ln 4}{2n}.
\end{equation}
Using the pointwise estimate, we obtain
\begin{equation}
|\mathsf{Bias}(H(P_n))| \leq \frac{3}{2}\sqrt{\frac{S}{n}} \ln 4.
\end{equation}

It was shown by \cite[Prop. 1]{Paninski2003} that the squared bias of MLE $H(P_n)$ is upper bounded as
\begin{equation}\label{eqn.paninskientropy}
(\mathsf{Bias}(H(P_n)))^2 \leq \left( \ln \left( 1+ \frac{S-1}{n} \right) \right)^2,
\end{equation}
which is better than the two bounds we obtained using Bernstein polynomial results. However, we remark that (\ref{eqn.paninskientropy}) is obtained using special properties of the entropy function and connections between KL-divergence and $\chi^2$-divergence \cite{Tsybakov2008}, which cannot be applied to general functions.

\end{enumerate}

To the best of our knowledge, \cite{Strukov--Timan1977mathematical} was the first to analyze the non-asymptotic bias of the MLE in estimating $F_\alpha(P)$ and $H(P)$, but the techniques were specialized to these functionals.

\subsubsection{Bounding the variance}

The Efron--Stein inequality gives a general upper bound on the variance.
\begin{lemma}\label{lemma.esnew}\cite[Theorem 3.1]{Boucheron--Lugosi--Massart2013}
Let $Z_1,\ldots,Z_n$ be independent random variables and let $f(Z_1,Z_2,\ldots,Z_n)$ be a square integrable function. Moreover, if $Z_1',Z_2',\ldots,Z_n'$ are independent copies of $Z_1,Z_2,\ldots,Z_n$ and if we define, for every $i = 1,2,\ldots,n$,
\begin{equation}
f_i' = f(Z_1,Z_2,\ldots,Z_{i-1},Z_i',Z_{i+1},\ldots,Z_n),
\end{equation}
then
\begin{equation}
\mathsf{Var}(f) \leq \frac{1}{2} \sum_{i = 1}^n \bE \left[ (f - f_i')^2 \right].
\end{equation}
\end{lemma}

The following inequality, which is called the bounded differences inequality, is a useful corollary of the Efron--Stein inequality.

\begin{lemma}\label{lemma.es}\cite[Corollary 3.2]{Boucheron--Lugosi--Massart2013}
If function $f: \mathcal{Z}^n \to \mathbb{R}$ has the \emph{bounded differences property}, i.e. for some nonnegative constants $c_1,c_2,\ldots,c_n$,
\begin{equation}
\sup_{z_1,\ldots,z_n,z_i'\in \mathcal{Z}} |f(z_1,\ldots,z_n) - f(z_1,\ldots,z_{i-1},z_i',z_{i+1},\ldots,z_n)| \leq c_i, 1\leq i \leq n,
\end{equation}
then
\begin{equation}
\mathsf{Var}(f(Z_1,Z_2,\ldots,Z_n)) \leq \frac{1}{4}\sum_{i=1}^n c_i^2,
\end{equation}
given that $Z_1,Z_2,\ldots,Z_n$ are independent random variables.
\end{lemma}

\begin{corollary}\label{cor.vargeneralf}
The variance of $F(P_n)$ satisfies the following upper bound:
\begin{equation}
\mathsf{Var}(F(P_n)) \leq n\cdot\max_{0\leq j <n}(f((j+1)/n)-f(j/n))^2.
\end{equation}
If $f(\cdot)$ is monotone, then we can strengthen the bound to be
\begin{equation}
\mathsf{Var}(F(P_n)) \leq \frac{n}{4}\cdot\max_{0\leq j <n}(f((j+1)/n)-f(j/n))^2.
\end{equation}
\end{corollary}

Now we bound the variance for $F_\alpha(P_n),\alpha>1$. We have
\begin{equation}
\max_{0\leq j <n} (((j+1)/n)^\alpha - (j/n)^\alpha)^2 \leq \left( 1- \left( 1- \frac{1}{n} \right)^\alpha \right)^2 \leq\left( \frac{\alpha}{n} \right)^2,
\end{equation}
where in the last step we used Bernoulli's inequality: $(1+x)^r \geq 1+rx,\forall r \geq 1, x>-1, x\in \mathbb{R}$. Using Lemma~\ref{lemma.es}, we know the variance is upper bounded by
\begin{equation}
\mathsf{Var}(F_\alpha(P_n)) \leq \frac{\alpha^2}{4n}.
\end{equation}

We bound the variance of $F_\alpha(P_n), 0<\alpha<1$ in the following lemma.

\begin{lemma}\label{lemma.varianceboundfalphabetween01}
For $0<\alpha<1$, we have
  \begin{align}
    \sup_{P\in\mathcal{M}_S}\mathsf{Var}(F_\alpha(P_n)) &\le \begin{cases}  \frac{10S}{n^{2\alpha}}+ \left(\frac{3\alpha\cdot2^{3+2\alpha}+1}{8\alpha^2}\left(\frac{8\alpha}{e}\right)^{2\alpha}+4\right)\left(\frac{S}{n^{2\alpha}}\wedge \frac{1}{n^{2\alpha-1}}\right) & 0<\alpha<1/2 \\ \frac{10S^{2-2\alpha}}{n}+ \left(\frac{3\alpha\cdot2^{3+2\alpha}+1}{8\alpha^2}\left(\frac{8\alpha}{e}\right)^{2\alpha}+4\right)\left(\frac{S}{n^{2\alpha}}\wedge \frac{1}{n^{2\alpha-1}}\right) & 1/2\leq \alpha<1 \end{cases} \\
    &\lesssim \begin{cases} \frac{S}{n^{2\alpha}}  & \ 0<\alpha<1/2 \\ \frac{S^{2-2\alpha}}{n} + \left(\frac{S}{n^{2\alpha}}\wedge \frac{1}{n^{2\alpha-1}}\right) & \ 1/2\leq \alpha<1 \end{cases}
  \end{align}
\end{lemma}

Further, one can show that for all $\alpha\in (0,1)$,
\begin{equation}
\frac{3\alpha\cdot2^{3+2\alpha}+1}{8\alpha^2}\left(\frac{8\alpha}{e}\right)^{2\alpha}+4 \leq \frac{120}{\alpha^2},
\end{equation}
which is used in Theorem~\ref{thm.main}.

Regarding the variance of $H(P_n)$, we have
\begin{lemma}\label{lemma.varianceboundentropymle}
\begin{equation}
\sup_{P \in \mathcal{M}_S} \mathsf{Var}(H(P_n)) \leq \frac{(\ln n)^2}{n}\wedge \frac{2(\ln S + 2)^2}{n} \lesssim \frac{(\ln S)^2 \wedge (\ln n)^2}{n}.
\end{equation}
\end{lemma}

\subsection{Proofs of Theorem~\ref{thm.loweralphalargerthanone}, \ref{thm.lowerfalpha} and ~\ref{thm.lowerentropy}}

The following lemma was proved in \cite{Braess--Sauer2004}.
\begin{lemma}\label{lemma.qn1lower}
Let $k\geq 4$ be an even number. Suppose that the $k$-th derivative of $f$ satisfies $f^{(k)} \leq 0$ in $(0,1)$, $Q_{k-1}$ is the Taylor polynomial of order $k-1$ to $f$ at some $x_1$ in $(0,1)$. Then for $x\in [0,1]$,
\begin{equation}
f(x) - B_n[f](x) \geq Q_{k-1} - B_n[Q_{k-1}](x).
\end{equation}
\end{lemma}

\subsubsection{Proof of Theorem~\ref{thm.loweralphalargerthanone}: lower bounds for estimation of $F_\alpha(P)$ when $1<\alpha<3/2$}

Consider $f_\alpha(x) = -x^\alpha, 1<\alpha<2, x\in [0,1]$. Applying Lemma~\ref{lemma.qn1lower} to $f_\alpha$, taking $k = 6$, we have the following result.

\begin{lemma}\label{lemma.biasalphalarge}
Suppose $f_\alpha(x) = -x^\alpha, 1<\alpha<2$ on $[0,1]$. For all $x\in (0,1)$, we have
\begin{align}
\hspace*{-4cm} & f_\alpha(x) -B_n[f_\alpha](x) \nonumber \\
\quad & \geq \max \left \{ \frac{\alpha(\alpha-1)x^{\alpha-2}(1-x)}{2n} \left( x + \frac{(2-\alpha)(3\alpha-1)x}{12n} + \frac{(2-\alpha)(5-3\alpha)}{12n} \right)  + \frac{R_1(x)}{n^3} + \frac{R_2(x)}{n^4}, 0 \right \},
\end{align}
where
\begin{align}
R_1(x) & = \frac{\alpha(\alpha-1)(\alpha-2)(\alpha-3) x^{\alpha-3} (1-x)}{24} \left( 1+2(1-x)((5-2\alpha)x + \alpha-4) \right), \\
R_2(x) & = \frac{\alpha(\alpha-1)(\alpha-2)(\alpha-3)(\alpha-4) x^{\alpha-4} (1-x)(1-2x)(1-12x(1-x))}{120}.
\end{align}
\end{lemma}

Note that we have assumed $S = cn,c>0$. If $c\leq 1$, we take a uniform distribution on $S$ elements $P = (1/S,1/S,\ldots,1/S)$, otherwise we take distribution $P = (1/n,1/n,\ldots,1/n,0,\ldots,0)$. We first analyze the $c\leq 1$ case. Applying Lemma~\ref{lemma.biasalphalarge}, we have
\begin{align}
& \sum_{i = 1}^S f_\alpha(1/S) - B_n[f_\alpha](1/S) \nonumber \\
& = \bE F_\alpha(P_n) - F_\alpha(P) \nonumber \\
& \geq S \cdot \Big( \frac{\alpha(\alpha-1)}{2 S^{\alpha-2}n} \left( \frac{1}{S} + \frac{(2-\alpha)(5-3\alpha)}{12n} \right) \nonumber \\
&  \quad + \frac{\alpha(\alpha-1)(\alpha-2)(\alpha-3)}{24S^{\alpha-3}n^3}(1+2(\alpha-4)) + \frac{\alpha(\alpha-1)(\alpha-2)(\alpha-3)(\alpha-4)}{120S^{\alpha-4} n^4} + o(n^{-\alpha})\Big ) \nonumber \\
& = \frac{\alpha(\alpha-1)}{n^{\alpha-1}} \Big( \frac{1}{2c^{\alpha-3}}\left(\frac{1}{c}+\frac{(2-\alpha)(5-3\alpha)}{12}\right) + \frac{(\alpha-2)(\alpha-3)(1+2(\alpha-4))}{24 c^{\alpha-4}} \nonumber\\
& \quad + \frac{(\alpha-2)(\alpha-3)(\alpha-4)}{120c^{\alpha-5}} \Big) + o(n^{-(\alpha-1)}) \nonumber\\
& = \frac{\alpha(\alpha-1)c^{2-\alpha}}{n^{\alpha-1}} \Big(\frac{1}{2}+ \frac{(2-\alpha)(5-3\alpha)c}{24} +  \frac{(\alpha-2)(\alpha-3)(1+2(\alpha-4))c^{2}}{24 } \nonumber\\
& \quad + \frac{(\alpha-2)(\alpha-3)(\alpha-4)c^{3}}{120} \Big) + o(n^{-(\alpha-1)}) \nonumber \\
& \geq \frac{\alpha c^{2-\alpha}(124-330\alpha + 285 \alpha^2-90 \alpha^3 + 11 \alpha^4)}{120 n^{\alpha-1}} + o(n^{-(\alpha-1)}), \nonumber
\end{align}
where in the last step we have taken $c = 1$ in the following expression
\[
\frac{1}{2}+ \frac{(2-\alpha)(5-3\alpha)c}{24} +  \frac{(\alpha-2)(\alpha-3)(1+2(\alpha-4))c^{2}}{24 } + \frac{(\alpha-2)(\alpha-3)(\alpha-4)c^{3}}{120},
\]
and considered the fact that it is a monotonically decreasing function with respect to $c$ on $(0,1]$ for any $\alpha\in (1,3/2)$.

For cases when $c>1$, since we take $P = (1/n,1/n,\ldots,1/n,0,\ldots,0)$, the analysis is exactly the same as that above when we set $c=1$. One can verify that the function $\alpha(124-330\alpha + 285 \alpha^2-90 \alpha^3 + 11 \alpha^4)/120$ is positive on interval $(1,3/2)$. Defining $\sqrt{c_\alpha} = \alpha c^{2-\alpha}(124-330\alpha + 285 \alpha^2-90 \alpha^3 + 11 \alpha^4)/120>0$ when $c\leq 1$, and $\sqrt{c_\alpha} = \alpha (124-330\alpha + 285 \alpha^2-90 \alpha^3 + 11 \alpha^4)/120>0$ when $c>1$, Theorem~\ref{thm.loweralphalargerthanone} is proved.

\subsubsection{Proof of Theorem~\ref{thm.lowerfalpha}: lower bounds for estimation of $F_\alpha(P)$ when $0<\alpha<1$}

Applying Lemma~\ref{lemma.qn1lower} to function $f_\alpha(x) = x^\alpha, \alpha \in (0,1)$, taking $k = 4$, we have the following result:
\begin{lemma}\label{lemma.alphalower}
For $f_\alpha(x) = x^\alpha$ on $[0,1]$, $\alpha\in (0,1),  x\in (0,1)$, we have
\begin{equation}
f_\alpha(x) - B_n[f_\alpha](x) \geq \max \left\{ \frac{\alpha(1-\alpha)}{2n} x^{\alpha-2} (1-x) \left( x - \frac{2-\alpha}{3n} \right), 0\right\}
\end{equation}
\end{lemma}

Suppose $\forall 1\leq i\leq S$, $p_i\geq \frac{1}{n}$. We have $n\geq S$. Applying Lemma~\ref{lemma.alphalower},
\begin{align}
F_\alpha(P) - \bE F_\alpha(P_n) & \geq \sum_{i = 1}^S \frac{\alpha(1-\alpha)}{2n} p_i^{\alpha-2} (1-p_i) \frac{1}{3n} \\
& = \sum_{i =1}^S \frac{\alpha(1-\alpha)}{6n^2}p_i^{\alpha-2} (1-p_i)
\end{align}

For distribution $W = (w_1,w_2,\ldots,w_S) \in \mathcal{M}_S$ such that
\begin{equation}
1\leq i \leq S-1, w_i = \frac{1}{n}; \quad w_S = 1- \frac{S-1}{n},
\end{equation}
we have
\begin{align}
F_\alpha(W) - \bE_W F_\alpha(P_n) &  \geq \sum_{i = 1}^{S-1} \frac{\alpha(1-\alpha)}{6n^2} \left(\frac{1}{n} \right)^{\alpha-2} \left( 1-\frac{1}{n} \right) \\
& = \frac{\alpha(1-\alpha)(S-1)}{6n^\alpha}\frac{n-1}{n}.
\end{align}
Thus, we know for all $0<\alpha<1$,
\begin{equation}
\sup_{P \in \mathcal{M}_S} \bE_P \left( F_\alpha(P) - F_\alpha(P_n) \right)^2 \geq \frac{\alpha^2(1-\alpha)^2 (S-1)^2}{36 n^{2\alpha}} \left( 1-\frac{1}{n}\right)^2.
\end{equation}

It is shown in \cite{Jiao--Venkat--Han--Weissman2014minimax} that the following minimax lower bound holds for estimation of $F_\alpha(P), 1/2\leq \alpha<1$.
\begin{lemma}\label{lemma.minimaxlowerfalpha12to1}
 For $\frac{1}{2}\le\alpha<1$, we have
  \begin{align}
    \inf_{\hat{F}}\sup_{P\in\mathcal{M}_S} \bE_P\left(\hat{F}-F_\alpha(P)\right)^2 &\ge \frac{\alpha^2}{32en}\left[(2(S-1))^{1-\alpha}-2^{-\alpha} -\frac{1-\alpha}{4n}\left((2(S-1))^{1-\alpha}+2^{-\alpha}\right)\right]^2 \nonumber \\
    & \quad \quad  - e^{-n/4}S^{2(1-\alpha)}\nonumber \\
    &\gtrsim \frac{S^{2-2\alpha}}{n},
  \end{align}
  where the infimum is taken over all possible estimators.
  \end{lemma}
Since this lower bound holds for all possible estimators, it also holds for the MLE $F_\alpha(P_n)$. In other words,
\begin{align}
& \sup_{P \in \mathcal{M}_S} \bE_P \left( F_\alpha(P) - F_\alpha(P_n) \right)^2 \\
& \quad \geq \frac{\alpha^2}{32en}\left[(2(S-1))^{1-\alpha}-2^{-\alpha} -\frac{1-\alpha}{4n}\left((2(S-1))^{1-\alpha}+2^{-\alpha}\right)\right]^2 - e^{-n/4}S^{2(1-\alpha)}.
\end{align}

Since $\max\{a,b\}\geq \frac{1}{2}(a+b)$, we have the desired bound in Theorem~\ref{thm.lowerfalpha}.

\subsubsection{Proof of Theorem~\ref{thm.lowerentropy}: lower bounds for estimation of $H(P)$}

Braess and Sauer \cite{Braess--Sauer2004} derived the following lower bound for the approximation error of Bernstein polynomials for the function $g(x) = -x \ln x$:
\begin{lemma}\label{lemma.glower}
Define $g(x) = -x\ln x$ on $[0,1]$. For $x \geq \frac{15}{n}, x\in [0,1]$, we have
\begin{equation}
g(x) - B_n[g](x) \geq \frac{1-x}{2n} + \frac{1}{20n^2 x} - \frac{x}{12 n^2}.
\end{equation}
\end{lemma}

Applying Lemma~\ref{lemma.glower} to the estimation of $H(P)$, we know that if $\forall 1\leq i\leq S, p_i \geq \frac{15}{n}$,
\begin{equation}
H(P) - \bE H(P_n) \geq \frac{S-1}{2n} + \frac{1}{20n^2} \left( \sum_{i = 1}^S \frac{1}{p_i} \right) - \frac{1}{12n^2}.
\end{equation}
In order to guarantee that $\forall 1\leq i\leq S, p_i\geq \frac{15}{n}$, we need
\begin{equation}
1 = \sum_{i = 1}^S p_i \geq \sum_{i =1}^S \frac{15}{n} = \frac{15S}{n},
\end{equation}
which implies that
\begin{equation}
n \geq 15S.
\end{equation}
Since
\begin{equation}
\sum_{i = 1}^S \frac{1}{p_i} \geq S^2,
\end{equation}
we have
\begin{equation}
\sup_{P\in \mathcal{M}_S} \left(  H(P) - \bE H(P_n) \right)  \geq \frac{S-1}{2n} + \frac{S^2}{20n^2} - \frac{1}{12n^2}.
\end{equation}
Thus, when $n\geq 15S$,
\begin{equation}
\sup_{P\in \mathcal{M}_S} \bE_P \left( H(P) - H(P_n) \right)^2 \geq \left( \frac{S-1}{2n} + \frac{S^2}{20n^2} - \frac{1}{12n^2} \right)^2.
\end{equation}

It was shown in \cite[Prop. 1]{Wu--Yang2014minimax} that the following minimax lower bound holds.
\begin{lemma}\label{lemma.minimaxlowerentropyvariance}
There exists a universal constant $c>0$ such that
\begin{equation}
\inf_{\hat{H}} \sup_{P \in \mathcal{M}_S} \bE_P \left( \hat{H} - H(P) \right)^2 \geq c \frac{\ln^2 S}{n},
\end{equation}
where the infimum is taken over all possible estimators $\hat{H}$.
\end{lemma}

Hence, we have
\begin{align}
& \sup_{P\in \mathcal{M}_S} \bE_P \left( H(P) - H(P_n) \right)^2 \nonumber \\
& \quad \geq \max\left\{ \left( \frac{S-1}{2n} + \frac{S^2}{20n^2} - \frac{1}{12n^2} \right)^2 , c \frac{\ln^2 S}{n} \right\}  \\
& \quad \geq \frac{1}{2}\left( \frac{S-1}{2n} + \frac{S^2}{20n^2} - \frac{1}{12n^2} \right)^2 + \frac{c}{2} \frac{\ln^2 S}{n}.
\end{align}

Similar arguments can be applied to the Miller--Madow estimator.

\section*{Acknowledgments}

We thank Dany Leviatan, Gancho Tachev, and Radu Paltanea for very helpful discussions regarding the literature on approximation theory using positive linear operators. We thank Jayadev Acharya, Alon Orlitsky, Ananda Theertha Suresh, and Himanshu Tyagi for communicating to us the independent discovery that it suffices to take $n\gg 1$ samples to consistently estimate $F_\alpha(P)$, when $\alpha>1$.

\appendices

\section{Auxiliary Lemmas}
We begin with the definition of the negative association property, which allows us to upper bound the variance by treating each component of the empirical distribution $P_n(i)$ as ``independent'' random variables.
\begin{definition}
  \cite[Def. 2.1]{joag-dev1983} Random variables $X_1,X_2,\cdots,X_S$ are said to be negatively associated if for any pair of disjoint subsets $A_1,A_2$ of $\{1,2,\cdots,S\}$, and any component-wise increasing functions $f_1,f_2$,
  \begin{align}
   \mathsf{Cov}\left(f_1(X_i,i\in A_1), f_2(X_j,j\in A_2)\right) \le 0.
  \end{align}
\end{definition}

To verify whether random variables $X_1,X_2,\cdots,X_S$ are negatively associated or not, the following lemma presents a useful criterion.
\begin{lemma}\label{lem_NA}
  \cite[Thm. 2.9]{joag-dev1983} Let $X_1,X_2,\cdots,X_S$ be $S$ independent random variables with log-concave densities. Then the joint conditional distribution of $X_1,X_2,\cdots,X_S$ given $\sum_{i=1}^S X_i$ is negatively associated.
\end{lemma}

In light of the preceding lemma, we can obtain the following corollary.
\begin{corollary}\label{cor_NA_Multinomial}
  For any discrete probability distribution vector $P\in\mathcal{M}_S$, the random variables $\mathbf{X}=(X_1,X_2,\cdots,X_S)$ drawn from the Multinomial distribution $\mathbf{X}\sim\mathsf{Multinomial}(n,P)$ are negatively associated.
\end{corollary}
\begin{proof}
  Consider the Poissonized model $Y_i\sim \mathsf{Poi}(np_i), 1\le i\le S$ with all $Y_i$ independent, it is straightforward to verify that each $Y_i$ possesses a log-concave distribution. Then conditioning on $\sum_{i=1}^S Y_i=n$, we know that $(Y_1,Y_2,\cdots,Y_S)|(\sum_{i=1}^S Y_i=n) \sim \mathsf{Multinomial}(n,P)$, hence Lemma \ref{lem_NA} yields the desired result.
\end{proof}

The following lemma gives some tail bounds for Poisson or Binomial random variables.
\begin{lemma}\label{lem_chernoff}
\cite[Exercise 4.7]{mitzenmacher2005probability} If $X\sim \mathsf{Poi}(\lambda)$ or $X\sim \mathsf{B}(n,\frac{\lambda}{n})$, then for any $\delta>0$, we have
\begin{align}
\bP(X \geq (1+\delta) \lambda) & \leq \left( \frac{e^\delta}{(1+\delta)^{1+\delta}} \right)^\lambda, \\
\bP(X \leq (1-\delta) \lambda) & \leq  \left( \frac{e^{-\delta}}{(1-\delta)^{1-\delta}} \right)^\lambda\leq  e^{-\delta^2\lambda/2}.
\end{align}
\end{lemma}

To establish the upper bound of the variance obtained by the plug-in estimator $F_\alpha(P_n)$, we split $p$ into two different regimes $p\le 1/n$ or $p>1/n$, and the following lemmas give the corresponding variance bounds.
\begin{lemma}\label{lem_variance_p_small}
  For $nX\sim\mathsf{B}(n,p),p\le 1/n$, we have
  \begin{align}
    \mathsf{Var}(X^\alpha) \le  \frac{2}{n^{2\alpha}}\wedge \frac{2p}{n^{2\alpha-1}}  \quad 0<\alpha<1 .
  \end{align}
\end{lemma}
\begin{lemma}\label{lem_variance_p_big}
  For $nX\sim\mathsf{B}(n,p),p> 1/n$, we have
  \begin{align}
\mathsf{Var}(X^\alpha) \le  \frac{10p^{2\alpha-1}}{n} + \frac{3}{2\alpha}\left(\frac{16\alpha}{en}\right)^{2\alpha} + \frac{2}{n^{2\alpha}} + \frac{1}{8\alpha^2}\left(\frac{8\alpha}{en}\right)^{2\alpha} & \quad 0<\alpha<1
\end{align}
\end{lemma}

\section{Proofs of Main Lemmas}
\subsection{Proof of Lemma~\ref{lemma.biasgeneralf}}
We compute the first moment of $F(P_n)$.
\begin{equation}
\bE F(P_n) = \sum_{j = 0}^n f \left( \frac{j}{n} \right) \bE h_j,
\end{equation}
and
\begin{equation}
\bE h_j = \bE \sum_{i = 1}^S \mathbbm{1}(X_i = j) = \sum_{i = 1}^S \bP(X_i = j) = \sum_{i = 1}^S \binom{n}{j} p_i^j(1-p_i)^{n-j}.
\end{equation}
Thus, we have
\begin{equation}
\bE F(P_n) = \sum_{j = 0}^n f \left( \frac{j}{n} \right)\sum_{i = 1}^S \binom{n}{j} p_i^j(1-p_i)^{n-j} = \sum_{j = 0}^n \sum_{i = 1}^S f \left( \frac{j}{n} \right) \binom{n}{j} p_i^j(1-p_i)^{n-j}.
\end{equation}

The bias of $F(P_n)$ is
\begin{equation}
\mathsf{Bias}(F(P_n)) = \bE F(P_n) - F(P) =  \sum_{i = 1}^S \left( \sum_{j = 0}^n f \left( \frac{j}{n} \right) \binom{n}{j} p_i^j(1-p_i)^{n-j} - f(p_i) \right).
\end{equation}

\subsection{Proof of Lemma~\ref{lemma.biasalphaonetwo}}
The bias of $F_\alpha(P_n), 1<\alpha<2$ can be expressed as follows:
\begin{align}
| \mathsf{Bias}(F_\alpha(P_n))| & = | \bE \sum_{i = 1}^S P_n^\alpha(i) - p_i^\alpha | \\
& \leq \left| \bE \sum_{i: p_i \leq \frac{1}{n}} P_n^\alpha(i) - p_i^\alpha \right| + \left| \bE \sum_{i: p_i > \frac{1}{n}} P_n^\alpha(i) - p_i^\alpha \right| \\
& \triangleq B_1 + B_2.
\end{align}

Now we bound $B_1$ and $B_2$ separately. It follows from Jensen's inequality that for any $i$,
\begin{equation}
\bE P_n^\alpha(i) \geq p_i^\alpha, \quad 1\leq i \leq S.
\end{equation}

Hence, we have
\begin{align}
B_1 & = \bE \sum_{i: p_i \leq \frac{1}{n}} P_n^\alpha(i) - p_i^\alpha \\
& = \bE \sum_{i: p_i \leq \frac{1}{n}} P_n^\alpha(i) -  \frac{(np_i)^\alpha}{n^\alpha}  \\
& \leq \bE \sum_{i: p_i \leq \frac{1}{n}} P_n^\alpha(i) -  \frac{(np_i)^2}{n^\alpha}  \\
& = \bE \sum_{i: p_i \leq \frac{1}{n}} \frac{(n P_n(i))^\alpha}{n^\alpha}-  \frac{(np_i)^2}{n^\alpha}  \\
& \leq \bE \sum_{i: p_i \leq \frac{1}{n}} \frac{(n P_n(i))^2}{n^\alpha} -  \frac{(np_i)^2}{n^\alpha} \\
& = \sum_{i: p_i \leq \frac{1}{n}}  \frac{\bE(n P_n(i))^2}{n^\alpha}-  \frac{(np_i)^2}{n^\alpha}  \\
& = \sum_{i: p_i \leq \frac{1}{n}} \frac{(n p_i)^2 + np_i(1-p_i)}{n^\alpha}-  \frac{(np_i)^2}{n^\alpha} \\
& \leq \sum_{i: p_i \leq \frac{1}{n}} \frac{np_i}{n^\alpha}\\
& = \frac{1}{n^{\alpha-1}},
\end{align}
where we have used the fact that $nP_n(i) \geq 1$ for any $P_n(i)\neq 0$.

Regarding $B_2$, we have the following bounds:
\begin{align}
B_2 & = \left| \bE \sum_{i: p_i >\frac{1}{n}} P_n^\alpha(i) - p_i^\alpha \right| \\
& \leq \sum_{i: p_i > \frac{1}{n}} \bE | P_n^\alpha(i) - p_i^\alpha | \\
& \leq \sum_{i: p_i > \frac{1}{n}}  \frac{3}{2}|2-2^\alpha| \left( \frac{p_i(1-p_i)}{n} \right)^{\alpha/2} \\
& \leq \frac{3|2-2^\alpha|}{2n^{\alpha/2}} \sum_{i: p_i > \frac{1}{n}} p_i^{\alpha/2},
\end{align}
where the second inequality follows from the pointwise bound on the Bernstein approximation error in Lemma~\ref{lemma.bernsteinerror}.

Denoting $| \{ i: p_i > \frac{1}{n} \} | = K \leq n$, we know
\begin{equation}
\sum_{i: p_i > \frac{1}{n}} p_i^{\alpha/2} \leq K^{1-\alpha/2} \leq  n^{1-\alpha/2},
\end{equation}
which implies that
\begin{equation}
B_2 \leq \frac{3|2-2^\alpha|}{2n^{\alpha/2}}n^{1-\alpha/2} = \frac{3|2-2^\alpha|}{2n^{\alpha-1}}.
\end{equation}

Therefore, we have
\begin{align}
| \mathsf{Bias}(F_\alpha(P_n))| & \leq  B_1 + B_2 \\
& \leq \frac{1}{n^{\alpha-1}}+ \frac{3|2-2^\alpha|}{2n^{\alpha-1}} \\
& \leq \frac{3|2-2^\alpha| + 2}{2n^{\alpha-1}} \\
& \leq \frac{4}{n^{\alpha-1}}.
\end{align}

\subsection{Proof of Lemma~\ref{lemma.dtmoduluscomputation}}

We first compute the second-order modulus. Fix $t, 0< t\leq 1/2$. Defining $M \triangleq \frac{u+v}{2}$, then the computation of second-order modulus is equivalent to maximization of $|f(M-t) - 2 f(M) + f(M+t)|$ over interval $M \in [t, 1-t]$, since all the functions we consider are strictly convex or concave over $[0,1]$.

For $f(x) = x^\alpha,0<\alpha<1$, $f(x)$ is strictly concave on $[0,1]$. It follows from Jensen's inequality that
\begin{equation}
g(M) = (M-t)^\alpha - 2M^\alpha + (M+t)^\alpha \leq 0,
\end{equation}
and it suffices to minimize this function of $M$ in order to obtain the modulus. Taking derivative of $g(M)$, we have
\begin{equation}
g'(M) = \alpha \left( (M-t)^{\alpha-1} - 2 M^{\alpha-1} + (M+t)^{\alpha-1} \right) \geq 0,
\end{equation}
since $x^{\alpha-1}$ is a convex function on $[t,1-t]$. It implies that the function $g(M)$ is non-decreasing, and the minimum of $g(M)$ over $M\in [t,1-t]$ is attained at $M = t$, and the minimum value is $g(t) = (2^\alpha-2) t^\alpha$. Hence, the corresponding second-order modulus is $|2-2^\alpha| t^\alpha$.

Analogous procedures computes the second-order modulus for $x^\alpha,1<\alpha<2$ and $-x\ln x$.

Now we consider the computation of Ditzian--Totik second-order modulus. Fix $t, 0<t\leq 1$. Again denote $M \triangleq \frac{u+v}{2} \in [0,1]$. Then the optimization is over the regime $|u-v| \leq 2t\varphi(M) = 2t \sqrt{M(1-M)}$. Equivalently, it is the interval $[M-t\sqrt{M(1-M)},M+t\sqrt{M(1-M)}] \cap [0,1]$.

Since the function $f(x) = -x\ln x$ is strictly convex on $[0,1]$, the maximum of $\left|f(u)-2f\left(\frac{u+v}{2}\right)+f(v)\right|$ is definitely attained when $u$ and $v$ take the boundary values of the feasible interval $[M-t\sqrt{M(1-M)},M+t\sqrt{M(1-M)}] \cap [0,1]$.

Define $\Delta \triangleq t\sqrt{\frac{1-M}{M}}$. The feasible interval can be equivalently written as $[M-\Delta M, M+\Delta M] \cap [0,1]$. We have
\begin{equation}
M - t\sqrt{M(1-M)} \geq 0 \Leftrightarrow M \geq \frac{t^2}{1+t^2},
\end{equation}
as well as
\begin{equation}
M + t\sqrt{M(1-M)} \leq 1 \Leftrightarrow M \leq \frac{1}{1+t^2}.
\end{equation}

Hence, it is equivalent to maximize over three regimes:
\begin{enumerate}
\item Regime A:

$u = 0, v = 2M, 0\leq M \leq \frac{t^2}{1+t^2}$.
\item Regime B:

$u = M-\Delta M, v = M + \Delta M, M \in \left[ \frac{t^2}{1+t^2}, \frac{1}{1+t^2} \right]$
\item Regime C:

$u = 2M-1, v = 1, 1 \geq M \geq \frac{1}{1+t^2}$.
\end{enumerate}

Over regime A, we have
\begin{equation}
\left|f(u)-2f\left(\frac{u+v}{2}\right)+f(v)\right| = 2M \ln 2.
\end{equation}
Maximizing over $0\leq M \leq \frac{t^2}{1+t^2}$, the maximum value is $\frac{t^2 \ln 4}{1+t^2}$, attained at $M = \frac{t^2}{1+t^2}$.

Over regime C, we have
\begin{equation}
\left|f(u)-2f\left(\frac{u+v}{2}\right)+f(v)\right| = \left | 2M \ln M - (2M-1) \ln (2M-1) \right|.
\end{equation}
Maximizing over $\frac{1}{1+t^2} \leq M \leq 1$, the maximum is attained at $M = \frac{1}{1+t^2}$, and the maximum value is no more than $\frac{t^2 \ln 4}{1+t^2}$.

Now we consider regime B. Since $M  \in \left[ \frac{t^2}{1+t^2}, \frac{1}{1+t^2} \right]$ in regime B, we know $\Delta = t\sqrt{\frac{1-M}{M}} \in [t^2,1]$. We have

\begin{equation}
\left|f(u)-2f\left(\frac{u+v}{2}\right)+f(v)\right| = M\left | (1-\Delta)\ln(1-\Delta) + (1+\Delta)\ln(1+\Delta) \right|.
\end{equation}
Since $\Delta = t\sqrt{\frac{1-M}{M}}$ implies $M = \frac{t^2}{t^2 + \Delta^2}$, we can recast the corresponding optimization problem as maximizing
\begin{equation}
\frac{t^2}{\Delta^2 + t^2} \left | (1-\Delta)\ln(1-\Delta) + (1+\Delta)\ln(1+\Delta) \right|
\end{equation}
subject to constraint $\Delta \in [t^2, 1]$. One can show that the maximum is always attained at $\Delta = 1$, with the maximum value $\frac{t^2 \ln 4}{1+t^2}$.

To sum up, we conclude that when $0< t\leq 1$, the maximum of the optimization problem defining $\omega^2_\varphi(-x\ln x,t)$ is always attained at $u = 0, v = \frac{2t^2}{1+t^2}$, with the resulting modulus $\frac{t^2 \ln 4}{1+t^2}$.

Analogous computation can also be done for function $x^\alpha,0<\alpha<1$. For the function $x^\alpha,1<\alpha<2$, it is hard to compute the modulus exactly, but it is easy to show that it is of order $t^2$.

\subsection{Proof of Lemma~\ref{lemma.varianceboundfalphabetween01}}

In light of Lemma \ref{lem_variance_p_small} and \ref{lem_variance_p_big}, we have
\begin{align}
& \sum_{i=1}^S \mathsf{Var}(P_n(i)^\alpha) \nonumber \\
  &= \sum_{i: p_i\le 1/n} \mathsf{Var}(P_n(i)^\alpha) + \sum_{i: p_i> 1/n} \mathsf{Var}(P_n(i)^\alpha)\\
  &\le \sum_{i: p_i\le 1/n} \frac{2}{n^{2\alpha}}\wedge \frac{2p_i}{n^{2\alpha-1}}+ \sum_{i: p_i>1/n}\left(\frac{10p_i^{2\alpha-1}}{n} + \frac{3}{2\alpha}\left(\frac{16\alpha}{en}\right)^{2\alpha} + \frac{2}{n^{2\alpha}} + \frac{1}{8\alpha^2}\left(\frac{8\alpha}{en}\right)^{2\alpha}\right)\\
  &\le \begin{cases} \left(\frac{2S}{n^{2\alpha}}\wedge \frac{2}{n^{2\alpha-1}}\right)+  \frac{10S}{n^{2\alpha}} + \left(\frac{3\alpha\cdot2^{3+2\alpha}+1}{8\alpha^2}\left(\frac{8\alpha}{e}\right)^{2\alpha}+2\right)\left(\frac{S}{n^{2\alpha}}\wedge \frac{1}{n^{2\alpha-1}}\right) & \ 0<\alpha<1/2 \\ \left(\frac{2S}{n^{2\alpha}}\wedge \frac{2}{n^{2\alpha-1}}\right)+  \frac{10S^{2-2\alpha}}{n} + \left(\frac{3\alpha\cdot2^{3+2\alpha}+1}{8\alpha^2}\left(\frac{8\alpha}{e}\right)^{2\alpha}+2\right)\left(\frac{S}{n^{2\alpha}}\wedge \frac{1}{n^{2\alpha-1}}\right) & 1/2\leq \alpha<1 \end{cases}
\end{align}
where we have used the concavity of $x^{2\alpha-1}$ when $1/2\le \alpha<1$ in the last step.

Now we exploit the negative association property of all random variables $P_n(i),1\le i\le S$.  Corollary \ref{cor_NA_Multinomial} and monotonically increasing property of $x^\alpha$ yield
\begin{align}
  \mathsf{Var}(F_\alpha(P_n)) = \sum_{i=1}^S \mathsf{Var}(P_n(i)^\alpha) + 2\sum_{1\le i<j\le S}\mathsf{Cov}(P_n(i)^\alpha,P_n(j)^\alpha)\le \sum_{i=1}^S \mathsf{Var}(P_n(i)^\alpha),
\end{align}
thereby finishing the proof of Lemma~\ref{lemma.varianceboundfalphabetween01}.

\subsection{Proof of Lemma~\ref{lemma.varianceboundentropymle}}

The upper bound $(\ln n)^2/n$ follows from Corollary~\ref{cor.vargeneralf}. We apply the Efron--Stein inequality (Lemma~\ref{lemma.esnew}) to obtain the other bound. Denote the $n$ i.i.d. samples from distribution $P$ as $Z_1,Z_2,\ldots,Z_n \in \mathcal{Z}$. Denoting the MLE $H(P_n)$ as $\hat{H}(Z_1,Z_2,\ldots,Z_n)$, since it is invariant to any permutation of $\{Z_1,Z_2,\ldots,Z_n\}$, we know that the Efron--Stein inequality implies
\begin{equation}\label{eqn.entropyesnew}
\mathsf{Var}(H(P_n)) \leq \frac{n}{2} \bE \left( \hat{H}(Z_1,Z_2,\ldots,Z_n) - \hat{H}(Z_1',Z_2,\ldots,Z_n) \right)^2,
\end{equation}
where $Z_1'$ is an i.i.d. copy of $Z_1$.

Recall that
\begin{equation}
X_i = \sum_{j = 1}^n \mathbbm{1}(Z_j = i),\quad 1\leq i \leq S.
\end{equation}

For notional brevity, we denote the $S$-tuple $(X_1,X_2,\ldots,X_S)$ as $X_1^S$, and the $n$-tuple $(Z_1,Z_2,\ldots,Z_n)$ as $Z_1^n$. A specific realization of $(X_1,X_2,\ldots,X_S)$ is denoted by $x_1^S = (x_1,x_2,\ldots,x_S)$, and a specific realization of $(Z_1,Z_2,\ldots,Z_n)$ is denoted by $z_1^n = (z_1,z_2,\ldots,z_n)$.

In order to upper bound the right hand side of (\ref{eqn.entropyesnew}), we first condition on $\{X_1,X_2,\ldots,X_S\}$. In other words, we use
\begin{align}
& \bE \left( \hat{H}(Z_1,Z_2,\ldots,Z_n) - \hat{H}(Z_1',Z_2,\ldots,Z_n) \right)^2 \\
 & \quad = \sum_{x_1^S} \bP(X_1^S = x_1^S) \bE \left[ \left( \hat{H}(Z_1,Z_2,\ldots,Z_n) - \hat{H}(Z_1',Z_2,\ldots,Z_n) \right)^2 \Bigg | X_1^S = x_1^S\right].
\end{align}

The following lemma calculates the conditional distribution of $Z_1$ conditioned on $(X_1,X_2,\ldots,X_S)$.
\begin{lemma}\label{lemma.conditionalpaninski}
The conditional distribution of $Z_1$ conditioned on $(X_1,X_2,\ldots,X_S)$ is given by the following discrete distribution:
\begin{equation}
(X_1/n,X_2/n,\ldots,X_S/n).
\end{equation}
\end{lemma}

\begin{proof}
By definition of conditional distribution, for any $k, 1\leq k \leq S$, we have
\begin{align}
\bP(Z_1=k| X_1^S = x_1^S) & = \frac{\bP(Z_1 = k, X_1^S = x_1^S)}{\bP(X_1^S = x_1^S)} \\
& = \frac{\bP(Z_1 = k)\bP(X_1^S = x_1^S|Z_1 = k)}{\bP(X_1^S = x_1^S)} \\
& = \frac{p_k \binom{n-1}{x_1,x_2,\ldots,x_k-1,\ldots,x_S} p_k^{x_k-1} \prod_{i \neq k} p_i^{x_i}}{\binom{n}{x_1,x_2,\ldots,x_S} \prod_{1\leq i\leq S} p_i^{x_i}} \\
& = \frac{\binom{n-1}{x_1,x_2,\ldots,x_k-1,\ldots,x_S}}{\binom{n}{x_1,x_2,\ldots,x_S}} \\
& = \frac{x_k}{n},
\end{align}
where the multinomial coefficient $\binom{n}{x_1,x_2,\ldots,x_S}$ is defined as
\begin{equation}
\binom{n}{x_1,x_2,\ldots,x_S} = \frac{n!}{\prod_{i = 1}^S x_i!}.
\end{equation}
\end{proof}

Denoting $r(p) = -p\ln p$, we have $r(j/n) \triangleq\frac{-j}{n}\ln \frac{j}{n}$. We rewrite
\begin{equation}
\hat{H}(Z_1',Z_2,\ldots,Z_n)-\hat{H}(Z_1,Z_2,\ldots,Z_n)  = D_- + D_+,
\end{equation}
where
\begin{align}
D_- & = r\left( \frac{X_{Z_1}-1}{n} \right) - r\left(\frac{X_{Z_1}}{n}\right)\\
D_+ & = \begin{cases} r\left(\frac{X_{Z_1'+1}}{n} \right) - r\left(\frac{X_{Z_1'}}{n}\right) & Z_1 \neq Z_1'\\ r\left(\frac{X_{Z_1'}}{n} \right) - r\left(\frac{X_{Z_1'-1}}{n}\right) & Z_1 = Z_1' \end{cases}
\end{align}

Here, $D_-$ is the change in $\hat{H}$ that occurs when $Z_1$ is removed according to the distribution specified in Lemma~\ref{lemma.conditionalpaninski}, and $D_+$ is the change in $\hat{H}$ that occurs when $Z_1'$ is added back according to the true distribution $P$.

Now we compute $\bE [D_-^2|X_1^S]$ and $\bE [D_+^2| X_1^S]$. We have
\begin{align}
\bE[D_-^2|X_1^S] & = \sum_{1\leq i\leq S} \frac{X_i}{n} \left( r\left(\frac{X_i-1}{n}\right) - r\left(\frac{X_i}{n}\right) \right)^2,
\end{align}
and
\begin{align}
& \bE[D_+^2|X_1^S] \nonumber \\
 & \quad = \sum_{1\leq i\leq S} p_i  \frac{X_i}{n} \left(  r\left(\frac{X_i}{n}\right) -r\left(\frac{X_i-1}{n}\right) \right)^2 +\sum_{1\leq i\leq S} p_i\left(1-\frac{X_i}{n}\right) \left(  r\left(\frac{X_i + 1}{n} \right)-r\left(\frac{X_i}{n}\right) \right)^2 .
\end{align}

Note that we interpret $\frac{X_i}{n} \left(  r\left(\frac{X_i}{n}\right) -r\left(\frac{X_i-1}{n}\right) \right)^2$ as $0$ when $X_i = 0$. Taking expectations of $\bE [D_-^2|X_1^S]$ and $\bE [D_+^2| X_1^S]$ with respect to $X_1^S$, we have
\begin{align}
\bE [D_-^2] & = \sum_{1\leq i\leq S} \sum_{1\leq j\leq n} \frac{j}{n} \left( r\left(\frac{j-1}{n} \right) - r\left(\frac{j}{n}\right)\right)^2 \bP(\mathsf{B}(n,p_i) = j)
\end{align}
and
\begin{align}
& \bE[D_+^2] \nonumber \\
 & \quad = \sum_{1\leq i\leq S} \sum_{0\leq j\leq n} \left( \frac{j}{n} \left(r\left(\frac{j-1}{n} \right)- r\left(\frac{j}{n}\right)\right)^2  + \left(1-\frac{j}{n}\right) \left(r\left(\frac{j}{n}\right) - r\left(\frac{j+1}{n}\right)\right)^2 \right) \nonumber \\
 & \quad \quad \times p_i \bP(\mathsf{B}(n,p_i) = j).
\end{align}

After some algebra, one can show that $\bE[D_+^2] = \bE[D_-^2]$. It then follows from (\ref{eqn.entropyesnew}) that
\begin{align}
\mathsf{Var}(H(P_n)) & \leq \frac{n}{2} \cdot \bE \left( \hat{H}(Z_1,Z_2,\ldots,Z_n) - \hat{H}(Z_1',Z_2,\ldots,Z_n) \right)^2 \\
& = \frac{n}{2} \cdot \bE \left( D_- + D_+ \right)^2 \\
& \leq n \cdot \bE (D_-^2 + D_+^2) \\
& \leq 2n \bE D_-^2 \\
& = 2n \cdot \sum_{1\leq i\leq S} \bE P_n(i) \left( r(P_n(i)) - r(P_n(i)-\frac{1}{n}) \right)^2 \label{eqn.espaninskifurther}
\end{align}

The proof above is an elaborate version of that in \cite[App. B.3]{Paninski2003}. Now we proceed to obtain non-asymptotic upper bounds of (\ref{eqn.espaninskifurther}). For $x\geq 1/n$, it follows from Taylor expansion with integral form residue that
\begin{align}
(x-\frac{1}{n}) \ln (x-\frac{1}{n}) & = x\ln x + (\ln x + 1) (-\frac{1}{n}) + \int_x^{x-\frac{1}{n}} (x-\frac{1}{n}-u) \frac{1}{u} du.
\end{align}
Then, we have
\begin{align}
\left|r(P_n(i)) - r\left(P_n(i) -\frac{1}{n}\right)\right| & \leq \frac{|\ln P_n(i) + 1|}{n} + \left| \int_{P_n(i)}^{P_n(i)-\frac{1}{n}} \frac{P_n(i)-\frac{1}{n}}{u}du \right| + \frac{1}{n} \\
& \leq \frac{|\ln P_n(i) + 1|+2}{n}.
\end{align}

Hence, we have
\begin{equation}
\mathsf{Var}(H(P_n)) \leq 2n\cdot\sum_{1\leq i\leq S} \bE P_n(i) \left( \frac{|\ln P_n(i) +1|+2}{n}\right)^2.
\end{equation}
Noting that $\ln P_n(i) \leq 0$, we have
\begin{align}
\mathsf{Var}(H(P_n)) & \leq \frac{2}{n}\cdot\sum_{1\leq i\leq S} \bE P_n(i) \left( \ln P_n(i)-2 \right)^2 \\
& \leq \frac{2}{n} \sum_{1\leq i\leq S} p_i(\ln p_i - 2)^2 \\
& \leq \frac{2}{n} S \cdot \frac{1}{S} (-\ln S - 2)^2 \\
& = \frac{2(\ln S + 2)^2}{n},
\end{align}
where we have used the fact that $x(\ln x -2)^2$ is a concave function on $[0,1]$.

\subsection{Proof of Lemma~\ref{lemma.biasalphalarge}}

It is well known (see, e.g. \cite[Cor. 10.4.2]{Devore--Lorentz1993}) that if $f$ is concave in $(0,1)$, then
\begin{equation}
f(x) - B_n[f](x) \geq 0,\quad 0\leq x\leq 1.
\end{equation}

Hence we focus on deriving the other bound. For concave function $f_\alpha(x) = -x^\alpha,\alpha\in (1,2) $, Taylor's polynomial of degree $5$ at $x = x_0$ takes the form
\begin{align*}
Q_5(x) & = -\frac{\alpha(\alpha-1)}{2} x_0^{\alpha-2} (x-x_0)^2 - \frac{\alpha(\alpha-1)(\alpha-2)}{6} x_0^{\alpha-3} (x-x_0)^3 \\
& \quad -\frac{\alpha(\alpha-1)(\alpha-2)(\alpha-3)}{24} x_0^{\alpha-4}(x-x_0)^4 - \frac{\alpha(\alpha-1)(\alpha-2)(\alpha-3)(\alpha-4)}{120} x_0^{\alpha-5} (x-x_0)^5 \\
& \quad + \textrm{affine terms of }x
\end{align*}

We know that the Bernstein polynomial of any affine function on $[0,1]$ is the affine function itself, hence it suffices to consider the non-affine part of $Q_5(x)$. \cite[Prop. 4]{Braess--Sauer2004} showed the following results for Bernstein polynomials:
\begin{lemma}\label{lemma.brastaylor}
Let $0\leq x_0 \leq 1$. Then we have
\begin{align}
B_n[(x-x_0)^2](x_0) & =  \frac{x_0(1-x_0)}{n} \\
B_n[(x-x_0)^3](x_0) & = \frac{x_0(1-x_0)}{n^2}(1-2x_0) \\
B_n[(x-x_0)^4](x_0) & = 3 \frac{x_0^2(1-x_0)^2}{n^2} + \frac{x_0(1-x_0)}{n^3} [ 1-6x_0(1-x_0)] \\
B_n[(x-x_0)^5](x_0) & = \left( 10 \frac{x_0^2(1-x_0)^2}{n^3} + \frac{x_0(1-x_0)}{n^4}[1-12 x_0(1-x_0)] \right)(1-2x_0)
\end{align}
\end{lemma}

Applying Lemma~\ref{lemma.qn1lower} and Lemma~\ref{lemma.brastaylor}, taking $x_0 =x$, we have
\begin{align}
& Q_5(x) - B_n[Q_5](x)\\
 & =  \frac{\alpha(\alpha-1)}{2}x^{\alpha-2} \frac{x(1-x)}{n} + \frac{\alpha(\alpha-1)(\alpha-2)}{6}x^{\alpha-3} \frac{x(1-x)}{n^2}(1-2x) \\
& \quad +\frac{\alpha(\alpha-1)(\alpha-2)(\alpha-3)}{24} x^{\alpha-4} \left(  3 \frac{x^2(1-x)^2}{n^2} + \frac{x(1-x)}{n^3} [ 1-6x(1-x)]\right) \\
& \quad + \frac{\alpha(\alpha-1)(\alpha-2)(\alpha-3)(\alpha-4)}{120} x^{\alpha-5} \left \{ \left( 10 \frac{x^2(1-x)^2}{n^3} + \frac{x(1-x)}{n^4}[1-12 x(1-x)] \right)(1-2x) \right \}
\end{align}

After some algebra, we have
\begin{align}
& Q_5(x) - B_n[Q_5](x)\nonumber \\
& \quad =   \frac{\alpha(\alpha-1)x^{\alpha-2}(1-x)}{2n} \left( x + \frac{(2-\alpha)(3\alpha-1)x}{12n} + \frac{(2-\alpha)(5-3\alpha)}{12n} \right)  + \frac{R_1(x)}{n^3} + \frac{R_2(x)}{n^4},
\end{align}
where
\begin{align}
R_1(x) & = \frac{\alpha(\alpha-1)(\alpha-2)(\alpha-3) x^{\alpha-3} (1-x)}{24} \left( 1+2(1-x)((5-2\alpha)x + \alpha-4) \right) \\
R_2(x) & = \frac{\alpha(\alpha-1)(\alpha-2)(\alpha-3)(\alpha-4) x^{\alpha-4} (1-x)(1-2x)(1-12x(1-x))}{120}
\end{align}

Hence, we have
\begin{align}
& f_\alpha(x) - B_n[f_\alpha](x) \nonumber\\
& \geq Q_5(x) - B_n[Q_5](x) \nonumber \\
& = \frac{\alpha(\alpha-1)x^{\alpha-2}(1-x)}{2n} \left( x + \frac{(2-\alpha)(3\alpha-1)x}{12n} + \frac{(2-\alpha)(5-3\alpha)}{12n} \right)  + \frac{R_1(x)}{n^3} + \frac{R_2(x)}{n^4}.  \nonumber
\end{align}

\subsection{Proof of Lemma~\ref{lemma.alphalower}}

It is well known (see, e.g. \cite[Cor. 10.4.2]{Devore--Lorentz1993}) that if $f$ is concave in $(0,1)$, then
\begin{equation}
f(x) - B_n[f](x) \geq 0,\quad 0\leq x\leq 1.
\end{equation}

Hence we focus on deriving the other bound. For function $f_\alpha(x) = x^\alpha$, Taylor's polynomial of degree $3$ at $x = x_0$ takes the form
\begin{equation}
Q_3(x) = \frac{\alpha(\alpha-1)}{2} x_0^{\alpha-2} (x-x_0)^2 + \frac{\alpha(\alpha-1)(\alpha-2)}{6} x_0^{\alpha-3} (x-x_0)^3 + \textrm{ affine terms of }x.
\end{equation}

Applying Lemma~\ref{lemma.qn1lower} and Lemma~\ref{lemma.brastaylor}, taking $x_0 =x$, we have
\begin{align}
Q_3(x) - B_n[Q_3](x) & = - \frac{\alpha(\alpha-1)}{2}x^{\alpha-2} \frac{x(1-x)}{n} - \frac{\alpha(\alpha-1)(\alpha-2)}{6}x^{\alpha-3} \frac{x(1-x)}{n^2}(1-2x) \\
& = \frac{\alpha(1-\alpha)}{2n} x^{\alpha-2}(1-x) \left( x - \frac{2-\alpha}{3n} (1-2x) \right) \\
& \geq \frac{\alpha(1-\alpha)}{2n}x^{\alpha-2} (1-x) \left( x - \frac{2-\alpha}{3n} \right).
\end{align}

Hence, we have
\begin{equation}
f_\alpha(x) - B_n[f_\alpha](x) \geq Q_3(x) - B_n[Q_3](x) \geq \frac{\alpha(1-\alpha)}{2n}x^{\alpha-2} (1-x) \left( x - \frac{2-\alpha}{3n} \right).
\end{equation}

\subsection{Proof of Lemma \ref{lem_variance_p_small}}
Since $nX$ is an integer, we have $(nX)^2\ge (nX)^{2\alpha},0<\alpha<1$. Hence,
\begin{align}
  \mathsf{Var}(X^\alpha) \le \bE X^{2\alpha} = \frac{\bE (nX)^{2\alpha}}{n^{2\alpha}} \le  \frac{\bE (nX)^{2}}{n^{2\alpha}} = \frac{(np)^2+np(1-p)}{n^{2\alpha}}
  \le \frac{2}{n^{2\alpha}}\wedge \frac{2p}{n^{2\alpha-1}},
\end{align}
which completes the proof.

\subsection{Proof of Lemma \ref{lem_variance_p_big}}
Denoting $f(p)=p^\alpha,0<\alpha<1$, we have
\begin{align}
\mathsf{Var}(f(X)) & = \bE f^2(X) - (\bE f(X))^2 \\
& = \bE f^2(X) - f^2(p) + f^2(p) - (\bE f(X))^2 \\
& \leq | \bE f^2(X) - f^2(p)|+ | f^2(p) - (\bE f(X)-f(p) + f(p))^2 |\\
& = | \bE f^2(X) - f^2(p)|+ |(\bE f(X)-f(p))^2 + 2f(p) (\bE f(X)-f(p))| \\
& \leq | \bE f^2(X) - f^2(p)| + |\bE f(X)-f(p)|^2 + 2f(p)|\bE f(X)-f(p)|. \label{eqn.varianceestimatelarge}
\end{align}

Hence, it suffices to obtain bounds on $| \bE f^2(X) - f^2(p)|$ and $|\bE f(X) - f(p)|$. Denoting $r(x) = f^2(x)$, it follows from Taylor's formula and the integral representation of the remainder term that
\begin{equation}
r(X) = f^2(p) + r'(p)(X-p) + R_1(X;p),
\end{equation}
\begin{equation}
R_1(X;p)=\int_p^X (X-u)r''(u)du = \frac{1}{2}r''(\eta_X)(X-p)^2, \quad \eta_X \in [\min\{X,p\},\max\{X,p\}].
\end{equation}

Similarly, we have
\begin{equation}
f(X) = f(p) + f'(p)(X-p) + R_2(X;p),
\end{equation}
\begin{equation}
\quad R_2(X;p) = \int_p^X (X-u)f''(u)du = \frac{1}{2} f''(\nu_X)(X-p)^2,\quad \nu_X\in [\min\{X,p\},\max\{X,p\}].
\end{equation}

Taking expectation on both sides with respect to $X$, where $nX \sim \mathsf{B}(n,p), p\geq \Delta$, we have
\begin{equation}\label{eqn.u2biaslarge}
|\bE f^2(X) - f^2(p)| = |\bE R_1(X;p) |.
\end{equation}
Similarly, we have
\begin{equation}
|\bE f(X) - f(p)| =  | \bE R_2(X;p)|.
\end{equation}

It is straightforward to show that
\begin{align}
  |r''(x)|&=2\alpha(2\alpha-1)x^{2\alpha-2} \le 2x^{2\alpha-2},\\
  |f''(x)|&=\alpha(1-\alpha)x^{\alpha-2} \le \frac{1}{4}x^{\alpha-2}.
\end{align}

Now we are in the position to bound $|\bE R_1(X;p)|$ and $|\bE R_2(X;p)|$. For $|\bE R_1(X;p)|$, we have
  \begin{align}
|\bE R_1(X;p)| & \leq \bE |R_1(X;p)| \\
& = \bE [|R_1(X;p)\mathbbm{1}(X\geq p/2)|] + \bE[R_1(X;p)\mathbbm{1}(X<p/2)] \\
& \leq \bE \left[ 2(p/2)^{2\alpha-2} (X-p)^2\right] + \bE[R_1(X;p)\mathbbm{1}(X<p/2)] \\
& \leq 8\frac{p^{2\alpha-1}}{n} + \sup_{x\leq p/2}|R_1(x;p)|\bP(nX<np/2) \\
& \leq 8\frac{p^{2\alpha-1}}{n} + \sup_{x\leq p/2}|R_1(x;p)| e^{-np/8},
\end{align}
where in the last step we have used Lemma \ref{lem_chernoff}. Regarding $\sup_{x\leq p/2}|R_1(x;p)|$, for any $x\leq p/2$, we have
\begin{align}
R_1(x;p) = \int_x^p (u-x)r''(u)du \leq \int_x^p (u-x) 2u^{2\alpha-2}du
 \leq 2 \int_x^p u^{2\alpha-1}du
 \leq 2 \int_0^p u^{2\alpha-1}du
 = \frac{p^{2\alpha}}{\alpha}.
\end{align}

Hence, we have
\begin{equation}
|\bE R_1(X;p)| \leq \frac{8p^{2\alpha-1}}{n} + \frac{1}{\alpha}p^{2\alpha}e^{-np/8}.
\end{equation}

Analogously, we obtain the following bound for $|\bE R_2(X;p)|$:
\begin{equation}
|\bE R_2(X;p)|\leq \frac{p^{\alpha-1}}{n} + \frac{1}{4\alpha}p^\alpha e^{-np/8}.
\end{equation}

Plugging these estimates of $|\bE R_1(X;p)|$ and $|\bE R_2(X;p)|$ into (\ref{eqn.varianceestimatelarge}), we have for $p\geq 1/n$,
\begin{align}
\mathsf{Var}(X^\alpha)  &\leq \frac{8p^{2\alpha-1}}{n} + \frac{1}{\alpha}p^{2\alpha}e^{-np/8} +  \left(\frac{p^{\alpha-1}}{n} + \frac{1}{4\alpha} p^\alpha e^{-np/8} \right)^2 +2f(p)\left(\frac{p^{\alpha-1}}{n} + \frac{1}{4\alpha}p^\alpha e^{-np/8} \right)\\
&\le \frac{8p^{2\alpha-1}}{n} + \frac{1}{\alpha}p^{2\alpha}e^{-np/8} + \frac{2p^{2(\alpha-1)}}{n^2} + \frac{1}{8\alpha^2}p^{2\alpha} e^{-np/4}+2p^\alpha\left(\frac{p^{\alpha-1}}{n} + \frac{1}{4\alpha}p^\alpha e^{-np/8} \right)\\
&\le \frac{10p^{2\alpha-1}}{n} + \frac{3}{2\alpha}p^{2\alpha}e^{-np/8} + \frac{2}{n^{2\alpha}} + \frac{1}{8\alpha^2}p^{2\alpha} e^{-np/4}\\
&\le \frac{10p^{2\alpha-1}}{n} + \frac{3}{2\alpha}\left(\frac{16\alpha}{en}\right)^{2\alpha} + \frac{2}{n^{2\alpha}} + \frac{1}{8\alpha^2}\left(\frac{8\alpha}{en}\right)^{2\alpha}.
\end{align}
where we have used the following inequality in the last step: for $x\in(0,1)$ and any $c>0$,
\begin{align}
  x^{2\alpha}e^{-cnx} \le \left(\frac{2\alpha}{cen}\right)^{2\alpha}.
\end{align}

Note that if $0<\alpha<1/2$, we can upper bound $\frac{10p^{2\alpha-1}}{n}$ by $\frac{10}{n^{2\alpha}}$, since we have constrained $p>\frac{1}{n}$.

\subsection{Proof of Corollary~\ref{cor.vargeneralf}}

In our case, apparently $F(P_n)$ is a function of $n$ independent random variables $\{Z_i\}_{1\leq i\leq n}$ taking values in $\mathcal{Z} = \{1,2,\ldots,S\}$. Changing one location of the sample would make some symbol with count $j$ to have count $j+1$, and another symbol with count $i$ to have count $i-1$. Then the total change in the functional estimator is
\begin{equation}
f\left(\frac{j+1}{n}\right) - f \left( \frac{j}{n}\right) - f\left(\frac{i}{n}\right) + f\left(\frac{i-1}{n}\right).
\end{equation}

If $f$ is monotone, then the total change would be upper bounded by $\max_{0\leq j<n} |f((j+1)/n) - f(j/n)|$. If $f$ is not monotone, the total change can be upper bounded by $2 \cdot\max_{0\leq j<n} |f((j+1)/n) - f(j/n)|$. Applying Lemma~\ref{lemma.es}, we have the desired bounds.

\bibliographystyle{IEEEtran}
\bibliography{di}

\end{document}


TITLE: Can we find the limit of a function if we know the limit of its reciprocal?
QUESTION [1 upvotes]: In a question I am given that the limit of f(x) -> e as x tends to infinity
Can I assume that the limit of 1/f(x) -> 1/e as x tends to infinity?

REPLY [1 votes]: For sure! If a non vanishing function has a non zero limit $l$ at a point, the limit of $\frac{1}{f}$ at that point is equal to $\frac{1}{l}$.