The Fourier transform of Poisson multinomial distributions and its algorithmic applications

DOI10.1145/2897518.2897552zbMATH Open1373.68318arXiv1511.03592OpenAlexW2962765673MaRDI QIDQ5361902FDOQ5361902

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)

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.

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

Recommendations

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

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)

Cited In (12)

• Title not available (Why is that?)
• Title not available (Why is that?)
• Robust estimators in high-dimensions without the computational intractability
• Title not available (Why is that?)
• 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)