Open Problems:36 - Revision history

Krzysztof Onak: updated header

2013-03-07T01:53:23Z

updated header

Krzysztof Onak at 05:29, 16 November 2012

2012-11-16T05:29:02Z

Krzysztof Onak: Created page with "{{DISPLAYTITLE:Problem 36: Learning an $f$-Transformed Product Distribution}} {{Infobox |label1 = Proposed by |data1 = Rocco A. Servedio |label2 = Source |data2 = [[Workshops:..."

2012-11-13T15:06:10Z

Created page with "{{DISPLAYTITLE:Problem 36: Learning an $f$-Transformed Product Distribution}} {{Infobox |label1 = Proposed by |data1 = Rocco A. Servedio |label2 = Source |data2 = [[Workshops:..."

New page

{{DISPLAYTITLE:Problem 36: Learning an $f$-Transformed Product Distribution}}
{{Infobox
|label1 = Proposed by
|data1 = Rocco A. Servedio
|label2 = Source
|data2 = [[Workshops:Bertinoro_2011|Bertinoro 2011]]
|label3 = Short link
|data3 = http://sublinear.info/36
}}
In this learning setting there are $n$ independent Bernoulli random variables
$X_1,...,X_n$ with ''unknown'' $E[X_i]=p_i$. There is a ''known''
transformation function $f:\{0,1\}^n \mapsto R$, where $R$ is some range.
The learner has access to independent draws from $f(X_1,...,X_n)$;
i.e., each example for the learner is obtained by independently drawing
$X_1,...,X_n$, applying $f$, and giving the result to the learner. Call
this distribution $D_f$.
The learner's job is to construct a hypothesis distribution $D'$ over the
range set such that the variation distance between $D_f$ and $D'$ is
at most $\epsilon$, with high probability.

'''Question:''' Give some necessary or sufficient conditions on $f$
that make the “learn an $f$-transformed product distribution” problem
solvable using $O_{\epsilon}(1)$ queries, independent of $n$.

'''Background:''' The following is known {{cite|DaskalakisDS-11}}:
# For $f(X)=X_1 + ... + X_n$, there's a learning algorithm using poly$(1/\epsilon)$ queries independent of $n$.
# For $f(X) = \sum_{i=1}^n i\cdot X_i$, any algorithm for learning to constant accuracy must make $\Omega(n)$ queries.

@@ Line 1: / Line 1: @@
 {{Header
 |source=bertinoro11
 |who=Rocco A. Servedio

@@ Line 1: / Line 1: @@
-{{DISPLAYTITLE:Problem 36: Learning an $f$-Transformed Product Distribution}}
+{{Header
-{{Infobox
+|title=Learning an $f$-Transformed Product Distribution
-|label1 = Proposed by
+|source=bertinoro11
-|data1 = Rocco A. Servedio
+|who=Rocco A. Servedio
 }}
 In this learning setting there are $n$ independent Bernoulli random variables