1

Minimax Estimation of the L1 Distance
Jiantao Jiao, Student Member, IEEE, Yanjun Han, Student Member, IEEE, and Tsachy Weissman, Fellow, IEEE.

arXiv:1705.00807v5 [math.ST] 10 Sep 2017

Abstract
We consider the problem of estimating the L1 distance between two discrete probability measures P and Q from empirical data
in a nonasymptotic and large alphabet setting. When Q is known and one obtains n samples from P , we show that for every Q,
the minimax rate-optimal estimator with n samples achieves performance comparable to that of the maximum likelihood estimator
(MLE) with n ln n samples. When both P and Q are unknown, we construct minimax rate-optimal estimators whose worst case
performance is essentially that of the known Q case with Q being uniform, implying that Q being uniform is essentially the most
difficult case. The effective sample size enlargement phenomenon, identified in Jiao et al. (2015), holds both in the known Q case
for every Q and the Q unknown case. However, the construction of optimal estimators for L1 (P, Q) requires new techniques and
insights beyond the Approximation methodology of functional estimation in Jiao et al. (2015).
Index Terms
Divergence estimation, total variation distance, multivariate approximation theory, functional estimation, optimal classification
error, high dimensional statistics, Hellinger distance

I. I NTRODUCTION
A. Problem formulation
Statistical functionals are usually used to quantify the fundamental limits of data processing tasks such as data compression
(e.g. Shannon entropy [1]), data transmission (e.g. mutual information [1]), estimation and testing (e.g. Kullback–Leibler
divergence [2, Thm. 11.8.3], L1 distance [3, Chap. 13]), etc. They measure the difficulties of the corresponding data processing
tasks and shed light on how much improvement one may expect beyond the current state-of-the-art approaches. In this sense,
it is of great value to obtain accurate estimates of these functionals in various problems.
In this paper, we consider estimating the L1 distance between two discrete distributions P = (p1 , p2 , . . . , pS ), Q =
(q1 , q2 , . . . , qS ), which is defined as:
L1 (P, Q) ,

S
X
i=1

|pi − qi |.

(1)

Throughout we use the squared error loss, i.e., the risk function for an estimator L̂ is defined as
R(P, Q; L̂) , E|L̂(X n , Y n ) − L1 (P, Q)|2 ,

(2)

i.i.d.

where (Xi , Yi ) ∼ P × Q. The maximum risk of an estimator L̂, and the minimax risk in estimating L1 (P, Q) are defined as
Rmaximum (P, Q; L̂) ,

sup

R(P, Q; L̂),

(3)

P ∈P,Q∈Q

Rminimax (P, Q) , inf

sup

R(P, Q; L̂),

(4)

L̂ P ∈P,Q∈Q

respectively, where P, Q are given collections (uncertainty sets) of probability measures P and Q, respectively, and the infimum
is taken over all possible estimators L̂.
The L1 distance is closely related to the Bayes error, i.e., the fundamental limit, in classification problems. Specifically, for
a two-class classification problem, if the prior probabilities for each class are equal, then the minimum probability of error
achieved using the optimal classifier is given by
1 1
− L1 (PX|Y =1 , PX|Y =0 ),
(5)
2 4
where Y ∈ {0, 1} indicates the class, and PX|Y are the class-conditional distributions. Hence, the problem of estimating
L∗ in this classification problem is reduced to estimating the L1 distance between the two class-conditional distributions
PX|Y =1 , PX|Y =0 from the empirical data. In the statistical learning theory literature, most work on Bayes classification error
estimation deals with the case that PX|Y =1 and PX|Y =0 are continuous distributions, and it turns out that even in an asymptotic
setting it is very difficult to estimate this quantity in this general continuous case. Indeed, we know from [4, Section 8.5] the
L∗ =

Jiantao Jiao, Yanjun Han, and Tsachy Weissman are with the Department of Electrical Engineering, Stanford University, CA, USA. Email: {jiantao,yjhan,
tsachy}@stanford.edu
The materials in this paper was presented in part at the 2016 IEEE International Symposium on Information Theory, Barcelona, Spain.

2

negative result that for every sample size n, any estimate of the Bayes error L̂n , and any ǫ > 0, there exist some class-conditional
distributions such that E|L̂n − L∗ | ≥ 14 − ǫ.
This negative result shows that one needs to look at special classes of the class-conditional distributions in order to obtain
meaningful and consistent estimates. In the discrete setting, the seminal work of Valiant and Valiant [5] deserves
pspecial mention.
They constructed an estimator for L1 (P, Q) and showed that when S/ ln S . n . S, it achieves L1 error S/(n ln n), and
it takes at least n ≫ lnSS samples to achieve consistent estimation of L1 (P, Q).
q Valiant and Valiant [6] constructed another

S
S
estimator of L1 (P, Q) using linear programming which achieves the L1 error n ln
n when n ≍ ln S . We argue in this paper
that the simplest estimator
p for L1 (P, Q), namely plugging in the empirical distribution Pn , Qn and obtaining L1 (Pn , Qn )
achieves L1 error rate S/n for n & S. In this sense, the optimal estimator seems to enlarge the sample size n to n ln n in
the error rate expression. This phenomenon was termed the effective sample size enlargement in [7].

B. Approximation: the general recipe
We emphasize that the observed effective sample size enlargement here is another manifestation of the recently discovered
phenomenon in functional estimation of high dimensional objects. There has been a recent wave of study on functional
estimation of high dimensional parameters [6]–[9], and it was
that for a wide class of functional
PS shown in Jiao et al.
P[7]
S
estimation problems (including Shannon entropy H(P ) = i=1 −pi ln pi , Fα , i=1 pα
i , and mutual information), there
exists a general methodology, termed Approximation, that can be applied to design minimax rate-optimal estimators whose
performance with n samples is essentially that of the MLE (maximum likelihood estimator, or the plug-in approach) with
n ln n samples.
The general methodology of Approximation in [7] is as follows. Consider estimating G(θ) of a parameter θ ∈ Θ ⊂ Rp for an
experiment {Pθ : θ ∈ Θ}, with a consistent estimator θ̂n for θ, where n is the number of observations. Suppose the functional
G(θ) is analytic1 everywhere except at θ ∈ Θ0 . A natural estimator for G(θ) is G(θ̂n ), and we know from classical asymptotics
[10, Lemma 8.14] that given the benign LAN (Local Asymptotic Normality) condition [10], G(θ̂n ) is asymptotically efficient
for G(θ) for θ ∈
/ Θ0 if θ̂n is asymptotically efficient for θ. In the estimation of functionals of discrete distributions, Θ is
the S-dimensional probability simplex, and a natural candidate for θ̂n is the empirical distribution, which is unbiased for any
θ ∈ Θ.
We propose to conduct the following two-step procedure in estimating G(θ).
1) Classify the Regime: Compute θ̂n , and declare that we are in the “non-smooth” regime if θ̂n is “close” enough to Θ0 .
Otherwise declare we are in the “smooth” regime;
2) Estimate:
• If θ̂n falls in the “smooth” regime, use an estimator “similar” to G(θ̂n ) to estimate G(θ);
• If θ̂n falls in the “non-smooth” regime, replace the functional G(θ) in the “non-smooth” regime by an approximation
Gappr (θ) (another functional) which can be estimated without bias, then apply an unbiased estimator for the functional
Gappr (θ).
Approaches of this nature appeared before [7] in Lepski, Nemirovski, and Spokoiny [11], Cai and Low [12], Vinck et
al. [13], Valiant and Valiant [5]. It was developed independently for entropy estimation by Wu and Yang [8], and the ideas
proved to be very fruitful in Acharya et al. [9], Wu and Yang [14], Orlitsky, Suresh, and Wu [15], Wu and Yang [16]. However,
we emphasize that in all the examples
Pp above exceptR for the L1 distance estimator in Valiant and Valiant [5], the functionals
considered all take the form G( i=1 f (θi )) or G( f (p(x))dx), where p(x) is a univariate density or function, and each
α
θi ∈ R. In particular, the functions f (·) considered are everywhere analytic except at zero, e.g., xα , |x|
PS for α > 0 and
x ln x. Most of these features are violated in the L1 distance estimation problem. If we write L1 (P, Q) = i=1 f (pi , qi ) with
f (x, y) = |x − y| ∈ C([0, 1]2 ), then we have:
1) a bivariate function f (x, y) in the sum;
2) a function f (x, y) which is analytic except on a segment x = y ∈ [0, 1].
As discussed in Jiao et al. [7], approximation of multivariate functions is much more involved than that of univariate functions,
and the fact that the “non-smooth” regime is around a line segment here makes the application of the Approximation approach
quite difficult: what shape should we use to specify the “non-smooth” regime? We provide a comprehensive answer to this
problem in this paper, thereby substantially generalizing the applicability of the Approximation methodology and demonstrate
the intricacy of functional estimation problems in high dimensions. Our recent work [17] presents the most up-to-date version of
the general Approximation methodology, which is applied to construct minimax rate-optimal estimators for the KL divergence
(also see Bu et al. [18]), χ2 -divergence, and the squared Hellinger distance. The effective sample size enlargement phenomenon
holds in all these cases as well.
We emphasize that the complications triggered by the bivariate function f (x, y) = |x − y| make the L1 distance estimation
problem highly challenging. Indeed, prior to our work, the only known estimators that require sublinear samples were in [5],
1A

function f is analytic at a point x0 if and only if its Taylor series about x0 converges to f in some neighborhood of x0 .

3

q
S
S
[6], which achieved L1 error n ln
n in the regime of ln S . n . S but not the regime n & S, and the lower bound was
S
proved for the regime n ≍ ln S , i.e., the constant error regime. The complete characterization of the minimax rates and the
estimator that achieves the minimax rates were unknown prior to this work.
Our main contributions in this paper are the following:
1) We apply the Approximation methodology to construct minimax rate-optimal estimators with linear complexity for
L1 (P, Q) when Q is known, and show that for any fixed Q, our estimator performs with n samples at least as well
as the plug-in estimator with
samples. Precisely, the performance of the plug-in estimator for any fixed Q is
PS n ln np
dictated by the functional i=1 qi ∧ qni , while that of the minimax rate-optimal estimator is dictated by the functional
p qi
PS
i=1 qi ∧
n ln n . Furthermore, we show that any plug-in approach does not work. As we argue in Lemma 20, for
estimating L1 (P, Q) with known Q, for any distribution estimate P̂ constructed from the samples from P , the estimator
L1 (P̂ , Q) does not achieve the minimax rates in the worst case if P̂ does not depend on Q. Concretely, the performance
of any plug-in rule P̂ behaves essentially as the MLE in the worst case.
2) We generalize the Approximation methodology in [7] to construct a minimax rate-optimal estimator for L1 (P, Q) when
both P and Q are unknown. We illustrate the novelty of our scheme via the following results:
a) The performance of our estimator with n samples is essentially that of the MLE with n ln n samples.
b) Any algorithm that only conducts approximation around the origin does not achieve the minimax rates. Indeed,
as we argue in Lemma 17, for any algorithm that employs the MLE when p̂ & lnnn , q̂ & lnnn cannot achieve the
minimax rates when n ≫ S. The reason why the estimator of Valiant and Valiant [5] cannot achieve the minimax
rates when n ≫ S is that [5] did not conduct approximation when p and q are large. One of our key contributions
is to figure out how to conduct approximation when p̂ & lnnn , q̂ & lnnn and achieve the minimax rates when n ≫ S.
c) Best polynomial approximation is not sufficient for achieving minimax rate-optimality in this problem. As we
argue in Lemma 18, for approximation in the lower left corner, any one-dimensional polynomial that achieves the
best approximation error rate cannot be used in constructing the optimal estimator, and it is necessary to use a
multivariate polynomial with certain pointwise error guarantees. One of our key contributions is to construct a
proper multivariate polynomial with desired pointwise approximation error.
d) Approximation over the union of the “nonsmooth” regime does not work. As we show in Lemma 19, there does not
exist a single multivariate polynomial that achieves the desired approximation error over the whole “nonsmooth”
regime. Instead, in our approach, we construct polynomial approximations of the function f (p, q) = |p − q| over
a random regime that is determined by empirical data. To our knowledge, it is the first time that a random
approximation regime approach appears in the functional estimation literature.
e) Our estimator is agnostic to the potentially unknown support size S, but behaves as well as the minimax rate-optimal
estimator that knows the support size S.
The rest of the paper is organized as follows. In Section II and III, we present a thorough performance analysis of the
MLE and explicitly construct the minimax rate-optimal estimators, where Section II covers the known Q case and Section
III generalizes to the case of unknown Q. Discussions in Section IV highlight the significance and novelty of our approaches
by reviewing several other approaches which are shown to be suboptimal. The auxiliary lemmas used throughout this paper
are collected in Appendix A. Proofs of all the lemmas in the main text can be found in Appendix B, where proofs of all the
auxiliary lemmas are collected in Appendix C.
Notation: for non-negative sequences aγ , bγ , we use the notation aγ . bγ to denote that there exists a universal constant
a
C such that supγ bγγ ≤ C, and aγ & bγ is equivalent to bγ . aγ . Notation aγ ≍ bγ is equivalent to aγ . bγ and bγ . aγ .
a
Notation aγ ≫ bγ means that lim inf γ bγγ = ∞, and aγ ≪ bγ is equivalent to bγ ≫ aγ . We write a ∧ b = min{a, b} and
a ∨ b = max{a, b}. Moreover, polydn denotes the set of all d-variate polynomials of degree of each variable no more than n,
and En [f ; I] denotes the distance of the function f to the space polydn in the uniform norm k · k∞,I on I ⊂ Rd . The space
poly1n is also abbreviated as polyn . All logarithms are in the natural base. The notation x ≥ Y, where x is a real number and
Y is a set of real numbers, is equivalent to x ≥ y for all y ∈ Y.
Throughout this paper, we utilize the Poisson sampling model instead of the binomial model, whose minimax risks can be
shown to be on the same scale, as in [7, Lemma 16].
II. D IVERGENCE E STIMATION WITH K NOWN Q
First we consider the case where Q = (q1 , · · · , qS ) is known while P is an unknown distribution with support S =
{1, 2, · · · , S}. In other words, P = MS and Q = {Q}. We analyze the performance of the MLE in this case, and construct
the approximation-based minimax rate-optimal estimator.
We utilize the Poisson sampling model, in which we observe a Poisson random vector
X = [X1 , X2 , . . . , XS ],
where the coordinates of X are mutually independent, and Xi ∼ Poi(npi ). We define p̂i =

(6)
Xi
n

as the empirical probabilities.

4

A. Performance of the MLE
PS
The MLE serves as a natural estimator for the L1 distance which can be expressed as L1 (Pn , Q) =
i=1 |p̂i − qi |,
where Pn = X/n = (p̂1 , p̂2 , · · · , p̂S ) is the empirical distribution. Since we are using the Poisson sampling mode, we have
np̂i ∼ Poi(npi ).
The following lemma provides sharp estimates of E|p̂i − pi |, which can be viewed as an analog of the binomial case studied
in [19].
Lemma 1. Suppose nq̂ ∼ Poi(nq). Then,
E|q̂ − q| ∈
Hence,
1
√
2

