<p>I think that the answer is "no", although I'm not certain and would also be interested in other examples. One thing that is known is that agnostic learning is significantly harder from an information theoretic perspective in the SQ model. Agnostically learning monotone disjunctions to error epsilon requires only $d/\epsilon^2$ examples in the PAC setting (though the task of learning might then be computationally hard...). In the SQ model, there is no agnostic learning algorithm for monotone disjunctions that has a polynomial dependence on $1/\epsilon$ in terms of the number of queries it makes, even ignoring computational considerations.</p>

CC BY-SA 2.5
2011-02-08T03:34:40.707Z
Thanks, Aaron -- that was my understanding of the state of things as well, but I wasn't sure.  If nobody gives me an example soon, I'll mark yours as the accepted answer.
Lev Reyzin
CC BY-SA 2.5
2011-02-07T22:20:02.023Z
2011-02-07T22:20:02.023Z
Aaron Roth
<p>This is a good question. I guess you are looking for a different separation technique rather than just a different class of functions (since it is easy to give natural and artificial examples of concept classes that still rely on BKW result for the separation). I'd go further and say that even the parities example is not a decisive separation since SQ model gives learning with noise rate inverse polynomially close to 1/2 whereas BKW does not allow noise of the rate $1/2-n^{-\epsilon}$. I think it would be interesting to find a "pure" separation. It seems that this would also require a new technique, answering your original question.</p>

CC BY-SA 2.5
2011-04-04T20:44:59.487Z
Yes, that's right, I want a different separation technique, and not something that relies on BKW.  Your additional question of pure separation is also interesting.
Lev Reyzin
CC BY-SA 2.5
2011-04-04T19:59:03.927Z
2011-04-04T19:59:03.927Z
Vitaly
<p>Angluin and Laird ('88) <a href="https://doi.org/10.1023/A:1022873112823" rel="nofollow noreferrer">formalized</a> learning with randomly corrupted data in the model &quot;PAC with random classification noise&quot; (or noisy PAC). This model is similar to <a href="https://en.wikipedia.org/wiki/Probably_approximately_correct_learning" rel="nofollow noreferrer">PAC learning</a>, except for the labels of the examples given to the learner are corrupted (flipped), independently at random, with probability <span class="math-container">$\eta &lt; 1/2$</span>.</p>
<p>To help characterize what is learnable in the noisy PAC model, Kearns ('93) <a href="http://reference.kfupm.edu.sa/content/e/f/efficient_noise_tolerant_learning_from_s_66565.pdf" rel="nofollow noreferrer">introduced</a> the <a href="http://vtaly.net/papers/Kearns93-2017.pdf" rel="nofollow noreferrer">Statistical Query model</a> (SQ) for learning.  In this model, a learner can query a statistical oracle for properties of the target distribution, and he showed that any class that is SQ learnable is learnable in noisy PAC.  Kearns also proved that <a href="https://en.wikipedia.org/wiki/Parity_function" rel="nofollow noreferrer">parities</a> on <span class="math-container">$n$</span> variables cannot be learned in time faster than <span class="math-container">$2^{n/c}$</span> for some constant <span class="math-container">$c$</span>.</p>
<p>Then Blum et al. ('00) <a href="https://dl.acm.org/doi/10.1145/335305.335355" rel="nofollow noreferrer">separated</a> noisy PAC from SQ by showing that parities on the first <span class="math-container">$(\log(n) \log\log(n))$</span> are polynomial-time learnable in the noisy PAC model but not in the SQ model.</p>
<p>My question is this:</p>
<blockquote>
<p>Parities (on the first <span class="math-container">$(\log(n) \log\log(n))$</span> variables) are learnable in the noisy PAC model but not in the SQ model.  Are there any other specific classes, sufficiently different from parity, that are known to be learnable in noisy PAC but not in SQ?</p>
</blockquote>

<lg.learning>
Any Hypothesis Classes Other than Parity in Noisy PAC but not in SQ?
Lev Reyzin
# Any Hypothesis Classes Other than Parity in Noisy PAC but not in SQ?

(Asked by: username_0 on 2011-02-06)

Angluin and Laird ('88) [formalized](https://doi.org/10.1023/A:1022873112823) learning with randomly corrupted data in the model "PAC with random classification noise" (or noisy PAC). This model is similar to [PAC learning](https://en.wikipedia.org/wiki/Probably_approximately_correct_learning), except for the labels of the examples given to the learner are corrupted (flipped), independently at random, with probability $\eta < 1/2$.

To help characterize what is learnable in the noisy PAC model, Kearns ('93) [introduced](http://reference.kfupm.edu.sa/content/e/f/efficient_noise_tolerant_learning_from_s_66565.pdf) the [Statistical Query model](http://vtaly.net/papers/Kearns93-2017.pdf) (SQ) for learning. In this model, a learner can query a statistical oracle for properties of the target distribution, and he showed that any class that is SQ learnable is learnable in noisy PAC. Kearns also proved that [parities](https://en.wikipedia.org/wiki/Parity_function) on $n$ variables cannot be learned in time faster than $2^{n/c}$ for some constant $c$.

Then Blum et al. ('00) [separated](https://dl.acm.org/doi/10.1145/335305.335355) noisy PAC from SQ by showing that parities on the first $(\log(n) \log\log(n))$ are polynomial-time learnable in the noisy PAC model but not in the SQ model.

My question is this:

> Parities (on the first $(\log(n) \log\log(n))$ variables) are learnable in the noisy PAC model but not in the SQ model. Are there any other specific classes, sufficiently different from parity, that are known to be learnable in noisy PAC but not in SQ?

**Tags:** lg.learning

---

## 2 answers

### Answer by username_1 on 2011-02-07. Score: 6 | Accepted answer

I think that the answer is "no", although I'm not certain and would also be interested in other examples. One thing that is known is that agnostic learning is significantly harder from an information theoretic perspective in the SQ model. Agnostically learning monotone disjunctions to error epsilon requires only $d/\epsilon^2$ examples in the PAC setting (though the task of learning might then be computationally hard...). In the SQ model, there is no agnostic learning algorithm for monotone disjunctions that has a polynomial dependence on $1/\epsilon$ in terms of the number of queries it makes, even ignoring computational considerations.

> **Comments:**
> **username_0**: Thanks, Aaron -- that was my understanding of the state of things as well, but I wasn't sure.  If nobody gives me an example soon, I'll mark yours as the accepted answer.  

---

### Answer by username_2 on 2011-04-04. Score: 6

This is a good question. I guess you are looking for a different separation technique rather than just a different class of functions (since it is easy to give natural and artificial examples of concept classes that still rely on BKW result for the separation). I'd go further and say that even the parities example is not a decisive separation since SQ model gives learning with noise rate inverse polynomially close to 1/2 whereas BKW does not allow noise of the rate $1/2-n^{-\epsilon}$. I think it would be interesting to find a "pure" separation. It seems that this would also require a new technique, answering your original question.

> **Comments:**
> **username_0**: Yes, that's right, I want a different separation technique, and not something that relies on BKW.  Your additional question of pure separation is also interesting.  

---

