The Fourier Transform of Poisson Multinomial Distributions and its Algorithmic Applications

An (n, k)-Poisson Multinomial Distribution (PMD) is a random variable of the form X = sumi=1n Xi, where the Xi's are independent random vectors supported on the set of standard basis vectors in ℝk. 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 em 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: bf 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 widetildeOk(1/ε2), and runs in time widetildeOk(1/ε2) · log n. Previously, no algorithm with a poly(1/ε) runtime was known, even for k=3. bf Game Theory. We give the first efficient polynomial-time approximation scheme (EPTAS) for computing Nash equilibria in anonymous games. For normalized anonymous games with n players and k strategies, our algorithm computes a well-supported ε-Nash equilibrium in time nO(k3) · (k/ε)^O(k3log(k/ε)/loglog(k/ε))k-1. The best previous algorithm for this problem had running time n(f(k)/ε)k, where f(k) = Omega(kk2), for any k>2. bf 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 by completely removing the dependence on n in the error bound.