A CLT and tight lower bounds for estimating entropy
A CLT and tight lower bounds for estimating entropy
复制标题
CLT 和估计熵的严格下界
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Paul Valiant
中科院分区：
文献类型：
--
作者：
G. Valiant;Paul Valiant
我们证明了两个新的多元中心限制定理；在地球距离矩阵下，对相应的平均值和协方差的多元高斯的独立性分布的总和（也称为Wasserstein指标）。证明了“广义多项式”分布的更强大但更具体的中心限制定理，这是由材料参数化的大量离散分布，它概括了二项式和多项式分布，并描述了计算机科学中遇到的许多分布。多元分布到多个高斯分布，与我们的第一个中央限制定理的度量相比，通过四舍五入到最近的晶格点。从广义的多项式分布中绘制的表现基本上是从具有相同的平均值和协方差的离散的高斯绘制的本文的第二部分，我们采用此中央限制定理来在样品复杂性上建立ω（n log n）的下限，以估算分布的熵或支撑大小（其中1/n是在该分布的下限域中的任何元素）以及在伴侣纸上构建的规范估计器[33]，这解决了这些估计问题的样本复杂性的长期开放问题，尤其是恒定因素。 2，有一对分布的家族d，d'每个元素的发生概率至少为1/n，其熵满足h（d）-h（d）-h（d'）> c1，并且其支持的大小不同。至少C2N，因此在O（N log N）上没有算法可以将D与D'区分开，以大于2/3的概率。 ，表明对添加剂C内的样本复杂性为ω（n C log n）。通过拉瓜多项式构建可能具有独立关注的一对分布d，d'。
We prove two new multivariate central limit theorems; the first relates the sum of indepen- dent distributions to the multivariate Gaussian of corresponding mean and covariance, under the earthmover distance matric (also known as the Wasserstein metric). We leverage this central limit theorem to prove a stronger but more specific central limit theorem for “generalized multinomial” distributions—a large class of discrete distributions, parameterized by matrices, that generalize binomial and multinomial distributions, and describe many distributions encountered in computer science. This central limit theorem relates a generalized multinomial distribution to a multivari- ate Gaussian distribution, discretized by rounding to the nearest lattice points. In contrast to the metric of our first central limit theorem, this bound is in terms of statistical distance, which imme- diately implies that any algorithm with input drawn from a generalized multinomial distribution behaves essentially as if the input were drawn from a discretized Gaussian with the same mean and covariance. Such tools in the multivariate setting are rare, and we hope this new tool will be of use to the community. In the second part of the paper, we employ this central limit theorem to establish a lower bound of Ω( n log n ) on the sample complexity of additively estimating the entropy or support size of a distribution (where 1/n is a lower bound on the probability of any element in the domain). Together with the canonical estimator constructed in the companion paper [33], this settles the longstanding open question of the sample complexities of these estimation problems, up to constant factors. In particular, for any constants c1 2 , there is a family of pairs of distributions D,D′ each of whose elements occurs with probability at least 1/n, whose entropies satisfy H(D)−H(D′) > c1, and whose support sizes differ by at least c2n, such that no algorithm on o( n log n ) samples can distinguish D from D ′ with probability greater than 2/3. For the problem of estimating entropy, we also provide a bound on the rate of convergence of an optimal estimator, showing that the sample complexity of estimating entropy to within additive c is Ω ( n c log n ) . The previous lower-bounds on these sample complexities were n/2 √ log , for constant c, from [34]. We explicitly exhibit such a family of pairs of distributions D,D′ via a Laguerre polynomial construction that may be of independent interest.