(

{2qe−nq }
0≤q≤
p q pq
[ 2n , n ] q ≥ n1

1
n

.

(7)

r 
r 


q
q
q∧
≤ E|q̂ − q| ≤ 2 q ∧
.
n
n

(8)

Lemma 2. Suppose nq̂ ∼ Poi(nq). Then, for any p ≥ 0,
r r 

p
q
|E|q̂ − p| − |q − p|| ≤ 2 · min p, q,
.
,
n
n

(9)

Further,
1
sup |E|q̂ − p| − |q − p|| ≥ √
2
q≥0

r 

p
p∧
.
n

(10)

The next lemma upper bounds the variance of |q̂ − p|, nq̂ ∼ Poi(nq).
Lemma 3. Suppose nq̂ ∼ Poi(nq). Then, for any p ≥ 0,

q
.
n
We obtain the upper and lower bounds for the mean squared error of L1 (Pn , Q).
Var(|q̂ − p|) ≤

(11)

Theorem 1. The maximum likelihood estimator L1 (Pn , Q) satisfies
sup EP |L1 (Pn , Q) − L1 (P, Q)|2 ≤ 4

P ∈MS

We can also lower bound the worst case mean squared error as
1
sup EP |L1 (Pn , Q) − L1 (P, Q)|2 ≥
2
P ∈MS
Proof. We have
2

EP |L1 (Pn , Q) − L1 (P, Q)| =
Hence,
S
X
i=1

where we applied Lemma 2.

S
X
i=1

S
X
i=1

qi
n

qi ∧

r

qi ∧

S
X
i=1

E|p̂i − qi | − |pi − qi |

E|p̂i − qi | − |pi − qi | ≤

S
X

i=1
S
X

!2

r

!2

qi
n

+

!2

(12)

.

(13)

+ Var(L1 (Pn , Q)).

E||p̂i − qi | − |pi − qi ||

r 

qi
2 qi ∧
≤
,
n
i=1

1
.
n

(14)

(15)

(16)

5

To analyze the variance, due to the mutual independence of {p̂i , 1 ≤ i ≤ S}, we have
Var(L1 (Pn , Q)) =
≤
=

S
X

i=1
S
X
i=1

Var(|p̂i − qi |)

(17)

pi
n

(18)

1
,
n

(19)

where we used Lemma 3 in the second step.
The proof of the upper bound is complete. Regarding the lower bound, setting P = Q, we have
S
X
i=1

E|p̂i − qi | − |pi − qi | ≥
=

S
X

i=1
S
X
i=1

E|p̂i − pi |

E|p̂i − pi |
S

1 X
qi ∧
≥ √
2 i=1
The following corollary is straightforward since supQ∈MS
Corollary 1. If n & S, we have
sup
P,Q∈MS

PS

i=1 qi ∧

(20)

p qi
n

≍

r

q

EP |L1 (Pn , Q) − L1 (P, Q)|2 ≍

(21)
qi
.
n

S
n

S
.
n

(22)

when n & S.

(23)

Hence, it is necessary and sufficient for the MLE to have n ≫ S samples to be consistent in terms of the worst case mean
squared error.
B. Construction of the optimal estimator
We apply our general recipe to construct the minimax rate-optimal estimator. For simplicity of analysis, we conduct the
classical “splitting” operation [20] on the Poisson random vector X, and obtain two independent identically distributed random
vectors Xj = [X1,j , X2,j , . . . , XS,j ]T , j ∈ {1, 2}, such that each component Xi,j in Xj has distribution Poi(npi /2), and all
i
coordinates in Xj are independent. For each coordinate i, the splitting process generates a random sequence {Tik }X
k=1 such
PXi
Xi
that {Tik }k=1 |X ∼ multinomial(Xi ; (1/2, 1/2)), and assign Xi,j = k=1 1(Tik = j) for j ∈ {1, 2}. All the random variables
i
{{Tik }X
k=1 : 1 ≤ i ≤ S} are conditionally independent given our observation X. The “splitted” empirical probabilities are
defined as p̂i,j = Xi,j /(n/2). To simplify notation, we redefine n/2 as n to ensure that np̂i,j ∼ Poi(npi ), j = 1, 2. We
emphasize that the sampling splitting approach is not needed for the actual estimator construction.
We construct two set functions with variable q as input defined as:

[0, 2c1nln n ],
q ≤ c1 nln n
q
q
U (q; c1 ) =
(24)
[q − c1 q ln n , q + c1 q ln n ], c1 ln n < q ≤ 1.
n
n
n

[0, (c1 +cn3 ) ln n ],
q ≤ c1 nln n
q
q
(25)
U1 (q) =
[q − c3 q ln n , q + c3 q ln n ], c1 ln n < q ≤ 1.
n
n
n
Here c1 > 0, c1 > c3 > 0 are universal constants that will be determined later. The set U (q; c1 ) is constructed to satisfy the
following property:
Lemma 4. Suppose nq̂ ∼ Poi(nq). Then,
P(q̂ ∈
/ U (q; c1 )) ≤
where the set function U (q; c1 ) is defined in (24).

2
nc1 /3

,

(26)

6

It is clear that for any q ∈ [0, 1], U1 (q) ⊂ U (q; c1 ). The constants c1 > 0, c1 > c3 > 0 will be chosen later to make sure
that the following three “good” events have overwhelming probability:
E1 =
E2 =
E3 =

S
\

i=1
S
\

i=1
S
\

i=1

{p̂i,1 > U1 (qi ) ⇒ pi ≥ qi }

(27)

{p̂i,1 < U1 (qi ) ⇒ pi ≤ qi }

(28)

{p̂i,1 ∈ U1 (qi ) ⇒ pi ∈ U (qi ; c1 )} .

(29)

Here A ⇒ B represents the logical implication operation that is equivalent to Ac ∪B. The intuitions behind the constructions
of these “good” events are as follows. Since we use the first half of the samples p̂i,1 to classify regime, and would later use
three different estimators depending on whether p̂i,1 lies to the left, to the right, or inside U1 (qi ), it is desirable that we can
infer the relationship between pi and qi based on the location of p̂i,1 . The reason why these events can be controlled to have
high probabilities is that we have specifically designed U1 (q) to make it a strict subset of the set U (q; c1 ), and the sets U (q; c1 )
are designed to satisfy Lemma 4, which ensures that the size of U (q; c1 ) is essentially the length of the confidence interval
when the empirical probability q̂ is observed.
We have the following lemma controlling the probability of these probabilities.
Lemma 5. Denote the overall “good” event E = E1 ∩ E2 ∩ E3 , where E1 , E2 , E3 are defined in (27),(28),(29). Then,
P(E c ) ≤
where
β = min



3S
,
nβ


√
√
c23 (c1 − c3 )2 ( c1 − c3 )2
.
,
,
3c1
4c1
3

(30)

(31)

Now we construct the estimator. In the “smooth” regime, i.e., p̂ ∈
/ U1 (q), we simply employ the plug-in approach to estimate
f (p, q). In the “non-smooth” regime, i.e., p̂ ∈ U1 (q), we need to approximate f (p, q) by another functional which can be
estimated without bias. We consider the best polynomial approximation of f (x, q) on U (q; c1 ) ⊃ U1 (q), which is defined as
PK (x; q) = argmin

max

P ∈polyK z∈U(q;c1 )

|f (z, q) − P (z)|

(32)

where polyK denotes the set of polynomials with degree no more than K. Once we obtain PK (x; q), we can use an unbiased
estimate P̃K (p̂; q) such that EP̃K (p̂; q) = PK (p; q) for np̂ ∼ Poi(np). As a result, the bias of the estimator P̃K (p̂; q) in the
“non-smooth” regime is exactly the approximation error of PK (x; q) in approximating f (x, q) = |x − q| on U (q; c1 ), which
can be significantly smaller than the MLE. The following lemma gives the bias and variance bound of P̃K (p̂; q).
Lemma 6. For np̂ ∼ Poi(np) with p ∈ U (q; c1 ), we have
r
1 q ln n
|EP̃K (p̂; q) − |p − q|| . q ∧
K
n
B K ln n
Var(P̃K (p̂; q)) .
(p + q)
n

(33)
(34)

for some universal constant B > 0, where P̃K (p̂; q) is the unique unbiased estimate of PK (x; q) defined in (32), U (q; c1 ) is
defined in (24) and K = c2 ln n, c2 < c1 .
p
p
Hence, the bias is of the order q ∧ q/(n ln n), a logarithmic improvement compared to the result q ∧ nq in Lemma 2.
In summary, we have the following construction.
Estimator Construction 1. We use the first half samples to classify regimes and the second half samples for estimation.
Denote
L̃1 =

S
X
i=1

and define

[(p̂i,2 − qi )1(p̂i,1 > U1 (qi )) + (qi − p̂i,2 )1(p̂i,1 < U1 (qi )) + P̃K (p̂i,2 ; qi )1(p̂i,1 ∈ U1 (qi ))]



L̂(1) = 0 ∨ L̃1 ∧ 2 ,

(35)

(36)

7

where U (qi ; c1 ) and U1 (qi ) are given by (24), (25), K = c2 ln n, and c1 , c2 > 0, c3 > 0 are properly chosen universal
constants.
The performance of this estimator is presented in the following theorem.
Theorem 2. The performance of L̂(1) satisfies
sup EP |L̂

P ∈MS

(1)

2

− L1 (P, Q)| .

S
X
i=1

qi ∧

r

qi
n ln n

!2

+

ln n
S
+ β,
1−ǫ
n
n

(37)

where ǫ > 0 is a constant that can be made as small as possible, and β > 0 is a constant that can be made as large as
possible.
Proof. Recall the “good” events E1 , E2 , E3 defined in (27),(28),(29) and define E = E1 ∩ E2 ∩ E3 . We have
h
i
h
i
E(L̂(1) − L1 (P, Q))2 = E (L̂(1) − L1 (P, Q))2 1(E) + E (L̂(1) − L1 (P, Q))2 1(E c )
i
h
≤ E (L̃1 − L1 (P, Q))2 1(E) + 4P(E c )
h
i 12S
≤ E (L̃1 − L1 (P, Q))2 1(E) + β ,
n
where we have applied Lemma 5.
Define the random variables
X
E1 =
(p̂i,2 − qi ) − |pi − qi |

(38)
(39)
(40)

(41)

i∈I1

E2 =

E3 =

X

i∈I2

X

i∈I3

(qi − p̂i,2 ) − |pi − qi |

(42)

P̃K (p̂i,2 ; qi ) − |pi − qi |,

(43)

where the random index sets I1 , I2 , I3 are defined as

I1 = {i : p̂i,1 > U1 (qi ) ⇒ pi ≥ qi }
I2 = {i : p̂i,1 < U1 (qi ) ⇒ pi ≤ qi }

(44)
(45)

I3 = {i : p̂i,1 ∈ U1 (qi ) ⇒ pi ∈ U (qi ; c1 )}.

(46)

The indices I1 , I2 , I3 are independent of the random variables {p̂i,2 : 1 ≤ i ≤ S}. Since

(L̃1 − L1 (P, Q))1(E) = E1 1(E) + E2 1(E) + E3 1(E),

(47)

it follows from Cauchy’s inequality that
 12S
E(L̂(1) − L1 (P, Q))2 ≤ 3 EE12 + EE22 + EE32 + β ,
n

(48)

where β is defined in (31).
It follows from the law of total variance that

EE12 = E Var(E1 |I1 ) + (E[E1 |I1 ])2
= EVar(E1 |I1 )
≤

S
X
pi
i=1



n

1
,
n
where we have used the fact that E[E1 |I1 ] = 0 with probability one and Lemma 3. Similarly we have EE22 ≤ n−1 .
=

(49)
(50)
(51)
(52)

8

Regarding EE32 , it follows from Lemma 6 and the mutual independence of {p̂i,2 : 1 ≤ i ≤ S} that
!2
r
S
S
X
X
B K ln n
qi
2
EE3 .
qi ∧
(pi + qi ) +
n
n ln n
i=1
i=1
!
2
r
S
X
qi
ln n
qi ∧
≤
+ 1−ǫ ,
n ln n
n
i=1

(53)

(54)

where ǫ = c2 ln B.
Hence,

E(L̂(1) − L1 (P, Q))2 .
where β is defined in (31) and ǫ = c2 ln B.

S
X
i=1

qi ∧

r

qi
n ln n

!2

The following corollary is immediate.
P

√
S √
qi ∧ qi n ln n , we have
Corollary 2. Suppose ln S . ln n . ln
i=1
sup EP |L̂

(1)

P ∈MS

In particular, if ln n . ln S, we have
sup
P,Q∈MS

2

− L1 (P, Q)| .

S
X
i=1

qi ∧

EP |L̂(1) − L1 (P, Q)|2 .

+

r

ln n
S
+ β,
n1−ǫ
n

(55)

!2

(56)

qi
n ln n

.

S
.
n ln n

(57)

n
. When ln n .
Proof. For the first part, when ln n & ln S, one may choose c1 , c3 large enough to ensure that nSβ . nln1−ǫ

P


2
√
p
P
S √
S
qi
ln n
qi ∧ qi n ln n , one may choose c2 small enough to ensure that n1−ǫ .
ln
.
i=1
i=1 qi ∧
n ln n
The second part is proved upon noticing that
r
S
S r
X
X
qi
qi
qi ∧
≤
(58)
n
ln
n
n
ln
n
i=1
i=1
r
S
≤
.
(59)
n ln n

C. Minimax lower bound
It was shown in Valiant and Valiant [5] that if Q is the uniform distribution, when n ≍ lnSS , the minimax risk of estimating
L1 (P, Q) is a constant.
We prove a minimax lower bound for every Q, and show that the performance achieved by our estimator in Theorem 2 is
minimax rate-optimal for every fixed Q.
The main tool we employ is the so-called method of two fuzzy hypotheses presented in Tsybakov [21]. Suppose we observe
a random vector Z ∈ (Z, A) which has distribution Pθ where θ ∈ Θ. Let σ0 and σ1 be two prior distributions supported on
Θ. Write Fi for the marginal distribution of Z when the prior is σi for i = 0, 1. Let T̂ = T̂ (Z) be an arbitrary estimator of a
function T (θ) based on Z. We have the following general minimax lower bound.
Lemma 7. [21, Thm. 2.15] Given the setting above, suppose there exist ζ ∈ R, s > 0, 0 ≤ β0 , β1 < 1 such that

If V (F1 , F0 ) ≤ η < 1, then

σ0 (θ : T (θ) ≤ ζ − s) ≥ 1 − β0
σ1 (θ : T (θ) ≥ ζ + s) ≥ 1 − β1 .

(60)
(61)


 1−η−β −β
0
1
,
inf sup Pθ |T̂ − T (θ)| ≥ s ≥
2
T̂ θ∈Θ

(62)

where Fi , i = 0, 1 are the marginal distributions of Z when the priors are σi , i = 0, 1, respectively.

9

Here V (P, Q) is the total variation distance between two probability measures P, Q on the measurable space (Z, A).
Concretely, we have
Z
1
V (P, Q) , sup |P (A) − Q(A)| =
|p − q|dν,
(63)
2
A∈A
dQ
where p = dP
dν , q = dν , and ν is a dominating measure so that P ≪ ν, Q ≪ ν.
The following lemma was shown in Cai and Low [12]:

Lemma 8. For any given even integer L > 0, there exist two probability measures ν0 and ν1 on [−1, 1] that satisfy the
following conditions:
1) Rν0 and ν1 areR symmetric around 0;
2) R tl ν1 (dt) = R tl ν0 (dt), for l = 0, 1, 2, . . . , L;
3) |t|ν1 (dt) − |t|ν0 (dt) = 2EL [|t|; [−1, 1]],
where EL [|t|; [−1, 1]] is the distance in the uniform norm on [−1, 1] from the absolute value function |t| to the space polyL .
It is known that EL [|t|; [−1, 1]] = β∗ L−1 (1 + o(1)), where β∗ ≈ 0.2802 is the Bernstein constant [22].
.
The following lemma deals with the approximation theoretic properties of function |x−a|−a
x

Lemma 9. For any function f (x; a) =
or L such that

|x−a|−a
,x
x

∈ [0, 1], there exists a universal constant D > 0 that does not depend on a

a
EL [f (x; a); [ , 1]] &
D

(

1
√
L a

1
L2

1

0<a<

≤a≤

1
2

(64)

1
L2

where EL [f ; I] denotes the distance in the uniform norm on interval I from the function f to the space polyL .
Similar to Lemma 8, the next lemma constructs two measures for the function f (x; a) =
identical to that of Lemma 8.

|x−a|−a
.
x

The proof is essentially

, a ∈ [0, 1], there exist two probability measures
Lemma 10. For any 0 < η < 1 and positive integer L > 0, f (x; a) = |x−a|−a
x
ν1η,a , ν0η,a on [η, 1] such that
R
R
1) R tl ν1η,a (dt) = tl νR0η,a (dt), for all l = 0, 1, 2, . . . , L;
η,a
2) f (t; a)ν1 (dt) − f (t; a)ν0η,a (dt) = 2EL [f (x; a); [η, 1]],
where EL [f (x; a); [η, 1]] is the distance in the uniform norm on [η, 1] from the function f (x; a) to the space polyL .
The next lemma is an extension of [8, Lemma 3].
Lemma 11. Suppose U0 , U1 are two random variables supported on [a−M, a+M ], where a ≥ M ≥ 0 are constants. Suppose
E[U0j ] = E[U1j ], 0 ≤ j ≤ L. Denote the marginal distribution of X where X|λ ∼ Poi(λ), λ ∼ Ui as Fi . If L + 1 ≥ (2eM )2 /a,
then
!L+1
eM
,
(65)
V (F0 , F1 ) ≤ 2 p
a(L + 1)
where V (F0 , F1 ) is the total variation distance defined in (63).
We consider the set of approximate probability vectors
(
MS (ǫ) =

P :

S
X
i=1

)

pi − 1 ≤ ǫ ,

(66)

with some constant ǫ > 0. We further define the minimax risk under the Poisson sampling model with respect to MS (ǫ) with
a fixed Q as

2
(67)
RP (S, n, Q, ǫ) = inf sup EP L̂ − L1 (P, Q) .
L̂ P ∈MS (ǫ)

The following lemma relates RP (S, n, Q, ǫ) to RP (S, n, Q, 0).

Lemma 12. For any S, n ∈ N+ , 0 < ǫ < 1 and any distribution Q ∈ MS , we have

1
1
1
RP (S, n, Q, ǫ) − e−n(1−ǫ)/8 − ǫ2 .
4
2
2
Now we are ready to prove our main minimax lower bound.
RP (S, n(1 − ǫ)/4, Q, 0) ≥

(68)

10

Theorem 3. Suppose ln n & ln S,

PS

j=1 qj

∧

q

qj
n ln n

≫

q

ln n
n

+

√
S ln n
,S
n

2

inf sup EP |L̂ − L1 (P, Q)| &
L̂ P ∈MS

where the infimum is taken over all possible estimators.
In particular, if n & lnSS , ln n . ln S, we have

S
X
i=1

≥ 2. Then,

qi ∧

r

sup inf sup EP |L̂ − L1 (P, Q)|2 &

Q∈MS L̂ P ∈MS

qi
n ln n

!2

,

S
.
n ln n

(69)

(70)

Proof. Fix the distribution Q ∈ MS . Without loss of generality we assume that qS = min1≤j≤S qj . We construct two
probability measures µ0 , µ1 on the distribution P that will later be used in Lemma 7. Concretely, we use an independent prior
generation, and set
(q )

(q )

(q )
µ1 0

(q )
µ1 1

µ0 = µ0 0 ⊗ µ0 1 ⊗ . . . ⊗ δ1−γ

(71)

µ1 =

(72)

(qj )

In other words, we assign independent priors µi
symbol pS . The constant γ will later be set to

γ=

⊗

⊗ . . . ⊗ δ1−γ .

to each symbol pj , 1 ≤ j ≤ S − 1, and assign a delta mass at 1 − γ to the
X

n
j:qj ≤ c ln
n

qj
+
D

X

qj ,

(73)

n
j:qj > c ln
n

where D is the constant in Lemma 9, and c > 0 is a universal constant.
(q)
Now we construct µi , i ∈ {0, 1} for a generic q ∈ (0, 1). We consider two different cases.
η,a
n
1) 0 < q ≤ c ln
n , where c > 0 is a universal constant. We first construct two new probability measures ν̃i , i = 0, 1 from
η,a
the two probability measures constructed in Lemma 10. For i = 0, 1, the restriction of ν̃i is absolutely continuous with
respect to νi , with the Radon–Nikodym derivative given by
dν̃iη,a
η
= ≤ 1,
dνiη,a
t

t ∈ [η, 1],

(74)

and ν̃iη,a ({0}) = 1 − ν̃iη,a ([η, 1]) ≥ 0. Hence, ν̃iη,a , i = 0, 1 are probability measures on [0, 1], with the following
properties:
R
R
a) R tν̃1η,a (dt) = R tν̃0η,a (dt) = η;
b) R tl ν̃1η,a (dt) = tl ν̃0η,a
R (dt), for all l = 2, 3, . . . , L + 1;
c) |x − a|ν̃1η,a (dt) − |x − a|ν̃0η,a (dt) = 2ηEL [f (x; a); [η, 1]].
The construction of the Radon–Nikodym derivatives are inspired by Wu and Yang [8]. Define
L = d2 ln n, η =

a
q
2c ln n
,a =
,M =
,
D
M
n

(75)

where D is the constant in Lemma 9 and d2 > 0 is a universal constant. It follows from the assumption that 0 < a ≤ 21 .
(q)
(q)
Let g(x) = M x and let µi be the measures on [0, M ] defined by µi (A) = ν̃iη,a (g −1 (A)) for i = 0, 1. It then follows
that
Z
Z
q
(q)
(q)
(76)
tµ1 (dt) = tµ0 (dt) = ;
D
Z
Z
(q)
(q)
(77)
tl µ1 (dt) = tl µ0 (dt), for all l = 2, 3, . . . , L + 1;
Z
Z
(q)
(q)
|t − q|µ1 (dt) − |t − q|µ0 (dt) = 2ηM EL [f (x; a); [η, 1]]
(78)
r
q
&q∧
.
(79)
n ln n
q
cq ln n
n
.
Define
function
g(x)
=
q
+
2) q > c ln
n
n x, where x ∈ [−1, 1]. Let νi , i = 0, 1 be the two measures constructed in
(q)

(q)

Lemma 8. We define two new measures µi , i = 0, 1 by µi (A) = νi (g −1 (A)). Let
L = d2 ln n.

(80)

11

It then follows that
Z

Z

(q)
tµ0 (dt)

=

(q)

tl µ0 (dt) =

Z

(q)

tµ1 (dt) = q;

Z

(q)

tl µ1 (dt), for all l = 2, 3, . . . , L + 1;
r
Z
Z
cq ln n
(q)
(q)
EL [|t|; [−1, 1]]
|t − q|µ1 (dt) − |t − q|µ0 (dt) = 2
n
r
q
&q∧
.
n ln n

Since we have set pS = 1 − γ, where γ is defined in (73), it is clear that




S
S
X
X
pj 
pj  = Eµ1 
Eµ0 

(81)
(82)
(83)
(84)

(85)

j=1

j=1

= 1.

(86)

Now the construction of the two priors µ0 and µ1 are complete. In light of Lemma 12, it suffices to lower bound
RP (S, n, Q, ǫ) to give a lower bound to RP (S, n, Q, 0).
Let
χ
ǫ=
(87)
, χ = Eµ1 L1 (P, Q) − Eµ0 L1 (P, Q).
10
We know from (79) and (84) that
r
S−1
X
qj
(88)
qj ∧
χ&
n
ln n
j=1
r
 S

1 X
qj
qj ∧
(89)
≥ 1−
S j=1
n ln n
r
S
X
qj
qj ∧
,
(90)
&
n ln n
j=1
since we have assumed that qS = min1≤j≤S qj .
For i = 0, 1, introduce the events
\n
χo
P : |L1 (P, Q) − Eµi L1 (P, Q)| ≤
Ei = MS (ǫ)
.
4
It follows from the union bound that


S

X
χ
pj − 1 > ǫ + µi |L1 (P, Q) − Eµi [L1 (P, Q)]| >
µi [(Ei )c ] ≤ µi 
.
4
j=1

(91)

(92)

Introduce

F (Q) =

X

n
j:qj ≤ c ln
n



2c ln n
n

2

+

X

n
j:qj > c ln
n

4cqj ln n
n

