On the Structure, Covering, and Learning of Poisson Multinomial Distributions
Authors:
- Constantinos DaskalakisCDConstantinos Daskalakis
- Gautam KamathGKGautam Kamath
- Christos TzamosCTChristos Tzamos
Open Access
- 1 October 2015
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 1203-1217
Abstract
An (n, k)-Poisson Multinomial Distribution (PMD) is the distribution of the sum of n independent random vectors supported on the set Bk={e 1 ,...,ek} of standard basis vectors in R k . We prove a structural characterization of these distributions, showing that, for all ε > 0, any (n, k)-Poisson multinomial random vector is ε-close, in total variation distance, to the sum of a discretized multidimensional Gaussian and an independent (poly(k/ε), k)-Poisson multinomial random vector. Our structural characterization extends the multi-dimensional CLT of Valiant and Valiant, by simultaneously applying to all approximation requirements ε. In particular, it overcomes factors depending on log n and, importantly, the minimum Eigen value of the PMD's covariance matrix. We use our structural characterization to obtain an ε-cover, in total variation distance, of the set of all (n, k)-PMDs, significantly improving the cover size of Daskalakis and Papadimitriou, and obtaining the same qualitative dependence of the cover size on n and ε as the k=2 cover of Daskalakis and Papadimitriou. We further exploit this structure to show that (n, k)-PMDs can be learned to within ε in total variation distance from Õ k (1/ε) samples, which is near-optimal in terms of dependence on ε and independent of n. In particular, our result generalizes the single-dimensional result of Daskalakis, Diakonikolas and Servedio for Poisson binomials to arbitrary dimension. Finally, as a corollary of our results on PMDs, we give a Õk(1/ε 2 ) sample algorithm for learning (n, k)-sums of independent integer random variables (SIIRVs), which is near-optimal for constant k.Keywords
All Related Versions
This publication has 14 references indexed in Scilit:
- Approximate Nash equilibria in anonymous gamesJournal of Economic Theory, 2015
- Testing Poisson Binomial Distributions2014
- Sorting with adversarial comparators and application to density estimation2014
- Learning Sums of Independent Integer Random Variables2013
- Discretized Multinomial Distributions and Nash Equilibria in Anonymous Games2008
- Multinomial and Krawtchouk Approximations to the Generalized Multinomial DistributionTheory of Probability & Its Applications, 2002
- Combinatorial Methods in Density Estimation2001
- Stein's Method and Multinomial ApproximationThe Annals of Applied Probability, 1992
- Poisson approximations of multinomial distributions and point processesJournal of Multivariate Analysis, 1988
- Stein's method and poisson process convergenceJournal of Applied Probability, 1988