<p>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 <a href="https://www.cis.upenn.edu/%7Emkearns/papers/sq-journal.pdf" rel="nofollow noreferrer">Kearns (1998)</a>.</p>
<p>For example, consider a concrete problem such as nonparametric density estimation. <strong>If I have a lower bound on the number of SQ queries required to learn a density <span class="math-container">$f$</span>, does this imply anything about the number of IID queries required to learn <span class="math-container">$f$</span>?</strong> (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.)</p>
<p>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.</p>
<p><strong>A simpler question:</strong> Are there <em>known</em> 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?</p>

CC BY-SA 4.0
2022-08-12T18:32:12.510Z
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).
Vitaly
CC BY-SA 4.0
2022-08-23T14:41:22.740Z
@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.)
student3365
<machine-learning><lg.learning><st.statistics><pac-learning><sample-complexity>
Relationship between statistical query lower bounds and "traditional" iid sampling lower bounds
student3365
# Relationship between statistical query lower bounds and "traditional" iid sampling lower bounds

(Asked by: username_0 on 2022-08-11)

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)](https://www.cis.upenn.edu/%7Emkearns/papers/sq-journal.pdf).

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?

**Tags:** machine-learning, lg.learning, st.statistics, pac-learning, sample-complexity
> **Comments:**
> **username_1**: 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).  
> **username_0**: @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.)  

---

## 0 answers

