Estimation of KL Divergence: Optimal Minimax Rate

DOI10.1109/TIT.2018.2805844MaRDI QIDQ4569211zbMATH OpenOpenAlexFDO

Authors Yuheng Bu, Shaofeng Zou, Yingbin Liang, Venugopal V. Veeravalli

Publication date 27 June 2018

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

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

Mathematics Subject Classification ID

Nonparametric estimation (62G05) Measures of information, entropy (94A17)

Abstract: The problem of estimating the Kullback-Leibler divergence $D(P|Q)$ between two unknown distributions $P$ and $Q$ is studied, under the assumption that the alphabet size $k$ of the distributions can scale to infinity. The estimation is based on $m$ independent samples drawn from $P$ and $n$ independent samples drawn from $Q$. It is first shown that there does not exist any consistent estimator that guarantees asymptotically small worst-case quadratic risk over the set of all pairs of distributions. A restricted set that contains pairs of distributions, with density ratio bounded by a function $f(k)$ is further considered. {An augmented plug-in estimator is proposed, and its worst-case quadratic risk is shown to be within a constant factor of $(frackm+frackf(k)n{)}^2+fraclo{g}^{2}f(k)m+fracf(k)n$, if $m$ and $n$ exceed a constant factor of $k$ and $kf(k)$, respectively.} Moreover, the minimax quadratic risk is characterized to be within a constant factor of $(frackmlogk+frackf(k)nlogk{)}^2+fraclo{g}^{2}f(k)m+fracf(k)n$, if $m$ and $n$ exceed a constant factor of $k/log(k)$ and $kf(k)/logk$, respectively. The lower bound on the minimax quadratic risk is characterized by employing a generalized Le Cam's method. A minimax optimal estimator is then constructed by employing both the polynomial approximation and the plug-in approaches.

Recommendations

• Minimax Optimal Estimation of KL Divergence for Continuous Distributions
• Minimization of the Kullback-Leibler divergence over a log-normal exponential arc
• Minimum \(f\)-divergence estimators and quasi-likelihood functions
• Optimal rates and constants in \(L_ 2\)-minimax estimation of probability density functions
• Parameter estimation based on cumulative Kullback-Leibler divergence
• Nonparametric estimation of Kullback-Leibler divergence
• Minimum \(K_\phi\)-divergence estimator.
• Optimal robust estimates using the Kullback-Leibler divergence

Cited in

(7)

• Minimax Optimal Estimation of KL Divergence for Continuous Distributions
• Optimal rates of entropy estimation over Lipschitz balls
• Embedding distributional data
• Optimal Estimation of Wasserstein Distance on a Tree With an Application to Microbiome Studies
• Comparing and Weighting Imperfect Models Using D-Probabilities
• Correcting convexity bias in function and functional estimate
• Approximate profile maximum likelihood

This page was built for publication: Estimation of KL Divergence: Optimal Minimax Rate

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