<p>As title, I saw some <a href="https://www.cs.ox.ac.uk/people/varun.kanade/docs/computational-FK12.pdf" rel="nofollow noreferrer">paper</a> mentioned they are equivalent, but I'd wonder how to prove they are? is it something to do with PAC as SQ is a restricted version of PAC?</p>

CC BY-SA 4.0
2020-12-01T21:59:17.367Z
Did you see there references (Bshouty and Feldman, 2001; Feldman, 2008) given in that paper?
Aryeh
CC BY-SA 4.0
2020-12-02T00:23:37.490Z
Yes. However, [Feldman 2008](https://people.mpi-inf.mpg.de/~mehlhorn/SeminarEvolvability/p619-feldman.pdf) seems Lemma 3.1 touches a bit on this topic, but not quite...
As for [Bshouty and Feldman 2001](https://www.jmlr.org/papers/volume2/bshouty02a/bshouty02a.pdf) I thought it could be lemma 30, but I am not really sure how is it related.
Yo Ruson
<pac-learning>
Is statistical query learning equivalent to correlational statistical query learning given a fixed distribution?
Yo Ruson
# Is statistical query learning equivalent to correlational statistical query learning given a fixed distribution?

(Asked by: username_0 on 2020-12-01)

As title, I saw some [paper](https://www.cs.ox.ac.uk/people/varun.kanade/docs/computational-FK12.pdf) mentioned they are equivalent, but I'd wonder how to prove they are? is it something to do with PAC as SQ is a restricted version of PAC?

**Tags:** pac-learning

> **Comments:**
> **username_1**: Did you see there references (Bshouty and Feldman, 2001; Feldman, 2008) given in that paper?  
> **username_0**: Yes. However, [Feldman 2008](https://people.mpi-inf.mpg.de/~mehlhorn/SeminarEvolvability/p619-feldman.pdf) seems Lemma 3.1 touches a bit on this topic, but not quite... As for [Bshouty and Feldman 2001](https://www.jmlr.org/papers/volume2/bshouty02a/bshouty02a.pdf) I thought it could be lemma 30, but I am not really sure how is it related.  

---

## 0 answers

