text: 6 RW RR 10 000 40 000 5000 20 000 r r + + 0.2 0.4 0.6 0.8 1.0 0.2 0.4 0.6 0.8 1.0 -20 000 -5000 -40 000 -10 000 (a) (b) − FIG. 3: (a)Weinhold scalar curvature R vs. r for b = 1.5, Φ = 1, R = 12 (b)Ruppeiner scalar curvature R vs. r for − + 0 + b = 1.5, Φ = 1, R = 12; 0 − − 12b2π2Q2 4bπS√ R S2 gW = 0 , (24) SS √32π3/2S5/2 b b3√/2 π gW = , (25) QQ S √ − b3/2 πQ gW = gW = . (26) SQ QS 2S3/2 And Weinhold scalar curvature can be obtained via programming as (cid:2) (cid:3) √ − − − 8π3/2S3/2 b 96b3π3Q2 4b2π2(8 + Q2R )S 20bπR S2 3R2S3 RW = − − 0 0 0 , (27) (4b2π2Q2 4bπS R S2)3 0 which can be reexpressed into the function of Φ as − 8b5(4 + r2 R )(8 + 3r2 R ) + 32b3( 24 + r2 R )Φ2 RW = + 0 + 0 − + 0 . (28) r (4b2 + b2r2 R 4Φ2)3 + + 0 − Comparing Eq.(28) with Eq.(17), one may ﬁnd that Weinhold scalar curvature shares the same factor 4b2 +b2r2 R + 0 4Φ2 in the denominator as the speciﬁc heat does, implying it would diverge exactly where the speciﬁc heat diverges. This is also shown intuitively in Fig. 3(a). Since the Ruppeiner’s metric is conformally connected to the Weinhold’s metric through the map [25] dS2 dS2 = W . (29) R T it is convenient to derive the components of Ruppeiner’s metric from those of Weinhold’s metric. They can be calculated as ##LTFigure## ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: RW

text: RR

text: r

text: r

text: (a)

text: (b)

text: FIG.

text: (a)Weinhold

text: scalar

text: curvature

text: R

text: vs.

text: r

text: for

text: b

text: Φ

text: R

text: (b)Ruppeiner

text: scalar

text: curvature

text: R

text: vs.

text: r

text: for

text: b

text: Φ

text: R

text: R

text: gW

text: SS

text: b

text: π

text: gW

text: QQ

text: S

text: πQ

text: gW

text: gW

text: SQ

text: QS

text: And

text: Weinhold

text: scalar

text: curvature

text: can

text: be

text: obtained

text: via

text: programming

text: as

text: b

text: )S

text: RW

text: R

text: which

text: can

text: be

text: reexpressed

text: into

text: the

text: function

text: of

text: Φ

text: as

text: R

text: R

text: R

text: RW

text: r

text: R

text: Comparing

text: with

text: one

text: may

text: ﬁnd

text: that

text: Weinhold

text: scalar

text: curvature

text: shares

text: the

text: same

text: factor

text: R

text: in

text: the

text: denominator

text: as

text: the

text: speciﬁc

text: heat

text: does,

text: implying

text: it

text: would

text: diverge

text: exactly

text: where

text: the

text: speciﬁc

text: heat

text: diverges.

text: This

text: is

text: also

text: shown

text: intuitively

text: in

text: Fig.

text: Since

text: the

text: Ruppeiner’s

text: metric

text: is

text: conformally

text: connected

text: to

text: the

text: Weinhold’s

text: metric

text: through

text: the

text: map

text: W

text: R

text: T

text: it

text: is

text: convenient

text: to

text: derive

text: the

text: components

text: of

text: Ruppeiner’s

text: metric

text: from

text: those

text: of

text: Weinhold’s

text: metric.

text: They

text: can

text: be

text: calculated

text: as

text: ##LTFigure##

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 1 Minimax Rate-Optimal Estimation of Divergences between Discrete Distributions Yanjun Han, Student Member, IEEE, Jiantao Jiao, Student Member, IEEE, and Tsachy Weissman, Fellow, IEEE. Abstract We reﬁne the general methodology in [1] for the construction and analysis of essentially minimax estimators for a wide class of functionals of ﬁnite dimensional parameters, and elaborate on the case of discrete distributions with support size S comparable with the number of observations n. Speciﬁcally, we determine the “smooth” and “non-smooth” regimes based on the conﬁdence set and the smoothness of the functional. In the “non-smooth” regime, we apply an unbiased estimator for a suitable polynomial approximation of the functional. In the “smooth” regime, we construct a general version of the bias-corrected Maximum Likelihood Estimator (MLE) based on Taylor expansion. We apply the general methodology to the problem of estimating the KL divergence between two discrete probability measures P and Q from empirical data in a non-asymptotic and possibly large alphabet setting. We construct minimax rate-optimal estimators (cid:107) for D(P Q) when the likelihood ratio is upper bounded by a constant which may depend on the support size, and show that the performance of the optimal estimator with n samples is essentially that of the MLE with n ln n samples. Our estimator is adaptive in the sense that it does not require the knowledge of the support size nor the upper bound on the likelihood ratio. We show that the general methodology results in minimax rate-optimal estimators for other divergences as well, such as the Hellinger distance and the χ2-divergence. Our approach reﬁnes the Approximation methodology recently developed for the construction of near minimax estimators of functionals of high-dimensional parameters, such as entropy, Re´nyi entropy, mutual information and (cid:96) distance in large alphabet settings, and shows that the effective sample size enlargement phenomenon holds signiﬁcantly more 1 widely than previously established. Index Terms Divergence estimation, KL divergence, multivariate approximation theory, Taylor expansion, functional estimation, maximum likelihood estimator, high dimensional statistics, minimax lower bound I. INTRODUCTION Given jointly independent m samples from P = (p , · · · , p ) and n samples from Q = (q , · · · , q ) over some unknown 1 S 1 S common alphabet of size S, consider the problem of estimating a functional of the distribution of the following form: (cid:88)S F(P, Q) = f(p , q ) (1) i i i=1 where f : A → R is a continuous function with some A ⊂ [0, 1]2. Note that by allowing f to solely depend on p, this problem generalizes the functional estimation problem considered in [1]. Among the most fundamental of such functionals is the f-divergence [2] (cid:90) (cid:18) (cid:19) (cid:18) (cid:19) dP (cid:88)S p D (P(cid:107)Q) = f dQ = f i q (2) f i dQ q i i=1 for some convex function f with f(1) = 0. The f-divergence serves as the fundamental information contained in binary statistical models [3] and enjoys numerable applications in information theory [4] and statistics [5]. Among many f-divergences, we focus on the estimation problem of the Kullback–Leibler (KL) divergence (with f(t) = t ln t − t + 1) in this paper, and the general approach naturally extends to the Hellinger distance and χ2-divergence. The KL divergence is an important measure of the discrepancy between two discrete distributions P = (p , · · · , p ) and Q = 1 S (q , · · · , q ), deﬁned as [6] 1 S (cid:40)(cid:80) S p ln pi if P (cid:28) Q, D(P(cid:107)Q) = i=1 i qi (3) +∞ otherwise, { Yanjun Han, Jiantao Jiao, and Tsachy Weissman are with the Department of Electrical Engineering, Stanford University, CA, USA. Email: yjhan, jiantao, } tsachy @stanford.edu. The material in this paper was presented in part at the 2016 IEEE International Symposium on Information Theory and Its Applications (ISITA), Monterey, USA. ##LTLine## ##LTLine## ##LTLine##

label: paragraph

text: Minimax

label: title

text: Rate-Optimal

text: Estimation

text: of

text: Divergences

text: between

text: Discrete

text: Distributions

text: Yanjun

label: author

text: Han,

text: Student

text: Member,

text: IEEE,

text: Jiantao

text: Jiao,

text: Student

text: Member,

text: IEEE,

text: and

text: Tsachy

text: Weissman,

text: Fellow,

text: IEEE.

text: Abstract

text: We

label: abstract

text: reﬁne

text: the

text: general

text: methodology

text: in

text: for

text: the

text: construction

text: and

text: analysis

text: of

text: essentially

text: minimax

text: estimators

text: for

text: a

text: wide

text: class

text: of

text: functionals

text: of

text: ﬁnite

text: dimensional

text: parameters,

text: and

text: elaborate

text: on

text: the

text: case

text: of

text: discrete

text: distributions

text: with

text: support

text: size

text: S

text: comparable

text: with

text: the

text: number

text: of

text: observations

text: n.

text: Speciﬁcally,

text: we

text: determine

text: the

text: “smooth”

text: and

text: “non-smooth”

text: regimes

text: based

text: on

text: the

text: conﬁdence

text: set

text: and

text: the

text: smoothness

text: of

text: the

text: functional.

text: In

text: the

text: “non-smooth”

text: regime,

text: we

text: apply

text: an

text: unbiased

text: estimator

text: for

text: a

text: suitable

text: polynomial

text: approximation

text: of

text: the

text: functional.

text: In

text: the

text: “smooth”

text: regime,

text: we

text: construct

text: a

text: general

text: version

text: of

text: the

text: bias-corrected

text: Maximum

text: Likelihood

text: Estimator

text: (MLE)

text: based

text: on

text: Taylor

text: expansion.

text: We

text: apply

text: the

text: general

text: methodology

text: to

text: the

text: problem

text: of

text: estimating

text: the

text: KL

text: divergence

text: between

text: two

text: discrete

text: probability

text: measures

text: P

text: and

text: Q

text: from

text: empirical

text: data

text: in

text: a

text: non-asymptotic

text: and

text: possibly

text: large

text: alphabet

text: setting.

text: We

text: construct

text: minimax

text: rate-optimal

text: estimators

text: for

text: D(P

text: Q)

text: when

text: the

text: likelihood

text: ratio

text: is

text: upper

text: bounded

text: by

text: a

text: constant

text: which

text: may

text: depend

text: on

text: the

text: support

text: size,

text: and

text: show

text: that

text: the

text: performance

text: of

text: the

text: optimal

text: estimator

text: with

text: n

text: samples

text: is

text: essentially

text: that

text: of

text: the

text: MLE

text: with

text: n

text: ln

text: n

text: samples.

text: Our

text: estimator

text: is

text: adaptive

text: in

text: the

text: sense

text: that

text: it

text: does

text: not

text: require

text: the

text: knowledge

text: of

text: the

text: support

text: size

text: nor

text: the

text: upper

text: bound

text: on

text: the

text: likelihood

text: ratio.

text: We

text: show

text: that

text: the

text: general

text: methodology

text: results

text: in

text: minimax

text: rate-optimal

text: estimators

text: for

text: other

text: divergences

text: as

text: well,

text: such

text: as

text: the

text: Hellinger

text: distance

text: and

text: the

text: Our

text: approach

text: reﬁnes

text: the

text: Approximation

text: methodology

text: recently

text: developed

text: for

text: the

text: construction

text: of

text: near

text: minimax

text: estimators

text: of

text: functionals

text: of

text: high-dimensional

text: parameters,

text: such

text: as

text: entropy,

text: Re´nyi

text: entropy,

text: mutual

text: information

text: and

text: distance

text: in

text: large

text: alphabet

text: settings,

text: and

text: shows

text: that

text: the

text: effective

text: sample

text: size

text: enlargement

text: phenomenon

text: holds

text: signiﬁcantly

text: more

text: widely

text: than

text: previously

text: established.

text: Index

text: Terms

text: Divergence

text: estimation,

text: KL

text: divergence,

text: multivariate

text: approximation

text: theory,

text: Taylor

text: expansion,

text: functional

text: estimation,

text: maximum

text: likelihood

text: estimator,

text: high

text: dimensional

text: statistics,

text: minimax

text: lower

text: bound

text: I.

text: INTRODUCTION

text: Given

text: jointly

text: independent

text: m

text: samples

text: from

text: P

