A size-free CLT for poisson multinomials and its applications
A size-free CLT for poisson multinomials and its applications
复制标题
泊松多项式的无尺寸CLT及其应用
DOI：
10.1145/2897518.2897519
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Christos Tzamos
中科院分区：
文献类型：
--
作者：
C. Daskalakis;Anindya De;Gautam Kamath;Christos Tzamos
AN（N，K） - 贫乏的多项式分布（PMD）是在bk = {e1，…，Ek}上支持的n个独立的随机向量的总和，我们在ℝK中表明任何（n）。 ，k）-pmd是poly（k/σ） - 在总变化距离上与（适当离散的）多维高斯（具有相同前两个矩）的（适当离散的）多维高斯，从而消除了Valiant and Valiant的中心极限定理对N的依赖。有趣的是，我们的CLT是通过启动Valiant-Valiant CLT本身通过Daskalakis，Kamath和Tzamos在最近的工作中的结构表征而获得的，又可以利用我们的更强的CLT来获得有效的PTA显着改善艺术的状态，并定性地匹配运行时间对n和1/є的运行时间依赖性最著名的算法两局匿名游戏。 Batson，Spielman和Srivastava的Laplacian物品的最新定理和稀疏结果。在PMD的傅立叶频谱中，我们表明可以从Polyk（1/є）时间中的OK（1/є2）样品中学到这些分布，从而消除了运行时间对1/є的准多项式依赖性，从先前的工作中删除。
An (n,k)-Poisson Multinomial Distribution (PMD) is the distribution of the sum of n independent random vectors supported on the set Bk={e1,…,ek} of standard basis vectors in ℝk. We show that any (n,k)-PMD is poly(k/σ)-close in total variation distance to the (appropriately discretized) multi-dimensional Gaussian with the same first two moments, removing the dependence on n from the Central Limit Theorem of Valiant and Valiant. Interestingly, our CLT is obtained by bootstrapping the Valiant-Valiant CLT itself through the structural characterization of PMDs shown in recent work by Daskalakis, Kamath and Tzamos. In turn, our stronger CLT can be leveraged to obtain an efficient PTAS for approximate Nash equilibria in anonymous games, significantly improving the state of the art, and matching qualitatively the running time dependence on n and 1/є of the best known algorithm for two-strategy anonymous games. Our new CLT also enables the construction of covers for the set of (n,k)-PMDs, which are proper and whose size is shown to be essentially optimal. Our cover construction combines our CLT with the Shapley-Folkman theorem and recent sparsification results for Laplacian matrices by Batson, Spielman, and Srivastava. Our cover size lower bound is based on an algebraic geometric construction. Finally, leveraging the structural properties of the Fourier spectrum of PMDs we show that these distributions can be learned from Ok(1/є2) samples in polyk(1/є)-time, removing the quasi-polynomial dependence of the running time on 1/є from prior work.