Minimax estimation of the L1 distance

Jiantao Jiao, Yanjun Han, Tsachy Weissman

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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).

Original languageEnglish (US)
Title of host publicationProceedings - ISIT 2016; 2016 IEEE International Symposium on Information Theory
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages750-754
Number of pages5
ISBN (Electronic)9781509018062
DOIs
StatePublished - Aug 10 2016
Event2016 IEEE International Symposium on Information Theory, ISIT 2016 - Barcelona, Spain
Duration: Jul 10 2016Jul 15 2016

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
Volume2016-August
ISSN (Print)2157-8095

Other

Other2016 IEEE International Symposium on Information Theory, ISIT 2016
Country/TerritorySpain
CityBarcelona
Period7/10/167/15/16

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Information Systems
  • Modeling and Simulation
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Minimax estimation of the L1 distance'. Together they form a unique fingerprint.

Cite this