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 -