4c2 S ln2 n 4c ln n
+
.
n2
n
It follows from the Hoeffing inequality in Lemma 35 that




χ2
2ǫ2
c
+ 2 exp −
µi [(Ei ) ] ≤ 2 exp −
F (Q)
8F (Q)
→ 0,
q
q
√
P
q
since we have assumed that Sj=1 qj ∧ n lnj n ≫ lnnn + Snln n .
≤

(93)

(94)

(95)
(96)

12

Denote by πi the conditional distribution defined as
πi (A) =

µi (Ei ∩ A)
, i = 0, 1.
µi (Ei )

(97)

Now consider π0 , π1 as two priors and denote the corresponding marginal distributions on the observations (X1 , X2 , . . . , XS )
as F0 , F1 . Note that Xj ∼ Poi(npj ). Setting
χ
(98)
ζ = Eµ0 [L1 (P, Q)] +
2
χ
s= ,
(99)
4
we have β0 = β1 = 0 in Lemma 7. The total variation distance is then upper bounded as
V (F0 , F1 ) ≤ V (F0 , G0 ) + V (G0 , G1 ) + V (G1 , F1 )
≤ µ0 [(E0 )c ] + V (G0 , G1 ) + µ1 [(E1 )c ]

(100)
(101)

≤ V (G0 , G1 ) + o(1),

(102)

where Gi is the marginal
PS distribution of the observations under priors µi . It follows from Lemma 11 and the fact that
V (⊗Si=1 Pi , ⊗Si=1 Qi ) ≤ i=1 V (Pi , Qi ) that
S−1
X  1 d2 ln n
(103)
2
V (G0 , G1 ) ≤
2
i=1
≤

2S

(104)

2d2 ln n

2S
nd2 ln 2
→ 0,

=

(105)
(106)

as long as ln n & ln S since one can take d2 to be arbitrarily large.
It follows from Lemma 7 and Markov’s inequality that
RP (S, n, Q, ǫ) ≥ s2 · inf

sup

L̂ P ∈MS (ǫ)

s2
(1 − o(1))
2
χ2
=
(1 − o(1)),
32



P |L̂ − L1 (P, Q)| ≥ s

≥

(107)
(108)
(109)

which together with Lemma 12 implies that
1
1
1
RP (S, n, Q, ǫ) − e−n(1−ǫ)/8 − ǫ2
4
2
2
χ2
1 −n(1−χ/10)/8
χ2
≥
(1 − o(1)) − e
−
128
2
200
& χ2
!2
r
S
X
qi
qi ∧
&
,
n ln n
i=1

RP (S, n(1 − ǫ)/4, Q, 0) ≥

(110)
(111)
(112)
(113)

as long as we choose the constants d2 large enough to guarantee that χ ≤ 5.

Combining Corollary 2 and Theorem 3, we have the following theorem.
P

√
S √
Theorem 4. Suppose ln S . ln n . ln
qi ∧ qi n ln n , S ≥ 2. Then,
i=1
2

inf sup EP |L̂ − L1 (P, Q)| ≍
L̂ P ∈MS

S
X
i=1

qi ∧

r

qi
n ln n

!2

.

(114)

13

In particular, if n &

S
ln S , ln n

. ln S, then
sup inf sup EP |L̂ − L1 (P, Q)|2 ≍

Q∈MS L̂ P ∈MS

S
.
n ln n

(115)

The estimator in Construction 1 achieves the minimax rates for every fixed Q.
III. D IVERGENCE E STIMATION WITH U NKNOWN Q
Now we consider the general case where both P and Q are unknown to us, i.e., P = Q = MS .
We utilize the Poisson sampling model, in which we observe two Poisson random vectors
X = [X1 , X2 , . . . , XS ],

(116)

Y = [Y1 , Y2 , . . . , YS ],

(117)

where all the coordinates of X and Y are mutually independent, and Xi ∼ Poi(npi ), Yi ∼ Poi(nqi ). We introduce the empirical
probabilities p̂i = Xni , q̂i = Yni .
A. Performance of the MLE
P
In this case, the MLE is expressed as L1 (Pn , Qn ) = Si=1 |p̂i −q̂i |. Since |L1 (Pn , Qn )−L1 (P, Q)| ≤ L1 (Pn , P )+L1 (Qn , Q)
by the triangle inequality, and E|p̂i − q̂i | ≥ E|p̂i − qi | by the conditional Jensen’s inequality, Theorem 1 can again be applied
here to give the performance of the MLE.
Theorem 5. If n & S, the MLE satisfies
sup
P,Q∈MS

E|L1 (Pn , Qn ) − L1 (P, Q)|2 ≍

S
.
n

(118)

Hence, the MLE achieves the mean squared error S/n, and requires n ≫ S samples to be consistent.
B. Construction of the optimal estimator
Again we apply our general recipe to construct the optimal estimator, but encounter several new difficulties: f (x, y) = |x−y|
is not analytic on a segment, and both the uncertainty set and the polynomial approximation need to be generalized to the 2D
case. We will overcome these obstacles step by step.
For simplicity of analysis, we conduct the classical “splitting” operation [20] on the Poisson random vector X, and obtain two
independent identically distributed random vectors Xj = [X1,j , X2,j , . . . , XS,j ]T , j ∈ {1, 2}, such that each component Xi,j in
Xj has distribution Poi(npi /2), and all coordinates in Xj are independent. For each coordinate i, the splitting process generates
PXi
Xi
i
a random sequence {Tik }X
k=1 such that {Tik }k=1 |X ∼ multinomial(Xi ; (1/2, 1/2)), and assign Xi,j =
k=1 1(Tik = j) for
i
j ∈ {1, 2}. All the random variables {{Tik }X
k=1 : 1 ≤ i ≤ S} are conditionally independent given our observation X. The
splitting operation is similarly conducted for the Poisson random vector Y. The “splitted” empirical probabilities are defined
as p̂i,j = Xi,j /(n/2), q̂i,j = Yi,j /(n/2). To simplify notation, we redefine n/2 as n to ensure that np̂i,j ∼ Poi(npi ), j = 1, 2.
We emphasize that the sampling splitting approach is not needed for the actual estimator construction.
As usual, first we classify “smooth” and “non-smooth” regimes. Since the function f (x, y) = |x − y| ∈ C([0, 1]2 ) is not
analytic on the segment x = y ∈ [0, 1], we are looking for the “uncertainty set” U containing this segment such that any
(p, q) ∈ U can be “localized” in the previous sense. We have the following lemma.

Lemma 13. The two-dimensional set U ⊂ [0, 1]2 defined as
r
√
2c1 ln n √
U = {(p, q) : |p − q| ≤
( p + q), p ∈ [0, 1], q ∈ [0, 1]}
n
satisfies
U ⊃ ∪x∈[0,1] U (x; c1 ) × U (x; c1 ),

(119)

(120)

where U (x; c1 ) is given by (24).
We design another set U1 as follows:
r

(c1 + c3 ) ln n √
√
(121)
( p + q)},
n
where 0 < c3 < c1 . Clearly U1 ⊂ U . We choose the constants c1 and c3 later to ensure that the following four events happen
with high probability:
U1 = {(p, q) : |p − q| ≤

14

E1 =
E2 =
E3 =
E4 =

S
\

(

i=1
(
S
\

i=1
(
S
\
i=1
S 
\

i=1

p̂i,1 − q̂i,1
p̂i,1 − q̂i,1
p̂i,1 + q̂i,1

)
p
(c1 + c3 ) ln n p
>
( p̂i,1 + q̂i,1 ) ⇒ pi ≥ qi
n
)
r
p
(c1 + c3 ) ln n p
<−
( p̂i,1 + q̂i,1 ) ⇒ pi ≤ qi
n
2 )

c1 ln n
2c1 ln n
<
.
⇒ (pi , qi ) ∈ 0,
n
n
r

(p̂i,1 , q̂i,1 ) ∈ U1 , p̂i,1 + q̂i,1 ≥

(122)

(123)

(124)

c1 ln n
c1 ln n
pi + qi
⇒ (pi , qi ) ∈ U, pi + qi ≥
, p̂i,1 + q̂i,1 ≥
n
2n
2



.

(125)

We have the following lemma controlling the probability of these events happening simultaneously.
Lemma 14. Denote the overall “good” event E = E1 ∩ E2 ∩ E3 ∩ E4 , where E1 , E2 , E3 , E4 are defined in (122),(123),(124),
8
− 1 ≈ 0.373,
(125). Then, assuming cc31 < (√2+1)
2
P(E c ) ≤

15S
,
nβ

(126)

where the constant β is given by
β = min


c

1

6

2

,

(c1 − c3 ) 1
,
96c1
3

√
2c1 −

!2 
√

√
2+1
.
c1 + c3

2

(127)

It is evident that we can make β in (127) arbitrarily large by taking c1 large and keeping c3 /c1 a small constant. Clearly, if the
true parameters (p, q) ∈
/ U , the MLE would be a decent estimator. It suffices to construct estimators when the true parameters
(p, q) ∈ U . The known Q case seems to suggest that we consider the best polynomial approximation of f (x, y) = |x − y| on
U . However, this will not work for two reasons:
1) the entire 2D stripe U is too large for the polynomial approximation error to vanish at the correct rate;
2) best polynomial approximation in the 2D case is not unique, and may not achieve the desired pointwise error.
We will explore these reasons in more detail in Section IV. To solve the first problem, we remark that although U is the
set such that its element can be localized within U , a specific element (x, y) ∈ U can be localized in a much smaller subset
U (x; c1 ) × U (y; c1 ) ⊂ U , where U (x; c1 ) is given by (24). Hence, the approximation regime should be dependent on the
empirical observations to fully utilize the available information.
For the second problem, we need to design a specific polynomial with satisfactory pointwise approximation properties. Our
approximation recipe is the following. Take K = c2 ln n.

2
√
√ √
√
1) Over the square 0, 2c1nln n : we consider the decomposition |x−y| = ( x+ √
y)| x− y| and√introduce the following
√
√
two bivariate polynomials uK (x, y) and vK (x, y) to uniformly approximate x + y and | x − y|, respectively.
Specifically, we have
√
√
√
√
(128)
sup |P (x, y) − ( x + y)|
sup |uK (x, y) − ( x + y)| = inf 2
(x,y)∈[0,1]2

sup
(x,y)∈[0,1]2

√

|vK (x, y) − | x −

√

P ∈polyK (x,y)∈[0,1]2

y|| =

inf

P ∈poly2K

sup
(x,y)∈[0,1]2

√
√
|P (x, y) − | x − y||.

(129)

Then, denote h2K (x, y) = uK (x, y)vK (x, y) − uK (0, 0)vK (0, 0), we use the polynomial


xn
yn
2c1 ln n
(1)
(130)
h2K
,
PK (x, y) =
n
2c1 ln n 2c1 ln n

2
(1)
(1)
to approximate |x − y| over the square 0, 2c1nln n . The polynomial PK (x, y) satisfies PK (0, 0) = 0. We remove the
(1)
constant term in the definition of PK to guarantee that the estimator we construct is agnostic to the unknown support size
S. In practice, uK and vK can be replaced by the efficiently implementable lowpass filtered Chebyshev expansion [23],
which achieves the same error rate as the best polynomial approximation.
ln n
, we utilize the best approximation polynomial of |t|
2) Once we can assert with high probability (p, q) ∈ U, p + q ≥ c12n

15

on [−1, 1] with order K. Denote it as
sup |P (t) − |t||

RK (t) = argmin

(131)

P ∈polyK t∈[−1,1]

=

K
X

rj tj ,

(132)

j=0

we have
(2)

PK (x, y; p̂i,1 , q̂i,1 ) =

K
X
j=0

where W =

q

rj W −j+1 (x − y)j ,

q
(p̂i,1 + q̂i,1 ) ∨ n1 ).

(133)

