Computational query complexity of SQ-learning

Question

It is known that for PAC learning, there are natural concept classes (e.g. subsets of decision lists) for which there are polynomial gaps between the sample complexity needed for information theoretic learning by a computationally unbounded learner, and the sample complexity needed by a polynomial-time learner. (see, e.g. http://portal.acm.org/citation.cfm?id=267489&dl=GUIDE or http://portal.acm.org/citation.cfm?id=301437)

These results seem to depend on encoding a secret in particular examples, however, and so don't naturally translate into the SQ-model of learning, where the learner just gets to query statistical properties of the distribution.

Is it known whether there exist concept classes for which information-theoretic learning in the SQ model is possible with O(f(n)) queries, but computationally efficient learning is only possible with Omega(g(n)) queries for g(n) >> f(n)?

Answer 1

I've asked (myself) this question a while ago. At least for learning with respect to a specific distribution there is a fairly simple example of a concept class that is information theoretically SQ-learnable but is NP-hard to SQ learn. Let \phi a binary encoding of a SAT instance and y be its lexicographically first satisfying assignment (or 0^n is the instance is unsatisfiable). Now let f(\phi) be a function that over one half of the domain is the MAJ(\phi) and over the second half of the domain equals PAR(y). Here MAJ is the majority function over variables which are set to 1 in the string \phi and PAR(y) is the parity function over variables which are set to 1 in the string y. Let F be the class of functions obtained in this way. To SQ learn F over the uniform distribution U one only needs to learn majorities (which is easy) to find \phi and then find y. On the other hand, it is fairly easy to reduce SAT to SQ learning of F (to any accuracy noticeably greater than 3/4) over the uniform distribution. The reason for this, naturally, is that parities are essentially "invisible" to SQs and hence it is necessary to solve SAT to learn F.

Answer 2

This is a nice question. The power of the statistical query model is precisely the ability to prove unconditional lower bounds for learning with SQ -- for example, parity is not learnable with a polynomial number statistical queries.

I am not aware of results of the form you ask, but perhaps we are missing something obvious...