<p>The SQ model was made to analyze noise tolerant learning -- namely an algorithm that works by making statistical queries will work under classification noise.  As Aaron said, most PAC algorithms that we have turn out to have equivalents in the SQ model.  The one exception is Gaussian elimination, which is used in learning parities (one can even use <a href="http://arxiv.org/pdf/cs/0010022">a clever application of it</a> to learn log(n)loglog(n) size parities in the classification noise model).  We also know that parities cannot be learned with statistical queries, and it turns out most interesting classes like decision trees can simulate parity functions.  So, in our quest to get PAC learning algorithms for many interesting classes (like decision trees, DNF, etc.), we know we need fundamentally new learning algorithms that don't work in the statistical query model.</p>

CC BY-SA 2.5
2010-11-17T02:40:46.957Z
Interesting. Do you have a reference that parities can not be learned in SQ model ?
Mohammad Alaggan
CC BY-SA 2.5
2010-11-17T06:09:56.650Z
it was proven by Kearns in his original paper defining the model: http://portal.acm.org/citation.cfm?doid=293347.293351 and then shown again by Blum et al where they defined the SQ dimension of a class http://portal.acm.org/citation.cfm?id=195058.195147 . Basically, the argument goes like this: parities are "pairwise independent" w.r.t. the uniform distribution, so you pretty much have to guess the correct parity to learn anything, and there a lot of possible parities...
Lev Reyzin
CC BY-SA 2.5
2010-11-15T16:25:31.513Z
2010-11-15T16:25:31.513Z
Lev Reyzin
<p>I'd like to clarify Aaron's response slightly. Nearly every agnostic algorithm (once again, except for anything that uses Gaussian elimination) can be made to work in the SQ model. Naturally, agnostic learning is harder than non-agnostic learning, but this is an independent question.</p>

CC BY-SA 3.0
2011-06-16T17:54:10.290Z
Yes, thats true. The point I wanted to make is that agnostic learning might be hard for two distinct reasons: computational complexity, and sample complexity. In the PAC model, sample  complexity is not a problem: Simply take VCDIM$/\epsilon^2$ examples and find the hypothesis with lowest empirical error (this might be computationally hard of course). In the SQ model, even sample complexity is a problem. Even ignoring computational efficiency, you need a superpolynomially large dataset to learn disjunctions on d variables, as compared to a dataset that is merely linear in d for PAC learning.
Aaron Roth
CC BY-SA 3.0
2011-06-15T21:28:52.453Z
2011-06-15T21:28:52.453Z
user5591
<p>Almost every algorithm that works in the PAC model (with the exception of parity learning algorithms) can be made to work in the SQ model. See e.g. this paper of Blum et al. in which several popular algorithms are translated into their SQ equivalents (<a href="http://portal.acm.org/citation.cfm?id=1065184">Practical Privacy: the SuLQ framework</a>). The paper is in principle concerned with "privacy", but you can ignore that -- it is really just implementing algorithms with SQ queries. </p>

<p>Agnostic learning, on the other hand, is much harder in the SQ model: computational issues aside (though these are important), the sample complexity required for agnostic learning is roughly the same as that required for exact learning, if you actually have access to the data points. On the other hand, agnostic learning becomes much harder in the SQ model -- you will usually need to make superpolynomially many queries, even for classes as simple as monotone disjunctions. See this paper by Feldman (<a href="http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5438617">A complete characterization of statistical query learning with applications to evolvability</a>) or this recent paper by Gupta et al. (<a href="http://www.cs.cmu.edu/~alroth/SQconjunctions.html">Privately Releasing Conjunctions and the Statistical Query Barrier</a>)</p>

CC BY-SA 2.5
2010-11-15T08:28:37.230Z
really nice answer Aaron :) many thanks :)
Deyaa
CC BY-SA 2.5
2010-11-14T22:58:28.203Z
2010-11-14T23:05:31.290Z
2010-11-14T23:05:31.290Z
Aaron Roth
<p>I asked this <a href="https://stats.stackexchange.com/questions/4513">question</a> in cross validated Q&amp;A but seems that it is related to CS much more than Statistics.</p>

<p>Can you give me examples of machine learning algorithms which learn from the statistical properties of the dataset not the individual observations themselves i.e. employ the <a href="http://portal.acm.org/citation.cfm?doid=293347.293351" rel="nofollow noreferrer">statistical query model</a>?</p>

