On the Structure, Covering, and Learning of Poisson Multinomial Distributions

An (n,k)-Poisson Multinomial Distribution (PMD) is the distribution of the sum of n independent random vectors supported on the set cal Bk=e1,ldots,ek of standard basis vectors in ℝk. We prove a structural characterization of these distributions, showing that, for all varepsilon >0, any (n, k)-Poisson multinomial random vector is varepsilon-close, in total variation distance, to the sum of a discretized multidimensional Gaussian and an independent (poly(k/varepsilon), k)-Poisson multinomial random vector. Our structural characterization extends the multi-dimensional CLT of Valiant and Valiant, by simultaneously applying to all approximation requirements varepsilon. In particular, it overcomes factors depending on log n and, importantly, the minimum eigenvalue of the PMD's covariance matrix from the distance to a multidimensional Gaussian random variable. We use our structural characterization to obtain an varepsilon-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 varepsilon 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 varepsilon in total variation distance from tildeOk(1/varepsilon2) samples, which is near-optimal in terms of dependence on varepsilon and independent of n. In particular, our result generalizes the single-dimensional result of Daskalakis, Diakonikolas, and Servedio for Poisson Binomials to arbitrary dimension.