TY - JOUR

T1 - Minimax estimation of the L1 distance

AU - Jiao, Jiantao

AU - Han, Yanjun

AU - Weissman, Tsachy

N1 - Funding Information:
Manuscript received May 7, 2017; revised April 29, 2018; accepted May 26, 2018. Date of publication June 11, 2018; date of current version September 13, 2018. This work was supported by the Center for Science of Information (CSoI), which is an NSF Science and Technology Center, under Grant CCF-0939370. The work of J. Jiao was supported by the 3Com Stanford Graduate Fellowship. This paper was presented in part at the 2016 IEEE International Symposium on Information Theory.
Publisher Copyright:
© 2018 IEEE.

PY - 2018/10

Y1 - 2018/10

N2 - We consider the problem of estimating the L1 distance between two discrete probability measures P and Q from empirical data in a nonasymptotic and large alphabet setting. When Q is known and one obtains n samples from P, we show that for every Q, the minimax rate-optimal estimator with n samples achieves performance comparable to that of the maximum likelihood estimator with nlnn samples. When both P and Q are unknown, we construct minimax rate-optimal estimators, whose worst case performance is essentially that of the known Q case with Q being uniform, implying that Q being uniform is essentially the most difficult case. The effective sample size enlargement phenomenon, identified by Jiao et al., holds both in the known Q case for every Q and the Q unknown case. However, the construction of optimal estimators for |P-Q|1 requires new techniques and insights beyond the approximation-based method of functional estimation by Jiao et al.

AB - We consider the problem of estimating the L1 distance between two discrete probability measures P and Q from empirical data in a nonasymptotic and large alphabet setting. When Q is known and one obtains n samples from P, we show that for every Q, the minimax rate-optimal estimator with n samples achieves performance comparable to that of the maximum likelihood estimator with nlnn samples. When both P and Q are unknown, we construct minimax rate-optimal estimators, whose worst case performance is essentially that of the known Q case with Q being uniform, implying that Q being uniform is essentially the most difficult case. The effective sample size enlargement phenomenon, identified by Jiao et al., holds both in the known Q case for every Q and the Q unknown case. However, the construction of optimal estimators for |P-Q|1 requires new techniques and insights beyond the approximation-based method of functional estimation by Jiao et al.

KW - Divergence estimation

KW - functional estimation

KW - high-dimensional statistics

KW - multivariate approximation theory

KW - optimal classification error

KW - total variation distance

UR - http://www.scopus.com/inward/record.url?scp=85048460173&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85048460173&partnerID=8YFLogxK

U2 - 10.1109/TIT.2018.2846245

DO - 10.1109/TIT.2018.2846245

M3 - Article

AN - SCOPUS:85048460173

SN - 0018-9448

VL - 64

SP - 6672

EP - 6706

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

IS - 10

M1 - 8379458

ER -