The Fourier transform of Poisson multinomial distributions and its algorithmic applications

DOI10.1145/2897518.2897552MaRDI QIDQ5361902zbMATH OpenOpenAlexFDO

Authors Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart

Publication date 29 September 2017

Published in Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1511.03592

zbMATH Keywords

central limit theoremFourier analysiscomputational learning theoryanonymous gameslearning distributions

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Estimation in multivariate analysis (62H12) Central limit and other weak theorems (60F05) Analysis of algorithms (68W40) Noncooperative games (91A10)

Abstract: An $(n,k)$-Poisson Multinomial Distribution (PMD) is a random variable of the form $X=su{m}_{i=1}^n{X}_i$, where the $X_i$'s are independent random vectors supported on the set of standard basis vectors in $mathbb{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 {em 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: {�f 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 $epsilon$ using a near-optimal sample size of $widetilde{O}_k(1/epsilo{n}^2),$ and runs in time $widetilde{O}_k(1/epsilo{n}^2)cdotlogn.$ Previously, no algorithm with a $mathrmpoly(1/epsilon)$ runtime was known, even for $k=3.$ {�f 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 $epsilon$-Nash equilibrium in time $n^{O(k^3)}cdot(k/epsilon{)}^{O(k^{3}log(k/epsilon)/loglog(k/epsilon){)}^{k-1}}.$ The best previous algorithm for this problem had running time $n^{(f(k)/epsilon{)}^k},$ where $f(k)=Omega(k^{k^2})$, for any $k>2.$ {�f 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.

Recommendations

• A size-free CLT for Poisson multinomials and its applications
• Playing anonymous games using simple strategies
• Sparse covers for sums of indicators

Cited in

(12)

• scientific article; zbMATH DE number 6866347 (Why is no real title available?)
• scientific article; zbMATH DE number 7307484 (Why is no real title available?)
• Robust estimators in high-dimensions without the computational intractability
• scientific article; zbMATH DE number 4149313 (Why is no real title available?)
• Query complexity of approximate equilibria in anonymous games
• On the Power of Learning from k-Wise Queries
• A size-free CLT for Poisson multinomials and its applications
• Technical Note—An Algorithm for Computing the Convolution of Poisson Negative Binomial and Geometric Distributions
• Density estimation for shift-invariant multidimensional distributions
• Sparse covers for sums of indicators
• The Poisson binomial distribution -- old \& new
• The Poisson Multinomial Distribution and Its Applications in Voting Theory, Ecological Inference, and Machine Learning

This page was built for publication: The Fourier transform of Poisson multinomial distributions and its algorithmic applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5361902)