8c1 ln n
(
n

(1)

Finally, we use the second part of the samples to construct the unbiased estimators for PK (x, y) defined in (130) and
(2)
(1)
(2)
PK (x, y; p̂i,1 , q̂i,1 ) defined in (133). Concretely, we introduce the estimators P̃K (p̂i,2 , q̂i,2 ) and P̃K (p̂i,2 , q̂i,2 ; p̂i,1 , q̂i,1 ) such
that
h
i
(1)
(1)
E P̃K (p̂i,2 , q̂i,2 ) = PK (p, q)
(134)


(2)
(2)
(135)
E P̃K (p̂i,2 , q̂i,2 ; p̂i,1 , q̂i,1 ) p̂i,1 , q̂i,1 = PK (p, q; p̂i,1 , q̂i,1 ).
These unbiased estimators are easy to construct since for any r, s ≥ 1, r, s ∈ Z, (np̂, nq̂) ∼ Poi(np) × Poi(nq), we have [24,
Ex. 2.8]
 s−1 

r−1
Y
j
i Y
q̂ −
= pr q s .
(136)
p̂ −
E
n
n
j=0
i=0

2
(1)
We first present the performance of the estimator P̃K (p̂i,2 , q̂i,2 ) when (p, q) ∈ 0, 2c1nln n .
2

Lemma 15. Suppose (p, q) ∈ 0, 2c1nln n , (np̂, nq̂) ∼ Poi(np) × Poi(nq). Then,
r
1 ln n √
√
1 ln n
(1)
( p + q) + 2
|EP̃K (p̂, q̂) − |p − q|| .
K
n
K n
BK
(1)
(p + q),
Var(P̃K (p̂, q̂)) .
n

(137)
(138)

(1)

for some universal constant B > 0. The estimator P̃K is introduced in (134), and K = c2 ln n, c2 < c1 .
(2)

We then analyze the estimator P̃K (p̂i,2 , q̂i,2 ; p̂i,1 , q̂i,1 ) when (p, q) ∈ U, p + q ≥

ln n
,x + y ≥
Lemma 16. Suppose (p, q) ∈ U, p + q ≥ c12n
Suppose (np̂, nq̂) ∼ Poi(np) × Poi(nq). Then,

p+q
2 ,x

c1 ln n
2n .

∈ [0, 1], y ∈ [0, 1], where the set U is defined in (119).
r

ln n √
√
( x + y)
n
BK
(2)
Var(P̃K (p̂, q̂; x, y)) .
(x + y),
n

(2)
EP̃K (p̂, q̂; x, y)

1
− |p − q| .
K

(139)
(140)

(2)

for some universal constant B > 0. The estimator P̃K is introduced in (135), and K = c2 ln n, c2 < c1 .
The final estimator is presented as follows.
Estimator Construction 2. As before, use sample splitting to obtain (p̂i,1 , q̂i,1 ) and (p̂i,2 , q̂i,2 ). Denote
q

p
(c1 +c3 ) ln n p


( p̂i,1 + q̂i,1 )
p̂
−
q̂
p̂
−
q̂
>
i,2
i,2
i,1
i,1

n

q


p
p

q̂i,2 − p̂i,2
p̂i,1 − q̂i,1 < − (c1 +cn3 ) ln n ( p̂i,1 + q̂i,1 )
L̃2 =

(1)

P̃K (p̂i,2 , q̂i,2 )
p̂i,1 + q̂i,1 < c1 nln n




 (2)
P̃K (p̂i,2 , p̂i,2 ; p̂i,1 , q̂i,1 ) (p̂i,1 , q̂i,1 ) ∈ U1 , p̂i,1 + q̂i,1 ≥ c1 nln n

(141)

16

and define


L̂(2) = 0 ∨ L̃2 ∧ 2 .

(142)

(1)

(2)

Here U is given by (119), U1 is defined in (121), the estimators P̃K and P̃K are defined in (134) and (135) K = c2 ln n,
8
and c1 > c3 > c2 > 0 are properly chosen universal constants, cc31 < (√2+1)
− 1 ≈ 0.373.
2
q
1

Θ0

(p̂1 , q̂1 )
plug-in: q̂2 − p̂2
(p̂1 , q̂1 )

1D polynomial approximation
of |t|q
(t = p − q)
√
with width 8c1nln n p̂1 + q̂1

(c1 +c3 ) ln n
n

2D polynomial
approximation
(p̂ , q̂ )
of |p − q| 1 1
0

|p − q| =

q

(c1 +c3 ) ln n √
( p
n

+

√
q)

plug-in: p̂2 − q̂2
(p̂1 , q̂1 )
p
1

(c1 +c3 ) ln n
n

Fig. 1: Pictorial explanation of the minimax rate-optimal estimator in the unknown Q case. Note that we use (p̂1 , q̂1 ) to
determine which one of the four estimators to use, and then apply the second independent sample (p̂2 , q̂2 ) to estimate. The
dashed diagonal line denotes the points where the function f (p, q) = |p − q| is not analytic.
The next theorem presents the performance of L̂(2) .
Theorem 6. For ln n . ln S, we have
sup
P,Q∈MS

E|L̂(2) − L1 (P, Q)|2 .

S
.
n ln n

(143)

Proof. Recall the “good” events E1 , E2 , E3 , E4 defined in (122),(123),(124),(125) and introduce E = E1 ∩ E2 ∩ E3 ∩ E4 . We
have
i
h
i

2
h
(144)
E L̂(2) − L1 (P, Q) = E (L̂(2) − L1 (P, Q))2 1(E) + E (L̂(2) − L1 (P, Q))2 1(E c )
h
i
≤ E (L̃2 − L1 (P, Q))2 1(E) + 4P(E c )
(145)
h
i 60S
(146)
≤ E (L̃2 − L1 (P, Q))2 1(E) + β ,
n
where we have applied Lemma 14 and the constant β is defined in (127).
Define the random variables
X
E1 =
(p̂i,2 − q̂i,2 − |pi − qi |)
(147)
i∈I1

E2 =

E3 =
E4 =

X

i∈I2

(q̂i,2 − p̂i,2 − |pi − qi |)

X

i∈I3

X

i∈I4

(1)

P̃K (p̂i,2 , q̂i,2 ) − |pi − qi |
(2)

(148)


P̃K (p̂i,2 , q̂i,2 ; p̂i,1 , q̂i,1 ) − |pi − qi |

(149)


(150)

17

where the random index sets I1 , I2 , I3 , I4 are defined as
)
(
r
p
(c1 + c3 ) ln n p
I1 = i : p̂i,1 − q̂i,1 >
( p̂i,1 + q̂i,1 ) ⇒ pi ≥ qi
n
)
(
r
p
(c1 + c3 ) ln n p
I2 = i : p̂i,1 − q̂i,1 < −
( p̂i,1 + q̂i,1 ) ⇒ pi ≤ qi
n
(
2 )

c1 ln n
2c1 ln n
I3 = i : p̂i,1 + q̂i,1 <
⇒ (pi , qi ) ∈ 0,
n
n


c1 ln n
pi + qi
c1 ln n
.
⇒ (pi , qi ) ∈ U, pi + qi ≥
, p̂i,1 + q̂i,1 ≥
I4 = i : (p̂i,1 , q̂i,1 ) ∈ U1 , p̂i,1 + q̂i,1 ≥
n
2n
2

(151)
(152)
(153)
(154)

The index sets I1 , I2 , I3 , I4 are independent of the random variables {p̂i,2 : 1 ≤ i ≤ S} and {q̂i,2 : 1 ≤ i ≤ S}. It follows
from the definition of the Ei ’s that


L̃2 − L1 (P, Q) 1(E) = E1 1(E) + E2 1(E) + E3 1(E) + E4 1(E).
(155)

Hence, it follows from the Cauchy–Schwarz inequality that

4

2
X
 60S
(2)
E Ej2 + β
E L̂ − L1 (P, Q) ≤ 4
n
j=1

(156)

It follows from the law of total variance that

EE12 = E Var(E1 |I1 ) + (E[E1 |I1 ])2
= EVar(E1 |I1 )
≤

S
X
i=1



(157)
(158)

pi + qi
n

(159)

2
,
(160)
n
where we have used the fact that E[E2 |I2 ] = 0 with probability one, the independence of p̂i,2 and q̂i,2 , and Lemma 3. Similarly
we have EE22 ≤ n2 .
Regarding EE32 , it follows from Lemma 15 and the mutual independence of {p̂i,2 : 1 ≤ i ≤ S} and {q̂i,2 : 1 ≤ i ≤ S} that
!2
√
S
S √
X
X
pi + qi
BK
1
2
√
EE3 .
(161)
(pi + qi ) +
+
n
n ln n
n ln n
i=1
i=1
2

S
S
1
,
(162)
∨
. 1−ǫ +
n
n ln n
n ln n
=

where ǫ = c2 ln B. 
Regarding E E42 , it follows from the bias-variance decomposition and Lemma 16 that
E[E42 |{(p̂i,1 , q̂i,1 )

: 1 ≤ i ≤ S}] .

S
X
BK
i=1

n

(p̂i,1 + q̂i,1 ) +

S
X
i=1

!2
p
p̂i,1 + q̂i,1
√
,
n ln n

(163)

18

where the constant B is the one in Lemma 16. Taking expectations with respect to {(p̂i,1 , q̂i,1 ) : 1 ≤ i ≤ S}, we have
!2
S
S p
X
X
p̂i,1 + q̂i,1
1
2
√
(164)
E[E4 ] .
E(p̂i,1 + q̂i,1 ) + E
n1−ǫ
n ln n
i=1
i=1
!
r
r
S X
S
X
2
p̂i,1 + q̂i,1 p̂j,1 + q̂j,1
E
≤ 1−ǫ +
(165)
n
n ln n
n ln n
i=1 j=1
r
r


S
X
X
p̂i,1 + q̂i,1
2
E[p̂i,1 + q̂i,1 ] E[p̂j,1 + q̂j,1 ]
E
+
≤ 1−ǫ +
(166)
n
n ln n
n ln n
n ln n
i=1
1≤i,j≤S,i6=j
X pi + qi + pj + qj
2
2
+
(167)
≤ 1−ǫ +
n
n ln n
n ln n
1≤i,j≤S

.

1

n1−ǫ

S
+
,
n ln n

(168)

where ǫ = c2 ln B.
Combining everything together, we have

2
E L̂(2) − L1 (P, Q) .

1
n1−ǫ

+

S
∨
n ln n



S
n ln n

2

+

S
,
nβ

(169)

where ǫ = c2 ln B, and the constant B is the larger constant between the one in Lemma 15 and Lemma 16. The constant β
is in (127).
1
S
S
If ln n . ln S, we can take c2 small enough and c1 , c3 large enough to guarantee that nSβ . n ln
n , n1−ǫ . n ln n . Upon
(2)
noting that L̂ ∈ [0, 2], we have

2
S
E L̂(2) − L1 (P, Q) .
.
(170)
n ln n

Since the lower bound for the known Q case also serves as a lower bound for the general case with a simulation argument,
Theorem 3 and Theorem 6 yield that L̂(2) is minimax rate-optimal. Note that L̂(2) achieves the minimax rate without knowing
the support size S a priori. Moreover, the effective sample size enlargement effect holds again: the performance of the optimal
estimator with n samples is essentially that of the MLE with n ln n samples.
IV. C OMPARISON

WITH

OTHER A PPROACHES

In this section, we review some other possible approaches in estimating the L1 distance, and apply approximation theory to
argue the strict suboptimality of some approaches.
A. Approximation only around the origin
In the previous papers [5]–[9] in estimating entropy, power sum, mutual information, etc, the approximation methodology
is conducted only around the origin. However, we remark that this is insufficient in estimating the L1 distance. We have the
following result.
Lemma 17. Let L̂ denote an estimator of L1 (P, Q) that satisfies the following:
L̂ =

S
X

g(p̂i , q̂i ),

(171)

i=1


2
where the estimator g(p̂i , q̂i ) ∈ [−B, B] is a bounded function that satisfies g(p̂i , q̂i ) = |p̂i − q̂i | when (p̂i , q̂i ) ∈
/ 0, 2c1nln n ,
g(0, 0) = 0. Suppose n ≫ S. Then,
sup
P,Q∈MS

E|L̂ − L1 (P, Q)|2 ≫

S
.
n ln n

(172)

Lemma 17 explains the reason why the estimator of Valiant and Valiant [5] can only achieve the optimal error rate when
n . S . n ln n, but ours achieves the optimal error rate for a much large set of parameter configurations.

19

B. One-dimensional approximation in the 2D case
In the construction of L̂(2) , we split into two cases when (p̂, q̂) ∈√U1 , i.e., 1D
approximation of |t| via the substitution
√
√ √
t = x − y if p̂ + q̂ > c1 ln n/n, and the decomposition of |x − y| into ( x + y)| x − y| otherwise. Can we always do 1D
approximation of |t|pwith t = x− y to achieve the desired approximation error, i.e., propose some P (t) ∈ polyK with K ≍ ln n
1
and |P (t) − |t|| . |t|/(n ln n) + n ln
n for any |t| ≤ c1 ln n/n? We have the following lemma regarding the approximation
of |t|.
Lemma 18. If QK (t) ∈ polyK is even with QK (0) = 0, and achieves the best uniform error rate maxt∈[−1,1] |QK (t) − |t|| .
1/K, we have
lim sup
K→∞

1
K

||t| − |QK (t) − |t|||
< ∞.
t2
0<|t|≤1
sup

Now we apply Lemma 18 to the hypothetical polynomial P (t). Doing parameter substitution t =
assumption we have for any y ∈ [−1, 1],
p


|y|
n
1
c1 ln n
P
y − |y| .
+ 2,
c1 ln n
n
K
K

(173)
c1 ln n
n y, y

∈ [−1, 1], by
(174)

where K ≍ ln n. It follows from Jensen’s inequality that
p
 



|y|
n
c1 ln n
c1 ln n
1
P
(175)
y +P −
y
/2 − |y| .
+ 2.
c1 ln n
n
n
K
K


Define Q(y) = c1 nln n P c1 nln n y + P − c1 nln n y /2. It is clear that Q(y) satisfies the assumptions in Lemma 18. Hence,
|Q(y) − |y|| ≥ |y| − CKy 2 .

However, it contradicts the upper bound (175) when K12 ≪ |y| ≪
rate that is achieved by our 2D approximation approach.

1
K.

(176)

Hence, any 1D approximation does not achieve the error

C. Approximation on the entire 2D stripe
In the unknown Q case we have decomposed the stripe U into subsets where polynomial approximations take place. Is it
2
possible
p that we use a single polynomial P (x, y) ∈ polyK of degree K ≍ ln n to approximate |x′ − y| such that |P (x, y) − |x −
y|| . (x + y)/(n ln n) for any (x, y) ∈ U ? We prove that the answer is negative even for U = ∪x∈[c1 ln n/n,tn ] U (x; c1 ) ×
U (x; c1 ) ⊂ U and any tn ≫ (ln n)3 /n.

Lemma 19. If (ln n)3 /n ≪ tn ≤ 1/2, K ≍ ln n, we have
√
lim inf n ln n · inf 2 sup
n→∞

P ∈polyK

(x,y)∈U ′

|P (x, y) − |x − y||
√
= +∞.
x+y

′

Lemma 19pshows that for a too large set U (e.g., U ′ = U ), every polynomial fails to achieve the desired approximation
error bound (x + y)/(n ln n). Hence, it is necessary to make the approximation regime be random and dependent on the
empirical observations.
D. The failure of any plug-in approach
It is evident that the optimal L1 distance estimators we constructed heavily exploit the interactions of P and Q. For example,
in the known Q case, the estimator for L1 (P, Q) is not of the form L1 (g(Pn ), Q), where g(·) is an arbitrary function of the
empirical distribution of P that is independent of Q.
We show that for any estimator g(Pn ) of the distribution P , the plug-in approach L1 (g(Pn ), Q) does not achieve the minimax
rates in estimating L1 (P, Q) when one considers the worst cases among all P, Q ∈ MS .

Lemma 20. Consider the known Q case. Suppose g(Pn ) ∈ RS is an arbitrary function of the empirical distribution Pn , and
g(·) does not depend on Q. Then, if n & S,
sup
P,Q∈MS

2

EP (L1 (g(Pn ), Q) − L1 (P, Q)) &

S
.
n

(177)

Lemma 20 shows that since the plug-in approach L1 (g(Pn ), Q) does not explicitly exploit the nonsmoothness of the function
L1 (P, Q), in the worst case it behaves essentially like the maximum likelihood estimator as shown in Corollary 1.

20

V. ACKNOWLEDGEMENTS
We are grateful to Vilmos Totik for discussing multivariate approximation theory, and for the insights that motivated the
proof of Lemma 19. We would like to thank Gregory Valiant for discussing the estimator in [5].
A PPENDIX A
AUXILIARY L EMMAS
The first-order symmetric difference of a function f is given by




h
h
∆1h f (x) = f x +
−f x−
,
2
2

(178)

while the second order symmetric difference is given by

∆2h f (x) = ∆h ∆1h f (x)

(179)

= f (x + h) − 2f (x) + f (x − h).

(180)

Analogously, the r-th order symmetric difference can be defined, and it is zero when [x, x + rh] or [x − rh, x] are not inside
the domain of f .
p
For function f (x) with domain [0, 1], ϕ(x) = x(1 − x), the first-order Ditzian–Totik modulus of smoothness is defined
as
ωϕ1 (f, t) , sup k∆1hϕ f (x)k∞ ,
(181)
0<h≤t

and the second-order Ditzian–Totik modulus of smoothness is defined as
ωϕ2 (f, t) , sup k∆2hϕ f (x)k∞ .

(182)

0<h≤t

Similarly, we can also define the r-th order Ditzian–Totik modulus of smoothness for a function f (x) with domain [0, 1]2 :
r
ω[0,1]
2 (f, t) =

sup
1≤i≤2,0<h≤t,x∈[0,1]2

|∆ri,hϕ(xi ) f (x)|,

(183)

where ∆i,h denotes the symmetric difference with respect to the i-th coordinate.
The next lemma upper bounds the best polynomial approximation error by the Ditzian-Totik moduli.
Lemma 21. [25, Thm. 7.2.1, Thm. 12.1.1.] There exists a universal constant M (r) > 0 such that for any function f ∈ C[0, 1],
En (f ; [0, 1]) ≤ M (r)ωϕr (f, n−1 ),

n > r,

(184)

where En [f ; I] denotes the distance of the function f to the space polyn in the uniform norm k · k∞,I on I ⊂ R. Moreover,
if f (x) : [0, 1]2 7→ R, we have
−1
r
),
En [f ; [0, 1]2 ] ≤ M ω[0,1]
2 (f, n

(185)

for any r < n, where M is independent of f and n, and En [f ; [0, 1]2 ] denotes the distance of the function f to the space
poly2n in the uniform norm on [0, 1]2 .
The modulus ωϕ2 (f, t) is computed for a variety of functions in the following lemma.
Lemma 22. [25, Chap. 3.4] Suppose f (x) = xδ , 0 < δ < 1, x ∈ [0, 1]. Then,
ωϕ2 (f, t) ≍ t2δ

ωϕ1 (f, t)

(186)
2δ

≍ max{t , t}

(187)

where ωϕ1 (f, t) is defined in (181), ωϕ2 (f, t) is defined in (182).
√
√
Lemma 23. Suppose f (x; a) = | x − a|, x ∈ [0, 1], and a ∈ [0, 1] is a parameter. Then,
t
ωϕ1 (f, t) ≤ √ .
2

Next lemma computes the Ditzian–Totik modulus for function f (x) = |2x∆ − q|, x ∈ [0, 1].

(188)

21

Lemma 24. Suppose f (x) = |2x∆ − q|, ∆ > 0, 0 ≤ q ≤ 2∆, x ∈ [0, 1]. Then, for any integer K ≥ 1,

2∆
2q
q ≤ 1+K

2

 √
2
−1
2 q(2∆−q)
2∆
2∆K 2
ωϕ (f, K ) =
K
1+K 2 ≤ q ≤ 1+K 2



2
2(2∆ − q) 2∆K
1+K 2 ≤ q ≤ 2∆
( p
)
q(2∆ − q)
. min q,
, (2∆ − q) ,
K

(189)

(190)

where ωϕ2 (f, t) is defined in (182).
Lemma 25 (Markov’s inequality). [26, Chap 4, Thm 1.4] Suppose Pn ∈ polyn is defined on [−1, 1]. Then,
sup |Pn′ (x)| ≤ n2

x∈[−1,1]

sup |Pn (x)|

(191)

x∈[−1,1]

Lemma 26. [25, Thm. 7.3.1.] For Pn the best n-th degree polynomial approximation to f in [0, 1] and an integer r ∈ {1, 2}
we have
sup |ϕr Pn(r) | ≤ M nr ωϕr (f, n−1 ),

(192)

x∈[0,1]

where ϕ(x) =

p
x(1 − x) and M is independent of n and f .

The next lemma shows that a polynomial on [−1, 1] nearly attains its supremum norm in a slightly smaller interval contained
in [−1, 1].
Lemma 27. [25, Thm. 8.4.8.] Suppose c > 0 is a constant, Pn ∈ polyn defined on [−1, 1], n2 > c. Then, there exists a
constant M (c) > 0 that does not depend on n and Pn such that
sup |Pn (x)| ≤ M (c)

x∈[−1,1]

sup
x∈[−1+cn−2 ,1−cn−2 ]

|Pn (x)|.

(193)

Lemma 28. Suppose PK (x) is the best approximation polynomial with order K of function f (x) ∈ C[0, 1] defined as
PK (x) = argmin max |f (x) − P (x)|.

(194)

P ∈polyK x∈[0,1]

Then, the best approximation polynomial with order 2K of function f (z 2 ), z ∈ [−1, 1] is given by PK (z 2 ).
The following lemma characterizes the upper bounds of the coefficients of a bounded real polynomial.
P
Lemma 29. [17] Let pn (x) = nν=0 aν xν be a polynomial of degree at most n such that |pn (x)| ≤ A for x ∈ [a, b]. Then
1) If a + b 6= 0, then

−ν 
n
a+b
b+a
|aν | ≤ 27n/2 A
+1 ,
ν = 0, · · · , n.
(195)
2
b−a
2) If a + b = 0, then

√
|aν | ≤ Ab−ν ( 2 + 1)n ,

ν = 0, · · · , n.

(196)
j

The following lemma gives an upper bound for the second moment of the unbiased estimate of (p − q) in Poisson model.
Lemma 30. Suppose nX ∼ Poi(np), p ≥ 0, q ≥ 0. Then, the estimator

j  
k−1
X
Y
h
j
j−k
gj,q (X) ,
(−q)
X−
n
k
k=0

(197)

h=0

is the unique unbiased estimator for (p − q)j , j ≥ 0, j ∈ N, and its second moment is given by
j  2
X
j
pk k!
2
E[(gj,q (X)) ] =
(p − q)2(j−k) k
k
n
k=0


 p j
n(p − q)2
Assuming p > 0,
Lj −
= j!
n
p

(198)
(199)

22

where Lm (x) stands for the Laguerre polynomial with order m, which is defined as:
m  
X
m (−x)k
Lm (x) =
k!
k
k=0
n
o
2
If M ≥ max n(p−q)
, j , we have
p
E[(gj,q (X))2 ] ≤
When k = 0,

Qk−1

h=0

X−

h
n





2M p
n

j

(200)

.

(201)

, 1. When p = 0, gj,q (X) ≡ (−q)j , E[gj,q (X)]2 ≡ q 2j .

We construct the unbiased estimator of (p − q)j , j ≥ 0 when both p and q are unknown as in the following lemma.
Lemma 31. Suppose (np̂, nq̂) ∼ Poi(np)×Poi(nq). Then, the following estimator using (p̂, q̂) is the unique unbiased estimator
for (p − q)j , j ≥ 0, j ∈ Z:
j−k
j   k−1
X
X
m
i
j Y
j−k
(202)
(q̂ − ).
(p̂ − )(−1)
Âj (p̂, q̂) =
n
n
k
m=0
i=0

k=0

Furthermore,

EÂ2j


j
8j(p ∨ q)
2
≤ 2(p − q) ∨
.
n

(203)

The following lemma characterizes the behavior of the central moments of Poisson distributions.
Lemma 32. Suppose np̂ ∼ Poi(np). Then, for any integer s ≥ 2, there exist ⌊s/2⌋ constants hj,s that are independent of n,
such that
E(p̂ − p)s =

⌊s/2⌋
1 X
hj,s (np)j .
ns j=1

(204)

Furthermore,
|hj,s | ≤

2j j s
j!

(205)

 s s
≤ (2ee/(e−1) )s
.
ln s

Consequently, there exists a constant Cs > 0 depending only on s satisfying (Cs )1/s .
E|p̂ − p|s ≤ Cs

s/2

(np)

∨ (np)

ns

(206)
s
ln s

such that

.

(207)

s
We emphasize that the scaling lnss is consistent with the general moment bounds in [27]. However, the results in [27]
do not directly apply here. Furthermore, Lemma 32 provides bounds on each individual hj,s , which is not obtainable from a
general moment bound.
1
, where np̂ ∼ Poi(np).
The next lemma controls the moments of p̂∨1/n
Lemma 33. Suppose np̂ ∼ Poi(np). Then, for any integer j ≥ 0, there exists a constant Bj depending only on j such that
E
One may take Bj = j


j j
e

+ 1 + j2j+1 + j



16(j+1)
e

Bj
1
1 j ≤ pj .
(p̂ ∨ n )

j+1

(208)

.

The following lemma gives well-known tail bounds for Poisson and binomial random variables.
Lemma 34. [28, Exercise 4.7] If X ∼ Poi(λ) or X ∼ B(n, nλ ), then for any δ > 0, we have
λ

2
eδ
≤ e−δ λ/3 ∨ e−δλ/3
P(X ≥ (1 + δ)λ) ≤
1+δ
(1 + δ)

λ
2
e−δ
P(X ≤ (1 − δ)λ) ≤
≤ e−δ λ/2 .
(1 − δ)1−δ

(209)
(210)

23

The following lemma presents the Hoeffding bound.
Lemma 35. [29] Let XP
1 , X2 , . . . , Xn be independent random variables such that Xi takes its value in [ai , bi ] almost surely
n
for all i ≤ n. Let Sn = i=1 Xi , we have for any t > 0,


2t2
P {|Sn − E[Sn ]| ≥ t} ≤ 2 exp − Pn
.
(211)
2
i=1 (bi − ai )
A PPENDIX B
P ROOFS OF MAIN LEMMAS

A. Proof of Lemma 1
The following upper bound is straightforward:
p
E|q̂ − q|2
r
q
.
=
n

E|q̂ − q| ≤

(212)
(213)

Regarding the other upper bound and the lower bound, we utilize the exact analytic expression [30] for E|X − λ| for
X ∼ Poi(λ). It follows from [30] that for random variable X ∼ Poi(λ),
E|X − λ| = 2λ

e−λ λ[λ]
,
[λ]!

(214)

where [λ] denotes the greatest integer less than or equal to λ.
When 0 < λ ≤ 1, we have
which implies that if 0 < q ≤

1
n,

E|X − λ| = 2λe−λ ,

E|q̂ − q| = 2qe−nq
∈ [2qe

−1

, 2q].

Regarding the final lower bound, it suffices to show that for X ∼ Poi(λ), λ ≥ 1, we have
r
λ
.
E|X − λ| ≥
2
Hence, it suffices to show
√
λ[λ]
2 2λe−λ
≥1
[λ]!
for all λ ≥ 1. It is equivalent to

√
λn
2 2λe−λ
≥1
n!

(215)

(216)
(217)

(218)

(219)

(220)

