The Fourier Transform of Poisson Multinomial Distributions and its Algorithmic Applications

Abstract

An (n, k)-Poisson Multinomial Distribution (PMD) is a random variable of the form X = _i=1^n X_i, where the X_i's are independent random vectors supported on the set of standard basis vectors in R^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 approximately sparse, i.e., roughly speaking, its L_1-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 O_k(1/^2), and runs in time O_k(1/^2) 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 n players and k strategies, our algorithm computes a well-supported -Nash equilibrium in time n^O(k^3) (k/)^O(k^3(k/)/(k/))^k-1. The best previous algorithm for this problem had running time n^(f(k)/)^k, where f(k) = (k^k^2), 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 by completely removing the dependence on n in the error bound.

Tasks

Reproductions