Minimax Estimation of KL Divergence between Discrete Distributions

Yanjun Han, Jiantao Jiao, Tsachy Weissman

Abstract

We study the minimax estimation of $\alpha$-divergences between discrete distributions for integer $\alpha\ge 1$, which include the Kullback--Leibler divergence and the $\chi^2$-divergences as special examples. Dropping the usual theoretical tricks to acquire independence, we construct the first minimax rate-optimal estimator which does not require any Poissonization, sample splitting, or explicit construction of approximating polynomials. The estimator uses a hybrid approach which solves a problem-independent linear program based on moment matching in the non-smooth regime, and applies a problem-dependent bias-corrected plug-in estimator in the smooth regime, with a soft decision boundary between these regimes.
BibTeX
@misc{han2016minimax,
  author = {Yanjun Han and Jiantao Jiao and Tsachy Weissman},
  title = {{Minimax Estimation of KL Divergence between Discrete Distributions}},
  year = {2016},
  eprint = {1605.09124},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1605.09124},
}
Figure