# Properly Learning Poisson Binomial Distributions in Almost Polynomial Time

arXiv: https://arxiv.org/abs/1511.04066 · HTML: https://mlsanity.com/paper/1511.04066/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Nov 2015.

## Built on by (most cited first, 3 of 3)

- [Learning and Covering Sums of Independent Random Variables with Unbounded Support](https://mlsanity.com/paper/2210.13313/) (2022)
- [Optimal Algorithms for Augmented Testing of Discrete Distributions](https://mlsanity.com/paper/2412.00974/) (2024)
- [Learning Mixture Models via Efficient High-dimensional Sparse Fourier Transforms](https://mlsanity.com/paper/2601.05157/) (2026)

## Abstract (arXiv)

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.