# A parity learning question

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)

• I'm not sure I understand the model. What do you specify in an oracle call? Are the examples always drawn from the distribution specified by the target? – Lev Reyzin Apr 8 '13 at 18:21
• In an oracle call, you invoke f() and it returns a value. – Suresh Venkat Apr 8 '13 at 20:44
• So depending on the target function $f \in F$, either $p$ or $q$ is always used to generate examples? (I assume you are pac learning some class $F$.) – Lev Reyzin Apr 8 '13 at 21:25
• Yes that is correct. the problem is to learn which one (or learn the parity bit being used) – Suresh Venkat Apr 9 '13 at 2:53
• I am not sure how you adapt the PAC model to this model. But it seems that it's enough to be able to distinguish $p$ from $q$ with probability $1 - 1/(2k)$ and then you can get the $f(x)$ values for $k$ linearly independent $x$ and use gaussian elimination to find $f$ (since $f$ is linear). distinguishing two well-separated gaussians will be easy for example. – Sasho Nikolov Apr 11 '13 at 7:04

The discussion in the comments below indicades that I have misunderstood the question. My answer is premised on the Oracle taking no input and returning $(x, f(x))$ where $x \sim p$ or $x \sim q$, depending on $f \in F$. This is apparently not what's being asked.

Because the target distribution is fixed for every target $f^* \in F$, the PAC-sample upper bound applies (this follows from the fact that the target distribution for this bound can even completely depend on $f^*$). Hence, $$m \le \tilde{O}\left(\frac{1}{\epsilon}\left(\mathrm{VC}(F) + \log(1/\delta) \right) \right)$$ examples should suffice to find a hypothesis of error $\le \epsilon$ w.p. $\ge 1-\delta$. Note -- after seeing these examples, one needs to find a consistent hypothesis from $F$, and this may not be tractable.

On the other hand, one can get a nearly matching lower bound even for the case of $p=q=U$, the uniform distribution, where $m \ge \Omega(\mathrm{VC}(F))$ examples are still required (this can be improved slightly).

The variational distance between $p$ and $q$, as well as $k$ may play a role in the small gap between these bounds, but I doubt it.

• The typical PAC-learning setting has an oracle $(f,D)$ that draws a sample $x$ from distribution $D$, and returns $(x, f(x))$. This is not the setting described in Suresh's question or the blog post that inspired it: bit.ly/YtwdST. In both of these, the oracle is the function $f$, and the learner is free to submit any element from the instance set (bitstrings of length $n$). Lev, does your answer assume an oracle of the first type, or the second type? If the second type, are we still talking about PAC-learning? – Keki Burjorjee Apr 10 '13 at 17:01
• I see. In PAC, the "oracle" usually is thought of as a button which returns $(x, f(x))$ where $x \sim D$. The Oracle you describe is called a "membership query" to $f$. My answer only applies to the former. If you only membership queries, how do you find out any information about $p$ or $q$ using Suresh's framework? Let's say $p=q$ for simplicity. – Lev Reyzin Apr 10 '13 at 18:15
• Thanks for that clarification. So in the case Suresh described, the "membership query" oracle works as follows (I presume you've put this entity in quotes because the oracle can return a real value, not just a boolean is-a-member/not-a-member answer): if the parity of the effective attributes is 1, then the result returned is drawn from distribution $p$. Otherwise, the result is drawn from distribution $q$. There's an additional wrinkle. The oracle remembers all its previous answers, and returns them if queried with the same input. In other words, it is deterministic. – Keki Burjorjee Apr 10 '13 at 19:08
• I don't understand. If the oracle is simply a function $f$ and you query it by giving it $x$, doesn't it just return $f(x)$? How does $p$ or $q$ come in to play if the learner is generating $x$ himself? I think I've been failing to understand this basic point all along... – Lev Reyzin Apr 10 '13 at 19:44
• For $p=\mathcal N(+0.25, 1)$ and $q = \mathcal N(-0.25, 1)$, the pseudocode of the oracle for the problem with the "wrinkle" is given at the bottom of this reddit comment: bit.ly/XvVMC4 (def fitness() ...). I can't inline the code because SE doesn't allow newlines in comments. To obtain the "non-wrinkly" version of the problem, just remove the line random_number_generator.set_seed(x). – Keki Burjorjee Apr 10 '13 at 21:57