Minimax Estimation of Discrete Distributions Under <inline-formula> <tex-math notation="LaTeX">\ell _{1} </tex-math></inline-formula> Loss

DOI10.1109/TIT.2015.2478816MaRDI QIDQ2977141zbMATH OpenFDO

Authors Yanjun Han, Jiantao Jiao, Tsachy Weissman

Publication date 28 April 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1411.1467

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Abstract: We analyze the problem of discrete distribution estimation under $el{l}_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/lnn$, while the asymptotic minimax risk is $H/lnn$. Moreover, Moreover, we show that a hard-thresholding estimator oblivious to the unknown upper bound $H$, is asymptotically minimax. However, if we constrain the estimates to lie in the simplex of probability distributions, then the asymptotic minimax risk is again $2H/lnn$. We draw connections between our work and the literature on density estimation, entropy estimation, total variation distance ($el{l}_1$ divergence) estimation, joint distribution estimation in stochastic processes, normal mean estimation, and adaptive estimation.

Recommendations

• Minimax Estimation of Functionals of Discrete Distributions
• Minimax estimation of the bounded parameter of some discrete distributions under LINEX loss function
• Minimax estimation of a bounded parameter of a discrete distribution
• scientific article; zbMATH DE number 224060
• scientific article; zbMATH DE number 5661284
• Minimax estimation of parameter for a class of scale distributions under different loss functions
• scientific article; zbMATH DE number 503315
• Minimax estimation of the parameters of a class of distributions under the squared log error and MLINEX loss functions
• scientific article; zbMATH DE number 4133294

Cited in

(9)

• Statistical estimation of ergodic Markov chain kernel over discrete state space
• Learning Markov models via low-rank optimization
• Approximate profile maximum likelihood
• Minimax rate of distribution estimation on unknown submanifolds under adversarial losses
• Frontiers of statistics and machine learning. Abstracts from the workshop held March 23--28, 2025
• Minimax learning of ergodic Markov chains
• On the statistical complexity of sample amplification
• Estimation of discrete distributions in relative entropy, and the deviations of the missing mass
• Asymptotic analysis of the jittering kernel density estimator

This page was built for publication: Minimax Estimation of Discrete Distributions Under <inline-formula> <tex-math notation="LaTeX">$\ell _{1}$ </tex-math></inline-formula> Loss

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2977141)