for λ ∈ [n, n + 1) for all
n ≥ 1.
√ the integers
n
Since the function 2 2λe−λ λn! is monotonically increasing for λ ∈ [n, n + 1/2], and monotonically decreasing for λ ∈
[n + 1/2, n + 1), it suffices to consider integers λ. Hence, it suffices to show for any integer n ≥ 1,
√
nn
≥1
(221)
2 2ne−n
n!
n
p
(n + 1)
2 2(n + 1)e−n−1
≥ 1,
(222)
n!
which is equivalent to
√  n n
n! ≤ 8n
.
(223)
e
It follows from [31] that for any positive integer n,
 n n
√
1 √
,
(224)
n! < 2πe 12n n
e
√
√
1
which implies (223) since 2πe 12n < 8 for all positive integers.

24

B. Proof of Lemma 2
We first assume q ≥ p. Applying the relation
x = (x)+ − (x)−

(225)

|x| = (x)+ + (x)−

(226)
(227)

where (x)+ = max{x, 0}, (x)− = − min{x, 0}, we have
|E|q̂ − p| − |q − p|| = |E|q̂ − p| − (q − p)|
= |E(q̂ − p) − (q − p) + 2E(q̂ − p)− |
= 2E(q̂ − p)− .

(228)
(229)
(230)

Construct random variable p̂ such that np̂ ∼ Poi(np) is on the same probability space as q̂, with the relationship nq̂ = np̂ + Z,
where Z is independent of p̂ and Z ∼ Poi(n(q − p)). Hence, q̂ ≥ p̂ with probability one. We have
2E(q̂ − p)− ≤ 2E(p̂ − p)−
= E|p̂ − p| − E(p̂ − p)

(231)
(232)

= E|p̂ − p|
r r 

q
p
≤ 2 · min p, q,
,
,
n
n

(233)
(234)

where we applied Lemma 1 in the last step. The case of q ≤ p can be proved analogously.
Regarding the lower bound, we have
sup |E|q̂ − p| − |q − p|| ≥ E|p̂ − p|

(235)

q≥0

1
≥√
2

r 

p
p∧
,
n

(236)

where we lower bound via taking q = p and using Lemma 1.
C. Proof of Lemma 3
For nq̂ ∼ Poi(nq),

2

Var(|q̂ − p|) = inf E (|q̂ − p| − a)

(237)

a

2

≤ E (|q̂ − p| − |q − p|)
2

≤ E|q̂ − q|
q
= ,
n

(238)
(239)
(240)

where we used the fact that ||a| − |b|| ≤ |a − b|.
D. Proof of Lemma 4
We first consider the case of q ≤

c1 ln n
n .

In this case,



2c1 ln n
P(q̂ ∈
/ U (q; c1 )) = P q̂ >
n
= P(Poi(nq) > 2c1 ln n)

(241)
(242)

≤ P(Poi(c1 ln n) > 2c1 ln n)

(243)

≤e

(244)

−

=n

c1 ln n
3

−

c1
3

,

(245)

25

where we used Lemma 34 in the last step. When q >
r

c1 ln n
n ,

we have
!

!
r
c1 q ln n
c1 q ln n
+ P q̂ < q −
P(q̂ ∈
/ U (q; c1 )) ≤ P q̂ > q +
n
n
p
p
= P(Poi(nq) > nq + c1 qn ln n) + P(Poi(nq) < nq − c1 qn ln n)
≤e
≤

−

c1 ln n nq
nq
3

+e

−

c1 ln n nq
nq
2

2
,
nc1 /3

(246)
(247)
(248)
(249)

where we applied Lemma 34 again.
E. Proof of Lemma 5
Since
P(E c ) = P(E1c ∪ E2c ∪ E3c )
≤ P(E1c ) + P(E2c ) + P(E3c ),

(250)
(251)

it suffices to control P(Eic ), i = 1, 2, 3 separately. We have
P(E1c )

=P

S
[

i=1

!

{p̂i,1 > U1 (qi ), pi < qi }

(252)

≤ SP (p̂i,1 > U1 (qi ), pi < qi )

(253)

≤ SP (Poi(nqi ) > n · U1 (qi )) .

Note that if qi ≤

c1 ln n
n ,

(254)

then it follows from Lemma 34 that
P (Poi(nqi ) > n · U1 (qi )) ≤ P (Poi(c1 ln n) > (c1 + c3 ) ln n)
≤e

If qi >

c1 ln n
n ,

c2
− 3c3
1

ln n

.

(255)
(256)

then it follows from Lemma 34 that


p
P (Poi(nqi ) > n · U1 (qi )) ≤ P Poi(nqi ) > nqi + c3 qn ln n
≤e

c ln n
− 33

(257)

.

(258)

S
.
nβ

(259)

Hence,
P(E1c ) ≤
Analogously, P(p̂i,1 < U1 (qi ), pi > qi ) = 0 when qi ≤

c1 ln n
n ,

and when qi >

P(p̂i,1 < U1 (qi ), pi > qi ) ≤ P(Poi(nqi ) ≤ nqi −
≤e

−

c3 ln n
2

.

c1 ln n
n ,

p
c3 qi n ln n)

(260)
(261)

Hence,
P(E2c ) ≤
As for P(E3c ), when qi ≤

S
.
nβ

(262)

c1 ln n
n ,

P(p̂i,1 ∈ U1 (qi ), pi ∈
/ U (qi ; c1 )) ≤ P(Poi(2c1 ln n) ≤ (c1 + c3 ) ln n)
≤e
When qi >

(c −c )2
− 14c 3
1

ln n

.

(263)
(264)

c1 ln n
n ,

P(p̂i,1 ∈ U1 (qi ), pi > U (qi ; c1 )) ≤ P(Poi(nqi +
≤e
≤e

−



p
p
c1 qi n ln n) ≤ nqi + c3 qi n ln n)

√
√
√
( c1 − c3 ) qi n ln n
nqi +

√

c1 qi n ln n

√
√
( c1 − c3 )2 ln n
−
4

.

2

1
2 (nqi +

√

c1 qi n ln n)

(265)
(266)
(267)

26

P(p̂i,1 ∈ U1 (qi ), pi < U (qi ; c1 )) ≤ P(Poi(nqi −
≤e

√
√
√
( c1 − c3 ) qi n ln n
−
3

≤ e−
≤e

p
p
c1 qi n ln n) ≥ nqi − c3 qi n ln n)

c1 −

√
c1 c3
3

ln n

√
√
( c1 − c3 )2
−
3

∨e

ln n

∨e

−

√
√
( c1 − c3 )2 nqi ln n
3(nqi −

√
√
( c1 − c3 )2
−
3

√

c1 nqi ln n)

ln n

.

(268)
(269)
(270)
(271)

Consequently,
S
.
nβ

P(E3c ) ≤

(272)

F. Proof of Lemma 6
To simplify the notation we denote ∆ = c1 nln n . We split the proof into two cases: q ≤ ∆ and q > ∆.
1) The case q ≤ ∆, p ∈ U (q; c1 ) = [0, 2∆]. In this case, it follows from (32) that PK (x; q) is the best approximation
x
polynomial of function |x − q| over x ∈ [0, 2∆]. Define y = 2∆
and introduce function
g(y) = |2y∆ − q|, y ∈ [0, 1].

(273)

Define the best approximation polynomial of g(y) ∈ C[0, 1] with order K as
HK (y) = argmin max |g(y) − P (y)|.
P ∈polyK y∈[0,1]

It follows from Lemma 21 and 24 that there exists a universal constant M > 0 such that
√ 

q∆
.
sup |HK (y) − g(y)| ≤ M q ∧
K
y∈[0,1]
It implies that there exists another universal constant M1 > 0 such that
√ 

q∆
sup |HK (y)| ≤ max |g(y)| + M q ∧
K
y∈[0,1]
y∈[0,1]
≤ M1 ∆.

Denoting HK (y) =

PK

j=0

(274)

(275)

(276)
(277)

aj y j and using x = 2∆y, we know
PK (x; q) =

K
X

aj (2∆)−j xj

(278)

j=0

√ 

q∆
q∧
K
r
1 q ln n
.q∧
.
K
n

sup |PK (x; q) − |x − q|| ≤ M

x∈[0,2∆]

It follows from Lemma 30 that

Qj−1

k=0

k
n

(279)
(280)

is the unique unbiased estimator of pj when np̂ ∼ Poi(np). Hence,

j−1
K
Y
X
k
aj (2∆)−j
p̂ −
P̃K (p̂; q) =
,
(281)
n
j=0
p̂ −



k=0

and EP̃K (p̂; q) = P
PK (p; q).
K
Since HK (z 2 ) = j=0 aj z 2j is a polynomial with degree no more than 2K and satisfies
sup |HK (z 2 )| ≤ M1 ∆,

(282)

z∈[−1,1]

It follows from Lemma 29 that for all 0 ≤ j ≤ K,
|aj | ≤ M1 ∆

√

2+1

2K

.

(283)

27

Now we prove the variance properties of P̃K (p̂; q). We have



j−1
K
Y
X
k

Var(P̃K (p̂; q)) = Var 
aj (2∆)−j
p̂ −
n
j=0
k=0


!!1/2 2
j−1
K
Y
X
k

p̂ −
≤
|aj |(2∆)−j Var
n
j=0
k=0



j/2 2
K
X
2M
p

≤ max |aj |2  (2∆)−j
0≤j≤K
n
j=1


j/2 2
K 
X
2M
p

= max |aj |2 
2n
0≤j≤K
4∆
j=1

2
K 
j/2
X
p

≤ max |aj |2 
0≤j≤K
∆
j=1


r j 2
K−1
X
p 
p
= max |aj |2 
,
0≤j≤K
∆ j=0
∆

(284)

(285)

(286)

(287)

(288)

(289)

where we have applied Lemma 30 with M = max{2n∆, K} = 2n∆ since we have assumed c2 < c1 , K = c2 ln n.
Since p ≤ 2∆, we have
2

K−1
X
p
Var(P̃K (p̂; q)) ≤ max |aj |2 
2j/2 
(290)
0≤j≤K
∆ j=0

p K
B
(291)
∆
ln n
. BK
(p + q).
(292)
n
2) The case q > ∆.
√ In this case,
√ it follows from (32) that PK (x; q) is the best approximation polynomial of function |x − q|
over x ∈ [q − q∆, q + q∆]. Denote the best approximation polynomial of |y| on [−1, 1] with order K as
. ∆2

RK (y) =

K
X

rj y j .

(293)

j=0

√
Using x = q + y q∆, we have
PK (x; q) =

K
X
j=0

p
rj ( q∆)−j+1 (x − q)j .

(294)

It is well known that [26, Chap. 9, Thm. 3.3] there exists a universal constant M3 such that
|RK (y) − |y|| ≤

Consequently, for p ∈ [q −

√
√
q∆, q + q∆],

M3
, ∀y ∈ [−1, 1].
K

r
√
1 q ln n
M3 q∆
.
.
|PK (p; q) − |p − q|| ≤
K
K
n
It follows from Lemma 30 that gj,q (p̂), np̂ ∼ Poi(np) defined as

j  
k−1
X
Y
j
h
j−k
(−q)
gj,q (p̂) ,
p̂ −
n
k
k=0

h=0

(295)

(296)

(297)

28

is the unique unbiased estimator for (p − q)j , j ≥ 0, j ∈ N. Hence,
P̃K (p̂; q) =

K
X
j=0

p
rj ( q∆)−j+1 gj,q (p̂).

(298)

It was shown in Cai and Low [12, Lemma 2] that |rj | ≤ 23K , 0 ≤ j ≤ K. We study the variance properties of P̃K (p̂; q)
as follows.
2
}. Note that if p = 0 the variance of this P̃K (p̂; q) is zero. We now consider p 6= 0.
Define M4 , max{K, n(p−q)
p
Applying Lemma 30 and the fact that the standard deviation of a sum of random variables is upper bounded by the sum
of standard deviations of corresponding random variables, we have


K
X
p
rj ( q∆)−j+1 gj,q (p̂)
(299)
Var(P̃K (p̂; q)) = Var 
j=0



≤

K
X
j=0

2
p
|rj |( q∆)−j+1 Var1/2 (gj,q (p̂))



j/2 2
K p
X
2M
p
4

≤ 26K q∆  ( q∆)−j
n
j=0


j/2 2
K 
X
2M
p
4

≤ 26K q∆ 
nq∆
j=0
2
 K+1
c
−1
6K
≤ 2 q∆
c−1
c2
≤
(8c)2K q∆
(c − 1)2
ln n
q,
. BK
n


(300)

(301)

(302)

(303)
(304)
(305)

q
√ p
4p
where c = max{ 2, 2 c2 /c1 }. Recall that K = c2 ln n, ∆ = c1 nln n . It suffices to show 2M
nq∆ ≤ c to complete the
proof. Indeed, we have
s
s
r
r
r
√
2p
2K(q + q∆)
2K · 2q
4K
4c2
(306)
·K ≤
≤
≤
=
nq∆
nq∆
nq∆
n∆
c1
s
s
s
2p n(p − q)2
2(p − q)2
2q∆ √
(307)
·
=
≤
= 2.
nq∆
p
q∆
q∆
G. Proof of Lemma 9
It is clear that supx∈[0,1] |f (x; a)| ≤ 1. Introduce
fη (x; a) =
=

|η + (1 − η)x − a| − a
η + (1 − η)x
x−

a−η
a
1−η − 1−η
η
1−η + x

,

(308)

(309)

a
where η = D
, D > 1. We have EL [f (x; a); [η, 1]] = EL [fη (x; a); [0, 1]]. Recall the second-order Ditzian–Totik modulus of
smoothness given in (182)

ωϕ2 (f, t) = sup sup |∆2hϕ f (x)|,
0<h≤t x

p
where ϕ = x(1 − x), ∆2hϕ f (x) = f (x + hϕ) + f (x − hϕ) − 2f (x).
We deal with the two cases separately.

(310)

29

1)

1
L2

≤ a ≤ 21 : Denote δ =

which ensures that

Since

a−η
1−η

1
DL ϕ



a−η
1−η



. It is easy to verify that if

1
L2

≤ a ≤ 21 , D ≥ 3, then

1
1+(DL)2

± δ ∈ [0, 1]. We lower bound ωϕ2 (f, t) for fη as follows:


a−η
2
−1
2
ωϕ (fη , (DL) ) ≥ ∆ϕ/(DL) fη
.
1−η
∆2ϕ/(DL) fη



a−η
1−η



=

≤

a−η
1−η

≤

(DL)2
1+(DL2 ) ,

(311)

2δ
a ,
δ + 1−η

(312)

we have
ωϕ2 (fη , (DL)−1 ) ≥

2δ
a .
δ + 1−η

(313)

The relationship between ωϕ2 (f, n1 ) and En [f ; [0, 1]] was shown in [25, Thm. 7.2.4.] that there exists a universal positive
constant M2 such that
n
1
1 X
(k + 1)Ek [fη ; [0, 1]] ≥ M2 ωϕ2 (fη , ).
n2
n

(314)

k=0

Utilizing the non-increasing property of En [fη ; [0, 1]] with respect to n yields
EL [fη ; [0, 1]] ≥
&

DL
X
1
Ek [fη ; [0, 1]]
DL − L

(315)

k=L+1

DL
X
1
(k + 1)Ek [fη ; [0, 1]]
(DL)2

(316)

k=L+1

≥

M2 ωϕ2 (fη ,

L
1
1 X
)−
(k + 1)Ek [fη ; [0, 1]].
DL
(DL)2

(317)

k=0

Now we work out an upper bound on Ek [fη ; [0, 1]]. It follows from Lemma 21 that there exists a universal constant M1
such that
1
(318)
Ek [fη ; [0, 1]] ≤ M1 ωϕ1 (fη , ),
k
where ωϕ1 (f, t) = sup0<h≤t supx |∆1hϕ f (x)|, where ∆1hϕ f (x) = f (x + hϕ/2) − f (x − hϕ/2). It follows from straight1
forward algebra that ωϕ1 (fη , k1 ) . k√
. Hence,
a
L
L
1 X
1 X 1
√
(k
+
1)E
[f
;
[0,
1]]
.
k η
(DL)2
D 2 L2
a
k=0

.


1
1
a
ϕ a−η
Since δ = DL
1−η , η = D , L2 ≤ a ≤
constants M3 > 0, M4 > 0 such that

1
2,

√
a
DL

≤ a for a ≥

1
√ .
D2 L a

for D large enough, we know δ &
√

EL [fη ; [0, 1]] & M3

where we used the fact that

(319)

k=0

=

1
D

&

1
D

1
L2 , D

a

√ DL
a
DL +

− M4

1
√
D2 L a

(320)
√
a
DL

a
!
√
1
1
a
√
√
M3
− M4
L a +a
DL a
DL


√
1
a 1
√
M3
− M4
,
L 2a
DL a

and there exist two universal

(321)
(322)
(323)

≥ 1. Hence,



√
M4
1 M3
−
L a · EL [fη ; [0, 1]] &
D
2
D
≥ d1 > 0

(324)
(325)

30

when D is large enough.
2) 0 < a < L12 : for D > 1 we have
ωϕ2 (fη , (DL)−1 )
where ǫ = min
Since

n

1
DL ϕ



a−η
1−η



≥

∆2ǫ fη



o
, a−η
1−η .
∆2ǫ fη







a−η
1−η

= 1 + fη
≥ 0,



a−η
1−η



a−η
+ǫ
1−η

,

(326)



(327)
(328)



