On the complexity of estimating Rènyi divergences

M. Skórski, in:, 2017 IEEE International Symposium on Information Theory (ISIT), IEEE, 2017, p. 8006529.


Conference Paper | Published | English
Department
Abstract
This paper studies the complexity of estimating Rényi divergences of discrete distributions: p observed from samples and the baseline distribution q known a priori. Extending the results of Acharya et al. (SODA'15) on estimating Rényi entropy, we present improved estimation techniques together with upper and lower bounds on the sample complexity. We show that, contrarily to estimating Rényi entropy where a sublinear (in the alphabet size) number of samples suffices, the sample complexity is heavily dependent on events occurring unlikely in q, and is unbounded in general (no matter what an estimation technique is used). For any divergence of integer order bigger than 1, we provide upper and lower bounds on the number of samples dependent on probabilities of p and q (the lower bounds hold for non-integer orders as well). We conclude that the worst-case sample complexity is polynomial in the alphabet size if and only if the probabilities of q are non-negligible. This gives theoretical insights into heuristics used in the applied literature to handle numerical instability, which occurs for small probabilities of q. Our result shows that they should be handled with care not only because of numerical issues, but also because of a blow up in the sample complexity.
Publishing Year
Date Published
2017-08-09
Proceedings Title
2017 IEEE International Symposium on Information Theory (ISIT)
Article Number
8006529
Conference
ISIT: International Symposium on Information Theory
Conference Location
Aachen, Germany
Conference Date
2017-06-25 – 2017-06-30
IST-REx-ID

Cite this

Skórski M. On the complexity of estimating Rènyi divergences. In: 2017 IEEE International Symposium on Information Theory (ISIT). IEEE; 2017:8006529. doi:10.1109/isit.2017.8006529
Skórski, M. (2017). On the complexity of estimating Rènyi divergences. In 2017 IEEE International Symposium on Information Theory (ISIT) (p. 8006529). Aachen, Germany: IEEE. https://doi.org/10.1109/isit.2017.8006529
Skórski, Maciej. “On the Complexity of Estimating Rènyi Divergences.” In 2017 IEEE International Symposium on Information Theory (ISIT), 8006529. IEEE, 2017. https://doi.org/10.1109/isit.2017.8006529.
M. Skórski, “On the complexity of estimating Rènyi divergences,” in 2017 IEEE International Symposium on Information Theory (ISIT), Aachen, Germany, 2017, p. 8006529.
Skórski M. 2017. On the complexity of estimating Rènyi divergences. 2017 IEEE International Symposium on Information Theory (ISIT). ISIT: International Symposium on Information Theory 8006529.
Skórski, Maciej. “On the Complexity of Estimating Rènyi Divergences.” 2017 IEEE International Symposium on Information Theory (ISIT), IEEE, 2017, p. 8006529, doi:10.1109/isit.2017.8006529.

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data IST Research Explorer

Sources

arXiv 1702.01666

Search this title in

Google Scholar
ISBN Search