## Abstract

We consider the problem of learning an unknown product distribution

Information-theoretic arguments show that for every transformation function

As our main positive result we give a highly efficient algorithm for learning a sum of independent unknown Bernoulli random variables, corresponding to the transformation function

**over***X***{0,1}**using samples^{n}**where***ƒ(X)**is a \emph{known} transformation function. Each choice of a transformation function***ƒ***specifies a learning problem in this framework.***ƒ**Information-theoretic arguments show that for every transformation function

*the corresponding learning problem can be solved to accuracy $\eps$, using $\tilde{O}(n/\eps^2)$ examples, by a generic algorithm whose running time may be exponential in***ƒ***n*. We show that this learning problem can be computationally intractable even for constant $\eps$ and rather simple transformation functions. Moreover, the above sample complexity bound is nearly optimal for the general problem, as we give a simple explicit linear transformation function**with integer weights***ƒ(x)=w⋅x***and prove that the corresponding learning problem requires Ω(n) samples.***w*_{i}≤nAs our main positive result we give a highly efficient algorithm for learning a sum of independent unknown Bernoulli random variables, corresponding to the transformation function

**. Our algorithm learns to $\eps$-accuracy in poly(***f(x)=∑*^{n}_{i=1}x_{i}*n*) time, using a surprising poly$(1/\eps)$ number of samples that is independent of*n*. We also give an efficient algorithm that uses $\log n \cdot \poly(1/\eps)$ samples but has running time that is only $\poly(\log n, 1/\eps).$Original language | English |
---|---|

Journal | Computing Research Repository (CoRR) |

Volume | abs/1103.0598 |

Publication status | Published - 2011 |