Learning transformed product distributions

Constantinos Daskalakis, Ilias Diakonikolas, Rocco A. Servedio

Research output: Contribution to journalArticlepeer-review

Abstract

We consider the problem of learning an unknown product distribution X over {0,1}n using samples ƒ(X)  where ƒ  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 ƒ(x)=w⋅x  with integer weights wi ≤n  and prove that the corresponding learning problem requires Ω(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)=∑ni=1 xi . 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).$
Original languageEnglish
JournalComputing Research Repository (CoRR)
Volumeabs/1103.0598
Publication statusPublished - 2011

Fingerprint

Dive into the research topics of 'Learning transformed product distributions'. Together they form a unique fingerprint.

Cite this