Minimax estimation of the L1 distance

Jiantao Jiao; Yanjun Han; Tsachy Weissman

doi:10.1109/ISIT.2016.7541399

Minimax estimation of the L₁ distance

Jiantao Jiao, Yanjun Han, Tsachy Weissman

Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We consider the problem of estimating the L₁ distance between two discrete probability measures P and Q from empirical data in a nonasymptotic and large alphabet setting. We construct minimax rate-optimal estimators for L₁(P,Q) when Q is either known or unknown, and show that the performance of the optimal estimators with n samples is essentially that of the Maximum Likelihood Estimators (MLE) with n ln n samples. Hence, we demonstrate that the effective sample size enlargement phenomenon, discovered and discussed in Jiao et al. (2015), holds for this problem as well. However, the construction of optimal estimators for L₁(P,Q) requires new techniques and insights outside the scope of the Approximation methodology of functional estimation in Jiao et al. (2015).

Original language	English (US)
Title of host publication	Proceedings - ISIT 2016; 2016 IEEE International Symposium on Information Theory
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	750-754
Number of pages	5
ISBN (Electronic)	9781509018062
DOIs	https://doi.org/10.1109/ISIT.2016.7541399
State	Published - Aug 10 2016
Event	2016 IEEE International Symposium on Information Theory, ISIT 2016 - Barcelona, Spain Duration: Jul 10 2016 → Jul 15 2016

Publication series

Name	IEEE International Symposium on Information Theory - Proceedings
Volume	2016-August
ISSN (Print)	2157-8095

Other

Other	2016 IEEE International Symposium on Information Theory, ISIT 2016
Country/Territory	Spain
City	Barcelona
Period	7/10/16 → 7/15/16

ASJC Scopus subject areas

Theoretical Computer Science
Information Systems
Modeling and Simulation
Applied Mathematics

Access to Document

10.1109/ISIT.2016.7541399

Cite this

Jiao, J., Han, Y., & Weissman, T. (2016). Minimax estimation of the L₁ distance. In Proceedings - ISIT 2016; 2016 IEEE International Symposium on Information Theory (pp. 750-754). Article 7541399 (IEEE International Symposium on Information Theory - Proceedings; Vol. 2016-August). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ISIT.2016.7541399

Minimax estimation of the L₁ distance. / Jiao, Jiantao; Han, Yanjun; Weissman, Tsachy.
Proceedings - ISIT 2016; 2016 IEEE International Symposium on Information Theory. Institute of Electrical and Electronics Engineers Inc., 2016. p. 750-754 7541399 (IEEE International Symposium on Information Theory - Proceedings; Vol. 2016-August).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Jiao, J, Han, Y & Weissman, T 2016, Minimax estimation of the L₁ distance. in Proceedings - ISIT 2016; 2016 IEEE International Symposium on Information Theory., 7541399, IEEE International Symposium on Information Theory - Proceedings, vol. 2016-August, Institute of Electrical and Electronics Engineers Inc., pp. 750-754, 2016 IEEE International Symposium on Information Theory, ISIT 2016, Barcelona, Spain, 7/10/16. https://doi.org/10.1109/ISIT.2016.7541399

@inproceedings{dc92d97b96b1444eab7bb2b6530f8611,

title = "Minimax estimation of the L1 distance",

abstract = "We consider the problem of estimating the L1 distance between two discrete probability measures P and Q from empirical data in a nonasymptotic and large alphabet setting. We construct minimax rate-optimal estimators for L1(P,Q) when Q is either known or unknown, and show that the performance of the optimal estimators with n samples is essentially that of the Maximum Likelihood Estimators (MLE) with n ln n samples. Hence, we demonstrate that the effective sample size enlargement phenomenon, discovered and discussed in Jiao et al. (2015), holds for this problem as well. However, the construction of optimal estimators for L1(P,Q) requires new techniques and insights outside the scope of the Approximation methodology of functional estimation in Jiao et al. (2015).",

author = "Jiantao Jiao and Yanjun Han and Tsachy Weissman",

note = "Publisher Copyright: {\textcopyright} 2016 IEEE.; 2016 IEEE International Symposium on Information Theory, ISIT 2016 ; Conference date: 10-07-2016 Through 15-07-2016",

year = "2016",

month = aug,

day = "10",

doi = "10.1109/ISIT.2016.7541399",

language = "English (US)",

series = "IEEE International Symposium on Information Theory - Proceedings",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "750--754",

booktitle = "Proceedings - ISIT 2016; 2016 IEEE International Symposium on Information Theory",

}

TY - GEN

T1 - Minimax estimation of the L1 distance

AU - Jiao, Jiantao

AU - Han, Yanjun

AU - Weissman, Tsachy

PY - 2016/8/10

Y1 - 2016/8/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. We construct minimax rate-optimal estimators for L1(P,Q) when Q is either known or unknown, and show that the performance of the optimal estimators with n samples is essentially that of the Maximum Likelihood Estimators (MLE) with n ln n samples. Hence, we demonstrate that the effective sample size enlargement phenomenon, discovered and discussed in Jiao et al. (2015), holds for this problem as well. However, the construction of optimal estimators for L1(P,Q) requires new techniques and insights outside the scope of the Approximation methodology of functional estimation in Jiao et al. (2015).

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. We construct minimax rate-optimal estimators for L1(P,Q) when Q is either known or unknown, and show that the performance of the optimal estimators with n samples is essentially that of the Maximum Likelihood Estimators (MLE) with n ln n samples. Hence, we demonstrate that the effective sample size enlargement phenomenon, discovered and discussed in Jiao et al. (2015), holds for this problem as well. However, the construction of optimal estimators for L1(P,Q) requires new techniques and insights outside the scope of the Approximation methodology of functional estimation in Jiao et al. (2015).

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

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

U2 - 10.1109/ISIT.2016.7541399

DO - 10.1109/ISIT.2016.7541399

M3 - Conference contribution

AN - SCOPUS:84985993094

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 750

EP - 754

BT - Proceedings - ISIT 2016; 2016 IEEE International Symposium on Information Theory

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2016 IEEE International Symposium on Information Theory, ISIT 2016

Y2 - 10 July 2016 through 15 July 2016

ER -