Coming from a more statistical background, it is not clear to me if or how lower bounds in the statistical query (SQ) model imply anything useful about traditional learning problems with iid samples (lets call this model IID). The SQ model I am referring to here is the SQ model from Kearns (1998).

For example, consider a concrete problem such as nonparametric density estimation. If I have a lower bound on the number of SQ queries required to learn a density $f$, does this imply anything about the number of IID queries required to learn $f$? (Note: I don't care about this specific problem, I am just using it as an example. Of course we already know what the IID lower bounds for this problem are.)

It is clear that we can simulate an SQ oracle with IID, just by sampling (see p. 6 of the linked paper). But the other way around is not so clear to me and I have not found this discussed in the literature anywhere.

A simpler question: Are there known problems for which there is a (unimprovable) gap between SQ and IID lower bounds? For example, is there a problem that requires super-polynomially many SQ queries, but only polynomially many IID queries?

  • 1
    $\begingroup$ The paper of Kearns (1998) you cite answers the question you ask by giving the example of parity learning. And a remark, MCMC is not needed to simulate SQ queries using random samples (as also shown already in the paper of Kearns). $\endgroup$
    – Vitaly
    Commented Aug 12, 2022 at 18:32
  • $\begingroup$ @Vitaly Great point, I forgot about that example which indeed answers the second part. I am still curious if there are any known implications SQ => IID. (And you're right about MCMC, that was a slip. I just meant random sampling.) $\endgroup$ Commented Aug 23, 2022 at 14:41


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.