Let us define a class of functions over a set of $n$ bits. Fix two distributions $p, q$ that are reasonably different from each other (if you like, their variational distance is at least $\epsilon$, or something similar). Now each function $f$ in this class is defined by a collection of $k$ indices $S$, and is evaluated as follows: If the parity of the selected bits is 0, return a random sample from $p$, else return a random sample from $q$.Problem: Suppose I'm given oracle access to some $f$ from this class, and while I know $\epsilon$ (or some other measure of distance), I don't know $p$ and $q$. Are there any bounds on the number of calls I need to make to  PAC-learn $f$ ? Presumably my answer will be in terms of $n, k$ and $\epsilon$. Note: I didn't specify the output domain. Again, I'm flexible, but for now let's say that $p$ and $q$ are defined over a finite domain $[1..M]$. In general, I'd also be interested in the case when they are defined over ${\mathbb R}$ (for example, if they're Gaussians)
A parity learning question
lg.learning