CC BY-SA 2.5
2010-11-14T21:39:47.477Z
what is the statistical query model ?
Suresh Venkat
CC BY-SA 2.5
2010-11-14T21:52:16.440Z
from Kearns paper http://portal.acm.org/citation.cfm?doid=293347.293351: "in this model a learning algorithm is forbidden to examine individual examples of the unknown target function, but is given acess to an oracle providing estimates of probabilities over the sample space of random examples.". sorry if it is not obvious, I've updated my question with the link to the paper
Deyaa
<lg.learning><machine-learning>
Statistical query model algorithms?
Deyaa
# Statistical query model algorithms?

(Asked by: username_0 on 2010-11-14)

I asked this [question](https://stats.stackexchange.com/questions/4513) in cross validated Q&A but seems that it is related to CS much more than Statistics.

Can you give me examples of machine learning algorithms which learn from the statistical properties of the dataset not the individual observations themselves i.e. employ the [statistical query model](http://portal.acm.org/citation.cfm?doid=293347.293351)?

**Tags:** lg.learning, machine-learning
> **Comments:**
> **username_1**: what is the statistical query model ?  
> **username_0**: from Kearns paper http://portal.acm.org/citation.cfm?doid=293347.293351: "in this model a learning algorithm is forbidden to examine individual examples of the unknown target function, but is given acess to an oracle providing estimates of probabilities over the sample space of random examples.". sorry if it is not obvious, I've updated my question with the link to the paper  

---

## 3 answers

### Answer by username_5 on 2010-11-14. Score: 14 | Accepted answer

Almost every algorithm that works in the PAC model (with the exception of parity learning algorithms) can be made to work in the SQ model. See e.g. this paper of Blum et al. in which several popular algorithms are translated into their SQ equivalents ([Practical Privacy: the SuLQ framework](http://portal.acm.org/citation.cfm?id=1065184)). The paper is in principle concerned with "privacy", but you can ignore that -- it is really just implementing algorithms with SQ queries.

Agnostic learning, on the other hand, is much harder in the SQ model: computational issues aside (though these are important), the sample complexity required for agnostic learning is roughly the same as that required for exact learning, if you actually have access to the data points. On the other hand, agnostic learning becomes much harder in the SQ model -- you will usually need to make superpolynomially many queries, even for classes as simple as monotone disjunctions. See this paper by Feldman ([A complete characterization of statistical query learning with applications to evolvability](http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5438617)) or this recent paper by Gupta et al. ([Privately Releasing Conjunctions and the Statistical Query Barrier](http://www.cs.cmu.edu/~alroth/SQconjunctions.html))

> **Comments:**
> **username_0**: really nice answer Aaron :) many thanks :)  

---

### Answer by username_2 on 2010-11-15. Score: 7

The SQ model was made to analyze noise tolerant learning -- namely an algorithm that works by making statistical queries will work under classification noise. As Aaron said, most PAC algorithms that we have turn out to have equivalents in the SQ model. The one exception is Gaussian elimination, which is used in learning parities (one can even use [a clever application of it](http://arxiv.org/pdf/cs/0010022) to learn log(n)loglog(n) size parities in the classification noise model). We also know that parities cannot be learned with statistical queries, and it turns out most interesting classes like decision trees can simulate parity functions. So, in our quest to get PAC learning algorithms for many interesting classes (like decision trees, DNF, etc.), we know we need fundamentally new learning algorithms that don't work in the statistical query model.

> **Comments:**
> **username_3**: Interesting. Do you have a reference that parities can not be learned in SQ model ?  
> **username_2**: it was proven by Kearns in his original paper defining the model: http://portal.acm.org/citation.cfm?doid=293347.293351 and then shown again by Blum et al where they defined the SQ dimension of a class http://portal.acm.org/citation.cfm?id=195058.195147 . Basically, the argument goes like this: parities are "pairwise independent" w.r.t. the uniform distribution, so you pretty much have to guess the correct parity to learn anything, and there a lot of possible parities...  

---

### Answer by username_4 on 2011-06-15. Score: 5

I'd like to clarify Aaron's response slightly. Nearly every agnostic algorithm (once again, except for anything that uses Gaussian elimination) can be made to work in the SQ model. Naturally, agnostic learning is harder than non-agnostic learning, but this is an independent question.

> **Comments:**
> **username_5**: Yes, thats true. The point I wanted to make is that agnostic learning might be hard for two distinct reasons: computational complexity, and sample complexity. In the PAC model, sample  complexity is not a problem: Simply take VCDIM$/\epsilon^2$ examples and find the hypothesis with lowest empirical error (this might be computationally hard of course). In the SQ model, even sample complexity is a problem. Even ignoring computational efficiency, you need a superpolynomially large dataset to learn disjunctions on d variables, as compared to a dataset that is merely linear in d for PAC learning.  

---

