On the complexity of estimating Rènyi divergences
On the complexity of estimating Rènyi divergences
复制标题
关于估计 Rènyi 散度的复杂性
DOI：
10.1109/isit.2017.8006529
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
M. Skorski
中科院分区：
文献类型：
--
作者：
M. Skorski
本文研究了估计离散分布的Rényi散度的复杂性：从样本中观察到的P和已知的基线分布Q。推广了Acharya等人的结果。(SODA‘15)关于Rényi熵的估计，我们给出了改进的估计方法以及样本复杂度的上下界。我们证明，与估计Rényi熵相反，在次线性(按字母表大小)样本数量足够的情况下，样本复杂性严重依赖于在Q中不太可能发生的事件，并且通常是无界的(无论使用什么估计技术)。对于任何大于1的整数阶偏差，我们给出了依赖于p和q的概率的样本数目的上界和下界(下界对于非整数阶也是成立的)。我们得出结论：最坏情况下的样本复杂度是字母表大小的多项式当且仅当q的概率是不可忽略的。这为应用文献中用来处理数值不稳定性的启发式提供了理论上的见解。我们的结果表明，应该谨慎处理它们，不仅是因为数值问题，还因为样本复杂性的爆炸性。
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.
离散分布之间 KL 散度的极小最大速率最优估计。
DOI：
--
发表时间：
2016
期刊：
International Symposium on Information Theory and its Applications. International Symposium on Information Theory and its Applications
影响因子：
--
作者：
Han,Yanjun;Jiao,Jiantao;Weissman,Tsachy
通讯作者：
Weissman,Tsachy