text: (p

text: p

text: and

text: n

text: samples

text: from

text: Q

text: (q

text: q

text: over

text: some

text: unknown

text: S

text: S

text: common

text: alphabet

text: of

text: size

text: S,

text: consider

text: the

text: problem

text: of

text: estimating

text: a

text: functional

text: of

text: the

text: distribution

text: of

text: the

text: following

text: form:

text: F(P,

text: Q)

text: f(p

text: q

text: i

text: i

text: where

text: f

text: A

text: R

text: is

text: a

text: continuous

text: function

text: with

text: some

text: A

text: Note

text: that

text: by

text: allowing

text: f

text: to

text: solely

text: depend

text: on

text: p,

text: this

text: problem

text: generalizes

text: the

text: functional

text: estimation

text: problem

text: considered

text: in

text: Among

text: the

text: most

text: fundamental

text: of

text: such

text: functionals

text: is

text: the

text: f-divergence

text: dP

text: p

text: D

text: f

text: dQ

text: f

text: i

text: q

text: f

text: i

text: dQ

text: q

text: i

text: for

text: some

text: convex

text: function

text: f

text: with

text: The

text: f-divergence

text: serves

text: as

text: the

text: fundamental

text: information

text: contained

text: in

text: binary

text: statistical

text: models

text: and

text: enjoys

text: numerable

text: applications

text: in

text: information

text: theory

text: and

text: statistics

text: Among

text: many

text: f-divergences,

text: we

text: focus

text: on

text: the

text: estimation

text: problem

text: of

text: the

text: Kullback–Leibler

text: (KL)

text: divergence

text: (with

text: f(t)

text: t

text: ln

text: t

text: t

text: in

text: this

text: paper,

text: and

text: the

text: general

text: approach

text: naturally

text: extends

text: to

text: the

text: Hellinger

text: distance

text: and

text: The

text: KL

text: divergence

text: is

text: an

text: important

text: measure

text: of

text: the

text: discrepancy

text: between

text: two

text: discrete

text: distributions

text: P

text: (p

text: p

text: and

text: Q

text: S

text: (q

text: q

text: deﬁned

text: as

text: S

text: S

text: p

text: ln

text: pi

text: if

text: P

text: Q,

text: i

text: qi

text: otherwise,

text: Yanjun

text: Han,

text: Jiantao

text: Jiao,

text: and

text: Tsachy

text: Weissman

text: are

text: with

text: the

text: Department

text: of

text: Electrical

text: Engineering,

text: Stanford

text: University,

text: CA,

text: USA.

text: Email:

text: yjhan,

text: jiantao,

text: tsachy

text: @stanford.edu.

text: The

text: material

text: in

text: this

text: paper

text: was

text: presented

text: in

text: part

text: at

text: the

text: IEEE

text: International

text: Symposium

text: on

text: Information

text: Theory

text: and

text: Its

text: Applications

text: (ISITA),

text: Monterey,

text: USA.

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 21 as it may seem, the present authors showed in [24] that the variance has an explicit expression in Poisson models, which is the so-called Charlier polynomial [42]. Hence, we have good tools for the analysis of both the bias and the variance of T˜ns,I(pˆ1, qˆ1; pˆ2, qˆ2), which is presented in the following lemma. Lemma 9. Let c1 lnm ≤ p ≤ u(S)q, q ≤ 2c1 lnn, and Poisson random variables m(pˆ , pˆ ) ∼ Poi(mp)×Poi(mp), n(qˆ , qˆ ) ∼ 2m n 1 2 1 2 Poi(nq) × Poi(nq) be independent. If c ≥ 2c and c ln n ≥ 1, we have 1 2 2 (cid:18) (cid:19) 42c u(S) |E[T˜ns,I(pˆ1, qˆ1; pˆ2, qˆ2)] − p ln q| ≤ ClnpW c21 · pn ln n + 2m−c1/36(1 − p ln q) 2 (cid:18) (cid:19) 16c u(S) ln n 2c u(S) ln n 1 (cid:0) (cid:1) + 1 1 + 42C2 + (c ln n)2(C2 + (ln n)2) (138) n1−11c2 ln2 n m ln 2 ln (cid:18) (cid:19) 16c u(S) ln n 2c u(S) ln n 1 (cid:0) (cid:1) Var(T˜ns,I(pˆ1, qˆ1; pˆ2, qˆ2)) ≤ n11−11c2 ln2 1 n + m 42Cl2n + (c2 ln n)2(Cl2n + (ln n)2) + 2m−c1/36 (139) where W(·) and C > 0 are given in Lemma 23. In particular, by Lemma 5, if c > 72 and 11c ln 2 < (cid:15) ∈ (0, 1), we have ln 1 2 (cid:18) (cid:19) 1 u(S) u(S)(ln n)5 u(S) ln n 1 |E[T˜ns,I(pˆ1, qˆ1; pˆ2, qˆ2) + UH(pˆ1)] + p ln(p/q)| (cid:46) m ln m + pW(pn ln n) + n1−(cid:15) n + m (140) (cid:18) (cid:19) p(1 + (ln p)2) 1 u(S)(ln n)5 u(S) ln n 1 Var(T˜ns,I(pˆ1, qˆ1; pˆ2, qˆ2) + UH(pˆ1)) (cid:46) m + m3 + n1−(cid:15) n + m (141) (cid:18) (cid:19) u(S)(ln n)3 p 1 u(S)(ln n)5 u(S) ln n 1 (cid:46) + + + + . (142) mn m m3 n1−(cid:15) n m Here pW( u(S) ) corresponds to the polynomial approximation error, which will become the leading term in the bias. pnlnn Now we consider the “non-smooth” regime II where p ≤ 2c1 lnm, q ≤ 2c1 lnn and p ≤ u(S)q. By the estimator construction, m n it is necessary to deal with the best 2D polynomial approximation of p ln q in (cid:26) (cid:27) 2c ln m 4c ln n R = (p, q) ∈ [0, 1]2 : 0 ≤ p ≤ 1 , 0 ≤ q ≤ 1 , p ≤ u(S)q . (143) m n We emphasize that the polynomial approximation in general multivariate case is extremely complicated. Rice [43] wrote: “The theory of Chebyshev approximation (a.k.a. best approximation) for functions of one real variable has been understood for some time and is quite elegant. For about ﬁfty years attempts have been made to generalize this theory to functions of several variables. These attempts have failed because of the lack of uniqueness of best approximations to functions of more than one variable. ” We also show in [24] that the non-uniqueness can cause serious trouble: some polynomial that achieves the best approximation error cannot be used in our general methodology in functional estimation. What if we relax the requirement of computing the best approximation in the multivariate case, and merely analyze the best approximation rate (i.e., the best approximation error up to a multiplicative constant)? That turns out also to be extremely difﬁcult. Ditzian and Totik [44, Chap. 12] obtained the error rate estimate on simple polytopes3, balls, and spheres, and it remained open until very recently Totik [45] generalized the results to general polytopes. For results in balls and spheres, the readers are referred to Dai and Xu [46]. We still know little about regimes beyond polytopes, balls, and spheres. Complicated as the general multivariate case is, it is still possible to solve our problem since the approximation region R in (143) is a convex polytope. Now we review the general theory of polynomial approximation in convex polytopes [45]. In Rd we call a closed set K ⊂ Rd a convex polytope if it is the convex hull of ﬁnitely many points. Let x ∈ K and e ∈ Rd be a direction (i.e., a unit vector). For continuous function f on K, we deﬁne the r-th symmetric difference in the direction e as 3A simple polytope in Rd is a polytope such that each vertex has d edges. ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: as

text: it

text: may

text: seem,

text: the

text: present

text: authors

text: showed

text: in

text: that

text: the

text: variance

text: has

text: an

text: explicit

text: expression

text: in

text: Poisson

text: models,

text: which

text: is

text: the

text: so-called

text: Charlier

text: polynomial

text: Hence,

text: we

text: have

text: good

text: tools

text: for

text: the

text: analysis

text: of

text: both

text: the

text: bias

text: and

text: the

text: variance

text: of

text: which

text: is

text: presented

text: in

text: the

text: following

text: lemma.

text: Lemma

text: Let

text: lnm

text: p

text: u(S)q,

text: q

text: lnn,

text: and

text: Poisson

text: random

text: variables

text: m(pˆ

text: pˆ

text: Poi(mp)×Poi(mp),

text: n(qˆ

text: qˆ

text: n

text: Poi(nq)

text: Poi(nq)

text: be

text: independent.

text: If

text: c

text: and

text: c

text: ln

text: n

text: we

text: have

text: u(S)

text: p

text: ln

text: q|

text: ClnpW

text: pn

text: ln

text: n

text: p

text: ln

text: q)

text: u(S)

text: ln

text: n

text: u(S)

text: ln

text: n

text: (c

text: ln

text: (ln

text: n

text: m

text: ln

text: ln

text: u(S)

text: ln

text: n

text: u(S)

text: ln

text: n

text: n

text: m

text: ln

text: (ln

text: where

text: W(·)

text: and

text: C

text: are

text: given

text: in

text: Lemma

text: In

text: particular,

text: by

text: Lemma

text: if

text: c

text: and

text: ln

text: we

text: have

text: ln

text: u(S)

text: u(S)(ln

text: u(S)

text: ln

text: n

text: p

text: ln(p/q)|

text: m

text: ln

text: m

text: pW(pn

text: ln

text: n)

text: n

text: m

text: (ln

text: u(S)(ln

text: u(S)

text: ln

text: n

text: m

text: n

text: m

text: u(S)(ln

text: p

text: u(S)(ln

text: u(S)

text: ln

text: n

text: mn

text: m

text: n

text: m

text: Here

text: pW(

text: u(S)

text: corresponds

text: to

text: the

text: polynomial

text: approximation

text: error,

text: which

text: will

text: become

text: the

text: leading

text: term

text: in

text: the

text: bias.

text: pnlnn

text: Now

text: we

text: consider

text: the

text: “non-smooth”

text: regime

text: II

text: where

text: p

text: lnm,

text: q

text: lnn

text: and

text: p

text: u(S)q.

text: By

text: the

text: estimator

text: construction,

text: m

text: n

text: it

text: is

text: necessary

text: to

text: deal

text: with

text: the

text: best

text: polynomial

text: approximation

text: of

text: p

text: ln

text: q

text: in

text: ln

text: m

text: ln

text: n

text: R

text: (p,

text: q)

text: p

text: q

text: p

text: u(S)q

text: m

text: n

text: We

text: emphasize

text: that

text: the

text: polynomial

text: approximation

text: in

text: general

text: multivariate

text: case

text: is

text: extremely

text: complicated.

text: Rice

text: wrote:

text: “The

text: theory

text: of

text: Chebyshev

text: approximation

text: (a.k.a.

text: best

text: approximation)

text: for

text: functions

text: of

text: one

text: real

text: variable

text: has

text: been

text: understood

text: for

text: some

text: time

text: and

text: is

text: quite

text: elegant.

text: For

text: about

text: ﬁfty

text: years

text: attempts

text: have

text: been

text: made

text: to

text: generalize

text: this

text: theory

text: to

text: functions

text: of

text: several

text: variables.

text: These

text: attempts

text: have

text: failed

text: because

text: of

text: the

text: lack

text: of

text: uniqueness

text: of

text: best

text: approximations

text: to

text: functions

text: of

text: more

text: than

text: one

text: variable.

text: We

text: also

text: show

text: in

text: that

text: the

text: non-uniqueness

text: can

text: cause

text: serious

text: trouble:

text: some

text: polynomial

text: that

text: achieves

text: the

text: best

text: approximation

text: error

text: cannot

text: be

text: used

text: in

text: our

text: general

text: methodology

text: in

text: functional

text: estimation.

text: What

text: if

text: we

text: relax

text: the

text: requirement

text: of

text: computing

text: the

text: best

text: approximation

text: in

text: the

text: multivariate

text: case,

text: and

text: merely

text: analyze

text: the

text: best

text: approximation

text: rate

text: (i.e.,

text: the

text: best

text: approximation

text: error

text: up

text: to

text: a

text: multiplicative

text: constant)?

text: That

text: turns

text: out

text: also

text: to

text: be

text: extremely

text: difﬁcult.

text: Ditzian

text: and

text: Totik

text: Chap.

text: obtained

text: the

text: error

text: rate

text: estimate

text: on

text: simple

text: balls,

text: and

text: spheres,

text: and

text: it

text: remained

text: open

text: until

text: very

text: recently

text: Totik

text: generalized

text: the

text: results

text: to

text: general

text: polytopes.

text: For

text: results

text: in

text: balls

text: and

text: spheres,

text: the

text: readers

text: are

text: referred

text: to

text: Dai

text: and

text: Xu

text: We

text: still

text: know

text: little

text: about

text: regimes

text: beyond

text: polytopes,

text: balls,

text: and

text: spheres.

text: Complicated

text: as

text: the

text: general

text: multivariate

text: case

text: is,

text: it

text: is

text: still

text: possible

text: to

text: solve

text: our

text: problem

text: since

text: the

text: approximation

text: region

text: R

text: in

text: is

text: a

text: convex

text: polytope.

text: Now

text: we

text: review

text: the

text: general

text: theory

text: of

text: polynomial

text: approximation

text: in

text: convex

text: polytopes

text: In

text: Rd

text: we

text: call

text: a

text: closed

text: set

text: K

text: Rd

text: a

text: convex

text: polytope

text: if

text: it

text: is

text: the

text: convex

text: hull

text: of

text: ﬁnitely

text: many

text: points.

text: Let

text: x

text: K

text: and

text: e

text: Rd

text: be

text: a

text: direction

text: (i.e.,

text: a

text: unit

text: vector).

text: For

text: continuous

text: function

text: f

text: on

text: K,

text: we

text: deﬁne

text: the

text: r-th

text: symmetric

text: difference

text: in

text: the

text: direction

text: e

text: as

text: simple

text: polytope

text: in

text: Rd

text: is

text: a

text: polytope

text: such

text: that

text: each

text: vertex

text: has

text: d

text: edges.

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 25 (cid:18) (cid:19) S Su(S) Su(S) S S(u(S))2 |Bias(Dˆ)| (cid:46) + + ( )2 + + (173) m ln m n ln n n ln n m2 n2−2(cid:15) (cid:18) (cid:19) S Su(S) Su(S) S Su(S) (cid:46) + + ( )2 + + ( )2 (174) m ln m n ln n n ln n m2 n ln n S Su(S) (cid:46) + (175) m ln m n ln n (cid:18) (cid:19) S Su(S) S S(u(S))2 (1 + ln u(S))2 u(S) Var(Dˆ) (cid:46) ( )2 + ( )2 + + + + (176) m ln m n ln n m2 n2−4(cid:15) m n S Su(S) (ln u(S))2 u(S) (cid:46) ( )2 + ( )2 + + . (177) m ln m n ln n m n Hence we come to the following theorem. Theorem 5. Let m (cid:38) S , n (cid:38) Su(S), ln S (cid:38) ln(m ∨ n) and n (cid:46) mu(S). Then for our estimator Dˆ in (103) constructed lnS lnS lnn lnm from the general recipe, we have (cid:16) (cid:17)2 (cid:18) S Su(S)(cid:19)2 (ln u(S))2 u(S) sup E Dˆ − D(P(cid:107)Q) (cid:46) + + + . (178) (P,Q) m ln m n ln n m n (P,Q)∈US,u(S) Moreover, Dˆ does not require the knowledge of the support size S. C. An adaptive estimator So far we have obtained an essentially minimax estimator via our general recipe. However, since this estimator is purely obtained from the general method, it is not surprising that it is also subject to some disadvantages. Firstly, in the estimator we do not specify the explicit form of the best 2D polynomial approximation in the “non-smooth” regime II. Although the best 1D polynomial approximation is unique and can be efﬁciently obtained via the Remez algorithm [47], which has been efﬁciently implemented in Matlab [48], the best 2D polynomial approximation is not unique and hard to compute. Moreover, as what we have remarked before, the non-uniqueness forces us to add an unnecessary condition n (cid:46) mu(S) in Lemma 11 lnn lnm and thus in Theorem 5. Secondly, although the estimator does not require the knowledge of the support size S (we remove the constant term in the polynomial approximation), but it requires the upper bound on the likelihood ratio u(S) (in the design of “non-smooth” regime I). In practice, we wish to obtain an adaptive estimator which achieves the minimax rate and is agnostic to both S and u(S). Thirdly, for the estimator construction in the “non-smooth” regime I, the approximating polynomial depends on the empirical probabilities (i.e., we cannot store the polynomials in advance), which incurs large computational complexity. To resolve these issues, we need to apply some tricks to explicitly construct an approximating polynomial for f(p, q) = p ln q in the “non-smooth” regime, i.e., q ≤ 2c1 lnn. We ﬁrst suppose that there exists a 1D polynomial T(q) in q with degree (cid:46) ln n n such that pT(q) has the desired approximation property for f(p, q) = p ln q in the entire “non-smooth” regime, i.e., we need not to distinguish “non-smooth” regimes I and II. We remark that either the 1D approximation or only one approximation on the entire “non-smooth” regime is not always doable in general. For example, for estimating the (cid:96) distance, it has been shown 1 in [24] that not only any single approximation in the entire “non-smooth” regime will always fail to give the correct order of the approximation error, but any 1D polynomial approximation of |p − q| in p − q will also not work when both p and q are small. Nevertheless, this ambitious target can be achieved in our special example. Motivated by Lemma 9 and Lemma 11, the correct order of the approximation error is u(S) , i.e., T(q) should satisfy that nlnn u(S) sup |pT(q) − p ln q| (cid:46) . (179) n ln n 0≤q≤2c1 lnn n Since p ≤ u(S)q, it sufﬁces to have 1 2c ln n |T(q) − ln q| (cid:46) , ∀q ∈ (0, 1 ] (180) qn ln n n ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

label: equation

text: S

text: Su(S)

text: Su(S)

text: S

text: |Bias(Dˆ)|

text: m

text: ln

text: m

text: n

text: ln

text: n

text: n

text: ln

text: n

text: S

text: Su(S)

text: Su(S)

text: S

text: Su(S)

text: m

text: ln

text: m

text: n

text: ln

text: n

text: n

text: ln

text: n

text: n

text: ln

text: n

text: S

text: Su(S)

text: m

text: ln

text: m

text: n

text: ln

text: n

text: S

text: Su(S)

text: S

text: ln

text: u(S)

text: Var(Dˆ)

text: m

text: ln

text: m

text: n

text: ln

text: n

text: m

text: n

text: S

text: Su(S)

text: (ln

text: u(S)

text: m

text: ln

text: m

text: n

text: ln

text: n

text: m

text: n

text: Hence

text: we

text: come

text: to

text: the

text: following

text: theorem.

text: Theorem

text: Let

text: m

text: S

text: n

text: Su(S),

text: ln

text: S

text: ln(m

text: n)

text: and

text: n

text: mu(S).

text: Then

text: for

text: our

text: estimator

text: Dˆ

text: in

text: constructed

text: lnS

text: lnS

text: lnn

text: lnm

text: from

text: the

text: general

text: recipe,

text: we

text: have

text: S

text: (ln

text: u(S)

text: sup

text: E

text: Dˆ

text: (P,Q)

text: m

text: ln

text: m

text: n

text: ln

text: n

text: m

text: n

text: (P,Q)∈US,u(S)

text: Moreover,

text: Dˆ

text: does

text: not

text: require

text: the

text: knowledge

text: of

text: the

text: support

text: size

text: S.

text: C.

text: An

text: adaptive

text: estimator

text: So

text: far

text: we

text: have

text: obtained

text: an

text: essentially

text: minimax

text: estimator

text: via

text: our

text: general

text: recipe.

text: However,

text: since

text: this

text: estimator

text: is

text: purely

text: obtained

text: from

text: the

text: general

text: method,

text: it

text: is

text: not

text: surprising

text: that

text: it

text: is

text: also

text: subject

text: to

text: some

text: disadvantages.

text: Firstly,

text: in

text: the

text: estimator

text: we

text: do

text: not

text: specify

text: the

text: explicit

text: form

text: of

text: the

text: best

text: polynomial

text: approximation

text: in

text: the

text: “non-smooth”

text: regime

text: II.

text: Although

text: the

text: best

text: polynomial

text: approximation

text: is

text: unique

text: and

text: can

text: be

text: efﬁciently

text: obtained

text: via

text: the

text: Remez

text: algorithm

text: which

text: has

text: been

text: efﬁciently

text: implemented

text: in

text: Matlab

text: the

text: best

text: polynomial

text: approximation

text: is

text: not

text: unique

text: and

text: hard

text: to

text: compute.

text: Moreover,

text: as

text: what

text: we

text: have

text: remarked

text: before,

text: the

text: non-uniqueness

text: forces

text: us

text: to

text: add

text: an

text: unnecessary

text: condition

text: n

text: mu(S)

text: in

text: Lemma

text: lnn

text: lnm

text: and

text: thus

text: in

text: Theorem

text: Secondly,

text: although

text: the

text: estimator

text: does

text: not

text: require

text: the

text: knowledge

text: of

text: the

text: support

text: size

text: S

text: (we

text: remove

text: the

text: constant

text: term

text: in

text: the

text: polynomial

text: approximation),

text: but

text: it

text: requires

text: the

text: upper

text: bound

text: on

text: the

text: likelihood

text: ratio

text: u(S)

text: (in

text: the

text: design

text: of

text: “non-smooth”

text: regime

text: I).

text: In

text: practice,

text: we

text: wish

text: to

text: obtain

text: an

text: adaptive

text: estimator

text: which

text: achieves

text: the

text: minimax

text: rate

text: and

text: is

text: agnostic

text: to

text: both

text: S

text: and

text: u(S).

text: Thirdly,

text: for

text: the

text: estimator

text: construction

text: in

text: the

text: “non-smooth”

text: regime

text: I,

text: the

text: approximating

text: polynomial

text: depends

text: on

text: the

text: empirical

text: probabilities

text: (i.e.,

text: we

text: cannot

text: store

text: the

text: polynomials

text: in

text: advance),

text: which

text: incurs

text: large

text: computational

text: complexity.

text: To

text: resolve

text: these

text: issues,

text: we

text: need

text: to

text: apply

text: some

text: tricks

text: to

text: explicitly

text: construct

text: an

text: approximating

text: polynomial

text: for

text: f(p,

text: q)

text: p

text: ln

text: q

text: in

text: the

text: “non-smooth”

text: regime,

text: i.e.,

text: q

text: lnn.

text: We

text: ﬁrst

text: suppose

text: that

text: there

text: exists

text: a

text: polynomial

text: T(q)

text: in

text: q

text: with

text: degree

text: ln

text: n

text: n

text: such

text: that

text: pT(q)

text: has

text: the

text: desired

text: approximation

text: property

text: for

text: f(p,

text: q)

text: p

text: ln

text: q

text: in

text: the

text: entire

text: “non-smooth”

text: regime,

text: i.e.,

text: we

text: need

text: not

text: to

text: distinguish

text: “non-smooth”

text: regimes

text: I

text: and

text: II.

text: We

text: remark

text: that

text: either

text: the

text: approximation

text: or

text: only

text: one

text: approximation

text: on

text: the

text: entire

text: “non-smooth”

text: regime

text: is

text: not

text: always

text: doable

text: in

text: general.

text: For

text: example,

text: for

text: estimating

text: the

text: distance,

text: it

text: has

text: been

text: shown

text: in

text: that

text: not

text: only

text: any

text: single

text: approximation

text: in

text: the

text: entire

text: “non-smooth”

text: regime

text: will

text: always

text: fail

text: to

text: give

text: the

text: correct

text: order

text: of

text: the

text: approximation

text: error,

text: but

text: any

text: polynomial

text: approximation

text: of

text: |p

text: q|

text: in

text: p

text: q

text: will

text: also

text: not

text: work

text: when

text: both

text: p

text: and

text: q

text: are

text: small.

text: Nevertheless,

text: this

text: ambitious

text: target

text: can

text: be

text: achieved

text: in

text: our

text: special

text: example.

text: Motivated

text: by

text: Lemma

text: and

text: Lemma

text: the

text: correct

text: order

text: of

text: the

text: approximation

text: error

text: is

text: u(S)

text: i.e.,

text: T(q)

text: should

text: satisfy

text: that

text: nlnn

text: u(S)

text: sup

text: |pT(q)

text: p

text: ln

text: q|

text: n

text: ln

text: n

text: lnn

text: n

text: Since

text: p

text: u(S)q,

text: it

text: sufﬁces

text: to

text: have

text: ln

text: n

text: |T(q)

text: ln

text: q|

text: ∀q

text: qn

text: ln

text: n

text: n

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 27 p 1 “Non-smooth” regime: “Smooth” regime: pˆ× unbiased estimate of a special plug-in approach with 1D polynomial approximation of ln q order-three bias correction 0 q c1 lnn n (cid:80) Fig. 4: Pictorial explanation of our adaptive estimator for S p ln q . i=1 i i Note that in Lemma 14 we have removed the condition n (cid:46) mu(S) in Lemma 11. Moreover, since the upper bounds of the lnn lnm bias and variance of T˜ns presented in Lemma 14 are no worse than those in Lemma 9 and Lemma 11, by the same argument in Lemma 12 and Lemma 13 we conclude that the adaptive estimator DˆA is rate-optimal, and thereby satisﬁes Theorem 1. IV. MINIMAX LOWER BOUND In this section, we prove the minimax lower bounds presented in Theorem 1. There are two main lemmas that we employ towards the proof of the minimax lower bound. The ﬁrst is the Le Cam two-point method, which helps to prove the minimax lower bound corresponding to the variance, or equivalently, the classical asymptotics. Suppose we observe a random vector Z ∈ (Z, A) which has distribution P where θ ∈ Θ. Let θ and θ be two elements of Θ. Let Tˆ = Tˆ(Z) be an arbitrary θ 0 1 estimator of a function T(θ) based on Z. Le Cam’s two-point method gives the following general minimax lower bound. Lemma 15. [5, Sec. 2.4.2] The following inequality holds: (cid:18) (cid:19) |T(θ ) − T(θ )| 1 inf sup P |Tˆ − T(θ)| ≥ 1 0 ≥ exp (−D (P (cid:107)P )) . (191) Tˆ θ∈Θ θ 2 4 θ1 θ0 The second lemma is the so-called method of two fuzzy hypotheses presented in Tsybakov [5]. Suppose we observe a random vector Z ∈ (Z, A) which has distribution P where θ ∈ Θ. Let σ and σ be two prior distributions supported on Θ. θ 0 1 Write F for the marginal distribution of Z when the prior is σ for i = 0, 1. Let Tˆ = Tˆ(Z) be an arbitrary estimator of a i i function T(θ) based on Z. We have the following general minimax lower bound. Lemma 16. [5, Thm. 2.15] Given the setting above, suppose there exist ζ ∈ R, s > 0, 0 ≤ β , β < 1 such that 0 1 σ (θ : T(θ) ≤ ζ − s) ≥ 1 − β (192) 0 0 σ (θ : T(θ) ≥ ζ + s) ≥ 1 − β . (193) 1 1 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: p

text: “Non-smooth”

text: regime:

text: “Smooth”

text: regime:

text: pˆ×

text: unbiased

text: estimate

text: of

text: a

text: special

text: plug-in

text: approach

text: with

text: polynomial

text: approximation

text: of

text: ln

text: q

text: order-three

text: bias

text: correction

text: q

text: lnn

text: n

label: caption

text: Fig.

text: Pictorial

text: explanation

text: of

text: our

text: adaptive

text: estimator

text: for

text: S

text: p

text: ln

text: q

text: i

text: i

text: Note

text: that

text: in

text: Lemma

text: we

text: have

text: removed

text: the

text: condition

text: n

text: mu(S)

text: in

text: Lemma

text: Moreover,

text: since

text: the

text: upper

text: bounds

text: of

text: the

text: lnn

text: lnm

text: bias

text: and

text: variance

text: of

text: T˜ns

text: presented

text: in

text: Lemma

text: are

text: no

text: worse

text: than

text: those

text: in

text: Lemma

text: and

text: Lemma

text: by

text: the

text: same

text: argument

text: in

text: Lemma

text: and

text: Lemma

text: we

text: conclude

text: that

text: the

text: adaptive

text: estimator

text: DˆA

text: is

text: rate-optimal,

text: and

text: thereby

text: satisﬁes

text: Theorem

text: IV.

text: MINIMAX

text: LOWER

text: BOUND

text: In

text: this

text: section,

text: we

text: prove

text: the

text: minimax

text: lower

text: bounds

text: presented

text: in

text: Theorem

text: There

text: are

text: two

text: main

text: lemmas

text: that

text: we

text: employ

text: towards

text: the

text: proof

text: of

text: the

text: minimax

text: lower

text: bound.

text: The

text: ﬁrst

text: is

text: the

text: Le

text: Cam

text: two-point

text: method,

text: which

text: helps

text: to

text: prove

text: the

text: minimax

text: lower

text: bound

text: corresponding

text: to

text: the

text: variance,

text: or

text: equivalently,

text: the

text: classical

text: asymptotics.

text: Suppose

text: we

text: observe

text: a

text: random

text: vector

text: Z

text: (Z,

text: A)

text: which

text: has

text: distribution

text: P

text: where

text: θ

text: Θ.

text: Let

text: θ

text: and

text: θ

text: be

text: two

text: elements

text: of

text: Θ.

text: Let

text: Tˆ

text: Tˆ(Z)

text: be

text: an

text: arbitrary

text: θ

text: estimator

text: of

text: a

text: function

text: T(θ)

text: based

text: on

text: Z.

text: Le

text: Cam’s

text: two-point

text: method

text: gives

text: the

text: following

text: general

text: minimax

text: lower

text: bound.

text: Lemma

text: Sec.

text: The

text: following

text: inequality

text: holds:

text: |T(θ

text: T(θ

text: inf

text: sup

text: P

text: |Tˆ

text: T(θ)|

text: exp

text: (−D

text: (P

text: Tˆ

text: θ∈Θ

text: θ

text: θ1

text: θ0

text: The

text: second

text: lemma

text: is

text: the

text: so-called

text: method

text: of

text: two

text: fuzzy

text: hypotheses

text: presented

text: in

text: Tsybakov

text: Suppose

text: we

text: observe

text: a

text: random

text: vector

text: Z

text: (Z,

text: A)

text: which

text: has

text: distribution

text: P

text: where

text: θ

text: Θ.

text: Let

text: σ

text: and

text: σ

text: be

text: two

text: prior

text: distributions

text: supported

text: on

text: Θ.

text: θ

text: Write

text: F

text: for

text: the

text: marginal

text: distribution

text: of

text: Z

text: when

text: the

text: prior

text: is

text: σ

text: for

text: i

text: Let

text: Tˆ

text: Tˆ(Z)

text: be

text: an

text: arbitrary

text: estimator

text: of

text: a

text: i

text: i

text: function

text: T(θ)

text: based

text: on

text: Z.

text: We

text: have

text: the

text: following

text: general

text: minimax

text: lower

text: bound.

text: Lemma

text: Thm.

text: Given

text: the

text: setting

text: above,

text: suppose

text: there

text: exist

text: ζ

text: R,

text: s

text: β

text: β

text: such

text: that

text: σ

text: (θ

text: T(θ)

text: ζ

text: s)

text: β

text: σ

text: (θ

text: T(θ)

text: ζ

text: s)

text: β

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 28 If V (F , F ) ≤ η < 1, then 1 0 (cid:16) (cid:17) 1 − η − β − β inf sup P |Tˆ − T(θ)| ≥ s ≥ 0 1 , (194) θ Tˆ θ∈Θ 2 where F , i = 0, 1 are the marginal distributions of Z when the priors are σ , i = 0, 1, respectively. i i Here V (P, Q) is the total variation distance between two probability measures P, Q on the measurable space (Z, A). Concretely, we have (cid:90) 1 V (P, Q) (cid:44) sup |P(A) − Q(A)| = |p − q|dν, (195) 2 A∈A where p = dP , q = dQ, and ν is a dominating measure so that P (cid:28) ν, Q (cid:28) ν. dν dν By the proof of the achievability results in previous sections, we observe that ( S + Su(S))2 corresponds to the squared mlnm nlnn bias term, and (lnS)2 + u(S) corresponds to the variance term. In the sequel we will also prove the minimax lower bound for m n the squared bias term and the variance term separately. A. Minimax lower bound for the “variance” First we prove that when n (cid:38) u(S), we have (cid:16) (cid:17) 2 u(S) inf sup E Dˆ − D(P(cid:107)Q) (cid:38) . (196) Dˆ (P,Q)∈US,u(S) (P,Q) n Fix P = ( 1 , · · · , 1 , 1). Applying Lemma 15 to our Poisson sampling model nqˆ ∼ Poi(nq ), 1 ≤ i ≤ S, we know 2(S−1) 2(S−1) 2 i i that for feasible θ = P ×Q = (p , · · · , p )×(q , · · · , q ), θ = P ×Q = (p , · · · , p )×(q(cid:48) , · · · , q(cid:48) ) with θ , θ ∈ U , 1 1 1 S 1 S 0 0 1 S 1 S 0 1 S,u(S) (cid:88)S D (P (cid:107)P ) = D (Poi(mp ) × Poi(nq )(cid:107)Poi(mp ) × Poi(nq(cid:48))) (197) θ1 θ0 i i i i i=1 (cid:88)S = D(Poi(nq )(cid:107)Poi(nq(cid:48))) (198) i i i=1 (cid:20) (cid:21) (cid:88)S (cid:88)∞ q = P (Poi(nq ) = k) · k ln i − n(q − q(cid:48)) (199) i q(cid:48) i i i=1 k=0 i (cid:88)S q (cid:88)S = np ln i − n (q − q(cid:48)) (200) i q(cid:48) i i i=1 i i=1 = nD(Q (cid:107)Q ), (201) 1 0 then Markov’s inequality yields (cid:16) (cid:17) 2 |D(θ ) − D(θ )|2 inf sup E Dˆ − D(P(cid:107)Q) ≥ 1 0 × Dˆ (P,Q)∈US,u(S) (P,Q) 4 (cid:18) (cid:19) |D(θ ) − D(θ )| inf sup P |Dˆ − D(P(cid:107)Q)| ≥ 1 0 (202) Dˆ P∈MS 2 |D(P(cid:107)Q ) − D(P(cid:107)Q )|2 ≥ 1 0 exp (−nD(Q (cid:107)Q )) (203) 1 0 16 where we are operating under the Poisson sampling model. Fix (cid:15) ∈ (0, 1/2) to be speciﬁed later. Letting ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: If

text: V

text: (F

text: F

text: η

text: then

text: η

text: β

text: β

text: inf

text: sup

text: P

text: |Tˆ

text: T(θ)|

text: s

text: θ

text: Tˆ

text: θ∈Θ

text: where

text: F

text: i

text: are

text: the

text: marginal

text: distributions

text: of

text: Z

text: when

text: the

text: priors

text: are

text: σ

text: i

text: respectively.

text: i

text: i

text: Here

text: V

text: (P,

text: Q)

text: is

text: the

text: total

text: variation

text: distance

text: between

text: two

text: probability

text: measures

text: P,

text: Q

text: on

text: the

text: measurable

text: space

text: (Z,

text: A).

text: Concretely,

text: we

text: have

text: V

text: (P,

text: Q)

text: sup

text: |P(A)

text: Q(A)|

text: |p

text: q|dν,

text: A∈A

text: where

text: p

text: dP

text: q

text: dQ,

text: and

text: ν

text: is

text: a

text: dominating

text: measure

text: so

text: that

text: P

text: ν,

text: Q

text: ν.

text: dν

text: dν

text: By

text: the

text: proof

text: of

text: the

text: achievability

text: results

text: in

text: previous

text: sections,

text: we

text: observe

text: that

text: S

text: corresponds

text: to

text: the

text: squared

text: mlnm

text: nlnn

text: bias

text: term,

text: and

text: u(S)

text: corresponds

text: to

text: the

text: variance

text: term.

text: In

text: the

text: sequel

text: we

text: will

text: also

text: prove

text: the

text: minimax

text: lower

text: bound

text: for

text: m

text: n

text: the

text: squared

text: bias

text: term

text: and

text: the

text: variance

text: term

text: separately.

text: A.

text: Minimax

text: lower

text: bound

text: for

text: the

text: “variance”

text: First

text: we

text: prove

text: that

text: when

text: n

text: u(S),

text: we

text: have

text: u(S)

text: inf

text: sup

text: E

text: Dˆ

text: Dˆ

text: (P,Q)∈US,u(S)

text: (P,Q)

text: n

text: Fix

text: P

text: Applying

text: Lemma

text: to

text: our

text: Poisson

text: sampling

text: model

text: nqˆ

text: Poi(nq

text: i

text: S,

text: we

text: know

text: i

text: i

text: that

text: for

text: feasible

text: θ

text: P

text: ×Q

text: (p

text: p

text: )×(q

text: q

text: θ

text: P

text: ×Q

text: (p

text: p

text: with

text: θ

text: θ

text: U

text: S

text: S

text: S

text: S

text: S,u(S)

text: D

text: (P

text: D

text: (Poi(mp

text: Poi(nq

text: θ1

text: θ0

text: i

text: i

text: i

text: i

text: D(Poi(nq

text: i

text: i

text: q

text: P

text: (Poi(nq

text: k)

text: k

text: ln

text: i

text: n(q

text: i

text: i

text: i

text: i

text: q

text: np

text: ln

text: i

text: n

text: (q

text: i

text: i

text: i

text: i

text: nD(Q

text: then

text: Markov’s

text: inequality

text: yields

text: |D(θ

text: D(θ

text: inf

text: sup

text: E

text: Dˆ

text: Dˆ

text: (P,Q)∈US,u(S)

text: (P,Q)

text: |D(θ

text: D(θ

text: inf

text: sup

text: P

text: |Dˆ

text: Dˆ

text: P∈MS

text: exp

text: (−nD(Q

text: where

text: we

text: are

text: operating

text: under

text: the

text: Poisson

text: sampling

text: model.

text: Fix

text: to

text: be

text: speciﬁed

text: later.

text: Letting

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 34 R˜ (x) (cid:44) (R (x) ∧ 1) ∨ (−1) (253) l l (cid:18) (cid:19) R (x) (cid:44) c(cid:88)2 lnl a 2c1 ln l −k+12 k(cid:89)−1(x − j ) (254) l c2 lnl,k l l k=1 j=0 coefﬁcients {a } are given by (251), and c , c > 0 are some suitably chosen universal constants. K,k 1 2 The previous estimator does not require the knowledge of S since it assigns zero to unseen symbols (we remove the constant (cid:80) √ term in the expression of R (x)). Note that since the Hellinger distance H2(P, Q) = 1− S p q enjoys a natural separation l i=1 i i in its variables (p , q ), the pair (p , q ) is also separated in our resulting estimator. Moreover, in our estimator construction we i i i i can also merge (pˆ , pˆ ) and (qˆ , qˆ ) to result in a two-fold sample splitting. i,1 i,2 i,1 i,2 Now we analyze the bias of the previous estimator. When p < 2c1 lnm is small, by [1, Lemma 17], we know that m √ √ (cid:112) p √ ∆ 1 |ER (pˆ) − p| = | ∆ Q ( ) − p| (cid:46) m (cid:46) √ . (255) m m Km ∆m Km2 m ln m When p ≥ 2c1 lnm is large, by Lemma 6 with r = 0 we know that m (cid:12) √ (cid:12) (cid:112) √ p (cid:12)d2 ξ (cid:12) 1 1 |E pˆ− p| (cid:46) m · ξ∈[spu/2p,2p] (cid:12)(cid:12) dξ2 (cid:12)(cid:12) (cid:46) m√p (cid:46) √m ln m. (256) Hence, the total bias of Tˆ can be upper bounded as (cid:18) √ √ (cid:19) (cid:114) (cid:114) (cid:115) (cid:88)S q p S S S |Bias(Tˆ)| (cid:46) √ i + √ i ≤ + (cid:16) (257) m ln m n ln n m ln m n ln n (m ∧ n) ln(m ∧ n) i=1 as shown in Theorem 3. The variance can also be obtained in a similar fashion, and we omit the details. B. Optimal estimator for the χ2-divergence For the χ2-divergence χ2(P, Q) over U , the bivariate function of interest is f(p, q) = p2 . We ﬁrst classify the regime. S,u(S) q Since this function shares very similar analytic properties as the function p ln q used in the KL divergence case, and our parameter set U remains the same, here the “smooth” and “non-smooth” regimes are also given by S,u(S) c ln n Θˆs = [0, 1] × [ 1 , 1] (258) n c ln n Θˆns = [0, 1] × [0, 1 ] (259) n with some universal constant c > 0. 1 Next we estimate f(p, q) = p2 in each regime. In the “smooth” regime where q ≥ c1 lnn, we seek to correct the bias of q n the plug-in estimator 1/qˆ in estimating 1/q. Based on our general bias correction technique (31), we simply use the following order-three bias correction: 1 qˆ − qˆ (qˆ − qˆ )2 4qˆ (qˆ − qˆ )3 3qˆ2 6qˆ Tˆ(3)(qˆ , qˆ ) = − 2 1 + 2 1 − 2 − 2 1 + 2 − 2 . (260) 1 2 qˆ qˆ2 qˆ3 nqˆ3 qˆ4 nqˆ4 n2qˆ4 1 1 1 1 1 1 1 Since p2 admits an unbiased estimate pˆ(pˆ− 1 ) in the Poisson model mpˆ ∼ Poi(mp), the overall estimator in the “smooth” m regime is given by (cid:18) (cid:19) 1 Tˆs(pˆ1, qˆ1; pˆ2, qˆ2) = pˆ1 pˆ1 − · Tˆ(3)(qˆ1, qˆ2) · 1(qˆ1 (cid:54)= 0) (261) m (cid:18) (cid:19) (cid:18) (cid:19) 1 1 qˆ − qˆ (qˆ − qˆ )2 4qˆ (qˆ − qˆ )3 3qˆ2 6qˆ = pˆ1 pˆ1 − m · qˆ − 2 qˆ2 1 + 2 qˆ3 1 − nqˆ23 − 2 qˆ4 1 + nqˆ24 − n2qˆ24 · 1(qˆ1 (cid:54)= 0). (262) 1 1 1 1 1 1 1 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: R˜

text: (x)

text: (R

text: (x)

text: l

text: l

text: R

text: (x)

text: lnl

text: a

text: ln

text: l

text: j

text: l

text: lnl,k

text: l

text: l

text: coefﬁcients

text: {a

text: are

text: given

text: by

text: and

text: c

text: c

text: are

text: some

text: suitably

text: chosen

text: universal

text: constants.

text: K,k

text: The

text: previous

text: estimator

text: does

text: not

text: require

text: the

text: knowledge

text: of

text: S

text: since

text: it

text: assigns

text: zero

text: to

text: unseen

text: symbols

text: (we

text: remove

text: the

text: constant

text: term

text: in

text: the

text: expression

text: of

text: R

text: (x)).

text: Note

text: that

text: since

text: the

text: Hellinger

text: distance

text: Q)

text: 1−

text: S

text: p

text: q

text: enjoys

text: a

text: natural

text: separation

text: l

text: i

text: i

text: in

text: its

text: variables

text: (p

text: q

text: the

text: pair

text: (p

text: q

text: is

text: also

text: separated

text: in

text: our

text: resulting

text: estimator.

text: Moreover,

text: in

text: our

text: estimator

text: construction

text: we

text: i

text: i

text: i

text: i

text: can

text: also

text: merge

text: (pˆ

text: pˆ

text: and

text: (qˆ

text: qˆ

text: to

text: result

text: in

text: a

text: two-fold

text: sample

text: splitting.

text: Now

text: we

text: analyze

text: the

text: bias

text: of

text: the

text: previous

text: estimator.

text: When

text: p

text: lnm

text: is

text: small,

text: by

text: Lemma

text: we

text: know

text: that

text: m

text: p

text: |ER

text: (pˆ)

text: p|

text: Q

text: p|

text: m

text: m

text: m

text: Km

text: ∆m

text: m

text: ln

text: m

text: When

text: p

text: lnm

text: is

text: large,

text: by

text: Lemma

text: with

text: r

text: we

text: know

text: that

text: m

text: p

text: ξ

text: |E

text: pˆ−

text: p|

text: m

text: m√p

text: √m

text: ln

text: m.

text: Hence,

text: the

text: total

text: bias

text: of

text: Tˆ

text: can

text: be

text: upper

text: bounded

text: as

text: q

text: p

text: S

text: S

text: S

text: |Bias(Tˆ)|

text: i

text: i

text: m

text: ln

text: m

text: n

text: ln

text: n

text: m

text: ln

text: m

text: n

text: ln

text: n

text: (m

text: n)

text: ln(m

text: n)

text: as

text: shown

text: in

text: Theorem

text: The

text: variance

text: can

text: also

text: be

text: obtained

text: in

text: a

text: similar

text: fashion,

text: and

text: we

text: omit

text: the

text: details.

text: B.

text: Optimal

text: estimator

text: for

text: the

text: For

text: the

text: Q)

text: over

text: U

text: the

text: bivariate

text: function

text: of

text: interest

text: is

text: f(p,

text: q)

text: We

text: ﬁrst

text: classify

text: the

text: regime.

text: S,u(S)

text: q

text: Since

text: this

text: function

text: shares

text: very

text: similar

text: analytic

text: properties

text: as

text: the

text: function

text: p

text: ln

text: q

text: used

text: in

text: the

text: KL

text: divergence

text: case,

text: and

text: our

text: parameter

text: set

text: U

text: remains

text: the

text: same,

text: here

text: the

text: “smooth”

text: and

text: “non-smooth”

text: regimes

text: are

text: also

text: given

text: by

text: S,u(S)

text: c

text: ln

text: n

text: Θˆs

text: n

text: c

text: ln

text: n

text: Θˆns

text: n

text: with

text: some

text: universal

text: constant

text: c

text: Next

text: we

text: estimate

text: f(p,

text: q)

text: in

text: each

text: regime.

text: In

text: the

text: “smooth”

text: regime

text: where

text: q

text: lnn,

text: we

text: seek

text: to

text: correct

text: the

text: bias

text: of

text: q

text: n

text: the

text: plug-in

text: estimator

text: in

text: estimating

text: Based

text: on

text: our

text: general

text: bias

text: correction

text: technique

text: we

text: simply

text: use

text: the

text: following

text: order-three

text: bias

text: correction:

text: qˆ

text: qˆ

text: (qˆ

text: qˆ

text: (qˆ

text: qˆ

text: qˆ

text: qˆ

text: Since

text: admits

text: an

text: unbiased

text: estimate

text: pˆ(pˆ−

text: in

text: the

text: Poisson

text: model

text: mpˆ

text: Poi(mp),

text: the

text: overall

text: estimator

text: in

text: the

text: “smooth”

text: m

text: regime

text: is

text: given

text: by

text: m

text: qˆ

text: qˆ

text: (qˆ

text: qˆ

text: (qˆ

text: qˆ

text: m

text: qˆ

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 48 c ln m c ln m Ts(pˆ, qˆ) = Ts,I(pˆ, qˆ)1(pˆ3 > 1 ) + Ts,II(pˆ, qˆ)1(pˆ3 ≤ 1 ). (416) m m By Lemma 7, the bias can be upper bounded as |Ts(pˆ, qˆ) + ln(p/q)| ≤ |ETs,I(pˆ, qˆ) + p ln(p/q)| + |ETs,II(pˆ, qˆ) + p ln(p/q)| (417) 1 u(S) (cid:46) + . (418) m ln m n ln n As for the variance, by Lemma 30 we have Var(Ts(pˆ, qˆ)) ≤ Var(Ts,I(pˆ, qˆ)) + Var(Ts,II(pˆ, qˆ)) + (ETs,I(pˆ, qˆ) − ETs,II(pˆ, qˆ))2 (419) ≤ Var(Ts,I(pˆ, qˆ)) + Var(Ts,II(pˆ, qˆ)) + 2|ETs,I(pˆ, qˆ) + p ln(p/q)|2 + 2|ETs,II(pˆ, qˆ) + p ln(p/q)|2 (420) (cid:18) (cid:19) 1 p(1 + ln u(S))2 q u(S) pu(S) 1 u(S) 2 (cid:46) + + + + + + (421) m2−(cid:15) m m mn n m ln m n ln n (cid:18) (cid:19) (cid:18) (cid:19) 1 p(1 + ln u(S))2 q u(S) pu(S) 1 2 u(S) 2 (cid:46) + + + + + + (422) m2−(cid:15) m m mn n m ln m n ln n (cid:18) (cid:19) 1 p(1 + ln u(S))2 q u(S) pu(S) u(S) 2 (cid:46) + + + + + (423) m2−(cid:15) m m mn n n ln n as desired. H. Proof of Lemma 9 (cid:113) Denote by E the event that 2p ≤ pˆ ≤ p + 1 c1pˆ2 lnm, then by Lemma 28 we have 3 2 2 m (cid:114) 2p 1 c pˆ ln m P(Ec) ≤ P(pˆ < ) + P(pˆ > p + 1 2 ) (424) 2 2 3 2 m (cid:114) (cid:114) c p ln m 1 c p ln m ≤ P(pˆ < p − 1 ) + P(pˆ > p + 1 ) (425) 2 2 18m 2 m  (cid:32)(cid:115) (cid:33)   (cid:32)(cid:115) (cid:33)  2 2 1 c ln m 1 c ln m ≤ exp − 1 · mp + exp − 1 · mp (426) 2 18mp 3 4mp ≤ 2e−c1m/36. (427) Note that conditioning on the event E, we have pˆ ≥ c1 lnm, and 2 3m (cid:32) √ (cid:33) (cid:32) (cid:114) (cid:33) 2p 1 3 1 1 c pˆ ln m p 2c ln n 0 < ≤ pˆ − pˆ ≤ pˆ − 1 2 ≤ ≤ q ≤ 1 (428) 2 2 2 21u(S) u(S) 2 u(S) 2 m u(S) n i.e., the approximation region contains q. We ﬁrst analyze the variance: Var(T˜ns,I(pˆ1, qˆ1; pˆ2, qˆ2)) ≤ E[T˜ns,I(pˆ1, qˆ1; pˆ2, qˆ2)2] (429) = E[T˜ns,I(pˆ1, qˆ1; pˆ2, qˆ2)21(E)] + E[T˜ns,I(pˆ1, qˆ1; pˆ2, qˆ2)21(Ec)] (430) ≤ E[Tns,I(pˆ1, qˆ1; pˆ2, qˆ2)21(E)] + 1 · P(Ec). (431) Note that conditioning on E, we have ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: c

text: ln

text: m

text: c

text: ln

text: m

text: Ts(pˆ,

text: qˆ)

text: Ts,I(pˆ,

text: Ts,II(pˆ,

text: m

text: m

text: By

text: Lemma

text: the

text: bias

text: can

text: be

text: upper

text: bounded

text: as

text: |Ts(pˆ,

text: qˆ)

text: ln(p/q)|

text: |ETs,I(pˆ,

text: qˆ)

text: p

text: ln(p/q)|

text: |ETs,II(pˆ,

text: qˆ)

text: p

text: ln(p/q)|

text: u(S)

text: m

text: ln

text: m

text: n

text: ln

text: n

text: As

text: for

text: the

text: variance,

text: by

text: Lemma

text: we

text: have

text: Var(Ts(pˆ,

text: qˆ))

text: Var(Ts,I(pˆ,

text: qˆ))

text: Var(Ts,II(pˆ,

text: qˆ))

text: (ETs,I(pˆ,

text: qˆ)

text: ETs,II(pˆ,

text: Var(Ts,I(pˆ,

text: qˆ))

text: Var(Ts,II(pˆ,

text: qˆ))

text: qˆ)

text: p

text: qˆ)

text: p

text: ln

text: q

text: u(S)

text: pu(S)

text: u(S)

text: m

text: m

text: mn

text: n

text: m

text: ln

text: m

text: n

text: ln

text: n

text: ln

text: q

text: u(S)

text: pu(S)

text: u(S)

text: m

text: m

text: mn

text: n

text: m

text: ln

text: m

text: n

text: ln

text: n

text: ln

text: q

text: u(S)

text: pu(S)

text: u(S)

text: m

text: m

text: mn

text: n

text: n

text: ln

text: n

text: as

text: desired.

text: H.

text: Proof

text: of

text: Lemma

text: Denote

text: by

text: E

text: the

text: event

text: that

text: pˆ

text: p

text: lnm,

text: then

text: by

text: Lemma

text: we

text: have

text: m

text: c

text: pˆ

text: ln

text: m

text: P(Ec)

text: P(pˆ

text: P(pˆ

text: p

text: m

text: c

text: p

text: ln

text: m

text: c

text: p

text: ln

text: m

text: P(pˆ

text: p

text: P(pˆ

text: p

text: m

text: c

text: ln

text: m

text: c

text: ln

text: m

text: exp

text: mp

text: exp

text: mp

text: Note

text: that

text: conditioning

text: on

text: the

text: event

text: E,

text: we

text: have

text: pˆ

text: lnm,

text: and

text: c

text: pˆ

text: ln

text: m

text: p

text: ln

text: n

text: pˆ

text: pˆ

text: pˆ

text: q

text: u(S)

text: u(S)

text: m

text: u(S)

text: n

text: i.e.,

text: the

text: approximation

text: region

text: contains

text: q.

text: We

text: ﬁrst

text: analyze

text: the

text: variance:

text: P(Ec).

text: Note

text: that

text: conditioning

text: on

text: E,

text: we

text: have

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 7 Θ(1) (cid:44) Θ − ∪ U (x) (23) s x∈Θˆ0 1 Θ(2) (cid:44) ∪ U (x) (24) ns x∈Θˆ0 2 Θˆs (cid:44) {θˆn ∈ Θˆ : Θ(s1) ⊃ U1(θˆn)} (25) Θˆns (cid:44) {θˆn ∈ Θˆ : Θ(n2s) ⊃ U2(θˆn)} (26) satisfy that Θˆs ∪ Θˆns = Θˆ (by passing through subsets it does not matter if Θˆs ∩ Θˆns (cid:54)= ∅). Note that in this case we must have Θ(s1) ∩ Θ(n2s) (cid:54)= ∅, i.e., there exists some θ which belongs to both the “smooth” regime and the “non-smooth” regime. The interpretation of this approach is as follows. If the true parameter θ falls in the “smooth” regime Θ(s1), then the plug- in approach will work; conversely, if the true parameter θ falls in the “non-smooth” regime Θ(n2s), then the approximation idea will work. Then Θ(s1) ∩Θ(n2s) (cid:54)= ∅ implies that there exists an intermediate regime such that both the plug-in approach and the approximation approach work when θ falls into this regime. This intermediate regime is unnecessary when we are given the partial information whether θ ∈ Θ(s1) or θ ∈ Θ(n2s), but it becomes important when we need to infer this partial information based on θˆ . Our target is as follows: if the true parameter θ does not fall in the “smooth” (resp. n “non-smooth”) regime, then with high probability we will also declare based on θˆ that we are not in the “smooth” (resp. n “non-smooth”) regime. Mathematically, with high probability, θ ∈ Θ − Θ(s1) implies θˆn ∈ Θˆns, and θ ∈ Θ − Θ(n2s) implies θˆn ∈ Θˆs. Note that if θ ∈ Θ(s1) ∩ Θ(n2s) falls in the intermediate regime, either θˆn ∈ Θˆs or θˆn ∈ Θˆns sufﬁces for our estimator to perform well. The key fact is that this target is fulﬁlled by the deﬁnition of conﬁdence sets: if θ ∈ Θ − Θ(s1) and θˆn ∈/ Θˆns, we have θˆn ∈ Θˆs, and by deﬁnition of Θˆs we have U1(θˆn) ⊂ Θ(s1), which implies θ ∈/ U1(θˆn). As a result, sup Pθ(θˆn ∈/ Θˆns) ≤ sup Pθ(θ ∈/ U1(θˆn)) ≤ sup Pθ(θ ∈/ U1(θˆn)) ≤ rn(1) (27) θ∈Θ−Θ(s1) θ∈Θ−Θ(s1) θ∈Θ and similarly supθ∈Θ−Θ(ns2) Pθ(θˆn ∈/ Θˆs) ≤ rn(2). Hence, we successfully localize θ via conﬁdence sets based on θˆn such that the true parameter θ is very likely to belong to the declared regime based on θˆ . n A pictorial illustration of this idea is shown in Figure 2. Θˆ = Θ U (θˆ ) 2 2 θˆ 2 θˆ 1 U (θˆ ) 1 1 Θˆ0 Θˆns Θˆs Θ − Θ(s1) I II III Θ − Θ(n2s) IV Fig. 2: Pictorial explanation of the “smooth” and “non-smooth” regimes based on θ and θˆ , respectively. In the above ﬁgure, n we have Θ(s1) = II ∪ III ∪ IV, Θ(n2s) = I ∪ II ∪ III, Θˆs = III ∪ IV, and Θˆns = I ∪ II. In particular, Θ(s1) ∩ Θ(n2s) = II ∪ III is the intermediate regime, where both the plug-in and the approximation approach are performing well. For θˆ1 ∈ Θˆns, we have U1(θˆ1) ⊂ Θ(n2s); for θˆ2 ∈ Θˆs, we have U2(θˆ2) ⊂ Θ(s1). 3) Question 3: Given a conﬁdence set {U(x)}x∈Θˆ of a satisfactory signiﬁcance level rn, after observing θˆn ∈ Θˆns we can always set the approximation region to be U(θˆn). Note that U(θˆn) ⊂ Θns by deﬁnition, and in fact U(θˆn) can be considerably smaller than Θns, which makes it a desirable regime to approximate over rather than Θns and is proved to be necessary in [24]. The reason why U(θˆ ) is sufﬁcient is as follows: by deﬁnition of conﬁdence sets we have n sup P (θ ∈ U(θˆ )) ≤ r , hence with probability at least 1−r , the approximation region U(θˆ ) based on θˆ covers θ∈Θ θ n n n n n

text: Θ

text: U

text: (x)

text: s

text: x∈Θˆ0

text: U

text: (x)

text: ns

text: x∈Θˆ0

text: Θˆs

text: {θˆn

text: Θˆ

text: Θˆns

text: {θˆn

text: Θˆ

text: satisfy

label: list

text: that

text: Θˆs

text: Θˆns

text: Θˆ

text: (by

text: passing

text: through

text: subsets

text: it

text: does

text: not

text: matter

text: if

text: Θˆs

text: Θˆns

text: Note

text: that

text: in

text: this

text: case

text: we

text: must

text: have

text: i.e.,

text: there

text: exists

text: some

text: θ

text: which

text: belongs

text: to

text: both

text: the

text: “smooth”

text: regime

text: and

text: the

text: “non-smooth”

text: regime.

text: The

text: interpretation

text: of

text: this

text: approach

text: is

text: as

text: follows.

text: If

text: the

text: true

text: parameter

text: θ

text: falls

text: in

text: the

text: “smooth”

text: regime

text: then

text: the

text: plug-

text: in

text: approach

text: will

text: work;

text: conversely,

text: if

text: the

text: true

text: parameter

text: θ

text: falls

text: in

text: the

text: “non-smooth”

text: regime

text: then

text: the

text: approximation

text: idea

text: will

text: work.

text: Then

text: implies

text: that

text: there

text: exists

text: an

text: intermediate

text: regime

text: such

text: that

text: both

text: the

text: plug-in

text: approach

text: and

text: the

text: approximation

text: approach

text: work

text: when

text: θ

text: falls

text: into

text: this

text: regime.

text: This

text: intermediate

text: regime

text: is

text: unnecessary

text: when

text: we

text: are

text: given

text: the

text: partial

text: information

text: whether

text: θ

text: or

text: θ

text: but

text: it

text: becomes

text: important

text: when

text: we

text: need

text: to

text: infer

text: this

text: partial

text: information

text: based

text: on

text: θˆ

text: Our

text: target

text: is

text: as

text: follows:

text: if

text: the

text: true

text: parameter

text: θ

text: does

text: not

text: fall

text: in

text: the

text: “smooth”

text: (resp.

text: n

text: “non-smooth”)

text: regime,

text: then

text: with

text: high

text: probability

text: we

text: will

text: also

text: declare

text: based

text: on

text: θˆ

text: that

text: we

text: are

text: not

text: in

text: the

text: “smooth”

text: (resp.

text: n

text: “non-smooth”)

text: regime.

text: Mathematically,

text: with

text: high

text: probability,

text: θ

text: Θ

text: implies

text: θˆn

text: Θˆns,

text: and

text: θ

text: Θ

text: implies

text: θˆn

text: Θˆs.

text: Note

text: that

text: if

text: θ

text: falls

text: in

text: the

text: intermediate

text: regime,

text: either

text: θˆn

text: Θˆs

text: or

text: θˆn

text: Θˆns

text: sufﬁces

text: for

text: our

text: estimator

text: to

text: perform

text: well.

text: The

text: key

text: fact

text: is

text: that

text: this

text: target

text: is

text: fulﬁlled

text: by

text: the

text: deﬁnition

text: of

text: conﬁdence

text: sets:

text: if

text: θ

text: Θ

text: and

text: θˆn

text: Θˆns,

text: we

text: have

text: θˆn

text: Θˆs,

text: and

text: by

text: deﬁnition

text: of

text: Θˆs

text: we

text: have

text: which

text: implies

text: θ

text: As

text: a

text: result,

text: sup

text: Pθ(θˆn

text: Θˆns)

text: sup

text: Pθ(θ

text: sup

text: Pθ(θ

text: θ∈Θ−Θ(s1)

text: θ∈Θ−Θ(s1)

text: θ∈Θ

text: and

text: similarly

text: Pθ(θˆn

text: Θˆs)

text: Hence,

text: we

text: successfully

text: localize

text: θ

text: via

text: conﬁdence

text: sets

text: based

text: on

text: θˆn

text: such

text: that

text: the

text: true

text: parameter

text: θ

text: is

text: very

text: likely

text: to

text: belong

text: to

text: the

text: declared

text: regime

text: based

text: on

text: θˆ

text: n

text: A

text: pictorial

text: illustration

text: of

text: this

text: idea

text: is

text: shown

text: in

text: Figure

text: Θˆ

text: Θ

text: U

text: (θˆ

text: θˆ

text: θˆ

text: U

text: (θˆ

text: Θˆ0

text: Θˆns

text: Θˆs

text: Θ

text: I

text: II

text: III

text: Θ

text: IV

text: Fig.

text: Pictorial

text: explanation

text: of

text: the

text: “smooth”

text: and

text: “non-smooth”

text: regimes

text: based

text: on

text: θ

text: and

text: θˆ

text: respectively.

text: In

text: the

text: above

text: ﬁgure,

text: n

text: we

text: have

text: II

text: III

text: IV,

text: I

text: II

text: III,

text: Θˆs

text: III

text: IV,

text: and

text: Θˆns

text: I

text: II.

text: In

text: particular,

text: II

text: III

text: is

text: the

text: intermediate

text: regime,

text: where

text: both

text: the

text: plug-in

text: and

text: the

text: approximation

text: approach

text: are

text: performing

text: well.

text: For

text: θˆ1

text: Θˆns,

text: we

text: have

text: for

text: θˆ2

text: Θˆs,

text: we

text: have

text: Question

text: Given

text: a

text: conﬁdence

text: set

text: {U(x)}x∈Θˆ

text: of

text: a

text: satisfactory

text: signiﬁcance

text: level

text: rn,

text: after

text: observing

text: θˆn

text: Θˆns

text: we

text: can

text: always

text: set

text: the

text: approximation

text: region

text: to

text: be

text: U(θˆn).

text: Note

text: that

text: U(θˆn)

text: Θns

text: by

text: deﬁnition,

text: and

text: in

text: fact

text: U(θˆn)

text: can

text: be

text: considerably

text: smaller

text: than

text: Θns,

text: which

text: makes

text: it

text: a

text: desirable

text: regime

text: to

text: approximate

text: over

text: rather

text: than

text: Θns

text: and

text: is

text: proved

text: to

text: be

text: necessary

text: in

text: The

text: reason

text: why

text: U(θˆ

text: is

text: sufﬁcient

text: is

text: as

text: follows:

text: by

text: deﬁnition

text: of

text: conﬁdence

text: sets

text: we

text: have

text: n

text: sup

text: P

text: (θ

text: U(θˆ

text: r

text: hence

text: with

text: probability

text: at

text: least

text: the

text: approximation

text: region

text: U(θˆ

text: based

text: on

text: θˆ

text: covers

text: θ∈Θ

text: θ

text: n

text: n

text: n

text: n

text: n


text: 62 [13] C. M. Bishop, “Pattern recognition,” Machine Learning, vol. 128, 2006. [14] D. P. Kingma and M. Welling, “Auto-encoding variational bayes,” arXiv preprint arXiv:1312.6114, 2013. [15] Q. Wang, S. R. Kulkarni, and S. Verdu´, “Divergence estimation of continuous distributions based on data-dependent partitions,” Information Theory, IEEE Transactions on, vol. 51, no. 9, pp. 3064–3074, 2005. [16] Y. K. Lee and B. U. Park, “Estimation of Kullback–Leibler divergence by local likelihood,” Annals of the Institute of Statistical Mathematics, vol. 58, no. 2, pp. 327–340, 2006. [17] A. Gretton, K. M. Borgwardt, M. Rasch, B. Scho¨lkopf, and A. J. Smola, “A kernel method for the two-sample-problem,” in Advances in neural information processing systems, 2006, pp. 513–520. [18] F. Pe´rez-Cruz, “Kullback-Leibler divergence estimation of continuous distributions,” in Information Theory, 2008. ISIT 2008. IEEE International Symposium on. IEEE, 2008, pp. 1666–1670. [19] Q. Wang, S. R. Kulkarni, and S. Verdu´, “Divergence estimation for multidimensional densities via-nearest-neighbor distances,” Information Theory, IEEE Transactions on, vol. 55, no. 5, pp. 2392–2405, 2009. [20] X. Nguyen, M. J. Wainwright, and M. I. Jordan, “Estimating divergence functionals and the likelihood ratio by convex risk minimization,” Information Theory, IEEE Transactions on, vol. 56, no. 11, pp. 5847–5861, 2010. [21] H. Cai, S. R. Kulkarni, and S. Verdu´, “Universal divergence estimation for ﬁnite-alphabet sources,” Information Theory, IEEE Transactions on, vol. 52, no. 8, pp. 3456–3475, 2006. [22] Z. Zhang and M. Grabchak, “Nonparametric estimation of Ku¨llback-Leibler divergence,” Neural computation, vol. 26, no. 11, pp. 2570–2593, 2014. [23] A. W. Van der Vaart, Asymptotic statistics. Cambridge university press, 2000, vol. 3. [24] J. Jiao, Y. Han, and T. Weissman, “Minimax estimation of the l1 distance,” in 2016 IEEE International Symposium on Information Theory (ISIT). IEEE, 2016, pp. 750–754. [25] Y. Bu, S. Zou, Y. Liang, and V. V. Veeravalli, “Estimation of KL divergence between large-alphabet distributions,” in 2016 IEEE International Symposium on Information Theory (ISIT). IEEE, 2016, pp. 1118–1122. [26] ——, “Estimation of KL divergence: Optimal minimax rate,” arXiv preprint arXiv:1607.02653, 2016. [27] 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. [28] 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. [29] 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. [30] Y. Wu and P. Yang, “Minimax rates of entropy estimation on large alphabets via best polynomial approximation,” arXiv preprint arXiv:1407.0381, 2014. [31] J. Acharya, A. Orlitsky, A. T. Suresh, and H. Tyagi, “The complexity of estimating Re´nyi entropy.” SODA, 2015. [32] Y. Wu and P. Yang, “Chebyshev polynomials, moment matching, and optimal estimation of the unseen,” arXiv preprint arXiv:1504.01227, 2015. [33] Y. Han, J. Jiao, R. Mukherjee, and T. Weissman, “Optimal estimation of Lr norm of functions in Gaussian white noise,” in preparation, 2016. [34] G. A. Miller, “Note on the bias of information estimates,” Information Theory in Psychology: Problems and Methods, vol. 2, pp. 95–100, 1955. [35] A. Carlton, “On the bias of information estimates.” Psychological Bulletin, vol. 71, no. 2, p. 108, 1969. [36] A. Nemirovski, “Topics in non-parametric,” Ecole d’Ete´ de Probabilite´s de Saint-Flour, vol. 28, p. 85, 2000. [37] M. Mitzenmacher and E. Upfal, Probability and computing: Randomized algorithms and probabilistic analysis. Cambridge University Press, 2005. [38] J. Jiao, K. Venkat, Y. Han, and T. Weissman, “Non-asymptotic theory for the plug-in rule in functional estimation,” arXiv preprint arXiv:1406.6959, 2014. [39] D. Braess and T. Sauer, “Bernstein polynomials and learning theory,” Journal of Approximation Theory, vol. 128, no. 2, pp. 187–206, 2004. [40] A. Tsybakov, “Aggregation and high-dimensional statistics,” Lecture notes for the course given at the E´cole d’e´te´ de Probabilite´s in Saint-Flour, URL http://www. crest. fr/ckﬁnder/userﬁles/ﬁles/Pageperso/ATsybakov/Lecture notes SFlour. pdf, vol. 16, p. 20, 2013. [41] C. S. Withers, “Bias reduction by Taylor series,” Communications in Statistics-Theory and Methods, vol. 16, no. 8, pp. 2369–2383, 1987. [42] G. Peccati and M. S. Taqqu, “Some facts about Charlier polynomials,” in Wiener Chaos: Moments, Cumulants and Diagrams. Springer, 2011, pp. 171–175. [43] J. R. Rice, “Tchebycheff approximation in several variables,” Transactions of the American Mathematical Society, pp. 444–466, 1963. [44] Z. Ditzian and V. Totik, Moduli of smoothness. Springer, 1987. [45] V. Totik, Polynomial Approximation on Polytopes. Memoirs of the American Mathematical Society, 2013, vol. 232. [46] F. Dai and Y. Xu, Approximation theory and harmonic analysis on spheres and balls. Springer, 2013. [47] E. Y. Remez, “Sur la de´termination des polynoˆmes d’approximation de degre´ donne´e,” Comm. Soc. Math. Kharkov, vol. 10, pp. 41–63, 1934. [48] Chebfun Version 5, The Chebfun Development Team, 2014, http://www.chebfun.org/. [49] A. Haar, “Die minkowskische geometrie und die anna¨herung an stetige funktionen,” Mathematische Annalen, vol. 78, no. 1, pp. 294–311, 1917. [50] O. Lepski, A. Nemirovski, and V. Spokoiny, “On estimation of the Lr norm of a regression function,” Probability theory and related ﬁelds, vol. 113, no. 2, pp. 221–253, 1999. [51] J. Jiao, Y. Han, and T. Weissman, “Minimax estimation of divergence functions,” in preparation. [52] M. Qazi and Q. Rahman, “Some coefﬁcient estimates for polynomials on the unit interval,” Serdica Math. J, vol. 33, pp. 449–474, 2007. [53] M. Mitzenmacher and E. Upfal, Probability and computing: Randomized algorithms and probabilistic analysis. Cambridge University Press, 2005. [54] J. C. Mason and D. C. Handscomb, Chebyshev polynomials. CRC Press, 2002. [55] A. Wald, Statistical decision functions. Wiley, 1950. ##LTLine## ##LTLine##

label: reference

text: C.

text: M.

text: Bishop,

text: “Pattern

text: recognition,”

text: Machine

text: Learning,

text: vol.

text: D.

text: P.

text: Kingma

text: and

text: M.

text: Welling,

text: “Auto-encoding

text: variational

text: bayes,”

text: arXiv

text: preprint

text: Q.

text: Wang,

text: S.

text: R.

text: Kulkarni,

text: and

text: S.

text: Verdu´,

text: “Divergence

text: estimation

text: of

text: continuous

text: distributions

text: based

text: on

text: data-dependent

text: partitions,”

text: Information

text: Theory,

text: IEEE

text: Transactions

text: on,

text: vol.

text: no.

text: pp.

text: Y.

text: K.

text: Lee

text: and

text: B.

text: U.

text: Park,

text: “Estimation

text: of

text: Kullback–Leibler

text: divergence

text: by

text: local

text: likelihood,”

text: Annals

text: of

text: the

text: Institute

text: of

text: Statistical

text: Mathematics,

text: vol.

text: no.

text: pp.

text: A.

text: Gretton,

text: K.

text: M.

text: Borgwardt,

text: M.

text: Rasch,

text: B.

text: Scho¨lkopf,

text: and

text: A.

text: J.

text: Smola,

text: “A

text: kernel

text: method

text: for

text: the

text: two-sample-problem,”

text: in

text: Advances

text: in

text: neural

text: information

text: processing

text: systems,

text: pp.

text: F.

text: Pe´rez-Cruz,

text: “Kullback-Leibler

text: divergence

text: estimation

text: of

text: continuous

text: distributions,”

text: in

text: Information

text: Theory,

text: ISIT

text: IEEE

text: International

text: Symposium

text: on.

text: IEEE,

text: pp.

text: Q.

text: Wang,

text: S.

text: R.

text: Kulkarni,

text: and

text: S.

text: Verdu´,

text: “Divergence

text: estimation

text: for

text: multidimensional

text: densities

text: via-nearest-neighbor

text: distances,”

text: Information

text: Theory,

text: IEEE

text: Transactions

text: on,

text: vol.

text: no.

text: pp.

text: X.

text: Nguyen,

text: M.

text: J.

text: Wainwright,

text: and

text: M.

text: I.

text: Jordan,

text: “Estimating

text: divergence

text: functionals

text: and

text: the

text: likelihood

text: ratio

text: by

text: convex

text: risk

text: minimization,”

text: Information

text: Theory,

text: IEEE

text: Transactions

text: on,

text: vol.

text: no.

text: pp.

text: H.

text: Cai,

text: S.

text: R.

text: Kulkarni,

text: and

text: S.

text: Verdu´,

text: “Universal

text: divergence

text: estimation

text: for

text: ﬁnite-alphabet

text: sources,”

text: Information

text: Theory,

text: IEEE

text: Transactions

text: on,

text: vol.

text: no.

text: pp.

text: Z.

text: Zhang

text: and

text: M.

text: Grabchak,

text: “Nonparametric

text: estimation

text: of

text: Ku¨llback-Leibler

text: divergence,”

text: Neural

text: computation,

text: vol.

text: no.

text: pp.

text: A.

text: W.

text: Van

text: der

text: Vaart,

text: Asymptotic

text: statistics.

text: Cambridge

text: university

text: press,

text: vol.

text: J.

text: Jiao,

text: Y.

text: Han,

text: and

text: T.

text: Weissman,

text: “Minimax

text: estimation

text: of

text: the

text: distance,”

text: in

text: IEEE

text: International

text: Symposium

text: on

text: Information

text: Theory

text: (ISIT).

text: IEEE,

text: pp.

text: Y.

text: Bu,

text: S.

text: Zou,

text: Y.

text: Liang,

text: and

text: V.

text: V.

text: Veeravalli,

text: “Estimation

text: of

text: KL

text: divergence

text: between

text: large-alphabet

text: distributions,”

text: in

text: IEEE

text: International

text: Symposium

text: on

text: Information

text: Theory

text: (ISIT).

text: IEEE,

text: pp.

text: “Estimation

text: of

text: KL

text: divergence:

text: Optimal

text: minimax

text: rate,”

text: arXiv

text: preprint

text: T.

text: T.

text: Cai

text: and

text: M.

text: G.

text: Low,

text: “Testing

text: composite

text: hypotheses,

text: Hermite

text: polynomials

text: and

text: optimal

text: estimation

text: of

text: a

text: nonsmooth

text: functional,”

text: The

text: Annals

text: of

text: Statistics,

text: vol.

text: no.

text: pp.

text: G.

text: Valiant

text: and

text: P.

text: Valiant,

text: “The

text: power

text: of

text: linear

text: estimators,”

text: in

text: Foundations

text: of

text: Computer

text: Science

text: (FOCS),

text: IEEE

text: Annual

text: Symposium

text: on.

text: IEEE,

text: pp.

text: P.

text: Valiant

text: and

text: G.

text: Valiant,

text: “Estimating

text: the

text: unseen:

text: improved

text: estimators

text: for

text: entropy

text: and

text: other

text: properties,”

text: in

text: Advances

text: in

text: Neural

text: Information

text: Processing

text: Systems,

text: pp.

text: Y.

text: Wu

text: and

text: P.

text: Yang,

text: “Minimax

text: rates

text: of

text: entropy

text: estimation

text: on

text: large

text: alphabets

text: via

text: best

text: polynomial

text: approximation,”

text: arXiv

text: preprint

text: J.

text: Acharya,

text: A.

text: Orlitsky,

text: A.

text: T.

text: Suresh,

text: and

text: H.

text: Tyagi,

text: “The

text: complexity

text: of

text: estimating

text: Re´nyi

text: entropy.”

text: SODA,

text: Y.

text: Wu

text: and

text: P.

text: Yang,

text: “Chebyshev

text: polynomials,

text: moment

text: matching,

text: and

text: optimal

text: estimation

text: of

text: the

text: unseen,”

text: arXiv

text: preprint

text: Y.

text: Han,

text: J.

text: Jiao,

text: R.

text: Mukherjee,

text: and

text: T.

text: Weissman,

text: “Optimal

text: estimation

text: of

text: Lr

text: norm

text: of

text: functions

text: in

text: Gaussian

text: white

text: noise,”

text: in

text: preparation,

text: G.

text: A.

text: Miller,

text: “Note

text: on

text: the

text: bias

text: of

text: information

text: estimates,”

text: Information

text: Theory

text: in

text: Psychology:

text: Problems

text: and

text: Methods,

text: vol.

text: pp.

text: A.

text: Carlton,

text: “On

text: the

text: bias

text: of

text: information

text: estimates.”

text: Psychological

text: Bulletin,

text: vol.

text: no.

text: p.

text: A.

text: Nemirovski,

text: “Topics

text: in

text: non-parametric,”

text: Ecole

text: d’Ete´

text: de

text: Probabilite´s

text: de

text: Saint-Flour,

text: vol.

text: p.

text: M.

text: Mitzenmacher

text: and

text: E.

text: Upfal,

text: Probability

text: and

text: computing:

text: Randomized

text: algorithms

text: and

text: probabilistic

text: analysis.

text: Cambridge

text: University

text: Press,

text: J.

text: Jiao,

text: K.

text: Venkat,

text: Y.

text: Han,

text: and

text: T.

text: Weissman,

text: “Non-asymptotic

text: theory

text: for

text: the

text: plug-in

text: rule

text: in

text: functional

text: estimation,”

text: arXiv

text: preprint

text: D.

text: Braess

text: and

text: T.

text: Sauer,

text: “Bernstein

text: polynomials

text: and

text: learning

text: theory,”

text: Journal

text: of

text: Approximation

text: Theory,

text: vol.

text: no.

text: pp.

text: A.

text: Tsybakov,

text: “Aggregation

text: and

text: high-dimensional

text: statistics,”

text: Lecture

text: notes

text: for

text: the

text: course

text: given

text: at

text: the

text: E´cole

text: d’e´te´

text: de

text: Probabilite´s

text: in

text: Saint-Flour,

text: URL

text: crest.

text: notes

text: SFlour.

text: pdf,

text: vol.

text: p.

text: C.

text: S.

text: Withers,

text: “Bias

text: reduction

text: by

text: Taylor

text: series,”

text: Communications

text: in

text: Statistics-Theory

text: and

text: Methods,

text: vol.

text: no.

text: pp.

text: G.

text: Peccati

text: and

text: M.

text: S.

text: Taqqu,

text: “Some

text: facts

text: about

text: Charlier

text: polynomials,”

text: in

text: Wiener

text: Chaos:

text: Moments,

text: Cumulants

text: and

text: Diagrams.

text: Springer,

text: pp.

text: J.

text: R.

text: Rice,

text: “Tchebycheff

text: approximation

text: in

text: several

text: variables,”

text: Transactions

text: of

text: the

text: American

text: Mathematical

text: Society,

text: pp.

text: Z.

text: Ditzian

text: and

text: V.

text: Totik,

text: Moduli

text: of

text: smoothness.

text: Springer,

text: V.

text: Totik,

text: Polynomial

text: Approximation

text: on

text: Polytopes.

text: Memoirs

text: of

text: the

text: American

text: Mathematical

text: Society,

text: vol.

text: F.

text: Dai

text: and

text: Y.

text: Xu,

text: Approximation

text: theory

text: and

text: harmonic

text: analysis

text: on

text: spheres

text: and

text: balls.

text: Springer,

text: E.

text: Y.

text: Remez,

text: “Sur

text: la

text: de´termination

text: des

text: polynoˆmes

text: d’approximation

text: de

text: degre´

text: donne´e,”

text: Comm.

text: Soc.

text: Math.

text: Kharkov,

text: vol.

text: pp.

text: Chebfun

text: Version

text: The

text: Chebfun

text: Development

text: Team,

text: A.

text: Haar,

text: “Die

text: minkowskische

text: geometrie

text: und

text: die

text: anna¨herung

text: an

text: stetige

text: funktionen,”

text: Mathematische

text: Annalen,

text: vol.

text: no.

text: pp.

text: O.

text: Lepski,

text: A.

text: Nemirovski,

text: and

text: V.

text: Spokoiny,

text: “On

text: estimation

text: of

text: the

text: Lr

text: norm

text: of

text: a

text: regression

text: function,”

text: Probability

text: theory

text: and

text: related

text: ﬁelds,

text: vol.

text: no.

text: pp.

text: J.

text: Jiao,

text: Y.

text: Han,

text: and

text: T.

text: Weissman,

text: “Minimax

text: estimation

text: of

text: divergence

text: functions,”

text: in

text: preparation.

text: M.

text: Qazi

text: and

text: Q.

text: Rahman,

text: “Some

text: coefﬁcient

text: estimates

text: for

text: polynomials

text: on

text: the

text: unit

text: interval,”

text: Serdica

text: Math.

text: J,

text: vol.

text: pp.

text: M.

text: Mitzenmacher

text: and

text: E.

text: Upfal,

text: Probability

text: and

text: computing:

text: Randomized

text: algorithms

text: and

text: probabilistic

text: analysis.

text: Cambridge

text: University

text: Press,

text: J.

text: C.

text: Mason

text: and

text: D.

text: C.

text: Handscomb,

text: Chebyshev

text: polynomials.

text: CRC

text: Press,

text: A.

text: Wald,

text: Statistical

text: decision

text: functions.

text: Wiley,

text: ##LTLine##

text: ##LTLine##