The Fourier Transform of Poisson Multinomial Distributions and its Algorithmic Applications

We study Poisson Multinomial Distributions – a fundamental family of discrete distributions that generalize the binomial and multinomial distributions, and are commonly encountered in computer science. Formally, an (n, k)-Poisson Multinomial Distribution (PMD) is a random variable of the form X =Pni=1 Xi, where the Xi’s are independent random vectors supported on the set {e1, e2, . . . , ek} of standard basis vectors in Rk. In this paper, we obtain a refined structural understanding of PMDs by analyzing their Fourier transform. As our core structural result, we prove that the Fourier transform of PMDs is approximately sparse, i.e., roughly speaking, its L1-norm is small outside a small set. By building on this result, we obtain the following applications:Learning Theory. We design the first computationally efficient learning algorithm for PMDs with respect to the total variation distance. Our algorithm learns an arbitrary (n, k)-PMD within variation distance using a near-optimal sample size of Oek(1/2), and runs in timeOek(1/2) · log n. Previously, no algorithm with a poly(1/) runtime was known, even for k = 3.Game Theory. We give the first efficient polynomial-time approximation scheme (EPTAS) for computing Nash equilibria in anonymous games. For normalized anonymous games with nplayers and k strategies, our algorithm computes a well-supported -Nash equilibrium in time nO(k3)· (k/)O(k3log(k/)/ log log(k/))k−1. The best previous algorithm for this problem [DP08, DP14] had running time n(f(k)/)k, where f(k) = Ω(kk2), for any k > 2.Statistics. We prove a multivariate central limit theorem (CLT) that relates an arbitrary PMD to a discretized multivariate Gaussian with the same mean and covariance, in total variation distance. Our new CLT strengthens the CLT of Valiant and Valiant [VV10, VV11] by completely removing the dependence on n in the error bound. Along the way we prove several new structural results of independent interest about PMDs. These include: (i) a robust moment-matching lemma, roughly stating that two PMDs that approximately agree on their low-degree parameter moments are close in variation distance; (ii) near-optimal size proper -covers for PMDs in total variation distance (constructive upper bound and nearly-matching lower bound). In addition to Fourier analysis, we employ a number of analytic tools, including the saddle point method from complex analysis, that may find other applications.