2
−1
). Note that the function fη (·) is a non-decreasing
it suffices to lower bound fη a−η
1−η + ǫ to lower bound ωϕ (fη , (DL)
function.


√
a
1
We have DL
ϕ a−η
1−η & DL for D large enough, and


a−η a−η
2D − 2
1 + fη
=
+
(329)
1−η
1−η
2D − 1



√
1
a−η
a
a−η
& √
+
ϕ
(330)
1 + fη
1−η
DL
1−η
a + DLa
1/L
&
(331)
1/L + D/L
1
,
(332)
=
1+D

where we used the fact that the function
Hence, we have shown that

√

√
x
x+DLx

is a non-increasing function for x ≥ 0.

ωϕ2 (fη , (DL)−1 )

& min

Following (317), we have that
EL [fη ; [0, 1]] ≥ M2 ωϕ2 (fη ,
&



1
2D − 2
,
2D − 1 D + 1



.

(333)

L
1
1 X
)−
(k + 1)Ek [fη ; [0, 1]]
DL
(DL)2

(334)

k=0

L
1 X
1
−
(k + 1)
D (DL)2

(335)

k=0

1
1
−
D D2
≥ d1 > 0,
&

(336)
(337)

when D is large enough. Here we used the fact that Ek [fη ; [0, 1]] ≤ 1.
H. Proof of Lemma 11
We have
V (F0 , F1 ) =
For each j ≥ 0, j ∈ Z, we introduce function

∞

1X 1
E[e−U0 U0j − e−U1 U1j ] .
2 j=0 j!

(338)

fj (x) = e−(a+Mx) (a + M x)j ,

where x ∈ [−1, 1]. We introduce a + M Xi = Ui , i = 0, 1. It follows from the assumptions that
We write the series expansion of fj (x) as follows:
fj (x) = fj (0) +

(k)
∞
X
fj (0)
k=1

k!

xk .

(339)
E[X0j ]

=

E[X1j ], 0

≤ j ≤ L.
(340)

31

Hence,
∞

1X 1
V (F0 , F1 ) =
2 j=0 j!
≤
=

X fj(k) (0)
E(X0k − X1k )
k!

(341)

k≥L+1

(k)
∞
1 X X 2 fj (0)
2 j=0
j!
k!

(342)

k≥L+1

(k)
∞
1 X 2 X fj (0)
,
2
k! j=0
j!

(343)

k≥L+1

where we used the fact that Xi ∈ [−1, 1], i = 0, 1.
It follows from the Leibniz formula for derivatives of products of functions that
k  
X
k
(k)
−a
(e−Mx )(k−m) ((a + M x)j )(m)
fj (x) = e
m
m=0
k∧j  
X
j!
k
(−M )k−m e−Mx
= e−a
M m (a + M x)j−m
m
(j
−
m)!
m=0
k∧j  
X
j!
k
−(a+Mx)
k
(−1)k−m
=e
M
(a + M x)j−m
m
(j
−
m)!
m=0
k∧j  
X
j!
k
−(a+Mx)
k
j−k
(a + M x)k−m .
(−1)k−m
=e
M (a + M x)
(j
−
m)!
m
m=0

(344)

(345)

(346)

(347)

Hence,

(k)

fj (0)
aj
= e−a
j!
j!

M
a

k X
k∧j  
j!
k
(−1)k−m
ak−m .
m
(j
−
m)!
m=0

k

P(Z = j)



Construct random variable Z ∼ Poi(a). Then,
(k)

fj (0)
=
j!
where (j)m = j(j − 1) · · · (j − m + 1).
Consequently,

Introducing np̂ = Z, p =

a
n,



M
a

k  
X
k
(−a)k−m (j)m ,
m
m=0

 k
(k)
∞
k  
X
X
fj (0)
k
M
(−a)k−m (Z)m .
≤
E
m
j!
a
m=0
j=0

(348)

(349)

(350)

we have
k
k−m

(k)
k  
∞
X
X
fj (0)
(Z)m
k
−a
Mn
E
≤
j!
a
n
nm
m
m=0
j=0

k
Mn
=
E gk,a/n (p̂) ,
a

where gk,q (p̂) is the unique unbiased estimator for (p − q)k when np̂ ∼ Poi(np) introduced in Lemma 30.

(351)

(352)

32

It follows from Lemma 30 that
k q

(k)
∞
X
fj (0)
Mn
E(gk,a/n (p̂))2
≤
j!
a
j=0
 k r k
p k!
M
≤
p
nk
 k r k k
p k
M
≤
p
nk
 √ k
M pk
√
≤
p
n
r !k
k
.
= M
a
Hence, it follows from k! ≥

kk
ek

(353)

(354)
(355)
(356)
(357)

that
r !k
k
M
V (F0 , F1 ) ≤
a
k≥L+1
r !k
X 1
k
eM
≤
kk
a
k≥L+1
X  eM k
√
≤
ka
k≥L+1
!k
X
eM
p
≤
.
a(L + 1)
k≥L+1
X

It follows from the assumptions that

1
k!

(358)

(359)

(360)

(361)

eM
1
p
≤ .
2
a(L + 1)

Consequently,
V (F0 , F1 ) ≤
≤2
I. Proof of Lemma 12

eM
p
a(L + 1)

!L+1

eM
p
a(L + 1)

!L+1

1−
.

(362)

eM
p
a(L + 1)

!!−1

We define the minimax risk under the multinomial sampling model for a fixed Q as

2
R(S, n, Q) = inf sup EP L̂ − L1 (P, Q) .

(363)

(364)

(365)

L̂ P ∈MS

Fix δ > 0. Let L̂ = L̂(X1 , X2 , . . . , XS ) be a near-minimax estimator of L1 (P, Q) under the multinomial model for every
sample size n, which means that for every sample size n,

2
sup E L̂ − L1 (P, Q) < R(S, n, Q) + δ.
(366)
P ∈MS

Here the random vector (X1 , X2 , . . . , XS ) follows multinomial distribution parametrized by n, P , and the estimator L̂ obtains
the number of samples n from this random vector.
Now we consider P
the Poisson sampling
P model, where Xi ’s are mutually independent with marginal distributions Xi ∼
Poi(npi ). Let n′ = Si=1 Xi ∼ Poi(n Si=1 pi ). We use the estimator L̂(X1 , X2 , . . . , XS ) to estimate L1 (P, Q) under the

33

Poisson sampling model. For any P ∈ MS (ǫ) under the Poisson sampling model, we have
!
!
!2

2
P
P
EP L̂ − L1 (P, Q) ≤ EP L̂ − L1 PS
, Q + L 1 PS
, Q − L1 (P, Q)
i=1 pi
i=1 pi
!!2
!
!2
P
P
≤ 2EP L̂ − L1 PS
,Q
, Q − L1 (P, Q)
+ 2 L 1 PS
i=1 pi
i=1 pi
!!2
P
,Q
+ 2ǫ2 ,
≤ 2EP L̂ − L1 PS
p
i=1 i
PS
where we used the fact that (a + b)2 ≤ 2a2 + 2b2 for any a, b ∈ R, and the fact that if i=1 pi = A, then
!
S
X
P
L 1 PS
||pi /A − qi | − |pi − qi ||
, Q − L1 (P, Q) ≤
i=1 pi
i=1
≤

=

S
X

i=1
S
X
i=1

(367)

(368)

(369)

(370)

|pi /A − pi |

(371)

pi
|1 − A|
A

(372)

= |A − 1|
≤ ǫ.

(373)
(374)

Then,
EP




∞
2
X
L̂ − L1 (P, Q) ≤ 2
EP  L̂ − L1
m=0

≤2

∞
X

P
PS

i=1 pi

,Q

!

2



n′ = m P(n′ = m) + 2ǫ2

R(S, m, Q)P(n′ = m) + 2(δ + ǫ2 )

(375)

(376)

m=0

≤ 2 (1 · P(n′ ≤ n(1 − ǫ)/2) + R(S, n(1 − ǫ)/2, Q)P(n′ ≥ n(1 − ǫ)/2)) + 2(δ + ǫ2 )
′

2

≤ 2R(S, n(1 − ǫ)/2, Q) + 2P(n ≤ n(1 − ǫ)/2) + 2(δ + ǫ )

≤ 2R(S, n(1 − ǫ)/2, Q) + 2P(Poi(n(1 − ǫ)) ≤ n(1 − ǫ)/2) + 2(δ + ǫ2 )

≤ 2R(S, n(1 − ǫ)/2, Q) + 2e−n(1−ǫ)/8 + 2(δ + ǫ2 ),

(377)
(378)
(379)
(380)

′
where we used
 the fact that conditioned on n = m, (X1 , X2 , . . . , XS ) follows multinomial distribution parametrized by

m, PSP p , the monotonicity of R(S, m, Q) as a function of m, R(S, m, Q) ≤ 1, and Lemma 34.
i=1 i

2
Taking supremum of EP L̂ − L1 (P, Q) over MS (ǫ) and using the arbitrariness of δ, we have

RP (S, n, Q, ǫ) ≤ 2R(S, n(1 − ǫ)/2, Q) + 2e−n(1−ǫ)/8 + 2ǫ2 ,

(381)

which is equivalent to
1
RP (S, n, Q, ǫ) − e−n(1−ǫ)/8 − ǫ2 .
2
It follows from [7, Lemma 16] that R(S, n, Q) ≤ 2RP (S, n/2, Q, 0). Hence,
R(S, n(1 − ǫ)/2, Q) ≥

1
R(S, n(1 − ǫ)/2, Q)
2
1
1
1
≥ RP (S, n, Q, ǫ) − e−n(1−ǫ)/8 − ǫ2 .
4
2
2

RP (S, n(1 − ǫ)/4, Q, 0) ≥

(382)

(383)
(384)

J. Proof of Lemma 13
2

c1 ln n
It is clear that the square 0, 2c1nln n ⊂ U . Tosee how we obtained the whole
 expression of U , for any
 x >q n , we study

q
q
q
c1 x ln n
c1 x ln n
c1 x ln n
c1 x ln n
, where the other curve x +
the envelope of the parametrized extremal points x −
,x +
,x −
n
n
n
n
can be dealt with analogously.

34

For p = x −

q

c1 x ln n
,q
n

=x+

q

c1 x ln n
,
n

we have
p − q = −2

r

c1 x ln n
n

(385)

p + q = 2x.

(386)

Hence,
2c1 ln n
(p + q).
n
We have that for all points (p, q) ∈ ∪x∈[0,1] U (x; c1 ) × U (x; c1 ),
r
2c1 ln n √
|p − q| ≤
p+q
r n
2c1 ln n √
√
( p + q),
≤
n
√
√
√
where we used the inequality p + q ≤ p + q in the last step.
(p − q)2 =

(387)

(388)
(389)

K. Proof of Lemma 14
It follows from the union bound that
P(E c ) = P(E1c ∪ E2c ∪ E3c ∪ E4c )

(390)

≤ P(E1c ) + P(E2c ) + P(E3c ) + P(E4c ).

(391)

Hence, it suffices to analyze each P(Eic ), i = 1, 2, 3, 4.
1) Analysis of P(E1c ):
)!
(
r
S
[
p
(c1 + c3 ) ln n p
c
( p̂i,1 + q̂i,1 )
pi < qi , p̂i,1 − q̂i,1 >
P(E1 ) = P
n
i=1
!
r
S
X
p
(c1 + c3 ) ln n p
P pi < qi , p̂i,1 − q̂i,1 >
( p̂i,1 + q̂i,1 )
≤
n
i=1
!
r
S
X
p
p
(c1 + c3 ) ln n
P pi < qi , p̂i,1 − q̂i,1 >
=
n
i=1
!
r
S
X
p
p
(c1 + c3 ) ln n
.
P pi = qi , p̂i,1 − q̂i,1 >
≤
n
i=1

(392)

(393)

(394)

(395)

It follows from Lemma 13 that the set U (pi ; (c1 + c3 )/2) × U (pi ; (c1 + c3 )/2) ⊂ U1 . Hence,
P(E1c ) ≤
≤
=

S
X

i=1
S
X

i=1
S
X
i=1

P(pi = qi , (p̂i,1 , q̂i,1 ) ∈
/ U (pi ; (c1 + c3 )/2) × U (pi ; (c1 + c3 )/2))

(396)

(1 − P(pi = qi , (p̂i,1 , q̂i,1 ) ∈ U (pi ; (c1 + c3 )/2) × U (pi ; (c1 + c3 )/2)))

(397)

(1 − P(p̂i,1 ∈ U (pi ; (c1 + c3 )/2)P(qi = pi , q̂i,1 ∈ U (pi ; (c1 + c3 )/2))) .

(398)

It follows from Lemma 4 that

P(E1c )

≤S
≤


1− 1−

4S
n

c1 +c3
6

2
n

c1 +c3
6

2 !

(399)

.

2) Analysis of P(E2c ): following similar steps as in the analysis of P(E1c ), we have P(E2c ) ≤

(400)
4S

n

c1 +c3
6

.

35

3) Analysis of P(E3c ):
P(E3c )

S
[

(



2

c1 ln n
, p̂i,1 + q̂i,1 <
=P
n
i=1
!


S
[
2c1 ln n
c1 ln n
≤P
pi + qi >
, p̂i,1 + q̂i,1 <
n
n
i=1


S
X
2c1 ln n
c1 ln n
P pi + qi >
, p̂i,1 + q̂i,1 <
≤
n
n
i=1
2c1 ln n
(pi , qi ) ∈
/ 0,
n

)!

≤ SP (Poi(2c1 ln n) < c1 ln n)
1 2 2c1 ln n
2
≤ Se−( 2 )
=

S

,
nc1 /4
where we have used the fact that np̂i,1 + nq̂i,1 ∼ Poi(np + nq) and Lemma 34.
4) Analysis of P(E4c ):


S
S
X
X
c1 ln n
c1 ln n
P p̂i,1 + q̂i,1 >
P((pi , qi ) ∈
/ U, (p̂i,1 , q̂i,1 ) ∈ U1 ) +
, pi + qi <
P(E4c ) ≤
n
2n
i=1
i=1


S
X
c1 ln n
pi + qi
P p̂i,1 + q̂i,1 ≥
+
.
, p̂i,1 + q̂i,1 ≤
n
2
i=1

(401)

(402)
(403)
(404)
(405)
(406)

(407)

We have



S
X
c1 ln n
c1 ln n
, pi + qi <
P p̂i,1 + q̂i,1 >
n
2n
i=1




c1 ln n
≤ SP Poi
> c1 ln n
2
S
≤ c /6
n1

(408)



S
X
pi + qi
c1 ln n
, p̂i,1 + q̂i,1 ≤
P p̂i,1 + q̂i,1 ≥
n
2
i=1


S
X
2c1 ln n
pi + qi
P pi + qi ≥
≤
, p̂i,1 + q̂i,1 ≤
n
2
i=1


S
X
n(pi + qi )
, n(pi + qi ) ≥ 2c1 ln n
P Poi(npi + nqi ) ≤
≤
2
i=1

(410)

(409)

and

1 2c1 ln n

≤ Se− 4 2
S
≤ c /4 .
n1
It suffices to show that there exists some constant c > 0 such that


\
[

U (p; c) × U (q; c) U1 = ∅,
(p,q)∈U
/

(411)
(412)
(413)

(414)

36

where U (·; c) is defined in (24). Indeed, in this case it follows from Lemma 4 that
S
X
i=1

P((pi , qi ) ∈
/ U, (p̂i,1 , q̂i,1 ) ∈ U1 ) ≤
≤
=
≤
≤

S
X

i=1
S
X

i=1
S
X

i=1
S
X

P((p̂i,1 , q̂i,1 ) ∈
/ U (pi ; c) × U (qi ; c))

(415)

(1 − P((p̂i,1 , q̂i,1 ) ∈ U (pi ; c) × U (qi ; c)))

(416)

(1 − P(p̂i,1 ∈ U (pi ; c))P(q̂i,1 ∈ U (qi ; c)))

(417)

i=1

4S
.
nc/3


1− 1−

2
nc/3

2 !

(418)
(419)

q
√ √
Now we work to prove (414). Without loss of generality we assume (p, q) satisfies q − p ≥ 2c1nln n and the constant
c < c1 . Underqthis assumption we have q ≥ 2c1nln n . We will show that for any point (x, y) ∈ U (p; c) × U (q; c), we have
√
√
y − x ≥ (c1 +cn3 ) ln n , thereby proving (414).
n
If p ≤ c ln
n , we have for any (x, y) ∈ U (p; c) × U (q; c),
s
r
r
√
cq ln n
2c ln n
√
−
(420)
y− x≥ q−
n
n
r
r
2c1 ln n √
2c ln n
ln n
≥
− 2cc1
−
,
(421)
n
n
n
√
where in the second step we used the fact that the function x − ax, a > 0 is monotonically increasing when x ≥ a/4.
Hence, we need to guarantee that
r
q

√
√
√
ln n
√
y− x≥
2c1 − 2cc1 − 2c
(422)
n
r
ln n √
(423)
c1 + c3 ,
≥
n
which can be reduced to the quadratic inequality:
r 2 
r
r
2c
2c c3
c3
+
− 1 ≤ 0.
(424)
+ 1+2 1+
c1
c1
c1
c1
2

−c3 )
One can easily verify that c = (c132c
satisfies this inequality since 0 < c3 < c1 .
1
c ln n
Now we consider the case of p > n . Then, for any (x, y) ∈ U (p; c) × U (q; c),
s
s
r
r
√
cq ln n
cp ln n
√
− p+
y− x≥ q−
n
n
q
q
cq ln n
cp ln n
q−
−p−
n
n
r
= r
q
q
q − cq nln n + p + cp nln n
q
√
√ √
√
√
n √
( q − p)( q + p) − c ln
q)
n ( p+
r
r
=
q
q
q − cq nln n + p + cp nln n
r
√
√
√
√
q+ p
ln n
r
r
≥ ( 2c1 − c)
.
q
q
n
cq ln n
cp ln n
q−
+ p+
n
n

(425)

(426)

(427)

(428)

37

Further, since p >

c ln n
n ,

r

q−

q

√
√
q+ p
r

cq ln n
n

+

p+

q

cp ln n
n

√
√
q+ p
√
≥ √
q + 2p

(429)

q
√
√
p + 2c1nln n + p
q
≥ √
√
2p + p + 2c1nln n

(430)

2
,
≥ √
2+1

(431)

√
x+ p
√
x+ 2p

2x+a
is a monotonically increasing function of x when x ≥ 0, and the function (√2+1)x+a
q
√
√
is a monotonically decreasing function of x when a > 0, x > 0. To guarantee that y − x ≥ (c1 +cn3 ) ln n , we need

where we used the fact that

√
√  √
2
√
2c1 − c ≥ c1 + c3 ,
2+1

which is equivalent to

c≤
with the constraint that

c3
c1

<

√ 8
( 2+1)2

√
2c1 −

(432)

!2
√
2 + 1√
c1 + c3 ,
2

(433)

− 1 ≈ 0.373.

L. Proof of Lemma 15
(1)

We first analyze the bias. To simplify the notation we denote ∆ = c1 nln n . It follows from the definition of P̃K that for
2
(p, q) ∈ [0, 2∆] ,
 p
q 
(1)
− |p − q|,
(434)
,
EP̃K (p̂, q̂) − |p − q| = 2∆h2K
2∆ 2∆
where h2K (x, y) = uK (x, y)vK (x, y) − uK (0, 0)vK (0, 0), and uK (x, y) and vK (x, y) satisfy (128).
We
that there exists a universal constant M > 0 such that sup(x,y)∈[0,1]2 |uK (x, y)vK (x, y) − |x − y|| ≤
 first argue 

M

√

√
x+ y
K

+

1
K2

. Indeed,

√
√
√
√
√
√ √
√
|uK (x, y)vK (x, y) − |x − y|| = uK (x, y)vK (x, y) − uK (x, y)| x − y| + uK (x, y)| x − y| − ( x + y)| x − y|
(435)
√
√
√
√
√
√
≤ |uK (x, y)||vK (x, y) − | x − y|| + | x − y||uK (x, y) − x − y|
(436)
√
√
√
√
√
√
√
√
≤ |uK (x, y) − ( x + y)||vK (x, y) − | x − y|| + ( x + y)|vK (x, y) − | x − y||
√
√
√
√
+ | x − y||uK (x, y) − x − y|.
(437)
√
√
√
√
It follows from Lemma 21 and Lemma 23 that the best polynomial approximation error of ( x + y) and | x − y| over
1
. Hence,
the unit square are both of order K

√
√
x+ y
1
(438)
|uK (x, y)vK (x, y) − |x − y|| ≤ M
+ 2 ,
K
K
which implies that there exists another constant M > 0 such that
|uK (x, y)vK (x, y) − uK (0, 0)vK (0, 0) − |x − y|| ≤ M

√

x+
K

√

y

1
+ 2
K



,

(439)

38

Denote x =

p
2∆ , y

=

q
2∆ ,

we have
 p
q 
− |p − q|
,
2∆ 
2∆
p
p
q
q
= 2∆ h2K
−
,
−
2∆ 2∆
2∆ 2∆
= 2∆|h2K (x, y) − |x − y||

√
√
x+ y
1
+ 2
≤ 2∆M
K
K
r
r

p
q
1
1
= 2∆M
+
+
K
2∆
2∆ K
r
1 ln n √
1 ln n
√
( p + q) + 2
.
.
K
n
K n

(1)

EP̃K (p̂, q̂) − |p − q| = 2∆h2K

We now analyze the variance. Express the polynomial h2K (x, y) ∈ poly22K explicitly as
X
h2K (x, y) =
hij xi y j

(440)
(441)
(442)
(443)
(444)
(445)

(446)

0≤i≤2K,0≤j≤2K,i+j≥1

X

=

0≤i≤2K




X

0≤j≤2K,i+j≥1



hij y j  xi .

(447)

For any fixed value of y, h2K (x2 , y 2 ) is a polynomial of x with degree no more than 4K that is uniformly bounded by a
universal constant on [−1, 1]. It follows from Lemma 29 that for any fixed y ∈ [−1, 1],
X
√
(448)
|
hij y 2j | ≤ M ( 2 + 1)4K ,
0≤j≤2K

which, together with Lemma 29, implies that

(1)

Since P̃K is the unbiased estimator of 2∆h2K
(1)

P̃K (p̂, q̂) =

√
|hij | ≤ M ( 2 + 1)8K .

p
q
2∆ , 2∆ , we know
X
hij (2∆)1−i−j gi,0 (p̂)gj,0 (q̂),

(449)

(450)

0≤i,j≤2K,i+j≥1

where gj,q (p̂) is thepunbiased estimator for (p − q)j introduced in Lemma 30.
Denote kXk2 = E(X − EX)2 and M1 = 2K ∨ 2n∆. Using the triangle inequality of the norm k · k2 and Lemma 30, we
know
X
(1)
kP̃K (p̂, q̂)k2 ≤
|hij |(2∆)1−i−j kgi,0 (p̂)k2 kgj,0 (q̂)k2
(451)
0≤i,j≤2K,i+j≥1

≤

X

!i
!j
r
r
2M1 p
2M1 q
1
1
2∆
n
2∆
n
r
r
i 
j

p
q
2∆
2∆

√
M ( 2 + 1)8K (2∆)

0≤i,j≤2K,i+j≥1

√
ln n
. ( 2 + 1)8K
n

X

0≤i,j≤2K,i+j≥1

(452)

(453)

Since for any x ∈ [0, 1], y ∈ [0, 1],
X

0≤i,j≤2K,i+j≥1

xi y j ≤

2K
X

yj +

2K
X
i=1

j=1

xi + xy

≤ 2(2K) (x + y)

xi y j

(454)

0≤i,j≤2K−1

≤ y(2K) + x(2K) + xy(2K)2
2

X

(455)
(456)

39

we know
√
(ln n)3
(1)
kP̃K (p̂, q̂)k2 . ( 2 + 1)8K
n
r
1
. B K (p + q).
n

r

p
+
2∆

r

q
2∆



(457)
(458)

for some constant B > 0. Hence,
(1)

Var(P̃K (p̂, q̂)) . B K

p+q
.
n

(459)

M. Proof of Lemma 16
(2)

We first analyze the bias. It follows from the definition of P̃K that
K
i X
h
(2)
rj W −j+1 (p − q)j ,
E P̃K (p̂, q̂; x, y) =

(460)

j=0

q
q
where W = 8c1nln n (x + y) ∨ n1 .
Since (p + q) ∈ U , we know
r

2c1 ln n √
√
( p + q)
n
r
2c1 ln n √ √
2( p + q)
≤
r n
2c1 ln n √ p
≤
2 2(x + y)
n
≤ W,

|p − q| ≤

(461)
(462)
(463)

(464)
p
√
√
where we have used the fact that p + q ≤ 2(p + q) and the assumption that p + q ≤ 2(x + y).
1
Hence, it follows from the property that the best order-K polynomial approximation error of |t| over [−1, 1] is Θ( K
) [26,
Chap. 9, Thm. 3.3] that
K
X
j=0

rj W −j+1 (p − q)j − |p − q| .

W
K

1
.
K

(465)
r

ln n √
x + y.
n

(466)

Then we analyze the variance. It was shown in Cai and Low [12, Lemmap2] that |rj | ≤ 23K , 0 ≤ j ≤ K. Denote the
unbiased estimator of (p − q)j by Âj (p̂, q̂) and introduce the norm kXk2 = E(X − E[X])2 . It follows from the triangle
inequality of the norm kXk2 and the fact that constants have zero variance that
(2)

kP̃K k2 ≤

K
X
j=1

|rj |W −j+1 kÂj k2 .

(467)

It follows from Lemma 31 that
EÂ2j ≤


j
8j(p ∨ q)
2(p − q)2 ∨
.
n

(468)

Hence,
(2)
kP̃K k2

≤ 23K W
=2

3K

W

K
X
j=1

K
X
j=1

!j
p
√
8j(p ∨ q)
2|p − q|
√
∨
W
nW
Cj ,

(469)

(470)

40

where

p
√
8j(p ∨ q)
2|p − q|
√
∨
W
nW
√ q 2c ln n √
√
p
1
( p + q)
2
8K(p + q)
n
q
∨√ q
≤
√
√
8c1 ln n
x+y
n 8c1nln n x + y
n
r √
√
√
p+ q
c2 p + q
√
∨
≤ √ √
c1 x + y
2 x+y
r
√
2c2
≤ 2∨
c1
√
≤ 2.

C=

(471)

(472)

(473)
(474)
(475)

Consequently,
(2)
kP̃K k2

≤2
r
.

where B is some universal constant.

r

√
8c1 ln n √
x + yK( 2)K
n
x
+
y
BK
,
n

3K

N. Proof of Lemma 17
We consider two different parameter settings.
1) S ≪ n . S ln S: In this case, we construct the distribution P as 2


c ln n c ln n
c ln n
P =
,
,...,
, 0, . . . , 0 ,
n
n
n

(476)
(477)

(478)

n
where c > 2c1 is a constant that will be chosen later, and Q = P . Without loss of generality we assume c ln
n is an
n
integer. We now argue that for each index 1 ≤ i ≤ c ln n ,
√
ln n
|Eg(p̂i , q̂i ) − |pi − qi || &
.
(479)
n

2
2
1
It follows from Lemma 34 that P p̂i ≤ 2c1nln n ≤ e− 2 (1−2c1 /c) c ln n= n−β , where β = 2c 1 − 2cc1 . Note that β can
be made arbitrarily large by taking the constant c large. Define E = p̂i ≥ 2c1nln n , q̂i ≥ 2c1nln n . We have

Eg(p̂i , q̂i ) = E (g 1(E) + g 1(E c ))
= E (|p̂i − q̂i |1(E)) + E (g 1(E c ))

(480)
(481)

= E|p̂i − q̂i | − E (|p̂i − q̂i |1(E c )) + E (g 1(E c ))
= E|p̂i − q̂i | + E ((g − |p̂i − q̂i |) 1(E c )) .

Since |g| ≤ B, we have
|E ((g − |p̂i − q̂i |) 1(E c ))| ≤ (B + 1)

2
.
nβ

(482)
(483)

(484)

It follows from the triangle inequality that
2(B + 1)
(485)
nβ
It follows from the conditional version of Jensen’s inequality that E|p̂i − q̂i | ≥ E|p̂i − pi |, and by Lemma 1 we have
r
pi
E|p̂i − q̂i | ≥
(486)
2n
r
c ln n
(487)
=
2
√ 2n
ln n
&
.
(488)
n
|Eg(p̂i , q̂i )| ≥ E|p̂i − q̂i | −

2 Technically,

the distribution P has support no more than S. However, a standard continuity argument implies that the same conclusion holds.

41

√
ln n
≫ 2(B+1)
for β
n
nβ
1
S
ln n ≫ n ln n since S ≪ n.

Since

> 1, we conclude that (479) is true. Hence, the total bias of L̂ is at least



2) n ≫ S ln S: In this case, we construct P, Q to be uniform distributions with support size S. Since S1 ≫
2
 q
1
=
from arguments analogous to those above that the squared bias of L̂ is at least the order S 2Sn

n
c ln n

√

ln n
n

2

=

ln n
n , it follows
S
S
2n ≫ n ln n .

O. Proof of Lemma 18
Since ||a| − |b|| ≤ |a − b|, it suffices to show that there exists a universal constant C > 0 such that
|QK (t)| ≤ CKt2

(489)
√
for |t| ≤ 1. Define x = |t|. Since QK (t) is even, it follows that QK (t) = R(t2 ), where R ∈ polyK is a polynomial. The
polynomial R satisfies the following:
R(0) = 0
√
1
max |R(x) − x| . .
K
x∈[0,1]

(490)
(491)

√
It suffices to show that |R(x)| ≤ CKx. Let T (x) ∈ polyK denote the best approximation polynomial√of the function x
1
on [0, 1] with order no more than K. It follows from Lemma 21 and Lemma 22 that supx∈[0,1] |T (x) − x| . K . It follows
from the triangle inequality that
√
√ 
sup |R(x) − T (x)| ≤ sup |R(x) − x| + |T (x) − x|
(492)
x∈[0,1]

x∈[0,1]

1
.
K
It follows from the Markov inequality (Lemma 25) that supx∈[0,1] |R′ (x) − T ′ (x)| . K. Since for any 0 ≤ x ≤ 1,
Z x
|R(x)| =
R′ (u)du
Z0 x
Z x
=
(R′ (u) − T ′ (u))du +
T ′ (u)du
0
0
Z x
≤ x sup |R′ (x) − T ′ (x)| +
T ′ (u)du
.

x∈[0,1]

(493)

(494)
(495)
(496)

0

Z

x

T ′ (u)du ,

(497)

p
sup | x(1 − x)T ′ (x)| . 1.

(498)

. Kx +

0

Rx
it suffices to show 0 T ′ (u)du . Kx.
It follows from Lemma 26 and Lemma 22 that

x∈[0,1]

Hence, it follows from Lemma 27 that

sup |T ′ (x)| .

x∈[0,1]

sup
x∈[1/K 2 ,1−1/K 2 ]

|T ′ (x)|

1
p
x(1 − x)
x∈[1/K 2 ,1−1/K 2 ]
. K.

.

sup

(499)
(500)
(501)

Hence,
Z

0

The proof is complete.

x

T ′ (u)du . Kx.

(502)

42

P. Proof of Lemma 19
We prove the lemma by contradiction. Assuming the contrary, then there exist universal constants c, C > 0 and polynomial
P (x, y) ∈ poly2K of degree K = c ln n such that
sup
(x,y)∈U ′

|P (x, y) − |x − y||
C
√
≤ √
x+y
n ln n

(503)

q
q
where U ′ = ∪x∈[ c1 ln n ,tn ] U (x; c1 ) ∪ U (x; c1 ). Now for any t ∈ [ c1 nln n , tn ], we have (t − 21 c1 tnln n , t + 21 c1 tnln n ) ∈ U ′ ,
n
and plugging in this pair yields
q
q
q
|P (t − 21 c1 tnln n , t + 21 c1 tnln n ) − c1 tnln n |
C
√
≤ √
sup
.
(504)
c ln n
2t
n ln n
t∈[ 1 n ,tn ]
q
q
Similarly, for (t + 12 c1 tnln n , t − 12 c1 tnln n ) ∈ U ′ we also have
q
q
q
|P (t + 21 c1 tnln n , t − 21 c1 tnln n ) − c1 tnln n |
C
√
sup
≤ √
.
(505)
c ln n
2t
n ln n
t∈[ 1 n ,tn ]
Now consider
1
Q(t) =
2

r

n
c1 ln n

1
P (t −
2

r

1
c1 t ln n
,t+
n
2

r

1
c1 t ln n
) + P (t +
n
2

r

1
c1 t ln n
,t−
n
2

r

!
c1 t ln n
)
n

(506)

it is easy to see that Q(t) is a polynomial of t, and deg Q ≤ 2K. Moreover, adding the previous two inequalities together, by
triangle inequality we obtain
r
√
2
|Q(t) − t|
C
1
√
sup
·
. .
(507)
≤
c1 ln n
K
c ln n
t
,tn ]
t∈[ 1
n

(ln n)
n

3

, we have ηn ,

c1 ln n
ntn

−1

1
K2 .

Define R(t) = tn 2 Q(tn · t) for t ∈ [ηn , 1], (507) becomes
√
√
t
,
∀t ∈ [ηn , 1].
(508)
|R(t) − t| .
K
√
Moreover, deg R ≤ 2K. Now let S be the best degree-2K approximating polynomial of t in the uniform norm on [ηn , 1],
using second-order Ditzian–Totik modulus of smoothness (Lemma 21) and ηn ≪ K12 we arrive at
√
1
(509)
sup |S(t) − t| . .
K
t∈[ηn ,1]
Since tn ≫

≪

Furthermore, following the proof of Lemma 18 we can prove that
sup |S ′ (t)| . K.

(510)

t∈[ηn ,1]

As a result, by triangle inequality we have
sup |R(t) − S(t)| ≤ sup |R(t) −

t∈[ηn ,1]

t∈[ηn ,1]

√
√
t| + sup |S(t) − t|

1
1
1
+
. .
K
K
K
Since R(t) − S(t) is also a polynomial of degree ≤ 2K, by Markov’s inequality (Lemma 25)
.

sup |R′ (t) − S ′ (t)| ≤

t∈[ηn ,1]

(511)

t∈[ηn ,1]

2
· 4K 2 sup |R(t) − S(t)| . K
1 − ηn
t∈[ηn ,1]

(512)

(513)

and finally by triangle inequality again
sup |R′ (t)| ≤ sup |R′ (t) − S ′ (t)| + sup |S ′ (t)| . K.

t∈[ηn ,1]

t∈[ηn ,1]

t∈[ηn ,1]

(514)

43

Now we are about to arrive at the desired contradiction. Choosing t = ηn and t = 2ηn in (508), we have




D √
D √
1−
ηn ≤ R(ηn ) ≤ 1 +
ηn ,
K
K




D p
D p
1−
2ηn ≤ R(2ηn ) ≤ 1 +
2ηn
K
K

with D > 0 a suitable universal constant appearing in the RHS of (508). As a result,




D p
D √
√
R(2ηn ) − R(ηn ) ≥ 1 −
2ηn − 1 +
ηn & ηn
K
K

(515)
(516)

(517)

and by the mean value theorem we conclude that there exists some ξ ∈ [tn , 2tn ] such that
R′ (ξ) =

1
R(2ηn ) − R(ηn )
& √ ≫K
2ηn − ηn
ηn

where the last inequality follows from the fact that ηn ≪
(514), and thus we are done.

1
K2 .

(518)

However, this inequality is contradicting to our previous result

Q. Proof of Lemma 20
We have
sup
P,Q∈MS

2

EP (L1 (g(Pn ), Q) − L1 (P, Q)) ≥ sup EP (L1 (g(Pn ), P ))

2

(519)

P ∈MS

≥



2
sup EP L1 (g(Pn ), P )

(520)

P ∈MS

S
,
(521)
n
where the last step follows from the result of minimax risk for estimating the discrete distribution P under ℓ1 loss in [32, Cor.
4].
&

A PPENDIX C
P ROOFS

OF AUXILIARY LEMMAS

A. Proof of Lemma 23
We split the analysis of |f (x + hϕ/2) − f (x − hϕ/2)| into two cases:
hϕ
1) x − hϕ
2 ≥ a or x + 2 ≤ a: in this case,
p
p
|f (x + hϕ/2) − f (x − hϕ/2)| = x + hϕ/2 − x − hϕ/2
hϕ
p
= p
x + hϕ/2 + x − hϕ/2
hϕ
≤ p
x + hϕ/2 + x − hϕ/2
√
h 1−x
√
=
2
t
≤ √ ,
2
√
√
√
where we have used the fact that x + y ≥ x + y and 0 < h ≤ t.
hϕ
2) x − hϕ
2 < a < x + 2 : in this case
p
p
√
|f (x + hϕ/2) − f (x − hϕ/2)| =
x + hϕ/2 + x − hϕ/2 − 2 a
p
p
√ √
≤ max{ x + hϕ/2 − a, a − x − hϕ/2}
p
p
≤ x + hϕ/2 − x − hϕ/2
t
≤√ .
2

