Properly Learning Poisson Binomial Distributions in Almost Polynomial Time

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 widetildeO(1/ε2) samples from an unknown PBD p, our algorithm runs in time (1/ε)O(log log (1/ε)), and outputs a hypothesis PBD that is ε-close to p in total variation distance. The previously best known running time for properly learning PBDs was (1/ε)O(log(1/ε)). As one of our main contributions, we provide a novel structural characterization of PBDs. We prove that, for all ε >0, there exists an explicit collection calM of (1/ε)O(log log (1/ε)) vectors of multiplicities, such that for any PBD p there exists a PBD q with O(log(1/ε)) distinct parameters whose multiplicities are given by some element of cal M, such that q is ε-close to 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~citeDKS15. Our aforementioned structural characterization allows us to reduce the corresponding fitting problem to a collection of (1/ε)O(log log(1/ε)) systems of low-degree polynomial inequalities. We show that each such system can be solved in time (1/ε)O(log log(1/ε)), which yields the overall running time of our algorithm.