Properly Learning Poisson Binomial Distributions in Almost Polynomial Time

Abstract

We give an algorithm for properly learning Poisson binomial distributions. A Poisson binomial distribution (PBD) of order $n$ is the discrete probability distribution of the sum of $n$ mutually independent Bernoulli random variables. Given $\tilde{O}(1/{\epsilon }^2)$ samples from an unknown PBD $\mathbf{p}$, our algorithm runs in time $(1/\epsilon {)}^{O(\log \log (1/\epsilon ))}$, and outputs a hypothesis PBD that is $\epsilon$-close to $\mathbf{p}$ in total variation distance. The previously best known running time for properly learning PBDs was $(1/\epsilon {)}^{O(\log (1/\epsilon ))}$. As one of our main contributions, we provide a novel structural characterization of PBDs. We prove that, for all $\epsilon >0,$ there exists an explicit collection $\mathcal{M}$ of $(1/\epsilon {)}^{O(\log \log (1/\epsilon ))}$ vectors of multiplicities, such that for any PBD $\mathbf{p}$ there exists a PBD $\mathbf{q}$ with $O(\log (1/\epsilon ))$ distinct parameters whose multiplicities are given by some element of $\mathcal{M}$, such that $\mathbf{q}$ is $\epsilon$-close to $\mathbf{p}$. Our proof combines tools from Fourier analysis and algebraic geometry. Our approach to the proper learning problem is as follows: Starting with an accurate non-proper hypothesis, we fit a PBD to this hypothesis. More specifically, we essentially start with the hypothesis computed by the computationally efficient non-proper learning algorithm in our recent work~\cite{DKS15}. Our aforementioned structural characterization allows us to reduce the corresponding fitting problem to a collection of $(1/\epsilon {)}^{O(\log \log (1/\epsilon ))}$ systems of low-degree polynomial inequalities. We show that each such system can be solved in time $(1/\epsilon {)}^{O(\log \log (1/\epsilon ))}$, which yields the overall running time of our algorithm.

References in corpus (5)

• Polynomial Learning of Distribution Families
• Optimal Testing for Properties of Distributions
• A Nearly Optimal and Agnostic Algorithm for Properly Learning a Mixture of k Gaussians, for any Constant k
• Optimal Learning via the Fourier Transform for Sums of Independent Integer Random Variables
• Query Complexity of Approximate Equilibria in Anonymous Games

Cited by in corpus (10)

• Learning Multivariate Log-concave Distributions
• Near-Optimal Closeness Testing of Discrete Histogram Distributions
• Optimal Learning via the Fourier Transform for Sums of Independent Integer Random Variables
• The Poisson binomial distribution -- Old & New
• Fourier-Based Testing for Families of Distributions
• Learning Populations of Parameters
• A Polynomial Time Algorithm for Maximum Likelihood Estimation of Multivariate Log-concave Densities
• Learning Mixtures of Linear Regressions in Subexponential Time via Fourier Moments
• A Polynomial Time Algorithm for Log-Concave Maximum Likelihood via Locally Exponential Families
• Learning Powers of Poisson Binomial Distributions