(522)
(523)
(524)
(525)
(526)

(527)
(528)
(529)
(530)

44

B. Proof of Lemma 24
It follows from taking derivatives that for convex function f (x), the function f (x − t) − 2f (x) + f (x + t) is a nondecreasing
function of t. Since f (x) = |2x∆ − q| is a convex function, it follows from straightforward algebra that
ωϕ2 (f, K −1 ) = max{

max

2

1
K
z∈[ 1+K
2 , 1+K 2 ]

A2 (z), max2 A3 (z)},
A1 (z), max
1
z< 1+K 2

(531)

K
z> 1+K
2

where
A1 (z) = f

!
p
z(1 − z)
− 2f (z) + f
z−
K

!
p
z(1 − z)
z+
K

(532)

A2 (z) = f (0) − 2f (z) + f (2z)
A3 (z) = f (2z − 1) − 2f (z) + f (1).

(533)
(534)

We break the proof into three parts.
q
q
1
K2
1) We first prove that when 1+K
2 ≤ 2∆ ≤ 1+K 2 , the maximum of achieved by A1 (z) at z = 2∆ .
2
q
1
K
Consider first the case 1+K
2 ≤ z ≤ 1+K 2 and function A1 (z). If z > 2∆ , without loss of generality we can assume
√
z(1−z)
q
z−
< 2∆
, since otherwise A1 (z) = 0. Then,
K
!
!
p
p
z(1 − z)
z(1 − z)
− 2(2z∆ − q) + 2 z +
∆−q
(535)
A1 (z) = q − 2∆ (z −
K
K
!
p
z(1 − z)
q
= 4∆
.
(536)
−z+
K
2∆
2

q
K
1
Taking derivative with respect to z, it suffices to show this derivative is non-positive when 1+K
2 ≤ 2∆ ≤ 1+K 2 , z ≥
√
z(1−z)
q
q
< 2∆
. We have the derivative expressed as
2∆ , z −
K
!
!
p
1 − 2z − 2K z(1 − z)
1 − 2z
p
p
(537)
− 1 = 4∆
4∆
2K z(1 − z)
2K z(1 − z)
p
1
Since 1 − 2z − 2K z(1 − z) is a convex function, it achieves its maximum at the endpoints. When we set z = 1+K
2
q
and z = 1 it is both negative. Similar arguments work for the case of z < 2∆ . Hence, we conclude that when
q
1
K2
1+K 2 ≤ 2∆ ≤ 1+K 2 ,
p
2 q(2∆ − q)
max 2 A1 (z) =
.
(538)
K
1
K
2 ≤z≤
2
1+K

Consider the case z >
this case

2

K
1+K 2

1+K

and the function A3 (z). It suffices to assume 2z − 1 ≤

q
2∆

since otherwise A3 (z) = 0. In

A3 (z) = q − (2z − 1)2∆ − 2(2z∆ − q) + 2∆ − q

(539)

= 4∆ + 2q − 8z∆,

which is a decreasing function in z, implying maxz>
1
1+K 2

K2
1+K 2

A3 (z) ≤ max

1
1+K 2

(540)
2

K
≤z≤ 1+K
2

A1 (z). Similar arguments work

for the z <
and A2 (z) case.
q
q
1
2) We now prove that when 2∆
≤ 1+K
2 , the maximum is achieved by A2 (z) at 2∆ .
1
1
In this case, it suffices to consider z ≤ 1+K 2 . Indeed, if z > 1+K 2 , then the second order difference in the non-zero
1
1
case is given by (535), which is shown to be a decreasing function when z > 1+K
2 . Now consider z ≤ 1+K 2 . We
discuss three cases separately:
q
a) 2z ≤ 2∆
: in this case, A2 (z) = 0.
q
b) z ≤ 2∆ ≤ 2z: in this case,
A2 (z) = q − 2(q − 2z∆) + 4z∆ − q
= 8z∆ − 2q,

which is an increasing function of z. It implies that in this regime one should take z =
is 2q.

(541)
(542)
q
2∆ .

The resulting A2 (z)

45

c)

q
2∆

≤ z: in this case, the second order difference is
q − 2(2z∆ − q) + 4z∆ − q = 2q,

which is independent of z.
q
≤
Hence, we have shown that for 2∆

1
1+K 2 ,

(543)

the maximum is achieved by A2 (z) and
max A2 (z) = 2q.

(544)

1
z≤ 1+K
2

3) The case of 2∆ ≥

q
2∆

≥

K2
1+K 2

can be dealt with in a fashion similar to the case of

q
2∆

≤

1
1+K 2 ,

resulting in

max2 A3 (z) = 2(2∆ − q).

(545)

K
z≥ 1+K
2

C. Proof of Lemma 28
It suffices to show that for any polynomial Q ∈ poly2K ,

sup |Q(z) − f (z 2 )| ≥

z∈[−1,1]

sup |PK (z 2 ) − f (z 2 )|

(546)

z∈[−1,1]

