Learning Poisson binomial distributions (Q2345953)

The paper deals with a standard problem concerning unsupervised learning, i.e., learning a Poisson binomial distribution. Firstly, a highly efficient algorithm which learns to \(\epsilon\)-accuracy using \(\widetilde O(1/\epsilon^3)\) samples independent of \(n\) is provided. The second result consists in a proper learning algorithm that learns to \(\epsilon\)-accuracy using a nearly optimal sample complexity. Finally, some extensions to weighted sums of independent Bernoulli random variables are also provided.