Any Hypothesis Classes Other than Parity in Noisy PAC but not in SQ?

Question

Angluin and Laird ('88) formalized learning with randomly corrupted data in the model "PAC with random classification noise" (or noisy PAC). This model is similar to PAC 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 the Statistical Query model (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 on $n$ variables cannot be learned in time faster than $2^{n/c}$ for some constant $c$.

Then Blum et al. ('00) separated 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?

Answer 1

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.

Answer 2

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.