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)

  • $\begingroup$ 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? $\endgroup$ – Lev Reyzin Apr 8 '13 at 18:21
  • 1
    $\begingroup$ In an oracle call, you invoke f() and it returns a value. $\endgroup$ – Suresh Venkat Apr 8 '13 at 20:44
  • $\begingroup$ 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$.) $\endgroup$ – Lev Reyzin Apr 8 '13 at 21:25
  • $\begingroup$ Yes that is correct. the problem is to learn which one (or learn the parity bit being used) $\endgroup$ – Suresh Venkat Apr 9 '13 at 2:53
  • 2
    $\begingroup$ 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. $\endgroup$ – 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.

| cite | improve this answer | |
  • $\begingroup$ 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? $\endgroup$ – Keki Burjorjee Apr 10 '13 at 17:01
  • 1
    $\begingroup$ 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. $\endgroup$ – Lev Reyzin Apr 10 '13 at 18:15
  • $\begingroup$ 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. $\endgroup$ – Keki Burjorjee Apr 10 '13 at 19:08
  • 1
    $\begingroup$ 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... $\endgroup$ – Lev Reyzin Apr 10 '13 at 19:44
  • $\begingroup$ 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). $\endgroup$ – Keki Burjorjee Apr 10 '13 at 21:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.