Projects per year
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 L1norm 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 nearoptimal 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 polynomialtime approximation scheme (EPTAS) for computing Nash equilibria in anonymous games. For normalized anonymous games with nplayers and k strategies, our algorithm computes a wellsupported 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 momentmatching lemma, roughly stating that two PMDs that approximately agree on their lowdegree parameter moments are close in variation distance; (ii) nearoptimal size proper covers for PMDs in total variation distance (constructive upper bound and nearlymatching 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 language  English 

Title of host publication  STOC 2016 Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing 
Publisher  ACM 
Pages  10601073 
Number of pages  67 
ISBN (Print)  9781450341325 
DOIs  
Publication status  Published  2016 
Event  48th Annual ACM SIGACT Symposium on Theory of Computing  Hyatt Regency, Cambridge, United States Duration: 19 Jun 2016 → 21 Jun 2016 http://acmstoc.org/stoc2016/ 
Conference
Conference  48th Annual ACM SIGACT Symposium on Theory of Computing 

Abbreviated title  STOC 2016 
Country/Territory  United States 
City  Cambridge 
Period  19/06/16 → 21/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.Projects
 1 Finished

Sublinear Algorithms for Approximating Probability Distribution
Diakonikolas, I.
1/09/14 → 31/08/15
Project: Research