The Fourier Transform of Poisson Multinomial Distributions and its Algorithmic Applications

Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

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.
Original languageEnglish
Title of host publicationSTOC 2016 Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing
PublisherACM
Pages1060-1073
Number of pages67
ISBN (Print)978-1-4503-4132-5
DOIs
Publication statusPublished - 2016
Event48th Annual ACM SIGACT Symposium on Theory of Computing - Hyatt Regency, Cambridge, United States
Duration: 19 Jun 201621 Jun 2016
http://acm-stoc.org/stoc2016/

Conference

Conference48th Annual ACM SIGACT Symposium on Theory of Computing
Abbreviated titleSTOC 2016
Country/TerritoryUnited States
CityCambridge
Period19/06/1621/06/16
Internet address

Fingerprint

Dive into the research topics of 'The Fourier Transform of Poisson Multinomial Distributions and its Algorithmic Applications'. Together they form a unique fingerprint.

Cite this