TY - GEN

T1 - A size-free CLT for Poisson multinomials and its applications

AU - Daskalakis, Constantinos

AU - De, Anindya

AU - Tzamos, Christos

AU - Kamath, Gautam

N1 - Funding Information:
Supported by a Microsoft Research Faculty Fellowship, and NSF Award CCF-0953960 (CAREER) and CCF-1551875. This work was done in part while the author was visiting the Simons Institute for the Theory of Computing. Supported by NSF Award CCF-0953960 (CAREER) and ONR grant N0001 4-12-1-0999. This work was done in part while the author was an intern at Microsoft Research Cambridge and visiting the Simons Institute for the Theory of Computing. Supported by NSF Award CCF-0953960 (CAREER), ONR grant N00014-12-1-0999, and a Simons Award for Graduate Students in Theoretical Computer Science. This work was done in part while the author was visiting the Simons Institute for the Theory of Computing.
Publisher Copyright:
© 2016 ACM. 978-1-4503-4132-5/16/06...$15.00.

PY - 2016/6/19

Y1 - 2016/6/19

N2 - 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.

AB - 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.

KW - Applied probability

KW - Central Limit Theorem

KW - Computational learning theory

KW - Learning distributions

UR - http://www.scopus.com/inward/record.url?scp=84979200755&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84979200755&partnerID=8YFLogxK

U2 - 10.1145/2897518.2897519

DO - 10.1145/2897518.2897519

M3 - Conference contribution

AN - SCOPUS:84979200755

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 1074

EP - 1086

BT - STOC 2016 - Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing

A2 - Mansour, Yishay

A2 - Wichs, Daniel

PB - Association for Computing Machinery

T2 - 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016

Y2 - 19 June 2016 through 21 June 2016

ER -