%0 Journal Article %1 daskalakis2011learning %A Daskalakis, Constantinos %A Diakonikolas, Ilias %A Servedio, Rocco A. %D 2011 %K probability stats %T Learning transformed product distributions %U http://arxiv.org/abs/1103.0598 %X We consider the problem of learning an unknown product distribution $X$ over $\0,1\^n$ using samples $f(X)$ where $f$ is a known transformation function. Each choice of a transformation function $f$ specifies a learning problem in this framework. Information-theoretic arguments show that for every transformation function $f$ the corresponding learning problem can be solved to accuracy $\eps$, using $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 $f(x)=w x$ with integer weights $w_i n$ and prove that the corresponding learning problem requires $Ømega(n)$ samples. 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 $f(x)= \sum_i=1^n x_i$. Our algorithm learns to $\eps$-accuracy in poly$(n)$ time, using a surprising poly$(1/\eps)$ number of samples that is independent of $n.$ We also give an efficient algorithm that uses $n \poly(1/\eps)$ samples but has running time that is only $\poly(n, 1/\eps).$

@article{daskalakis2011learning, abstract = {We consider the problem of learning an unknown product distribution $X$ over $\{0,1\}^n$ using samples $f(X)$ where $f$ is a \emph{known} transformation function. Each choice of a transformation function $f$ specifies a learning problem in this framework. Information-theoretic arguments show that for every transformation function $f$ 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 $f(x)=w \cdot x$ with integer weights $w_i \leq n$ and prove that the corresponding learning problem requires $\Omega(n)$ samples. 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 $f(x)= \sum_{i=1}^n x_i$. Our algorithm learns to $\eps$-accuracy in poly$(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).$}, added-at = {2020-02-26T13:55:37.000+0100}, author = {Daskalakis, Constantinos and Diakonikolas, Ilias and Servedio, Rocco A.}, biburl = {https://www.bibsonomy.org/bibtex/2fc6b6969b7f0164b732d2564e3b900ec/kirk86}, description = {[1103.0598] Learning transformed product distributions}, interhash = {1a2138fbceeb249ac4fecdc2614ba257}, intrahash = {fc6b6969b7f0164b732d2564e3b900ec}, keywords = {probability stats}, note = {cite arxiv:1103.0598}, timestamp = {2020-02-26T13:55:37.000+0100}, title = {Learning transformed product distributions}, url = {http://arxiv.org/abs/1103.0598}, year = 2011 }