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)?