An $(n, k)$-Poisson Multinomial Distribution (PMD) is a random variable of the form $X = \sum_{ 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: { \bf 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/\epsilon^2),$ and runs in time $\widetilde{ O}_k(1/\epsilon^2) \cdot \log n.$ Previously, no algorithm with a $\mathrm{ poly}(1/\epsilon)$ runtime was known, even for $k=3.$ { \bf 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)/\log\log(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.$ { \bf 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.
Categories: cs.DS cs.GT cs.LG math.PR math.ST stat.TH