= sup |PK (z 2 ) − f (z 2 )|

(547)

z∈[0,1]

Define
Q(z) + Q(−z)
2
Q(z) − Q(−z)
o(z) =
.
2
It is clear that e(z) is an even function, o(z) is an odd function, and Q(z) = e(z) + o(z). We have
e(z) =

sup |f (z 2 ) − Q(z)| =

z∈[−1,1]

sup |f (z 2 ) − e(z) − o(z)|

(548)
(549)

(550)

z∈[−1,1]

= sup max{|f (z 2 ) − e(z) − o(z)|, |f (z 2 ) − e(z) + o(z)|}

(551)


|f (z 2 ) − e(z) − o(z)| + |f (z 2 ) − e(z) + o(z)| /2

(552)

z∈[0,1]

≥ sup

z∈[0,1]

≥ sup

z∈[0,1]

(f (z 2 ) − e(z) − o(z)) + (f (z 2 ) − e(z) + o(z))
2

= sup |f (z 2 ) − e(z)|,

(553)
(554)

z∈[0,1]

where we have used the fact that max{a, b} ≥ a+b
2 and the convexity of the function |z|.
There exists another polynomial UK (z) ∈ polyK such that UK (z 2 ) = e(z). Hence, for any Q ∈ poly2K ,
sup |f (z 2 ) − Q(z)| ≥ sup |f (z 2 ) − UK (z 2 )|

z∈[−1,1]

(555)

z∈[0,1]

= sup |f (z) − UK (z)|

(556)

≥ sup |f (z) − PK (z)|

(557)

z∈[0,1]

z∈[0,1]

=

sup |f (z 2 ) − PK (z 2 )|

(558)

z∈[−1,1]

(559)
where we used the definition of PK (z). The proof is complete.
D. Proof of Lemma 30
The Charlier polynomial cn (x, a), a > 0 is defined as follows:
cn (x, a) =

n
X
r=0

(−1)n−r

 
n (x)r
,
r ar

(560)

46

where (x)r = x · (x − 1) · · · · · (x − r + 1) is the falling factorial. It satisfies the following generating function relation [33]:
x

∞
X
t
cn (x, a) n
, x ∈ N.
(561)
t = e−t 1 +
n!
a
n=0

Substituting t by at, we have

∞
X
an cn (x, a) n
x
t = e−at (1 + t) , x ∈ N.
n!
n=0

Note that we have

an cn (x, a) =

n
X

(−1)n−r

r=0

 
n n−r
a
(x)r ,
r

(562)

(563)

which is well defined even for a = 0. If a = 0, then an cn (x, a) may be defined as
an cn (x, a) , (x)n .

(564)

We note that relation (562) is true also when a = 0. Indeed, the case a = 0 reduces to the relation:
∞
X
(x)n n
t = (1 + t)x , x ∈ N.
n!
n=0

(565)

Assuming Y ∼ Poi(λ), replacing x with random variable Y in (562) and taking expectation on both sides, we have
∞
∞
n
X
X
(λ − a) n
Ean cn (Y, a) n
t = e−at E (1 + t)Y = et(λ−a) =
t
n!
n!
n=0
n=0

(566)

Note that Ean cn (Y, a) does not depend on t. Hence we know

n

Thus, if nX ∼ Poi(np), a = nq, we have

Ean cn (Y, a) = (λ − a) .

(567)

Eq j cj (nX, nq) = (p − q)j , j ≥ 0.

(568)

Expanding q j cj (nX, nq) implies that it is equal to gj,q (X) defined in Lemma 30. The estimator gj,q (X) being the unique
unbiased estimator of (p − q)j follows from the Lehmann–Scheffe Theorem [34, Chap. 2, Thm. 1.11] and the complete
sufficiency of X in model nX ∼ Poi(np)( [34, Chap. 1, Thm. 6.22]).
Now we proceed to bound the second moment of gj,q (X). It follows from (562) that for any a + b ≥ 0,

which implies that

∞
X
(a + b)n cn (x, a + b) n
t = e−(a+b)t (1 + t)x , x ∈ N,
n!
n=0

∞
∞
X
X
an cn (x, a) n
(a + b)n cn (x, a + b) n
t = e−bt
t
n!
n!
n=0
n=0


!
∞
∞
n
j
X
X
a
c
(x,
a)
(−bt)
n
n

=
t
j!
n!
n=0
j=0

=

∞ X
∞
X
an cn (x, a)(−b)j n+j
t
n!j!
j=0 n=0

(569)

(570)

(571)

(572)

It follows from coefficient matching that
n
n   k
X
(a + b)n cn (x, a + b) X ak ck (x, a)(−b)n−k
n a ck (x, a)(−b)n−k
=
=
,
n!
k!(n − k)!
n!
k
k=0

which simplifies to

(573)

k=0

j  
X
j
(−b)j−k ak ck (x, a).
(a + b) cj (x, a + b) =
k
j

k=0

(574)

47

Now assume nX ∼ Poi(np). Taking a + b = nq, a = np and dividing both sides by nj , we have
j  
j  
X
1 X j
j
j
j−k
k
q cj (nX, nq) = j
(n(p − q))
(np) ck (nX, np) =
(p − q)j−k pk ck (nX, np).
n
k
k
k=0

(575)

k=0

The Charlier polynomials are orthogonal with respect to the Poisson measure. Concretely, for Y ∼ Poi(λ) [33],
Ecn (Y, λ)cm (Y, λ) =

For nX ∼ Poi(np), we have

n!
δmn .
λn

2
pj j!
E pj cj (nX, np) = j ,
n

which is also true for p = 0.
Applying the orthogonal property of Charlier polynomials and assuming p > 0, we have
j  2
X
2
2
j
E q j cj (nX, nq) = E
(p − q)2(j−k) E pk ck (nX, np)
k
k=0


j
2
X
j
pk k!
=
(p − q)2(j−k) k
n
k
k=0


j
 p k
X j
1
(p − q)2(j−k)
= j!
k
n (j − k)!
k=0
j  
 p j−k 1
X
j
= j!
(p − q)2k
n
k!
k
k=0




j
k
 p j X
1
j
n(p − q)2
= j!
Assuming p > 0
n
p
k!
k
k=0


 p j
n(p − q)2
,
Lj −
= j!
n
p
where Lm (x) stands for the Laguerre polynomial with order m, which is defined as:
m  
X
m (−x)k
Lm (x) =
k
k!
k=0
n
o
2
If we further assume M ≥ max n(p−q)
, j , we have
p
j  
 p j X
2
j Mk
E q cj (nX, nq) ≤ j!
n
k k!
k=0
j  
 p j X
j Mj
≤ j!
n
k j!
k=0

j
2M p
=
.
n
j

(576)

(577)

(578)

(579)

(580)

(581)

(582)
(583)

(584)

(585)

(586)
(587)

E. Proof of Lemma 31
Qk−1
It follows from the fact that E i=0 (p̂ − ni ) = pk for np̂ ∼ Poi(nq) [24, Ex. 2.8] that Âj is unbiased for estimating (p − q)j .
It follows from the Lehmann–Scheffe Theorem [34, Chap. 2, Thm. 1.11] and the complete sufficiency of (p̂, q̂) ( [34, Chap.
1, Thm. 6.22]) that Âj is the unique unbiased estimator for (p − q)j .
We now work out a different form of Âj . It follows from the binomial theorem that for any fixed r > 0,
(p − q)j = (p − r − (q − r))j
k  
X
j
=
(p − r)k (−1)j−k (q − r)j−k .
k
k=0

(588)
(589)

48

Clearly, the following estimator is also unbiased for estimating (p − q)j :
j  
X
j
gk,r (p̂)(−1)j−k gj−k,r (q̂),
k

(590)

k=0

where gk,r (p̂) and gj−k,r (q̂) are the unique unbiased estimators for (p−r)k and (q−r)j−k introduced in Lemma 30, respectively.
It follows from the uniqueness of Âj that
j  
X
j
gk,r (p̂)(−1)j−k gj−k,r (q̂).
(591)
Âj =
k
k=0

2

1/2

Using kXk2 = (E[X ])

and the triangle inequality for the norm kXk2, we have
j  
X
j
kgk,r (p̂)gj−k,r (q̂)k2
kÂj k2 ≤
k
k=0
j  
X
j
=
kgk,r (p̂)k2 kgj−k,r (q̂)k2 ,
k

(592)

(593)

k=0

where we have used the independence of p̂ and q̂ in the last step.
2
2
8j(p∨q)
2
Define M1 = n(p−r)
∨ j, M2 = n(q−r)
∨ j, and set r = p+q
. It follows from Lemma 30
p
q
2 . Define M = 2(p − q) ∨
n
that
k/2 
(j−k)/2
j  
X
2M2 q
j
2M1 p
(594)
kÂj k2 ≤
n
n
k
k=0
!j
r
r
2M1 p
2M2 q
=
(595)
+
n
n
!j
r
r
(p − q)2 2jp
(p − q)2 2jq
(596)
∨
+
∨
=
2
n
2
n
= M j/2 .

(597)

F. Proof of Lemma 32
Equation (204) follows from [25, Lemma 9.5.5.]. Now we prove the bound on the magnitude of |hj,s |. Note that the moment
generating function of p̂ − p is given by
z/n

E[exp(z(p̂ − p))] = e−zp enp(e

−1)

Written as formal power series of z, the previous identity becomes
! ∞
∞
∞
X
X
E(p̂ − p)s s
(−p)i i X nk pk
z =
z
s!
i!
k!
s=0
i=0

(598)

∞
X
1 z l
( )
l! n
l=1

k=0

Hence, by comparing the coefficient of nj−s z s at both sides, we obtain

j
X
X
(−p)i  pj−i
hj,s pj
=
s!
i!
(j − i)!
i=0

!k 

j−i
Y

a1 +···+aj−i =s−i,a1 ,··· ,aj−i ≥1 l=1

Moreover,

X

j−i
Y

a1 +···+aj−i =s−i,a1 ,··· ,aj−i ≥1 l=1

1
≤
al ! a
≤

X

1 +···+aj−i =s−i

X

a1 +···+aj

j−i
Y

l=1

.


1 
.
al !

1
al !

j
Y
js
1
= .
al !
s!
=s
l=1

(599)

(600)

(601)

(602)

49

Then,
j
X
1
1
js
i!
(j
−
i)!
i=0
j  
js X j
=
j! i=0 i

|hj,s | ≤

(604)

2j j s
.
j!

(605)

2j j s
js
≤ 2s
j!
j!

(606)

=
Since 1 ≤ j ≤ s, we have

(603)

js
≤ 2s √
2πj(j/e)j
j s ej
≤ 2s j .
j

(607)
(608)

s x

Now we consider the maximization problem maxx≥0 xxxe . It follows from taking derivatives that this function attains it
unique maximum at point x∗ which satisfies the following:
x∗ ln x∗ = s.

(609)

Recall the Lambert W function is defined over [−1/e, ∞) by the equation W (z)eW (z) = z, we know that
x∗ = eW (s) .

(610)

The following upper bound on W (s) was proved in [35]: for any s > e,
e ln ln s
e − 1 ln s
1
,
≤ ln s − ln ln s +
e−1

W (s) ≤ ln s − ln ln s +

where we have used the fact that maxx>0
Hence, for any s ≥ 3,

ln x
x

(611)
(612)

= 1e .

|hj,s | ≤ (2e)s esW (s)

(613)

 s s
≤ (2ee/(e−1) )s
,
ln s
which turns out to be also correct for s = 2 since h1,2 = 1.

(614)

G. Proof of Lemma 33
It is clear that when p ≤
follows:

1
n,

the statement is true. It suffices to consider the case of p >

gn (p) =
It is evident that gn (p) ≤

1
pj

(

1
pj
j

n − jnj+1 p −

and
1
=
gn (p̂) −
(p̂ ∨ n1 )j

(

p≥

1
n


1

0≤p<

0

p̂ ≥

n

jnj

1
n

1
n.

Introduce function gn (p) as

.

1
n

p̂ = 0

(615)

(616)

We have


1
1
− gn (p̂) + |E [gn (p) − gn (p̂)]| + gn (p)
≤ E
E
(p̂ ∨ n1 )j
(p̂ ∨ n1 )j
1
≤ jnj e−np + j + |E [gn (p) − gn (p̂)]| .
p

(617)
(618)

50

Since the function gn (p) is continuously differentiable on (0, ∞), we have






E (gn (p) − gn (p̂))2 = E (gn (p) − gn (p̂))2 1(p̂ ≥ p/2) + E (gn (p) − gn (p̂))2 1(p̂ ≤ p/2)
≤ sup

|gn′ (ξ)|2 E(p

ξ≥p/2
2

≤

2

− p̂) +

sup |gn′ (ξ)|2 p2 P(p̂
ξ>0

≤ p/2)

j
p
+ j 2 n2j+2 p2 e−np/8 ,
(p/2)2j+2 n

(619)
(620)
(621)

where we applied Lemma 34 in the last step. Hence,
E

p
1
1
j −np
+ j + E(gn (p) − gn (p̂))2
1 j ≤ jn e
p
(p̂ ∨ n )
r
j
1
p
+ jnj+1 pe−np/16
≤ jnj e−np + j +
p
(p/2)j+1 n
1
j2j+1
≤ jnj e−np + j +
+ jnj+1 pe−np/16 ,
p
pj

where in the last step we used the the assumption that p ≥
E

1
n.

(622)
(623)
(624)

Consequently,

pj
≤ j(np)j e−np + 1 + j2j+1 + j(np)j+1 e−np/16
(p̂ ∨ n1 )j
 j
j+1

j
16(j + 1)
j+1
≤j
+ 1 + j2
+j
,
e
e

where we have used the fact that for any p ≥ 0,

(np)k e−cnp ≤



k
ec

k

.

(625)
(626)

(627)

R EFERENCES
[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
[9]
[10]
[11]
[12]
[13]
[14]
[15]
[16]
[17]
[18]
[19]
[20]
[21]
[22]
[23]
[24]
[25]
[26]

C. E. Shannon, “A mathematical theory of communication,” The Bell System Technical Journal, vol. 27, pp. 379–423, 623–656, 1948.
T. M. Cover and J. A. Thomas, Elements of Information Theory, 2nd ed. New York: Wiley, 2006.
E. L. Lehmann and J. P. Romano, Testing statistical hypotheses. Springer, 2005.
L. Devroye, L. Györfi, and G. Lugosi, “A probabilistic theory of pattern recognition,” 1996.
G. Valiant and P. Valiant, “The power of linear estimators,” in Foundations of Computer Science (FOCS), 2011 IEEE 52nd Annual Symposium on.
IEEE, 2011, pp. 403–412.
P. Valiant and G. Valiant, “Estimating the unseen: improved estimators for entropy and other properties,” in Advances in Neural Information Processing
Systems, 2013, pp. 2157–2165.
J. Jiao, K. Venkat, Y. Han, and T. Weissman, “Minimax estimation of functionals of discrete distributions,” Information Theory, IEEE Transactions on,
vol. 61, no. 5, pp. 2835–2885, 2015.
Y. Wu and P. Yang, “Minimax rates of entropy estimation on large alphabets via best polynomial approximation,” IEEE Transactions on Information
Theory, vol. 62, no. 6, pp. 3702–3720, 2016.
J. Acharya, A. Orlitsky, A. T. Suresh, and H. Tyagi, “Estimating Rényi entropy of discrete distributions,” IEEE Transactions on Information Theory,
vol. 63, no. 1, pp. 38–56, Jan 2017.
A. W. Van der Vaart, Asymptotic statistics. Cambridge university press, 2000, vol. 3.
O. Lepski, A. Nemirovski, and V. Spokoiny, “On estimation of the Lr norm of a regression function,” Probability theory and related fields, vol. 113,
no. 2, pp. 221–253, 1999.
T. T. Cai and M. G. Low, “Testing composite hypotheses, Hermite polynomials and optimal estimation of a nonsmooth functional,” The Annals of
Statistics, vol. 39, no. 2, pp. 1012–1041, 2011.
M. Vinck, F. P. Battaglia, V. B. Balakirsky, A. H. Vinck, and C. M. Pennartz, “Estimation of the entropy based on its polynomial representation,” Physical
Review E, vol. 85, no. 5, p. 051139, 2012.
Y. Wu and P. Yang, “Chebyshev polynomials, moment matching, and optimal estimation of the unseen,” arXiv preprint arXiv:1504.01227, 2015.
A. Orlitsky, A. T. Suresh, and Y. Wu, “Optimal prediction of the number of unseen species,” Proceedings of the National Academy of Sciences, p.
201607774, 2016.
Y. Wu and P. Yang, “Sample complexity of the distinct elements problem,” arXiv preprint arXiv:1612.03375, 2016.
Y. Han, J. Jiao, and T. Weissman, “Minimax rate-optimal estimation of divergences between discrete distributions,” arXiv preprint arXiv:1605.09124,
2016.
Y. Bu, S. Zou, Y. Liang, and V. V. Veeravalli, “Estimation of KL divergence: Optimal minimax rate,” arXiv preprint arXiv:1607.02653, 2016.
D. Berend and A. Kontorovich, “A sharp estimate of the binomial mean absolute deviation with applications,” Statistics & Probability Letters, vol. 83,
no. 4, pp. 1254–1259, 2013.
A. Tsybakov, “Aggregation and high-dimensional statistics,” Lecture notes for the course given at the École dété de Probabilités in Saint-Flour, URL
http://www. crest. fr/ckfinder/userfiles/files/Pageperso/ATsybakov/Lecture notes SFlour. pdf, vol. 16, p. 20, 2013.
——, Introduction to Nonparametric Estimation. Springer-Verlag, 2008.
S. Bernstein, “Sur la meilleure approximation de |x| par des polynomes de degrés donnés,” Acta Mathematica, vol. 37, no. 1, pp. 1–57, 1914.
H. N. Mhaskar, P. Nevai, and E. Shvarts, “Applications of classical approximation theory to periodic basis function networks and computational harmonic
analysis,” Bulletin of Mathematical Sciences, vol. 3, no. 3, pp. 485–549, 2013.
C. S. Withers, “Bias reduction by Taylor series,” Communications in Statistics-Theory and Methods, vol. 16, no. 8, pp. 2369–2383, 1987.
Z. Ditzian and V. Totik, Moduli of smoothness. Springer, 1987.
R. A. DeVore and G. G. Lorentz, Constructive approximation. Springer, 1993, vol. 303.

51

[27] R. Latala, “Estimation of moments of sums of independent real random variables,” The Annals of Probability, pp. 1502–1513, 1997.
[28] M. Mitzenmacher and E. Upfal, Probability and computing: Randomized algorithms and probabilistic analysis. Cambridge University Press, 2005.
[29] W. Hoeffding, “Probability inequalities for sums of bounded random variables,” Journal of the American statistical association, vol. 58, no. 301, pp.
13–30, 1963.
[30] P. Diaconis and S. Zabell, “Closed form summation for classical distributions: variations on a theme of de moivre,” Statistical Science, pp. 284–302,
1991.
[31] H. Robbins, “A remark on Stirling’s formula,” The American Mathematical Monthly, vol. 62, no. 1, pp. 26–29, 1955.
[32] Y. Han, J. Jiao, and T. Weissman, “Minimax estimation of discrete distributions under l1 loss,” IEEE Transactions on Information Theory, vol. 61,
no. 11, pp. 6343–6354, 2015.
[33] G. Peccati and M. S. Taqqu, “Some facts about Charlier polynomials,” in Wiener Chaos: Moments, Cumulants and Diagrams. Springer, 2011, pp.
171–175.
[34] E. L. Lehmann and G. Casella, Theory of point estimation. Springer, 1998, vol. 31.
[35] A. Hoorfar and M. Hassani, “Inequalities on the lambert W function and hyperpower function,” J. Inequal. Pure and Appl. Math, vol. 9, no. 2, pp. 5–9,
2008.

