A size-free CLT for Poisson multinomials and its applications

Constantinos Daskalakis, Anindya De, Christos Tzamos, Gautam Kamath

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

16 Scopus citations

Abstract

An (n,k)-Poisson Multinomial Distribution (PMD) is the distribution of the sum of n independent random vectors supported on the set Bk = {e1,..., ek} of standard basis vectors in R. We show that any (n, k)-PMD is poly(k/σ)-close in total variation distance to the (appropriately discretized) multi-dimensional Gaussian with the same first two moments, removing the dependence on n from the Central Limit Theorem of Valiant and Valiant. Interestingly, our CLT is obtained by bootstrapping the Valiant-Valiant CLT itself through the structural characterization of PMDs shown in recent work by Daskalakis, Kamath and Tzamos. In turn, our stronger CLT can be leveraged to obtain an efficient PTAS for approximate Nash equilibria in anonymous games, significantly improving the state of the art, and matching qualitatively the running time dependence on n and 1/ϵ of the best known algorithm for two-strategy anonymous games. Our new CLT also enables the construction of covers for the set of (n, k)-PMDs, which are proper and whose size is shown to be essentially optimal. Our cover construction combines our CLT with the Shapley-Folkman theorem and recent sparsification results for Laplacian matrices by Batson, Spielman, and Srivastava. Our cover size lower bound is based on an algebraic geometric construction. Finally, leveraging the structural properties of the Fourier spectrum of PMDs we show that these distributions can be learned from Ok(1/ϵ2) samples in polyk(1/ϵ)-time, removing the quasi-polynomial dependence of the running time on 1/ϵ from prior work.

Original languageEnglish (US)
Title of host publicationSTOC 2016 - Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing
EditorsYishay Mansour, Daniel Wichs
PublisherAssociation for Computing Machinery
Pages1074-1086
Number of pages13
ISBN (Electronic)9781450341325
DOIs
StatePublished - Jun 19 2016
Event48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016 - Cambridge, United States
Duration: Jun 19 2016Jun 21 2016

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
Volume19-21-June-2016
ISSN (Print)0737-8017

Other

Other48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016
CountryUnited States
CityCambridge
Period6/19/166/21/16

Keywords

  • Applied probability
  • Central Limit Theorem
  • Computational learning theory
  • Learning distributions

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'A size-free CLT for Poisson multinomials and its applications'. Together they form a unique fingerprint.

Cite this