Minimax estimation of discrete distributions

Yanjun Han; Jiantao Jiao; Tsachy Weissman

doi:10.1109/ISIT.2015.7282864

Minimax estimation of discrete distributions

Yanjun Han, Jiantao Jiao, Tsachy Weissman

Mathematics

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

Abstract

We analyze the problem of discrete distribution estimation under ℓ¹ loss. We provide non-asymptotic upper and lower bounds on the maximum risk of the empirical distribution (the maximum likelihood estimator), and the minimax risk in regimes where the alphabet size S may grow with the number of observations n. We show that among distributions with bounded entropy H, the asymptotic maximum risk for the empirical distribution is 2H / ln n, while the asymptotic minimax risk is H / ln n. Moreover, a hard-thresholding estimator, whose threshold does not depend on the unknown upper bound H, is asymptotically minimax. We draw connections between our work and the literature on density estimation, entropy estimation, total variation distance (ℓ¹ divergence) estimation, joint distribution estimation in stochastic processes, normal mean estimation, and adaptive estimation.

Original language	English (US)
Title of host publication	Proceedings - 2015 IEEE International Symposium on Information Theory, ISIT 2015
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	2291-2295
Number of pages	5
ISBN (Electronic)	9781467377041
DOIs	https://doi.org/10.1109/ISIT.2015.7282864
State	Published - Sep 28 2015
Event	IEEE International Symposium on Information Theory, ISIT 2015 - Hong Kong, Hong Kong Duration: Jun 14 2015 → Jun 19 2015

Publication series

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

Other

Other	IEEE International Symposium on Information Theory, ISIT 2015
Country/Territory	Hong Kong
City	Hong Kong
Period	6/14/15 → 6/19/15

ASJC Scopus subject areas

Theoretical Computer Science
Information Systems
Modeling and Simulation
Applied Mathematics

Access to Document

10.1109/ISIT.2015.7282864

Cite this

Han, Y., Jiao, J., & Weissman, T. (2015). Minimax estimation of discrete distributions. In Proceedings - 2015 IEEE International Symposium on Information Theory, ISIT 2015 (pp. 2291-2295). Article 7282864 (IEEE International Symposium on Information Theory - Proceedings; Vol. 2015-June). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ISIT.2015.7282864

Minimax estimation of discrete distributions. / Han, Yanjun; Jiao, Jiantao; Weissman, Tsachy.
Proceedings - 2015 IEEE International Symposium on Information Theory, ISIT 2015. Institute of Electrical and Electronics Engineers Inc., 2015. p. 2291-2295 7282864 (IEEE International Symposium on Information Theory - Proceedings; Vol. 2015-June).

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

Han, Y, Jiao, J & Weissman, T 2015, Minimax estimation of discrete distributions. in Proceedings - 2015 IEEE International Symposium on Information Theory, ISIT 2015., 7282864, IEEE International Symposium on Information Theory - Proceedings, vol. 2015-June, Institute of Electrical and Electronics Engineers Inc., pp. 2291-2295, IEEE International Symposium on Information Theory, ISIT 2015, Hong Kong, Hong Kong, 6/14/15. https://doi.org/10.1109/ISIT.2015.7282864

@inproceedings{a0c0dea2bf5343b8a70b6d0336c2f1f9,

title = "Minimax estimation of discrete distributions",

abstract = "We analyze the problem of discrete distribution estimation under ℓ1 loss. We provide non-asymptotic upper and lower bounds on the maximum risk of the empirical distribution (the maximum likelihood estimator), and the minimax risk in regimes where the alphabet size S may grow with the number of observations n. We show that among distributions with bounded entropy H, the asymptotic maximum risk for the empirical distribution is 2H / ln n, while the asymptotic minimax risk is H / ln n. Moreover, a hard-thresholding estimator, whose threshold does not depend on the unknown upper bound H, is asymptotically minimax. We draw connections between our work and the literature on density estimation, entropy estimation, total variation distance (ℓ1 divergence) estimation, joint distribution estimation in stochastic processes, normal mean estimation, and adaptive estimation.",

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

note = "Publisher Copyright: {\textcopyright} 2015 IEEE.; IEEE International Symposium on Information Theory, ISIT 2015 ; Conference date: 14-06-2015 Through 19-06-2015",

year = "2015",

month = sep,

day = "28",

doi = "10.1109/ISIT.2015.7282864",

language = "English (US)",

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

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

pages = "2291--2295",

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

}

TY - GEN

T1 - Minimax estimation of discrete distributions

AU - Han, Yanjun

AU - Jiao, Jiantao

AU - Weissman, Tsachy

PY - 2015/9/28

Y1 - 2015/9/28

N2 - We analyze the problem of discrete distribution estimation under ℓ1 loss. We provide non-asymptotic upper and lower bounds on the maximum risk of the empirical distribution (the maximum likelihood estimator), and the minimax risk in regimes where the alphabet size S may grow with the number of observations n. We show that among distributions with bounded entropy H, the asymptotic maximum risk for the empirical distribution is 2H / ln n, while the asymptotic minimax risk is H / ln n. Moreover, a hard-thresholding estimator, whose threshold does not depend on the unknown upper bound H, is asymptotically minimax. We draw connections between our work and the literature on density estimation, entropy estimation, total variation distance (ℓ1 divergence) estimation, joint distribution estimation in stochastic processes, normal mean estimation, and adaptive estimation.

AB - We analyze the problem of discrete distribution estimation under ℓ1 loss. We provide non-asymptotic upper and lower bounds on the maximum risk of the empirical distribution (the maximum likelihood estimator), and the minimax risk in regimes where the alphabet size S may grow with the number of observations n. We show that among distributions with bounded entropy H, the asymptotic maximum risk for the empirical distribution is 2H / ln n, while the asymptotic minimax risk is H / ln n. Moreover, a hard-thresholding estimator, whose threshold does not depend on the unknown upper bound H, is asymptotically minimax. We draw connections between our work and the literature on density estimation, entropy estimation, total variation distance (ℓ1 divergence) estimation, joint distribution estimation in stochastic processes, normal mean estimation, and adaptive estimation.

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

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

U2 - 10.1109/ISIT.2015.7282864

DO - 10.1109/ISIT.2015.7282864

M3 - Conference contribution

AN - SCOPUS:84983163199

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 2291

EP - 2295

BT - Proceedings - 2015 IEEE International Symposium on Information Theory, ISIT 2015

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - IEEE International Symposium on Information Theory, ISIT 2015

Y2 - 14 June 2015 through 19 June 2015

ER -

Minimax estimation of discrete distributions

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this